LEB128
読み：エルイービー-ひゃくにじゅうはち
外語：LEB128: Little Endian Base 128
数値の表現方法の一つで、8ビット長の可変長とするもの。
目次
概要
特徴
Base 128
用途
種類
unsigned LEB128
signed LEB128
概要
コンピューター
の性能は向上し、32ビット、64ビット、128ビットなど、扱える数値の長さも増えていった。
しかし、日常的に使う値は小さな値が多く、64ビットや128ビットをフルに扱い続ける業務はそう多くはない。そこで作られたのが、小さな値は短く符号化される可変長の表現形式である。
特徴
Base 128
LEB128のB128は、Base 128の意である。Base 128は、データを128種類の値の可変長とするものである。
128=2
7
であり、つまり7ビット単位で数値は扱われる。
用途
デバッグ用ファイルフォーマットDWARFで使うために設計された。
Android
用仮想マシン
Dalvik
の実行フォーマット
dex
でも使われているが、dexは
ZIP
で圧縮されて
apk
になるので、圧縮効率を落としたり、直に実行するリアルプロセッサーの製造を難しくするような符号化の採用目的は定かではない。
また
LLVM
のビットコードも似たような方法が使われている。
種類
unsigned LEB128と、signed LEB128がある。
両者を自動的に識別する手段はないため、デコーダーは、予めどちらかを知っている必要がある。
unsigned LEB128
7ビットを値の表現に用い、最上位ビット(MSB)を継続の有無を表わすフラグに使う。
MSBが1であれば継続があり、0ならそのバイトで終了となる。
また、下位バイトから順番に記録される。これは、
UTF-8
のように上位バイトから記録するものとはちょうど逆になる。
例えば、10進で344865(= 0x54321)を符号化した場合、次のようになるだろう。
1010100001100100001 (2進数にする)
10101 0000110 0100001 (7ビットごとに区切る)
00010101 10000110 10100001 (MSBを設定する)
0x15 0x86 0xA1 (16進数にする)
そして、実際の出力は下位バイトからなので「0xA1 0x86 0x15」の順に出力(ファイルに記録)される。
signed LEB128
signedの場合も、符号化方法は同様である。
符号化する前に数値は2の補数形式とする。また、自動的に符号拡張する前提であり、このため出力する値の最上位ビットが1になっている場合、残る7ビットすべて1になるようなバイトを出力する必要はない。
例えば、10進で-344865(= 0xFFFABCDF)を符号化した場合、次のようになるだろう。
11111111 11111010 10111100 11011111 (2進数にする)
11111111111
1101010 1111001 1011111 (7ビットごとに区切る、1のみの塊は捨てる)
01101010 11111001 11011111 (残した値にMSBを設定する)
0x6A 0xF9 0xDF (16進数にする)
そして、実際の出力は下位バイトからなので「0xDF 0xF9 0x6A」の順に出力(ファイルに記録)される。
デコードして出てきた結果の値の最上位(この場合はビット20)が1であるので、32ビット値にするにせよ64ビット以上の値にするにせよ、上位は全て1で埋めて負の数として復号することになる。
再検索