After I wrote the TIL on ELF, a senior of mine asked me to look into wasm files as well (him being a wasm connoisseur). Thus, I began reading about wasm and its file formats when I read about LEB-128.
What's LEB-128?¶
LEB128 (Little Endian Base 128) is a variable-length code compression used to store an arbitrarily large integer in a small number of bytes. It is commonly used in the DWARF debug file format, WebAssembly, and Android's Dalvik Executable (DEX) format.
It is similar to variable-length quantity (VLQ, big-endian), but LEB128 is little-endian. Both encodings allow numbers larger than a single byte to be stored in a variable number of bytes.
LEB-128 works in the following manner:-
- The number is represented in little-endian format (the least significant 7-bit groups come first).
- Each byte contains 7 bits of data and 1 bit (the most significant bit / MSB) indicating whether further bytes follow:
MSB = 1: further bytes follow in the stream.MSB = 0: this is the last byte.
There are variants of LEB-128, for unsigned and signed integers. I've described them below:-
Unsigned LEB128 (ULEB128)¶
To encode an unsigned integer:
1. Zero-extend the number to a multiple of 7 bits.
2. Divide the number into 7-bit groups.
3. Emit each group in little-endian order, setting the most significant bit (0x80) on all but the last group.
Example: 624485
- In binary:
10011000011101100101 - Pad with zeros to a multiple of 7 bits:
0100110 0001110 1100101 - Partition into 7-bit groups (low to high):
1100101($101$) $\to$ set MSB:11100101(0xE5)0001110($14$) $\to$ set MSB:10001110(0x8E)0100110($38$) $\to$ last group:00100110(0x26)- Result:
0xE5 0x8E 0x26(3 bytes instead of 4).
Signed LEB128 (SLEB128)¶
To encode a signed integer (two's complement): 1. Sign-extend the number to a multiple of 7 bits. 2. The sign of the number is carried by the 6th bit (the most significant bit of the 7-bit payload) of the final group (0 for positive, 1 for negative). 3. Emit each group, setting the MSB on all but the last group.
Example: -624485
- In 21-bit two's complement:
1011001 1110001 0011011 - Partition into 7-bit groups (low to high):
0011011($27$) $\to$ set MSB:10011011(0x9B)1110001($113$) $\to$ set MSB:11110001(0xF1)1011001($89$, bit 6 is 1 for negative) $\to$ last group:01011001(0x59)- Result:
0x9B 0xF1 0x59.
Sibling Variants of LEB128¶
- Protocol Buffers Varints: Uses standard ULEB128 for unsigned integers, and pairs it with ZigZag encoding ($(n \ll 1) \oplus (n \gg 31)$) for signed integers so negative numbers compress into small positive integers.
- Variable-Length Quantity (VLQ): The big-endian sibling of LEB128 (most significant 7-bit group first), used in MIDI delta times and JavaScript Source Maps.
- SQLite Varints: Stores variable-length integers up to 9 bytes, where the 9th byte uses all 8 bits directly without a continuation flag.
While I was at this, I decided that a step-by-step visualizer for both ULEB128 and SLEB128 would be a fun little addition to the bitflip page. You can check it out here :D