---
title: 2023q1 Homework3 (quiz3)
tags: Linux核心實作
---

# 2023q1 Homework3 ([quiz3](https://hackmd.io/@sysprog/linux2023-quiz3))
contributed by < [`lorian0738`](https://github.com/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](https://en.wikipedia.org/wiki/Linear-feedback_shift_register) (LFSR) 的運作原理，搭配在 [Linux 核心原始程式碼](https://github.com/torvalds/linux)中，用 git log 和 grep 找出 LFSR 的應用案例

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

### 2. 解釋[上述程式碼](https://gist.github.com/jserv/15c6ef4383d5d010326cdc4382ffdd1d)運作的原理

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 核心原始程式碼中找到 $log_{2}({x})$ 的實作 (整數)，要涵蓋不同的整數型態寬度，以及是否能運用微處理器提供的指令來加速。也從 Linux 核心找出整數 $log_{2}({x})$ 的應用案例並解說。

### 4. lab0-c 提供類似的實作 [log2_lshift16.h](https://github.com/sysprog21/lab0-c/blob/master/log2_lshift16.h)，解釋其原理並嘗試改進其效能

## 測驗 4