Variable-length quantity

A variable-length quantity (VLQ) is a universal code that uses an arbitrary number of binary octets (eight-bit bytes) to represent an arbitrarily large integer. It was defined for use in the standard MIDI file format^[1] to save additional space for a resource constrained system, and is also used in the later Extensible Music Format (XMF). A VLQ is essentially a base-128 representation of an unsigned integer with the addition of the eighth bit to mark continuation of bytes. See the example below.

Base-128 is also used in ASN.1 BER encoding to encode tag numbers, and it is used in the WAP environment, where it is called variable length unsigned integer or uintvar. The DWARF debugging format^[2] defines a variant called LEB128 (or ULEB128 for unsigned numbers), where the least significant group of 7 bits are encoded in the first byte and the most significant bits are in the last byte. Google's protocol buffers use a similar format to have compact representation of integer values,^[3] as does Oracle's Portable Object Format (POF)^[4] and the Microsoft .NET Framework's "7-bit encoded int" in the BinaryReader and BinaryWriter classes.^[5]

General structure

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

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.

Other variants

In the data format for Unreal Packages used by the Unreal Engine, a variable length quantity scheme called Compact Indices^[6] is used. The only difference in this encoding is that the first VLQ has the sixth binary digit reserved to indicate whether the encoded integer is positive or negative.

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

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

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

Any consecutive VLQ octet follows the general structure.

Examples

Diagram showing how to convert 106,903 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 if 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:

References

External links

• MIDI Manufacturers Association (MMA) - Source for English-language MIDI specs
• Association of Musical Electronics Industry (AMEI) -Source for Japanese-language MIDI specs