= Filespec Structured Data Modelling Language User Guide Jari Vetoniemi Filespec Version 0.1 :toc: :toclevels: 3 :numbered: .License Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. == Introduction === Abstract Often while developing a software, it has to understand and access some sort of binary data. Often there might be a library or something that helps you with this task. However, many times these solutions are lacking or doesn't work properly on different platforms. Sometimes there might not be solution at all for your particular environment and you have to do it yourself again. Or even if you are creating a new format, there's lack of tools to prototype it, and every change needs refactoring of the packing/unpacking code. === Motivation Filespec lets you describe the format itself, so that you can generate portable and effecient code for reading and writing the specified data in a simple way. It also provides bunch of utilities that helps you develop formats, or even used as a tool for reading and writing binary files. === Overview Goal of Filespec is to document the structured data and relationships within, so the data can be understood completely. === Related Work ==== Kaitai Kaitai is probably not very well known utility, that has similar goal to Filespec. Explain cons: - Depends on runtime - Can only model data which runtime supports (only certain compression/decompression available for example, while in Filespec filters can express anything) - Mainly designed for generated code, not general utility - Uses YAML for modelling structured data which is quite wordy and akward ///////////////////////////////// How Filespec is different from Kaitai. Explain the uses cases that would be difficult or impossible on Kaitai. ///////////////////////////////// ////////////////////// === Development Status ////////////////////// == Modelling Structured Data === Filespec Specifications Brief of Filespec specifications and syntax .Modelling ELF header ---- include::../spec/elf.fspec[] ---- === Top-level keywords Top-level keywords, they can't be used inside struct declarations. [options="header"] |======================================================== | Keyword | Description | enum { ... } | Declares enumeration | struct _name_ { ... } | Declares structured data |======================================================== === Enums ---- enum { first, second, seventh = 7, eight }; ---- === Structs ---- struct blob { type name (array ...) (| filter ...) (visual hint); }; ---- ==== Types Basic types to express binary data. [options="header"] |================================================================================================== | Type | Description | if (_expr_) { ... } else { ... } | Conditional | select (_expr_) { ... } _name_ | Tagged union | struct _name_ | Substructure | u??, s?? | Unsigned, signed ??bit integer (e.g. u8 for 8bit unsigned integer) |================================================================================================== ==== If Conditional reading/writing of fields depending on the result of _expr_. ---- u8 version; if (version >= 2) { u8 ver2_field; } if (version >= 3) { u8 ver3_field; } else { u8 removed_old_field; } ---- ==== Select Conditionally pack/unpack field depending on the result of _expr_. This is identical to tagged union, variant, etc... and generates into union in C. There may not be duplicate cases inside single select. ---- u8 type; select (type) { 0) struct string string (array ...) (| filter ...) (visual hint); 1) u1 bool; *) u32 any; } value; ---- ==== Arrays Valid expressions that can be used to define array size during declaration. [options="header"] |======================================================================== | Expression | Description | _expr_ | Result of expression | \'str' | Grow array until occurance of str in binary data | until (_expr_) | Grow array until condition has been reached |======================================================================== .Reading length prefixed data ---- u16 num_items dec; struct item items[num_items]; ---- .Reading null terminated string ---- u8 cstr['\0'] str; ---- .Reading repeating pattern until we hit stop condition ---- struct pattern pattern[until (pattern.last_block)]; ---- .Reading repeating pattern until the data ends ---- struct pattern pattern[until (false)]; ---- ==== Filters Filters can be used to sanity check and transform data into more sensible format while still maintaining compatible data layout for both packing and unpacking. They also act as documentation for the data, e.g. documenting possible encoding, compression and valid data range of member. Filters are merely an idea, generated packer/unpacker generates call to the filter, but leaves the implementation to you. Thus use of filters do not imply runtime dependency, nor they force that you actually implement the filter. For example, you do not want to run the compression filters implicitly as it would use too much memory, and instead do it only when data is being accessed. It's useful for Filespec interpreter to implement common set of filters to be able to pack/unpack wide variety of formats. When modelling new formats consider contributing your filter to the interpeter. Filters for official interepter are implemented as command pairs (Thus filters are merely optional dependency in interpeter) [options="header"] |============================================================================ | Filter | Description | matches(_str_) | Data matches _str_ | range(_min_, _max_) | Data is within the range of _min_ and _max_ | encoding(_str_, ...) | Data is encoded with algorithm _str_ | compression(_str_, ...) | Data is compressed with algorithm _str_ | encryption(_str_, _key_, ...) | Data is encrypted with algorithm _str_ |============================================================================ .Validating file headers ---- u8 header[4] | matches('\x7fELF') str; ---- .Decoding strings ---- u8 name[32] | encoding('sjis') str; ---- .Decompressing data ---- u32 data_sz; u8 data[until (false)] | compression('deflate', data_sz) hex; ---- ==== Visual hints Visual hints can be used to advice tools how data should be presented to human, as well as provide small documentation what kind of data to expect. [options="header"] |=========================================== | Hint | Description | nul | Do not visualize data | dec | Visualize data as decimal | hex | Visualize data as hexdecimal | str | Visualize data as string | mime/type | Associate data with media type |=========================================== == Relationships To keep Filespec specifications 2-way, that is, structure can be both packed and unpacked, specification has to make sure it forms the required relationships between members. Compiler has enough information to deduce whether specification forms all the needed relationships, thus it can throw warning or error when the specification does not fill the 2-way critera. === Implicit Relationships Implicit relationships are formed when result of member is referenced. For example using result of member as array size, or as a filter parameter. .Array relationship In packing case, even if _len_ would not be filled, we can deduce the correct value of _len_ from the length of _str_ if it has been filled. We can also use this information to verify that length of _str_ matches the value of _len_, if both have been filled. ---- u16 len; u8 str[len] str; ---- .Parameter relationship In packing case, the same rules apply as in array relationship. Implicit relationship is formed between _decompressed_sz_ member and compression filter. ---- u32 decompressed_sz dec; u8 data[until (false)] | compression('zlib', decompressed_sz); ---- == Implementation === Compiler Compiler is implemented with Ragel. It parses the source and emits bytecode in a single pass. The compiler is very simple and possible future steps such as optimizations would be done on the bytecode level instead the source level. === Validator Validator takes the output of compiler and checks the bytecode for validity and that it follows a standard pattern. Having validator pass simplifies the code of translators, as they can assume their input is valid and don't need to do constant error checking. It also helps catch bugs from compiler early on. === Bytecode The bytecode is low-level representation of Filespec specification. It's merely a stack machine with values and operations. To be able to still understand the low-level representation and generate high-level code, the bytecode is guaranteed to follow predictable pattern (by validator). To make sure all source level attributes such as mathematical expressions can be translated losslessly to target language, the bytecode may contain special attributes. [options="header"] |===================================== | Opcode | Decimal | Description | OP_ADD | 0 | a + b | OP_SUB | 1 | a - b | OP_MUL | 2 | a * b | OP_DIV | 3 | a / b | OP_MOD | 4 | a % b | OP_BIT_AND | 5 | a & b | OP_BIT_OR | 6 | a \| b | OP_BIT_XOR | 7 | a ^ b | OP_BIT_LEFT | 8 | a << b | OP_BIT_RIGHT | 9 | a >> b |===================================== === Translators Translators take in the Filespec bytecode and output packer/unpacker in a target language. Translators are probably the best place to implement domain specific and language specific optimizations and options. === Interpreters Interpreters can be used to run compiled bytecode and use the information to understand and transform structured data as a external utility. For example it could give shell ability to understand and parse binary formats. Or make it very easy to pack and unpack files, create game translation tools, etc... Interpreters can also act as debugging tools, such as visualize the model on top of hexadecimal view of data to aid modelling / reverse engineering of data.