Varints, Zigzag, and Prefix Encoding of Integers

A fixed-width integer encoding is a promise that every value occupies the same number of bytes. It makes offset arithmetic constant-time, alignment predictable, and decoding a single load. It also spends eight bytes on the number 3. Serialization formats aimed at storage or at the wire frequently prefer the opposite bet: most integers in real data are small, so a variable-length encoding that costs one byte for small values and more only for large ones wins on average, and the length is recoverable from the first byte.

That bet has a specific failure mode, and it is worth knowing before choosing the encoding.

The continuation-bit scheme

The common variable-length integer, standardized for debug information as LEB128 and used for integers throughout Protocol Buffers and WebAssembly, encodes seven payload bits per byte and reserves the high bit as a continuation flag. Values below 128 take one byte, below 16384 take two, below $2^{21}$ take three, and so on to a maximum of ten bytes for a full 64-bit value.

#include <stdint.h>
#include <stddef.h>

/* Decode one unsigned LEB128 value; *n receives the byte count.
   Returns 0 and sets *n to 0 on a malformed stream longer than 10 bytes. */
uint64_t uleb_decode(const uint8_t *buf, size_t *n) {
    uint64_t v = 0;
    unsigned shift = 0;
    size_t i = 0;
    for (;;) {
        if (i == 10) { *n = 0; return 0; }   /* cap: 10 bytes is the maximum */
        uint8_t b = buf[i++];
        v |= (uint64_t)(b & 0x7f) << shift;
        if ((b & 0x80) == 0) break;
        shift += 7;
    }
    *n = i;
    return v;
}

/* Encode; caller supplies at least 10 bytes of room. */
size_t uleb_encode(uint64_t v, uint8_t *out) {
    size_t i = 0;
    do {
        uint8_t b = v & 0x7f;
        v >>= 7;
        if (v) b |= 0x80;
        out[i++] = b;
    } while (v);
    return i;
}

The decoder is a loop with a data-dependent trip count, so it cannot be unrolled or vectorized in the general case. This is the central cost of the encoding: every value requires a branch per byte, and a stream of varints decodes at roughly one byte per few cycles rather than eight bytes per cycle for a fixed-width load. Formats that care about decode throughput respond either by making the common case branchless for one or two bytes, or by giving up varints for bit packing, where widths are known from metadata rather than from the data.

Two guards belong in any decoder. A corrupt stream can supply continuation bits forever, so the loop must cap the shift at 63 or the byte count at 10; without the cap, shift overflows into undefined behaviour in C. And the encoding is not canonical by default: 0x80 0x00 also decodes to zero, so a reader that hashes or compares encoded bytes must normalize, or the format must state that non-canonical encodings are invalid.

Zigzag and the sign problem

A signed value encoded directly as two’s complement destroys the small-number advantage, because negative numbers have all their high bits set. The value $-1$ as a 64-bit two’s complement integer needs ten varint bytes, the maximum, while $+1$ needs one. Zigzag fixes this by mapping signed to unsigned with the low bit carrying the sign: $0 \mapsto 0$, $-1 \mapsto 1$, $1 \mapsto 2$, $-2 \mapsto 3$, and so on.

For a 32-bit value the mapping is (n << 1) ^ (n >> 31) using an arithmetic shift, which is the standard idiom and is branch-free. The inverse is (u >> 1) ^ -(u & 1), again branch-free. After the mapping, small magnitudes of either sign take one byte, and the cost tracks magnitude rather than bit pattern. The same transformation is what makes delta encoding of timestamps effective: differences between adjacent values are small and often negative, so zigzag applied to the delta keeps them in one or two bytes.

uint32_t zigzag32(int32_t n) { return (uint32_t)((n << 1) ^ (n >> 31)); }
int32_t  unzigzag32(uint32_t u) { return (int32_t)((u >> 1) ^ (~(u & 1) + 1)); }

The expression relies on two behaviours that C does not guarantee for signed types. Left-shifting a negative value is undefined, and right-shifting one is implementation-defined rather than arithmetic. Every mainstream compiler on two’s complement hardware produces the intended result, and the standard formulation used by serialization libraries casts to the unsigned type first, shifts there, and casts back, which removes the signed-shift question entirely. A decoder written for portability should do the same rather than rely on the compiler.

Bit packing and the width-from-metadata alternative

The alternative to self-describing width is width supplied out of band. Parquet and Arrow both support bit-packed encodings where a column’s values are stored at a fixed width $b$ bits chosen from the maximum value in the page, with the width recorded in the page header. Eight 3-bit values fit in three bytes, giving 37.5 percent of the space of a byte-per-value encoding with no continuation bits and no per-value branches. Decoding is a shift and mask at a known offset, which vectorizes cleanly.

The choice of block size interacts with both schemes differently. A varint stream needs no block metadata at all, since each value describes itself, so the decoder can start anywhere that a value boundary is known and can stream without buffering. A bit-packed block must be decoded as a unit, because the offset of value $i$ is $i \cdot b / 8$ and depends on the width chosen for the whole block; a reader that wants value $i$ alone must still decode the block’s header and compute the bit offset, and a reader that wants to start mid-block needs the block’s start, not just a byte position. Block sizes in the low thousands of values keep the wasted decode small while amortizing the header to well under a bit per value.

The trade is that the width is a property of the block, not of the value, so one large value forces the whole block wide. A block of a million small counters with a single outlier at $2^{20}$ costs 20 bits per value instead of 4, a 5x loss that a varint encoding would not suffer, since varints pay only for the values that are large. Formats mitigate this by choosing the block size and by splitting patched values out, but the tension is inherent: self-describing encodings localize cost to the value, block-level encodings localize it to the block.

Prefix encoding for sorted data

A third family exploits ordering. When values share leading bytes, storing the shared prefix once and only the differing suffix per value removes redundancy that neither varint nor bit packing touches. Parquet’s delta encodings, and the front-coding used in Lucene’s term dictionary, both do this; the general form stores a prefix length and a suffix per value, so a run of keys beginning with the same 12 bytes pays 12 bytes once instead of once per key.

Prefix encoding requires sorted input to be effective, because unsorted data has no stable prefix structure, and it requires a decoder that reconstructs each value before use, which defeats random access within the block: value $i$ can only be recovered after values $0..i-1$. That is acceptable for a scan and unacceptable for a point lookup, so formats that support both apply prefix encoding only to blocks they expect to be scanned.

Choosing among them

The decision procedure is short. If the reader needs random access at value granularity and the values are small and uniformly distributed, use fixed width: the memory and decode cost is predictable and the addressing is one multiply. If the values are mostly small with a long tail, use a self-describing variable-length encoding and accept the branchy decoder, or a block-level width with outlier splitting. If the values are sorted, prefix or delta encoding on top of either will beat both. If the values are a narrow domain, dictionary encoding replaces them with ordinals and the integer encoding then applies to the ordinals, as described in Dictionary Encoding and the Cardinality Cliff.

Compression changes the ranking, and not always in the direction the size arithmetic suggests. A fixed-width integer column often compresses to well under its nominal width under a general-purpose codec, because high bytes repeat, so the apparent 4x penalty of fixed width over a one-byte varint can shrink to almost nothing once the page is compressed. A varint stream compresses too, but its byte-aligned payload is already close to entropy for small values, leaving less for the codec to remove. The fair comparison is between compressed sizes, not raw ones, and it usually favours fixed width more than a raw byte count implies.

Decode cost cuts the other way and is often decisive. A compressed fixed-width column needs a decompression pass before any comparison, whereas a varint column can be decoded and compared in one pass without an intermediate buffer. For a scan that filters most rows out, the extra pass dominates, which is why encodings that fuse decode with predicate evaluation are worth the complexity.

One constraint cuts across all of these: the encoding must be decodable in a streaming fashion with bounded state. A scheme that requires the whole block to decode one value is fine for scans and fatal for a page cache that wants to serve a single row. Every format resolves this by making the unit of encoding the unit of caching, which is why the page, not the column, is the addressable unit in the formats described in Inside a Parquet File.