Go:二进制编码机制

Question

我正在尝试制作一个新的二进制编码包，因为标准的 Go 编码/二进制包并不完全符合我的要求。

我不明白的是为什么编码/二进制在 binary.PutUvarint 中使用 x >>= 7 而不是 x >>= 8。如果我理解正确的话，这是故意将位移动 7 而不是 8，这导致总大小为 80 位来存储 uint64 而不是 64 位，这显然是所需的位数。为什么？这是什么原因？这一定与它正在生成可变长度的 byte slice 这一事实有关，但为什么 >>7 会对此有所帮助？

这里给出二进制编码函数供大家引用:

func PutUvarint(buf []byte, x uint64) int {
    i := 0
    for x >= 0x80 {
        buf[i] = byte(x) | 0x80
        x >>= 7
        i++
    }
    buf[i] = byte(x)
    return i + 1
}

Answer 1

encoding/binary/varint.go

package binary

// This file implements "varint" encoding of 64-bit integers.
// The encoding is:
// - unsigned integers are serialized 7 bits at a time, starting with the
//   least significant bits
// - the most significant bit (msb) in each output byte indicates if there
//   is a continuation byte (msb = 1)
// - signed integers are mapped to unsigned integers using "zig-zag"
//   encoding: Positive values x are written as 2*x + 0, negative values
//   are written as 2*(^x) + 1; that is, negative numbers are complemented
//   and whether to complement is encoded in bit 0.
//
// Design note:
// At most 10 bytes are needed for 64-bit values. The encoding could
// be more dense: a full 64-bit value needs an extra byte just to hold bit 63.
// Instead, the msb of the previous byte could be used to hold bit 63 since we
// know there can't be more than 64 bits. This is a trivial improvement and
// would reduce the maximum encoding length to 9 bytes. However, it breaks the
// invariant that the msb is always the "continuation bit" and thus makes the
// format incompatible with a varint encoding for larger numbers (say 128-bit).

无损数据压缩的经典技术是霍夫曼编码，其中较常见的符号通常使用比不太常见的符号更少的位数来表示。实际上，较小的数字最常出现。因此，如果我们能够有效地表示小数，即使较大数的表示效率较低，我们也将获得无损数据压缩。

Uvarint 是一种使用一个或多个字节序列化无符号整数的方法。较小的数字占用较少的字节数。 uvarint 中的每个字节，除了最后一个字节，都设置了最高有效位 (msb)——这表明还有更多的字节要来。每个字节的低 7 位用于存储 7 位组中的数字，最低有效组在前。我们可以对具有任意位数的无符号整数执行此操作。

例如，

uint bits : uvarint bytes
7 7f : 1 7f 
14 3fff : 2 ff7f 
21 1fffff : 3 ffff7f 
28 fffffff : 4 ffffff7f 
35 7ffffffff : 5 ffffffff7f 
42 3ffffffffff : 6 ffffffffff7f 
49 1ffffffffffff : 7 ffffffffffff7f 
56 ffffffffffffff : 8 ffffffffffffff7f 
63 7fffffffffffffff : 9 ffffffffffffffff7f 
64 ffffffffffffffff : 10 ffffffffffffffffff01 

依此类推，对于我们想要的任意多的 uint 位。

如果我们有很多数字表示为无符号 64 位整数的 1 到 49 位，序列化为 1 到 7 字节的 uvarint，我们不会关心是否有几个数字表示为 57到 64 位无符号 64 位整数，序列化为 9 到 10 字节的 uvarint。

引用资料:

Huffman coding

Variable-length quantity