Go:二进制编码的机制

Question

我正在尝试创建一个新的二进制编码包,因为标准的Go编码/二进制包并不能完全符合我的要求.

我不明白的是为什么编码/二进制文件正在使用x >>= 7中binary.PutUvarint代替x >>= 8.如果我理解正确,这是故意将位移位7而不是8,这导致整体大小为80位来存储uint64而不是64位,这显然是所需的位数.为什么？这是什么原因？这必须与它生成可变长度的字节切片这一事实有关,但为什么>> 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

编码/二进制/ 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).

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

Uvarints是一种使用一个或多个字节序列化无符号整数的方法.较小的数字占用较少的字节数.除最后一个字节外,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位数.

如果我们有很多数字表示为1到49位的无符号64位整数,序列化为1到7个字节的uvarints,我们不会在意我们是否有一些表示为57到64位的数字无符号64位整数的序列化为9到10个字节的uvarints.

参考文献:

霍夫曼编码

可变长度数量