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，...）。提出了“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 >= 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

解码无符号整数
result = 0;
shift = 0;
unsigned char byte;
do {
byte = get_next_byte_in_input();
result |= (byte & 0x7f)

解码有符号整数
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)

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)

用途

Android项目在其 Dalvik 可执行格式 (.dex) 文件格式中使用 LEB128。
惠普 IA-64 异常处理中的压缩表。
DWARF文件格式使用无符号和有符号的LEB128编码。
mpatrol 试工具在其跟踪文件格式中使用 LEB128。
osu!在其“osu! 重放”（.osr）格式中使用 LEB128。
W3C 高效 XML 交换（EXI）使用 LEB128 表示无符号整数。
WebAssembly中。

评论 (0)