Variable-length quantity

From Just Solve the File Format Problem
Revision as of 15:50, 16 September 2017 by Jsummers (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
File Format
Name Variable-length quantity
Ontology

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:

Links

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox