2023q1 Homework3 (quiz3)

contributed by < lorian0738 >

測驗 1

測驗 2

測驗 3

Linear feedback shift register (LFSR) 是指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，其應用包括產生 PRNG。考慮一個運用 LFSR 來產生隨機數，並使其均勻分佈於 64 位元無號整數的有效空間 (distribution of uniformly arbitrarily large uint64_t)。
程式碼可參見 bucket_uniform.c (部分程式碼遮蔽):

• log2_64 : 計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)
• bucket_number : 在指定區間內，使產生的 LFSR 數值得以均勻分佈

1. 解釋 Linear feedback shift register (LFSR) 的運作原理，搭配在 Linux 核心原始程式碼中，用 git log 和 grep 找出 LFSR 的應用案例

LFSR 通常右移一串序列將最低位 (最左邊的位元) 做為輸出，且將輸出作為其中一個輸入，與挑選的其他 bits 做 XOR 等動作，得到的值作為那串 bits 的最高位元 (feed back)，重複以上動作，選得恰當的話可以做偽隨機數生成器

2. 解釋上述程式碼運作的原理

int main()
{
    int num_of_buckets = 120;          /* an example of some non-power of 2 */
    int num_of_iterations = (1 << 20); /* roughly 1 million */

    set_N_BUCKETS(num_of_buckets);
    set_N_BITS();

    unsigned int *buckets = malloc(N_BUCKETS * sizeof(unsigned int));

    int i = 0;
    while (i < N_BUCKETS) {
        *(buckets + i) = 0;
        i++;
    }
    fill_buckets(buckets, num_of_iterations);
    evaluate_buckets(buckets);
    free(buckets);
    return 0;
}

set_N_BUCKETS 將 N_BUCKETS 設為 num_of_buckets
set_N_BITS 將 N_BITS 設為 N_BUCKETS 取以 2 為底的對數並下取整函數，其中用 log2_64 這個函式來實作

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];
            } else {
                r = 48 + log_table_256[tt];
            }
        } else {
            t = ttt >> 8;
            if (t) {
                r = 40 + log_table_256[t];
            } else {
                r = 32 + log_table_256[ttt];
            }
        }
    } else {
        tt = v >> 16;
        if (tt) {
            t = tt >> 8;
            if (t) {
                r = 24 + log_table_256[t];
            } else {
                r = 16 + log_table_256[tt];
            }
        } else {
            t = v >> 8;
            if (t) {
                r = 8 + log_table_256[t];
            } else {
                r = 0 + log_table_256[v];
            }
        }
    }
    return r;
}

這個部份目的是對 N_BUCKETS 取以 2 為底的對數並下取整函數，首先將輸入值右移 32 位元，若是右移後非 0，表示這個數字大於等於

$2^{32}$，再繼續右移 16 位元，若還是非 0 則表示這個數字大於等於

$2^{48}$，再右移 8 個位元，若還是非 0 則表示這個數字大於等於

$2^{56}$，這時可回傳 56 加上剩下的值用 log_table_256 找到的值。

其他以此類推，總之就是先找到 8 個 bits 一起看時，該值最大大於等於 2 的第幾個 8 次方，例如大於

$2^{56}$、

$2^{48}$、

$2^{40}$、

$2^{32}$、

$2^{24}$…，而　

$2^8$ 就是 256，因此再從預定義好的 log_table_256 找出剩餘要加上的值

3. 在 Linux 核心原始程式碼中找到

$lo{g}_2(x)$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數

$lo{g}_2(x)$ 的應用案例並解說。

4. lab0-c 提供類似的實作 log2_lshift16.h，解釋其原理並嘗試改進其效能

測驗 4