通信用語の基礎知識 日本文化チャンネル桜二千人委員会 戻る

通常PC用 / 人気 更新 今日 カテ
電子計算機 > 仕様・構造 > 処理・処理方法 > データ > データ形式 > 整数 > 符号化方法
LEB128
辞書:電算用語の基礎知識 プログラミング用語編 (PTPROGY)
読み:エルイービー-ひゃくにじゅうはち
外語: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で埋めて負の数として復号することになる。

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

[再検索] [戻る]


通信用語の基礎知識検索システム WDIC Explorer Ver 7.03 (16-May-2019)
Search System : Copyright © Mirai corporation
Dictionary : Copyright © WDIC Creators club
KisoDic