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 偽代碼

### 編碼無符號整數

```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);
```

### 編碼有符號整數

```c
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);
}
```

### 解碼無符號整數

```c
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 */
```

### 解碼有符號整數

```c
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

```javascript
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

```javascript
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 類型的值編碼為八位字節字串。