LEB128

読み:エルイービー・ひゃくにじゅうはち
外語:LEB128: Little Endian Base 128 英語
品詞:名詞

数値の表現方法の一つで、8ビット長の可変長とするもの。

目次

コンピューターの性能は向上し、32ビット、64ビット、128ビットなど、扱える数値の長さも増えていった。

しかし、日常的に使う値は小さな値が多く、64ビットや128ビットをフルに扱い続ける業務はそう多くはない。そこで作られたのが、小さな値は短く符号化される可変長の表現形式である。

Base 128

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

128=27であり、つまり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)を符号化した場合、次のようになるだろう。

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

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

signed LEB128

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で埋めて負の数として復号することになる。

関連する用語
リトルエンディアン

コメントなどを投稿するフォームは、日本語対応時のみ表示されます


KisoDic通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club