LEB128

LEB128 (Little Endian Base 128) is a compact encoding method used to represent variable-sized integers. This format encodes numbers using groups of 7 bits per byte, which allows for the reduction of small numeric values while still retaining the ability to represent very large integers. There are two main variants: ULEB128 (Unsigned LEB128) for unsigned values and SLEB128 (Signed LEB128) for signed values.

To encode an integer in LEB128:

— Convert the number to binary (base 2)

— Divide the number into 7-bit blocks (and pad with leading 0s if necessary)

— Place the 7 least significant bits (right) in the first byte

— Set the continuation bit (bit 8, most significant) to 1 if another byte follows, otherwise set to 0

— Repeat until all bits are encoded

To decode an LEB128 sequence:

— Read the bytes one byte at a time.

— Extract the 7 least significant bits from each byte and concatenate them in reverse order.

— Continue as long as the continuation bit (bit 8, most significant) is set to 1.

— Reconstruct the final binary value from the accumulated bits.

An LEB128 value is recognizable by its binary structure [1.......][1.......]...[0.......]

Each byte has its most significant bit (bit 8) set to 1, except the last one which has this bit set to 0

ULEB128: Encodes unsigned integers (positive)

SLEB128: Encodes signed integers (negative)

Using LEB128 allows you to store numbers of any size (including very large, arbitrary size) while saving memory space for small integers.

VLQ (Variable-Length Quantity) is a similar concept for storing integers. The major difference is that LEB128 is little-endian (least significant bits first), while VLQ is big-endian (most significant bits first).