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 提及到了 lfsr ，而其所提到的 jent_lfsr_time 函式可以在 linux/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