owned this note
owned this note
Published
Linked with GitHub
# 2021q1 Homework2 (quiz2)
contributed by < `yellow-hank` >
###### tags: `LinuxKernel`
## 測驗 `1`
```cpp
#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 是在分割時，進行排序，合併時直接將排序好的合併。
```cpp
INIT_LIST_HEAD(&left.list);
```
上述會先初始化一個 double linked list
```cpp
list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list);
```
示意圖
```graphviz
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` 分割後部分
```graphviz
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 分割部分
```graphviz
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`
```cpp
get_middle(&q->list)
```
初始化 fast 指向下一個 node， slow 指向 list 的開頭
```graphviz
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 移動兩個節點
```graphviz
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 移動兩個節點
```graphviz
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 的中間點。
```graphviz
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 。
```cpp
list_merge_sort(&left);
list_merge_sort(q);
```
再一次呼叫 merge sort 排序 &left 和 q 。
```cpp
list_merge(&left.list, &q->list, &sorted);
```
此函式會合併 `&left.list` 和 `&q->list`，並且將結果存入 sorted
下圖會舉例由小排到大
```graphviz
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;
}
```
```graphviz
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 裡面
```graphviz
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。
```cpp
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
```cpp
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，
```graphviz
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 寫法如下：
```cpp
N |= 1 << k; //set kth position to 1
```
因為最大為 16 bits，可以逐一設定 k 以下的值為 1 ，直接引用 N 中位元為 1 ，且位置最高的當作 set bit bitwise operation 的 1 。需要考慮最高位元為 16 ，所以你可以這樣寫：
```cpp
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 的目標，下列是效率較好的程式碼：
```cpp
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
```
做完結果如下：
```graphviz
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
}
```
```cpp
(N + 1) >> 1;
```
N + 1 後結果如下：
```graphviz
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
}
```
往右位移一位
```graphviz
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` 實作程式碼:
```cpp
#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;
}
}
```
### 解釋原理
```cpp
size_t read_lhs = _read & 7;
```
一個 byte 有 8 個 bits ，需要從 _read 中得到從第幾個 byte 第幾個 bit 開始讀取。
```cpp=
_read / 8;
```
上述可以獲得在第幾個 byte
```cpp=
_read % 8;
```
上述可以獲得在第幾個 bit，上述的方式可以是改寫成更有效率的方式，因為 8 是 2 的 3 次方，所以可以藉由 bitwise operation 中的 and operation 獲得最低的 3 個 bit，得到下列的方式實作。
```cpp=
_read & 7;
```
```graphviz
digraph structs {
node[shape=record]
struct1 [label="{{?|?|?|?|?|?|?|?}}"];
}
```
做 and operation
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{0|0|0|0|0|1|1|1}}"];
}
```
會得到以下結果，跟取餘數是一樣。
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}
```
接下來移動 source 到要存取的 byte 中，如下列程式碼
```cpp
const uint8_t *source = (const uint8_t *) _src + (_read / 8);
```
write 的部分使用跟上述 read 一樣的方式移動到要寫入的 bit 位置
```cpp
size_t write_lhs = _write & 7;
size_t write_rhs = 8 - write_lhs;
uint8_t *dest = (uint8_t *) _dest + (_write / 8);
```
下列為設定要一次從最高位取走幾個 bit 的 mask。
```cpp
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。
```cpp
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 的複製
```cpp
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;
}
```
記憶體排序是根據下圖所示
```cpp
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 的部分。
```graphviz
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;
}
```
```cpp
if (bitsize < 8)
data &= read_mask[bitsize];
```
如果單次取的 bit 個數少於 8 時，需要透過上述設定移除不需要的資料
data 的資料
```graphviz
digraph structs {
node[shape=record]
struct1 [label="{{?|?|?|?|?|?|?|?}}"];
}
```
和 read_mask 做 and operation 移除不需要的資料
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{1|1|1|0|0|0|0|0}}"];
}
```
會得到以下結果，保留需要的資料。
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|0|0|0|0|0}}"];
}
```
```cpp
uint8_t original = *dest;
uint8_t mask = read_mask[write_lhs];
```
先設定好目的地的資料，和需要用來清空特定部分 bit 的 mask
```cpp
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 的操作。
```cpp
*dest++ = (original & mask) | (data >> write_lhs);
```
這是 data 中的值
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|0|0|0|0|0}}"];
}
```
藉由移動到 LSB 符合記憶體排序的方式
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}
```
original 的原始值
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|?|?|?|?|?}}"];
}
```
mask 的值
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{1|1|1|1|1|0|0|0}}"];
}
```
透過和 mask 做 bitwise and operation 清空特定的位置，得到下列結果
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|?|?|0|0|0}}"];
}
```
跟上述位移過的 data 進行合併
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{0|0|0|0|0|?|?|?}}"];
}
```
做 bitwise or operation
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|?|?|0|0|0}}"];
}
```
得到下列結果，完成第一個 byte 的複製
```graphviz
digraph structs {
node[shape=record]
struct2 [label="{{?|?|?|?|?|<f0>?|?|<f1>?}}"];
struct3 [label="new data"];
struct3 -> struct2:f0;
struct3 -> struct2:f1;
}
```
```cpp
original = *dest & write_mask[bitsize - write_rhs];
```
將第二個 byte 需要清空的地方移除，bitsize-write_rhs(=lhs的個數)，是需要放入的個數
```cpp
*dest = original | (data << write_rhs);
```
將資料放入到第二個 byte 中，完成橫跨兩個的 bytes 的複製
接下來探討一個 byte 內的複製
```cpp
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) 為停止的位置。最後透過與上述相同的方式複製到目的地中。
```cpp
count -= bitsize;
```
減去這次處理 bit 個數，以便迴圈檢查是否完成當初 count 設定需要複製 bit 的個數。
---
## 測驗 `4`
Sign in with Wallet
