研究 Protobuf 时发现一个挺好的算法 — ZigZag

2021年11月26日 阅读数:2
这篇文章主要向大家介绍研究 Protobuf 时发现一个挺好的算法 — ZigZag,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

收录于《深刻微服务》,做者 “老苗”git

我本来是想研究 Protobuf 原理呢,但在研究过程当中发现 Protobuf 在对负数编码时使用到了 ZigZag 算法,因此才有了本篇。固然你不懂 Protobuf 也彻底不影响阅读。github

在聊这个算法以前,咱们先聊聊进制、补码相关的东西。若是你懂,那就指向往下翻。算法

该篇代码:网络

https://github.com/miaogaolin/gofirst/tree/main/zigzagapp

进制

所谓进制,就是当某一位上的信息满时,须要往前进位。好比,十进制,就是当某一位上的数满十时进位;而某一位上的数满二时进位就是二进制,等等。函数

进位之间均可以相互转化,例如:微服务

十进制:10 → 二进制:1010 → 十六进制:Aui

我以前看过一个答案,说:为何十进制比较通用?编码

由于咱人类只有 10 个手指头,数一遍恰好十个数,因此十进制天然就成为默认的进制。那若是人类长 11 手指头,说不定就是十一进制。url

后来计算机的出现,一个数据的有无是最自然的信息承载单元,因此由 0 和 1 组成的二进制很天然成为计算机的进制方式。在此基础上,为了方便信息的使用,又采用了八进制、十六进制。

好了,进制这个东西就聊到这了。

三个东西

下来咱们对一个十进制正整数表示为二进制,例如:十进制 10 等于二进制 1010。

那若是二进制表示一个负数,该怎么办?下来咱们聊聊。

在计算机的世界里,定义了原码、反码和补码这几个东西。为了下来说解简单点,咱们假设使用一个字节(1Byte=8bits)表示一个数。

1. 原码

咱们用第一个位表示符号( 0 为非负数,1 为负数),剩下的位表示值。例如:

  • +8 → 原:00001000
  • -8 → 原: 10001000

2. 反码

咱们用第一位表示符号( 0 为非负数,1 为负数),剩下的位,非负数保持不变,负数按位求反。例如:

  • +8 → 原:0000 1000 → 反:0000 1000
  • -8 → 原:1000 1000 → 反:1111 0111

若是咱们用原码或者补码来表示整数的二进制,有什么问题吗?表面上看,彷佛挺好的。不过仔细思考就会发现两个问题:

第一,0 竟然能够用两个编码表示,+0 和 -0。

  • 原:0000 0000 → 1000 0000
  • 反:0000 0000 → 1111 1111

第二,计算机不知道符号位的存在,所以参加运算后,会出现一个奇怪的现象。

  • 原码

1 + (-1)

→ 0000 0001 + 1000 0001

→ 1000 0010

→ -2

明显是不对的!

  • 反码

1 + (-1)

→ 0000 0001 + 1111 111

→ 1111 1111

→ -0

这看起来也怪怪的。

所以,为了解决这些问题,咱们在计算机体系中引入了补码。

3. 补码

咱们用第一位表示符号( 0 为非负数,1 为负数),剩下的位非负数保持不变,负数按位求反末位加一。

  • +8 → 原:0000 1000 → 补:0000 1000
  • -8 → 原:1000 1000 → 补:1111 1000

如今咱们看看,把符号带进去运算会出现什么结果?

1 + (-1)

→ 0000 0001 + 1111 1111

→ 0000 0000

→ 0

很明显,经过这样的方式,计算机进行运算的时候,就不用关心符号这个问题,统一都按照满 2 进 1 规则处理。

好了,进制和补码的知识就说到这了,下来进入真正的主题。

ZigZag

在大多数状况下,咱们使用到的整数每每会比较小。

而咱们为了在系统通信时便于传输,每每须要一个整形(int3二、int64)做为基本的传输类型。

所以在大多数系统中,以 4 Bytes 和 8 Bytes 来表示。这样,为了传输一个整型 1,咱们须要传输 “00000000 00000000 00000000 00000001” 32 个 bits,而有价值的数据只有 1 位,剩下的都是浪费呀!

那怎么办呢?ZigZag 应用而生。那这个算法具体的思想是怎么样的呢?

对于正整数来说,若是在传输数据时,咱们把多余的 0 去掉,或者尽量的减小无心义的 0。那么咱们是否是就能够将数据进行压缩?那怎样进行压缩?

答案也很简单,例如 00000000 00000000 00000000 00000001 这个数。若是咱们只发送 1 位 或者 1 字节 00000001,是否是就会很大程度减小无用的数据?

固然,若是这个世界上只有正整数,那咱们就能够方便的作到这一点。惋惜,他竟然存在负数!那负数如何表示?

例如,十进制 -1 的补码表示为 11111111 11111111 11111111 11111111。

能够看到,前面全是 1,你说怎么弄?

ZigZag 给出了一个很巧妙的方法。咱们以前讲补码说过,补码的第一位是符号位,他阻碍了咱们对于前导 0 的压缩,那么,咱们就把这个符号位放到补码的最后,其余位总体前移一位。

补:**1**1111111 11111111 11111111 11111111

→ 符号后移:11111111 11111111 11111111 111111**1**

可是即便这样,也是很难压缩的。因而,这个算法就把负数的全部数据位按位求反,符号位保持不变,获得了这样的整数,以下:

十进制:-1

→ 补:**1**1111111 11111111 11111111 11111111

→ 符号后移:11111111 11111111 11111111 1111111**1**

→ ZigZag:00000000 00000000 00000000 0000000**1**

而对于非负整数,一样的将符号位移动到最后,其余位往前挪一位,数据保持不变,以下:

十进制:1

→ 补:**0**0000000 00000000 00000000 00000001

→ 符号后移:00000000 00000000 00000000 0000001**0**

→ ZigZag:00000000 00000000 00000000 0000001**0**

这样一弄,正数、0、负数都有一样的表示方法了。咱们就能够对小整数进行压缩了,对吧~

因而,就能够写成以下的代码:

func int32ToZigZag(n int32) int32 {
	return (n << 1) ^ (n >> 31)
}

n << 1 将整个值左移一位,无论正数、0、负数他们的最后一位都会变成了 0。讲解以下:

十进制:1

→ 补:**0**0000000 00000000 00000000 00000001

→ 左移一位:00000000 00000000 00000000 00000010

十进制:-1

→ 补:**1**1111111 11111111 11111111 11111111

→ 左移一位:11111111 11111111 11111111 11111110

n >> 31 将符号位放到最后一位。若是是非负数,则为全 0;若是是负数,就是全 1。讲解以下:

十进制:1

→ 补:**0**0000000 00000000 00000000 00000001

→ 右移 31 位:00000000 00000000 00000000 0000000**0**

十进制:-1

→ 补:**1**1111111 11111111 11111111 11111111

→ 右移 31 位:11111111 11111111 11111111 1111111**1**

最后这一步很巧妙,将二者进行按位异或操做。

十进制:1

n << 1 :00000000 00000000 00000000 00000010 ^

n >> 31: 00000000 00000000 00000000 0000000**0**

→ 00000000 00000000 00000000 0000001**0**

能够看到最终结果,数据位保持不变,而符号位也保持不变,只是符号位移动到了最后一位。

十进制:-1

n << 1:11111111 11111111 11111111 11111110 ^

n >> 31:11111111 11111111 11111111 1111111**1**

→ 00000000 00000000 00000000 0000000**1**

能够看到,数据位所有反转了,而符号位保持不变,且移动到了最后一位。这一步真的写的很巧妙!

ZigZag 还原代码以下:

func toInt32(zz int32) int32 {
	return int32(uint32(zz)>>1) ^ -(zz & 1)
}

相似的,咱们还原的代码就反过来写就能够了。不过这里要注意一点,就是右移的时候,须要用不带符号的移动,不然若是第一位是 1 的时,移动时会补1。因此,使用了无符号的移位操做uint32(zz)>>1

好了,有了该算法,就能够获得一个有前导 0 的整数。只是,该数据依然使用 4 字节存储。下来咱们要考虑如何尽量的减小字节数,而且还能还原。

例如,咱们将 1 按照如上算法转化获得:00000000 00000000 00000000 00000010。

下来咱们最好只须要发送 2 bits(10),或者发送 8 bits(00000010),把前面的 0 所有省掉。由于数据传输是以字节为单位,因此,咱们最好保持 8 bits这样的单位。因此咱们有 2 种作法:

  • 咱们能够额外增长一个字节,用来表示接下来有效的字节长度,好比:00000001 00000010,前 8 位表示接下来有 1 个字节须要传输,第二个 8 位表示真正的数据。这种方式虽然能达到咱们想要的效果,可是莫名的增长一个字节的额外浪费。有没有不浪费的办法呢?
  • 字节自表示方法。ZigZag 引入了一个方法,就是用字节本身表示本身。具体怎么作呢?咱们来看看代码。
func compress(zz int32) []byte {
	var res []byte
	size := binary.Size(zz)
	for i := 0; i < size; i++ {
		if (zz & ^0x7F) != 0 {
			res = append(res, byte(0x80|(zz&0x7F)))
			zz = int32(uint32(zz) >> 7)
		} else {
			res = append(res, byte(zz&0x7F))
			break
		}
	}
	return res
}

你们先看看代码里那个 ^0x7F,他到底是个什么数呢?

  • ^0x7F:11111111 11111111 11111111 10000000

他就是从倒数第八位开始,高位全为 1 的数。他的做用就是去除最后七位后,判断还有没有信息。

咱们把 ZigZag 值传递给这个函数,这个函数就将这个值从低位到高位切分红每 7 bits 一组,若是高位还有有效信息,则给这 7 bits 补上 1 个 bit 的 1(0x80)。如此反复 直到全是前导 0,便结束算法。

举个例来说:

十进制:-1000

→ 补:**1**1111111 11111111 11111100 00011000

→ ZigZag:00000000 00000000 00000111 1100111**1**

咱们先按照七位一组的方式将上面的数字划开,0000 0000000 0000000 0001111 1001111。

详细步骤以下:

  1. 他跟 ^0x7F 作与操做的结果,高位还有信息,因此,咱们把低 7 位取出来,并在倒数第八位上补一个 1(0x80):11001111。
  2. 将这个数右移七位,0000 0000000 0000000 0000000 0001111。
  3. 再取出最后的七位,跟 ^0x7F 作与操做,发现高位已经没有信息了(全是0),那么咱们就将最后 8 位完整的取出来:00001111,而且跳出循环,终止算法。
  4. 最终,咱们就获得了两个字节的数据 [11001111, 00001111]。

经过上面几步,咱们就将一个 4 字节的 ZigZag 变换后的数字变成了一个 2 字节的数据。若是咱们是网络传输的话,就直接发送这 2 个字节给对方进程。对方进程收到数据后,就能够进行数据的组装还原了。具体的还原操做以下:

func decompress(zzByte []byte) int32 {
   var res int32
   for i, offset := 0, 0; i < len(zzByte); i, offset = i+1, offset+7 {
      b := zzByte[i]
      if (b & 0x80) == 0x80 {
         res |= int32(b&0x7F) << offset
      } else {
         res |= int32(b) << offset
         break
      }
   }
   return res
}

整个过程就和压缩的时候是逆向的,对于每个字节,先看最高一位是否有 1(0x80)。若是有,就说明不是最后一个数据字节包,那取这个字节的最后七位进行拼装。不然,说明就是已经到了最后一个字节了,那直接拼装后,跳出循环,算法结束。最终获得 4 字节的整数。

结语

算法不是很复杂,遇到哪块不懂了,就好好观察想一想,这也是对 Protobuf 原理理解的重要部分。若是有不懂的,就在下方给我留言!

完整代码:

https://github.com/miaogaolin/gofirst/tree/main/zigzag