# 2021q1 Homework2 (quiz2)
###### tags:<`linux2021`>
## 題目`1`
考慮以下仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作:

#include <stddef.h>

/**
 * container_of() - Calculate address of object that contains address ptr
 * @ptr: pointer to member variable
 * @type: type of the structure containing ptr
 * @member: name of the member variable in struct @type
 *
 * Return: @type pointer of object containing ptr
 */
#ifndef container_of
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
#endif

/**
 * struct list_head - Head and node of a doubly-linked list
 * @prev: pointer to the previous node in the list
 * @next: pointer to the next node in the list
 */
struct list_head {
    struct list_head *prev, *next;
};

/**
 * LIST_HEAD - Declare list head and initialize it
 * @head: name of the new object
 */
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

/**
 * INIT_LIST_HEAD() - Initialize empty list head
 * @head: pointer to list head
 */
static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head; head->prev = head;
}

/**
 * list_add_tail() - Add a list node to the end of the list
 * @node: pointer to the new node
 * @head: pointer to the head of the list
 */
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

/**
 * list_del() - Remove a list node from the list
 * @node: pointer to the node
 */
static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next, *prev = node->prev;
    next->prev = prev; prev->next = next;
}

/**
 * list_empty() - Check if list head has no nodes attached
 * @head: pointer to the head of the list
 */
static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

/**
 * list_is_singular() - Check if list head has exactly one node attached
 * @head: pointer to the head of the list
 */
static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

/**
 * list_splice_tail() - Add list nodes from a list to end of another list
 * @list: pointer to the head of the list with the node entries
 * @head: pointer to the head of the list
 */
static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next, *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

/**
 * list_cut_position() - Move beginning of a list to another list
 * @head_to: pointer to the head of the list which receives nodes
 * @head_from: pointer to the head of the list
 * @node: pointer to the node in which defines the cutting point
 */
static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

/**
 * list_entry() - Calculate address of entry that contains list node
 * @node: pointer to list node
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_entry(node, type, member) container_of(node, type, member)

/**
 * list_first_entry() - get first entry of the list
 * @head: pointer to the head of the list
 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type
 */
#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

/**
 * list_for_each - iterate over list nodes
 * @node: list_head pointer used as iterator
 * @head: pointer to the head of the list
 */
#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)

接著延伸上述程式碼時做 doubly-linked list 的 merge sort:

#include <string.h>

typedef struct __element {
    char *value;
    struct __element *next;
    struct list_head list;
} list_ele_t;

typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    size_t size;
    struct list_head list;
} queue_t;

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (COND1 || COND2)
            break;
        fast = fast->next->next;
    }
    return list_entry(TTT, list_ele_t, list);
}

static void list_merge(struct list_head *lhs,
                       struct list_head *rhs,
                       struct list_head *head)
{
    INIT_LIST_HEAD(head);
    if (list_empty(lhs)) {
        list_splice_tail(lhs, head);
        return;
    }
    if (list_empty(rhs)) {
        list_splice_tail(rhs, head);
        return;
    }

    while (!list_empty(lhs) && !list_empty(rhs)) {
        char *lv = list_entry(lhs->next, list_ele_t, list)->value;
        char *rv = list_entry(rhs->next, list_ele_t, list)->value;
        struct list_head *tmp = strcmp(lv, rv) <= 0 ? lhs->next : rhs->next;
        list_del(tmp);
        list_add_tail(tmp, head);
    }
    list_splice_tail(list_empty(lhs) ? rhs : lhs, head);
}

void list_merge_sort(queue_t *q)
{
    if (list_is_singular(&q->list))
        return;

    queue_t left;
    struct list_head sorted;
    INIT_LIST_HEAD(&left.list);
    list_cut_position(&left.list, &q->list, MMM);
    list_merge_sort(&left);
    list_merge_sort(q);
    list_merge(&left.list, &q->list, &sorted);
    INIT_LIST_HEAD(&q->list);
    list_splice_tail(&sorted, &q->list);
}

* COND1 : `fast -> next == list`
* COND2 : `fasr->next->next == list`
* MMM : `&get_middle(&q->list)->list`
* TTT : `slow`

測試程式碼 main.c 如下：

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

static bool validate(queue_t *q)
{
    struct list_head *node;
    list_for_each (node, &q->list) {
        if (node->next == &q->list)
            break;
        if (strcmp(list_entry(node, list_ele_t, list)->value,
                   list_entry(node->next, list_ele_t, list)->value) > 0)
            return false;
    }
    return true;
}

static queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q) return NULL;

    q->head = q->tail = NULL;
    q->size = 0;
    INIT_LIST_HEAD(&q->list);
    return q;
}

static void q_free(queue_t *q)
{
    if (!q) return;

    list_ele_t *current = q->head;
    while (current) {
        list_ele_t *tmp = current;
        current = current->next;
        free(tmp->value);
        free(tmp);
    }
    free(q);
}

bool q_insert_head(queue_t *q, char *s)
{
    if (!q) return false;

    list_ele_t *newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    char *new_value = strdup(s);
    if (!new_value) {
        free(newh);
        return false;
    }

    newh->value = new_value;
    newh->next = q->head;
    q->head = newh;
    if (q->size == 0)
        q->tail = newh;
    q->size++;
    list_add_tail(&newh->list, &q->list);

    return true;
}

int main(void)
{
    FILE *fp = fopen("cities.txt", "r");
    if (!fp) {
        perror("failed to open cities.txt");
        exit(EXIT_FAILURE);
    }

    queue_t *q = q_new();
    char buf[256];
    while (fgets(buf, 256, fp))
        q_insert_head(q, buf);
    fclose(fp);

    list_merge_sort(q);
    assert(validate(q));

    q_free(q);

    return 0;
}

### （一）解釋程式碼運作原理：
根據 merge-sort 的實作方法，第一步先將整個序列對半分割：

digraph mergesort{
    O [label = "Original Array" , shape = Box]
    P1[label = "P1" , shape = Box]
    P2[label = "P2" , shape = Box]
    O -> P1 [label = "partition into two"]
    O -> P2
    
}

分別將左右兩個序列依照一樣的步驟分割直到不能再分割（size is 1）後倆倆合併 :

digraph merge{
    P1 [label = "E1(size 1)" , shape = "Box"]
    P2 [label = "E2(size 1)" , shape = "Box"]
    P3 [label = "E3(size 1)" , shape = "Box"]
    P4 [label = "E4(size 1)" , shape = "Box"]
    P5 [label = "M1(size 2)" , shape = "Box"]
    P6 [label = "M2(size 2)" , shape = "Box"]
    P1->P5 [label = "Merge" , fontcolor = red] 
    P2->P5
    P3->P6 [label = "  Merge" , fontcolor = red] 
    P4->P6
    P7 [label = "Final(size 4)" , shape = "Box"]
    P5 -> P7 [label = "Merge" , fontcolor = red]
    P6 -> P7
}

對於 Linked List 裡面該如何將其分成兩段？在程式碼中的 `get_middle` 使用的方法是利用 `fast` 、 `slow` 指標，`fast` 指標走訪 linked list 的速度是 `slow` 的兩倍，因為是 doubly linked list 所以當 `fast` 走到開頭的時候代表整個串列已經走訪完，所以 `slow` 指標會指在串列的中間位置，對應的程式碼為：

static list_ele_t *get_middle(struct list_head *list)
{
    struct list_head *fast = list->next, *slow;
    list_for_each (slow, list) {
        if (fast->next == list || fast->next->next == list)
            break;
        fast = fast->next->next;
    }
    return list_entry(slow, list_ele_t, list);
}

上述程式碼在最後的回傳值是 `list_ele_t*` (pointer to list_ele_t) ，但是 `slow` 是 `struct list_head*` (pointer to struct list_head) ，所以在回傳時使用 `list_entry` 巨集算出包含 `slow` 指標的 `list_ele_t` 記憶體位置。
接著看程式碼中在哪裡呼叫 `get_middle`：

...
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left.list, &q->list, &sorted);
...

由此可知是在 `list_cut_position` 中呼叫的，接下來看看 `list_cut_position` 的實作：

static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

對應的操作如圖：
* 一開始的狀況，`e1` 為 list 的開頭 `e3` 為中間的節點

digraph list{
    rankdir = LR
    head_from_first [label = "head_from_first" , shape = "box"]
    head_from [label = "head_from" , shape = "box"]
    head_to[shape = "box"]
    node_ [label = "node" , shape = "box"]
    e1 [shape = "box"]
    e2 [shape = "box"]
    e3 [shape = "box"]
    e4 [shape = "box"]
    e5 [shape = "box"]
    e1 -> e2[tailclip = true , arrowsize = 1] e2->e1
    e2 -> e3 e3->e2
    e3 -> e4 e4->e3
    e4 -> e5 e5->e4
    e1 -> e5 e5->e1
    head_to -> head_to
    head_from -> e1 [arrowhead = vee , style = dashed , color = red]
    head_from_first -> e2 [arrowhead = vee , style = dashed , color = red]
    node_ -> e3 [arrowhead = vee , style = dashed , color = red]
}

* 讓 `e1` (head_from 所指的記憶體位址) 的 next 指向 `e4` (node->next 所指的記憶體位址)，`e4` (head_from->next 所指的記憶體位址) 的 pre 指向 `e1` (head_from 所指的記憶體位址)

digraph list{
    rankdir = LR
    head_from_first [label = "head_from_first" , shape = "box"]
    head_from [label = "head_from" , shape = "box"]
    head_to[shape = "box"]
    node_ [label = "node" , shape = "box"]
    e1 [shape = "box"]
    e2 [shape = "box"]
    e3 [shape = "box"]
    e4 [shape = "box"]
    e5 [shape = "box"]
    e1 -> e4[ color = blue , style = dashed] e2->e1
    e2 -> e3 e3->e2
    e3 -> e4 e4->e1 [color = blue , style = dashed]
    e4 -> e5 e5->e4
    e1 -> e5 e5->e1
    head_to -> head_to
    head_from -> e1 [arrowhead = vee , style = dashed , color = red]
    head_from_first -> e2 [arrowhead = vee , style = dashed , color = red]
    node_ -> e3 [arrowhead = vee , style = dashed , color = red]
}

* 接下來執行完剩下的四行，就可以拆成兩段了

digraph list{
    rankdir = LR
    head_from_first [label = "head_from_first" , shape = "box"]
    head_from [label = "head_from" , shape = "box"]
    head_to[shape = "box"]
    node_ [label = "node" , shape = "box"]
    e1 [shape = "box"]
    e2 [shape = "box"]
    e3 [shape = "box"]
    e4 [shape = "box"]
    e5 [shape = "box"]
    e1 -> e4
    e2 -> head_to[color = blue] e3->e2
    e2 -> e3
    e3 -> head_to[color = blue] e4->e1
    e4 -> e5 e5->e4
    e1 -> e5 e5->e1
    head_to -> e3 [label = "pre" color = blue]
    head_to -> e2 [label = "next" color = blue]
    
    head_from -> e1 [arrowhead = vee , style = dashed , color = red]
    head_from_first -> e2 [arrowhead = vee , style = dashed , color = red]
    node_ -> e3 [arrowhead = vee , style = dashed , color = red]
}

接下來針對分出的兩段 linked list 個別去做 merge sort 依序遞迴下去，
(Keep going)

## 題目 `2`
考慮函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
假定 N = 101012 = 2110，那麼 func(21) 要得到 16，請補完程式碼，使其運作符合預期。
實作程式碼如下:

uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> X;
    N |= N >> Y;
    N |= N >> Z;

    return (N + 1) >> 1;
}

* X : 2
* Y : 4
* Z : 8
### （一）解釋程式碼運作原理
* 考慮以下數字 0b 1000 0000

digraph bits{
    node [shape=plaintext, fontcolor=red, fontsize=18]
     "Value:" -> "Bits:" [color=white]

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]
    values [label="<f0> 1 | <f1> 0 | <f2> 0 | <f3> 0 | <f4> 0 | <f5> 0 | <f6> 0 | <f7> 0", color=blue, fillcolor=white, style=filled]
     indices [label="0th | 1th | 2th | 3th | 4th | 5th |6th | 7th", color=white]
     { rank=same; "Value:"; values }
     { rank=same; "Bits:" ; indices}
     
}

* 先將其向右 shift 一格會變成

digraph bits{
    node [shape=plaintext, fontcolor=red, fontsize=18]
     "Value:" -> "Bits:" [color=white]

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]
    values [label="<f0> 0 | <f1> 1 | <f2> 0 | <f3> 0 | <f4> 0 | <f5> 0 | <f6> 0 | <f7> 0", color=blue, fillcolor=white, style=filled]
     indices [label="0th | 1th | 2th | 3th | 4th | 5th |6th | 7th", color=white]
     { rank=same; "Value:"; values }
     { rank=same; "Bits:" ; indices}
     
}

* 將其對原數做 `or(|)` 運算後得到的結果可見最高位元的右邊一格變成 1

digraph bits{
    node [shape=plaintext, fontcolor=red, fontsize=18]
     "Value:" -> "Bits:" [color=white]

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]
    values [label="<f0> 1 | <f1> 1 | <f2> 0 | <f3> 0 | <f4> 0 | <f5> 0 | <f6> 0 | <f7> 0", color=blue, fillcolor=white, style=filled]
     indices [label="0th | 1th | 2th | 3th | 4th | 5th |6th | 7th", color=white]
     { rank=same; "Value:"; values }
     { rank=same; "Bits:" ; indices}
     
}

* 目的是希望最高位元的右邊全部都變為 1 ，故必須用剛得到的結果繼續做，由於現在最高的二位元都為 1 ，必須對向右移 2 的結果做 `or` 運算才能把前面 4 位元都變為 1 ，結果如圖

digraph bits{
    node [shape=plaintext, fontcolor=red, fontsize=18]
     "Value:" -> "Bits:" [color=white]

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]
    values [label="<f0> 1 | <f1> 1 | <f2> 1 | <f3> 1 | <f4> 0 | <f5> 0 | <f6> 0 | <f7> 0", color=blue, fillcolor=white, style=filled]
     indices [label="0th | 1th | 2th | 3th | 4th | 5th |6th | 7th", color=white]
     { rank=same; "Value:"; values }
     { rank=same; "Bits:" ; indices}
     
}

* 接下來為了把最右邊的 4 位元都變成 1 ，就將結果向右移動 4 位元再做 `or` 便可以把它填滿並變成 1

digraph bits{
    node [shape=plaintext, fontcolor=red, fontsize=18]
     "Value:" -> "Bits:" [color=white]

    node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true]
    values [label="<f0> 1 | <f1> 1 | <f2> 1 | <f3> 1 | <f4> 1 | <f5> 1 | <f6> 1 | <f7> 1", color=blue, fillcolor=white, style=filled]
     indices [label="0th | 1th | 2th | 3th | 4th | 5th |6th | 7th", color=white]
     { rank=same; "Value:"; values }
     { rank=same; "Bits:" ; indices}
     
}

* 這邊舉例是 8 bit 的無號數，但題目敘述是對 16 bit 無號數做運算，故將剛剛得到的結果再向右移 8 個位元便可填滿最右邊 8 位元

### （二）查閱 linux 核心原始碼
#### `is_power_of_2`
在 [arch/microblaze/mm/pgtable.c](https://elixir.bootlin.com/linux/latest/source/arch/microblaze/mm/pgtable.c#L186) 中將其定為 macro：

#define is_power_of_2(x) ((x) != 0 && (((x) & ((x) - 1)) == 0))

若該數為 2 的冪次方則該數的最高非 0 位元右側必定全都為 0 ，將該數對該數扣 1 做 `and` 運算若為 0 則該數為 2 的冪次方