Variable-length quantity
From Just Solve the File Format Problem
(Difference between revisions)
(Created page with "{{FormatInfo |formattype=electronic |subcat=Binary Data }} '''Variable-length base-128''' refers a family of formats for encoding arbitrarily large integers. It does not seem ...") |
m |
||
| (8 intermediate revisions by one user not shown) | |||
| Line 1: | Line 1: | ||
{{FormatInfo | {{FormatInfo | ||
|formattype=electronic | |formattype=electronic | ||
| − | |subcat= | + | |subcat=Elements of File Formats |
}} | }} | ||
| − | + | 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 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 == | ||
| − | The | + | 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-[[Endianness|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 == | == Related formats == | ||
| − | Among the formats that use variable-length | + | Among the formats that use variable-length quantities are: |
| − | * [[BPG]] | + | * [[BPG]] ("ue7") |
| − | * [[DWARF]] | + | * [[DWARF]] ("LEB128", "ULEB128", "SLEB128") |
| − | * [[MIDI]] | + | * [[HLP (WinHelp)]] and [[Segmented Hypergraphics]] ("compressed short" and "compressed long"). |
| − | * [[Protobuf]] | + | * [[MIDI]] ("variable-length quantity") |
| − | * [[WBMP]] | + | * [[Protobuf]] ("base 128 varint") |
| + | * [[WBMP]] ("multi-byte integer") | ||
== Links == | == Links == | ||
* [[Wikipedia:Variable-length quantity|Wikipedia: Variable-length quantity]] | * [[Wikipedia:Variable-length quantity|Wikipedia: Variable-length quantity]] | ||
* [[Wikipedia:LEB128|Wikipedia: LEB128]] | * [[Wikipedia:LEB128|Wikipedia: LEB128]] | ||
| + | * [http://formats.kaitai.io/vlq_base128_be/index.html Kaitai Struct: vlq_base128_be] | ||
| + | * [http://formats.kaitai.io/vlq_base128_le/index.html Kaitai Struct: vlq_base128_le] | ||
| + | |||
| + | [[Category:Number formats]] | ||
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")
