path: root/doc/fspec-guide.adoc

= Filespec Structured Data Modelling Language User Guide
Jari Vetoniemi <mailroxas@gmail.com>
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.