Variable-Length Quantity (VLQ / LEB128) Codec
Storing small integers in fixed 64-bit slots wastes 87% of payload space. Variable-Length Quantity (LEB128/Varint) encodes integers using 7 payload bits per byte. The most significant bit (0x80) serves as a continuation flag, compressing small numbers into a single byte.
# Encode 7 bits with continuation flag:
byte = val & 0x7F
val >>= 7
if val > 0:
byte |= 0x80
# Variable-Length Quantity (VLQ / LEB128) Codec In most real-world software, 90% of integer values transmitted over the wire are small numbers: array lengths, HTTP status codes, timestamps, and user counts rarely exceed a few thousand. Allocating a fixed 64-bit integer (8 bytes) for the number `5` means transmitting 7 bytes of useless zeros! 📦🏎️ **Little-Endian Base 128 (LEB128)**, also known as **Varint** in Google Protocol Buffers and WebAssembly, encodes integers dynamically: - Each byte stores **7 bits of data**. - The highest bit (MSB, `0x80`) is a **continuation flag**: - `1`: more bytes follow. - `0`: this is the final byte. The number `1` is encoded as `0x01` (1 byte). The number `300` ($256 + 44$) is encoded as `0xAC 0x02` (2 bytes). ```python # Encoding: byte = val & 0x7F val >>= 7 if val > 0: byte |= 0x80 # Set continuation bit ``` ## Pop Quiz Why do Protocol Buffers and WebAssembly (Wasm) use LEB128/Varints instead of fixed 32-bit or 64-bit integers? - [ ] Small integers (0-127) take 1 byte instead of 4 or 8 bytes, drastically reducing wire payload sizes. - [ ] Varints enable hardware multiplication instructions on ARM processors. - [ ] Fixed integers cannot represent signed negative values across TCP connections. - [ ] Because Linux network sockets drop packets containing zero-value bytes. ## Real-World Challenge Implement an unsigned LEB128 codec: - `encode_uleb128(val: int) -> bytes` - `decode_uleb128(data: bytes, offset: int = 0) -> tuple[int, int]` (returns decoded integer and the count of bytes consumed). Test with small and large integers up to $1,000,000,000$. <details> <summary>Solution</summary> ```python def encode_uleb128(val: int) -> bytes: if val < 0: raise ValueError("ULEB128 only supports non-negative integers") if val == 0: return bytes([0]) buf = bytearray() while val > 0: byte = val & 0x7F val >>= 7 if val > 0: byte |= 0x80 buf.append(byte) return bytes(buf) def decode_uleb128(data: bytes, offset: int = 0) -> tuple[int, int]: val = 0 shift = 0 idx = offset total_len = len(data) while True: if idx >= total_len: raise ValueError(f"Truncated ULEB128 stream at offset {idx}") byte = data[idx] idx += 1 val |= (byte & 0x7F) << shift if (byte & 0x80) == 0: break shift += 7 bytes_consumed = idx - offset return val, bytes_consumed # Verification test_values = [0, 1, 42, 127, 128, 300, 65535, 1000000000] for number in test_values: encoded = encode_uleb128(number) decoded, consumed = decode_uleb128(encoded) assert decoded == number assert len(encoded) == consumed # Test single-byte boundary assert encode_uleb128(127) == bytes([0x7F]) assert encode_uleb128(128) == bytes([0x80, 0x01]) ``` </details>