LEB128

LEB128（Little Endian Base 128）是一种支持将任意大的整数编码到变长字节流的可变长度编码。DWARF调试文件格式以及WebAssembly中所有整数字面量的二进制编码都使用了 LEB128。

编码格式

LEB128格式与可变长度数量(VLQ) 格式非常相似；两者的主要区别在于，LEB128采用小端序，而可变长度数量采用大端序。两者都允许将小数字存储在单个字节中，同时还允许对任意长度的数字进行编码。LEB128有两个版本：无符号LEB128和有符号LEB128。解码器必须知道编码值是无符号 LEB128还是有符号LEB128才能正确解码。

无符号LEB128

要使用无符号LEB128（ULEB128）编码无符号数，首先要用二进制表示该数，然后用零将该数的二进制表示扩展至长度为7位的倍数（这样，如果数非零，则最高7位不全为0），将该数分成7位一组。每一个7位的组对应输出的一个字节，顺序从最低有效位到最高有效位，除了最后一个字节外，其他字节都置位最高位。WebAssembly 允许对零进行其他编码（0x80 0x00、0x80 0x80 0x00，...）。

例如，无符号数 624485 的编码方式如下：

最高有效位 ------------------ 最低有效位
      10011000011101100101 原始二进制
     010011000011101100101 填充为7位的倍数
   0100110 0001110 1100101 分成7位一组
00100110 10001110 11100101 在除最后一个（最高有效位）组之外的所有组上添加高1位以形成字节
    0x26     0x8E     0xE5 十六进制

→ 0xE5 0x8E 0x26           输出流（LSB 到 MSB）

有符号LEB128

有符号数的表示方式类似：以$N$位二进制补码表示需编码的数，其中$N$是7的倍数，然后按照无符号数的方式编码。

例如有符号数-123456的编码方式如下：

最高有效位 ------------------ 最低有效位
         11110001001000000 123456 的二进制编码
     000011110001001000000 填充到21位
     111100001110110111111 所有位取反（得到-123456在21位下的反码）
     111100001110111000000 加一（得到-123456在21位下的补码）
   1111000 0111011 1000000 分成7位一组
01111000 10111011 11000000 在除最后一个（最高有效位）组之外的所有组上添加高1位以形成字节
    0x78     0xBB     0xC0 十六进制

→ 0xC0 0xBB 0x78           输出流（LSB 到 MSB）

快速解码

直接使用标量实现 LEB128 解码速度相当慢，在分支预测错误成本相对较高的现代硬件上更是如此。一系列论文提出了用于加速解码的 SIMD 技术（在这些论文中，它被称为 VByte，但实际上是同一种编码的另一个名称）。“矢量化 VByte 解码”论文提出了“Masked VByte”，它在商用Haswell硬件上实现了每秒 6.5 亿到 27 亿个整数的速度，具体取决于编码密度。

后续论文提出了一种变体编码“Stream VByte：更快的面向字节的整数压缩” ，其速度提升至每秒超过 40 亿个整数。这种流编码将控制流与编码数据分离，因此与 LEB128 二进制不兼容。

类 C 伪代码

编码无符号整数

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

编码有符号整数

more = 1;
negative = (value < 0);

/* the size in bits of the variable "value", e.g., 64 if value's type is int64_t */
size = sizeof(value) * CHAR_BITS; /* no. of bits in signed integer */

while (more) {
 byte = value & 0x7f; /* 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
   this does not happen on most programming languages if "value" is in a signed type to begin with */
 if (negative)
  value |= (~0 << (size - 7)); /* sign extend */

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

解码无符号整数

result = 0; 
shift = 0;
unsigned char byte;
do {
 byte = get_next_byte_in_input();
 result |= (byte & 0x7f << shift); /* low-order 7 bits of value */
 shift += 7;
} while (byte & 0x80 == 0); /* get high-order bit of byte */

解码有符号整数

result = 0; 
shift = 0;

/* the size in bits of the result variable, e.g., 64 if result's type is int64_t */
size = sizeof(result) * CHAR_BITS; /* no. of bits in signed integer */

/* will be assigned inside the do-while loop, but referenced afterwards */
unsigned char byte;

do {
 byte = get_next_byte_in_input();
 result |= (byte & 0x7f << shift); /* low-order 7 bits of value */
 shift += 7;
} while (byte & 0x80 == 0); /* get high-order bit of byte */

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

JavaScript 代码

编码有符号BigInt

const encodeSignedLeb128FromBigInt = (value) => { 
 value = BigInt(value);
 const result = [];
 while (true) {
  const byte_ = Number(value & 0x7fn);
  value >>= 7n;
  if (
   (value === 0n && (byte_ & 0x40) === 0) ||
   (value === -1n && (byte_ & 0x40) !== 0)
  ) {
   result.push(byte_);
   return result;
  }
  result.push(byte_ | 0x80);
 }
};

解码有符号BigInt

const decodeSignedBigInt = (input) => { 
 let result = 0n;
 let shift = 0;
 while (true) {
  const byte = input.shift();
  result |= BigInt((byte & 0x7f) << shift);
  shift += 7;
  if ((byte & 0x80) === 0) {
   // "sign-extending" does not apply to bigint because it has no fixed size
   // instead, we work by handling it as a two's complement of "shift" bits long,
   // which is provided by BigInt.asIntN
   return BigInt.asIntN(shift, result);
  }
 }
};

用途

• Android项目在其 Dalvik 可执行格式 (.dex) 文件格式中使用 LEB128。
• 惠普 IA-64 异常处理中的压缩表。
• DWARF文件格式使用无符号和有符号的LEB128编码。
• .NET在BinaryReader和BinaryWriter类中支持“7位编码整数”格式。将字符串写入BinaryWriter时，字符串长度使用此方法进行编码。
• Minecraft在其协议中使用LEB128来测量数据包内数据的长度。
• mpatrol 试工具在其跟踪文件格式中使用 LEB128。
• osu!在其“osu! 重放”（.osr）格式中使用 LEB128。
• W3C 高效 XML 交换（EXI）使用 LEB128 表示无符号整数。
• WebAssembly中。
• xz文件格式中。

相关编码

• Dlugosz 的可变长度整数编码（原版）在前三个长度分隔符处使用 7 位的倍数，但此后增量会发生变化。它还将所有前缀位放在字的开头，而不是每个字节的开头。
• 人体学输入设备（HID）报告描述符字节使用2位长的位域来编码后续整数的大小，该整数的字节数为零、一、二或四字节，始终采用小端序。符号性（即是否使用符号扩展缩短的整数）取决于描述符的类型。
• LLVM位码文件格式使用了类似的技术不同之处在于将值分成与上下文相关的大小的位组，最高位表示连续性，而不是固定的 7 位。
• 协议缓冲区（Protobuf）对无符号整数使用相同的编码，但对有符号整数进行编码时，将符号作为第一个字节的最低有效位。
• ASN.1 BER、DER将每个 ASN.1 类型的值编码为八位字节字符串。

参见

• DWARF 调试文件格式
• UTF-7