skoo's notes

努力记录一些自己觉得有趣的东西...
30 September 2013
by skoo

我首次见到Base 128 Varint这个编码算法是在Google protobuf中,也不知道在它之前是否就已经出现了。最近,又碰到有人问如何对一个整数进行变长编码?也就是说给定的一个整数,能用1个字节存储就用一个字节的内存,需要两个字节存储就用两个字节的内存,而不是统一固定用4个字节或者8个字节。好处显然是非常明显的,特别是在二进制网络协议设计的时候,对整数进行变长编码很有必要。

protobuf关于Base 128 Varint的介绍:https://developers.google.com/protocol-buffers/docs/encoding,这个文档展示的例子是如何根据一个Base 128 Varint编码的二进制序列解码出整数。这里完整的介绍一下,如何用Base 128 Varint算法去编码一个整数,以及解码一个二进制序列。

Base 128 Varint,为什么叫128?其实,就是因为只采用7bit的空间来存储有效数据,7bit当然最大只能存储128了。常规的一个byte是8个bit位,但在Base 128 Varint编码中,将最高的第8位用来作为一个标志位,如果这一位是1,就表示这个字节后面还有其他字节,如果这个位是0的话,就表示这是最后一个字节了,这样一来,就可以准确的知道一个整数的结束位置了。

就以protobuf文档中的整数300为例,先看一下如何将300编码成二进制序列。

300的二进制表示为:100101100,显然300这个整数只需要2个字节就可以存储了,根本不需要4个字节。

第一步:从低位到高位7bit划开,最后不足7bit的剩余部分用0补齐。也就是:0000010 0101100

第二步:反转字节顺序。结果:0101100 0000010。这其实就是规定了字节序的问题。

第三步:填充标志位。上一步产生的二进制序列,每个组只有7个bit位,不足8bit,因为还没有加上最高位的标志位。这一步加上标志位后就是:10101100 00000010。这样就得到了300经过base 128 varint编码后的结果了,2个字节搞定。

拿到二进制数据进行解码的过程当然就是编码过程的一个逆序了,这个一点难度都没有了。不过,这里的过程是人类自然语言的描述,和实际用计算语言来描述还是存在一点差异的。所以,如果真有一种程序语言可以用自然语言的方式来书写代码,那真的是很牛逼的样子。

Base 128 Varint编码算法其实挺简单的,简单到我还码这么多文字,都快觉得不好意思了。还是再附带一下代码,方便以后自取。

int encode_varint(char *buf, uint64_t x)
{
    int n;

    n = 0;

    while (x > 127) {
        buf[n++] = (char) (0x80 | (x & 0x7F));
        x >>= 7;
    }

    buf[n++] = (char) x;
    return n;
}

uint64_t decode_varint(char *buf)
{
    int      shift, n;
    uint64_t x, c;

    n = 0;
    x = 0;

    for (shift = 0; shift < 64; shift += 7) {
        c = (uint64_t) buf[n++];
        x |= (c & 0x7F) << shift;
        if ((c & 0x80) == 0) {
            break;
        }
    }

    return x;
}

用C简单的实现了对uint64_t类型的整数的变长编码和解码的函数,可以看出代码其实是很简单的。这个代码可以再优化一下,实现一个更加通用的版本。

十一玩开心!