Protocol Buffersでは00001000_10010110_00000001という3バイトがキー番号1、値150という情報へ読み替えられる

Protocol Buffersとは、キーとバリューを持つ構造化されたデータを小さく速く簡潔にシリアライズ/デシリアライズするための特定のプログラミング言語によらないメカニズムである。シリアライズ時にはバイナリになる。そのバイナリ化ひととおりの流れを日本語で私なりに説明する。ここに書いた情報は公式ページの [Encoding](https://developers.google.com/protocol-buffers/docs/encoding) に書いてあるし、ここに書いていない情報も公式ページにある。もし興味を持ったらそちらを読むとさらに理解できる。

この記事は 2019-06-01 に[Erlang & Elixir Fest 2019](https://elixir-fest.jp/)で「Protocol Buffers(proto3) を Elixir で実装する」という発表をするための資料を書いていたら生まれた。

----

Protocol Buffersではキーとバリューを持つ構造化された情報を扱う。キーとバリューの定義情報はprotoファイルと呼ばれるフォーマットに記載する。簡潔なprotoファイルは以下のようになる。

```proto
message Test1 {
  optional int32 a = 1;
}
```

Protocol Buffersではprotoファイルとデータの2つを元にシリアライズしてバイナリを生成する。
逆にデシリアライズするときは、protoファイルとバイナリの2つを元にデータを復元する。

`Test1` の `a` に `150` を設定したデータをProtocol Buffersでシリアライズするとわずか3バイト、2進数表現では `00001000_10010110_00000001` となる。Protocol Buffersにおける整数表現と、キーとバリューの扱い方という2点がわかれば、どうしてこうなるかを説明できる。

# 整数(Varint)の表現

整数の `1` という値は `00000001` で表現される。想像通りだろう。 `300` はどうだろうか。その場合は `10101100_00000010` で表現される。よくある数え方だと 32768 + 8192 + 2048 + 1024 + 2 = 44034 だ。なぜこれが `300` になるのだろうか。

Protocol Buffersの整数は、最後の1バイト以外、最上位のビットmsb(Most Significant Bit)が `1` になっている。つまりmsbを左から1バイト毎にチェックしていき、そのバイトのmsbが `1` だと次のバイトも値の一部であるとわかる。msbが `0` だとそのバイトで値の表現が終わるとわかる。つまりmsbをみればバイナリのどこに値の切れ目があるか判断できる。

`10101100_00000010` を左からバイト単位にみていくと、`10101100` は最上位のビットが `1` なので次のバイトも数値の構成要素だと判断できる。続いて `00000010` は最上位のビットが `0` なのでこのバイトで数値の構成要素が途切れると判断できる。

整数を表すバイトがどこまで続くかわかったら、次に全てのmsbを取り除く。つまり7ビットにする。

```
   10101100_00000010
->  0101100  0000010
```

そして7ビットのグループをひっくり返す。最下位(Last Significant)の7ビットグループが最上位に、右から二番目の7ビットグループが左から二番目に……という形だ。

```
   0101100  0000010
-> 0000010  0101100
```

最後にこれを単なるバイト列として足し合わせて数値に読みかえる。繋ぎあわせた最上位のビットで桁が足りなくて空白になったところは `0` とみなしていい。

```
    0000010  0101100
->   000001_00101100
-> 00000001_00101100
```

すると 256 + 32 + 8 + 4 = 300 となる。というわけでProtocol Buffersでは `300` という整数を `10101100_00000010` と表現できる。

ここまでの知識で先程のべた `Test1` の `a` に `150` を設定したデータの表現 `00001000_10010110_00000001` の下位2ビット `10010110_00000001` が `150` を示していることを下記のとおり説明できる。

```
   10010110_00000001
->  0010110  0000001 msbを除去した
->  0000001  0010110 7ビットのグループをひっくり返した
->   000000_10010110 8ビットずつになるように右へ詰めた
-> 00000000_10010110 空白に0を埋めた
```

128 + 16 + 4 + 2 = 150

残りの上位1ビットは想像のとおり「Test1のa」を表している。次に説明しよう。

# キーとバリューの表現

Protocol Buffersではデータをキーとバリューで表現するのだが、まだバリューに利用可能な整数表現しか学んでいない。キーとバリューの組み合わせをどのように行うか。実はProtocol Buffersのキー部分を深くみると2つの情報が含まれている。キー自身の情報とバリューの型表現だ。一つずつ説明しよう。

最初にキー自身の情報だ。Protocol Buffersでは、キーは整数として表現される。Protocol Buffersの設定ファイルprotoを再掲する。

```proto
message Test1 {
  optional int32 a = 1;
}
```

`a = 1` と書いてある。`a` というフィールドはバイナリ表現にしたときに `1` 番へ割り当てるという宣言だ。バイナリ表現には `a` という情報はどこにもなく、バイナリとprotoファイルを組み合わせないと元のデータへは復元できない。不便な面もあるものの、バイナリサイズを小さくするためにこうなっているのだろう。

次にバリューの型表現だ。これはキーに続くバリューの長さを把握できるように含まれている。先程の例 `int32 a = 1` を例にとるとバリューの型表現は `int32` に該当する。

つまり一対のキーとバリューを表したバイナリには、キーの整数表現、バリューの型表現、バリューの3要素が含まれている。

キーの整数表現はこれまでみてきた整数表現と変わらない。ただし通常とは異なり最後の3ビットだけはバリューの型表現に割り当てられている。バリューの型表現に3ビット持てると0-7まで8種類の型を表現できるがProtocol Buffersでは以下の表のとおり0-5の6種類が型として定義されている。そのうち3番と4番は利用しないので実質4種類だ。

| Bits      | Meaning          | Used For |
|:--------- |:---------------- |:-------- |
| `000` (0) | Varint           | int32, int64, uint32, uint64, sint32, sint64, bool, enum |
| `001` (1) | 64-bit           | fixed64, sfixed64, double |
| `010` (2) | Length-delimited | string, bytes, embedded messages, packed repeated fields |
| `011` (3) | Start group      | groups (deprecated) |
| `100` (4) | End group        | groups (deprecated) |
| `101` (5) | 32-bit           | fixed32, sfixed32, float |

これを踏まえてTest1のaに150を設定したデータをProtocol Buffersでシリアライズした `00001000_10010110_00000001` をチェックすると最初のバイト `00001000` のmsbが1ではないので、1バイト目で情報が途切れている。この1バイトがキー(キーの整数表現、バリューの型表現)部分、残りはバリュー部分となる。

次にキー `00001000` のうち、最後の3ビット `000` はバリューの型表現である。表によりバリューは Varint 型であることがわかる。
残りがキー番号になる。そして残りの `00001` を数値に換算すると `1` となる。

つまりProtocol Buffersのバイナリ `00001000_10010110_00000001` はキー番号1番、バリューの型はVarint、そして前述したように残り2ビットのバリューは150を表しているということになるのだ。

# ProtocolBuffersをより深く知るための参考リンク

- [Protocol Buffers のエンコーディング仕様の解説](https://qiita.com/aiueo4u/items/38195248a29e9ff719c7)
- [今さらProtocol Buffersと、手に馴染む道具の話](https://qiita.com/yugui/items/160737021d25d761b353)
- この記事では話さなかったけど公式リンクにはある話
  - [負の整数などをどう扱うか](https://developers.google.com/protocol-buffers/docs/encoding#signed-integers) - ZigZag encoding という名前がかっこいい
  - [Protocol Buffersでの文字列](https://developers.google.com/protocol-buffers/docs/encoding#strings)
  - [Protocol Buffersの中にProtocol Buffersを埋め込める。そのバイナリ表現](https://developers.google.com/protocol-buffers/docs/encoding#embedded)
  - [Protocol Buffersのフィールドは配列にもできる。そのバイナリ表現](https://developers.google.com/protocol-buffers/docs/encoding#optional)