# 2021q1 Homework2 (quiz2)
contributed by < `yellow-hank` >
###### tags: `LinuxKernel`

## 測驗 `1`

#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 (fast->next == list || fast->next->next == list)
            break;
        fast = fast->next->next;
    }
    return list_entry(slow, 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, &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);
}

### 解釋原理
Merge sort 先檢查 list 是否只有一個值，若只有一個則不進行排序，直接回傳。 Merge sort 是先分割，在合併時做排序。而 quick sort 是在分割時，進行排序，合併時直接將排序好的合併。

INIT_LIST_HEAD(&left.list);

上述會先初始化一個 double linked list

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

示意圖

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];
    struct4 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct5 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4:f1 -> struct3;
    struct5:f1 -> struct4;
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct3:f2 -> struct4;
    struct4:f2 -> struct5;
    struct5:f2 -> struct0:f0;
    struct0:f1 -> struct5
    struct0:f2 -> struct1:f0;
}

list_cut_position 會從 middle 切割成兩個 doubly-linked list

`&q->list` 分割後部分

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];

    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct0:f2 -> struct1:f0;
    struct3:f2 -> struct0;
    struct0:f1 -> struct3;
}

&left.list 分割部分

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    

    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct1:f2 -> struct2;
    struct2:f2 -> struct0;
    struct0:f2 -> struct1:f0;
    struct0:f1 -> struct2;
}

說明 `get_middle`

get_middle(&q->list)

初始化 fast 指向下一個 node， slow 指向 list 的開頭

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];
    struct4 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct5 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct6 [label="slow"];
    struct7 [label="fast"];
    
    struct6 -> struct0;
    struct7 -> struct1;
    
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4:f1 -> struct3;
    struct5:f1 -> struct4;
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct3:f2 -> struct4;
    struct4:f2 -> struct5;
    struct5:f2 -> struct0:f0;
    struct0:f1 -> struct5;
    struct0:f2 -> struct1:f0;
}

接下來移動 slow 至下一個節點， fast 移動兩個節點

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];
    struct4 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct5 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct6 [label="slow"];
    struct7 [label="fast"];
    
    struct6 -> struct1;
    struct7 -> struct3;
    
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4:f1 -> struct3;
    struct5:f1 -> struct4;
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct3:f2 -> struct4;
    struct4:f2 -> struct5;
    struct5:f2 -> struct0:f0;
    struct0:f1 -> struct5;
    struct0:f2 -> struct1:f0;
}

:::warning
避免說「一步」這樣不精準的話，走訪的過程中，你可以移動「一個節點」或數個。
:notes: jserv
:::

接下來移動 slow 至下一個節點， fast 移動兩個節點

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];
    struct4 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct5 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct6 [label="slow"];
    struct7 [label="fast"];
    
    struct6 -> struct2;
    struct7 -> struct5;
    
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4:f1 -> struct3;
    struct5:f1 -> struct4;
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct3:f2 -> struct4;
    struct4:f2 -> struct5;
    struct5:f2 -> struct0:f0;
    struct0:f1 -> struct5;
    struct0:f2 -> struct1:f0;
}

當 fast 接下來走到原本的開頭，slow 會是 list 的中間點。

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];
    struct4 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct5 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct6 [label="slow"];
    struct7 [label="fast"];
    
    struct6 -> struct3;
    struct7 -> struct0;
    
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4:f1 -> struct3;
    struct5:f1 -> struct4;
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct3:f2 -> struct4;
    struct4:f2 -> struct5;
    struct5:f2 -> struct0:f0;
    struct0:f1 -> struct5;
    struct0:f2 -> struct1:f0;
}

獲得中間的 node ，由 slow 指向著，回傳 slow 。

list_merge_sort(&left);
list_merge_sort(q);

再一次呼叫 merge sort 排序 &left 和 q 。

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

此函式會合併 `&left.list` 和 `&q->list`，並且將結果存入 sorted

下圖會舉例由小排到大

digraph structs {
    node[shape=record]
    
    struct1 [label="{<f0> 2|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 3|{<f1>prev|<f2>next}}"];
    struct3 [label="{<f0> 5|{<f1>prev|<f2>next}}"];

    struct0 [label="{{<f1>prev|<f2>next}}"];
    struct4 [label="{lhs}"];
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct3:f1 -> struct2;
    struct4 -> struct0
    
    struct1:f2 -> struct2;
    struct2:f2 -> struct3;
    struct0:f2 -> struct1:f0;
    struct3:f2 -> struct0;
    struct0:f1 -> struct3;

}

digraph structs {
	node[shape=record]
	
    struct1 [label="{<f0> 1|{<f1>prev|<f2>next}}"];
    struct2 [label="{<f0> 4|{<f1>prev|<f2>next}}"];
    struct4 [label="{rhs}"];
    

    struct0 [label="{{<f1>prev|<f2>next}}"];
    
    struct4 -> struct0;
    
    struct1:f1 -> struct0;
    struct2:f1 -> struct1;
    struct1:f2 -> struct2;
    struct2:f2 -> struct0;
    struct0:f2 -> struct1:f0;
    struct0:f1 -> struct2;
}

接下來會各自比較 lhs 和 rhs 的第一個值，將較小的值放入 sorted 裡面

digraph structs {
	node[shape=record]
    struct0 [label="sorted"];
    struct1 [label="{{<f1>prev|<f2>next}}"];
    struct2 [label="{1|{<f1>prev|<f2>next}}"];
    
    struct0 -> struct1;
    struct1:f2 -> struct2;
    struct2:f2 -> struct1;
    struct1:f1 -> struct2;
    struct2:f1 -> struct1;
}

然後將指向比較小的指標移動到下一個，接續重複上述動作，直到 lhs 或 rhs 其中一個為空。將不為空的那一部分直接接到 sorted 後面，完成一次合併，合併完後是一個排序好的 doubly-linked list。

INIT_LIST_HEAD(&q->list);
list_splice_tail(&sorted, &q->list);

初始化一個 doubly-linked list ，把排序好的 sorted 放到queue 的 list 中。

---

## 測驗 `2`
考慮函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 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;
}

假定 N = 10101~2~ = 21~10~，那麼 func(21) 要得到 16，請補完程式碼，使其運作符合預期。

### 解釋原理
要回傳小於或等於 Ｎ 的 power-of-2 ，先分成兩個部分，一個是 N = 0 和 N > 0。
#### N = 0
N = 0 轉換成二進位為 0000 0000 0000 0000~2~，可以看到上述的 bit 皆為0，所以不論怎麼位移，再和自己做 bitwise OR ，結果皆為零。

#### N > 0
N > 0 意味著在16個 bits 中可以找到一最高的位元值為1，只要把低於他的 bit 設為1，加1後，再往右位移1位，就能找到小於或等於 N 的 power-of-2。
假設第k位為Ｎ的最高 bit 值為1，

digraph structs {
	node[shape=record]
	struct1 [label="{{0|0|0|0|0|0|<f0> 1|?|?|?|?|?|?|?|?|?}}"];
    struct2[label="kth bit"];
    struct2 -> struct1:f0
}

set bit 的 bitwise operation 寫法如下：

N |= 1 << k; //set kth position to 1 

因為最大為 16 bits，可以逐一設定 k 以下的值為 1 ，直接引用 N 中位元為 1 ，且位置最高的當作 set bit bitwise operation 的 1 。需要考慮最高位元為 16 ，所以你可以這樣寫：

N |= N >> 1;
N |= N >> 2;
N |= N >> 3;
N |= N >> 4;
N |= N >> 5;
N |= N >> 6;
N |= N >> 7;
N |= N >> 8;
N |= N >> 9;
N |= N >> 10;
N |= N >> 11;
N |= N >> 12;
N |= N >> 13;
N |= N >> 14;
N |= N >> 15;

但是這樣效率太差，可以思考位移一次，和自己做一次 OR 會產生二倍的 1 ，最大是要產生 15 個 1，最少要做四次才能達到 15 的目標，下列是效率較好的程式碼：

N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;

做完結果如下：

digraph structs {
	node[shape=record]
	struct1 [label="{{0|0|0|0|0|0|<f0> 1|1|1|1|1|1|1|1|1|1}}"];
    struct2[label="kth bit"];
    struct2 -> struct1:f0
}

(N + 1) >> 1;

N + 1 後結果如下：

digraph structs {
	node[shape=record]
	struct1 [label="{{0|0|0|0|0|1|<f0> 0|0|0|0|0|0|0|0|0|0}}"];
    struct2[label="kth bit"];
    struct2 -> struct1:f0
}

往右位移一位

digraph structs {
	node[shape=record]
	struct1 [label="{{0|0|0|0|0|0|<f0> 1|0|0|0|0|0|0|0|0|0}}"];
    struct2[label="kth bit"];
    struct2 -> struct1:f0
}

得到在第 k 位值為 1 ，其餘皆為 0 的數，符合題目的小於或等於 N 的 power-of-2。

---

## 測驗 `3`

`bitcpy` 實作程式碼:

#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[write_lhs + bitsize];
            *dest++ = (original & mask) | (data >> write_lhs);
        }

        count -= bitsize;
    }
}

### 解釋原理

size_t read_lhs = _read & 7;

一個 byte 有 8 個 bits ，需要從 _read 中得到從第幾個 byte 第幾個 bit 開始讀取。

_read / 8;

上述可以獲得在第幾個 byte

_read % 8;

上述可以獲得在第幾個 bit，上述的方式可以是改寫成更有效率的方式，因為 8 是 2 的 3 次方，所以可以藉由 bitwise operation 中的 and operation 獲得最低的 3 個 bit，得到下列的方式實作。

_read & 7;

digraph structs {
	node[shape=record]
	struct1 [label="{{?|?|?|?|?|?|?|?}}"];
}

做 and operation

digraph structs {
	node[shape=record]
	struct2 [label="{{0|0|0|0|0|1|1|1}}"];
}

會得到以下結果，跟取餘數是一樣。

digraph structs {
	node[shape=record]
	struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}

接下來移動 source 到要存取的 byte 中，如下列程式碼

const uint8_t *source = (const uint8_t *) _src + (_read / 8);

write 的部分使用跟上述 read 一樣的方式移動到要寫入的 bit 位置

size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);

下列為設定要一次從最高位取走幾個 bit 的 mask。

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

下列為設定要一次從最高位清空幾個 bit 的 mask。

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

此處的迴圈只能一次最高能處理 8 bits 的複製

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[write_lhs + bitsize];
        *dest++ = (original & mask) | (data >> write_lhs);
    }

    count -= bitsize;
}

記憶體排序是根據下圖所示

if (read_lhs > 0) {
    data <<= read_lhs;
    if (bitsize > read_rhs)
        data |= (*source >> read_rhs);
}

read_lhs > 0 代表著取的資料不是從每個 bytes 的最高位開始取，所以需要藉由位移來將資料放入 data 中，下圖表示 data 的資料分成兩部份 lhs 和 rhs 的部分。rhs 的部分會透過 bitsize > read_rhs 來判斷當 bitsize 大過 lhs 的個數 =（8 - read_lhs）= read_rhs ，需要到下一個 bytes 取得 rhs 的部分。

digraph structs {
	node[shape=record]
	struct1 [label="{{<f0>?|?|?|<f1>?|<f2>?|?|?|<f3>?}}"];
    
    struct2 [label="{lhs}"];
    struct3 [label="{rhs}"];
    
    struct2 -> struct1:f0;
    struct2 -> struct1:f1;
    struct3 -> struct1:f2;
    struct3 -> struct1:f3;
    
}

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

如果單次取的 bit 個數少於 8 時，需要透過上述設定移除不需要的資料
data 的資料

digraph structs {
	node[shape=record]
	struct1 [label="{{?|?|?|?|?|?|?|?}}"];
}

和 read_mask 做 and operation 移除不需要的資料

digraph structs {
	node[shape=record]
	struct2 [label="{{1|1|1|0|0|0|0|0}}"];
}

會得到以下結果，保留需要的資料。

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|0|0|0|0|0}}"];
}

uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];

先設定好目的地的資料，和需要用來清空特定部分 bit 的 mask

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[write_lhs + bitsize];
    *dest++ = (original & mask) | (data >> write_lhs);
}

這裡分成兩個部分，一個是需要橫跨兩個 bytes 的操作，另一個只有在一個 byte 內完成，當 bitsize > write_rhs (＝ write_lhs 的個數) 時，需要進行兩個 bytes 的操作。

*dest++ = (original & mask) | (data >> write_lhs);

這是 data 中的值

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|0|0|0|0|0}}"];
}

藉由移動到 LSB 符合記憶體排序的方式

digraph structs {
	node[shape=record]
	struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}

original 的原始值

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|?|?|?|?|?}}"];
}

mask 的值

digraph structs {
	node[shape=record]
	struct2 [label="{{1|1|1|1|1|0|0|0}}"];
}

透過和 mask 做 bitwise and operation 清空特定的位置，得到下列結果

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|?|?|0|0|0}}"];
}

跟上述位移過的 data 進行合併

digraph structs {
	node[shape=record]
	struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}

做 bitwise or operation

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|?|?|0|0|0}}"];
}

得到下列結果，完成第一個 byte 的複製

digraph structs {
	node[shape=record]
	struct2 [label="{{?|?|?|?|?|<f0>?|?|<f1>?}}"];
    struct3 [label="new data"];
    
    struct3 -> struct2:f0;
    struct3 -> struct2:f1;
}

original = *dest & write_mask[bitsize - write_rhs];

將第二個 byte 需要清空的地方移除，bitsize-write_rhs(=lhs的個數)，是需要放入的個數

*dest = original | (data << write_rhs);

將資料放入到第二個 byte 中，完成橫跨兩個的 bytes 的複製

接下來探討一個 byte 內的複製

mask |= write_mask[write_lhs + bitsize];
*dest++ = (original & mask) | (data >> write_lhs);

原本的 mask 放著要從 lhs 開始清空的位置，但是是直接清空到位置 0 的部分，有機會會額外移除資料，需要透過 write_mask[write_lhs + bitsize] 來設定停止點，write_lhs + bitsize 代表著從 lhs 加上要複製的個數(bitsize) 為停止的位置。最後透過與上述相同的方式複製到目的地中。

count -= bitsize;

減去這次處理 bit 個數，以便迴圈檢查是否完成當初 count 設定需要複製 bit 的個數。

---

## 測驗 `4`