LEB128

LEB128のB128は、Base 128の意である。Base 128は、データを128種類の値の可変長とするものである。

128=2⁷であり、つまり7ビット単位で数値は扱われる。

デバッグ用ファイルフォーマットDWARFで使うために設計された。

Android用仮想マシンDalvikの実行フォーマットdexでも使われているが、dexはZIPで圧縮されてapkになるので、圧縮効率を落としたり、直に実行するリアルプロセッサーの製造を難しくするような符号化の採用目的は定かではない。

またLLVMのビットコードも似たような方法が使われている。

unsigned LEB128と、signed LEB128がある。

両者を自動的に識別する手段はないため、デコーダーは、予めどちらかを知っている必要がある。

7ビットを値の表現に用い、最上位ビット(MSB)を継続の有無を表わすフラグに使う。

MSBが1であれば継続があり、0ならそのバイトで終了となる。

また、下位バイトから順番に記録される。これは、UTF-8のように上位バイトから記録するものとはちょうど逆になる。

例えば、10進で344865(= 0x54321)を符号化した場合、次のようになるだろう。

1. 1010100001100100001 (2進数にする)
2. 10101 0000110 0100001 (7ビットごとに区切る)
3. 00010101 10000110 10100001 (MSBを設定する)
4. 0x15 0x86 0xA1 (16進数にする)

そして、実際の出力は下位バイトからなので「0xA1 0x86 0x15」の順に出力(ファイルに記録)される。

signedの場合も、符号化方法は同様である。

符号化する前に数値は2の補数形式とする。また、自動的に符号拡張する前提であり、このため出力する値の最上位ビットが1になっている場合、残る7ビットすべて1になるようなバイトを出力する必要はない。

例えば、10進で-344865(= 0xFFFABCDF)を符号化した場合、次のようになるだろう。

1. 11111111 11111010 10111100 11011111 (2進数にする)
2. 11111111111 1101010 1111001 1011111 (7ビットごとに区切る、1のみの塊は捨てる)
3. 01101010 11111001 11011111 (残した値にMSBを設定する)
4. 0x6A 0xF9 0xDF (16進数にする)

そして、実際の出力は下位バイトからなので「0xDF 0xF9 0x6A」の順に出力(ファイルに記録)される。

デコードして出てきた結果の値の最上位(この場合はビット20)が1であるので、32ビット値にするにせよ64ビット以上の値にするにせよ、上位は全て1で埋めて負の数として復号することになる。