# 2023q1 Homework3 (quiz3)
contributed by < [zeddyuu](https://github.com/zeddyuu) >
# 測驗 `1`

---
# 測驗 `2`
---
# 測驗 `3`

## LFSR 的原理以及 Linux kernel 中的應用案例

LFSR 指的是給定前一狀態的輸出，再將此輸出通過一個線性函數當作下次輸入的移位暫存器，且由於暫存器的狀態是有限的，最終會是一個重複的循環。

在 bash 中下以下指令可以用 commit 訊息關鍵字去搜尋 commit histroy

git log --grep='LFSR'

可以找到 [dec0fb3](https://github.com/torvalds/linux/commit/dec0fb3946c478e7bb6165a1b7a03092ceefd419) 在此 commit message 中包含關鍵字 `LFSR`

在 Linux kernel 中 LFSR 相關的應用的案例可以在 [linux/crypto/jitterentropy.c](https://github.com/torvalds/linux/blob/master/crypto/jitterentropy.c) 中的 `jent_lfsr_time` 函式中發現 Fibonacci LSFR 的應用。

## 解釋上述程式碼運作原理

`log2_64()` 函式的運作原理是利用位移 64 位元的數值，並且在位移後用分支來確認數值在於哪兩個 2 的冪之間，再利用 `log_table_256` 將剩餘的高位 8 個位元(數值在0~255以內)找出對應在 2 的哪個冪加上去即完成函式找出 `log2` 的功能。

舉例來說像是 $260_{2} = 100000100$ 進行計算，經過一系列分支最後只會跑右移 8 位元，高位仍然有值，故此值會在 $2^{8}$ ~ $2^{16}$ 之間，之後利用 `log_table_256` 去找出剩餘高位位元數值對應到哪個哪一個 2 的冪，也就是查表中 1 對應的 2 的冪為 0，因為確定此值在 $2^{8}$ ~ $2^{16}$ 故將 8 + 0 = 8，計算完成。

比較特別的是 `log_table_256` 的宣告方式

static const char log_table_256[256] = {
#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
    -1,   0,    1,    1,    2,    2,    2,    2,    3,    3,    3,
    3,    3,    3,    3,    3,    _(4), _(5), _(5), _(6), _(6), _(6),
    _(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7),
#undef _
};

其實可以寫成

#define _(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
static const char log_table_256[256] = {
    -1,   0,    1,    1,    2,    2,    2,    2,    3,    3,    3,
    3,    3,    3,    3,    3,    _(4), _(5), _(5), _(6), _(6), _(6),
    _(6), _(7), _(7), _(7), _(7), _(7), _(7), _(7), _(7),
#undef _
};

這樣就可以看出是透過巨集展開來達到產生 log table，以前總覺得巨集只能出現在 code 最前方定義，但在這邊學到巨集可以出現在程式碼中任何地方，並且對應到 [你所不知道的 C 語言](https://hackmd.io/@sysprog/c-prog/%2Fs%2FS1maxCXMl#_Generic-C11) 中提到的巨集實際的作用為產生程式碼，後先經過 preprocessor 後再交由 compiler 編譯程式。

---
# 測驗 `4`

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;                 
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    return r | shift | (x >> 1) + 1;       
}

## 解釋上述程式碼運作原理

此題的原理是每次檢查 x 有沒有超過 2 的冪個位元數，檢查過後再根據結果用 OR 操作做 bit set 去將 shift 的第 $log_2$ 位元做 set，代表此值一定大於此時 2 的冪，例如 $6_{2} = 0110$，檢查是否大於 $1111$，沒有代表此時的值不超過 $2^{4}$，再檢查是否大於 $0011$，有就把 shift 做 OR 操作 set bit 成 $0010$，代表此時的值必定大於等於 $2^{2}$，且可用於右移 x 繼續檢查是否大於 $0001$，沒有所以結束，因為要取 ceil 所以將結果 + 1 完成計算，另外一開始會減 1 是為了處理 x 剛好是 2 的冪 的情況。

故程式碼還缺少一次檢查是否大於 $2^{0} = 1$

r |= shift
shift = (x > 0x1) << 0;
r |= shift;

可以再簡化為

r | shift | (x >> 1)

:::success
TODO
改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有
:::