解讀 Golang 標準庫裏的 varint 實現

最近發現 Golang 標準庫竟然自帶了 varint 的實現，代碼位置在 encoding/binary/varint.go。剛好藉助 golang 標準庫的 varint 源碼，我們來系統地學習和梳理下 varint。

熟悉 protobuf 的人肯定對 varint 不陌生，protobuf 裏面除了帶 fix (如 fixed32、fixed64) 之外的整數類型, 都是 varint 編碼。

varint 主要是爲了解決兩個問題：

1. 空間效率：以 uint64 類型爲例，可以表示的最大值爲 18446744073709551615。然而在實際業務場景中，我們通常處理的整數值遠小於 uint64 的最大值。假設在我們的業務中，需要處理的整數值僅爲 1，但在網絡傳輸過程中，我們卻需要使用 8 個字節來表示這個值。這就導致了大量的空間浪費，因爲大部分字節並沒有實際存儲有效的信息。varint 編碼通過使用可變長度的字節序列來表示整數，使得小的整數可以用更少的字節表示，提高空間效率。

2. 兼容性：varint 使得我們可以在不改變編碼 / 解碼邏輯的情況下，處理不同大小的整數。這意味着我們可以在不破壞向後兼容性的情況下，將一個字段從較小的整數類型（如 uint32）升級到較大的整數類型（如 uint64）

本文將通過分析 Golang 標準庫自帶的 varint 源碼實現，介紹 varint 的設計原理以及 Golang 標準庫是如何解決 varint 在編碼負數時遇到的問題。

varint 的設計原理

varint 的設計原理非常簡單：

• 7bit 爲一組：將整數的二進制表示分爲 7 個 bit 位一組。從低位到高位，每 7 個 bit 位作爲一個單元。

• 最高位表示 “繼續” 標誌。在每個 7 位的單元前面添加一個標誌位，形成一個 8 位的字節。如果後面還有更多的字節，這個標誌位就設置爲 1，否則設置爲 0。

例如：對於一個整數 300，它的二進制表示是 100101100。我們可以將它分爲兩組，即 10 和 0101100。然後在每組前面添加標誌位，得到兩個字節 00000010 和 10101100，這兩個字節就是 300 的 varint 編碼。相比於用 uint32 的 4 字節表示，少了 50% 的存儲空間。

無符號整數的 varint

在 Golang 標準庫中有兩套 varint 的函數: 分別用於無符號整數的 PutUvarint 和 Uvarint，以及用於有符號整數的 Varint 和 PutVarint。

我們先看下無符號整數的 varint 實現，代碼如下：

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。這個常量對接下來的邏輯非常重要：

1. x >= 0x80。這意味着 x 的二進制表示形式至少有 8 位，我們剛纔講到 7 個 bit 位爲一組，那 x 就需要被拆分了。

2. byte(x) | 0x80。將 x 的最低 8 位與 1000 0000 進行按位或操作，然後將結果存儲在 buf[i] 中。這樣 既可以將最高位設置爲 1，同時也提取出了 x 的最低 7 位。

3. x >>= 7. 將 x 右移 7 位，處理下一個分組。

4. buf[i] = byte(x)。當 for 循環結束時，即意味着 x 的二進制表示形式最高位必然是 0。此時就不用做額外的補零操作了。

Uvarint 是 PutUvarint 的逆過程，本文就不再詳解了。

需要注意的是，varint 將整數劃分爲 7 位一組。這意味着，對於大整數 varint 將會出現負向優化。例如對於 uint64 的最大值來說，本來只需要 8 個 byte 來表示，但在 varint 中卻需要 10 個字節來表示了。（64/7 ≈ 10）

負數的編碼：zigzag 編碼

看似 varint 編碼已經完美無缺了，但以上忽略了一點：負數的存在。

我們知道，在計算機中數字是用補碼來表示的，而負數的補碼則是將其絕對值按位取反再加 1。這就意味着一個很小的負數，它的二進制形式對應於一個非常大的整數。例如：對於一個 32 位的整數 -5 來說，其絕對值 5 的二進制形式是 101。但 -5 的二進制形式卻是 11111111111111111111111111111011，如果使用 varint 對其編碼, 需要 5 個字節才能表示。

Golang 標準庫引入了 zigzag 編碼來解決這個問題，zigzag 的原理非常簡單：

• 對於正數 n，會將其映射爲 2n。例如整數 2，經過 zigzag 編碼之後變成了 4。

• 對於負數 -n 來說，會將其映射爲 2n-1。例如負數 -3，經過 zigzag 編碼之後變成了 5。

這樣負數和正數在數值上完全不會衝突，正整數和負整數交錯排列，這也是爲什麼叫做 zigzag 編碼 (鋸齒形編碼）的原因。同時，負數被轉換成正數之後，二進制編碼也精簡了許多。

例如：對 -5 進行 zigzag 編碼後，變成了 9，對應於二進製爲 00000000000000000000000000001001，使用 1 個字節即可表示 varint。

我們看下 Golang 標準庫的實現，代碼如下：

func PutVarint(buf []byte, x int64) int {
 // zigzag 編碼
 ux := uint64(x) << 1
 if x < 0 {
  ux = ^ux
 }
 return PutUvarint(buf, ux)
}

從代碼可以看出，對於有符號整數的 varint 實現，golang 標準庫這裏分成了兩步：

1. 先對整數進行 zigzag 編碼進行轉換

2. 對轉換之後的數值再進行 varint 編碼

我們詳細講下 zigzag 編碼的實現部分：

• 正數：ux := uint64(x) << 1。這個位運算左移一位，相當於 ux*2。對於正數，符合 ZigZag 編碼。

• 負數：ux := uint64(x) << 1; ux = ^ux。負數這裏就有些難以理解了，爲什麼這麼轉換之後就等於2n - 1了？

我們可以大概推導下整個過程，假設我們有個整數 -n：

1. 對原數值先左移，再進行取反。其實可以看做：對原數值先取反，再左移，然後 + 1。即 2*(~(-n))+1

2. 我們知道負數的補碼=絕對值按位取反+1，那如何根據補碼再推導出絕對值？這裏有個公式是：|A| = ~A+1

3. 我們將這個公式帶到第一步的式子裏面：2*(n-1) + 1 = 2n - 1。這就完美對應上了負數的 ZigZag 編碼。

在 Golang 標準庫裏面，調用 PutUvarint 時只會使用 varint 編碼，調用 PutVarint 會先進行 zigzag 編碼，再進行 varint 編碼。

而在 protobuf 中，如果類型是 int32、int64、uint32、uint64，只會使用 varint 編碼。使用 sint32、sint64 將先進行 zigzag 編碼，再進行 varint 編碼

varint 不適用的情況

雖然 varint 編碼設計非常精妙，但並不適用於所有的場景：

• 大整數：對於非常大的整數，varint 編碼可能會比固定長度的編碼更消耗空間。例如當所有的整數值域大於 2^63，那使用 varint 會用到 10 字節。相比於傳統的八字節整數，反而多用了 25% 的空間

• 需要快速隨機訪問的數據：由於 varint 是變長編碼，所以我們無法直接通過索引來訪問特定的整數，必須從頭開始解碼，直到找到我們需要的整數。這使得 varint 編碼不適合用於需要快速隨機訪問的數據。

• 需要頻繁進行數學運算的數據：由於 varint 編碼的數據需要先解碼才能進行數學運算，所以如果一個應用需要頻繁地對數據進行數學運算，那麼使用 varint 編碼可能會導致性能下降。

• 安全敏感的應用：varint 編碼的數據可能會暴露出一些關於原始整數的信息，例如它的大小。在某些安全敏感的應用中，這可能是不可接受的。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/oMALoiY_8dZWunfWuUcVNg