Base 128 Varints

博客分类：

互联网

Google

Google Protobuf里面提出了“Base 128 Varints”编码，这是一种变字节长度的编码，官方描述为：varints是用一个或多个字节序列化×××的一种方法。我理解要点有三个(1)操作是序列化(2)操作对象是×××(3)变长编码。重点是最后一点，他是如何编码的呢？

      （1）除了最后一个字节，varint中的每个字节的最高位设为1，表示后面还有字节出现

      （2）每个字节的低7位看成是一个组（group），这个组和他相邻的下一个7位组共同存储某个×××的“组合表示”，最低有效组在前面。

   上面的定义可能比较生硬，我没看具体例子之前，也没搞明白，我们来看http://code.google.com/intl/zh-CN/apis/protocolbuffers/docs/encoding.html#varints中的例子：

       (1)一个字节。下面只有一个字节，所以最高位是0，表示十进制1

           0000 0001

       (2)两个字节。

           1010 1100 0000 0010

       由于第一个字节后面还有一个字节，所以第一个字节的最高位设置为1，表示后面还有后继字节，第二个字节的最高位为0。去掉每个字节的最高位，我们对两个字节进行分组。第一个7位组：0101100，第二个7位组：0000010，组合起来就是：0101100 0000010，由于最低有效组在前面，所以两个7位组进行调换，结果为：0000010  0101100，中间的空格是为了大家区分，去掉前面的0，也就是：100101100，十进制为1*2^8 + 1*2^5 + 1*2^3 + 1*2^2 = 256 + 32 + 8 + 4 = 300。

      （3）三个字节。我们换种方式，给定某个×××，要求写出他的varint表示，这里当然是落在需要3个字节表示的×××。16380可以吗？不可以！因为16380 < 2^14，所以2个字节足以，我们就以27491为例，27491的二进制表示为：

0110 1011 0110 0011

       注意这里是高字节之前，低字节在后，和varint的编码规则相反，首先按照7位一组划分为：0000001 1010110  1100011，然后反转为：1100011 1010110  0000001，最后将末尾的7位组前面补0组成一个字节，两个7位组都补1分别组成一个字节：

11100011 11010110  00000001

(4)更多字节。聪明的你可能发现，varint编码中4个字节最大表示的数为2^28,非常正确，同时说明了天下没有免费的午餐，有得有失。Protobuf引入了fixed32解决这个问题的，如果某个字段经常大于2^28,应当优选fixed32，他是固定长度为32位的。

    三．String和bytes

    string和bytes的表示形式一致，都是“长度+值”，其中长度采用varint编码，值为字符序列或者二进制码流