2023q1 Homework3 (quiz3)

測驗一

程式碼原理

在 include/linux/rbtree_types.h 中 tree node 宣告為

struct rb_node {
    unsigned long  __rb_parent_color;
    struct rb_node *rb_right;
    struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

而在 incomplete treesort.c 中 tree node 宣告為

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

在看完 Linux 核心的紅黑樹 得知，透過 __attribute__((aligned(sizeof(long)))) 讓編譯器知道 struct rb_node 會對齊 sizeof(long)，這樣就會讓指標最低 2 個位元是沒有使用到的，就可以把顏色的資料放進去其中一個位元中。舉例來說，一個節點指標如果指向 0xF724315C ，這個位址轉成二進位會變成 ...1100，最低 2 個位元會是 0，Linux 核心開發者利用這特性，將其中一個沒用到的位元拿來標注紅和黑這二種顏色。

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

可以看到會將 color 的最後一個 bit 當作顏色來使用，而 Linux kernel 會將親代節點跟顏色一起宣告，因為指標會對齊 sizeof(long) ，也就是 8 個 bytes ，所以指標的地址會是 8 的倍數，所以指標的最後 3 個 bits 不會使用到，故將指標最後 3 個 bits 設成 0 ，就能得到親代節點的地址，也就是將地址與 11....11000 作 and ，而 11....11000 只要將 00...00111 ，也就是 7 取反位元運算就能得到，所以 AAAA 為 (r)->color & ~7 。

typedef enum { CMAP_RED = 0, CMAP_BLACK } color_t;

可以看到將節點顏色紅色設成 0，黑色設成 1。

#define rb_set_red(r) \
    do {              \
        BBBB;         \
    } while (0)

要將節點設成紅色的，只須將最後一個 bit 設成 0 即可，也就是將地址與 11....11110 作 and，而 11....11110 只要將 00...00001 ，也就是 1 取反位元運算就能得到，所以 BBBB 為 (r)->color &= ~1。

#define rb_set_black(r) \
    do {                \
        CCCC;           \
    } while (0)

將節點設成紅色的，只須將最後一個 bit 設成 1 即可，所以只須 or 1 即可，故 CCCC 為 (r)->color |= 1 。

for (node_t *cur = obj->head;;) {
        int res = obj->comparator(&node->value, &cur->value);
        if (!res) /* If the key matches something else, don't insert */
            assert(0 && "not support repetitive value");

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

再來看到函式 cmap_insert ，主要是用來加入節點到紅黑樹中，變數 res 存放的是插入節點與目前走訪節點的比較值，0 表示相等，-1 表示插入節點小於目前走訪節點，1 表示插入節點大於目前走訪節點。
當 res = 0 時，則表示紅黑樹中已經有相同的數存在，所以不須插入。當 res = -1 時，會有兩種情形，第一種情形是目前走訪節點沒有左子節點，則將要插入節點設成目前走訪節點的左子節點，再調整顏色跟節點關係，第二種情形是目前走訪節點有左子節點，因為尚未得知後續節點的值大小，所以需要繼續往左子節點走訪，故 DDDD 為 cur = cur->left ，而 res = -1 時，也為同理，繼續往右子點走訪，故 EEEE 為 cur = cur->right 。

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 = FFFF;
    }
    node_t *node = cmap_first(map), *first = node;
    for (; node; node = cmap_next(node)) {
        *list = node;
        list = GGGG;
    }
    HHHH;
    *record = first;
    free(map);
}

再來是函式 tree_sort ，執行 tree_sort 須走訪每一個節點，所以一開始將節點一個個插入紅黑樹中，所以 FFFF 應為往下一個節點移動，list 為指向節點指標的指標，所以應先取出指標的地址 *list ，再找出下一個節點 (*list)->next ，再將這個指標的位址給 list ，所以 FFFF 為 &(*list)->next 。

static node_t *cmap_first(cmap_t obj)
{
    node_t *n = obj->head;
    if (!n)
        return NULL;

    while (n->left)
        n = n->left;
    return n;
}

函式 cmap_first 為找出最小的節點，而 cmap_next 會找出比目前節點還大，但是比其他所有節點還小的點，再將他們串接起來，所以 GGGG 跟 FFFF 一樣為 &(*list)->next，最後當所有節點走訪完，將最後一個節點指向 NULL，所以 HHHH 為 *list = NULL 。

答案

• AAAA = r->color & ~7
• BBBB = r->color &= ~1
• CCCC = r->color |= 1
• DDDD = cur = cur->left
• EEEE = cur = cur->right
• FFFF = &(*list)->next
• GGGG = &(*list)->next
• HHHH = *list = NULL

---

測驗二

程式碼原理

struct avl_node {
    unsigned long parent_balance;
    struct avl_node *left, *right;
} AVL_NODE_ALIGNED;

#define AVL_NODE_ALIGNED __attribute__((aligned(sizeof(unsigned long))))

架構與測驗一紅黑樹類似，指標也是對齊 sizeof(long) 。

static inline struct avl_node *avl_parent(struct avl_node *node)
{
    return (struct avl_node *) (IIII);
}

故要取得親代節點的位址，只須將最後 3 個 bits 設成 0 即可，所以 IIII 為 node->parent_balance & ~7 。

enum avl_node_balance { AVL_NEUTRAL = 0, AVL_LEFT, AVL_RIGHT, };

再來看到 balance 的定義，當左右子樹高度相等時為 0 ，當左子樹較右子樹高 1 時為 1 ，當右子樹較左子樹高 1 時為 2 ，所以總共需要 2 個 bits 來表示。

static inline enum avl_node_balance avl_balance(const struct avl_node *node)
{
    return (enum avl_node_balance)(JJJJ);
}

所以只須取得最右邊 2 個 bits 即可，故 JJJJ 為 node->parent_balance &= 3 。

static void avl_set_parent(struct avl_node *node, struct avl_node *parent)
{
    node->parent_balance =
        (unsigned long) parent | (KKKK);
}

再來要設定新的親代節點時，需要保留 balance 的資訊，也就是最右邊 3 個 bits，剩下的 bit 為舊的親代節點位址，故只須與舊位址的最右邊 3 個 bits or 即可，故 KKKK 為 node->parent_balance & 3 。

static void avl_set_balance(struct avl_node *node, enum avl_node_balance balance)
{
    node->parent_balance = (LLLL) | balance;
}

而要設定新的 balance 資訊時，只須留下除了最右邊 3 個 bits 以外的 bits 即可，故 LLLL 為 node->parent_balance & ~7 。

else {
    switch (avl_balance(parent)) {
    default:
    case AVL_RIGHT:
        /* new left child + right leaning == balanced
         * nothing to propagate upwards after that
         */
        avl_set_balance(parent, AVL_NEUTRAL);
        parent = NULL;
        break;
    case AVL_NEUTRAL:
        /* mark balance as left and continue upwards */
        avl_set_balance(parent, AVL_LEFT);
        break;
    case AVL_LEFT:
        /* compensate double left balance by rotation
         * and stop afterwards
         */
        switch (avl_balance(node)) {
        default:
        case AVL_LEFT:
        case AVL_NEUTRAL:
            MMMM(node, parent, root);
            break;
        case AVL_RIGHT:
            NNNN(node, parent, root);
            break;
        }

        parent = NULL;
        break;
    }
}

函式 avl_insert_balance 主要是用來平衡 AVL tree，主要會有 4 種情形需要做 rotation，分別是 LL 型、 LR 型、 RR 型、 RL 型，此 else 為 L 情形，所以 case AVL_NEUTRAL: 為 LL 型，而 case AVL_RIGHT: 為 LR 型，故 LL 型須做右旋，所以 MMMM 為 avl_rotate_right ，而 LR 型須先做左旋，再做右旋，所以 NNNN 為 avl_rotate_leftright 。

答案

• IIII = node->parent_balance & ~7
• JJJJ = node->parent_balance & 3
• KKKK = node->parent_balance & 3
• LLLL = node->parent_balance & ~7
• MMMM = avl_rotate_right
• NNNN = avl_rotate_leftright

---

測驗三

程式碼原理

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 可以處理的以 2 為底的 x 的對數，可以看到只有

$2^8$ ，所以若要處理 64 bit 的數值，只能將數值拆解成每 8 bit 進行處理。

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 = AAAA + log_table_256[t];
            } else {
                r = BBBB + log_table_256[tt];
            }
        } else {
            t = ttt >> 8;
            if (t) {
                r = CCCC + log_table_256[t];
            } else {
                r = DDDD + log_table_256[ttt];
            }
        }
    }
...
}

函式 log2_64 是用來計算以 2 為底的 x 的對數 (logarithm of x to the base b)，且下取整函數 (floor)，因為 log_table_256 只能處理

$2^8$ 的數，所以不難看出須以每 8 個 bit 進行處理。t 為將輸入右移 56 個 bit 的數，這裡以

$2^{57}$ 為例，t 會等於 1，而

$2^{57}$ 取 log 會等於 57 ，所以我們可以知道 output r 為 57 ，所以 AAAA + log_table_256[1] = 57 ，而 log_table_256[1] 查表為 0 ，所以 AAAA 為 56 。

2^57 >> 56 = 00...001
t = 1
log_table_256[1] = 1
AAAA + log_table_256[1] = 57
AAAA + 1 = 57
AAAA = 56

而 BBBB 為輸入大於 48 個 bit ，小於 56 個 bit 的情形，所以 BBBB 可以推得為 48 ，以此類推，以每 8 bit 為範圍去分。

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

再來看函式 lfsr ，LFSR 的功用為指給定前一狀態，將該輸出的線性函數作為輸入的移位暫存器，這裡用於產生隨機數。

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 & IIII)) +
           ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ));
    /* 'x >> (N_BITS + 1)' : take different set of bits -> better uniformity.
     * '... & mask011' guarantees that the result is less or equal N_BUCKETS.
     */
}

先來看函式 bucket_number 其作用為在指定區間內，使產生的 LFSR 數值得以均勻分佈，當 N_BUCKETS 為 120 時， mask111 與 mask011 分別為 127 與 63 ，lep 用來判定輸入值的最右邊 7 bit 是否會小於等於 bucket_number 。

N_BUCKETS = 120
N_BITS = log2_64(120) = 6
mask111 = (1 << (N_BITS + 1)) - 1 = (1 << (6 + 1)) - 1 = 127
mask011 = (1 << (N_BITS)) - 1     = (1 << (6)) - 1     = 63

因為lep 只為 0 或 1 ，所以 (leq * (x & IIII)) + ((1 - leq) * ((x >> (N_BITS + 1)) & JJJJ)); 會有兩種 case

case1: x & IIII
case2: ((x >> (N_BITS + 1)) & JJJJ

當lep = 1，則表示輸入值的最右邊 7 bit 會小於等於 bucket_number，所以輸出 x & mask111 即可，故 IIII 為 mask111 ，而若超過 bucket_number 時，則用不同組的 bit ，所以會先右移 N_BITS (7) ，因為該值可能會超過 bucket_number ，所以與 mask111 and 確保不會超過 bucket_number 。

答案

• AAAA = 56
• BBBB = 48
• CCCC = 40
• DDDD = 32
• EEEE = 24
• FFFF = 16
• GGGG = 8
• HHHH = 0
• IIII = mask111
• JJJJ = mask011

---

測驗四

程式碼原理

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 (KKKK) + 1;       
}

x 分別跟四個不同值比較，分別是

$2^{16}-1$,

$2^8-1$,

$2^4-1$,

$2^2-1$，也就是將 x 拆解成四個區間去判斷，並將其對數大小的結果存於變數 r 裡面，，當 x 大於第一個區間時，會將 16 存在 r 中，並將 x 右移 16 個 bit ，再去判斷剩下的 bit 在哪個區間裡，而可以看到在

$2^2-1$ 時，並無將其對數大小的結果存於變數 r 裡，所以最後須作 r | shift ，而這些區間加總為 16 + 8 + 4 + 2 = 30 ，所以若 x 大於

$2^{30}$ ，則最後的 x 會剩 2 個 bit ，於是將其右移1，去判斷其值是否大於

$2^{30}$ 或大於

$2^{31}$ ，所以 KKKK 為 r | shift | x >> 1，最後加 1 是為了取其對數的上界。

• KKKK = r | shift | x >> 1