# 2021q1 Homework2 (quiz2)
contributed by < `Edwardz43` >

> [第二周測驗題](https://hackmd.io/@sysprog/linux2021-quiz2)

## Q1

### 原理

與 `lab0` 的 `list` 很相似，主要差別在當時的 linked list 是自行完成相關的功能，而這邊則是利用仿效 `linux/list.h` 的雙向環狀串列來管理

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

digraph head {
    subgraph cluster0 {
    node[shape=record,style=filled,color=white];
    next[label="next"];
    perv[label="prev"];
    style=filled;
    color=lightgrey;
    label = "List_head";
    }
}

很單純的結構，只有兩個指標，一個指向前一個 node(`prev`)，另一個指向下一個 node(`next`)

使用上也不算複雜，只要在指定的 `struct` 內包含 `list_head` 這個成員，就可以利用它來與其他 node 鍊結，並利用相關的函式來管理串列，可以想像把一條練子==裝備==在身上，用來與其他人連結

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

初始化時利用 `INIT_LIST_HEAD` 巨集， 將 `next` 與 `prev` 都指向自己
>這時 `head` 是 `NULL`

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

digraph {
rankdir=LR;
node [shape="record",height=.1,width=.6];
edge [dir="both"];

omit1 [label="..." shape="none"];
tail [label="tail"];
new [label="node"];
head [label="head"];
omit2 [label="..." shape="none"];

omit1 -> tail;
tail -> head [style=dotted];
head -> omit2;
tail -> new -> head [color=red];
}

當有新的成員加入，會經由 `list_add_tail` 來鏈接，先由 `head->prev` 可以找到 `tail` ， 再將後者的 `next` 指標指向 `node`，之後 `node->next` 指向 `head`， 最後將 `head->prev` 改為指向新加入的 `node`，形成環狀的串列

/**
 * 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_is_singular` 用來檢驗是否為單節點

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

digraph {
rankdir=LR;
node [shape="record",height=.1,width=.6];
edge [dir="both"];

omit1 [label="..." shape="none"];
prev [label="prev"];
new [label="node"];
next [label="next"];
omit2 [label="..." shape="none"];

omit1 -> prev;
prev -> next [color=red];
next -> omit2;
prev -> new -> next [style=dotted];
}

移除 `node` 的過程與 `add` 類似，只是反過來做，將待移除節點的 `prev` 與 `next` 鏈結

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

函式的目標是取得 `list` 中間的節點，所以採用的方法相似於 `lab0` 用過的龜兔賽跑，分為 `slow` 與 `fast` 兩個指標

考量到數列的長度奇偶不同的狀況，這邊先分開討論：

### Odd

digraph Odd {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
list [label="list"];
node1 [label="node1"];
node2 [label="node2"];
node3 [label="node3"];
node4 [label="node4"];
node5 [label="node5"];

list -> node1 [label="next",color="red"];
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
list -> node5 [label="prev",color="red"];
node5 -> list;

f1 [label="f1",shape="none",fontcolor=green];
s1 [label="s1",shape="none",fontcolor=blue];
f1 -> node1 [style=dotted];
s1 -> node1 [style=dotted];

f2 [label="f2",shape="none",fontcolor=green];
s2 [label="s2",shape="none",fontcolor=blue];
s2 -> node2 [style=dotted];
f2 -> node3 [style=dotted];

f3 [label="f3",shape="none",fontcolor=green];
s3 [label="s3",shape="none",fontcolor=blue];
s3 -> node3 [style=dotted];
f3 -> node5 [style=dotted];
}

因為目的是要找到 middle of list，這邊採用的方式是類似龜兔賽跑，且兔子(`fast`)的速率是烏龜(`slow`)的兩倍，所以當兔子跑到終點(fast->next == list)時，烏龜正好跑到一半(`middle`)

slow: 1 -> 2 -> 3
fast: 1 -> 3 -> 5

### Even

digraph Even {
nodesep=.05;
rankdir=LR;
node [shape=record,width=.1,height=.1];
list [label="list"];
node1 [label="node1"];
node2 [label="node2"];
node3 [label="node3"];
node4 [label="node4"];
node5 [label="node5"];
node6 [label="node6"];

list -> node1 [label="next",color="red"];
node1 -> node2;
node2 -> node3;
node3 -> node4;
node4 -> node5;
node5 -> node6;
list -> node6 [label="prev",color="red"];
node6 -> list;

f1 [label="f1",shape="none",fontcolor=green];
s1 [label="s1",shape="none",fontcolor=blue];
f1 -> node1 [style=dotted];
s1 -> node1 [style=dotted];

f2 [label="f2",shape="none",fontcolor=green];
s2 [label="s2",shape="none",fontcolor=blue];
s2 -> node2 [style=dotted];
f2 -> node3 [style=dotted];

f3 [label="f3",shape="none",fontcolor=green];
s3 [label="s3",shape="none",fontcolor=blue];
s3 -> node3 [style=dotted];
f3 -> node5 [style=dotted];

f4 [label="f4",shape="none",fontcolor=green];
s4 [label="s4",shape="none",fontcolor=blue];
s4 -> node4 [style=dotted];
f4 -> list [style=dotted];
}

若是數列長度為偶數，因為 `fast` 每次移動兩個單位，就會出現 `fast->next` 碰不到 `list` 狀況

* slow: 1 -> 2 -> 3 -> 4
* fast: 1 -> 3 -> 5 -> list

因此需要多加一個判斷條件

...
if (fast->next == list || fast->next->next == list)
    break;
...

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

---

## Q2

/* return round down power of 2 with given unsigned int16 */
uint16_t func(uint16_t N) {
    /* change all right side bits to 1 */
    N |= N >> 1;
    N |= N >> 2;
    N |= N >> 4;
    N |= N >> 8;

    return (N + 1) >> 1;
}

目標是利用 bitwise operation 取得小於或等於 N 的 `power-of-2`，主要的想法是找到 Ｎ 的 `leading one bit`，並將其以下的 bit 都轉換成 1，之後再將其值 + 1 並向右 shift

考量到 `N` 為 uint_16，為了將 `leadiing one bit` 以下的==所有==位元都轉成 1，需要經過 4 次 ($2^4 = 16$) 的 `|=` 與 shift 操作

==e.g.==

$$\begin{gather*}N = 10101_2 = 21_{10}\end{gather*}$$

經過 `|=` 與 `shift` 處理後

$$\begin{gather*}N = 11111_2\\
N + 1 = 100000_2\\
N >> 1 = 10000_2 = 16_{10}\end{gather*}$$

:::warning
:bulb: `N + 1` overflow handling ?
:::
根據 ISO C99 `5.1.2.3 Program execution`
>*10 **In executing the fragment**
char c1, c2;
/* ... */
c1 = c1 + c2;
the ‘‘integer promotions’’ require that the abstract machine promote the value of each variable to ==int== size
and then add the two ints and truncate the sum. Provided the addition of two chars can be done without
overflow, or with overflow wrapping silently to produce the correct result, the actual execution need only
produce the same result, possibly omitting the promotions.

當程式執行 `(N + 1) >> 1` 時，==integer promotions== 機制會將 N 與 1 提升至 int 的寬度做計算，因此 N + 1 並不會發生 overflow，
>uint16 + uint16 always small than int

利用 gdb 作簡單的實驗：

...
12	    return (N + 1) >> 1;
(gdb) p N
$1 = 65535
(gdb) ptype N
type = unsigned short
(gdb) ptype N + 1
type = int
(gdb) ptype N - 1
type = int
(gdb) ptype N
type = unsigned short
(gdb) p N * 2
$3 = 131070
(gdb) ptype N * 2
type = int
(gdb) p (uint16_t)(N * 2)
$6 = 65534
(gdb) ptype (uint16_t)(N * 2)
type = unsigned short
...

在第 17 行的結果可以看出 `truncate` 發生作用，將溢位的部份截斷，所以輸出的結果為 65534

$1111111111111111_{2}=10_{65535}$
$1111111111111111_{2} \times 2 = 1111111111111110_2$
$11111111111111110_{2}\to_{truncate}1111111111111110_{2}=10_{65534}$

經過上述的過程，即便 `N + 1` 的結果超過 uint16_t 的上限，經過 shift 右移後所得到的值勢必滿足 `uint16_t` 的寬度，因此可以得到預期的結果

為了進一步求證，將題目的 `uint16_t` 改為 `uint32_t`

uint32_t func(uint32_t N)
{
    N |= N >> 1; 
    N |= N >> 2;  
    N |= N >> 4;  
    N |= N >> 8;  
    N |= N >> 16; 

    return (N + 1) >> 1;
}

int main(int argc, char *argv[])
{
    uint32_t a = strtoul(argv[1], NULL, 10); 
    printf("a=%u\n", a);
    uint32_t b = func(a);
    printf("b=%u\n", b);
    return 0;
}

輸入 32位元有號數的最大值 ==2147483647==

$ ./main 2147483647
a=2147483647
b=1073741824

得到正確的答案，再將輸入加 + 1

$ ./main 2147483648
a=2147483648
b=0

如預期中的，在第9行 `N + 1` 超過 uint32_t 的上限(4294967295) 發生 overflow，得到的答案為 0

---

## Q3

---

## Q4

###### tags: `week2` `sysprog2021q1`