varint 和 zigzag 编码

发表于 | 分类于
本文字数: 1.2k | 阅读时长 ≈ 4 分钟

200508-head-varint

varint

varint是一种压缩二进制整数的方法，编码过程中会将二进制中高位中连续n个0舍弃，因而对于较小的整数有很好的压缩效果。以无符号int32为例，正常存储需要4个字节，而经过varint编码后，对于较小的整数只需要1个字节。

编码原理

varint编码中，字节顺序按照小端序存储，每个字节的第1位称为最高有效位(most significant bit - msb)，后7位表示实际的值。msb为1则表示后面的字节还是属于当前的数据的，如果msb为0则表示这个字节是当前数据的最后一个字节。

大端序与小端序(引用自Wiki字节序))：

字节的排列方式有两个通用规则。例如，一个多位的整数，按照存储地址从低到高排序的字节中，如果该整数的最低有效字节（类似于最低有效位）在最高有效字节的前面，则称小端序；反之则称大端序。在网络应用中，字节序是一个必须被考虑的因素，因为不同机器类型可能采用不同标准的字节序，所以均按照网络标准转化。

例如假设上述变量x类型为int，位于地址0x100处，它的值为0x01234567，地址范围为0x100~0x103字节，其内部排列顺序依赖于机器的类型。大端法从首位开始将是：0x100: 01, 0x101: 23,..。而小端法将是：0x100: 67, 0x101: 45,..

以数字202058为例，首先将 00000000 00000011 00010101 01001010 从低位到高位按照每7位划分，按照小端序排列，如果不是最后1个字节，则在第一位补1，否则补0：

200508-varint

原本需要使用4个字节存储的数字，经过varint编码后只需要3字节存储，同时也可以看到对于较小的数字(如100)，只需要1个字节存储。

实现(java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
 * 解码
 *
 * @param bs 待编码字节列表
 * @return 解码数字
 */
private static int decodeVarint32(byte[] bs) {
    int x = 0;
    int s = 0;
    for (byte b : bs) {
        int unsignByte = Byte.toUnsignedInt(b); // 使用无符号数为例
        if (unsignByte < 0x80) {
            return x | unsignByte << s;
        }
        x |= (unsignByte & 0x7f) << s;
        s += 7;
    }
    return x;
}

/**
 * 编码
 *
 * @param value 待编码数字
 * @return 编码后字节列表
 */
private static byte[] encodeVarint32(int value) {
    byte[] bs = new byte[computeLength(value)];
    int index = 0;

    while (true) {
        if (value >= 0x80) {
            bs[index] = (byte) ((value & 0x7F) | 0x80);
            value >>>= 7;
            index++;
        } else {
            bs[index] = (byte) (value);
            break;
        }
    }
    return bs;
}

/**
 * 计算varint所需字节数
 *
 * @param value 目标值
 * @return 所需字节数
 */
private static int computeLength(int value) {
    if ((value & (0xffffffff << 7)) == 0) {
        return 1;
    }
    if ((value & (0xffffffff << 14)) == 0) {
        return 2;
    }
    if ((value & (0xffffffff << 21)) == 0) {
        return 3;
    }
    if ((value & (0xffffffff << 28)) == 0) {
        return 4;
    }
    return 5;
}

zigzag

可以看到varint对于无符号整数的处理还是不错的，但是对于有符号数，由于最高位是是符号位，如果是负数，那最高位就是1，这种情况下varint就会使用5个字节存储，会比原来更加浪费空间。zigzag编码就是为了解决负数问题的，同时其对正数也没有很大的影响。

编码

int类型zigzag编码为(n << 1) ^ (n >> 31)：

  1. 左移1位去除符号位，最低位补0
  2. 右移31位将符号位放到最低位，如果负数高位补1，正数高位补0
  3. 按位异或

以1为例，为00000000 00000000 00000000 00000001，左移一位00000000 00000000 00000000 00000010，右移31位00000000 00000000 00000000 00000000，对二者异或00000000 00000000 00000000 00000010，可以看到数据位保持不变，而符号位移动到了最后一位。

以-1为例，为11111111 11111111 11111111 11111111，左移一位11111111 11111111 11111111 11111110，右移31位11111111 11111111 11111111 11111111，对二者异或00000000 00000000 00000000 00000001，可以看到数据位全部反转了，而符号位移动到了最后一位。

在这种情况下，可以先使用zigzag编码，后使用varint编码

解码

int类型zigzag解码为(n >>> 1) ^ -(n & 1)：

  1. 无符号右移一位
  2. 按位与1，然后取负值(对于正数就是0，负数就是-1)
  3. 按位异或

以zigzag编码后00000000 00000000 00000000 00000010为例，无符号右移一位00000000 00000000 00000000 00000001，按位与100000000 00000000 00000000 00000000，取负值00000000 00000000 00000000 00000000，对二者异或00000000 00000000 00000000 00000001，结果为1。

以zigzag编码后00000000 00000000 00000000 00000001为例，无符号右移一位00000000 00000000 00000000 00000000，按位与100000000 00000000 00000000 00000001，取负值11111111 11111111 11111111 11111111，对二者异或11111111 11111111 11111111 11111111，结果为-1。

在这种情况下，可以先使用varint解码，后使用zigzag解码

参考

varint和zigzag编码

详解varint编码原理

小而巧的数字压缩算法：zigzag