LEB128

LEB128 または Little Endian Base 128 は任意精度の整数を少ないバイト数に格納するのに用いられる可変長符号圧縮である。

LEB128はDWARF デバッグファイルフォーマットや WebAssembly のすべての整数リテラルの符号化方式に使用されている。

符号化形式 LEB128形式は可変長数値表現 (VLQ) と非常に似ている。主な違いは LEB128 はリトルエンディアンであるのに対し、可変長数値表現はビッグエンディアンであることであり、どちらも小さな数値を1バイトで格納できる一方で、任意の長さの数値をエンコードすることもできる。LEB128には2つのバージョンがあり、符号無しLEB128と符号付きLEB128である。復号する際は、エンコードされた値が符号無しLEB128か符号付きLEB128かを知っている必要がある。

符号無し LEB128 符号無し整数を Unsigned LEB128 (ULEB128) にするには、まず2進数で表現する。

次に数値を7ビットの倍数になるようにゼロ拡張する（数値が0でない場合、最上位7ビットがすべて0にならないようにする）。数値を7ビットのグループに分割する。各7ビットグループに対して、最下位グループから最上位グループの順に1バイトずつ出力する。各バイトは、そのグループを7つの最下位ビットに持つ。最後のバイトを除くすべてのバイトの最上位ビットを1に設定する。数値0は通常、単一バイト0x00としてエンコードされる。WebAssemblyでは、0の代替エンコーディングも許可されている（0x80 0x00、0x80 0x80 0x00、...）。 MSB ------------------ LSB 10011000011101100101 元の値の2進数表現 010011000011101100101 7の倍数ビットに拡張 0100110 0001110 1100101 7ビットごとに分割 00100110 10001110 11100101 最後（最上位）のグループを除くすべてに高位1ビットを追加してバイトを形成 0x26 0x8E 0xE5 16進数表現

→ 0xE5 0x8E 0x26 出力 (最下位ビットから最上位ビットの順)

符号付き LEB128 符号付きの数値も同様に表現される。2の補数で表現された、7の倍数のビットから始め、符号なしエンコーディングと同様にグループに分割する。

例えば、符号付き数値-123456は0xC0 0xBB 0x78としてエンコードされる。 MSB ------------------ LSB 11110001001000000 123456 の2進数表現 000011110001001000000 7の倍数ビットに拡張 (21ビット) 111100001110110111111 すべてのビットを反転 (1の補数) 111100001110111000000 1を足す (2の補数) 1111000 0111011 1000000 7ビットごとに分割 01111000 10111011 11000000 最後（最上位）のグループを除くすべてに高位1ビットを追加してバイトを形成 0x78 0xBB 0xC0 16進数表現

→ 0xC0 0xBB 0x78 出力 (最下位ビットから最上位ビットの順)

C言語風擬似コード

符号無し整数のエンコード do { byte = value & 0x7f; /* value の下位7ビットを取得 */ value >>= 7; if (value != 0) /* まだバイトが続く */ byte |= 0x80; /* byte の最上位ビットを立てる */ emit(byte); } while (value != 0);

符号付き整数のエンコード more = 1; negative = (value < 0);

/* 変数 value のビット数。例えば value の型が int64_t なら、size は64になる */ size = sizeof(value) * CHAR_BITS; /* 符号付き整数のビット数 */

while (more) { byte = value & 0x7f; /* value の下位7ビットを取得 */ value >>= 7; /* 符号付き整数である左辺 value に対する右シフト >>= の実装が、算術シフトでなく論理シフトを使う場合のみ、以下が必要。ほとんどのプログラミング言語では、初めから value が符号付きならばこうしたことは起こらない */ if (negative) value |= (~0 << (size - 7)); /* 符号拡張 */

/* byte の符号ビットは上から2番目のビット (0x40) */ sign_bit = byte & 0x40; if ((value == 0 && sign_bit == 0) || (value == -1 && sign_bit != 0)) more = 0; else byte |= 0x80; /* byte の最上位ビットを立てる */ emit(byte); }

符号無し整数の復号 result = 0; shift = 0; unsigned char byte; do { byte = get_next_byte_in_input(); result |= (byte & 0x7f) << shift; /* byte の下位7ビットを取得 */ shift += 7; } while ((byte & 0x80) != 0); /* byte の最上位ビットを取得 */

符号付き整数の復号 result = 0; shift = 0;

/* 変数 resultのビット数。例えば result の型が int64_t なら、size は64になる */ size = sizeof(result) * CHAR_BITS; /* 符号付き整数のビット数 */

/* do-while ループの中で代入し、その後も利用 */ unsigned char byte;

do { byte = get_next_byte_in_input(); result |= (byte & 0x7f) << shift; /* byte の下位7ビットを取得 */ shift += 7; } while ((byte & 0x80) != 0); /* byte の最上位ビットを取得 */

/* byte の符号ビットは上から2番目のビット (0x40) */ if ((shift < size) && ((byte & 0x40) != 0)) /* 符号拡張 */ result |= (~0 << shift);

使用例

Android プロジェクトはDalvik 実行可能ファイルフォーマット (.dex) で LEB128 で使用。 Hewlett-Packard IA-64の例外処理におけるテーブルの圧縮。 DWARF ファイルフォーマットは、様々なフィールドで符号なしと符号付きの両方のLEB128エンコーディングを使用。 LLVM ではカバレッジマッピングフォーマットで使用している。LLVMのLEB128エンコーディングとデコーディングの実装は、前述の擬似コードと並んで有用である。 Microsoft .NET Framework では、BinaryReaderとBinaryWriterクラスで「7ビットエンコード整数」フォーマットをサポートしており、BinaryWriterで文字列を書き込む際、文字列の長さはこのメソッドでエンコードされている。 Minecraft は、パケット内のデータの長さを測定するためにプロトコルでLEB128を使用。 mpatrolデバッギングツールは、トレースファイルフォーマットでLEB128を使用。 osu! は、osu!リプレイ（.osr）フォーマットでLEB128を使用。 W3C Efficient XML Interchange (EXI) は、ここで説明されているのとまったく同じ方法で、LEB128を使用して符号無し整数を表現する。 WebAssemblyは、モジュールのポータブルなバイナリエンコーディングで使用。 Ixzファイルフォーマット

LEB128

Źródło i licencja