Protocol Buffersのwire formatのバイナリを読んでみる

## はじめに

Protocol Buffers (protobuf) では、wire formatという形式でバイナリにエンコードされます。しばしばwire formatのデータを読み書きすることもあるかと思います。ここでは備忘録も兼ねてwire formatのバイナリがどのようになっているか例とあわせてメモしておこうと思います。

## Wire formatのデータを読んでいく

### uint32を含むメッセージ

例えばuint32を含むメッセージは下記のように定義できます。

```protobuf:protobuf
message MyU32 {
  uint32 u32 = 1;
}
```

このメッセージ定義を使って、例えばGoなら下記のように初期化できます。

```go:Go
var m = &pb.MyU32{U32: 3}
```

このメッセージは、下記のようなバイト列にエンコードされます。

```go
[]byte{
	0x08,
	0x03,
}
```

読みやすく(?)変換すると下記のようになります。

```go
[]byte{
	1<<3 | 0b000, // field=1, WireType=VARINT (0b000)
	3,            // value=3
}
```

Wire formatでは、先頭1バイト[^1]のタグで「フィールド番号」と「wire type (データの型)」をあらわすようです。今回は `0b00001000` になっています。下位3ビットの `000` は VARINT (可変長整数) のwire typeをあらわし、フィールド番号 `1` を上位5ビット (`1<<3`) であらわしています。

VARINTは小さい値を少ないバイト列でエンコードできます。小さい値は出現頻度が高いため、トータルのデータサイズも小さくなりやすいというメリットがあります。今回は `3` という小さい整数のため、1バイトであらわせています。

[^1]: フィールド番号の数値が大きくなると2バイト以上になるようです。タグもVARINTとしてエンコードされるそうです。
[^2]: https://protobuf.dev/programming-guides/encoding/#structure

### uint32のデータが複数バイトにエンコードされる場合

可変長整数のデータが複数バイトにエンコードされる場合を見ていきます。

```go:Go
var m = &pb.MyU32{U32: 1 << 7}
```

上記のメッセージは、下記のようなバイト列にエンコードされます。

```go
[]byte{
	0x08,
	0x80, 0x01,
}
```

読みやすく(?)変換すると下記のようになります。

```go
[]byte{
	1<<3 | 0b000, // タグは前述のものと同じ

	// 1 << 7
	//   ↓ 0b10000000 を7ビットずつに分割
	// 0b_0000001, 0b_0000000
	//   ↓ バイト列を反転
	// 0b_0000000, 0b_0000001
	//   ↓ 後続があれば最上位ビットを立てる
	// 0b10000000, 0b00000001
	0b10000000|0b_0000000, 0b00000000|0b_0000001,
}
```

数値は7ビットずつ分割されてバイト列にエンコードされ、その後バイト列を反転させたものが使われます。このとき、バイト列のひとかたまりがどこまでか、識別できなくなってしまいます。そこでバイト列のひとかたまりを識別するために「後続のバイト列があれば最上位ビットを立てる （後続のバイト列がなければ立てない）」というふうにしているようです。

### 文字列

文字列のような、可変長のデータを含むメッセージを見ていきます。

```protobuf:protobuf
message MyStr {
  string str = 1;
}
```

このメッセージ定義を使って、例えばGoなら下記のように初期化できます。

```go:Go
var m = &pb.MyStr{Str: "aaa"}
```

上記のメッセージは、下記のようなバイト列にエンコードされます。

```go
[]byte{
	0x0a,
	0x03,
	0x61, 0x61, 0x61,
}
```

読みやすく(?)変換すると下記のようになります。

```go
[]byte{
	1<<3 | 0b010, // Field=1, WireType=LEN (0b010)
	3,            // Length=3
	'a', 'a', 'a',
}
```

今回タグは `0b00001010` となっています。下位3ビットの `010` で LEN (可変長データ)[^2] のwire typeをあらわし、フィールド番号 `1` を上位5ビット (`1<<3`) であらわしています。


そして、その次に文字列のバイト数が来ます。今回は3文字のため、`3` となります。その後、文字列の `aaa` が続きます。

### サブメッセージ

メッセージの中にメッセージを含める場合を見ていきます。

```protobuf:protobuf
message MySub {
  MyStr str = 1; // Submessage
}
```

このメッセージ定義を使って、例えばGoなら下記のように初期化できます。

```go:Go
var m = &pb.MySub{
	Sub: &pb.MyStr{Str: "aaa"},
}
```

上記のメッセージは、下記のようなバイト列にエンコードされます。

```go
[]byte{
	0x0a, 0x05,
	0x0a, 0x03, 0x61, 0x61, 0x61,
}
```

読みやすく(?)変換すると下記のようになります。

```go
[]byte{
	1<<3 | 0b010,  // Field=1, WireType=LEN (0b010)
	5,             // Length=5
	1<<3 | 0b010,  // Field=1, WireType=LEN (0b010)
	3,             // Length=3
	'a', 'a', 'a', // Value="aaa"
}
```

先頭の1バイトは、「フィールド番号=1 (`Sub` フィールド) のLEN (可変長データ)」が来ることを示しています。その次の `5` により、`Sub` フィールドをエンコードした際のバイト列の長さがわかります。

さらにその次の1バイトにより、フィールド番号=1 (`Str` フィールド) の文字列が来ることを示しています。その次の `3` により、`Str` フィールドの文字列長がわかります。そして文字列の本体の `aaa` が来ます。

### Repeated

`repeated` なフィールドを含むメッセージを見ていきます。

```protobuf:protobuf
message MyRepeated {
  repeated uint32 u32 = 1;
  repeated string str = 2;
}
```

このメッセージ定義を使って、例えばGoなら下記のように初期化できます。

```go:Go
var m = &pb.MyRepeated{
	U32: []uint32{3, 4},
	Str: []string{"a", "b"},
}
```

このメッセージは、下記のバイト列をデコードして得られます。

```go
var readable = []byte{
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	3,            // Value=3
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	4,            // Value=4
	2<<3 | 0b010, // Field=2, WireType=LEN (0b010)
	1,            // Length=1
	'a',          // Value="a"
	2<<3 | 0b010, // Field=2, WireType=LEN (0b010)
	1,            // Length=1
	'b',          // Value="b"
}
```

フォーマット自体はrepeatedでない場合と類似しています。 `repeated` の場合には、フィールドのデータが複数回あらわれる形により `repeated` をあらわしています。つまり `[]byte{0x08, 0x03}` から `&pb.MyU32{U32: 3}` や `&pb.MyRepeated{U32: []uint32{3}}` のどちらへもデコードできます。

ちなみにrepeatedなデータは、最近はより効率的な形式でエンコードされることもあるようです (LENを使って可変長データとして整数の配列としてあらわすなど)

```go
[]byte{
	0x0a, // 0b0001010 (Field=1, WireType=LEN)
	0x03, // Length=3
	0x04, 0x05, 0x06, // 数値の4, 5, 6
 }
```

### 順不同なRepeated

各フィールドのデータがあらわれる順番を変えてみます。

```go
var readable = []byte{
	2<<3 | 0b010, // Field=2, WireType=LEN (0b010)
	2,            // Length=2
	'a', 'a',     // Value="aa"
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	3,            // Value=3
	2<<3 | 0b010, // Field=2, WireType=LEN (0b010)
	2,            // Length=2
	'b', 'b',     // Value="bb"
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	4,            // Value=4
}
```

これをデコードしてみると、下記のような順不同になっていない場合と同じものが得られました。

```go:Go
&pb.MyRepeated{
	U32: []uint32{3, 4},
	Str: []string{"aa", "bb"},
}
```

Wire formatでは、こういった各フィールドのデータのあらわれる順番が順不同になっていてもデコードできるようになっています。

### repeated でない場合に同じフィールドのデータが複数回現れた場合

あるフィールドについて複数のデータがある場合はどうなるのでしょうか。下記のデータを、 `repeated` を含まない `MyU32` 型としてデコードしてみます。

```go
var readable = []byte{
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	3,            // Value=3
	1<<3 | 0b000, // Field=1, WireType=VARINT (0b000)
	4,            // Value=4
}
```

すると下記が得られました。

```go:Go
&pb.MyU32{U32: 4}
```

repeated でない場合に、同じフィールドのデータが複数回現れた場合は最後の値が採用されました。

## タグ早見表 (16進数版)

### VARINT (可変長整数)

| Hex  | Wire type | フィールド番号 |
| ---- | --------- | ------------ |
|  0x8 | VARINT    | 1            |
| 0x10 | VARINT    | 2            |
| 0x18 | VARINT    | 3            |
| 0x20 | VARINT    | 4            |
| 0x28 | VARINT    | 5            |
| 0x30 | VARINT    | 6            |
| 0x38 | VARINT    | 7            |
| 0x40 | VARINT    | 8            |
| ...  |  ...      | ...          |
| 0x80,0x1 |VARINT | 16           |
| ...  |  ...      | ...          |
| 0xf8,0x0f|VARINT | 255          |

### LEN (可変長データ)


| Hex  | Wire type | フィールド番号 |
| ---- | --------- | ------------ |
|  0xa | LEN       | 1            |
| 0x12 | LEN       | 2            |
| 0x1a | LEN       | 3            |
| 0x22 | LEN       | 4            |
| 0x2a | LEN       | 5            |
| 0x32 | LEN       | 6            |
| 0x3a | LEN       | 7            |
| 0x42 | LEN       | 8            |
| ...  |  ...      | ...          |
| 0x82,0x01 | LEN  | 16           |
| ...  |  ...      | ...          |
| 0xfa,0x0f | LEN  | 255          |

## その他

### protowireパッケージ

こういったwire formatのデータを構築する際に、Goなら `protowire` パッケージを使うと便利そうです。

https://pkg.go.dev/google.golang.org/protobuf/encoding/protowire

### 参考

https://protobuf.dev/programming-guides/encoding/

### 検証のコード

https://github.com/raiich/protobuf-test-go/tree/main