WatSON Composite Ingredients

Simple ingredients represent a single value, like a number or a string. My last post covered the basic details for simple ingredients. Composite ingredients are designed to contain other ingredients or multiple values. Some are used to change how things are written to the file, like the Compressed Ingredient. Others are designed to provide structure to the file like the Container and Map Ingredients.

For simplicity, I am listing only the 8-bit sizes for the Ingredients, but the structure is valid for any size type.

Byte Reduction Ingredients

The library and compressed ingredients are designed to reduce the number of bytes required by data stored in WatSON format.

Library ingredients contain strings that are used elsewhere in the document. This primarily applies to keys for the map ingredient, but also applies to bytes ingredients. Libraries use a zero based index (the first element is index zero), but the string at index zero is always an empty string. The empty string is because the index zero is reserved.. See the map and byte ingredients for more details.

Library scope is going to be mentioned in the description for byte and map ingredients. Right now I am defining that as the nearest library in a parent container, although scope should get its own dedicated post in the future.

<library-ingredient> ::= ‘L’ <8-bit-size> <empty-string-ingredient> <string-ingredient>*

Compressed ingredients contain a single ingredient that has been compressed. I toyed around with the idea of making them a container as well, but I felt the single ingredient child would make implementations more straightforward at the cost of a few extra bytes.

I am thinking of using Snappy for the compression method. I haven't decided how flexible that will be in the future.

<compressed-ingredient> ::= ‘Z’ <8-bit-size> <data>*

Structure Ingredients

Container and map ingredients are designed for nesting and providing structure a WatSON document.

A container contains other ingredients. It is used for nesting and grouping ingredients. Think of it as a vector or list. Nothing inside a WatSON document references positions in a container. Order will probably be important. especially with regard to library and header ingredients. 

<container-ingredient> ::= ‘C’ <8-bit-size> <ingredient>*

A map ingredient is a key value structure. The keys are 32 bit unsigned integers. Positive keys reference the in scope library. A key of zero is reserved for an empty string key. I think I will be using that key as optional metadata, but I haven’t thought through what and how that metadata will be used. That will probably get a dedicated post in the future.

<map-ingredient> ::= ‘M’ <8-bit-size> <map-data>*
<map-data> ::= <uint32> <ingredient>

Extension Ingredients

Binary and header ingredients change how a parser should interpret WatSON data that follows.

Binary ingredients store opaque binary data. A positive marshal hint is a reference into the in scope library. A marshal hint of zero is reserved for an undefined marshal hint. I am thinking of the marshal hint as a place to store the run-time type. WatSON doesn’t specify anything about the data.

<bytes-ingredient> ::= ‘B’ <8-bit-size> <marshall-hint> <data>*

Headers are string based maps that contain information about the file contents. They are optional ingredients, and used to document requirements for parsing the rest of the file. An example would be the character encoding for strings, although I am leaning towards utf-8 being mandatory. They can also be used to document schema information or metadata like the program that generated the file, etc.

<header-ingredient> ::= ‘H’ <size> <header-data>*
<header-data> ::= <c-string> <ingredient>

I like how the format is coming together. I have my incomplete reference implementation foundation, as rough as it is, checked in on github.

WatSON Data Types.

In my last post, I mentioned what I was calling the type marker:

<Type-marker> ::= <size-type> <data-type>

Size Type		Data Type
b7	b6	b5	b4	b3	b2	b1	b0

That post was dedicated to the highest 2 bits of the Type-Marker; the two bits that represent the size-type. This post is dedicated to the lower 6 bits: the data type. An MP4 atom uses 4 bytes to represent the data type (atom name). The size makes sense given the large, dynamic ecosystem that the specification is trying to support. Interestingly, the convention is not to describe the atom names as 4 byte integers. They are almost always referred to by their ascii representation. For example, the "Movie" atom is "\x6D\x6F\x6F\x76", which, if treated as a character string is "moov" (pronounced "Moo-V").

I like the idea of numeric identifiers having useful printed representations, so I copied that concept into the type markers for WatSON. For example, the single byte types of null, false, and true will be represented as the following:

<empty-false-type> ::= '0' ;; st == 00, dt == 110000
<empty-true-type> ::= '1' ;; st == 00, dt == 110001
<empty-null-type> ::= '?' ;; st == 00, dt == 111111

This manages to combined the size type and the data type into single character type marker that matches the convention for the type. This only holds true in the most common representation. Someone could create a short false type with an 8-bit length, similar to the following.

<short-false-type> ::= 'p' ;; st == 01, dt == 110000

The character 'p' doesn't represent false for me, but I see no reason to create rules preventing that ingredient. Using 2 bytes to store false is a waste of space. but it should not break parsing.

Going with this expectation about common sizing, I selected the following values for the lower six bits:

<simple-data-type> ::= 0x30 ;; False type
  | 0x31 ;; True type
  | 0x3F ;; Null type
  | 0x24 ;; Float type
  | 0x29 ;; 32-bit signed integer type
  | 0x2C ;; 64-bit signed integer type
  | 0x35 ;; 64-bit unsigned integer type
  | 0x22 ;; Bit-flags type
  | 0x33 ;; String type
  | 0x08 ;; Header type
  | 0x0C ;; Library type
  | 0x03 ;; Container type
  | 0x1A ;; Compressed container.
  | 0x0D ;; Map type
  | 0x02 ;; User defined binary type

I break them into two categories: empty and short. I’ll start by repeating the empty ingredient types from above:

<false-ingredient> ::= '0'
<true-ingredient> ::= '1'
<null-ingredient> ::= '?'

Then I have the simple short ingredients:

<double-ingredient> ::= ‘f’ ‘\x0A' <8-bytes-data>
<32-bit-int-ingredient> ::= ‘i’ ‘\x06' <4-bytes-data>
<64-bit-int-ingredient> ::= ‘l’ ‘\x0A’ <8-bytes-data>
<64-bit-uint-ingredient> ::= ‘u’ ‘\x0A’ <8-bytes-data>
<bit-flags-ingredient> ::= ‘b’ <8-bit-size> <data>*
<string-ingredient> ::= ’s’ <8-bit-size> <data>*

Last, I have the composite ingredients. I went with short sizes on these, mostly because of the lack of diversity above 127. My hand crafted WatSON documents are all less than 256 bytes, so the short sizing may be biased or flawed.

<header-ingredient> ::= ‘H’ <8-bit-size> <data>*
<library-ingredient> ::= ‘L’ <8-bit-size> <data>*
<container-ingredient> ::= ‘C’ <8-bit-size> <data>*
<compressed-ingredient> ::= ‘Z’ <8-bit-size> <data>*
<map-ingredient> ::= ‘M’ <8-bit-size> <data>*
<bytes-ingredient> ::= ‘B’ <8-bit-size> <data>*

I hope no one ever has to hand craft a file or see the characters, but I like that they make sense in smaller documents. For larger documents, you are probably going to need a tool or program to keep track of structure, so the letters on the composite ingredients are less important..

I think the next post will be focused on the composite ingredients. Specifically the containers.

WatSON Size and Type Specification

In trying to understand where I am going with the WatSON specification, it is useful to have some background on the MP4 file specification. Atomic Parsley provides a mostly easy to digest background on MP4 atoms.

In the first 8 bytes of every atom, you have enough context to either skip over the atom, or dive deeper into the atom. I wanted to create a specification that allowed the same type of flexibility. A specification where the fundamental component of the file format is simple, but easily extensible. I am trying to keep the size of the format down as well, so I wanted to come up with a model that lets me represent types like "true" and "false" in a single byte.

Note, the names used after here are just place holders. I have been more interested in the format concept than naming at this point:

<Ingredient> ::= <Type-Marker> [<Size> <data>*]

Every ingredient starts with a Type-Marker. Type Markers are a single byte with two components. The 6 lowest bits determine the data-type. This would be similar to the atom name in MP4 files. It basically tells the parser what to expect inside the data section.

The highest 2 bits of the Type-Marker represent the size-type. The size type describes how large the Size value will be. MP4 doesn't have a similar concept. Sizes are always 4 bytes long, and special sizes are used to communicate non-standard sizes.

Size Type		Data Type
b7	b6	b5	b4	b3	b2	b1	b0

The size type is basically a way to help reduce the overhead of smaller ingredients. Smaller types, like numbers, use 8-bit sizes, while larger types like long-strings and big-containers use a 64-size. Here is an example how a string ingredient could use the different size types.

<empty-string> ::= '\x33' ; st bits == 00, dt bits == 110011
<short-string> ::= 's' <8-bit-size> <data>* ; st == 01, dt == 110011
<med-string> ::= '\xB3' <16-bit-size> <data>* ; st == 10, dt == 110011
<long-string> ::= '\xF3' <64-bit-size> <data>* ; st == 11, dt == 110011

The overhead for storing different types is 1 byte, 2 bytes, 3 bytes and 9 bytes. An empty string is represented by a single byte, with no size data following. The other string types have a required size component of various lengths. String data in WatSON will not be null terminated.

For the most common cases, this uses less space than storing a string in bson format, which has a fixed 6 byte overhead (1 for type, 4 for size, 1 for null-terminator). For strings longer than 65k, it has a larger 9 byte overhead, but can also store strings significantly larger than 4 gigabytes.

I haven't decided how I want to flag compression requirements on 64-bit sizes. I was thinking of maybe having the 64-bit size be signed (negative being compressed), or maybe reserving the highest bits for special flags like encryption and compression. Another idea I am toying around with is a "compressed container", such that Ingredients themselves aren't compressed, but they exist in a container that is compressed.

All of this is draft ideas at this point, but I am looking for some feedback.

Something to replace BSON.

I have been working on my own implementation of the BSON Spec for about 3 years now. I have come to the conclusion that the BSON design seems haphazard and organic. The parsing is harder and more intensive than it should be. Scanning it is poorly designed. The specific types require too much knowledge to handle properly. They even continue making small changes to the specification, but not bumping the version number.

In order to solve my problems with it, I have decided to create my own specification and call it WatSON. Well, technically, I am calling it “왓슨”, but I don’t know how to type that on my English (US) keyboard.

Here are some of my design goals.

• Keys are defined at the start of the document to eliminate repetitive keys.

• Arrays don’t have keys at all.

• Types and Objects are connected, rather than being separated by the key name.

• Containers and strings have 64 bit size markers. Other types have 1 byte size markers. The format must have a simple rule for skipping elements that don’t match a known type.

• Document format is little-endian.

• String formats support Snappy compression.

• Format supports header information to influence how the document is read.

A lot of my influence in the design is coming from dealing with atoms in the MP4 file format. 

For more detail on how things are coming together:

• WatSON Size and Type Specification
• WatSON Data Types
• WatSON Composite Ingredients
• ... More to come