2023q1 Homework3 (quiz3)

contributed by < visitorckw >

2023q1 第 3 週測驗題

測驗 `1`

測驗 `2`

測驗 `3`

Reference: https://zh.wikipedia.org/wiki/线性反馈移位寄存器
LSFR 是一種轉換操作，通常用來生成看起來是隨機的且循環周期非常長的序列。
程式碼中的 log2_64 函數用來計算

l o g_{2}

的值。運用二分搜的概念，逐步尋找最高位所在的位置。而陣列 log_table_256 用來存放該 index 取

l o g_{2}

的值，透過巨集 _ 來展開。

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 來加速，並且程式碼撰寫上更為簡潔

uint64_t log2_64(uint64_t v)
{
    return 63 - __builtin_clz64(v);
}

lsfr 函數用來透過當前狀態轉移得到下一個狀態，new_bit 用來暫存將要放入最左邊的位元，並將其他位元向右位移 1 位。

/* 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 運算
  綜合以上兩種情況可以得到以下程式碼

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 紀錄位移的數量。

r = (x > 0xFFFF) << 4;
x >>= r;

接著以此類推，將 x 與 0xff 來做比較，藉此得知最高位在 0~7 bit 之間或是 8~15 bit 之間，並且用 r 紀錄位移的數量。

shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;

接著重複此過程直到範圍內剩下二個 bit 為止。

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 。

return (r | shift | x >> 1) + 1;

支援x = 0
再最一開始用一個變數紀錄 x 是否為 0，若 x 為 0 則將答案乘以 0 ，若不為 0 則乘以 1 。

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;       
}

2023q1 Homework3 (quiz3)

測驗 1

測驗 2

測驗 3

測驗 4

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`