浅析 Protobuf 整形编码方式:Varint 与 Zigzag

Protocol Buffer (简称Protobuf) 是Google出品的性能优异、跨语言、跨平台的序列化库。

为了更好的硬件效率,计算机中的数字通常使用定长整形(fixed length intergers)表示。然而在遍地微服务的今天,需要一种更灵活的方式传输数字以节省带宽。Varint (Variable length integers)便是一种用于压缩整形数字的方法。由于整数的分布并不是均匀的,相比于很大的整数,我们使用小的整数要更多一些,而 Varint 可以灵活地调整不同大小的整形所占的字节数。

Varint 编码

Protobuf 中的 Varint 根据整型大小与 128 的倍数关系进行不定长二进制编码,小于 128 的整型编码后占 1个字节,小于 256 的整型编码后占 2 个,依此类推,最多可以使用 10 个字节表示大于等于 2 的 63 次的整型;也就是说,当使用 Varint 编码 int32 范围内的整型时编码效率最高。为啥是 128 的倍数呢,这与其实现原理有关,如下图:

image.png

编码后的每个字节,首位标识是否为尾部,后续 7 位用于记录原始数字的二进制位,举个栗子,299 在 int32 下的二进制是

00000000 00000000 00000001 00101011

编码后的结果为 10101011 00000010,即每次传输可以节省 2 个字节,其对应的实现如下:

const maxVarintBytes = 10 // maximum length of a varint
// EncodeVarint returns the varint encoding of x.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
// Not used by the package itself, but helpful to clients
// wishing to use the same encoding.
func EncodeVarint(x uint64) []byte {
	var buf [maxVarintBytes]byte
	var n int
	for n = 0; x > 127; n++ {
		// 首位记 1, 写入原始数字从低位始的 7 个 bit
		buf[n] = 0x80 | uint8(x&0x7F)
		// 移走记录过的 7 位
		x >>= 7
	}
	// 剩余不足 7 位的部分直接以 8 位形式存下来,故首位为 0
	buf[n] = uint8(x)
	n++
	return buf[0:n]
}

里边使用了 2 个魔数,看一下它们的二进制就能理解了,& 0x7f 取得 7 个 bit,| 0x80 将首位标记为 1。

0x80 => 0000000010000000
0x7f => 0000000001111111

所以 Varint 的反序列化方式便是取每个字节的后 7 位逆序拼接,如下图(以 299 的编码结果举例):

image.png

源码如下:

// DecodeVarint reads a varint-encoded integer from the slice.
// It returns the integer and the number of bytes consumed, or
// zero if there is not enough.
// This is the format for the
// int32, int64, uint32, uint64, bool, and enum
// protocol buffer types.
func DecodeVarint(buf []byte) (x uint64, n int) {
	for shift := uint(0); shift < 64; shift += 7 {
		if n >= len(buf) {
			return 0, 0
		}
		b := uint64(buf[n])
		n++
		// 弃首位取 7 位并加回 x
		x |= (b & 0x7F) << shift
		// 首位为 0
		if (b & 0x80) == 0 {
			return x, n
		}
	}
	// The number is too large to represent in a 64-bit value.
	return 0, 0
}

这里有一个问题,EncodeVarintDecodeVarint 处理的都是 uint64 类型,如果我们需要处理负数呢?看看直接将负数作为 uint64 进行编码会得到什么:

fmt.Println(EncodeVarint(uint64(-299)))
// output:
// [213 253 255 255 255 255 255 255 255 1]

结果会得到 10 个字节的编码,因为 uint64(-299) 的值为 299 的补码,需要用 64 位表示!也就是最终会得到 varint 编码的最大长度,官方库中计算编码字节长度的源码如下:

// SizeVarint returns the varint encoding size of an integer.
func SizeVarint(x uint64) int {
	switch {
	case x < 1<<7:
		return 1
	case x < 1<<14:
		return 2
	case x < 1<<21:
		return 3
	case x < 1<<28:
		return 4
	case x < 1<<35:
		return 5
	case x < 1<<42:
		return 6
	case x < 1<<49:
		return 7
	case x < 1<<56:
		return 8
	case x < 1<<63:
		return 9
	}
	return 10
}

Zigzag

Zigzag 编码将有符号整型映射到无符号整型,如其名,编码后的值在正数与负数整型间摇摆,如下表:

Signed OriginalEncoded As
00
-11
12
-23
21474836474294967294
-21474836484294967295

其实现如下:

func Zigzag64(x uint64) uint64 {
	// 左移一位 XOR (-1 / 0 的 64 位补码)
	return (x << 1) ^ uint64(int64(x) >> 63)
}

这里要注意的是若 x 为负数,XOR 左边为 -x 的补码左移一位。下图以 -299 为例,先计算 299 补码,再 XOR 符号(-1 / 0)的补码,结果为 597;若为正数,Zigzag 的结果为原数的 2 倍。

image.png

小结

在写这篇文章的时候顺便复习了一波基础知识,比如 Varint 编码负数结果为什么是 10 个字节,原因就是负数是以补码的形式存储的。所以大学里看似入门的概念却是实际编程中都会遇到的东西,路漫漫其修远兮~

https://juejin.im/post/5dfe0c49f265da33bb43b3ba

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
JAVA
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论