---
tags: linux2023
---
# 2023q1 Homework3 (quiz3)
contributed by < `visitorckw` >
>[2023q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗 `1`
## 測驗 `2`
## 測驗 `3`
Reference: https://zh.wikipedia.org/wiki/%E7%BA%BF%E6%80%A7%E5%8F%8D%E9%A6%88%E7%A7%BB%E4%BD%8D%E5%AF%84%E5%AD%98%E5%99%A8
LSFR 是一種轉換操作，通常用來生成看起來是隨機的且循環周期非常長的序列。
程式碼中的 log2_64 函數用來計算 $log_2$ 的值。運用二分搜的概念，逐步尋找最高位所在的位置。而陣列 log_table_256 用來存放該 index 取 $log_2$ 的值，透過巨集 _ 來展開。
```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 _
};
#undef _
/* ASSUME x >= 1
* returns smallest integer b such that 2^b = 1 << b is >= x
*/
uint64_t log2_64(uint64_t v)
{
unsigned r;
uint64_t t, tt, ttt;
ttt = v >> 32;
if (ttt) {
tt = ttt >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 56 + log_table_256[t]; // AAAA
} else {
r = 48 + log_table_256[tt]; // BBBB
}
} else {
t = ttt >> 8;
if (t) {
r = 40 + log_table_256[t]; // CCCC
} else {
r = 32 + log_table_256[ttt]; // DDDD
}
}
} else {
tt = v >> 16;
if (tt) {
t = tt >> 8;
if (t) {
r = 24 + log_table_256[t]; // EEEE
} else {
r = 16 + log_table_256[tt]; // FFFF
}
} else {
t = v >> 8;
if (t) {
r = 8 + log_table_256[t]; // GGGG
} else {
r = 0 + log_table_256[v]; // HHHH
}
}
}
return r;
}
```
此函數可以利用 __builtin_clz64 來加速，並且程式碼撰寫上更為簡潔
```c
uint64_t log2_64(uint64_t v)
{
return 63 - __builtin_clz64(v);
}
```
lsfr 函數用來透過當前狀態轉移得到下一個狀態，new_bit 用來暫存將要放入最左邊的位元，並將其他位元向右位移 1 位。
```c
/* Implementation of LFSR (linear feedback shift register)
* on uint64_t using irreducible polynomial x^64 + x^61 + x^34 + x^9 + 1
* (On 32 bit we could use x^32 + x^22 + x^2 + x^1 + 1)
*/
static void lfsr(uint64_t *up)
{
uint64_t new_bit =
((*up) ^ ((*up) >> 3) ^ ((*up) >> 30) ^ ((*up) >> 55)) & 1u;
/* don't have to map '+1' in polynomial */
*up = ((*up) >> 1) | (new_bit << 63);
/* shift *up by 1 to RIGHT and insert new_bit at "empty" position */
}
```
bucket_number 函數則是會將傳入的參數 x 找到一個對應的 bucket。
mask111 為有效位全為 1 的 bitmask，而 mask011 則為 mask111 的最高位改設為 0 的 bitmask 。
程式會判斷 x & mask111 是否小於 bucket 的數量。
* 若 x & mask111 小於 bucket 的數量
* 直接返回 x & mask111 作為結果
* 若 x & mask111 不小於 bucket 的數量
* 取 x 的較高位數再跟 mask011 進行 and 運算
綜合以上兩種情況可以得到以下程式碼
```c
return (leq * (x & mask111)) + // IIII
((1 - leq) * ((x >> (N_BITS + 1)) & mask011)); // JJJJ
```
## 測驗 `4`
* 運作原理
一開始先將 x 減去 1 ，這樣就可以將問題轉成尋找 x 之中最高位的 1 。
程式中的 r 用來記錄總向右位移的位元數目。
利用二分搜尋的方式，尋找最高位的 1 所在的位置。
第一次先判斷 x 是否大於 0xff 來得知最高位在第 0~15 bit 之間還是在 16~31 bit 之間。若最高位在 16~31 bit 之間，則將 x 向右位移 16 位，下一次就只考慮最高位是在 0~15 bit 之間的何處，並且同時用 r 紀錄位移的數量。
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
接著以此類推，將 x 與 0xff 來做比較，藉此得知最高位在 0~7 bit 之間或是 8~15 bit 之間，並且用 r 紀錄位移的數量。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
接著重複此過程直到範圍內剩下二個 bit 為止。
```c
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
shift = (x > 0x3) << 1;
x >>= shift;
```
此時範圍內只剩下 0~1 bit 兩個位元。
首先將 r 跟 shift 的值相加 ( 運用 bitwiese or 運算速度較快 ) ，若最高位發生在第 1 個 bit 則要將答案再加一，因此再跟 ```x >> 1```做 or 運算。最後由於是向上取整，因此整個答案要再加上 1 。
```c
return (r | shift | x >> 1) + 1;
```
* 支援x = 0
再最一開始用一個變數紀錄 x 是否為 0，若 x 為 0 則將答案乘以 0 ，若不為 0 則乘以 1 。
```c
int ceil_log2(uint32_t x)
{
uint32_t r, shift;
uint32_t y = x != 0;
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) * y;
}
```
Sign in with Wallet
Connect another wallet