Variable-length quantity
(Category:Number formats) |
m |
||
| Line 5: | Line 5: | ||
By '''variable-length quantity''' ('''VLQ'''), we refer to a variety of schemes for encoding an integer in a variable number of [[byte]]s, 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. | By '''variable-length quantity''' ('''VLQ'''), we refer to a variety of schemes for encoding an integer in a variable number of [[byte]]s, 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 | + | 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 == | == Details == | ||
| Line 23: | Line 23: | ||
* [[BPG]] ("ue7") | * [[BPG]] ("ue7") | ||
* [[DWARF]] ("LEB128", "ULEB128", "SLEB128") | * [[DWARF]] ("LEB128", "ULEB128", "SLEB128") | ||
| − | * [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short" | + | * [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short" and "compressed long"). |
* [[MIDI]] ("variable-length quantity") | * [[MIDI]] ("variable-length quantity") | ||
* [[Protobuf]] ("base 128 varint") | * [[Protobuf]] ("base 128 varint") | ||
Latest revision as of 15:50, 16 September 2017
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.
[edit] 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.
[edit] 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")
