vint

vint

Short for Variable INTeger, vint is a library for encoding / decoding unsigned integers to / from a slice of bytes.

Format

The encoding is simple:

• If n < MaxUint8, encode the number with its usual 8-bit representation (with the most-significant-bit on the left).
• If n >= MaxUint8, set the first 8 bits to all 1s, subtract MaxUint8 from n, and attempt to encode the remainder in the next 16 bits.
• If the remainder >= MaxUint16, set those 16 bits to all 1s, subtract MaxUint16 and attempt to encode the remainder in the next 32 bits.
• If the remainder >= MaxUint32, set those 32 bits to all 1s, subtract MaxUint32 and encode the remainder in the next 64 bits.

All fields are encoded with the most-significant-bit on the left, ie big-endian.

Examples:

Usage

From examples/42.go:

import (
	"fmt"
	"github.com/SamuraiAck/vint"
)

func main() {
	fmt.Printf("Encode(42) produces %v\n", vint.Encode(uint8(42)))
	n, err := vint.Decode([]byte{42})
	fmt.Printf("Decode([]byte{42}) produces %v, %v\n", n, err)
	fmt.Printf("Length(42) produces %v\n", vint.Length(uint8(42)))
}

eric@ava:~/vint$ go run examples/42.go
Encode(42) produces [42]
Decode([]byte{42}) produces 42, <nil>
Length(42) produces 1
eric@ava:~/vint$ 

Pros

• Prefix-free, self-delimited, every integer has a unique encoding.
• No overhead for integers below 255.
• The encoding is simple enough that a human can inspect and decode it manually, making it suitable for eg low-bandwidth network maintenance protocols that consist primarily of short type-length-value tuples (TLVs).
• As there are very few operations involved, optimized implementations should be faster than more complicated encodings in benchmarks.

Cons

• No error detection.
• This encoding is not space-efficient for integers greater than 254, so any speed advantage due to its simplicity will probably be lost to transmission delays.
• This encoding is inefficient for negative integers cast to unsigned ints. Other varint libraries such as encoding/binary are better for signed integers.
• This library does not currently handle integers greater than MaxUint64. Decode will return an overflow error if the bytes passed to it correspond to an integer > MaxUint64.

Future work

• Optimize Encode / Decode functions.
• Add support for big.Ints?
• Update if Golang ever adds uint128.
• Make a bit-oriented library that puts the least-significant-bit on the left.