---
tags: Linux
---
# 2021q1 Homework2 (quiz2)
contributed by < `Chialiang86` >
## Todo
- [ ] 重寫測驗和解說
- [x] 測驗 1
- [x] 測驗 2
- [x] 測驗 3
- [ ] 測驗 4
## 重寫測驗
### 測驗 1
- 此題目的內容首先仿效 Linux 核心 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的精簡實作，設計了一套可以方便使用環狀 doubly-linked list 的介面；此外，從此作為基礎延伸出 merge sort 的實做。
- 由以下的程式碼不難看出， merge sort 的充分使用了 [divide-and-conquer](https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm) 的特性。
- **Divide** : 使用 `list_cut_position` 搭配 `get_middle` 函數藉由找出 list 中間點來將 list 切成左右兩部份，而從 list_cut_position 的參數 (parameter) 可看出 `node` 為 `list_head` 型態，而 `get_middle` 的回傳值型態為 `list_ele_t *` ，因此 `MMM` 代換為 `&get_middle(&q->list)->list` 。
- **Conquer** : 藉由遞迴呼叫 `list_merge_sort` 來分別將剛剛切出的左右兩 list 進行排序。
- **Combine** : 把左右兩邊排序完的 list 進行合併，成為更長的一個排序好的 list 。
```c=
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 /*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);
}
```
#### 探討 `list_cut_position` 函數
```c=
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
/* 1 */
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;
}
/* 2 */
head_from->next = node->next;
head_from->next->prev = head_from;
/* 3 */
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
- 以下圖示說明實做細節，程式碼中的註解對應了圖示順序。
**1.** 先將 `head_from_first` 指派為 `head_from->next` ，而 `node` 為 `head_from` 此環狀 list 依據 `get_middle` 算出的中間點。
``` graphviz
digraph G {
rankdir = LR
edge [arrowhead=normal, dir=both]
head_to [shape=record, label="{<h> head_to |<ptr>}"]
head_to:ptr:c->head_to:h
}
```
``` graphviz
digraph G {
rankdir = LR
node [shape=record, label="{<h> |<ptr>}"]
edge [arrowhead=normal, dir=both]
head_from [shape=record, label="{<h> head_from |<ptr>}"]
node1 [label="{<h>head_from_first |<ptr>}"]
node2 [label="{<h> node|<ptr>}"]
{node[shape=point height=0] p0 p4} // make p0 and p4 to small to see
p0:n -> head_from[arrowtail=none]
head_from:ptr:c -> node1
node1:ptr:c->node2
node2:ptr:c->node3
node3:ptr:c->p4:n[arrowhead=none]
p0:s -> p4:s[dir=none]
}
```
**2.** 將 `head_from->next` 指派為 `node->next` ；再把 `head_from->next->prev` 指派為 `head_from` 。
``` graphviz
digraph G {
rankdir = LR
node [shape=record, label="{<h> |<ptr>}"]
edge [arrowhead=normal, dir=both]
head_from [shape=record, label="{<h> head_from |<ptr>}"]
head_to [shape=record, label="{<h> head_to |<ptr>}"]
node1 [label="{<h>head_from_first |<ptr>}"]
node2 [label="{<h> node|<ptr>}"]
head_to->head_to:e
p0 [shape=point,height=0]
p4 [shape=point,color=none]
p0:n -> head_from[arrowtail=none]
head_from:ptr:c -> node3
node1:ptr:c->node2
node2:ptr:c->node3
node3:ptr:c->p4:n[arrowhead=none]
p0:s -> p4:s[dir=none]
}
```
**3.** `head_to->prev` 指派為 `node`,`node->next` 指派為 `head_to`, 再把 `head_to->next` 指派為 `head_from_first`,`head_to->next->prev` 指派為 `head_to` 。
- 此動作順利將環狀 list 分為兩個小環狀 list。
``` graphviz
digraph G {
rankdir = LR
node [shape=record, label="{<h> |<ptr>}"]
edge [arrowhead=normal, dir=both]
head_from [shape=record, label="{<h> head_from |<ptr>}"]
head_to [shape=record, label="{<h> head_to |<ptr>}"]
node1 [label="{<h>head_from_first |<ptr>}"]
node2 [label="{<h> node|<ptr>}"]
p0 [shape=point,height=0]
p4 [shape=point,color=none]
p10 [shape=point,height=0]
p14 [shape=point,color=none]
head_to:ptr:c->node1
node1:ptr:c->node2
node2:ptr:c->p14[arrowhead=none]
p10:s->p14:s[dir=none]
p10:n->head_to[arrowtail=none]
head_from:ptr:c -> node3
node3:ptr:c->p4:n[arrowhead=none]
p0:s -> p4:s[dir=none]
p0:n -> head_from[arrowtail=none]
}
```
#### 探討 `get_middle` 函數
- 此函數主要的目的在於找到實做 merge sort 的 list 之中間點。
- 其中 `list_for_each` 為一個 [function-liked macro](https://gcc.gnu.org/onlinedocs/cpp/Function-like-Macros.html#Function-like-Macros) ，主要是簡化走訪整個 list 的過程。
```c=
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
- 考慮 `low` 和 `fast` 兩變數，可看見 `slow` 每次執行完一輪會變為 `slow->next` ；但 `fast` 會變成 `fast->next->next` ，由其變數命名可知一個移動的較慢，另一個較快，主要目的是利用當 `fast` 到達起始點時， `slow` 到達 list 的中間位置，並將中間位置的指標藉由 `list_entry` 找出並回傳。
```c=
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 /*COND1*/ || fast->next->next == list /*COND2*/)
break;
fast = fast->next->next;
}
return list_entry(slow /*TTT*/, list_ele_t, list);
}
```
```c=
#define list_entry(node, type, member) container_of(node, type, member)
```
- 其中 `list_entry` 是由 `container_of` 這個 macro 來實現
#### 考慮 `container_of` 的定義：
```c=
#ifndef container_of
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#endif
```
- 首先探討 container_of 中的 `__extension__`
- `typeof` 關鍵字為 GNU C extension，並非 c 原始的標準。
- 而 `__typeof__` 為 alternate keyword ，根據 [gcc.gnu.org](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html) 中對 alternate keyword 的解釋 :
> -ansi and the various -std options disable certain keywords. This causes trouble when you want to use GNU C extensions, or a general-purpose header file that should be usable by all programs, including ISO C programs. The keywords asm, typeof and inline are not available in programs compiled with -ansi or -std
- 在 gcc 引數 (argument) 指定 `-ansi` 或 `-std` 時，某些關鍵字如 `typeof` , `asm`, `inline` 是無法編譯的，解決辦法是在關鍵字頭尾加上 `__` (用 `__typeof__` 代替 `typeof`) ，即 alternate keyword
- 然而 gcc 某些 option 如 `-pedantic` 會造成使用 GNU C extensions 產生 warning 的狀況，可以在 `__typeof__` 之前加上 `__extension__` 來避免。
- 可見主要功能為傳回 `struct` 中成員所在記憶體空間的起始位址（即 struct 的起始位址）
- 以 `container_of(slow, list_ele_t, list)` 當作範例
```c
typedef struct __element {
char *value;
struct __element *next;
struct list_head list;
} list_ele_t;
```
- `slow` 為 `list_head` 型態的指標， `list` 為 `list_ele_t` 其中一個成員的名稱（可以想成 `slow` 即為 `list_ele_t` 中 `list` 成員的實體），結果回傳 `slow` 所在的 `list_ele_t` 記憶體起始位置。
#### 改寫程式碼
- 經過觀察可以發現， `struct list_head` 已經具有完整 circular doubly-linked list 的結構，只要加上一個存放字串 (value) 的欄位即可時做出 list merge sort 。
- 以下的 `list_ele_t` 擴充了原有的 `struct list_head` 結構，主要是加上了可以存字串的 `value` 欄位
- 實作上我們直接省略 queue_t 這個結構（因為 `list_ele_t` 已經足夠去實做 list sort ），並且把 `list_ele_t` 中的 `struct list_head list` 放到第一個欄位，這樣有一個非常大的好處是，如果要進行走訪 list 的動作，只要直接把 `list_ele_t *` 強制轉型成 `struct list_head *` 即可，因為兩個指標指向的是同一塊記憶體位址，不需要用 `contain_of` 這個 `macro` 來計算 `list` 成員的相對記憶體位置，不但精簡了程式碼提高了可讀性，也省去了計算相對位置所使用的時間。
```c=
typedef struct __element {
struct list_head list;
char *value;
} list_ele_t;
```
- `q` 的型態改變成 `struct list_head *`，其實整個 `q` 的 list 只有 `q` 自己是真正屬於 `struct list_head *` ，其他的節點是有 `value` 成員的 `list_ele_t *`，因此 `q` 本身可以算是一個 dummy node ，只有指向 list 功能。
```c=
struct list_head *q = q_new();
```
- 關鍵的 `q_insert_head` 函數，以下程式碼第 17 行可以看到，`lsit_ele_t *` 型態的新節點 `newh` 被強制轉形成 `struct list_head *` 加到 `q->next` 中，雖然兩者型態不同，但因為指向的是同一塊記憶體空間，因此省去許多計算相對位置，或額外設計 struct 來操作記憶體空間的成本。
```c=
bool q_insert_head(struct list_head *q, char *s)
{
// modify
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;
list_add_tail((struct list_head *)newh, q->next);
return true;
}
```
- `q_free` 函數更改如下，傳進去的 type 雖然為 `struct list_head *` ，但走訪整條 list 要先轉型成 `list_ele_t *` 才能正確釋放記憶體。
```c=
static void q_free(struct list_head *q)
{
// modify
if (!q) return;
struct list_head *current = q->next;
while (current != q) {
struct list_head *tmp = current;
current = current->next;
free(((list_ele_t*)tmp)->value);
free(tmp);
}
}
```
- sort 的函數更改
```c=
static struct list_head *get_middle(struct list_head *list)
{
struct list_head *fast = list, *slow;
list_for_each (slow, list) {
if (fast->next != list || fast->next->next != list)
break;
fast = fast->next->next;
}
return slow;
}
static void list_merge(struct list_head *lhs,
struct list_head *rhs,
struct list_head *head)
{
INIT_LIST_HEAD(head);
while (!list_empty(lhs) && !list_empty(rhs)) {
char *lv = ((list_ele_t *)lhs->next)->value;
char *rv = ((list_ele_t *)rhs->next)->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(struct list_head *q)
{
if (list_is_singular(q))
return;
struct list_head left;
struct list_head sorted;
INIT_LIST_HEAD(&left);
list_cut_position(&left, q, get_middle(q));
list_merge_sort(&left);
list_merge_sort(q);
list_merge(&left, q, &sorted);
INIT_LIST_HEAD(q);
list_splice_tail(&sorted, q);
}
```
- 另外撰寫 `print` 函數來印出完整的 list
```c=
void print(struct list_head *head)
{
struct list_head* tmp;
list_for_each (tmp, head)
printf(" %s", ((list_ele_t*)tmp)->value);
}
```
- `main` 修改
```c=
int main(void)
{
FILE *fp = fopen("cities.txt", "r");
if (!fp) {
perror("failed to open cities.txt");
exit(EXIT_FAILURE);
}
struct list_head *q = q_new();
char buf[256];
while (fgets(buf, 256, fp))
q_insert_head(q, buf);
fclose(fp);
print(q);
list_merge_sort(q);
assert(validate(q));
print(q);
q_free(q);
return 0;
}
```
- 執行 `gcc -o q1 q1.c` 結果 (input 為 cities.txt)
```shell
..............
Burnopfield, United Kingdom
Novonikolayevka, Ukraine
Yertsevo, Russia
Apango, Guerrero, Mexico
Weggis, Switzerland
Bammatyurt, Russia
Buray, Philippines
Uggiate-Trevano, Italy
Saint-Pantaléon-de-Larche, France
..............
Yāşīd, Palestinian Territory
Zaamslag, Netherlands
Zabeltitz, Germany
Zaberfeld, Germany
Zabierzów Bocheński, Poland
Zabok, Croatia
Zabolotovka, Russia
Zaborze, Poland
Zabrušany, Czech Republic
Zabrzeg, Poland
Zabór, Poland
Zabłocie, Poland
Zabłudów, Poland
Zachenberg, Germany
Zacualpan, México, Mexico
Zadelsdorf, Germany
..............
```
### 測驗 2
- 函式 func 接受一個 16 位元無號整數 N，並回傳小於或等於 N 的 power-of-2 (漢字可寫作為 2 的冪)
- 實作程式碼如下
```c=
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;
}
```
#### 思考函數的意義
- 例如 `N` 為 30(0b11110) 或 20(0b10100)，為求小於等於 `N` 之二的冪，答案皆為 16(0b10000) ，觀察發現其實函數的輸出只跟 `N` 的二進制之 MSB(most signicant bit) 有關，輸入的值二進制最左邊的 1 才是關鍵。
- 思路：關注二進制最左邊的 1，其他的 1 視為 don't care
- 設輸入 `N` 為 : 0b00<font color=red>1</font>0001110001101
- `N |= N >> 1`: 0b00<font color=red>11</font>001111001111
- `N |= N >> 2`: 0b00<font color=red>1111</font>1111111111
- `N |= N >> 4`: 0b00<font color=red>11111111</font>001111
- `N |= N >> 8`: 0b00<font color=red>11111111111111</font>
- `(N + 1)` : 0b0<font color=red>1</font>000000000000000
- `(N + 1) >> 1` : 0b00<font color=red>1</font>00000000000000
- 可見函數是利用 2 進制的 MSB 來進行 Bitwise 操作，忽略 MSB 以下的值，藉由關鍵的 MSB 並善用 `>>` 和 `|` 運算子來將 MSB 以後的值都變成 1 ，再 +1 進位到產生"大於 `N` 之最大的二的冪"並右移一位來得到答案。
- 換句話說，若最後不進行右移的動作，函數即便成了回傳大於 `N` 之最小的二的冪。
### 測驗 3
- 題目所實做的為一個逐 bit 複製 data 給目標的函式，因為牽涉到 bitwise 的操作，因此要熟練 c 語言對於 bitwise 操作如 `|`,`&`,`>>`,`<<`,bitmask 或數字的二進制表示法等，並了解函數操作其中的意義。
- 以下程式碼擷取自題目的 `bitcpy` 函數：
```c=
while (count > 0) {
uint8_t data = *source++;
size_t bitsize = (count > 8) ? 8 : count;
if (read_lhs > 0) {
data <<= read_lhs /*RRR*/;
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] /*DDD*/;
*dest++ = (original & mask) | (data >> write_lhs);
}
count -= bitsize;
}
```
- 由程式碼可觀察出 `count` 為總共要複製的 bit 數，而 `bitsize` 為 while 迴圈進行一輪所複製的 bit 數 (bitsize <= 8)，而 `data` 為一個從 `_src` 複製的 buffer ，經過偏移量的處理，要把正確的資料複製給 `dest`， 大小為一個 byte。
- `read_lhs`(`write_lhs`) 和 `read_rhs`(`write_rhs`) 主要是操作從一個 byte 的角度處理 bit-offset 的變數，因為記憶體是以 byte 當作單位，因此 bit level 需要充分善用 c 中 bitwise 的特性，也是 `bitcpy` 最關鍵的變數之一。
- `read_lhs` 為 byte 中的左偏移量； `read_rhs` 為右偏移量，兩者相加為 8 (1 byte 為 8 bits)。
- 假設 `source` 指標所指的 byte 的值為 00101110, `read_lhs=3` , `read_rhs=5`
```c
data=source++; /* (*source) = 0b00101110 */
```
- 上述程式碼執行之後的狀況
```graphviz
digraph {
rankdir=BT
data [shape=plaintext, label="data"]
source [shape=plaintext, label="source"]
value [shape=box, label="00101110"]
value2 [shape=box, label="10111100"]
src [shape=plaintext, label="_src"]
node [shape=box, label="..."]
{
rank=same
src -> node1 -> node2 -> node3 -> value -> value2 -> node5 -> node6 -> node7
}
data->value[color=red]
source->value2[color=red]
}
```
- 偏移量 `read_lhs`, `read_rhs` 對 `data` 的表示：
```graphviz
digraph G{
rankdir=BT
read_lhs [shape=plaintext, label="read_lhs=3"]
read_rhs [shape=plaintext, label="read_rhs=5"]
source [shape=plaintext, label="source"]
value2 [shape=box, label="10111100"]
{
rank=LR
source->value2[color=red]
}
value [shape=record, style=dashed, label="<l>001|<r>01110"]
data [shape=plaintext]
data -> value:w[color=red]
read_lhs -> value:l
read_rhs -> value:r
}
```
- 先觀察第 4~8 行 if 的敘述，若 `read_lhs > 0` ，則必須從 byte 由左往右數第 read_lhs + 1 個 bit 開始讀取，相當於是先把 `data` 左移 `read_lhs` 個 bit。
```graphviz
digraph G{
rankdir=BT
data [shape=plaintext]
read_lhs [shape=plaintext, label="read_lhs=3"]
read_rhs [shape=plaintext, label="read_rhs=5"]
valuel [shape=box, fontcolor=red, style=dashed, label="001"]
valuer [shape=box, style=dashed, label="01110 000"]
source [shape=plaintext, label="source"]
value2 [shape=box, label="10111100"]
{
rank=LR
source->value2[color=red]
}
{
data -> valuer:n[color=red]
rank = same
valuel -> valuer[dir=none]
}
read_lhs -> valuel
read_rhs -> valuer
}
```
- 因為 `read_rhs` 代表 byte 中右邊的 bit 數，因此若 `bitsize` > `read_rhs`，則此回合會跨 byte 讀取資料至 `data`，因此要借用剛剛 `source++` 後的位址，進行 `data |= (*source >> read_rhs)`
```graphviz
digraph G{
rankdir=BT
data [shape=plaintext]
read_rhs [shape=plaintext, label="read_rhs=5"]
valuer [shape=box, style=dashed, label="01110 000"]
source [shape=plaintext, label="source"]
value2 [shape=box, label="00000 101"]
value3 [shape=box, label="11100 000"]
oreq [shape=plaintext, label="|="]
{
rank=LR
}
{
rank = same
valuer -> oreq[color=none]
oreq -> value2[color=none]
value2->value3
}
data -> valuer[color=red]
source -> value2[color=red]
read_rhs -> value3
}
```
```graphviz
digraph g{
data [shape=plaintext, label="data"]
value [shape=box, label="01110 101"]
data -> value[color=red]
}
```
- 最後再依據 `bitsize` 和 `read_mask` 來將要複製的 bit 進行 `&` 運算
- 假設 `bitsize = 7`
``` graphviz
digraph G{
rankdir=BT
data [shape=plaintext]
read_mask [shape=plaintext, label="read_mask[7]"]
valuer [shape=box, label="01110 101"]
valuemask [shape=box, label="11111110"]
and [shape=plaintext, label="&="]
{
rank = same
valuer -> and[color=none]
and -> valuemask[color=none]
}
data -> valuer[color=red]
read_mask -> valuemask
}
```
```graphviz
digraph g{
data [shape=plaintext, label="data"]
value [shape=box, label="0111010 0"]
data -> value[color=red]
}
```
- `data` 結果變為 0111010<font color="red">0</font>
- 類似的原理，觀察 13 到 24 行
```c
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] /*DDD*/;
*dest++ = (original & mask) | (data >> write_lhs);
}
```
- 以下假設 `write_lhs=5`, `write_rhs=3`, `bitsize=7`, `data=01101100`
- `if` 區塊的程式碼主要適用於要跨兩個 byte 把資料寫入 `dest` 中
- 其中`(original & mask) | (data >> write_lhs)` 這段程式碼是將 `data` 中的資料寫入 `dest` <font color=red>(此時指向左半邊的 byte)</font>，例如 mask = 0b11111000 ， `original & mask` 相當於先將 `original` 所指向的 byte 的右邊 3 個 bits 做清空的動作，因為會跨 byte 寫入，因此清空的 3 個 bit 之後會被寫入的資料取代。
``` graphviz
digraph G{
rankdir=BT
left [shape=plaintext, label="original"]
right [shape=plaintext, label="mask"]
result [shape=plaintext, label="res 1"]
l [shape=box, label="xxxxxxxx"]
r [shape=box, label="11111000"]
res [shape=box, label="xxxxx000"]
op [shape=plaintext, label="&"]
eq [shape=plaintext, label="="]
l1 [shape=plaintext, label="("]
r1 [shape=plaintext, label=")"]
{
rank = same
l1 -> l[color=none]
l -> op[color=none]
op -> r[color=none]
r -> r1 [color=none]
r1 -> eq [color=none]
eq -> res [color=none]
}
left -> l
right -> r
result -> res
}
```
``` graphviz
digraph G{
rankdir=BT
left [shape=plaintext, label="data"]
right [shape=plaintext, label="right_lhs"]
result [shape=plaintext, label="res 2"]
l [shape=box, label="01101100"]
r [shape=plaintext, label="5"]
res [shape=box, label="00000011"]
op [shape=plaintext, label=">>"]
eq [shape=plaintext, label="="]
l1 [shape=plaintext, label="("]
r1 [shape=plaintext, label=")"]
{
rank = same
l1 -> l[color=none]
l -> op[color=none]
op -> r[color=none]
r -> r1 [color=none]
r1 -> eq [color=none]
eq -> res [color=none]
}
left -> l
right -> r
result -> res
}
```
``` graphviz
digraph G{
rankdir=BT
left [shape=plaintext, label="res 1"]
right [shape=plaintext, label="res 2"]
result [shape=plaintext, label="dest"]
l [shape=box, label="xxxxx000"]
r [shape=box, label="00000011"]
res [shape=box, label="xxxxx011"]
op [shape=plaintext, label="&"]
eq [shape=plaintext, label="="]
l1 [shape=plaintext, label="("]
r1 [shape=plaintext, label=")"]
{
rank = same
l1 -> l[color=none]
l -> op[color=none]
op -> r[color=none]
r -> r1 [color=none]
r1 -> eq [color=none]
eq -> res [color=none]
}
left -> l
right -> r
result -> res
}
```
- 而 `original = *dest & write_mask[bitsize - write_rhs]` 為先將 `dest` <font color=red>(此時指向右半邊的 byte)</font> 左邊進行清空的動作。例如 `write_rhs=3`; `bitsize=7` 代表 `dest` 左邊兩個 bit 會被寫入（因為左邊 byte 中右邊 3 個 bits 被寫入， 7 - 3 = 4 剩下 4 bit 給右邊 byte）。
``` graphviz
digraph G{
rankdir=BT
dest [shape=plaintext]
write_mask [shape=plaintext]
original [shape=plaintext]
ori [shape=box, label="xxxxxxxx"]
msk [shape=box, label="00001111"]
res [shape=box, label="0000xxxx"]
and [shape=plaintext, label="&"]
eq [shape=plaintext, label="="]
l1 [shape=plaintext, label="("]
r1 [shape=plaintext, label=")"]
{
rank = same
l1 -> ori[color=none]
ori -> and[color=none]
and -> msk[color=none]
msk -> r1 [color=none]
r1 -> eq [color=none]
eq -> res [color=none]
}
dest -> ori
write_mask -> msk
original -> res
}
```
- `*dest = original | (data << write_rhs)` 這行是將 data 複製到 `dest` 中，由於 `data` 的左邊 `write_lhs` 個 bit 已複製完成，故現在把剩下的 bit 資料複製給 `dest` 。
``` graphviz
digraph G{
rankdir=BT
original [shape=plaintext]
data [shape=plaintext]
result [shape=plaintext, label="dest(+ 1 過後)"]
write_rhs [shape=plaintext]
ori [shape=box, label="0000xxxx"]
dat [shape=box, label="01101100"]
srl [shape=plaintext, label="3"]
res [shape=box, label="0110xxxx"]
and [shape=plaintext, label="&"]
sr [shape=plaintext, label="<<"]
eq [shape=plaintext, label="="]
l1 [shape=plaintext, label="("]
r1 [shape=plaintext, label=")"]
l2 [shape=plaintext, label="("]
r2 [shape=plaintext, label=")"]
{
rank = same
l1 -> ori[color=none]
ori -> and[color=none]
and -> l2
l2 -> dat [color=none]
dat -> sr [color=none]
sr -> srl [color=none]
srl -> r1 [color=none]
r1 -> r2 [color=none]
r2 -> eq [color=none]
eq -> res [color=none]
}
original -> ori
data -> dat
write_rhs -> srl
result -> res
}
```
- 結果如下
```graphviz
digraph g{
rankdir=BT
destptr [shape=box, label="_dest"]
node [shape=box, label="..."]
dest1 [shape=plaintext, label="dest"]
dest2 [shape=plaintext, label="dest(+ 1 過後)"]
d1 [shape=box, label="xxxxx011"]
d2 [shape=box, label="0110xxxx"]
{
rank = same
destptr -> node1
node1 -> node2 -> node3 -> d1 -> d2 -> node4 -> node5 -> node6[dir=none]
}
dest1 -> d1
dest2 -> d2
}
```
- `else` 區塊成處理是處理未跨 byte 資料寫入至 `dest`
- `mask |= write_mask[write_lhs + bitsize]` 的目的為將 `dest` 左邊及右邊不需要被寫入的 bit 保留，如 `wrtie_lhs = 5`,`mask` 原先為 `0b11111000`, `bitsize = 2`, 操作後 `mask ＝ 0b11111001`， 這個 `mask` 在下一行和 `original` 做 `&` 運算，代表 original 只有第 6, 7 兩個會被寫入的 bit 位置被 mask 清空，而把清空過的 `original` 和 `(data >> write_lhs)` （即右移 `write_lhs` 個 bit 的資料）進行 `|` 運算，成功把資料複製進 `dest` 中。
### 測驗 4
Sign in with Wallet
Connect another wallet