Varint 及其在 Golang 中的应用

发表于 2024-09-29 | 阅读次数: |

| 字数统计: 1,492 | 阅读时长 ≈ 6

Go 标准库中有一个 varint 的内置实现，可以在 encoding/binary/varint.go 中找到。这个实现类似于 protobuf 中使用的 varint。利用 Golang 标准库的 varint 源代码，我们将系统地学习和复习 varint 的概念。如果您熟悉 protobuf，您可能已经知道所有整数类型（除了固定类型，如 fixed32 和 fixed64）都使用 varint 编码。
varint 主要解决了两个问题：

空间效率：以 uint64 为例，它可以表示 18,446,744,073,709,551,615 这样大的数值。但在大多数实际应用中，我们的整数值要小得多。如果你的系统需要处理小到 1 的值，那么在传输过程中，你仍然需要使用 8 个字节来表示这个值，这就浪费了空间，因为大多数字节并不存储有用的数据。varint 编码使用长度可变的字节序列来表示整数，从而减少了较小值所需的空间。

兼容性：varint 允许我们在不改变编码/解码逻辑的情况下处理不同大小的整数。这意味着字段可以从较小的类型（如 uint32）升级到较大的类型（如 uint64），而不会破坏向后兼容性。

本文将深入研究 Golang varint 的实现，探讨其设计原理以及如何应对负数编码的挑战。

varint 的设计原则

varint 的设计基于简单的原则：

7 位分组：整数的二进制表示分为 7 位组。从最小有效位到最大有效位，每个 7 位组都是一个单位。
延续位：在每个 7 位组之前添加一个标志位，形成一个 8 位字节。如果后面有更多字节，则标志位设置为 1；否则设置为 0。

例如，整数 uint64(300) 的二进制表示为 100101100。将其分为两组-10 和 0101100，再加上标志位，就得到两个字节：00000010 和 10101100，这就是 300 的 varint 编码。与使用 4 个字节的 uint64 相比，varint 减少了 75% 的存储空间。

// list1:  uint64 to varint
func main() {  
    v := uint64(300)  
    bytes := make([]byte, 0)  
    bytes = binary.AppendUvarint(bytes, v)  
    fmt.Println(len(bytes))  
    for i := len(bytes); i > 0; i-- {  
       fmt.Printf("%08b ", bytes[i-1])  
    }  
}

varint 表示无符号整数

Go 标准库提供了两组 varint 函数：一组用于无符号整数（PutUvarint、Uvarint），另一组用于有符号整数（varint、Putvarint）。让我们先看看无符号整数 varint 的实现：

// list2: go src PutUvarint
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
}

代码中有一个基本常数：0x80 相当于二进制代码 1000 0000。这个常数对后面的逻辑非常重要：

x >= 0x80：这将检查 x 是否需要超过 7 位的表示。如果需要，则需要拆分 x。
byte(x) | 0x80：这将对 0x80（1000 0000）进行位操作，确保最高位设置为 1，并提取 x 的最低 7 位。
x >>= 7：将 x 右移 7 位，以处理下一组。
buf[i] = byte(x)：当循环结束时，最高位全为 0，因此无需进一步操作。

Uvarint 与 PutUvarint 相反。

需要注意的是：varint 将整数分成 7 位组，这意味着大整数可能会面临效率低下的问题。例如，uint64 的最大值需要 10 个字节，而不是通常的 8 个字节（64/7 ≈ 10）。

负数编码之字形编码

虽然 varint 的效率很高，但它并不考虑负数。在计算中，数字是以 2 的补码形式存储的，这意味着一个小的负数可能有一个很大的二进制表示。例如，32 位形式的 -5 表示为 1111111111111111111111111011，在 varint 编码中需要 5 个字节
Go 使用之字形编码来解决这个问题：

对于正数 n，将它们映射为 2n。
对于负数-n，将其映射为 2n-1。
例如，对 int32(-5) 进行 “之 “字形编码后，其值变为 9（000000000000000000001001），而 varint 只需 1 个字节即可表示该值。

下面是 Golang 的实现：

// go src Putvarint
func Putvarint(buf []byte, x int64) int {
    ux := uint64(x) << 1
    if x < 0 {
        ux = ^ux
    }
    return PutUvarint(buf, ux)
}

从代码中我们可以看到，对于有符号整数 varint 的实现，Go 标准库将其分为两个步骤：

首先，使用 ZigZag 编码转换整数。
然后，使用 varint 对转换后的值进行编码。

对于负数，还有一个额外的步骤：ux = ^ux。这部分可能会让人感到困惑–为什么这种变换的结果是 2n -1？

假设我们有一个整数 -n，我们可以大致推导出这个过程：

首先，将原值左移，然后倒置。结果是 2*(~(-n)) + 1。
负数的二进制是其绝对值加 1 的位反转。那么，我们如何从二的补码得出绝对值呢？有这样一个公式|A| = ~A + 1。

将此公式代入第一步：2*（n - 1）+ 1 = 2n - 1。这与负数的 ZigZag 编码完全吻合。

在 Go 标准库中，调用 PutUvarint 只应用 varint 编码，而调用 PutVarint 则首先应用 ZigZag 编码，然后再应用 varint 编码。

在 protobuf 中，如果类型是 int32、int64、uint32 或 uint64，则只使用 varint 编码。但是，对于 sint32 和 sint64，首先使用 ZigZag 编码，然后使用 varint 编码。

当 varint 不适用时

尽管 varint 有很多优点，但它并不是所有情况下都适用：

大整数：对于大整数，varint 编码的效率可能低于定长编码。
随机数据访问：由于 varint 使用可变长度，直接索引特定整数具有挑战性。
频繁的数学运算：变量编码数据需要在运算前解码，可能会影响性能。
安全敏感型应用：varint 编码可能会泄露原始整数大小的信息，这在安全环境中是不可接受的。

-------------The End-------------

cloud sjhan wechat

subscribe to my blog by scanning my public wechat account