# 2023q1 Homework3 (fibdrv)
contributed by < [davidlai1999](https://github.com/davidlai1999) >

## 開發環境

$ 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):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
    CPU family:          6
    Model:               158
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            10
    CPU max MHz:         4100.0000
    CPU min MHz:         800.0000
    BogoMIPS:            4399.99

## 處理 fib(93) 以上的 overflow 問題
* `fib_read` 返回值的型態為 `long long`，其為 64 位元的有號整數，其有效範圍介於 $2^{64−1}−1$ 與 $−2^{64}$ 之間，在將 `fibdrv` 中的限制 `MAX_LENGTH` 擴大後比對費氏數列的輸出，發現 Fib(93) 值為 -6246583658587674878 ，已經超出`long long` 的範圍，這也是預設限制最大可用項目為 92 的原因。
> F(92) = 7540113804746346429
F(93) = -6246583658587674878
F(94) = 1293530146158671551

* 根據二補數可以求出結果為何為該數值，原先要進位的數因為型態只有 64 位元而損失了 $2^{64}$ 。

$$
\begin{equation}
\begin{aligned}
if (A + B) &> T_{Max} \quad(overflow) \\
result &= A + B - 2^{64} \\
&= F(91) + F(92) - 2^{64} \\
&= -6246583658587674878
\end{aligned}
\end{equation}
$$
* 起初打算使用 `uint128_t` 來實作，但由於 `c90` 標準並不支援此型別，改用 [linux 核心模組 ](https://hackmd.io/@sysprog/linux2023-fibdrv/%2F%40sysprog%2Flinux2023-fibdrv-b)中提出的架構改寫，這個架構由兩個無號的 `long long` 組成，可以理解成將 `lower` 溢位後得到的值放置在 `upper` 中。

struct BigN {
    unsigned long long lower, upper;
};

* 但由於在表示這個架構下的數字時， `upper` 最小也有 $2^{64} = 18446744073709551616$ ，在 `client.c` 中要輸出時不是單單印出那直觀，於是我將架構改用字元儲存，原因是因為不用特地為了溢位去做處理，不論是在計算還是輸出都相較前一個架構直觀。
* 但它也存在缺點，第一點是運算資源相較純用數字來大的多，因為 1 個字元就佔 1 個位元組，一個字串就需要 128 個位元組，遠比 `unsigned long long` 的 8 位元組來的多。第二點是配套的函式增加，不像純數字可以直接透過加減處理，字串需要做像是找出字串長度、反轉字串等等額外處理。

char str[128];

* 由於數值會優先存放於字串左邊，從字串左邊開始走訪找到第一個 `'\0'` 即可知道該字串長度，這在反轉字串會用到。

int findLSB(char *a) {
    int count = 0;
    for (;a[count] != '\0';count++)
        ;
    return count;
}

* 用字串表示數字會遇到當字串長度不同時，做相加會存在字元對不上的問題，將字串反轉再做相加會變得容易許多，用上先前實作的 `findLSB` 尋找字串長度，令字串開頭與結尾兩兩互換並同時向彼此位移，已達到將對應字元互換的效果。

void reverse(char *a) {
    int last = findLSB(a) - 1, first = 0;
    char temp;
    while (first < last) {
        temp = a[first];
        a[first] = a[last];
        a[last] = temp;
        ++first;
        --last;
    }
}

* 相加利用 [`ascii code`](https://zh.wikipedia.org/zh-tw/ASCII) 將數字放在相鄰位置的特性，只要將字元減去 `'0'` 即可得到對應該位元的數字，以此概念達到相加的效果。其中 `data_a` 放置較小的值，`data_b` 則放置較大的值。

void add (char *data_a, char *data_b, char *out) {
    int count, sum, carry = 0;

    for (count = 0; count < findLSB(data_a); count++) {
        sum = (data_a[count] - '0') + (data_b[count] - '0') + carry;
        out[count] = '0' + sum % 10;
        carry = sum / 10;
    }
    for (; count < findLSB(data_b); count++) {
        sum = (data_b[count] - '0') + carry;
        out[count] = '0' + sum % 10;
        carry = sum / 10;
    }

    if (carry)
        out[count] = '0' + carry;
}

* 不再利用單純的回傳值，而是利用 [`copy_to_user`](https://archive.kernel.org/oldlinux/htmldocs/kernel-api/API---copy-to-user.html) 將 `kernal` 運算得到的結果放入 `buffer` 中回傳，使 `user` 能透過第三個參數 `long` 得知存取對象的長度。

static ssize_t fib_sequence(long long k, char *buf)
{
    /* FIXME: C99 variable-length array (VLA) is not allowed in Linux kernel. */
    char f1[128] = "0";
    char f2[128] = "1";
    char ans[128] = "0";

    reverse(f1);
    reverse(f2);

    for (int i = 2; i <= k; i++) {
        add(f1, f2, ans);
        swap_string(ans, f1, f2);
    }

    reverse(f2);

    int check = copy_to_user(buf, f2, 128);
    if (check) {
        printk("Copy_to_user fail.");
        return -1;
    }
    return 128;
}

* 實作字串結構後，可以將 93 以上的 `fibonacci number` 計算出來。

Reading from /dev/fibonacci at offset 90, returned the sequence 2880067194370816120.
Reading from /dev/fibonacci at offset 91, returned the sequence 4660046610375530309.
Reading from /dev/fibonacci at offset 92, returned the sequence 7540113804746346429.
Reading from /dev/fibonacci at offset 93, returned the sequence 12200160415121876738.
Reading from /dev/fibonacci at offset 94, returned the sequence 19740274219868223167.
Reading from /dev/fibonacci at offset 95, returned the sequence 31940434634990099905.
Reading from /dev/fibonacci at offset 96, returned the sequence 51680708854858323072.
Reading from /dev/fibonacci at offset 97, returned the sequence 83621143489848422977.
Reading from /dev/fibonacci at offset 98, returned the sequence 135301852344706746049.
Reading from /dev/fibonacci at offset 99, returned the sequence 218922995834555169026.
Reading from /dev/fibonacci at offset 100, returned the sequence 354224848179261915075.

## 大數運算

### bn 結構體
* 為了改善前兩個方法無法動態配置這個問題，從事先規劃範圍的方法改成用 `number` 這種指標來紀錄儲存空間的位址， `size` 用來紀錄該數值需要多少 `unsigned int` 來儲存， `sign` 用來紀錄數值的正負號。
* 這裡要特別注意變數 `capacity` ，由於 bn 結構體會因為數字的增長導致需要頻繁更改儲存空間長度，這會導致 `krealloc` 對效能造成的衝擊十分嚴重，這裡引入 `memory pool` 的概念，每次配置記憶體空間以 4 的倍數為單位配置，當 `size` 小於 `capacity` 代表配置的空間尚有餘額，不需要作 `krealloc` 。

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

### 修改結構體大小
* 若 bn 結構體沒有加入 `capacity` ，除了輸入長度相同，每次 `resize` 都必須呼叫 `krealloc` 更動記憶體空間，但因為引入 `memory pool` 的概念每次配置記憶體以 4 個 `int` 為單位配置，判斷時可以先讓 `size` 與 `capacity` 作比較，如果空間真的不夠再進行 `krealloc` 。

static int bn_resize(bn *src, size_t size)
{
    if (size == src->size)
        return 0;
    if (size > src->capacity) { /* need to allocate larger capacity */
        src->capacity = (size + (ALLOC_CHUNK_SIZE - 1)) &
                        ~(ALLOC_CHUNK_SIZE - 1);  // ceil to 4*n
        src->number =
            krealloc(src->number, sizeof(int) * src->capacity, GFP_KERNEL);
    }
    if (size > src->size) { /* memset(src, 0, size) */
        for (int i = src->size; i < size; i++)
            src->number[i] = 0;
    }
    src->size = size;

    return 0;
}

* 這個方法雖然可以有效的避免 `krealloc` 所帶來的影響，但要注意到的是這方法可能配置大於需求的空間，當配置的物件過多可能會對空間造成不小的開銷。
### bn_clz and bn_msb
* `bn_clz` 用於找出該物件所持有的數從左起算有多少連續為 0 的位元，從高位的 `number[i]` 開始算，若其為 0 則代表這個 `number[i]` 並沒有用來存放數值， cnt 加 1 個 int 的大小。若其值非 0 則用 `__builtin_clz` 找出剩餘連續 0 位元。
* `bn_msb` 要求出物件中的數值在儲存上真的用上多少個位元， `src->size * 32` 為該物件最多能儲存的位元數，再減去 `bn_clz` 即可得到結果。

static int bn_clz(const bn *src)
{
    int cnt = 0;
    for (int i = src->size - 1; i >= 0; i--) {
        if (src->number[i]) {
            // prevent undefined behavior when src = 0
            cnt += __builtin_clz(src->number[i]);
            return cnt;
        } else {
            cnt += 32;
        }
    }
    return cnt;
}

static int bn_msb(const bn *src)
{
    return src->size * 32 - bn_clz(src);
}

### bn 結構體比較大小
* 比較大小是進行加減重要的運算，前者較大回傳 1 ， 後者大回傳 -1 ， 兩者相同回傳 0 。可以透過 size 先進行第一步的比較，若兩者長度相同則需要迭代一一比較數值的大小。

int bn_cmp(const bn *a, const bn *b)
{
    if (a->size > b->size) {
        return 1;
    } else if (a->size < b->size) {
        return -1;
    } else {
        for (int i = a->size - 1; i >= 0; i--) {
            if (a->number[i] > b->number[i])
                return 1;
            if (a->number[i] < b->number[i])
                return -1;
        }
        return 0;
    }
}

### 加減法
* `bn_add` 主要是在確認傳入的兩個數之正負值，若兩者同號則只須傳入 `bn_do_add` 進行相加並確保結果與數入值同好即可。
* 當兩者異號時，兩者必須作相減，必須確保無視 `sign` 後數值較大者以第 1 個引數傳入 `bn_do_sub` ，這與其實作有關。可以發現真正實作加減的並非 `bn_add` 而是 `bn_do_add` 與 `bn_do_sub` 這兩個函數。

void bn_add(const bn *a, const bn *b, bn *c)
{
    if (a->sign == b->sign) {  // both positive or negative
        bn_do_add(a, b, c);
        c->sign = a->sign;
    } else {          // different sign
        if (a->sign)  // let a > 0, b < 0
            SWAP(a, b);
        int cmp = bn_cmp(a, b);
        if (cmp > 0) {
            /* |a| > |b| and b < 0, hence c = a - |b| */
            bn_do_sub(a, b, c);
            c->sign = 0;
        } else if (cmp < 0) {
            /* |a| < |b| and b < 0, hence c = -(|b| - |a|) */
            bn_do_sub(b, a, c);
            c->sign = 1;
        } else {
            /* |a| == |b| */
            bn_resize(c, 1);
            c->number[0] = 0;
            c->sign = 0;
        }
    }
}

* 當需要實作減法時，可以將第 2 個引數的 `sign` 直接變更再帶入 `bn_add` 中，以達到兩數相減的效果。

void bn_sub(const bn *a, const bn *b, bn *c)
{
    /* xor the sign bit of b and let bn_add handle it */
    bn tmp = *b;
    tmp.sign ^= 1;  // a - b = a + (-b)
    bn_add(a, &tmp, c);
}

* `bn_do_add` 是真的將兩者的 `number` 作相加的函式，起初需要先決定兩者相加後需要用到多少空間，於是執行 `MAX(bn_msb(a), bn_msb(b)) + 1` 來得到兩者相加最多需要多少位元，接著將其與 32 一同代入 `DIV_ROUNDUP` ，意義是這多位元至少需要多少型態為 `int` 的儲存，以它來更新結果的大小。
* 接著要注意的點為 `carry` 的型態為 `unsigned long long int` ，能避免溢位問題，且將值賦予給`number` 時只有後 32 位元會使用到，將 `carry` 移位 32 位元能使原先數值只剩進位的部份，並用於下一組 `number` 的相加。

static void bn_do_add(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b)) + 1
    int d = MAX(bn_msb(a), bn_msb(b)) + 1;
    d = DIV_ROUNDUP(d, 32) + !d;
    bn_resize(c, d);  // round up, min size = 1

    unsigned long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry += (unsigned long long int) tmp1 + tmp2;
        c->number[i] = carry;
        carry >>= 32;
    }

    if (!c->number[c->size - 1] &&
        c->size > 1)  // if biggest number is 0, than resize
        bn_resize(c, c->size - 1);
}

* `bn_do_sub` 傳入的參數中前者純看 `number` 一定大於後者。它與 `bn_do_add` 的原理很相似，差別在於 `carry` 代表的並非進位而是借位，當兩者的 `number[i]` 相減後為負數代表需要借位，這時將 `carry` 加上`（1LL << 32）`等同於向前一位借位， `carry` 設為 1 是為了讓下一組 `number[i]` 運算時還借位所用到的值。由於相減可能使高位的 `number[i]` 為 0 ，最後需要重新檢測 `number` 並 `resize` 。

static void bn_do_sub(const bn *a, const bn *b, bn *c)
{
    // max digits = max(sizeof(a) + sizeof(b))
    int d = MAX(a->size, b->size);
    bn_resize(c, d);

    long long int carry = 0;
    for (int i = 0; i < c->size; i++) {
        unsigned int tmp1 = (i < a->size) ? a->number[i] : 0;
        unsigned int tmp2 = (i < b->size) ? b->number[i] : 0;
        carry = (long long int) tmp1 - tmp2 - carry;
        if (carry < 0) {
            c->number[i] = carry + (1LL << 32);
            carry = 1;
        } else {
            c->number[i] = carry;
            carry = 0;
        }
    }

    d = bn_clz(c) / 32;
    if (d == c->size)
        --d;
    bn_resize(c, c->size - d);
}

### 乘法
* 在 `bn_mult` 中，相乘結果所需位元數改用 `bn_msb` 先找出該物件持有數值在儲存上所需的位元數再將兩者的結果相加來取得。
* 採用最簡單的 `long multiplication` ，如同手算乘法一樣將該位數對定的乘積疊加上去。這裡的 `carry` 與相加時的 `carry` 同樣都是用來存取進位的， `a->number[i] * b->number[j]` 得到的值會成為 `bn_mult_add` 的引數，由它來進行乘積的疊加。

void bn_mult(const bn *a, const bn *b, bn *c)
{
    /* max digits = sizeof(a) + sizeof(b) */
    int d = bn_msb(a) + bn_msb(b);
    d = DIV_ROUNDUP(d, 32) + !d;  // round up, min size = 1
    bn *tmp;
    /* make it work properly when c == a or c == b */
    if (c == a || c == b) {
        tmp = c;  // save c
        c = bn_alloc(d);
    } else {
        tmp = NULL;
        for (int i = 0; i < c->size; i++)
            c->number[i] = 0;
        bn_resize(c, d);
    }

    for (int i = 0; i < a->size; i++) {
        for (int j = 0; j < b->size; j++) {
            unsigned long long int carry = 0;
            carry = (unsigned long long int) a->number[i] * b->number[j];
            bn_mult_add(c, i + j, carry);
        }
    }
    c->sign = a->sign ^ b->sign;

    if (tmp) {
        bn_swap(tmp, c);  // restore c
        bn_free(c);
    }
}

* `bn_mult_add` 中 `offset` 這個參數為代表乘積應該從哪個位置開始疊加，由於乘積可能大於 32 位元，疊加不能只做一次，而是要確認相加沒有產生進位或是乘積本來就小於 32 位元才可以離開此函式。

static void bn_mult_add(bn *c, int offset, unsigned long long int x)
{
    unsigned long long int carry = 0;
    for (int i = offset; i < c->size; i++) {
        carry += c->number[i] + (x & 0xFFFFFFFF);
        c->number[i] = carry;
        carry >>= 32;
        x >>= 32;
        if (!x && !carry)  // done
            return;
    }
}

### 位移
* `bn_lshift` 用於實作 `fast doubling` ，主要要實現物件中數值乘 2 ，目前位移範圍不考慮到 32 位元以上。若需要位移的長度大於剩於可用的位元時，用 `bn_resize` 擴充 4 個 `int` 給存放位移後結果的 `dest` ，若需要位移的長度小於剩於可用的位元時，照原先長度 `bn_resize` 即可。
* 位移後的 `number[i]` 為原本的 `number[i] << shift` 與 `number[i-1] >> (32 - shift)` 做 `or` 運算後得到的結果，而 `number[0]` 因為不存在 `number[-1]` 而只做 `number[0] << shift` 。

void bn_lshift(const bn *src, size_t shift, bn *dest)
{
    size_t z = bn_clz(src);
    shift %= 32;  // only handle shift within 32 bits atm
    if (!shift)
        return;

    if (shift > z) {
        bn_resize(dest, src->size + 1);
    } else {
        bn_resize(dest, src->size);
    }
    /* bit shift */
    for (int i = src->size - 1; i > 0; i--)
        dest->number[i] =
            src->number[i] << shift | src->number[i - 1] >> (32 - shift);
    dest->number[0] = src->number[0] << shift;
}

### 利用 bn 結構體運算 fibonacci number
* 施工

### 改用 fast doubling 運算 fibonacci number
* 施工