2009/8/4 Marc Feeley feeley@iro.umontreal.ca:
On 3-Aug-09, at 4:06 PM, James Long wrote:
I also studied Gambit's serialization mechanisms using object->u8vector for compressing models and speeding up loading times.
Nice! I like your binary format where you use a single byte to indicate the length of the binary encoding of the *length* of the binary encoding of the object!
This sounds like a re-imagining of some of the ASN.1 encoding conventions. IIRC, there were two different length encodings that could be used for a given data field, one applied to any data type and the other (implicit length) only applied to structured types and relied on the components of the structure to all have their lengths completely specified.
The two explicit length methods were a length of length encoding and a string-based length encoding. In the length of length encoding, if the length is less than 128, you just use a single byte, with the high bit set to zero. Otherwise the high bit is set to one, and the low seven bits set to the length of length. The length is then encoded in that many bytes.
The encoding of ASN.1 tags was also interesting because they could potentially be infinitely long. IIRC (again) the first octet reserved 5 bits for the tag ID. If the tag ID was greater than 30, the 5 reserved bits were set to 31 (all ones) and then the low seven bits of the octets following the first tag octet were deemed to be part of the tag value if the high bit of the octet was set to 1. the last tag octet had the high bit set to 0 and the low-order bits were just thrown away.
Just a wee bit of historical context :)
david