= 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 Writeup about how writing and reading structured data is mostly done manually. === Motivation Writeup how boring it is to write similar code each time when trying to read or write structured data. How easy it is to make mistakes or cause unportable and unoptimized code. Write how filespec can help with reverse engineering and figuring out data structures, how it can be used to generate both packers and unpackers giving you powerful tools for working with structured data. === Overview Goal of Filespec is to document the structured data and relationships within, so the data can be understood and accessed 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[] ---- === Keywords |============================================================================= | struct _name_ { ... } | Declares structured data | enum _name_ { ... } | Declares enumeration | union _name_ (_var_) { ... } | Declares union, can be used to model variants |============================================================================= .Struct member declaration syntax Parenthesis indicate optional fields ---- member_name: member_type (array ...) (| filter ...) (visual hint); ---- === Types Basic types to express binary data. |================================================================ | struct _name_ | Named structured data (Struct member only) | enum _name_ | Value range is limited to the named enumeration | u8, s8 | Unsigned, signed 8bit integer | u16, s16 | Unsigned, signed 16bit integer | u32, s32 | Unsigned, signed 32bit integer | u64, s64 | Unsigned, signed 64bit integer |================================================================ === Arrays Valid values that can be used inside array subscript operation. |================================================= | _expr_ | Uses result of expression as array size | \'str' | Grow array until occurance of str | $ | Grow array until end of data is reached |================================================= .Reading length prefixed data ---- num_items: u16 dec; items: struct item[num_items]; ---- .Reading null terminated string ---- cstr: u8['\0'] str; ---- .Reading repeating pattern ---- pattern: struct pattern[$]; ---- === 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) |======================================================================== | matches(_str_) | Data matches _str_ | 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 ---- header: u8[4] | matches('\x7fELF') str; ---- .Decoding strings ---- name: u8[32] | encoding('sjis') str; ---- .Decompressing data ---- data_sz: u32; data: u8[$] | 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. |=========================================== | 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. ---- len: u16; str: u8[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. ---- decompressed_sz: u32 dec; data: u8[$] | compression('zlib', decompressed_sz); ---- === Explicit Relationships Sometimes we need to form explicit relationships when the structure is more complicated. TODO: When we can actually model FFXI string tables correctly, it will be a good example. == 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 follows a standard pattern, and isn't invalid. 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. TODO: Document bytecode operations and the predictable pattern here === 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.