LEB128のRubyによる実装

このエントリーをはてなブックマークに追加

Bitcoin CoreのChainstateDB等で使われる可変整数フィールドにBase128 VarIntという表現がある。よく知らなかったのだがこれはLEB128(Little Endian Base 128)と呼ばれ整数をバイト配列にするときに一般的な方式らしい。ChainstateDBにおいてはvoutのインデックスやamountの数値を表現するために利用されている。
(2018/10/7修正、追記)嘘である。Chainstate記録時にBitcoinCoreが用いている方式は正しくはLEB128ではない。改めてこちらの記事に掲載した。

LEB128 – Wikipedia
https://en.wikipedia.org/wiki/LEB128

下記がエンコード処理の実際となる。簡単に言うと、整数を2進数へ変換、7bitで割り切れるように上位に0埋めし分割、さらに7bit毎に最上位に1bit追加(最上位7bitには0、それ以外は1を付与)し8bit毎に16進数に変換し、バイト配列とした後にByte OrderをLittle Endianへ変更する。

624485                      変換対象整数
10011000011101100101 2進数表現

MSB ------------------ LSB 10011000011101100101 2進数表記 010011000011101100101 7bitで割り切れるようにMSB側に0埋め処理 0100110 0001110 1100101 7bit単位で分割 00100110 10001110 11100101 MSB側の最初の7bitの最上位bitには0を付与
それ以外のグループの最上位bitには1を付与 0x26 0x8E 0xE5 16進数表記 → 0xE5 0x8E 0x26 Little Endianへ変換(バイトオーダーの反転処理)

なぜこのような紛らわしい処理をしているのかというと、デコード時の利便性を考えてあるようだ。デコード時は1byteずつ読み込みながら1bit目をチェックし0になるまで読み込み続け、0になった時点で読み込みを終了する。あとはエンコード処理を逆転させてやれば復元できる。なおこの読み込み終了判定は読み込んだbyteに0x80をビット積してやった結果が0という記述が可能である。

Rubyによる実装

GemにはLEB128(https://rubygems.org/gems/leb128/versions/0.1.0 )という物が存在しているが、メタ情報が古いのかGemのLEB128は既にGithubのリポジトリが存在しない。そのためいささか車輪の再発明めいているが、向学の意味も含めて自分で実装してみた。

下記がRubyで実装したコードとなる。
https://gist.github.com/muyesh/0e29c9e6d66e801ebe4db3b6c7957768#file-leb128-rb

BitcoinのプロトコルにおけるVarInt表現

なお、紛らわしいことに、BitcoinではTransactionでの可変整数(64bit整数表現)フィールドにも下記のような独自の表現形を持っているため区別が必要だ。

Variable length integer : Protocol documentation – Bitcoin Wiki
https://en.bitcoin.it/wiki/Protocol_documentation#Variable_length_integer

Value Storage length Format
< 0xFD 1 uint8_t
<= 0xFFFF 3 0xFD followed by the length as uint16_t
<= 0xFFFF FFFF 5 0xFE followed by the length as uint32_t
9 0xFF followed by the length as uint64_t

この表現は上位1byteの値からintのサイズを判定し読み込むbyte数を得る。例えば1byte目が0xFD(253)未満であれば、そのbyteの数値を採用し、0xFDの場合は2byte読み込みuint16_tとする。同様に0xFEであればuint32_tとして4byte読み込み、0xFFであればuint64_tとして8byte読み込むと言った具合だ。
最初は何言ってるのかわからなかった。