Open2

Protocol Buffers のエンコード・デコードをマスターする

yukiyuki

https://developers.google.com/protocol-buffers/docs/encoding#varints

これなんだけど、ちょっと文脈を補いながら説明する必要があると思った。

ドキュメントでは、下記のバイト列は300です、と言われる。ところが、バイト列を見ただけの時点では、これは10進数に直すと44034となるはずで、少し直感に反する。

1010 1100 0000 0010

実は Protobuf のデコードのルールには次のようなものがあり、このルールを適用すると、上記のバイト列を300としてデコードすることができる。

  1. 前節で説明があるとおり、バイト列の先頭は MSB (most significant bit) というフラグになっている。これが0か1かで、自身の後ろにさらにバイト列が続くかどうかを判定する。0なら続かない。
  2. MSB を取る。
  3. Protocol Buffers の variant は(このスクラップでは説明してないが、そういうのがある)リトルエンディアンである。つまり、下位バイトから逆順にバイト列の並び替えが行われる。

では、先ほどの300としてデコード可能な2進数の並びに対して、上述のルールを1つずつ適用していく。

1 を適用する

MSB の下に ^ という記号を付与する。

1010 1100 0000 0010
▲         ▲

2 を適用する

MSB は不要なので、最終的には次のような結果を得られる。

010 1100 000 0010

3 を適用する

バイト単位で、下位バイトから最初になるように並び替える。つまり、下記のように並び替えられる。

010 1100 000 0010
──┬───── ────┬───
  │          │
  └────────┐ │
           │ │
   ┌───────┼─┘
   │       │
   ▼       ▼
000 0010 010 1100

つまり次のようなバイト列を得られる。

000 0010 010 1100

さらに、先5bitの0は計算上は不要なので、10進数に直す際には消して考える。なので、最終的には

10 010 1100

を10進数に直せばよいことになる。あとは、Protocol Buffers の公式ドキュメントの通り計算ができ、300という値を得られることがわかる。