Extensible Binary Meta-format

Gas Extensible Binary Meta-Format Blanton Black

Blanton Black • site: http://github.com/kuro/gas

1

Table of Contents

Gas!

2

Concept

2

Use Cases

2

Design Features

3

Extensibility

3

Portability

3

Number Encoding

4

Big Number Potential

Observations

4

5

Data Types

5

Performance

5

Integrity

5

Blanton Black • site: http://github.com/kuro/gas

1

Gas Extensible Binary Meta-Format CONCEPT Gas1 is an extensible binary container format. It is designed as a light-weight binary alternative to XML. Gas is a chunk based protocol format. Each chunk has an id, attributes, and a payload. Chunks for a tree. A chunk may have up to one parent, and any number of children. Unlike other chunk formats, such as IFF2, Gas removes all fixed fields. Instead, Gas uses a variable length number encoding, derived from EBML 3. Unlike EMBL, however, Gas lacks even basic type knowledge.

USE CASES

Gas was originally written to replace fixed network protocols. The original C implementation is designed to run well on any limited or embedded device that provides enough memory to build the trees. Meanwhile, Gas has proved useful for a variety of applications, including, but not limited to: - Network Communication Protocols - File Formats - Multimedia Containers (images, video, audio, etc.)

1 http://github.com/kuro/gas 2 http://en.wikipedia.org/wiki/Interchange_File_Format 3 http://ebml.sourceforge.net/

- Graphical Mesh Data Consider gas for a network protocols. For a minimal increase in bandwidth, it becomes possible to specify a protocol that can grow as necessary. Need a new field? Add a new attribute. And of course, adding an attribute does not break preexisting implementations. Next, consider video games. Unlike XML, Gas does not require escaping , or otherwise converting, binary data. Therefore, vertex information, for example, can be lifted out of the chunk and submitted directly to the graphics system.

DESIGN FEATURES

Extensibility The design philosophy necessitates that any use of gas define and adhere to its own conventions. In fact, Gas has zero knowledge of data types, such as floats, strings, or integers. As such, if required by the system, adding halfs4 to the specification does not require second-class status. Instead, everything from chunk IDs, to attribute keys and values, to payloads, are all treated as opaque binary blobs. The advantage, however, is that agreeing upon a field’s data type allows the application to quickly graft data into place. Furthermore, as architectures evolve over time, gas should remain relevant as long as computing systems remain binary and byte based. One should not worry about whether the protocol will work on 16, 32, 64, or 128bit architectures, and beyond. The only consideration is that all involved platforms adhere to the lowest common denominator within the specific system. Portability By default, Gas uses a given platform’s long type as its unsigned number format. This allows for the potential for overflow when a 64bit machine passes a large yet valid number to a peer where the largest data type is only 2 bytes. However, this is were application engineering comes in.

4 http://openexr.com

Also, there is no notion of endian conventions. Instead, number encoding and decoding is performed using bit masking and bit shifting.

NUMBER ENCODING

The Gas format has only one data type. It uses a number encoding format borrowed from EMBL5, which uses the minimum space required. Possible gas encoding lengths for a 32bit architecture: 1

2

3

4

0 to 2^7-2

1xxx xxxx

to 2^14-2

01xx xxxx

xxxx xxxx

to 2^21-2

001x xxxx

xxxx xxxx

xxxx xxxx

to 2^28-2

0001 xxxx

xxxx xxxx

xxxx xxxx

xxxx xxxx

to 2^35-2

0000 1xxx

xxxx xxxx

xxxx xxxx

xxxx xxxx

5

xxxx xxxx

Although the above chart demonstrates what is possible on a 32bit architecture, an upper limit to a number’s size is not defined. That is to say, any given implementation is limited only by the maximum size of its long data type. Since decoding takes place via bit shifting, an excessively large number will silently overflow. Big Number Potential Consider Ruby 6. The standard ruby interpreter seamlessly converts a Fixnum to a Bignum, both subclasses of Integer, as number size necessitates. Since the pure ruby version of gas does not care whether it is working with a Fixnum or a Bignum, there is no limit to a gas encoded number when a big number implementation is involved.

5 http://ebml.sourceforge.net/specs 6 http://ruby-lang.org

OBSERVATIONS

Data Types Gas has one, and only one, data type. That is the Gas number encoding. Beyond the custom number encoding, the container’s lack of type support is intentional. As a container, Gas’ only goal is to efficiently transfer data from one location to another. Type information, then, is left as an exercise for the protocol definer. In fact, it should be relatively straightforward to build a Protocol Buffer7 type extension on top of Gas. Performance Gas is intended to be fast to parse. However, at the time of this writing, performance has not been optimized, due to the fact that Gas itself has never been a bottleneck. Gas requires an update operation before performing writes. Integrity Gas is intended as a high level protocol, typically sitting on TCP or the filesystem, for example. As such, Gas does not provide checksums. In this respect, it is similar to XML. Within the context of networks, both TCP and UDP provide their own checksum verification. Within the context of filesystems, it is assumed that what is written will be read back. Consider ZFS and friends. In the event that additional verification is necessary, the author has had success placing Gas chunks on top of custom framing. Such framing, for example, would provide start markers as well as checksums.

7 http://code.google.com/p/protobuf/