# 2022q1 Homework3 (fibdrv)
contributed by <`curlyw819` >
###### tags: `linux2022`

## **大數運算**

:::danger
中英文間用一個半行空白字元或標點符號區隔。
:notes: jserv
:::

由於 Fib(92) 開始的計算會有 overflow 的問題，因此需要使用到大數運算的方法。原則上是直接使用字元運算並以陣列的形式來儲存，藉此來解決 overflow 的問題。

### **資料結構**
使用結構來儲存字元與操作所需的資訊，定義資料結構如下

typedef struct {
    char decimal[500];
    int length;
} bignum;

* `decimal[size - 1]` = `msb`，`number[0]` = `lsb`
* `length`用來儲存數字位數
#### **大數加法**
* 運算的過程使用ASCII來使數字以字元的方式直接做相加，所以兩數相加後要再減去多加的48
* 從個位數開始相加並且考慮進位，也就是說MSB為個位數

if (x->length < y->length)
        return bn_add(y, x, dest);

* 以上程式碼為了計算方便，使`x->length` >= `y->length`

void bn_add(bignum *x, bignum *y, bignum *dest)
{
    if (x->length < y->length)
        return bn_add(y, x, dest);
    int carry = 0;
    for (int i = 0; i < y->length; i++) {
        dest->decimal[i] = y->decimal[i] + x->decimal[i] + carry - OFFSET;
        if (dest->decimal[i] >= 10 + OFFSET) { // OFFSET = 48
            carry = 1;
            dest->decimal[i] -= 10;
        } else
            carry = 0;
    }
    for (int i = y->length; i < x->length; i++) {
        dest->decimal[i] = x->decimal[i] + carry;
        if (dest->decimal[i] >= 10 + OFFSET) {
            carry = 1;
            dest->decimal[i] -= 10;
        } else
            carry = 0;
    }
    dest->length = x->length;
    dest->decimal[dest->length] = carry + OFFSET;
    if (carry)
        dest->length++;
    dest->decimal[dest->length] = '\0';
}

第一個 `for` 是做字元的相加並考慮進位，結果放入 `dest`，第二個for是將較長的數字 `x` 剩餘的部分直接放入 `dest`
#### **新增數字**

#define bn_tmp(x) bn_new(&(bignum) { .length = 0 }, x)

bignum *bn_new(bignum *bn, char decimal[])
{
    bn->length = strlen(decimal);
    memcpy(bn->decimal, decimal, bn->length);
    return bn;
}

#### **fib_without_fast_doubling**
這邊的`fib`是沒有使用`fast_doubling`加速過的，且使用不會用到陣列的計算方式

bignum *fib_sequence_org(int k)
{
    int i;
    bignum *f0 = bn_tmp("0");
    bignum *f1 = bn_tmp("1");
    bignum *ans = bn_tmp("0");
    if(k == 0)
        return f0;
    if(k == 1)
        return f1;

    for(i = 2; i <= k; i++){
        bn_add(f0, f1, ans);
        f0 = f1;
        f1 = ans;
    }
    return ans;
}

## **效能量測**
第一階段我主要想測量在沒有`fast_doubling`的原始fib
量測結果尚未排除作業系統排程的干擾
### **量測user space 和 kernel space 間傳輸使用copy_to_user的傳遞時間**
* 使`fibdrv`中的`fib_read`回傳`fib_sequence_org`在`kernel space`運算費式數列的時間
* 量測`client`中`user space`呼叫`read`前後之時間差
* 將`kernel space`與`user space`量到的時間做相減，可得到`copy_to_user`的傳遞時間
#### **kernel space read**
* 在`kernel space`使用`ktime`

static ssize_t fib_read(struct file *file,
                        char *buf,
                        size_t size,
                        loff_t *offset)
{
    ktime_t k1, k2;
    k1 = ktime_get();
    char *rev_fib = fib_sequence_org(*offset)->decimal;
    int length = strlen(rev_fib);
    char result[MAX_DIGIT];
    for (int i = 0; i < length; i++)
        result[i] = rev_fib[length - 1 - i];
    result[length] = '\0';
    copy_to_user(buf, result, length + 1);
    k2 = ktime_sub(ktime_get(), k1);
    return (long long)ktime_to_ns(k2);
}

#### **user space read**
* 在`user space`使用`clock_gettime`

long elapse(struct timespec start, struct timespec end)
{
    return ((long) 1.0e+9 * end.tv_sec + end.tv_nsec) -
           ((long) 1.0e+9 * start.tv_sec + start.tv_nsec);
}

由於量測結果很小，所以先將其放大並增加精確度再相減

    for (int i = 0; i <= offset; i++) {
        lseek(fd, i, SEEK_SET);
        clock_gettime(CLOCK_REALTIME, &t1);
        sz = read(fd, buf, 500);
        clock_gettime(CLOCK_REALTIME, &t2);
        printf("%d ",i);

        printf("%lld ",elapse(t1,t2) - sz);
        
        printf("%ld ", elapse(t1, t2));

        printf("%lld \n",sz);


    }

#### gnuplot
將量測出的時間用gnuplot建成圖表
* 隨著`size`增加，傳輸的資料量也會增加，但是耗費的時間卻幾乎相同