Varint (LEB128)

Deep dive

How it works

In: an unsigned (or zigzag-mapped signed) integer · Out: 1-10 bytes, 7 payload bits each, low group first, high bit set on all but the last · State: none · Cost: O(bytes) per value, 1 + ⌊log2(v)/7⌋ bytes; order of 1-3 ns per value scalar

1. Unsigned LEB128: emit (v & 0x7F) | 0x80 while v ≥ 128, shifting v right by 7; then emit the last byte without the high bit.
2. Decode: OR (b & 0x7F) << 7i until a byte < 0x80.
3. Signed (SLEB128, DWARF/Wasm): arithmetic shift; stop when the remaining value is all sign bits and bit 6 of the last byte matches the sign. Decoder sign-extends from bit 6 of the last byte.
4. Zigzag (Protobuf sint, Avro, Kafka): map signed to unsigned with (n << 1) ^ (n >> 63), then unsigned LEB128: 0, −1, 1, −2 → 0, 1, 2, 3.

300 = 0b1_0010_1100
groups (LSB first): 010_1100, 000_0010
bytes: 1010_1100 0000_0010 = AC 02

Code

#[derive(Debug, PartialEq)]
pub enum VarintError { Truncated, Overflow }

pub fn write_u64(out: &mut Vec<u8>, mut v: u64) {
    while v >= 0x80 { out.push(v as u8 | 0x80); v >>= 7; }
    out.push(v as u8);
}

/// Returns (value, bytes consumed). Rejects bits beyond 64 and > 10 bytes.
pub fn read_u64(buf: &[u8]) -> Result<(u64, usize), VarintError> {
    let mut v = 0u64;
    for (i, &b) in buf.iter().enumerate().take(10) {
        if i == 9 && b > 1 { return Err(VarintError::Overflow); } // 10th byte may only hold bit 63
        v |= ((b & 0x7F) as u64) << (7 * i);
        if b < 0x80 { return Ok((v, i + 1)); }
    }
    Err(if buf.len() >= 10 { VarintError::Overflow } else { VarintError::Truncated })
}

/// Signed LEB128 (DWARF, WebAssembly).
pub fn write_i64(out: &mut Vec<u8>, mut v: i64) {
    loop {
        let byte = (v & 0x7F) as u8;
        v >>= 7; // arithmetic shift keeps the sign
        let done = (v == 0 && byte & 0x40 == 0) || (v == -1 && byte & 0x40 != 0);
        out.push(if done { byte } else { byte | 0x80 });
        if done { return; }
    }
}

pub fn read_i64(buf: &[u8]) -> Result<(i64, usize), VarintError> {
    let (mut v, mut shift) = (0i64, 0u32);
    for (i, &b) in buf.iter().enumerate().take(10) {
        v |= ((b & 0x7F) as i64) << shift;
        shift += 7;
        if b < 0x80 {
            if shift < 64 && b & 0x40 != 0 { v |= -1i64 << shift; } // sign-extend from bit 6
            return Ok((v, i + 1));
        }
    }
    Err(VarintError::Truncated)
}

/// Zigzag: Protobuf sint64, Avro long, Kafka record fields.
pub fn zigzag(n: i64) -> u64 { ((n << 1) ^ (n >> 63)) as u64 }
pub fn unzigzag(u: u64) -> i64 { ((u >> 1) as i64) ^ -((u & 1) as i64) }

/// QUIC varint (RFC 9000 section 16): 2-bit length prefix, big-endian, values < 2^62.
pub fn quic_write(out: &mut Vec<u8>, v: u64) {
    match v {
        0..=63 => out.push(v as u8),
        64..=16_383 => out.extend_from_slice(&(v as u16 | 0x4000).to_be_bytes()),
        16_384..=1_073_741_823 => out.extend_from_slice(&(v as u32 | 0x8000_0000).to_be_bytes()),
        _ => {
            assert!(v < 1 << 62);
            out.extend_from_slice(&(v | 0xC000_0000_0000_0000).to_be_bytes())
        }
    }
}

pub fn quic_read(buf: &[u8]) -> Option<(u64, usize)> {
    let len = 1usize << (buf.first()? >> 6); // length known from the first byte: no loop branch
    let b = buf.get(..len)?;
    let v = b[1..].iter().fold((b[0] & 0x3F) as u64, |v, &x| (v << 8) | x as u64);
    Some((v, len))
}

Complexity and constants

• Bytes per value: 1 + ⌊log2(v)/7⌋. Ratio vs fixed u32 on uniformly small values (< 128) is 4×; on 20-bit values 3 bytes vs 4.
• Decode cost is dominated by the branch on the continuation bit: predictable when all values have the same length, ~15-20 cycles per mispredict otherwise.
• Fast scalar decoders load 8 bytes at once, find the terminator with !word & 0x8080…80 + trailing_zeros, and compact 7-bit groups with shifts (or pext on BMI2 x86).
• SIMD: Masked VByte decodes standard LEB128 streams 2× or more faster than scalar using pshufb tables; changing the format to Stream VByte is faster still.

Efficiency

• Cost: scalar decode order of 1-3 ns per value, dominated by the branch on the continuation bit: predictable when all values have the same length, about 15-20 cycles per mispredict otherwise. Size: 1 + ⌊log2(v)/7⌋ bytes per value, 4x smaller than fixed u32 on values under 128. No memory beyond the buffer. Bound: branch misprediction.
• Levers:
  • fast path for 1-byte values (often 80 %+ of data) — skips the loop for most values — typical message data
  • load 8 bytes, find the terminator with !word & 0x8080…80 and trailing_zeros, compact with shifts or pext — branch-free length detection — scalar bulk decode
  • Masked VByte (pshufb tables) — 2x or more over scalar on standard LEB128 streams — format fixed by others
  • switch to Stream VByte — faster still — you control the format
  • zigzag for signed values — negative int32 costs 1 byte instead of 10 — any signed field
• Naive → standard → state of the art:
  • fixed u32/u64 fields · 4 or 8 bytes per value
  • scalar LEB128 loop · 1-3 ns per value, 1-10 bytes
  • unrolled batch decode with 1-byte fast path, or SIMD · several times faster per value

Implementation notes

• Protobuf field keys are varints: (field_number << 3) | wire_type; field numbers 1-15 fit in one byte, so give them to the most frequent fields.
• Length-delimited fields prefix a varint length; to write without a second pass, reserve a guess (1-2 bytes) and memmove if wrong, or compute sizes first (protobuf's ByteSizeLong pass).
• Canonical encoding: LEB128 allows overlong forms (0x80 0x00 = 0). Reject them where values are hashed or signed; WebAssembly tolerates padding but caps the length at ⌈N/7⌉ bytes and requires the unused high bits of the last byte to be zero (or sign) bits.
• Big-endian prefix varints (SQLite: up to 9 bytes, the 9th using all 8 bits) keep byte-wise sort order equal to numeric order, useful for keys; LEB128 does not.
• Batch decode: decode many values per call with an unrolled loop and a fast path for 1-byte values (often 80 %+ of data).

Pitfalls

• Encoding negative int32/int64 with plain varint: always 10 bytes; use zigzag (sint32).
• Missing bound checks: a stream of 0x80 bytes loops past 10 bytes or past the buffer; cap iterations and check length.
• Shifting by ≥ 64 in the decoder is UB in C/C++ (panics in Rust debug builds); stop at 10 bytes.
• Using varints for sort keys: byte order ≠ numeric order.
• Mixing LEB128 (LSB-first) with big-endian varint formats in the same codebase; they look alike and silently misdecode.

Variants and alternatives

In production

Serialization and RPC: Protocol Buffers, gRPC, Kafka record format and Avro (zigzag varints), Thrift compact protocol. Binary formats and tooling: WebAssembly binary format, DWARF debug info, Android DEX. Search and databases: Lucene VInt, SQLite records (big-endian varint). Networking: QUIC/HTTP3 (prefix varint, RFC 9000). Languages: Go encoding/binary (Uvarint).

Implementations

Sources

• DWARF Debugging Information Format Committee, DWARF Debugging Information Format Version 5, 2017 (section 7.6, LEB128). spec
• Google, Protocol Buffers: Encoding, protobuf.dev/programming-guides/encoding. docs
• J. Iyengar, M. Thomson, RFC 9000: QUIC: A UDP-Based Multiplexed and Secure Transport, 2021 (section 16). RFC
• J. Plaisance, N. Kurz, D. Lemire, Vectorized VByte Decoding, arXiv:1503.07387, 2015. arXiv · code
• J. Dean, Challenges in Building Large-Scale Information Retrieval Systems, WSDM keynote, 2009.
• WebAssembly Core Specification, Binary Format: Integers (LEB128, padding rules). spec