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

###### tags: `linux2021`

## 測驗 `1`
### 1. 解釋程式碼，說明其改進空間

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

- `slow` 在 `lost_for_each` loop 中起始位置為 `head`，每次遞增 1
- `fast` 的起始位置為 `head->next`，每次遞增 2，可以保證當

如此一來可以確保當 `slow` 在第 $n$ 個 node 時，`fast` 會在第 $2n$ 個 node，因此當 `fast` 到尾端、或是繞一圈回到 `head` 時 `slow` 會剛好停在第 $ceil(list\_size)$ 個 node，即 linked 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);
}

- 將 `lhs` 與 `rhs` 中的 head node 取出，比較其值大小後將值較小者從原有的 list 中移除，並串接至 `head`
- 當有 `lhs` 或 `rhs` 任一內容為空後，即可將另一方串接至 `head` 後 return

:::danger
開頭的兩個 if 條件式有誤，邏輯上應是用 `list_empty` 判定 `lhs` 或 `rhs` 任一空白，即無須處理空白的 list，直接將另一方串接至 `head` 後結束函式即可，因此程式碼應做以下修改

    if (list_empty(lhs)) {
-       list_splice_tail(lhs, head);
+       list_splice_tail(rhs, head);
        return;
    }
    if (list_empty(rhs)) {
-       list_splice_tail(rhs, head);
+       list_splice_tail(lhs, head);
        return;
    }

:::
:::warning
**改進空間：**
此處的 `list_del` function 我認為命名得不恰當，delete 應是將其直接從記憶體中釋放的意思，但此處只是要將 node 的前後連接斷開，目的並非刪除，將其改名為 `list_remove` 應會更加符合本意
:::

---

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, &get_middle(&q->list)->list
);
    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);
}

- 將 queue 透過 `list_cut_position` 從 `get_middle()` function 找到的中點切開，分別將左、右存放置新宣告的 `queue_t left`、以及原來的 `queue_t *q` 之中
- 用 `list_merge_sort` function 將左右的內容個別排序，再用 `list_merge` function 將左右合併
- `q` 的內容重製，並將結果放回 `q` 中即可
:::warning
**改進空間：**
- 在 recursive call 的每一層中真正有被操作到的其實只有 linked list 中的 nodes 本身，卻都需要宣告出一個新的 `queue_t left` 來暫存 merge sort 切割出的左半段，平白消耗 function call stack 中的 memory 空間
- 需要不斷將 queue 的 head 與 tail 重新設置，但每次 merge 又可能會被覆蓋掉，平白增加執行時間
:::

### 2. 將 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 的實作抽離為 standalone 程式，評測並說明其最佳化手段

---
## 測驗 `2`

### 1. 解釋程式碼運作原理

/* 找出小於等於 N 且最大的 power-of-2 */
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;
}

在 binary 的數值系統，一個數是 power-of-2 代表其所有 bits 中只有唯一一個 bit 是 `1`，其餘皆為 `0`，因此可以將題意轉為找出一個小於 N 、且符合上述條件的最大數，也就是要算出將位於最左邊的 `1` 保留，其餘 bits 都歸 `0` 的數

但本題的實做方式為將所有位於最左邊的 `1` (以下簡稱為 MS1) 右方的 bits 都轉成 `1`，再將這個結果 + 1 後往右 shift 一位，也可以得到相同的結果

本題將所有位於 MS1 右方的 bits 都轉成 `1` 的方式為先右移一位後與原數做 `|=`，可以確保在 MS1 正右方的 bit 將被轉變為 `1`，再右移兩位與原數做 `|=` 可以確保 MS1 右方的 3 個 bits 都會被轉變為 `1`，重複上述算法至右移 8 位即可得出答案

---

## 測驗 `3`

### 1. 解釋程式碼運作原理

#include <stdint.h>

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read / 8);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write / 8);

    static const uint8_t read_mask[] = {
        0x00, /*    == 0    00000000b   */
        0x80, /*    == 1    10000000b   */
        0xC0, /*    == 2    11000000b   */
        0xE0, /*    == 3    11100000b   */
        0xF0, /*    == 4    11110000b   */
        0xF8, /*    == 5    11111000b   */
        0xFC, /*    == 6    11111100b   */
        0xFE, /*    == 7    11111110b   */
        0xFF  /*    == 8    11111111b   */
    };

    static const uint8_t write_mask[] = {
        0xFF, /*    == 0    11111111b   */
        0x7F, /*    == 1    01111111b   */
        0x3F, /*    == 2    00111111b   */
        0x1F, /*    == 3    00011111b   */
        0x0F, /*    == 4    00001111b   */
        0x07, /*    == 5    00000111b   */
        0x03, /*    == 6    00000011b   */
        0x01, /*    == 7    00000001b   */
        0x00  /*    == 8    00000000b   */
    };

    while (count > 0) {
        uint8_t data = *source++;
        size_t bitsize = (count > 8) ? 8 : count;
        if (read_lhs > 0) {
            data <<= read_lhs;
            if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
        }

        if (bitsize < 8)
            data &= read_mask[bitsize];

        uint8_t original = *dest;
        uint8_t mask = read_mask[write_lhs];
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest++ = (original & mask) | (data >> write_lhs);
            original = *dest & write_mask[bitsize - write_rhs];
            *dest = original | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            mask |= write_mask[bitsize - write_lhs];
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }
}

:::info
**程式中變數 read/write、lhs/rhs 代表的意義：**
程式的實作策略為將 `_src` 中的 bits 一次一個 byte 搬移至 `_dest` 中，由於在 C 語言中存取一個變數的最小單位為 byte，因此若 bit offset 沒有剛好是 8 的倍數，則在開頭要存取的 byte 中會有部分的 bits 並不需要被讀取/寫入，非開頭存取的 byte 中也會有部份的 bits 在上一步中已經被讀取/寫入過了，應要跳過

因此，在讀取中的每個 byte 內，程式以 `read_lhs` 代表位於左半部不需要被讀取（要跳過）的 bits 數量， `read_rhs` 代表位於右半部真正需要讀進來的 bits 數量，寫出時的 `write_lhs` 、`write_rhs` 亦同理
:::

- 讀取出至多一個 byte，暫存至 `data` 中
- 用 `_src + (_read / 8)` 找到第一個有位元需要被讀取的 byte 位置，把值取出至 `data` 中
- 用 `data <<= read_lhs` 將左側不需要被讀取的位元跳過，留下需要的部份（共 `read_rhs` 個位元）
- 若本次要讀取的位元數量超過 `read_rhs` 個位元（前兩步已經處理好了的部份），則須跨越到下一個 byte 讀取：
- 讀出 `read_lhs` 個位元放至 `data` 的右側，也就是 `data |= (*source >> read_rhs)` ，即可填滿這次要讀取的一整個 byte
- 若本次要讀取的位元不滿一整個 byte，則透過 `read_mask` 將尾端多讀進 `data` 的部份去除
- 將 `data` 中暫存的資料寫出
- 用 `_dest + (_write / 8)` 找到第一個需要被寫入位元的 byte 位置
- 若本次處理的位元數量比當前的 byte 放得下的位元數量還多（即 `bitsize > write_rhs`）時，則需要跨越到下一個 byte 去做寫入：
- 用 `data >> write_lhs` 讓 `data` 中只剩下當前的 byte 放得下的位元數量（即 `write_rhs` 個位元）並且靠右
- 再用 `original & mask` 確保左側值不會被改到後寫入 `dest`
- 跨越到下一個 byte，將 `original` 更新為下一個 byte 還需要寫入的位元數量（`bitsize - write_lhs` 個位元）後再次寫入
- 若本次處理的的位元數量不足填滿第一個 byte（ `bitsize < write_rhs` ），則須注意不可讓超出 `bitsize` 個數的位元被修改到
- 將 `mask` 的值後段也設為 `1` 即可避免
- 即 `mask |= write_mask[bitsize - write_lhs]`

### 2. 說明其改進空間

:::info
**branch miss 所造成的效能浪費：**

程式中的 if 條件式在被編譯為執行檔時，會被轉換成組合語言中 branch 相關的 CPU instruction，若 CPU 處理 instruction 時有用到 pipeline 的架構，則會需要做 branch prediction 來預測之後 instruction 的執行順序，但若預測失敗（即所謂的 branch miss）則會造成往後所有處理到一半的 instruction 需要 revert 到 predict 前的狀態，平白浪費 CPU cycle，因此若可以減少程式中不必要的 if 條件式，可以有效提升程式的效能
:::

這段 `bitcpy` 程式中我發現在讀取的過程中，因為最後都能夠用 `read_mask` 將 `data` 中不需要的部分剔除，因此在這之前其實不需要刻意去調整 data 要讀取的 range 有多大、以及有沒有跨越到下一個 byte，直接將完整一個 byte 的大小讀取出來，最後再用 `read_mask` 留下需要的部分即可，因此程式可以改成如下，將所有 if 條件式移除：

        size_t bitsize = (count > 8) ? 8 : count;
-       if (read_lhs > 0) {
            data <<= read_lhs;
-           if (bitsize > read_rhs)
                data |= (*source >> read_rhs);
-       }

-       if (bitsize < 8)
            data &= read_mask[bitsize];
...            

此外，程式中另外宣告的兩個 `mask`，在使用時需要來回查看其內容，使用上有些許不便，額外宣告這兩個陣列也會增加記憶體 stack 空間的使用，應該有更好的實作方式，我觀察後發現兩陣列的內容有規律性，其實透過 bitwise 的操作就可以直接完成了，取代方式如下：

read_mask[i] == 0xFF << (8 - i)
write_mask[i] == 0xFF >> i

因此最終完成的程式如下：
> [GitHub](https://github.com/Nahemah1022/Linux2021-quizzes/blob/main/quiz2/bitcpy/bitcpy.c)

void bitcpy(void *_dest,      /* Address of the buffer to write to */
            size_t _write,    /* Bit offset to start writing to */
            const void *_src, /* Address of the buffer to read from */
            size_t _read,     /* Bit offset to start reading from */
            size_t count)
{
    size_t read_lhs = _read & 7;
    size_t read_rhs = 8 - read_lhs;
    const uint8_t *source = (const uint8_t *) _src + (_read / 8);
    size_t write_lhs = _write & 7;
    size_t write_rhs = 8 - write_lhs;
    uint8_t *dest = (uint8_t *) _dest + (_write / 8);

    while (count > 0) {
        uint8_t data = *source++;
        size_t bitsize = (count > 8) ? 8 : count;
        data <<= read_lhs;
        data |= (*source >> read_rhs);
        data &= 0xFF << (8 - bitsize);

        uint8_t original = *dest;
        uint8_t mask = 0xFF << (8 - write_lhs);
        if (bitsize > write_rhs) {
            /* Cross multiple bytes */
            *dest++ = (original & mask) | (data >> write_lhs);
            original = *dest & (0xFF >> (bitsize - write_rhs));
            *dest = original | (data << write_rhs);
        } else {
            // Since write_lhs + bitsize is never >= 8, no out-of-bound access.
            mask |= (0xFF >> (bitsize - write_lhs));
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }
}