# 2023q1 Homework3 (quiz3)

contributed by < `ItisCaleb` >

## 測驗 `1`

透過 ABI 的特性，我們可以將父節點的地址儲存在該節點的 `color` 欄位中，同時使用 `color` 欄位的 LSB 來表示該節點的顏色。
接著，我們可以使用位元運算對 `color` 進行操作，以得到父節點的地址或是節點的顏色。

typedef struct __node {
    uintptr_t color;
    struct __node *left, *right;
    ...
} node_t __attribute__((aligned(sizeof(long))));

#define rb_parent(r) ((node_t *) ((r)->color & ~1))
#define rb_color(r) ((color_t) (r)->color & 1)

#define rb_set_parent(r, p)                         \
    do {                                            \
        (r)->color = rb_color(r) | (uintptr_t) (p); \
    } while (0)
#define rb_set_red(r) \
    do {              \
        (r)->color &= ~1;         \
    } while (0)
#define rb_set_black(r) \
    do {                \
        (r)->color |= 1;           \
    } while (0)

在 `cmap_insert` 中，需要先從根節點開始走訪節點，直到找到樹的底端或是 NULL，才能進行插入操作。
在走訪的過程中，`res` 是比較新元素和當前節點的值的結果，以確定是要往左邊走還是右邊走。如果最終找到了 NULL ，那麼就可以把新元素插入到這個位置上。

if (res < 0) {
    if (!cur->left) {
        cur->left = node;
        rb_set_parent(node, cur);
        cmap_fix_colors(obj, node);
        break;
    }
    cur = cur->left;
} else {
    if (!cur->right) {
        cur->right = node;
        rb_set_parent(node, cur);
        cmap_fix_colors(obj, node);
        break;
    }
    cur = cur->right;
}

在 `tree_sort` 中，我們把 `list` 中的節點一個一個放進 `map` 裡，然後再透過`cmap_next` 一個一個拿出來，這樣就會是排序好的狀態
最後我們使用把 `list` 的結尾變成 NULL 並且指向第一個節點

void tree_sort(node_t **list)
{
    node_t **record = list;
    cmap_t map = cmap_new(sizeof(long), sizeof(NULL), cmap_cmp_int);
    while (*list) {
        cmap_insert(map, *list, NULL);
        list = &(*list)->next;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = &(*list)->next;
    }
    *list = NULL;
    *record = first;
    free(map);
}

而在觀察程式碼的時候，也看到了一些可以改進的地方

`cmap_rotate_left/right` 的大部份程式碼幾乎一樣，所以把同樣的部份抽離出來到 `cmap_do_rotate`，原本的函式只留下調整要 rotate 的 node

static node_t *cmap_rotate_left(cmap_t obj, node_t *node)
{
    node_t *r = node->right, *rl = r->left;

    /* Adjust */
    r->left = node;
    node->right = rl;
    return do_cmap_rotate(obj,r,rl);
}

static inline node_t *do_cmap_rotate(cmap_t obj, node_t *dir, node_t *ddir)
{
    node_t *node = rb_parent(dir);
    node_t *up = rb_parent(node);

    rb_set_parent(dir, up);
    rb_set_parent(node, dir);

    if (ddir)
        rb_set_parent(ddir, node);
    if (up) {
        if (up->right == node)
            up->right = dir;
        else
            up->left = dir;
    }
    if (node == obj->head)
        obj->head = dir;
    return dir;
}

同樣注意到 `cmap_l_l` 跟 `cmap_r_r` 交換顏色的程式碼相同，於是也抽離出來到 `cmap_swap_color`

static void cmap_r_r(cmap_t obj,
                     node_t *node UNUSED,
                     node_t *parent UNUSED,
                     node_t *grandparent,
                     node_t *uncle UNUSED)
{
    /* Rotate to the left according to grandparent */
    grandparent = cmap_rotate_left(obj, grandparent);

    /* Swap grandparent and uncle's colors */
    cmap_swap_color(grandparent,grandparent->left);
}

static inline void cmap_swap_color(node_t *a, node_t *b){
    color_t c1 = rb_color(a), c2 = rb_color(b);

    if (c1 == CMAP_RED)
        rb_set_red(b);
    else
        rb_set_black(b);

    if (c2 == CMAP_RED)
        rb_set_red(a);
    else
        rb_set_black(a);
};

## 測驗 `2`

priority queue 分別有 insert 跟 pop 的操作，並且各自有 balanced 跟 unbalanced 的版本

`avl_prio_queue_insert_unbalanced/balanced`
我們首先將 `cur_nodep` 指向 root
並且 `isminimal` 為確認要插入的 node 是否為最小的 flag

static inline void avl_prio_queue_insert_unbalanced(
    struct avl_prio_queue *queue,
    struct avlitem *new_entry)
{
    struct avl_node *parent = NULL;
    struct avl_node **cur_nodep = &queue->root.node;
    struct avlitem *cur_entry;
    int isminimal = 1;
    ...

接著便用迭代的方式走訪樹，比現在的 node 小就往左走，否則就往右走
如果往右走就表示要插入的 node 不為最小的 node

while (*cur_nodep) {
    cur_entry = avl_entry(*cur_nodep, struct avlitem, avl);

    parent = *cur_nodep;
    if (cmpint(&new_entry->i, &cur_entry->i) <= 0) {
        cur_nodep = &((*cur_nodep)->left);
    } else {
        cur_nodep = &((*cur_nodep)->right);
        isminimal = 0;
    }
}

如果是最小的 node，便更新 `queue->min_node`

if (isminimal)
    queue->min_node = &new_entry->avl;

最後我們便將要插入的 node 放到樹上
如果操作是 unbalanced，使用 `avl_link_node`，直接把 node 接上

avl_link_node(&new_entry->avl, parent, cur_nodep);

而 balanced 則使用 `avl_insert`，在接上 node 之後，函式會去計算並旋轉樹來確保平衡

avl_insert(&new_entry->avl, parent, cur_nodep, &queue->root);

`avl_prio_queue_pop_unbalanced/balanced`
pop 會回傳最小的 node
並且把 `queue->min_node` 更新成下一個 node

static inline struct avlitem *avl_prio_queue_pop_balanced(
    struct avl_prio_queue *queue)
{
    struct avlitem *item;

    if (!queue->min_node)
        return NULL;

    item = avl_entry(queue->min_node, struct avlitem, avl);
    queue->min_node = avl_next(queue->min_node);
    ...

最後一樣
unbalanced 會使用 `avl_erase_node`

avl_erase_node(&item->avl, &queue->root, &removed_right);

balanced 會使用 `avl_erase` 來確保樹是平衡的

avl_erase(&item->avl, &queue->root);

## 測驗 `3`

LFSR利用一組 binary pattern 作為初始狀態，然後將這組 binary pattern 通過一系列的位元移位、XOR運算等操作，產生出一系列的新數列，這些新數列看起來就像是隨機產生的序列。而LFSR通過改變移位寄存器的位元個數、XOR運算的默認值可以控制生成的數列長度和隨機性質。
LFSR就是一種通過移位、XOR等操作，生成隨機序列的技術。

題目給的 LFSR 實作是一種 Fibonacci LFSR
在這個例子裡 bit 是從左數到右並且從 1 開始
我們把 LSB (64th bit) 及選定的幾個 bit 稱為 tap
總共有幾個步驟

- 給定一個 binary pattern
- 將 tap 照順序去 xor，在這例子中是 64、61、34、9 個
- 把這組 binary pattern 向右位移，並且將上一步輸出的 bit 放到最左邊

要注意的是選定的 tap 要符合兩項條件

- 數量為偶數
- 所有數字的最大公因數為 1 (整集互質 setwise coprime)

而要產生新的數組就是把輸出的 binary pattern 作為 LFSR 的輸入

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

在 Linux 的 `crypto/jitterentropy.c` 中的 `jent_lfsr_time` 可以看到 Fibonacci LFSR 的實作

tmp = tmp >> (DATA_SIZE_BITS - 1);
/*
* Fibonacci LSFR with polynomial of
*  x^64 + x^61 + x^56 + x^31 + x^28 + x^23 + 1 which is
*  primitive according to
*   http://poincare.matf.bg.ac.rs/~ezivkovm/publications/primpol1.pdf
* (the shift values are the polynomial values minus one
* due to counting bits from 0 to 63). As the current
* position is always the LSB, the polynomial only needs
* to shift data in from the left without wrap.
*/
tmp ^= ((new >> 63) & 1);
tmp ^= ((new >> 60) & 1);
tmp ^= ((new >> 55) & 1);
tmp ^= ((new >> 30) & 1);
tmp ^= ((new >> 27) & 1);
tmp ^= ((new >> 22) & 1);
new <<= 1;
new ^= tmp;

題目本身會分配數個 bucket ，並且透過 LSFR 來生成數組把這些 bucket 填滿
`N_BUCKETS` 是 bucket 的數
`N_BITS` 則是 `N_BUCKETS` 以 2 為底的 log

首先我們來看 `log2_64`
題目定義了一個 `log_table_256`，展開來就會是 0 ~ 255 以 2 為底的 log

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

而 `log2_64` 可以簡化成下列這樣
方法是先將整數向右位移 32 位，如果移動後的值不為零，就代表最高的 32 個 bit 中至少有一個 bit 是 1，此時可以將整數再向右位移 16 位，以此類推，每次將位移的距離除以 2。當位移的距離為 8 時，就可以找到最左邊有東西的 8 個 bit 及它們的位置。
接著，透過對照 `log_table_256`，就能找出這 8 個 bit 對應的 log 值
最後便將位置加上透過 `log_table_256` 找到的值

uint64_t log2_64(uint64_t v){
    int n = 32,r = 0;
    for(;n>=8;n=n>>1){
        if(v>>n){
           v = v>>n;
           r += n;
        }
    }
    return r + log_table_256[v];
}

`bucket_number` 是用來把 LSFR 生成的數字限制在 `N_BUCKETS` 裡
`mask111` 是從 0~n 都為 1 的 bit pattern
`mask011` 則是從 0~n-1 都為 1 的 bit pattern
用 `mask111` 跟 `x` 去做 and 便可以得到`x` 0~n 的 bit pattern
如果這個數小於 `N_BUCKETS` 則回傳
而如果等於的話則將 `x` 向右位移 n+1 來獲取新的數組並且跟 `mask011` and 後回傳

/* n == number of totally available buckets, so buckets = \{0, ...,, n-1\}
 * ASSUME n < (1 << 32)
 */
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.
     */
}

而最後的 `fill_buckets` 便是透過 LSFR 生成數組並且使用`bucket_number` 後將輸出放進 bucket裡面

## 測驗 `4`

這個函式的方法跟測驗 3 的很像，同樣是不斷去找最左邊有東西的 bits
不同的點在於 `r` 是用 bit operation 去得到 MSB 的位置

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

而當輸入為 0 的時候會輸出 32
要改進並且讓函式一樣是 branchless 可以套用上一題 `bucket_number` 最後一行使用的方法

int ceil_log2(uint32_t x)
{
    uint32_t r, shift, is_zero = !x;
    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 iszero * -1 + !is_zero * ((r | shift | x >> 1) + 1);       
}