Variable-length quantity

From Wikipedia, the free encyclopedia

A variable-length quantity (VLQ) is a universal code that uses an arbitrary number of binary octets (eight-bit bytes) to represent an infinitely 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). It is also used in the WAP environment to represent unsigned integers of arbitrary length, where it is called variable length unsigned integer or uintvar.

1 General structure
2 Examples
3 References
4 External links
- 4.1 Official MIDI Standards Organizations

[edit] General structure

The encoding assumes an octet where the most significant bit (MSB), also commonly known as the sign bit, is reserved to indicate whether another octet follows. If the MSB is 0, then this is the last octet of the integer, otherwise another binary octet follows. The octets within an integer are arranged most significant first.

[edit] Examples

Diagram showing how to convert 106,903 from decimal to uintvar representation

Here we work an example with the 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.

The Standard MIDI File format specification gives more examples:^{[verification needed]}

Integer	Variable-length quantity
0x00000000	0x00
0x0000007F	0x7F
0x00000080	0x81 0x00
0x00002000	0xC0 0x00
0x00003FFF	0xFF 0x7F
0x00004000	0x81 0x80 0x00
0x00010000	0xFF 0xFF 0x7F
0x00020000	0x81 0x80 0x80 0x00
0x08000000	0xC0 0x80 0x80 0x00
0x0FFFFFFF	0xFF 0xFF 0xFF 0xE7