Go中varint压缩编码原理分析

编码介绍

varint是一种将整数编码为变长字节的压缩编码算法，本篇文章就是分析该编码算法的原理以及看一看go中的源码实现。

计算机中，整型数据是按照补码进行存储的，varint编码的原理就是将整数按照7bits划分，在最高位设置一个有效位表示后面是否还有该整数的部分，当最高位为1时表示后面还有该数据的字节，为0表示该字节是最后一个字节。

无符号整数

较小的值

举个例子：对于一个uint32来说，无论数字多大，都会占用4个字节的大小空间。对0000 0000 0000 0000 0000 0000 0000 0001 进行编码：

1. 首先将该数字按照7位进行分组

0000 0000000 0000000 0000000 0000001
1

2. 依次从低字节开始读，发现只需要一个字节就能表示,后面没有可用的字节，最高位置0

0000 0001
1

所以最终对1的编码只占用一个字节

较大的值

对0000 1111 1111 0000 1111 0000 1111 1111 进行编码

1. 首先按照7bit进行分组

0000 1111111 1000011 1100001 1111111
1

2. 依次读取低位字节进行编码

|  1111111 |  1100001 |  1000011 |  1111111 | 0000 |
 
| 11111111 | 11100001 | 11000011 | 01111111 |  
1
2
3

所以最终该数字占用 4 个字节

Go中的实现

go中关于varint编码的实现在binary包下，这里参考的是Go1.20

编码PutUvarint

func PutUvarint(buf []byte, x uint64) int {
  i := 0
  for x >= 0x80 {
    // 将该字节的最高位置 1， 表示后面还有数据
    buf[i] = byte(x) | 0x80
    // 将x向右移动7位(按照7bit进行分组的过程)
    x >>= 7
    i++
  }
  buf[i] = byte(x)
  return i + 1
}
1
2
3
4
5
6
7
8
9
10
11
12

循环条件就是判断当前x的值是否能用一个字节表示，大于0x80说明不能使用一个字节表示。

解码Uvarint

func Uvarint(buf []byte) (uint64, int) {
  var x uint64
  var s uint
  // 遍历buf中的每个字节，低位字节表示原数据的高位
  for i, b := range buf {
    // 如果i达到了64位数据所能编码的最大字节数，说明溢出
    if i == MaxVarintLen64 {
      // Catch byte reads past MaxVarintLen64.
      // See issue https://golang.org/issues/41185
      return 0, -(i + 1) // overflow
    }
    // 如果该字节小于0x80，说明该字节是最后一个有效字节
    if b < 0x80 {
      // 对于一个uint64的数据来说，64 % 7 = 1，所以最终只会多出1bit
      // 如果 b > 1,说明原数据并不是64位的，溢出
      if i == MaxVarintLen64-1 && b > 1 {
        return 0, -(i + 1) // overflow
      }
      return x | uint64(b)<<s, i + 1
    }
    // 将b最高位置0，加到x上
    x |= uint64(b&0x7f) << s
    s += 7
  }
  return 0, 0
}
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

有符号整数

较小的值(指绝对值)

对原码为1000 0000 0000 0000 0000 0000 0000 0001 的负数进行编码

负数的补码 = 除符号位外的位取反 + 1

1. 首先计算数字的补码，负数的补码是除符号位外取反+1

1111 1111 1111 1111 1111 1111 1111 1111
1

2. 按照7bit进行分组

 | 1111 | 1111111 | 1111111| 1111111 | 1111111 |
1

3. 编码

|  1111111 |  1111111 |  1111111 |  1111111 | 1111 |
| 11111111 | 11111111 | 11111111 | 11111111 | 0000 1111 |
1
2

所以最终-1占了5个字节

较大的负数(只绝对值)

对原码为1111 1111 1111 0000 0000 0000 0000 0001 的负数进行编码

1. 首先计算数字的补码，负数的补码是除符号位外取反+1

1000 0000 0000 1111 1111 1111 1111 1111
1

2. 按照7bit进行分组

1000 0000000 0111111 1111111 1111111
1

3. 编码

|  1111111 |  1111111 |  0111111 |  0000000 | 1000 |
| 11111111 | 11111111 | 10111111 | 10000000 | 0000 1000 |
1
2

由此可得，最终占用5个字节

Go中的实现

编码PutVarint

妙！！！

func PutVarint(buf []byte, x int64) int {
  // 去掉符号位，忽略符号位的影响，更方便处理
  ux := uint64(x) << 1
  // 如果x为负数，则对ux进行取反，此时最低位一定是1
  // 而对于正数来说，最低位始终为 0，也为解码时判断正负做了铺垫
  if x < 0 {
    ux = ^ux
  }
  // 经过上面的处理，如果x为负数，ux 为 x 的绝对值
  return PutUvarint(buf, ux)
}
1
2
3
4
5
6
7
8
9
10
11

解码Varint

func Varint(buf []byte) (int64, int) {
  ux, n := Uvarint(buf) // ok to continue in presence of error
  // 和上面的操作是相对的，因为最低位原本不属于原数据
  x := int64(ux >> 1)
  // 如果 ux 最低位为 1，说明原数据是负数，取反
  if ux&1 != 0 {
    x = ^x
  }
  return x, n
}
1
2
3
4
5
6
7
8
9
10

总结

varint编码的思想是：

• 对于小的数字使用更少的字节进行编码
• 对于大的数字使用更多的字节进行编码

因为大多数时候，我们的应用程序中会大量使用小的数字，而只是少量使用大的数字，所以使用varint压缩编码，在一定程度上可以节省空间。

但是通过原始的算法思想对负数进行编码时，由于负数在计算机中存储的特殊性，所以不会起到很好的作用，所以go在实对负数进行压缩编码时，首先将负数转化为正数表示，也就是取绝对值的操作，并在解码时通过最后一位来判断原数据是正数还是负数，这样varint对负数的压缩也效果同样很好。