LEB128な数の表現 - Dr.Deamon64 Wiki - Dr.Deamon64

Prev: ELFセクションとの関係

Next: デバッグ情報とDIE(.debug_info/.debug_abbrevセクションの概要)

目次に戻る：DWARFファイルフォーマット

LEB128な数の表現

LEB128って何？

このwiki含めて、DWARFの話をする際には、やったら登場するのが、この「LEB128」というキーワードです。
じゃ、何かというと、

「DWARF内で整数をバイナリ表現する際の表現方法(ビットの並べ方)」

です。

DWARFでは、実行ファイル内に「とにかく少ないデータ量(サイズ)で、できる限り多くのデータを突っ込む」ことが第一儀とされています。このため、なんと数値の表現方法まで短く、言うならば簡易的に圧縮する手法を取って、１バイトでも削減しようとがんばっています。
あ、ちなみにLEB128は、「Little Endian Base 128」の略です。このwikiでも、以後は全て「LEB１２８」、具体的には、符号なし(正数しかない)を「uLEB128」、符号あり(マイナス値になり得る)を「sLEB128」と書きます。

ということで、ここではそのがんばりをみていきます。

まずはunsigned版から

LEB128ですが、基本的な表現の方法は、以下のルールに沿って数値を表現する方法です。
もう、これは単純にデコード方法(アルゴリズム)を以下に示します。

• まず、最初の1Byte=8bitのうち、上位1bitと下位7bitを分けて考える。
• 下位7bitは、そのまま答えの数値の下位7bitとする。
• 上位１bitが、
  • 0なら → それで終り。下位7bitの数値がそのままLEB128表現での数値となる。(すなわち、127以下の数値は1Byteで表現できる)
  • 1なら → 次の1Byteに続く、という意味を示す。(すなわち、128以上の数値は2Byte以上必要)
• 次の1Byteを、同じく上位１bitと下位7bitに分ける。
• 下位7bitを、先程1Byte目の下位7bitの上の7bitとみなして、ORを取る。
  すなわち、1Byteの目の下位7bitは答え数値の下7bit、2Byte目の下位7bitは答え数値の14〜8bitになる。
• 上位1bitの値が1なら、 ３Byte目にも同じことを繰り返す
• 以後、上位1bitが0になるまで繰り返し。。。。

この方法は、一見すると1Byteで127までしか表現できないので、本来の1Byte unsignedの限界255まで表現できない点で、デグレってるようにも思えます。
が、仮に65535まで、すなわち最大16bitが必要、という数値をunsigned shortで表したら、1も0も15も2Byte必要です。
しかしながら、この方法なら、127までは1Byteで済みます。これは「割り切り」でしかないのですが、通常デバッグ情報では127未満の値になることが多いだろう、という判断を踏まえた場合、結果的に容量をちっちゃくできる可能性があります。
んで、DWARFではこの方式を最大限度利用しています。DWARFを見て行く際には、もっとも基本的な事項になるので、覚えましょうこれだけは。

参考まで、原文テキストにある、例を以下の表にうつします。なお、0xが付いていない数値は、全て１０進数です。

値	uLEB128 1Byte目	uLEB128 2Byte目
2	2 (0x02)	-
127	127 (0x7f)	-
128	128 (0+0x80=0x80)	1 0x01
129	129 (1+0x80=0x81)	1 0x01
130	130 (2+0x80=0x82)	1 0x01
12857 (0x3239)	185 (0x39+0x80=0xb9)	100 0x64

次に、signed版(sLEB128)

signed版も、unsigned版と基本的な考え方は同じです。 1Byte目から順に、上記1bitと下位7bitに分け、まず7bitをそのまま答えの7bitへ、上位1bitが1なら、次のバイトを上位1bitと下位7bitに分け、下位7bitは答え数値の14〜7bitへ、。。。の繰り返しをまずやります。
この処理の段階で、マイナスは気にしません。単なるビット操作として繰り返します。

で、この処理が上位1bit=0で終ってからが、一手間あります。
LEB128表現は、見てのとおり、7bit単位の数値データ＋1bitの次Byteの要否、ですから、1Byteだけの表現なら実質7bit、2Byte使った場合は14bitの数値、とみなせます。
ここで、仮に「7bitの符号付き(マイナスあり)二進数表現」であれば、7bit目の値が1の場合は、マイナスで、0なら正数ですよね。
はい。これがカラクリです。すなわち、

• 1Byteで表現された符号付きLEB128 → 7bit 目の値が1なら、負数。0なら、正数
• 2Byteで表現された符号付きLEB128 → 14bit目の値が1なら、負数。0なら、正数

になります。

なお、言うまでもなく、ボクらのコンピュータ君は、8bit単位です。なので、仮に7bitが1なら、8bit目も1にしてやる処理が最後に必要です。(でないとPCでは8bitの正数になってしまいます)
同様に、2Byte表現のLEB128負数なら、すなわち 14bit目が1だったら、16/15bit目を1にしなくてはなりません。sLEB128はこの手間が増えるので、要注意です。

最後に、いくつか原文の例をうつします。

値	sLEB128 1Byte目	sLEB128 2Byte目
2	2 (0x02)	-
-2	126 (0x7e)	-
127	255(127+128) (0x7e+0x80=0xff)	0 (0x00)
-127	129(1+128) (0x01+0x80=0x81)	127 (0x7f)
128	128(0+128) (0x00 + 0x80 = 0x80)	1 (0x01)
-128	128(0+128) (0x00 + 0x80 = 0x80)	127 (0x7f)
129	129(1+128) (0x01 + 0x80 = 0x81)	1 (0x01)
-129	255(127+128) (0x7f + 0x80 = 0xff)	126 (0x7e)

よーするに？

unsigned もsignedも、これを見るとあることが分かります。よーは、LEB128とは、
「1Byte=7bitとして扱った二進数表現 ＋ 1bitは次のByteがあるかのフラグ」
と言えます。(だから、LittleEndian Base128なんですね。7bit LittleEndian+とかの方が分かりやすい？んなことないか？)

Prev: ELFセクションとの関係

Next: デバッグ情報とDIE(.debug_info/.debug_abbrevセクションの概要)

目次に戻る：DWARFファイルフォーマット