biniou-format.txt

                              The Biniou format
                              -----------------

Contents:

1. Grammar
2. Tags
3. Fixed-length types
4. Vints
5. Field and variant name hashing
6. Numeric variants



1. Grammar


  TAGVAL ::= TAG VAL    // A biniou value with its matching tag

  VAL ::= ATOM
        | ARRAY
        | TUPLE
        | RECORD
        | NUM_VARIANT
        | VARIANT
        | TABLE
        | SHARED

  ATOM ::= unit     // 0, using one byte
         | bool     // 0 for false, 1 for true, using one byte
         | int8     // 1 arbitrary byte
         | int16    // 2 arbitrary bytes
         | int32    // 4 arbitrary bytes
         | int64    // 8 arbitrary bytes
         | float64  // IEEE-754 binary64
         | uvint    // unsigned variable-length int
         | svint    // signed variable-length int
         | STRING   // sequence of any number of bytes prefixed by its length

  STRING ::= LENGTH byte*
  ARRAY ::= LENGTH (TAG VAL* )?
  NUM_VARIANT ::= NUM_VARIANT_TAG TAGVAL?
  VARIANT ::= VARIANT_TAG TAGVAL?
  TUPLE ::= LENGTH TAGVAL*
  RECORD ::= LENGTH (FIELD_TAG TAGVAL)*
  TABLE ::= LENGTH (LENGTH (FIELD_TAG TAG)* (VAL* )* )? // list of records

  SHARED ::= OFFSET TAGVAL?  // Value given iff the offset is 0.
                             // Otherwise, the offset indicates the
                             // relative position to the left of a SHARED
                             // to which we are redirected.

  TAG ::= int8               // identifies a type of node
  LENGTH ::= uvint
  OFFSET ::= uvint
  NUM_VARIANT_TAG ::= int8   // 0-127 if no argument, 128-255 if has argument
  VARIANT_TAG ::= int32      // first bit indicates argument, then 31-bit hash
  FIELD_TAG ::= int32        // 31-bit hash (first bit always 1)



2. Tags


Tags indicate the shallow structure of any biniou value.

The biniou format is such that the tag of any value is known
from the input data.  This allows decoding biniou data as a tree
where each node represents a biniou value, without requiring external
type information.

The tag values for the various kinds of biniou values are:

    Type of value     Tag
    ---------------------------
    bool              0
    int8              1
    int16             2
    int32             3
    int64             4
    float64           12
    uvint             16
    svint             17
    string            18
    ARRAY             19
    TUPLE             20
    RECORD            21
    NUM_VARIANT       22
    VARIANT           23
    unit              24
    TABLE             25
    SHARED            26



3. Fixed-length types


Atomic values of type unit, bool, int8, int16, int32, int64 and float64
represent arbitrary sequences of 1, 2, 4 or 8 bytes.

In order to make the visualization of data easier,
the default interpretation of these values shall be used:

    Length
    in bytes   Type of value   Default interpretation
    ---------------------------------------------------------------------
    1          unit            0 represents the unit value
    1          bool            0 represents false, 1 represents true
    1          int8            unsigned 8-bit int
    2          int16           big endian unsigned 16-bit int
    4          int32           big endian unsigned 32-bit int
    8          int64           big endian unsigned 64-bit int
    8          float64         big endian IEEE-754 binary64 (double)



4. Vints


Vints are a variable-length, byte-aligned representation of
positive integers.

A vint is represented by a sequence of bytes from least significant
to most significant.  In all the bytes except the last one, the
high bit is set to 1 and indicates that more bytes follow.
The high bit of the last byte is set to 0.
The remaining 7 bits in each byte represent data.

Here is the representation of some sample values:

           0xxxxxxx
  0        00000000
  1        00000001
  2        00000010
  127      01111111

           1xxxxxxx 0xxxxxxx
  128      10000000 00000001
  129      10000001 00000001
  255      11111111 00000001
  256      11111111 00000010
  16383    11111111 01111111

           1xxxxxxx 1xxxxxxx 0xxxxxxx
  16384    10000000 10000000 00000001
  16385    10000001 10000000 00000001


Positive integers can be represented by standard vints.
We call this representation unsigned vint or uvint.

Arbitrary integers can also be represented using vints, after mapping
to positive integers.  We call this representation signed vint or svint.
Positive numbers and 0 are mapped to even numbers and negative numbers
are mapped to odd positive numbers.  Here is the mapping for
small numbers:

    vint              unsigned	            signed
    representation    interpretation	    interpretation
		      (uvint)               (svint)	
    0xxxxxx0
    00000000          0	             	    0
    00000010          2	             	    1
    00000100          4	                    2
    00000110          6	                    3

    0xxxxxx1					
    00000001          1	                    -1
    00000011          3	                    -2
    00000101          5                     -3



5. Field and variant name hashing


Record field names and variant names are represented by a
31-bit tag which must be a hash of the name.  The following
hash function must be used:

  hash(s):
    h <- 0
    for i = 0 to length(s) - 1 do
      h <- 223 * h + s[i]
    done
    h <- h mod 2^31
    return h

For example, hash("Hello") is 0x37eea2f2.

A full field tag or variant tag is made of 32 bits.
The first bit is 0 for variants without an argument, and 1 for
variants with an argument or record fields.
The remaining 31 bits are the hash of field or variant name described above.



6. Numeric variants


Numeric variants are a more compact alternative to variants using
32-bit hash-based tags since the tag of numeric variants
takes only one byte.

The most common use of numeric variants is for an option type.
A value of type option is either None or Some value,
e.g. None, Some 123 or Some 0.
This allows to represent undefined values without
reserving a special value called null or undefined.