Skip to content

Instantly share code, notes, and snippets.

@md-5
md-5 / beat.md
Created December 12, 2012 02:51
Variable length number encoding. Taken from http://byuu.org/programming/beat/.

Variable-length number encoding

Rather than limit the maximum file size supported to 16MB (24-bit) or 4GB (32-bit), beat patches use a variable-length encoding to support any number of bits, and thus, any possible file size.

The basic idea is that we encode the lowest seven bits of the number, and then the eighth bit of each byte is a flag to say whether the full number has been represented or not. If set, this is the last byte of the number. If not, then we shift out the low seven bits and repeat until the number is fully encoded.

One last optimization is to subtract one after each encode. Without this, one could encode '1' with 0x81 or 0x01 0x80, producing an ambiguity.

Decoding is the inverse of the above process.