Bijective Variable Length Quantities
A Variable Length Quantity is a codec between arbitrary precision non-negative integers, that is 0, 1, 2, 3, and so on until you run out of space, and byte strings.
Description
The basic form of a VLQ is that the final byte has the most significant bit set to 0, terminating the byte string, preceding bytes have it set to 1. Then the remaining 7 bits in each byte hold a base-128 digit, with the first byte holding the most significant digit.
This variant provides a bijective codec by biasing the quantity such that,
if all the digits of an n+1 digit sequence are 0 the quantity is 1 more than the maximum that can be encoded with n digits.
For example, the byte string 92 30 holds the digits 18 48 (base 128), which is 2352 (base 10),
the maximum value representable by a single digit is 127, so that gets a bias of 128,
for a decoded quantity of 2480.
This biasing can be efficiently implemented during decoding by adding 1 before incorporating subsequent digits, and during encoding by subtracting 1 after extracting each digit.
Properties
Compact
Compactness is, of course, dependent on the distribution of values to be encoded.
The ideal distribution for this VLQ is:
- 1/2 of values are <128
- 1/4 of values are <(128²+128)
- 1/8 of values are <(128³+128²+128)
- …
- 1/2ⁿ <(128ⁿ⁺¹-1)/127 - 1
Fast
Decoding operates on bytes (and the quantity type), uses addition, bit shifts, and bit masks, reads data sequentially. Encoding is similar, but uses subtraction instead, and, unfortunately, produces its output in reverse order.
Bijective
This codec is a bijection between quantities and a variable number of bytes. Notably, each byte string ending in a byte with the most significant bit cleared represents a distinct array of quantities.
Order Preserving
It preserves the order, and as the bijection is complete, there’s no validation required before sorting.
Self-Terminating
This codec is strongly self-terminating, the final byte can be found from any point in the byte string.
Self-Synchronizing
However, it is only weakly self-synchronizing. The codec requires external information to know that the current byte is the beginning of a value.
Usage and Implementations
Applications
- git.