Variable-length quantity

This article is about a code that uses a variable number of bytes. For a more general category of variable-bit-length codes, see variable-length code.

A variable-length quantity (VLQ) is a universal code used in various applications since 1983. It uses a sequence of binary octets (eight-bit bytes) to represent an arbitrarily large unsigned integer. A VLQ is essentially a base-128 representation of an unsigned integer with the addition of an eighth bit to each 7-bit group to mark continuation of the sequence of bytes. The byte order of VLQ is big endian, i.e., with the most significant bits sent first in the sequence of bytes. A little-endian variation exists called LEB128 that is identical except for endianness.

The mapping of integer values to VLQ codes is not unique, since the seven payload bits in the most significant bytes can all be equal to 0 (unless such prefixing with bytes equal to 0x80 is prohibited in the application). Thus, an integer can be represented using more bytes than the minimum number that is necessary. A variation used in Git removes this redundancy and extends the range of numbers that is representable by each multi-byte code length.

Variations to support signed integers also exist, using a sign bit with either sign–magnitude or two's complement representations.

Applications and history

Base-128 compression is known by many names – VB (Variable Byte), VByte, Varint, VInt, EncInt, etc.

A variable-length quantity (VLQ) was defined for use in the standard MIDI file format, version 1.0 of which was published in 1983. It is also used in the later Extensible Music Format (XMF), first published in 2001.

Base-128 is also used in ASN.1 BER encoding to encode tag numbers and object identifiers (first published in 1984). It is also used in the WAP environment, where it is called variable length unsigned integer or uintvar. RFC 6256 defines the same format and refers to it as a Self-Delimiting Numeric Value or SDNV. The DWARF debugging format defines a variant called LEB128 (or ULEB128 for unsigned numbers), where the least significant group of 7 bits is encoded in the first byte, and the most significant bits are in the last byte (so effectively it is the little-endian analog of a VLQ). Google Protocol Buffers use a similar format to have compact representation of integer values, as does Oracle Portable Object Format (POF) and the Microsoft .NET Framework "7-bit encoded int" in the BinaryReader and BinaryWriter classes.

It is also used extensively in web browsers for source mapping – which contain a lot of integer line and column number mappings – to keep the size of the map to a minimum.

Variable-width integers in LLVM use a similar principle. The encoding chunks are little-endian and need not be 8 bits in size. The LLVM documentation describes a field that uses 4-bit chunk, with each chunk consisting of 1 bit continuation and 3 bits payload.

Benefits

The primary benefits of VLQ encoding are its compactness and its flexibility to support any range of values.

In most applications, smaller integers are more commonly encountered than very large ones. With VLQ encoding, small numbers use fewer bytes, which typically results in using fewer bytes on average if a large quantity of integer values are encoded this way.

At the same time, VLQ encoding can also represent arbitrarily large integers, unlike fixed-wordlength representations such as 8-bit bytes, 16-bit words, 32-bit integers, or 64-bit long integers. There is no inherent upper bound on the range of values that can be represented by a VLQ encoding. In contrast, fixed-length integer representations would typically have either an inadequate range of representable values if a short wordlength is used, or can use too much data to represent each integer if a longer wordlength is used.

VLQ encoding is also simpler to encode and decode than most other variable-length codes such as Huffman codes, since VLQ codes use whole-byte chunks of data. More general variable-length codes typically require much more bit-oriented manipulation for encoding and decoding.

General structure

The encoding assumes an octet (an 8-bit byte) where the most significant bit (MSB), also commonly known as the sign bit, is reserved to indicate whether another VLQ octet follows.

VLQ octet

7	6	5	4	3	2	1	0
27	26	25	24	23	22	21	20
A	Bn

If A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.

B is a 7-bit number [0x00, 0x7F], and n is the position of the VLQ octet where B₀ is the least significant. The VLQ octets are arranged most significant first in a stream.

Variants

The general VLQ encoding is simple, but in basic form is only defined for unsigned integers (nonnegative, positive or zero), and is somewhat redundant, since prepending 0x80 octets corresponds to zero padding. There are various signed number representations to handle negative numbers, and techniques to remove the redundancy.

Group Varint Encoding

Google developed Group Varint Encoding (GVE) after observing that traditional VLQ encoding incurs many CPU branches during decompression. GVE uses a single byte as a header for 4 variable-length uint32 values. The header byte has 4 2-bit numbers representing the storage length of each of the following 4 uint32s. Such a layout eliminates the need to check and remove VLQ continuation bits. Data bytes can be copied directly to their destination. This layout reduces CPU branches, making GVE faster than VLQ on modern pipelined CPUs.

PrefixVarint is a similar design but with a uint64 maximum. It is said to have "been invented multiple times independently". It is possible to be changed into a chained version with infinitely many continuations.

Signed numbers

Sign bit

Negative numbers can be handled using a sign bit, which only needs to be present in the first octet.

In the data format for Unreal Packages used by the Unreal Engine, a variable-length quantity scheme called Compact Indices is used. The only difference in this encoding is that the first VLQ octet has the seventh bit reserved to indicate whether the encoded integer is positive or negative. Any consecutive VLQ octet follows the general structure.

Unreal Signed VLQ

First VLQ octet								Other VLQ octets
7	6	5	4	3	2	1	0	7	6	5	4	3	2	1	0
27	26	25	24	23	22	21	20	27	26	25	24	23	22	21	20
S	A	B0						A	Bn (n > 0)

If S is 0, then the VLQ represents a positive integer. If S is 1, then the VLQ represents a negative number.

If A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.

B is the number chunk being encoded, and n is the position of the VLQ octet where B₀ is the least significant. The VLQ octets are arranged least significant first in a stream.

Zigzag encoding

An alternative way to encode negative numbers is to use the least significant bit for sign. This is notably done for Google Protocol Buffers, and is known as a zigzag encoding for signed integers. One can encode the numbers so that encoded 0 corresponds to 0, 1 to −1, 10 to 1, 11 to −2, 100 to 2, etc.: counting up alternates between nonnegative (starting at 0) and negative (since each step changes the least-significant bit, hence the sign), whence the name "zigzag encoding". Concretely, transform the integer as (n << 1) ^ (n >> k - 1) for fixed k-bit integers. This has the effect of:

• Mapping positive numbers to their multiples of two: n << 1 is equivalent of n x 2. Example: 0, 1, 2, 3 are mapped to 0, 2, 4, 6.
• Mapping negative numbers to the positive odd numbers. A 32-bit negative integer has a form of 1xxx..., so n >> 31 fills all the bits with 1. XORing a two's complement negative number with all 1's turns it positive and subtracts 1. And remember that we multiplied the original number by 2 using n << 1. So -1, -2, -3 are mapped to 1, 3, 5.

Two's complement

LEB128 uses two's complement to represent signed numbers. In this scheme of representation, n bits encode a range from −2ⁿ to 2ⁿ − 1, and all negative numbers start with a 1 in the most significant bit. In Signed LEB128, the input is sign-extended so that its length is a multiple of 7 bits. From there the encoding proceeds as usual.

In LEB128, the stream is arranged least significant first.

Removing redundancy

With the VLQ encoding described above, any number that can be encoded with N octets can also be encoded with more than N octets simply by prepending additional 0x80 octets as zero-padding. For example, the decimal number 358 can be encoded as the 2-octet VLQ 0x8266, or the number 0358 can be encoded as 3-octet VLQ 0x808266, or 00358 as the 4-octet VLQ 0x80808266 and so forth.

However, the VLQ format used in Git removes this prepending redundancy and extends the representable range of shorter VLQs by adding an offset to VLQs of 2 or more octets in such a way that the lowest possible value for such an (N + 1)-octet VLQ becomes exactly one more than the maximum possible value for an N-octet VLQ. In particular, since a 1-octet VLQ can store a maximum value of 127, the minimum 2-octet VLQ (0x8000) is assigned the value 128 instead of 0. Conversely, the maximum value of such a 2-octet VLQ (0xFF7F) is 16511 instead of just 16383. Similarly, the minimum 3-octet VLQ (0x808000) has a value of 16512 instead of zero, which means that the maximum 3-octet VLQ (0xFFFF7F) is 2113663 instead of just 2097151.

In this way, there is one and only one encoding of each integer, making this a base-128 bijective numeration.

Examples

Diagram showing how to convert 106903 from decimal to uintvar representation

Here is a worked-out example for the decimal number 137:

• Represent the value in binary notation (e.g. 137 as 10001001)
• Break it up in groups of 7 bits starting from the lowest significant bit (e.g. 137 as 0000001 0001001). This is equivalent to representing the number in base 128.
• Take the lowest 7 bits, and that gives you the least significant byte (0000 1001). This byte comes last.
• For all the other groups of 7 bits (in the example, this is 000 0001), set the MSb to 1 (which gives 1000 0001 in our example). Thus 137 becomes 1000 0001 0000 1001, where the bits in boldface are something we added. These added bits denote whether there is another byte to follow or not. Thus, by definition, the very last byte of a variable-length integer will have 0 as its MSb.

Another way to look at this is to represent the value in base-128 and then set the MSB of all but the last base-128 digit to 1.

The Standard MIDI File format specification gives more examples:

Integer (decimal)	Integer (binary)	Variable-length quantity (binary)	Integer (hexadecimal)	Variable-length quantity (hexadecimal)
0	00000000 00000000 00000000 00000000	00000000	00000000	00
127	00000000 00000000 00000000 01111111	01111111	0000007F	7F
128	00000000 00000000 00000000 10000000	10000001 00000000	00000080	81 00
8192	00000000 00000000 00100000 00000000	11000000 00000000	00002000	C0 00
16383	00000000 00000000 00111111 11111111	11111111 01111111	00003FFF	FF 7F
16384	00000000 00000000 01000000 00000000	10000001 10000000 00000000	00004000	81 80 00
2097151	00000000 00011111 11111111 11111111	11111111 11111111 01111111	001FFFFF	FF FF 7F
2097152	00000000 00100000 00000000 00000000	10000001 10000000 10000000 00000000	00200000	81 80 80 00
134217728	00001000 00000000 00000000 00000000	11000000 10000000 10000000 00000000	08000000	C0 80 80 00
268435455	00001111 11111111 11111111 11111111	11111111 11111111 11111111 01111111	0FFFFFFF	FF FF FF 7F

External links

• MIDI Manufacturers Association (MMA) - Source for English-language MIDI specs
• Association of Musical Electronics Industry Archived 2010-01-17 at the Wayback Machine (AMEI) -Source for Japanese-language MIDI specs