vint64: simple and efficient variable-length integer encoding.
This crate implements a variable-length encoding for 64-bit little endian integers (sometimes also referred to as a variable-length quantity, or "VLQ") with a number of properties which make it superior in almost every way to other variable-length integer encodings like LEB128, SQLite "Varuints", or CBOR:
- Capable of expressing the full 64-bit integer range with a maximum of 9-bytes
- Total length of a
vint64can be determined via the first byte alone
- Provides the most compact encoding possible for every value in range
- No loops required to encode/decode
Integers serialized as unsigned
vint64 are (up to) 64-bit unsigned little
endian integers, with the
[0, (2⁶⁴)−1] range supported.
They have serialized lengths from 1-byte to 9-bytes depending on what value they're representing. The number of remaining bytes is stored in the leading byte, indicated by the number of trailing zeroes in that byte.
Below is an example of how prefix bits signal the length of the integer value which follows:
|7 bits||1 byte|
|14 bits||2 bytes|
|21 bits||3 bytes|
|28 bits||4 bytes|
|35 bits||5 bytes|
|42 bits||6 bytes|
|49 bits||7 bytes|
|56 bits||8 bytes|
|64 bits||9 bytes|
All arithmetic needed to serialize and deserialize
vint64 can be performed
using only 64-bit integers. The case of the prefix byte being all-zero is
a special case, and any remaining arithmetic is performed on the remaining
Some precedent for this sort of encoding can be found in the Extensible Binary Meta Language (used by e.g. the Matroska media container format), however note that the specific type of "vint" used by that format still requires a loop to decode.
// Encode a 64-bit integer as a vint64 let encoded = vint64::encode(42); assert_eq!(encoded.as_ref(), &[0x55]); // Get the length of a `vint64` from its first byte. // NOTE: this is inclusive of the first byte itself. let encoded_len = vint64::decoded_len(encoded.as_ref()); // Decode an encoded vint64 with trailing data let mut slice: &[u8] = &[0x55, 0xde, 0xad, 0xbe, 0xef]; let decoded = vint64::decode(&mut slice).unwrap(); assert_eq!(decoded, 42); assert_eq!(slice, &[0xde, 0xad, 0xbe, 0xef]); // Zigzag encoding can be used to encode signed vint64s. // Decode with `vint64::decode_signed`. let signed = vint64::signed::encode(-42); assert_eq!(signed.as_ref(), &[0xa7]);
Support for encoding signed integers as
Maximum length of a
Get the length of a
Encode an unsigned 64-bit integer as
Get the length of an encoded