From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

LEB128 or Little Endian Base 128 is a form of variable-length code compression used to store an arbitrarily large integer in a small number of bytes. LEB128 is used in the DWARF debug file format.[1][2]

Encoding format[edit]

LEB128 format is very similar to variable-length quantity format; the primary difference is that LEB128 is little-endian whereas variable-length quantities are big-endian. Both allow small numbers to be stored in a single byte, while also allowing encoding of arbitrarily long numbers. There are 2 versions of LEB128: unsigned LEB128 and signed LEB128. The decoder must know whether the encoded value is unsigned LEB128 or signed LEB128.

Unsigned LEB128[edit]

To encode an unsigned number using unsigned LEB128 first represent the number in binary. Then zero extend the number up to a multiple of 7 bits (such that if the number is non-zero, the most significant 7 bits are not all 0). Break the number up into groups of 7 bits. Output one encoded byte for each 7 bit group, from least significant to most significant group. Each byte will have the group in its 7 least significant bits. Set the most significant bit on each byte except the last byte. The number zero is encoded as a single byte 0x00.

As an example, here is how the unsigned number 624485 gets encoded:

MSB ------------------ LSB
      10011000011101100101  In raw binary
     010011000011101100101  Padded to a multiple of 7 bits
 0100110  0001110  1100101  Split into 7-bit groups
00100110 10001110 11100101  Add high 1 bits on all but last (most significant) group to form bytes
    0x26     0x8E     0xE5  In hexadecimal

→ 0xE5 0x8E 0x26            Output stream (LSB to MSB)

Unsigned LEB128 and VLQ (variable-length quantity) both compress any given integer into not only the same number of bits, but exactly the same bits—the two formats differ only in exactly how those bits are arranged.

Signed LEB128[edit]

A signed number is represented similarly, except that the two's complement number is sign extended up to a multiple of 7 bits (ensuring that the most significant bit is zero for a positive number and one for a negative number). Then the number is broken into groups as for the unsigned encoding.

For example the signed number -624485 (0xFFF6789B) is encoded as 0x9B 0xF1 0x59. The lower bits of the two's complement of it is 0110_01111000_10011011; to ensure the MSB of 1, padding one 1 to 21 bit is enough; and encoding 1011001_1110001_0011011 is 0x9B(10011011) 0xF1(11110001) 0x59 (01011001):

MSB ------------------ LSB 
      01100111100010011011  In raw two's complement binary
     101100111100010011011  Sign extended to a multiple of 7 bits
 1011001  1110001  0011011  Split into 7-bit groups
01011001 11110001 10011011  Add high 1 bits on all but last (most significant) group to form bytes
    0x59     0xF1     0x9B  In hexadecimal

→ 0x9B 0xF1 0x59            Output stream (LSB to MSB)

C-like pseudo-code[edit]

Encode unsigned integer[edit]

do {
  byte = low order 7 bits of value;
  value >>= 7;
  if (value != 0) /* more bytes to come */
    set high order bit of byte;
  emit byte;
} while (value != 0);

Encode signed integer[edit]

more = 1;
negative = (value < 0);
size = no. of bits in signed integer;
while(more) {
  byte = low order 7 bits of value;
  value >>= 7;
  /* the following is only necessary if the implementation of >>= uses a 
     logical shift rather than an arithmetic shift for a signed left operand */
  if (negative)
    value |= (~0 << (size - 7)); /* sign extend */

  /* sign bit of byte is second high order bit (0x40) */
  if ((value == 0 && sign bit of byte is clear) || (value == -1 && sign bit of byte is set))
    more = 0;
    set high order bit of byte;
  emit byte;

Decode unsigned integer[edit]

result = 0;
shift = 0;
while(true) {
  byte = next byte in input;
  result |= (low order 7 bits of byte) << shift;
  if (high order bit of byte == 0)
  shift += 7;

Decode signed integer[edit]

result = 0;
shift = 0;
size = number of bits in signed integer;
  byte = next byte in input;
  result |= (low order 7 bits of byte << shift);
  shift += 7;
}while(high order bit of byte != 0);

/* sign bit of byte is second high order bit (0x40) */
if ((shift <size) && (sign bit of byte is set))
  /* sign extend */
  result |= (~0 << shift);


The DWARF file format uses both unsigned and signed LEB128 encoding for various fields.[2]

The mpatrol debugging tool uses LEB128 in its tracing file format.[3]

The Android project uses LEB128 in its Dalvik Executable Format (.dex) file format.[4]

Compressing tables in Hewlett-Packard IA-64 exception handling.[5]

It is used in the Linux kernel for its DWARF implementation.[6]

It is used in WebAssembly's portable binary encoding of the modules.[7]

It is used in LLVM's Coverage Mapping Format.[8]

osu! uses LEB128 in its osu! replay (.osr) format.[9]

It is used in xz file format.[10]

Related Encodings[edit]

The LLVM bitcode file format uses a similar technique[11] except that the value is broken into groups of bits of context-dependent size, with the highest bit indicating a continuation, instead of a fixed 7 bits.

Dlugosz' Variable-Length Integer Encoding uses multiples of 7 bits for the first three size breaks, but after that the increments vary. It also puts all the prefix bits at the beginning of the word, instead of at the beginning of each byte.

Protocol Buffers use the same encoding for unsigned integers, but encode signed integers by prepending the sign as the least significant bit.


  1. ^ UNIX International (July 1993). "DWARF Debugging Information Format Specification Version 2.0, Draft" (PDF). Retrieved 2009-07-19. |section= ignored (help)
  2. ^ a b Free Standards Group (December 2005). "DWARF Debugging Information Format Specification Version 3.0" (PDF). p. 70. Retrieved 2009-07-19.
  3. ^ "MPatrol documentation". December 2008. Retrieved 2009-07-19.
  4. ^ "Dalvik Executable Format". 2007. Retrieved 2009-07-19.
  5. ^ Christophe de Dinechin (October 2000). "C++ Exception Handling for IA-64". Retrieved 2009-07-19.
  6. ^ Matt Fleming (2009). "DWARF implementation". Retrieved 2011-05-22.
  7. ^ WebAssembly (2016). "WebAssembly Binary Encoding". Retrieved 2016-03-15.
  8. ^ LLVM Project (2016). "LLVM Code Coverage Mapping Format". Retrieved 2016-10-20.
  9. ^ "Osr (file format) - osu!wiki". osu.ppy.sh. Retrieved 2017-03-18.
  10. ^ "The .xz File Format". tukaani.org. 2009. Retrieved 2017-10-30.
  11. ^ http://llvm.org/docs/BitCodeFormat.html#variable-width-value

See also[edit]