varint

Varint, short for variable-length integer, is a method of serializing integers using a variable number of bytes rather than a fixed size. In common base-128 implementations, an integer is encoded as a stream of bytes with the least-significant bits arriving first. Each byte carries seven data bits and one continuation bit: the most significant bit is set to 1 if another byte follows and 0 if this is the last byte. This design makes small values occupy fewer bytes, while larger values require more bytes, improving space efficiency for many datasets.

Varints are widely used in data interchange formats and RPC systems, including Google Protocol Buffers and Apache Thrift. They are typically used for unsigned integers, and signed values are often encoded with a technique such as zigzag encoding, which maps signed integers to unsigned values so that small magnitudes remain compact.

Encoding and decoding follow straightforward rules. To encode, repeatedly take the lower 7 bits of the value, emit them with the continuation bit set to 1, and right-shift the value by 7, stopping when the remaining value fits in 7 bits and emitting a final byte with the continuation bit cleared. To decode, read bytes sequentially, masking the lower 7 bits and assembling them into the result, stopping when a byte with the continuation bit cleared is encountered. The maximum length for a 64-bit value is 10 bytes. Varints are endianness-agnostic in practice because the encoding order is defined from least to most significant chunks.