研究 Protobuf 時發現一個挺好的演算法 — ZigZag

語言: CN / TW / HK

收錄於《深入微服務》,作者 “老苗”

我原本是想研究 Protobuf 原理呢,但在研究過程中發現 Protobuf 在對負數編碼時使用到了 ZigZag 演算法,所以才有了本篇。當然你不懂 Protobuf 也完全不影響閱讀。

在聊這個演算法之前,我們先聊聊進位制、補碼相關的東西。如果你懂,那就指向往下翻。

該篇程式碼:

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

進位制

所謂進位制,就是當某一位上的資訊滿時,需要往前進位。比如,十進位制,就是當某一位上的數滿十時進位;而某一位上的數滿二時進位就是二進位制,等等。

進位之間都可以相互轉化,例如:

十進位制:10 → 二進位制:1010 → 十六進位制:A

我之前看過一個答案,說:為什麼十進位制比較通用?

因為咱人類只有 10 個手指頭,數一遍剛好十個數,所以十進位制自然就成為預設的進位制。那如果人類長 11 手指頭,說不定就是十一進位制。

後來計算機的出現,一個數據的有無是最天然的資訊承載單元,所以由 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

在大多數情況下,我們使用到的整數往往會比較小。

而我們為了在系統通訊時便於傳輸,往往需要一個整形(int32、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 原理理解的重要部分。如果有不懂的,就在下方給我留言!

完整程式碼:

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