Varint — LEB128 (C)
Topics: variable-length integers, bit manipulation, encoding
Problem
Implement unsigned LEB128 varint encode/decode — the variable-length integer encoding used by
Protobuf, DWARF, and WebAssembly. Small numbers take one byte; big ones grow as needed.
size_t varint_encode(uint64_t v, unsigned char *out); // bytes written (<=10)
size_t varint_decode(const unsigned char *buf, size_t len, uint64_t *out); // bytes consumed, 0 on error
Each output byte holds 7 payload bits; the high bit 0x80 is a continuation flag ("more
bytes follow"), least-significant group first.
varint_encode: while v >= 0x80, emit (v & 0x7f) | 0x80 and shift right 7; emit the final
v & 0x7f. out has room for up to 10 bytes (64-bit max).varint_decode: accumulate 7 bits per byte until one has the continuation bit clear; return the
bytes consumed, or 0 if the input is truncated or would overflow 64 bits.
0 -> 00 127 -> 7F 128 -> 80 01 300 -> AC 02
Key concepts
- 7 bits per byte + continuation flag: mask
0x7f, set 0x80 while more groups remain.
- Shift to reassemble:
result |= (byte & 0x7f) << shift; shift += 7.
- Guard against bad input: stop with 0 if
shift >= 64 (overflow) or the buffer ends mid-number.
- Self-framing: a decoder consumes only its own bytes, so varints pack back-to-back in a stream.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/varint && /tmp/varint
Sign in to submit your solution.