深入Protobuf

Reference

深入 ProtoBuf - 简介 - 简书 (jianshu.com)

https://blog.csdn.net/weixin_43708622/article/details/111397290

正文

由于该作者讲的很好，我就直接引用了,引用自：

作者：401
链接：https://www.jianshu.com/p/73c9ed3a4877
来源：简书
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结的讲，Varints 编码的规则主要为以下三点：

1. 在每个字节开头的 bit 设置了 msb(most significant bit )，标识是否需要继续读取下一个字节
2. 存储数字对应的二进制补码
3. 补码的低位排在前面

例一

先来看一个最为简单的例子：

int32 val =  1;  // 设置一个 int32 的字段的值 val = 1; 这时编码的结果如下
原码：0000 ... 0000 0001 （一共32位...表示省略） // 1 的原码表示
补码：0000 ... 0000 0001 （一共32位...表示省略） // 1 的补码表示
Varints 编码：0#000 0001（0x01）  // 1 的 Varints 编码，其中第一个字节的 msb = 0

• 编码过程：
  数字 1 对应补码 0000 … 0000 0001（规则 2），从末端开始取每 7 位一组并且反转排序（规则 3），因为 0000 … 0000 0001 除了第一个取出的 7 位组（即原数列的后 7 位），剩下的均为 0。所以只需取第一个 7 位组，无需再取下一个 7 bit，那么第一个 7 位组的 msb = 0。最终得到

  0 | 000 0001（0x01） 

• 解码过程：
  我们再做一遍解码过程，加深理解。

  编码结果为 0#000 0001（0x01）。首先，每个字节的第一个 bit 为 msb 位，msb = 1 表示需要再读一个字节（还未结束），msb = 0 表示无需再读字节（读取到此为止）。

  在上面的例子中，数字 1 的 Varints 编码中 msb = 0，所以只需要读完第一个字节无需再读。去掉 msb 之后，剩下的 000 0001 就是补码的逆序，但是这里只有一个字节，所以无需反转，直接解释补码 000 0001，还原即为数字 1。

注意：这里编码数字 1，Varints 只使用了 1 个字节。而正常情况下 int32 将使用 4 个字节存储数字 1。

例二

再看一个需要两个字节的数字 666 的编码：

int32 val = 666; // 设置一个 int32 的字段的值 val = 666; 这时编码的结果如下
原码：000 ... 101 0011010  // 666 的源码
补码：000 ... 101 0011010  // 666 的补码
Varints 编码：1#0011010  0#000 0101 （9a 05）  // 666 的 Varints 编码

• 编码过程：
  666 的补码为 000 … 101 0011010，从后依次向前取 7 位组并反转排序，则得到：

  0011010 | 0000101

  加上 msb，则

  1 0011010 | 0 0000101 （0x9a 0x05）

• 解码过程：
  编码结果为 1#0011010 0#000 0101 （9a 05），与第一个例子类似，但是这里的第一个字节 msb = 1，所以需要再读一个字节，第二个字节的 msb = 0，则读取两个字节后停止。读到两个字节后先去掉两个 msb，剩下：

  0011010  000 0101

  将这两个 7-bit 组反转得到补码：

  000 0101 0011010

  然后还原其原码为 666。

注意：这里编码数字 666，Varints 只使用了 2 个字节 。而正常情况下 int32 将使用 4 个字节存储数字 666。

注意事项

varints编码真的牛逼，可以省略高位的零，进而压缩二进制编码，
比如这里编码数字 666，Varints 只使用了 2 个字节。而正常情况下 int32 将使用 4 个字节存储数字 666。

int32 val = 666; // 设置一个 int32 的字段的值 val = 666; 这时编码的结果如下
原码：000 ... 101 0011010 (一共32位) // 666 的源码
补码：000 ... 101 0011010 （一共32位） // 666 的补码
Varints 编码：1#0011010  0#000 0101 （9a 05）  // 666 的 Varints 编码

储存的数字过大导致效率降低

现在每个字节都拿出一个 bit 做 msb，而原先这个 bit 是可直接用来表示 Value 的，现在每个字节都少了一个 bit 位即只有 7 位能真正用来表达 Value。那就意味这 4 个字节能表达的最大数字为 2^28，而不再是 2^32 了。
这意味着什么？意味着当数字大于 2^28 时，采用 Varints 编码将导致分配 5 个字节，而原先明明只需要 4 个字节，此时 Varints 编码的效率不仅不是提高反而是下降。

但这并不影响 Varints 在实际应用时的高效，因为事实证明，在大多数情况下，小于 2^28 的数字比大于 2^28 的数字出现的更为频繁。

负数问题

注意，因为负数必须在最高位（符号位）置 1，这一点意味着无论如何，负数都必须占用所有字节，所以它的补码总是占满 8 个字节。你没法像正数那样去掉多余的高位（都是 0）。再加上 msb，最终 Varints 编码的结果将固定在 10 个字节。

为什么是十个字节？ int32 不应该是 4 个字节吗？这里是 ProtoBuf 基于兼容性的考虑（比如开发者将 int64 的字段改成 int32 后应当不影响旧程序），而将 int32 扩展成 int64 的八个字节。
为什么之前讲正数的时候没有这种扩展？。请仔细品味 Varints 编码，正数的前提下 int32 和 int64 天然兼容！

所以目前的情况是我们定义了一个 int32 类型的变量，如果将变量值设置为负数，那么直接采用 Varints 编码的话，其编码结果将总是占用十个字节，这显然不是我们希望得到的结果。如何解决？

ZigZag 编码

在上一节中我们提到了 Varints 编码对负数编码效率低的问题。

为解决这个问题，ProtoBuf 为我们提供了 sint32、sint64 两种类型，当你在使用这两种类型定义字段时，ProtoBuf 将使用 ZigZag 编码，而 ZigZag 编码将解决负数编码效率低的问题。

ZigZag 的原理和概念比我们想象的简单易懂，一句话就可概括介绍 ZigZag 编码：

ZigZag 编码：有符号整数映射到无符号整数，然后再使用 Varints 编码

zigzag编码原理解析

引用自：

版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/weixin_43708622/article/details/111397290

例如，对于负数-1，(11111111 11111111 11111111 11111111)补，全为1。

我们知道补码的最高位是符号位，对于负数，符号位为1，它阻碍了对于无意义0的压缩；既然有阻碍，那就得想办法解决这个阻碍；是否可以将符号位移动到补码的最后，然后数据位整体左移1位，这样就能把这个“阻碍”解决呢？

循环左移一位

$(-1)_{10}$

(11111111 11111111 11111111 11111111)补

符号位移动到最低位，数据位整体相对左移1位

(11111111 11111111 11111111 11111111)移位

对于绝对值小的负数，冗余的前导1还是很多；似乎解决的并不彻底

把数据位按位取反，符号位保持不变

(00000000_00000000_00000000_00000001)取反

除了符号位之外按位取反

经过移位和取反操作后，-1被“编码”成了1。如此，便能很好的压缩数据，精彩！

对于非负整数，只需完成 符号位移到最低位，数据位整体左移1位

我们再来看看整数1通过同样的处理后被“编码”成什么值。

$(1)_{10}$

(00000000 00000000 00000000 00000001)补

(00000000 00000000 00000000 00000010)移位

经过移位操作后，1被“编码”成了2。

综上

我们在使用Protobuf的时候要注意，字段的范围，看看他是否可能为负数，看看他是否可能超出 $2^{28}$