LEB128

LEB128(Little Endian Base 128)是一种变长代码压缩形式, 用于在少量字节中存储任意大整数. LEB128 目前被应用在 DWARF 调试文件格式和 WebAssembly 二进制编码中.

LEB128 有 2 个不同的版本: 无符号的 LEB128 和有符号的 LEB128. 解码器必须提前知道编码值是无符号 LEB128 还是有符号 LEB128.

无符号 LEB128

要使用无符号的 LEB128 编码无符号的数字, 首先要用二进制表示数字, 然后 zero extend 扩展到 7 位的倍数(这样, 如果该数字不为零, 则最高 7 位并不全为 0). 然后将数字按 7 位划分, 从最低有效位到最高有效位开始, 每 7 位数组输出一个编码字节. 除最后一个字节外, 在每个字节上设置最高有效位. 数字零被编码为单个字节 0x00.

例如, 以下是无符号数字 624485 的编码方式:

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)

有符号 LEB128

有符号 LEB128 编码与无符号 LEB128 编码过程类似, 区别在于在 zero extend 后, 需要对输出做一次补码运算.

例如, -123456 将被编码为 0xC0 0xBB 0x78:

MSB ------------------ LSB
         11110001001000000  Binary encoding of 123456
     000011110001001000000  As a 21-bit number
     111100001110110111111  Negating all bits (one’s complement)
     111100001110111000000  Adding one (two’s complement)
 1111000  0111011  1000000  Split into 7-bit groups
01111000 10111011 11000000  Add high 1 bits on all but last (most significant) group to form bytes
    0x78     0xBB     0xC0  In hexadecimal

> 0xC0 0xBB 0x78            Output stream (LSB to MSB)

测试用例

无符号 LEB128

Number Bytes
0 0x00
624485 0xe5, 0x8e, 0x26

有符号 LEB128

Number Bytes
0 0x00
624485 0xe5, 0x8e, 0x26
-123456 0xc0, 0xbb, 0x78

参考