Base 128 Varints

 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编码，值为字符序列或者二进制码流

评论

1 楼 yhxf_ie 2017-03-24  

             通俗易懂