# 2023q1 Homework3 (quiz3)
contributed by < `csm1735` >

## 測驗 `1`

---
## 測驗 `2`

---
## 測驗 `3`

### LFSR 的運作原理及案例
Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器

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 */
}

計算出 `new_bit` 後將 `up` 右移 1 位，再將 `new_bit`補到最高位。

$ git log --grep lfsr

透過該指令可以去搜尋包含關鍵字 `lfsr` 的 commit message
可以發現在此次 [commit](https://github.com/torvalds/linux/commit/dec0fb3946c478e7bb6165a1b7a03092ceefd419) 提及到了 `lfsr` ，而其所提到的 `jent_lfsr_time` 函式可以在 [linux/crypto/jitterentropy.c](https://github.com/torvalds/linux/blob/master/crypto/jitterentropy.c) 中發現

### 解釋程式碼原理
`log2_64` 功能為計算以 2 為底的 `x` 的對數，且下取至整數 (即 `floor` )，從程式碼可看到不斷的透過右移與 `if` 來判斷 `x` 的對數值會落在哪個區間，再以該區間的最小對數值為基底，去加上該部份透過 `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 _
};

這邊解釋一下 `log_table_256` 的作法，一開始看到時並沒有看懂，仔細看看後發現有跡可循，才理解是透過 macro 將 `_(n)` 定義成以逗號隔開的 16 個 n 值，因為像是對數值為 4 的為 16 ~ 31 共 16 個值，對數值為 5 的為 32 ~ 63 共 32 個值，而透過這種作法，我們只需要寫 `_(4), _(5), _(5)` 即可，能夠達到程式碼更精簡的效果。

unsigned int bucket_number(uint64_t x)
{
    uint64_t mask111 = (1 << (N_BITS + 1)) - 1;
    uint64_t mask011 = (1 << (N_BITS)) - 1; /* one 1 less */

    unsigned char leq = ((x & mask111) < N_BUCKETS);
    /* leq (less or equal) is 0 or 1. */

    return (leq * (x & mask111)) +
           ((1 - leq) * ((x >> (N_BITS + 1)) & mask011));
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

而此處透過 mask 的作法，可以保證結果可以小於 `N_BUCKETS` ，如果與 `mask111` 做 & 後的結果不小於 `N_BUCKETS` ，則改使用 `mask011` 。

---
## 測驗 `4`
### 解釋程式碼原理
`ceil_log2` 功能為計算以 2 為底的 `x` 的對數，且上取至整數 (即 `ceil` )

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 的冪次，如果有的話則透過左移去對特定的 bit 做 set ，並將 `x` 做右移去繼續檢查，而我們可以看出最後沒有繼續去對 `x > 1` 的狀況去檢查，因此推斷剩餘的程式碼為:

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

考量到 `KKKK` 的格式，可以將此段改寫為 `r | shift | x >> 1`