[][src]Crate vint64

vint64: simple and efficient variable-length integer encoding.

About

This crate implements a variable-length encoding for 64-bit little endian integers 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 vint64 can be determined via the first byte alone
  • Provides the most compact encoding possible for every value in range
  • No loops involved in decoding: just (unaligned) loads, masks, and shifts
  • No complex branch-heavy logic: decoding is CTZ + shifts and sanity checks

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:

PrefixPrecisionTotal Bytes
xxxxxxx17 bits1 byte
xxxxxx1014 bits2 bytes
xxxxx10021 bits3 bytes
xxxx100028 bits4 bytes
xxx1000035 bits5 bytes
xx10000042 bits6 bytes
x100000049 bits7 bytes
1000000056 bits8 bytes
0000000064 bits9 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 bytes.

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.

Usage

// 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::length_hint(encoded.as_ref()[0]);

// 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::encode_signed(-42);
assert_eq!(signed.as_ref(), &[0xa7]);

Structs

Error

Error type: indicates decoding failure

VInt64

vint64: serialized variable-width 64-bit integers

Constants

MAX_BYTES

Maximum length of a vint64 in bytes

Functions

decode

Decode a vint64-encoded unsigned 64-bit integer.

decode_signed

Decode a zigzag-encoded vint64 as a signed integer

decode_zigzag

Decode a signed 64-bit integer from zigzag encoding

encode

Encode an unsigned 64-bit integer as vint64

encode_signed

Encode a signed integer as a zigzag-encoded vint64

encode_zigzag

Encode a signed 64-bit integer in zigzag encoding

length_hint

Get the length of a vint64 from the first byte.