---
title: 2020 第三週作業
tags: _核心設計
breaks: true
---
# 2020q1 Homework2 (fibdrv)
contributed by < `babysuse` >

# 大綱
[toc]

# 作業描述

[完整描述](https://hackmd.io/@sysprog/linux2020-fibdrv)

# 作業筆記
## 費氏數列計算 Fast Doubling
一切都要從矩陣模型說起。因為 $F_{n+1} = F_n + F_{n-1}$，所以可以將一切運算式以矩陣型態列出

$(1)\quad\begin{align}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix}
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\begin{bmatrix}
F_{n} & F_{n-1} \\
F_{n-1} & F_{n-2}
\end{bmatrix} \\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{n-1}
\begin{bmatrix}
F_{2} & F_{1} \\
F_{1} & F_{0}
\end{bmatrix} \\
\\
&當\ F_0 = 0，F_1 = 1\ 時 \\
\\
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^n
\end{align}$

同理

$(2)\quad\begin{align}
\begin{bmatrix}
F_{2n+1} & F_{2n} \\
F_{2n} & F_{2n-1}
\end{bmatrix}
&= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}^{2n} \\
&= \begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix}
\begin{bmatrix}
F_{n+1} & F_{n} \\
F_{n} & F_{n-1}
\end{bmatrix} \\
&= \begin{bmatrix}
F_{n+1}^2 + F_{n}^2 & F_{n}\cdot(F_{n+1} + F_{n-1}) \\
F_{n}\cdot(F_{n+1} + F_{n-1}) & F{n}^2 + F_{n-1}^2
\end{bmatrix}
\end{align}$

因此

$(3)\quad\begin{align}
F_{2n+1} &= F_{n+1}^2 + F_{n}^2 \\
F_{2n} &= F_{n}\cdot(F_{n+1} + F_{n-1}) \\
&= F_{n}\cdot(F_{n+1} + (F_{n+1} - F_{n})) \\
&= F_{n}\cdot(2\cdot F_{n+1} - F_{n})
\end{align}$

然後根據第一段推導我們可以知道，第 $n$ 個費氏數矩陣相當於是第 $1$ 個的 $n$ 次冪；而 *Fasting Doubling* 從 $1$ 開始的話，就相當於是用公式速算以二為底指數的費氏數（好比說 $F_2、F_4、F_8$ 等），就是二進位的概念。以下用公式速算 $F_{10}$ 為例 &emsp; ($10$ 的二進制表示為 $(1010)_2$)

| 二進位數 | 1 | 0 | 1 | 0
|:-:|:-:|:-:|:-:|:-:|:-:|
| Fast Doubling | $F(0*2 + 1)$ | $F(1*2)$ | $F(2*2 + 1)$ | $F(5*2)$
| 公式帶入 | $F(0)$ | $F(1)$ | $F(2)$ | $F(5)$
| 求得 | $F(0)、\textbf{F(1)}$ | $\textbf{F(2)}、F(3)$ | $F(4)、\textbf{F(5)}$ | $\textbf{F(10)}、F(11)$ |

二進位數顛倒過來就是短除法求得餘數的次序，所以算法很像是將短除法的過程倒過來。

以程式執行就是以 bitwise operator `>>` 和 `__builtin_clz()` (count leading zeros) 依序取得二進位數。

#include <stdio.h>

int fib_qmatrix(int);

int main(){
    for (int i = 0; i <= 10; ++i)
        printf("f(%d) = %d\n", i, fib_qmatrix(i));
}

int fib_qmatrix(int n) {
    int a = 0;
    int b = 1;
    int clz = __builtin_clz(n);
    for(int i = 0; clz + i < 32; ++i) {
        int f2n_1 = b*b + a*a;
        int f2n = a*(2*b - a); 
        if (n >> (32 - clz - i - 1) & 1) {
            a = f2n_1;
            b = f2n + f2n_1;
        } else {
            a = f2n;
            b = f2n_1;
        }   
    }   
    return a;
}

這裡計算位移量的 `32 - clz - 1`，在核心程式碼中有所謂的 `fls` (find last set) 可以取代。

## Kernel Module Programming
在介紹和測試的描述中提到了用 `ls -l` 列出裝置資訊時會有一對數字，分別意義是 major number 和 minor number，前者是核心負責用來對應驅動的，後者是驅動用來對應硬體的。在程式碼中，用來註冊 character device 的函式 `alloc_chrdev_region(&fib_dev, 0, 1, DEV_FIBONACCI_NAME);` 會自動分配 major number。