# 2023q1 Homework3 (fibdrv)
contributed by `HaurHaur`
## 開發環境

$ gcc -version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture:           x86_64
  CPU op-mode(s):       32-bit, 64-bit
  Address sizes:        39 bits physical, 48 bits virtual
  Byte Order:           Little Endian
CPU(s):                 16
  On-line CPU(s) list:  0-15
Vendor ID:              GenuineIntel
  Model name:           Intel(R) Core(TM) i7-10700F CPU @ 2.90GHz
    CPU family:         6
    Model:              165
    Thread(s) per core: 2
    Core(s) per socket: 8
    Socket(s):          1
    Stepping:           5
    CPU max MHz:        4800.0000
    CPU min MHz:        800.0000
    BogoMIPS:           5799.77

## 開發紀錄
### VSCode 設定
參考 [Eroiko](https://hackmd.io/@Eroiko/fibdrv-impl) 的方法，對 C/C++ Extension 設定檔做修改，解決 VSCode include 紅色底線的問題。
### Fast doubling 測試
#### Naïve approach
#### Dynamic programming
#### Fast doubling (recursive)
#### Fast doubling (iterative)

### Makefile 分析
為了實作 Big Num 需要對 Makefile 做修改，所以先理解原本的 Makefile 是如何把 driver 載入 kernel 內的。

# Makefile
obj-m := $(TARGET_MODULE).o

`obj-m` 為指定最終要建立成的 `.ko` 檔是由哪些 `.o` 檔組成的，此例為 `fibdrv.o`，由於沒有 `fibdrv.o` 這個 target，Makefile 會自動執行 `gcc -c fibdrv -o fibdrv.o`，若 driver 由多個 `.o` 檔組成須加上 `<module_name>-y := <src1>.o <src2>.o ...`。
例如：

obj-m  := fibdrv.o
fibdrv-y := f1.o f2.o f3.o

# Makefile
KDIR := /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)
$(MAKE) -C $(KDIR) M=$(PWD) modules

`shell uname -r` 為取得 kernel 版本，所以 `KDIR` 為建立 kernel module 的 makefile 所在目錄，`shell pwd` 為目前所在目錄，也就是要被建立的 driver 所在目錄。第三行展開後相當於執行 `make -C /lib/modules/5.19.0-38-generic/build M=/home/haur/linux_2023/fibdrv modules`。其中 `-C` 參數會使 make 移動到該目錄。執行完 make 後就會產生一個 kernel object 檔(.ko)，接下來使用 `insmod fibdrv.ko` 就可以把 driver 載入 kernel 中。
### 大數運算
#### 結構體

typedef struct  _bn
{
    unsigned int *number;
    unsigned int size;
    int sign;
} bn;

#### bn_to_string

//bn_to_string
// log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
size_t len = (8 * sizeof(int) * src.size) / 3 + 2 + src.sign;

為計算 x 的 10 進位位數，其中 x 為 `bn src` 所存的數值，之所以要加上 2 ，其中一個 1 是為了存 `\0`，另一個是因為 x 需要 $log_{10}(x) + 1$ 位。