What Is LEB128 Encoding in the AV1 Bitstream?

Little Endian Base 128 (LEB128) is a variable-length integer compression format widely used in modern computing, including the Alliance for Open Media's AV1 video codec specification. This article explains how LEB128 works, how it is implemented within the AV1 bitstream to represent syntax elements like Open Bitstream Unit (OBU) sizes, and why it provides an optimal balance between payload efficiency and architectural flexibility.

How LEB128 Works

LEB128 allows arbitrarily large integers to be stored in a variable number of bytes. Rather than allocating a static 32-bit or 64-bit block for an integer—which wastes space when storing small numbers—LEB128 expands or contracts dynamically based on the value's magnitude.

The format encodes data using the following mechanism:

1. 7-Bit Segmentation: The binary representation of the integer is split into groups of 7 bits, starting from the least significant bits (little-endian order).
2. Continuation Bit (MSB): Each 7-bit chunk is placed into an 8-bit byte. The most significant bit (MSB, or bit 7) serves as a continuation flag:
   • A value of 1 indicates that more bytes follow.
   • A value of 0 indicates that this byte is the final byte of the integer.
3. Byte Assembly: The decoder reads bytes sequentially until it encounters a byte with an MSB of 0, strips the continuation bits, and reassembles the remaining 7-bit payloads in little-endian sequence.

Example: Encoding the Number 600

To illustrate how a decimal value is converted to unsigned LEB128 (ULEB128):

• Binary representation of 600: 10 0101 1000 (10 bits).
• Split into 7-bit groups:
  • Group 1 (lowest 7 bits): 101 1000 (88 in decimal)
  • Group 2 (remaining bits): 000 0100 (4 in decimal)
• Add continuation flags:
  • Group 1 is followed by more data, so the MSB becomes 1: 1101 1000 (0xD8 in hex).
  • Group 2 is the final byte, so the MSB becomes 0: 0000 0100 (0x04 in hex).
• Final Encoded Stream: 0xD8 0x04 (stored in 2 bytes instead of a standard 4-byte 32-bit integer).

LEB128 in the AV1 Bitstream Specification

In the AV1 specification, an unsigned variant denoted as leb128() is utilized primarily within the Open Bitstream Unit (OBU) framing structure.

The fundamental unit of an AV1 bitstream is the OBU, which carries video sequence headers, metadata, tile groups, and frame data. When an OBU header specifies that the size is present (via the obu_has_size_field flag), the exact length of the trailing payload is encoded using leb128().

The AV1 standard places specific requirements on its LEB128 implementation:

• Maximum Byte Limit: The AV1 specification restricts leb128() fields to a maximum of 8 bytes, which provides enough range to describe values up to 56 bits (exceeding petabytes in payload size, well beyond any realistic stream requirement).
• Bitstream Parsing Constraint: AV1 decoders must return an error if a LEB128 value exceeds 8 bytes or if the decoded value causes an integer overflow.
• Canonical Encoding Handling: While the specification allows for leading zeros in the numerical value (which manifest as trailing bytes with value 0x80 followed by 0x00), conforming encoders generally emit the minimal representation to preserve bandwidth.

Why AV1 Utilizes LEB128

1. Bandwidth Optimization: A large portion of OBUs contain small metadata elements, sequence headers, or temporal delimiters that only require tens or hundreds of bytes. LEB128 allows these units to declare their size in 1 or 2 bytes rather than consuming a fixed 4-byte or 8-byte field.
2. Support for Ultra-High Bitrates: Because the field dynamically expands, high-fidelity uncompressed frames, 8K keyframes, or extensive alpha-channel tiles can expand their size definitions without running into container-level length limits.
3. Simpler Parsing and Slicing: Because the OBU size is encoded with a self-terminating variable integer format right at the header, parsers can quickly read the length and skip irrelevant or unsupported OBUs without parsing the payload data itself.