Variable-length quantity
By variable-length quantity (VLQ), we refer to a variety of schemes for encoding an integer in a variable number of bytes, where the required number of bytes grows as the magnitude of the integer grows. Such formats can encode arbitrarily large integers, though artificial limits are sometimes imposed.
As far as we know, there is no widely-used standard for such number formats. Each file format specification that uses them typically uses its own definition, and invents its own name.
Details
The most common VLQ formats use a variable-length base-128 scheme in which 7 bits of each byte constitute a base-128 digit, and the 8th bit indicates whether there are any more digits.
Even this simple case has a combinatorial explosion of variants:
- The flag bit could be the most significant bit, or the least significant bit.
- The flag for end-of-number could be 0, or 1.
- The most-significant block of 7 bits could come first (big-endian style), or last (little-endian style).
- If negative numbers are supported, there are several different ways to do it.
- There could be a defined maximum number of bytes. If so, then for maximal-length codes, the final byte's flag bit could be repurposed.
Instead of having one flag bit per byte, there could be one every two bytes, resulting in a base-32768 encoding.
Related formats
Among the formats that use variable-length quantities are:
- BPG ("ue7")
- DWARF ("LEB128", "ULEB128", "SLEB128")
- HLP (WinHelp) and Segmented Hypergraphics ("compressed short" and "compressed long").
- MIDI ("variable-length quantity")
- Protobuf ("base 128 varint")
- WBMP ("multi-byte integer")
