Protocol Buffers のエンコーディング仕様の解説

# Protocol Buffersのエンコーディング仕様
https://developers.google.com/protocol-buffers/docs/encoding

※v2,v3のエンコーディング仕様は同じ模様

# まずは具体例

``` 
$ cat test.proto 
syntax = 'proto3';

message Hoge {
  message Foo {
    int32 aa = 1;
    int32 bb = 2;
  }
  int32 a = 1;
  int32 b = 2;
  string c = 3;
  repeated int32 d = 4;
  repeated Foo e = 5;
}
$ protoc --ruby_out=./ test.proto 
$ cat test.rb 
# Generated by the protocol buffer compiler.  DO NOT EDIT!
# source: test.proto

require 'google/protobuf'

Google::Protobuf::DescriptorPool.generated_pool.build do
  add_message "Hoge" do
    optional :a, :int32, 1
    optional :b, :int32, 2
    optional :c, :string, 3
    repeated :d, :int32, 4
    repeated :e, :message, 5, "Hoge.Foo"
  end
  add_message "Hoge.Foo" do
    optional :aa, :int32, 1
    optional :bb, :int32, 2
  end
end

Hoge = Google::Protobuf::DescriptorPool.generated_pool.lookup("Hoge").msgclass
Hoge::Foo = Google::Protobuf::DescriptorPool.generated_pool.lookup("Hoge.Foo").msgclass
$ irb
irb(main):001:0> require './test.rb'
=> true
irb(main):002:0> foo1 = Hoge::Foo.new(aa: 1, bb: 2)
=> <Hoge::Foo: aa: 1, bb: 2>
irb(main):003:0> foo2 = Hoge::Foo.new(aa: 3, bb: 4)
=> <Hoge::Foo: aa: 3, bb: 4>
irb(main):004:0> hoge = Hoge.new(a: 1, b: 2, c: 'abc', d: [3, 270, 86942], e: [foo1, foo2])
=> <Hoge: a: 1, b: 2, c: "abc", d: [3, 270, 86942], e: [<Hoge::Foo: aa: 1, bb: 2>, <Hoge::Foo: aa: 3, bb: 4>]>
irb(main):005:0> File.open("test.pb", "wb") do |f| f.write(hoge.to_proto); end
=> 30
irb(main):006:0>exit
$ hexdump test.pb
0000000 08 01 10 02 1a 03 61 62 63 20 03 20 8e 02 20 9e
0000010 a7 05 2a 04 08 01 10 02 2a 04 08 03 10 04      
000001e
```

# バイナリデータの解説

基本的にkey-valueペアで構成される。

key = タグナンバー * 8 + タイプ値

タイプ値は以下の通りに定義されている。

| Type | Meaning | Used For |
|------|---------|----------|
| 0 | varint | int32, int64, uint32, uint64, sint32, sing64, bool, enum |
| 1 | 64-bit | fixed64, sfixed64, double |
| 2 | Length-delimited | string, bytes, embedded messages, packed repeated fields |
| 3 |  | deprecated
| 4 |  | deprecated
| 5 | 32-bit | fixed32, sfix3d32, float

```
08             # key: 1 * 8 + 0 = \x08
    01         # value: 1

10             # key: 2 * 8 + 0 = \x10
    02         # value: 2

1a             # key: 3 * 8 + 2 = \x1a
    03         # length: 3 bytes
        61     # value: 'a'
        62     # value: 'b'
        63     # value: 'c'

20             # 4 * 8 + 0 = \x20
    03         # 3
20             # 4 * 8 + 0 = \x20
    8e 02      # 270
20             # 4 * 8 + 0 = \x20
    9e a7 05   # 86942

2a             # 5 * 8 + 2 = \x2a
    04         # 4 bytes follows
        08     # 1 * 8 + 0 = \x08
            01 # 1
        10     # 2 * 8 + 0 = \x10
            02 # 2
2a             # 5 * 8 + 2 = \x2a
    04         # 4 bytes follows
        08     # 1 * 8 + 0 = \x08
            03 # 3
        10     # 2 * 8 + 0 = \x10
            04 # 4
```

- repeatedは単にキー名を重複させて複数個配置している

- エンコードされたデータにメッセージ名、キー名の情報はない（データサイズ小さくなる）
    - デコード時にメッセージ定義を元にメッセージ名、キー名を復元する
    - 例えば、以下の2つのメッセージ定義は生成されるバイナリデータは同一であり、互換性がある。
        - message Hoge { int32 aaa = 1; }
        - message Foo { int32 bbb = 1; }

- 各key-valueの順番は任意
    - 以下の2つのバイナリデータは同等に扱える
        - `08 01 10 02`, `10 02 08 01` (Hogeのa,b)
    - repeatedじゃないキーが重複したら後方優先（マージに対応できる）

        ```
        Hoge.decode("\b\x01")
        => <Hoge: a: 1, b: 0, c: "", d: [], e: []>
        Hoge.decode("\b\x01\b\x02")
        => <Hoge: a: 2, b: 0, c: "", d: [], e: []>
        Hoge.decode("\b\x01\b\x02\b\x01")
        => <Hoge: a: 1, b: 0, c: "", d: [], e: []>
        ```
- 見知らぬキーは無視する

    ```
    Hoge.decode("\b\x01\30\x01").to_proto # \30 = 6th * 8 + 0; Hogeに6番のkey-valueはない。
    => "\b\x01"
    ```

# varintの内部表現

msbを終点バイトを表すために使用する。
まずは具体例

```
1     = 0000-0001
2     = 0000-0002
127   = 0111-1111
128   = 1000-0000 0000-0001
129   = 1000-0001 0000-0001
130   = 1000-0002 0000-0001
255   = 1111-1111 0000-0001
256   = 1000-0000 0000-0002
257   = 1000-0001 0000-0002
16383 = 1111-1111 0111-1111
16384 = 1000-0000 1000-0000 0000-0001
16385 = 1000-0001 1000-0000 0000-0001
```

## 変換方法

1010-1100 0000-0010を数値に変換する

1. msgをカット: 010-1100 000-0010
2. 順番を逆にする: 000-0010 010-1100
3. 計算する: 00000100101100 = 1 * 256 + 2 * 16 + 12 * 1 = 256 + 32 + 12 = 300