2023q1 Homework3 (quiz3)

contributed by < zeddyuu >

測驗 1

---

測驗 2

---

測驗 3

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

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

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

git log --grep='LFSR'

可以找到 dec0fb3 在此 commit message 中包含關鍵字 LFSR

在 Linux kernel 中 LFSR 相關的應用的案例可以在 linux/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 語言 中提到的巨集實際的作用為產生程式碼，後先經過 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 的第

$lo{g}_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)

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