# 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，預估此舉能夠大幅提升效能。
正在努力開發中...
Sign in with Wallet
Connect another wallet