参考文章
protobuf-encode-varint-and-zigzag
protobuf格式及实现
源码
官方文档
什么是Protocol Buffers
官方文档是这么说的：
Protocol Buffers是一种以有效并可扩展的格式编码结构化数据的方式。
可以用于结构化数据串行化，很适合做数据存储或 RPC 数据交换格式。它可用于通讯协议、数据存储等领域的语言无关、平台无关、可扩展的序列化结构数据格式。
优点：
- 信息的表示非常紧凑，这意味着消息的体积减少
- 性能高。它以高效的二进制方式存储
- “向后”兼容性
- 跨平台，支持多种语言
Protobuf的整体格式
以二进制流的方式存储，按照定义的字段顺序紧紧相邻。每个字段对应有key-value数据相邻，key由field_number和wire_type计算出，value由该字段定义的值（可能包括value长度）组成。
举个例子，我们定义了一个字段id：
syntax = "proto3";
message Test {
int64 id = 1;
}
实例化Test，并对test.id 赋值为1
key: value的格式如下：
在解释上面的内容之前先介绍一下Protobuf 采用的非常巧妙的 Encoding 方法Varint。
Varint
Varint是一种紧凑的表示数字的方法。
它用一个或多个字节来表示一个数字，值越小的数字使用越少的字节数。这能减少用来表示数字的字节数。比如对于 int32 类型的数字，一般需要 4 个 byte 来表示。但是采用 Varint，对于很小的 int32 类型的数字，则可以用 1 个 byte 来表示。当然凡事都有好的也有不好的一面，采用 Varint 表示法，大的数字则需要 5 个 byte 来表示。从统计的角度来说，一般不会所有的消息中的数字都是大数，因此大多数情况下，采用 Varint 后，可以用更少的字节数来表示数字信息。
Varint 中的每个 byte 的最高位 bit 有特殊的含义，如果该位为 1，表示后续的 byte 也是该数字的一部分，如果该位为 0，则结束。其他的 7 个 bit 都用来表示数字。
然后我们再来理解上面的图：
-
类型位（wire_type）：用来表示id字段的类型，本例中是int64，只用3bit表示字段的类型；类型位对应的含义如下图：
本例中int64类型位为0； -
指定tag（field_number）：本例中是1，即id = 1中的id，所以在指定tag中二进制为"0001"，实例图中只有4位（最大值15），但实际上可以更大，此时需要msb位进行配合；
key序列化的公式为varint(field_number << 3 | wire_type) -
msb(most significant bit)位：当msb位为1时，表示后续的 byte 也是该数字的一部分，如果该位为 0，则结束；举个栗子：test.id = 1, 所以在value部分的二进制位为"00000001"，表示后面没有更多信息了；如果test.id = 128，则value部分的二进制位为"10000000" "00000001",这两个byte都是用来表示128这个值的；
读者可能会困惑，"10000000" "00000001" 是如何表示128呢，因为Protobuf字节序采用 little-endian 的方式，最终计算前将两个 byte 的位置相互交换过一次，如下图：
再举个例子，我们将id的指定tag改为99，代码如下：
syntax = "proto3";
message Test {
int64 id = 99;
}
key部分的值："10011000" "00000110"，含义如下图
上面只是简单介绍了int32这种数据的表示方法，那对其他类型的数据proto buffer是如何表示的呢？
proto buffer中的各种数据表示方法
-
无符号整数: Base 128 Varints
小于 128 的数字都可以用一个 byte 表示。大于 128 的数字，比如 128，会用2个字节表示 -
有符号整数: zigzag 编码
一个负数一般会被表示为一个很大的整数，因为计算机定义负数的符号位为数字的最高位。如果采用 Varint 表示一个负数，那么一定需要 5 个 byte。为此 Google Protocol Buffer 定义了 sint32、sint64 这种有符号类型，采用 zigzag 编码。下面会重点介绍。 -
其他的数据类型
比如字符串等，用一个 varint 表示长度，然后将其余部分紧跟在这个长度部分之后即可。
注意的是字符串的存储并不会压缩空间。
Zigzag 编码
核心思想是用无符号数来表示有符号数字，正数和负数交错，使用 zigzag 编码，绝对值小的数字，无论正负都可以采用较少的 byte 来表示，充分利用了 Varint 这种技术。
对于正整数来讲，如果在传输的时候，我们把多余的0去掉（或者是尽可能去掉无意义的0），传输有意义的1开始的数据，那就可以做到数据的压缩。那怎么样压缩无意义的0呢？
答案也很简单，比如：00000000_00000000_00000000_00000001这个数字，我们如果能只发送一位1或者一个字节00000001，就将压缩很多额外的数据。
负数长什么样呢？
(-1)10 = (11111111_11111111_11111111_11111111)补
前面全是1，这怎么解决？
zigzag给出了一个很巧的方法：我们之前讲补码讲过，补码的第一位是符号位，他阻碍了我们对于前导0的压缩，那么，我们就把这个符号位放到补码的最后，其他位整体前移一位：
(-1)10
= (11111111_11111111_11111111_11111111)补
= (11111111_11111111_11111111_11111111)符号后移
但是即使这样，也是很难压缩的，因为数字绝对值越小，他所含的前导1越多。于是，这个算法就把负数的所有数据位按位求反，符号位保持不变，得到了这样的整数：
(-1)10
= (11111111_11111111_11111111_11111111)补
= (11111111_11111111_11111111_11111111)符号后移
= (00000000_00000000_00000000_00000001)zigzag
而对于非负整数，同样的将符号位移动到最后，其他位往前挪一位，数据保持不变。
(1)10
= (00000000_00000000_00000000_00000001)补
= (00000000_00000000_00000000_00000010)符号后移
= (00000000_00000000_00000000_00000010)zigzag
这样，正数、0、负数都有同样的表示方法了。我们就可以对小整数进行压缩了。这两种case，合并到一起，就可以写成如下的算法：
//整型值转换成zigzag值
int int_to_zigzag(int n)
{
return (n <<1) ^ (n >>31);
}
(1)10
= (00000000_00000000_00000000_00000001)补
左移一位 => (00000000_00000000_00000000_00000010)补
右移31位 => (00000000_00000000_00000000_00000000)补
按位异或 = (00000000_00000000_00000000_00000010)补
(-1)10
= (11111111_11111111_11111111_11111111)补
左移一位 => (11111111_11111111_11111111_11111110)补
右移31位 => (11111111_11111111_11111111_11111111)补
按位异或 = (00000000_00000000_00000000_00000001)补
- n << 1 :将整个值左移一位，不管正数、0、负数他们的最后一位就变成了0；
- n >> 31: 将符号位放到最后一位。如果是非负数，则为全0；如果是负数，就是全1。
- 最后这一步很巧妙，将两者进行按位异或操作。
可以看到，数据位全部反转了，而符号位保持不变，且移动到了最后一位。
我们将1转换成(00000000_00000000_00000000_00000010)zigzag这个以后，我们最好只需要发送2bits（10），或者发送8bits（00000010），把前面的0全部省掉。因为数据传输是以字节为单位，所以，我们最好保持8bits这样的单位。实际传输中我们怎么编码呢？
zigzag引入了一个方法，就是用字节自己表示自己。
字节自表示方法
压缩过程
int write_to_buffer(int zz,byte* buf,int size)
{
int ret =0;
for (int i =0; i < size; i++)
{
if ((zz & (~0x7f)) ==0)
{
buf[i] = (byte)zz;
ret = i +1;
break;
}
else
{
buf[i] = (byte)((zz &0x7f) |0x80);
zz = ((unsignedint)zz)>>7;
}
}
return ret;
}
将这个值从低位到高位切分成每7bits一组，如果高位还有有效信息，则给这7bits补上1个bit的1（0x80）。如此反复 直到全是前导0，便结束算法。
举个例来讲：
(-1000)10
= (11111111_11111111_11111100_00011000)补
= (00000000_00000000_00000111_11001111)zigzag
我们先按照七位一组的方式将上面的数字划开：
(0000-0000000-0000000-0001111-1001111)zigzag
A、他跟(~0x7f)做与操作的结果，高位还有信息，所以，我们把低7位取出来，并在倒数第八位上补一个1(0x80)：11001111
B、将这个数右移七位：(0000-0000000-0000000-0000000-0001111)zigzag
C、再取出最后的七位，跟(~0x7f)做与操作，发现高位已经没有信息了（全是0），那么我们就将最后8位完整的取出来：00001111，并且跳出循环，终止算法；
D、最终，我们就得到了两个字节的数据[11001111, 00001111]
通过上面几步，我们就将一个4字节的zigzag变换后的数字变成了一个2字节的数据。
还原过程
算法如下
int read_from_buffer(byte* buf,intmax_size)
{
int ret =0;
int offset =0;
for (int i =0; i < max_size; i++, offset +=7)
{
byte n = buf[i];
if ((n &0x80) !=0x80)
{
ret |= (n <<offset);
break;
}
else
{
ret |= ((n &0x7f) << offset);
}
}
return ret;
}
整个过程就和压缩的时候是逆向的：对于每一个字节，先看最高一位是否有1(0x80)。如果有，就说明不是最后一个数据字节包，那取这个字节的最后七位进行拼装。否则，说明就是已经到了最后一个字节了，那直接拼装后，跳出循环，算法结束。最终得到4字节的整数。
总结
这个算法使用的基础就是认为在大多数情况下，我们使用的数字都是不大的数字。那我们也能通过计算，得到每超过一个7位的信息以后，传输的字节数就会增加1。以至于，如果数字比较大的时候，原来4字节的数字还会变成5字节：
其他
1. string
message Test2 {
optional string b = 2;
}
实例化
test2=new Test2();
test2.b="testing";
则编码后的字节表示为：
12 07 74 65 73 74 69 6e 67
前两个字节为key:
第一个字节0x12 → field number = 2, type = 2.
第二个字节0x07表示后面数7位是该类型的value值。
第三个字节开始是testing
2. repeated
message Test4 {
repeated int32 d = 4 [packed=true];
}
实例化并赋值
test4 = new Test4();
test4.addd=3;
test4.addd=270;
test4.addd=86942;
编码后的结果
22 // key (field number 4, wire type 2)
06 // payload size (6 bytes)
03 // first element (varint 3)
8E 02 // second element (varint 270)
9E A7 05 // third element (varint 86942)
