# 2023q1 Homework3 (fibdrv) contributed by < `SPFishcool` > ## 開發環境 ```shell $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.1.0-asahi-2-2-ARCH Uptime: 12 mins Packages: 1207 (pacman) Shell: zsh 5.9 Resolution: 2560x1600 DE: Plasma 5.27.2 WM: KWin Theme: [Plasma], Breeze [GTK2/3] Icons: [Plasma], breeze [GTK2/3] Terminal: konsole CPU: (8) @ 2.424GHz Memory: 3746MiB / 15650MiB $ gcc -v Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/lib/gcc/aarch64-unknown-linux-gnu/12.1.0/lto-wrapper Target: aarch64-unknown-linux-gnu Configured with: /build/gcc/src/gcc/configure --enable-languages=c,c++,fortran,go,lto,objc,obj-c++ --enable-bootstrap --prefix=/usr --libdir=/usr/lib --libexecdir=/usr/lib --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=https://github.com/archlinuxarm/PKGBUILDs/issues --with-linker-hash-style=gnu --with-system-zlib --enable-__cxa_atexit --enable-checking=release --enable-clocale=gnu --enable-default-pie --enable-default-ssp --enable-gnu-indirect-function --enable-gnu-unique-object --enable-linker-build-id --enable-lto --enable-plugin --enable-shared --enable-threads=posix --disable-libssp --disable-libstdcxx-pch --disable-multilib --disable-werror --host=aarch64-unknown-linux-gnu --build=aarch64-unknown-linux-gnu --with-arch=armv8-a --enable-fix-cortex-a53-835769 --enable-fix-cortex-a53-843419 Thread model: posix Supported LTO compression algorithms: zlib zstd gcc version 12.1.0 (GCC) ``` ## 改善 big number fibonacci ### 初步嘗試 初步嘗試使用 `list_head` 改善大數問題，參考 [fibdrv:加速 Fibonacci 運算](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d)裡的 `list_head` 結構，首先我建立 `NEW_NODE`、`FULL_ADD64`、 `bn_add_smaller` 、`bn_to_string` 等函式和 `bn_node` 的 entry。 ```c static long long fib_sequence_bn(long long k, char *buf){ struct list_head *h1 = kmalloc(sizeof(*h1), GFP_KERNEL), *h2 = kmalloc(sizeof(*h2), GFP_KERNEL); if (!h1 || !h2) return 0; INIT_LIST_HEAD(h1); INIT_LIST_HEAD(h2); NEW_NODE(h1, 1); NEW_NODE(h2, 0); ``` 一開始預設 `h1` 為大數 `h2` 為小數，每次加完的數值就會存回 `h2`，因此在每次加完數後將 `h1` 、 `h2` 進行 swap ```c for (int i = 2;i <= k;i++){ bn_add_smaller(h1, h2); swap(h1, h2); } ``` 在 `bn_add_smaller` 裡會進行 `FULL_ADD64`，`FULL_ADD64` 會將兩數進行加法，`overflow` 內存入進位數，若有進位則為 `1`，否則為 `0`。 ```c #define FULL_ADD64(a, b, carry) \ ({ \ uint64_t res = (a) + (b) + (carry); \ uint64_t overflow = -!!(res >= BOUND64); \ (b) = res - (BOUND64 & overflow); \ overflow; \ }) ``` 如果回傳發現有 overflow ，表示這個節點數值超過了，就會新增新的節點存取接下來的數值。 最後再將這些節點的數值一一存成字串，最後將其 reverse （如果從最低位數開始存的話）。 ```c while (*cur != bn){ uint64_t val = list_entry(*cur, bn_node, link)->value; while(val > 0){ *p = (val % 10) + '0'; val /= 10; p++; } cur = &(*cur)->next; } *p = '\0'; // '\0' is end of String. bn_strnrev(str, len); ``` 經過 lab0 的經驗，若字串處理最後沒有結束字元（'\0'），在使用字串相關函式或 `printf` 有可能會發生 Segmentation fault！ 在完成函式後嘗試將字串能夠讓 [./client.c](https://github.com/SPFishcool/fibdrv/blob/master/client.c) 輸出，一開始想讓函式回傳 `char *` ```c static char *fib_sequence_bn(long long k) ``` 後來發現這個 `fibdrv.c` 裡面的 `read` function 是輸出 `ssize`，也就是一個數值，並不能這樣改，後來發現 `copy_to_user` 這個函式可以將字串貼到我們 [./client.c](https://github.com/SPFishcool/fibdrv/blob/master/client.c) 所設定的 buffer 上，因此函式可以輸出字串長度以便後續將我們存入的字串取出。 ```c if (k == 0) { __copy_to_user(buf, "0", 2); return 1; } __copy_to_user(buf, str, len + 1); return len; ``` 目前進度：能夠計算 $f(92)$ 以上 ### Binary Big Number By `list_head` 因為實作 Faster Doubling 的特性，十進位用運算會用到大量乘法，不妨嘗試實作使用二進制表示的 `list_head` Big Number。 首先，進制改變後程式修改最明顯的就是 `bn_to_string` ，原本是每個位數一一取出再將其轉為字串放入，但是二進制轉為十進制字串不適合這麼做，因為每考慮到一個位數整個數字都有可能會變動到，參考 [fibdrv:加速 Fibonacci 運算](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-d)中的 `bn_to_string`，這裡將從 linked list 的 tail 的最高位元開始拜訪，每拜訪一位就會將字串裡的數字乘二，相當於整數右移一位。 ```c for (struct list_head *cur = bn->prev;cur != bn;cur = cur->prev) { uint32_t val = list_entry(cur, bn_node, link)->value; for (uint32_t bit = 1UL << 31;bit;bit >>= 1) { int carry = !!(val & bit); for (int i = len - 2;i >= 0;i--) { dec_str[i] += dec_str[i] - '0' + carry; carry = (dec_str[i] > '9'); if (carry) dec_str[i] -= 10; } } } ``` 正在努力開發中... ## Faster Doubling ### 初步嘗試 在實作 Faster Doubling 會運用到大量乘法，若使用十進制進行運算並不是一個明智之舉，但若使用二進位進行運算，可以將乘法用位移和加法代替，再將 `bn_to_String` 功能寫成 binary to decimal String，預估此舉能夠大幅提升效能。 正在努力開發中...
Last changed by  
 
SPFishcool
196

Read more

4/16 一對一問題回復

linux 核心的 list_sort 實作考量 在 linux 核心的 list_sort 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。 此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容） 其效能比較根據如下（q_sort 為 lab0-c 實作之排序）： q_sort#nodecache-missesbranchesinstructionscontext-switch1000346977,9884516,04010100003,3403621,93744305,89500100000543,05326326,21194,3295,3471010000007491,55474,6974,191731,6153,305510 list_sort#nodecache-missesbranchesinstructionscontext-switch1000248977,7798519,92400100004,1257614,20284329,38450100000439,19226258,06964,3642,0292310000005824,68914,6028,350731,6579,34489

5/8/2023
2023q1 Homework6 (quiz6)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.2.0-asahi-11-1-edge-ARCH Uptime: 16 hours, 7 mins

4/27/2023
2023q1 Homework1 (lab0)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout OS: Ubuntu 22.04.1 LTS x86_64 Host: GL552VW 1.0 Kernel: 5.15.0-60-generic Uptime: 13 hours, 20 mins Packages: 1877 (dpkg), 9 (snap) Shell: bash 5.1.16

4/16/2023
2023q1 Homework2 (quiz2)

contributed by < SPFishcool > 測驗一 運作原理 程式裡 next_pow2(x) 要找出最接近且大於等於 x 的 2 的冪次方的值。 在改寫程式裡，有著幾行類似下方的程式碼。 x |= x >> 1; 這會讓 x 右移一位並將 1 set 到原本的 x 上，例如： 00100000 變成 00110000、 00100110 變成 00110111。

3/13/2023
Read more from SPFishcool
Published on HackMD