# 2023q1 Homework3 (quiz3) contributed by < [zeddyuu](https://github.com/zeddyuu) > # 測驗 `1` --- # 測驗 `2` --- # 測驗 `3` ## LFSR 的原理以及 Linux kernel 中的應用案例 LFSR 指的是給定前一狀態的輸出，再將此輸出通過一個線性函數當作下次輸入的移位暫存器，且由於暫存器的狀態是有限的，最終會是一個重複的循環。 在 bash 中下以下指令可以用 commit 訊息關鍵字去搜尋 commit histroy ```shell 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` 的宣告方式 ```c 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 _ }; ``` 其實可以寫成 ```c #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` ```c 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$ ```c r |= shift shift = (x > 0x1) << 0; r |= shift; ``` 可以再簡化為 ```c r | shift | (x >> 1) ``` :::success TODO 改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless 在 Linux 核心原始程式碼找出 ceil 和 log2 的組合 (類似的形式)，並解說應用案例，例如在 Linux 核心排程器就有 :::