http://vpri.org/fonc_wiki/index.php?title=Variable_Length_Integer
Variable Length Integers. A variable length integer allows storing an integer in a variable number of bytes. Doing this takes advantage of the fact that most often integer values tend towards 0, as well as allowing arbitrarily large values to be expressed without needing to make fundamental alterations to the file format.
If A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.
Variable Length Integers. A variable length integer allows storing an integer in a variable number of bytes. Doing this takes advantage of the fact that most often integer values tend towards 0, as well as allowing arbitrarily large values to be expressed without needing to make fundamental alterations to the file format.
VLI/UVLI (Unsigned VLI)
| Range | Pattern |
|---|---|
| 0..127 | 00..7F |
| 128..16383 | 80..BF XX |
| 16384..2097151 | C0..DF XX XX |
| 2097152..268435455 | E0..EF XX XX XX |
| 268435456..34359738367 | F0..F7 XX XX XX XX |
| 34359738368... | F8... |
Where XX is the low-order bits, proceeding from high-to-low ordering.
The pattern will break at 64 bits, allowing either a complete 64-bit value in 9 bytes (FF followed by 8 bytes), or requiring 10 bytes and allowing the pattern to continue up to 128 bits before another such pattern break.
UTF-8
UTF-8 is itself a form of VLI.
| Range | Encoding |
|---|---|
| 0..127 | 0xxxxxxx |
| 127..2047 | 110xxxxx 10yyyyyy |
| 2047..65535 | 1110xxxx 10yyyyyy 10zzzzzz |
| 65536..2097151 | 11110xxx 10yyyyyy 10zzzzzz 10wwwwww |
| 2097152... | ... |
However, UTF-8 is limited to a maximum value of U+10FFFF or 1114111, despite the encoding allowing for the representation of larger values.
https://en.wikipedia.org/wiki/Variable-length_quantityIf A is 0, then this is the last VLQ octet of the integer. If A is 1, then another VLQ octet follows.
- 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.
