L04: fibdrv

主講人: jserv / 課程討論區: 2023 年系統軟體課程

返回「Linux 核心設計/實作」課程進度表

整數編碼

閱讀〈Integer Encoding Algorithm 筆記〉及 invertedtomato/integer-compression

Variable Byte

Variable Byte 的方式是企圖採用最少的位元組來存取，使用最前面的 1 個 bit 當作 flag 來確認資料是否串聯下一個位元組 (若為 0 代表這是 LSB least sinificant bytes) 剩下 7 個 bits 拿來存資料:

數值 (unsigned long)	binary (32 bits)	Encode Variant
0	00000000 00000000 00000000 00000000	00000000
127	00000000 00000000 00000000 01111111	01111111
128	00000000 00000000 00000000 10000000	10000001 00000000
4294967295	11111111 11111111 11111111 11111111	10001111 11111111 11111111 11111111 01111111

這個方法採用最少位元組去編碼，但因為每 32-bits 使用 4 個位元去判斷是否為 LSByte 因此造成當我們要編碼的數值 超過

$2^{28}-1$ 的時候，編碼的位元組數反而會比沒編碼的位元組數多 1。

Run Length encoding (RLE)

根據第一個數字來判定後一個整數的重複次數來做壓縮，比如:

5 5 5 5 8 8 8 2 2 2 2 2

可被壓縮成:

4 5 3 8 5 2

若連續都為不同的數:

1 2 3 4 5 6

則會用一個負數來代表連續不同數的個數:

-6 1 2 3 4 5 6

這種編碼壓縮的方法特性很明顯:就是在數字間熵值 (entropy) 大時 (數字幾乎都不重複) 時，壓縮率很差。做為 Fibonacci 計算數值的壓縮來說，不是好的選擇。

Delta of Delta + Variable length coding

Delta 是個編碼常用的技巧，比如一個整數陣列為 [ 100, 109, 105, 117, 93] 根據我們的 delta 就可以編碼為 : [100, 9, 5, 17, -7]。再者繼續編成 delta of delta (DoD) : [100, 9, -4, 12, -24]。當我們產生出這種 DoD 格式的編碼之後，我們需要使用 Variable length coding (VLC) 的方法產生出 tag bits 才能在 Decode 階段正確的把 DoD 格式還原成原本的整數數值陣列， VLC 的方法用以下表格舉例:

DoD	tag bits	following bits
0	0	0
[-64,63]	10	7 bits
[-512,511]	110	10 bits
[-4096,4095]	1110	13 bits
[-32768,32767]	11110	16 bits
else	11111	64 bits

使用 DoD 的好處是:由於是目前這個整數數值與上一個整數數值的相差大小，因此即便一開始找的數值很差，對於 DoD 的影響就比單純使用 Difference 方法小。然後因為 tag bits 由左開始連續個 1 ，所以解碼是唯一不會有混淆的情況發生。這裡壓縮的效率與數值的變化是否很大有關。以 fib_drv bignum 而言，每個 apm_digits 的大小為 64-bits (根據我的電腦) 。因此分析最差的情況是 DoD 為需要 69 bits 去儲存下一個數。實際情況則要再分析是否能有效壓縮。

Binary Packing (BP128)

Binary Packing 技巧是判斷整數陣列裡面最大的值需要用幾個 bits 去儲存，其他數值也用相同的 bits 數去儲存即可。

102, 3332, 12, 7,33, 65535 

可以看到我們的最大值為 65535 (

$2^{16}-1$)，代表我們每一個整數都用 16 bits 去儲存。這裡也有一個問題就是這個陣列的數值最大值是否與我們原先編碼的 bytes 數有足夠的優化空間(比如我們最大值預期為原先編碼 bytes 數的 1/2 以下)。