Protobuf编码规则

支持类型

该表显示了在 .proto 文件中指定的类型，以及自动生成的类中的相应类型：

.proto Type	Notes	C++ Type	Java/Kotlin Type[1] Java/Kotlin 类型 [1]	Python Type[3]	Go Type	Ruby Type	C# Type	PHP Type	Dart Type
double		double	double	float	float64	Float	double	float	double
float		float	float	float	float32	Float	float	float	double
int32	varint编码。对于负数编码效率低下——如果字段可能有负值，建议改用 sint32。	int32	int	int	int32	Fixnum or Bignum (as required)	int	integer	int
int64	varint编码。对于负数编码效率低下——如果字段可能有负值，建议改用 sint64。	int64	long	int/long	int64	Bignum	long	integer/string	Int64
uint32	varint编码。	uint32	int	int/long	uint32	Fixnum or Bignum (as required)	uint	integer	int
uint64	varint编码。	uint64	long	int/long	uint64	Bignum	ulong	integer/string	Int64
sint32	zigzag和varint编码。有符号的 int 值。比常规的 int32 能更高效地编码负数。	int32	int	int	int32	Fixnum or Bignum (as required) ）	int	integer	int
sint64	zigzag和varint编码。有符号的 int 值。比常规的 int64 能更高效地编码负数。	int64	long	int/long	int64	Bignum	long	integer/string	Int64
fixed32	总是四个字节。如果值通常大于 2\(^{28}\) ，则比 uint32 更有效。	uint32	int	int/long	uint32	Fixnum or Bignum (as required)	uint	integer	int
fixed64	总是八个字节。如果值通常大于 2\({^56}\) ，则比 uint64 更有效。	uint64	long	int/long	uint64	Bignum	ulong	integer/string	Int64
sfixed32	总是四个字节。	int32	int	int	int32	Fixnum or Bignum (as required)	int	integer	int
sfixed64	总是八个字节。	int64	long	int/long	int64	Bignum	long	integer/string	Int64
bool		bool	boolean	bool	bool	TrueClass/FalseClass	bool	boolean	bool
string	字符串必须始终包含 UTF-8 编码或 7 位 ASCII 文本，并且不能长于 2\(^32\) 。	string	String	str/unicode	string	String (UTF-8)	string	string	String
bytes	可以包含任何不超过 2\(^{32}\) 的任意字节序列。	string	ByteString	str (Python 2) bytes (Python 3)	[]byte	String (ASCII-8BIT)	ByteString	string	List

消息结构

对于传统的 xml 或者 json 等方式的序列化中，编码时直接将 key 本身加进去，例如：

{
    "foo": 1,
    "bar": 2
}

这样最大的好处就是可读性强，但是缺点也很明显，传输效率低，每次都需要传输重复的字段名。Protobuf 使用了另一种方式，将每一个字段进行编号，这个编号被称为 field number 。通过 field_number 的方式解决 json 等方式重复传输字段名导致的效率低下问题，例如：

message {
  int32  foo = 1;
  string bar = 2;
}

field_number 的类型被称为wire types，目前有六种类型：VARINT, I64, LEN, SGROUP, EGROUP, and I32 (注：类型3和4已废弃)，因此需要至少3位来区分：

ID	Name	Used For
0	VARINT	int32, int64, uint32, uint64, sint32, sint64, bool, enum
1	I64	fixed64, sfixed64, double
2	LEN	string, bytes, embedded messages, packed repeated fields
3	SGROUP	group start (deprecated)
4	EGROUP	group end (deprecated)
5	I32	fixed32, sfixed32, float

当 message 被编码时，每一个 key-value 包含 <tag> <type> <paylog>，其结构如下：

+--------------+-----------+---------+
| field_number | wire_type | payload |
+--------------+-----------+---------+
    |               |             |
    |               |             |          +---------------+
    +---------------+             +--------->| (length) data |
    |      tag      |                        +---------------+
    +---------------+

• field_number 和 wire_type 被称为 tag，使用一个字节来表示（这里指编码前的一个字节，通过Varint编码后可能并非一个字节）。其值为 (field_number << 3) | wire_type ，换句话说低3位解释了wire_type，剩余的位则解释了field_number。
• payload 则为 value 具体值，根据 wire_type 的类型决定是否是采用 Length-Delimited 记录

额外一提的是由于 tag 结构如上所述，因此对于使用 Varint 编码的 1个字节来说去除最高位标志位和低三位保留给 wire_type使用，剩下四位能够表示[0, 15] 的字段标识，超过则需要使用多于一个字节来存储 tag 信息，因此尽可能将频繁使用的字段的字段标识定义在 [0, 15] 直接。

编码规则

Protobuf 使用一种紧凑的二进制格式来编码消息。编码规则包括以下几个方面：

• 每个字段都有一个唯一的标识符和一个类型，标识符和类型信息一起构成了字段的 tag。
• 字段的 tag 采用 Varint 编码方式进行编码，可以节省空间。
• 字符串类型的字段采用长度前缀方式进行编码，先编码字符串的长度，再编码字符串本身。
• 重复的字段可以使用 repeated 关键字进行定义，编码时将重复的值按照顺序编码成一个列表。

Varint 编码

Varint 是一种可变长度的编码方式，可以将一个整数编码成一个字节序列。值越小的数字，使用越少的字节数表示。它的原理是通过减少表示数字的字节数从而实现数据体积压缩。
Varint 编码的规则如下：

• 对于值小于 128 的整数，直接编码为一个字节；
• 对于值大于等于 128 的整数，将低 7 位编码到第一个字节中，将高位编码到后续的字节中，并在最高位添加一个标志位（1 表示后续还有字节，0 表示当前字节是最后一个字节）。每个字节的最高位也称 MSB(most significant bit)。
  在解码的时候，如果读到的字节的 MSB 是 1 话，则表示还有后序字节，一直读到 MSB 为 0 的字节为止。
  例如，int32类型、field_number为1、值位 300 的 Varint 编码为：

// 300 的二进制
00000001 00101100
// 按7位切割
00 0000010 0101100
// 高位全0省略
0000010 0101100
// 逆序，使用的小端字节序
0101100 0000010
// 每一组加上msb，除了最后一组是msb是0，其他的都为1
10101100 00000010
// 十六进制指
ac 02

// 按照 protobuf 的消息结构，其完整位
08 ac 02
|   |__|__ payload
|   
|----------- tag (field-number << 3 | wire-type) = (1 << 3 | 0) = 0x08

ZigZag编码

对于 int32/int64 的 proto type，值大于 0 时直接使用 Varint 编码，而值为负数时做了符号拓展，转换为 int64 的类型，再做 Varint 编码。负数高位为1，因此对于负数固定需要十个字节( ceil(64 / 7) = 10 )。（这里有个值得思考的问题是对于 int32 类型的负数为什么要转换为 int64 来处理？不转换的话使用5个字节就能够完成编码了。网上的一个说法是为了转换为 int64 类型时没有兼容性问题，此处由于还未阅读过源码，不知道内部是怎么处理的，因此暂时也没想通为什么因为兼容性问题需要做符号拓展。因为按照 Varint 编码规则解码的话，直接读取出来的值赋值给 int64 的类型也没有问题。int32 negative numbers）

很明显，这样对于负数的编码是非常低效的。因此 protobuf 引入 sint32 和 sint64，在编码时先将数字使用 ZigZag 编码，然后再使用 Varint 编码。
ZigZag 编码将有符号数映射为无符号数，对应的编解码规则如下：

static uint32_t ZigZagEncode32(int32_t v) {  
	// Note: the right-shift must be arithmetic  
	// Note: left shift must be unsigned because of overflow
    return (static_cast<uint32_t>(v) << 1) ^ static_cast<uint32_t>(v >> 31);  
}

static uint64_t ZigZagEncode64(int64_t v) {  
	// Note: the right-shift must be arithmetic  
	// Note: left shift must be unsigned because of overflow
    return (static_cast<uint64_t>(v) << 1) ^ static_cast<uint64_t>(v >> 63);  
}

int32_t ZigZagDecode32(uint32_t n) {
    // Note: Using unsigned types prevent undefined behavior
    return static_cast<int32_t>((n >> 1) ^ (~(n & 1) + 1));
} 

static int64_t ZigZagDecode64(uint64_t n) {
    // Note: Using unsigned types prevent undefined behavior
    return static_cast<int64_t>((n >> 1) ^ (~(n & 1) + 1));
}

因此如果传输的数据中可能包含有负数，那么应该使用 sint32/sint64 类型。因为 protobuf 中只定义了为这两种数据类型进行 ZigZag 编码再使用 Varint 编码。

Length-delimited 编码

wire_type 为 LEN，由于其具有动态长度，因此其由一个 Length 值保存长度大小，这个 Length 同样通过 Varint 编码，最后是其内容。
参照以下例子：

message Test2 {
  optional string b = 2;
}

b = "testing"

12 07 [74 65 73 74 69 6e 67]
|  |   t  e  s  t  i  n  g
|  |  |__|__|__|__|__|__ body 的 ASCII 码
|  |
|  |__ length = 6 = 0x06
|      
|__ Tag (field-number << 3 | wire-type) = (2 << 3 | 2) = 18 = 0x12