contributed by < LiChiiiii >
題目 - L04: fibdrv
開發環境
原本的程式碼是利用 dynamic programming 來計算,時間複雜度為 ,空間複雜度為 。因此改為使用 clz / ctz 一類的指令,搭配 Fast Doubling 使得時間複雜度降到 ,空間複雜度降到 。
原本的費氏數列定義為:
經過矩陣的推導後,可得到對於奇數和偶數的不同算法:
根據這個公式,每次進入 recursive
的數字一定是前一個數字的一半,而且 recursive tree
不會有增長,每次呼叫只會重複呼叫自己一次而已。
使用 __builtin_clzll
來計算有多少 leading 0s。
遇到 0
: 求 和
遇到 1
: 求 和 ,再求 (第 15 行的條件式)
以 為例: 610 = 1102
i | start | 3 | 2 | 1 | result |
---|---|---|---|---|---|
n | - | 110 | 110 | 110 | - |
F(n) | F(0) | F(0*1+1) = F(1) | F(2*1+1) = F(3) | F(2*3) = F(6) | F(6) |
a | 0 | 1 | 2 | 8 | 8 |
F(n) | F(1) | F(0*1+2) = F(2) | F(2*1+2) = F(4) | F(2*3+1) = F(7) | - |
b | 1 | 1 | 3 | 13 | - |
參考 L04: fibdrv
原始程式碼以 long long
來儲存費氏數列的計算結果,但是在 之後的運算會發生 overflow,導致無法正確地計算結果。因此自行定義結構 BigN
來儲存 128 位元的整數:
其中 lower
表示低位的 64 位元, upper
表示高位的 64 位元。
BigN
結構體的運算,包含加法運算、減法運算、乘法運算、右移 1 bit、左移 1 bit。其中BigN的乘法運算使用左移右移和加法運算來實作,減少原乘法運算的成本。各自計算兩個 64 位元整數的和,若 res.lower < a.lower
則要進位 upper
。
各自計算兩個 64 位元整數的差,若 a.lower < b.lower
則要借位 upper
。
使用了一個 while
循環來將 b
不斷右移,同時將 a
左移。在每次循環中,如果 b
的最低位是1,則將 a
加入到 res 中,最終得到 a
和 b
的乘積 res
。
最後利用上述自定義的結構和函數來更改程式碼:
原始程式碼在 fibdrv.c 中的 fib_read()
回傳計算出的 Fibonacci 數,最初想法是將 fib_read()
回傳的 ssize_t
的型態更改成自定義的 BigN
傳給 client ,但是不能隨意更改 read ,且在使用者模式的位址空間配置一個 buffer 空間時,核心裝置驅動不能直接寫入該地址,因此使用到 copy_to_user ,將想傳給使用者模式 (即運作中的 client) 的值複製到到fib_read()
的 buf 參數後,client 端方可接收到此值並印出。
上述程式碼修正過後發現 可以得到正確的數值,但是 之後依然是錯誤的。那是因為在 BigN_add()
中的 res.lower = a.lower + b.lower
發生了 overflow 。
我嘗試加上 (a.lower+b.lower) < a.lower
判斷低 64 位元在相加時是否發生 overflow ,若發生則宣告 128 位元的 temp
存放相加後的值,再將 temp & 0xFFFFFFFFFFFFFFFF
取出低 64 位元,並右移 64 位元取得進位的值(第 8 、 9 行)。
修正完的結果依然是錯誤的。
舉例來說, = 19740274219868223167 ,在 BigN_add()
希望可以得到 res.upper = 1
和 res.lower = 9740274219868223167
,但 19740274219868223167
在二進制取出的低 64 位元得到的會是 1293530146158671551
。
因此我嘗試將第 8 行改成使用 mod 來得到我想要的餘數,卻出現以下錯誤訊息:
顯然必須避免使用 128 位無符號整數取模運算。
我嘗試將 upper 轉成 __int128 的型態並左移 64 bits(就是乘上 的意思),接著將 upper 和 lower 轉成字串之後相加,來避免 overflow 的問題。最後把欲回傳運算結果轉成字串後存入 buf ,再由 client 印出存在 buf 的字串。
字串反轉
128 位元的整數轉成字串
兩個字串相加
更改結果成功印出正確數值。
使用 ktime
在核心模組中測量執行時間,發現 fib_write
此暫時沒作用,因此在此函式實作並回傳 kernel space 的執行時間。
使用 clock_gettime
計算在呼叫 fib_write
時所需的時間,可得到 user space 的執行時間。兩數相減即可得到 system call 的時間。
導入 driver.py 去除 95% 區間之外的值,可以把圖中的尖端消除掉。