Try   HackMD

2021q1 Homework2 (quiz2)

contributed by < Chialiang86 >

Todo

  • 重寫測驗和解說
    • 測驗 1
    • 測驗 2
    • 測驗 3
    • 測驗 4

重寫測驗

測驗 1

  • 此題目的內容首先仿效 Linux 核心 include/linux/list.h 的精簡實作,設計了一套可以方便使用環狀 doubly-linked list 的介面;此外,從此作為基礎延伸出 merge sort 的實做。
  • 由以下的程式碼不難看出, merge sort 的充分使用了 divide-and-conquer 的特性。
  • Divide : 使用 list_cut_position 搭配 get_middle 函數藉由找出 list 中間點來將 list 切成左右兩部份,而從 list_cut_position 的參數 (parameter) 可看出 nodelist_head 型態,而 get_middle 的回傳值型態為 list_ele_t * ,因此 MMM 代換為 &get_middle(&q->list)->list
  • Conquer : 藉由遞迴呼叫 list_merge_sort 來分別將剛剛切出的左右兩 list 進行排序。
  • Combine : 把左右兩邊排序完的 list 進行合併,成為更長的一個排序好的 list 。
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 函數

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 ,而 nodehead_from 此環狀 list 依據 get_middle 算出的中間點。







G



head_to

head_to

 



head_to:c->head_to:h












G



head_from

head_from

 



node1

head_from_first

 



head_from:c->node1






node2

node

 



node1:c->node2






node3

 

 



node2:c->node3






p0




p0:n->head_from





p4




p0:s->p4:s




node3:c->p4:n





2.head_from->next 指派為 node->next ;再把 head_from->next->prev 指派為 head_from







G



head_from

head_from

 



node3

 

 



head_from:c->node3






head_to

head_to

 



head_to->head_to:e






node1

head_from_first

 



node2

node

 



node1:c->node2






node2:c->node3






p0




p0:n->head_from





p4




p0:s->p4:s




node3:c->p4:n





3. head_to->prev 指派為 node,node->next 指派為 head_to, 再把 head_to->next 指派為 head_from_first,head_to->next->prev 指派為 head_to

  • 此動作順利將環狀 list 分為兩個小環狀 list。






G



head_from

head_from

 



node3

 

 



head_from:c->node3






head_to

head_to

 



node1

head_from_first

 



head_to:c->node1






node2

node

 



node1:c->node2






p14




node2:c->p14





p0




p0:n->head_from





p4




p0:s->p4:s




p10




p10:n->head_to





p10:s->p14:s




node3:c->p4:n





探討 get_middle 函數

  • 此函數主要的目的在於找到實做 merge sort 的 list 之中間點。
  • 其中 list_for_each 為一個 function-liked macro ,主要是簡化走訪整個 list 的過程。
#define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next)
  • 考慮 lowfast 兩變數,可看見 slow 每次執行完一輪會變為 slow->next ;但 fast 會變成 fast->next->next ,由其變數命名可知一個移動的較慢,另一個較快,主要目的是利用當 fast 到達起始點時, slow 到達 list 的中間位置,並將中間位置的指標藉由 list_entry 找出並回傳。
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); }
#define list_entry(node, type, member) container_of(node, type, member)
  • 其中 list_entry 是由 container_of 這個 macro 來實現

考慮 container_of 的定義:

#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 中對 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) 當作範例
typedef struct __element {
    char *value;
    struct __element *next;
    struct list_head list;
} list_ele_t;
  • slowlist_head 型態的指標, listlist_ele_t 其中一個成員的名稱(可以想成 slow 即為 list_ele_tlist 成員的實體),結果回傳 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 成員的相對記憶體位置,不但精簡了程式碼提高了可讀性,也省去了計算相對位置所使用的時間。
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 功能。
struct list_head *q = q_new();
  • 關鍵的 q_insert_head 函數,以下程式碼第 17 行可以看到,lsit_ele_t * 型態的新節點 newh 被強制轉形成 struct list_head * 加到 q->next 中,雖然兩者型態不同,但因為指向的是同一塊記憶體空間,因此省去許多計算相對位置,或額外設計 struct 來操作記憶體空間的成本。
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 * 才能正確釋放記憶體。
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 的函數更改
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
void print(struct list_head *head) { struct list_head* tmp; list_for_each (tmp, head) printf(" %s", ((list_ele_t*)tmp)->value); }
  • main 修改
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)
 ..............
 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 的冪)
  • 實作程式碼如下
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 為 : 0b0010001110001101
    • N |= N >> 1: 0b0011001111001111
    • N |= N >> 2: 0b0011111111111111
    • N |= N >> 4: 0b0011111111001111
    • N |= N >> 8: 0b0011111111111111
    • (N + 1) : 0b01000000000000000
    • (N + 1) >> 1 : 0b00100000000000000
  • 可見函數是利用 2 進制的 MSB 來進行 Bitwise 操作,忽略 MSB 以下的值,藉由關鍵的 MSB 並善用 >>| 運算子來將 MSB 以後的值都變成 1 ,再 +1 進位到產生"大於 N 之最大的二的冪"並右移一位來得到答案。
  • 換句話說,若最後不進行右移的動作,函數即便成了回傳大於 N 之最小的二的冪。

測驗 3

  • 題目所實做的為一個逐 bit 複製 data 給目標的函式,因為牽涉到 bitwise 的操作,因此要熟練 c 語言對於 bitwise 操作如 |,&,>>,<<,bitmask 或數字的二進制表示法等,並了解函數操作其中的意義。
  • 以下程式碼擷取自題目的 bitcpy 函數:
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

      ​​​​​​​​data=source++; /* (*source) = 0b00101110 */
      
    • 上述程式碼執行之後的狀況

    
    
    
    
    
    
    %0
    
    
    
    data
    data
    
    
    
    value
    
    00101110
    
    
    
    data->value
    
    
    
    
    
    source
    source
    
    
    
    value2
    
    10111100
    
    
    
    source->value2
    
    
    
    
    
    value->value2
    
    
    
    
    
    node5
    
    ...
    
    
    
    value2->node5
    
    
    
    
    
    src
    _src
    
    
    
    node1
    
    ...
    
    
    
    src->node1
    
    
    
    
    
    node2
    
    ...
    
    
    
    node1->node2
    
    
    
    
    
    node3
    
    ...
    
    
    
    node2->node3
    
    
    
    
    
    node3->value
    
    
    
    
    
    node6
    
    ...
    
    
    
    node5->node6
    
    
    
    
    
    node7
    
    ...
    
    
    
    node6->node7
    
    
    
    
    
    
    • 偏移量 read_lhs, read_rhsdata 的表示:
    
    
    
    
    
    
    G
    
    
    
    read_lhs
    read_lhs=3
    
    
    
    value
    
    001
    
    01110
    
    
    
    read_lhs->value:l
    
    
    
    
    
    read_rhs
    read_rhs=5
    
    
    
    read_rhs->value:r
    
    
    
    
    
    source
    source
    
    
    
    value2
    
    10111100
    
    
    
    source->value2
    
    
    
    
    
    data
    data
    
    
    
    data->value:w
    
    
    
    
    
    
    • 先觀察第 4~8 行 if 的敘述,若 read_lhs > 0 ,則必須從 byte 由左往右數第 read_lhs + 1 個 bit 開始讀取,相當於是先把 data 左移 read_lhs 個 bit。
    
    
    
    
    
    
    G
    
    
    
    data
    data
    
    
    
    valuer
    
    01110   000
    
    
    
    data->valuer:n
    
    
    
    
    
    read_lhs
    read_lhs=3
    
    
    
    valuel
    
    001
    
    
    
    read_lhs->valuel
    
    
    
    
    
    read_rhs
    read_rhs=5
    
    
    
    read_rhs->valuer
    
    
    
    
    
    valuel->valuer
    
    
    
    
    source
    source
    
    
    
    value2
    
    10111100
    
    
    
    source->value2
    
    
    
    
    
    
    • 因為 read_rhs 代表 byte 中右邊的 bit 數,因此若 bitsize > read_rhs,則此回合會跨 byte 讀取資料至 data,因此要借用剛剛 source++ 後的位址,進行 data |= (*source >> read_rhs)
    
    
    
    
    
    
    G
    
    
    
    data
    data
    
    
    
    valuer
    
    01110   000
    
    
    
    data->valuer
    
    
    
    
    
    read_rhs
    read_rhs=5
    
    
    
    value3
    
    11100  000
    
    
    
    read_rhs->value3
    
    
    
    
    
    oreq
    |=
    
    
    
    valuer->oreq
    
    
    
    
    
    source
    source
    
    
    
    value2
    
    00000  101
    
    
    
    source->value2
    
    
    
    
    
    value2->value3
    
    
    
    
    
    oreq->value2
    
    
    
    
    
    
    
    
    
    
    
    
    g
    
    
    
    data
    data
    
    
    
    value
    
    01110 101
    
    
    
    data->value
    
    
    
    
    
    
    • 最後再依據 bitsizeread_mask 來將要複製的 bit 進行 & 運算

      • 假設 bitsize = 7
      
      
      
      
      
      
      G
      
      
      
      data
      data
      
      
      
      valuer
      
      01110   101
      
      
      
      data->valuer
      
      
      
      
      
      read_mask
      read_mask[7]
      
      
      
      valuemask
      
      11111110
      
      
      
      read_mask->valuemask
      
      
      
      
      
      and
      &=
      
      
      
      valuer->and
      
      
      
      
      
      and->valuemask
      
      
      
      
      
      
      
      
      
      
      
      
      g
      
      
      
      data
      data
      
      
      
      value
      
      0111010   0
      
      
      
      data->value
      
      
      
      
      
      
      • data 結果變為 01110100
    • 類似的原理,觀察 13 到 24 行

      ​​​​​​​​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 (此時指向左半邊的 byte),例如 mask = 0b11111000 , original & mask 相當於先將 original 所指向的 byte 的右邊 3 個 bits 做清空的動作,因為會跨 byte 寫入,因此清空的 3 個 bit 之後會被寫入的資料取代。
        
        
        
        
        
        
        G
        
        
        
        left
        original
        
        
        
        l
        
        xxxxxxxx
        
        
        
        left->l
        
        
        
        
        
        right
        mask
        
        
        
        r
        
        11111000
        
        
        
        right->r
        
        
        
        
        
        result
        res 1
        
        
        
        res
        
        xxxxx000
        
        
        
        result->res
        
        
        
        
        
        op
        &
        
        
        
        l->op
        
        
        
        
        
        r1
        )
        
        
        
        r->r1
        
        
        
        
        
        op->r
        
        
        
        
        
        eq
        =
        
        
        
        eq->res
        
        
        
        
        
        l1
        (
        
        
        
        l1->l
        
        
        
        
        
        r1->eq
        
        
        
        
        
        
        
        
        
        
        
        
        G
        
        
        
        left
        data
        
        
        
        l
        
        01101100
        
        
        
        left->l
        
        
        
        
        
        right
        right_lhs
        
        
        
        r
        5
        
        
        
        right->r
        
        
        
        
        
        result
        res 2
        
        
        
        res
        
        00000011
        
        
        
        result->res
        
        
        
        
        
        op
        >>
        
        
        
        l->op
        
        
        
        
        
        r1
        )
        
        
        
        r->r1
        
        
        
        
        
        op->r
        
        
        
        
        
        eq
        =
        
        
        
        eq->res
        
        
        
        
        
        l1
        (
        
        
        
        l1->l
        
        
        
        
        
        r1->eq
        
        
        
        
        
        
        
        
        
        
        
        
        G
        
        
        
        left
        res 1
        
        
        
        l
        
        xxxxx000
        
        
        
        left->l
        
        
        
        
        
        right
        res 2
        
        
        
        r
        
        00000011
        
        
        
        right->r
        
        
        
        
        
        result
        dest
        
        
        
        res
        
        xxxxx011
        
        
        
        result->res
        
        
        
        
        
        op
        &
        
        
        
        l->op
        
        
        
        
        
        r1
        )
        
        
        
        r->r1
        
        
        
        
        
        op->r
        
        
        
        
        
        eq
        =
        
        
        
        eq->res
        
        
        
        
        
        l1
        (
        
        
        
        l1->l
        
        
        
        
        
        r1->eq
        
        
        
        
        
        
        • original = *dest & write_mask[bitsize - write_rhs] 為先將 dest (此時指向右半邊的 byte) 左邊進行清空的動作。例如 write_rhs=3; bitsize=7 代表 dest 左邊兩個 bit 會被寫入(因為左邊 byte 中右邊 3 個 bits 被寫入, 7 - 3 = 4 剩下 4 bit 給右邊 byte)。
        
        
        
        
        
        
        G
        
        
        
        dest
        dest
        
        
        
        ori
        
        xxxxxxxx
        
        
        
        dest->ori
        
        
        
        
        
        write_mask
        write_mask
        
        
        
        msk
        
        00001111
        
        
        
        write_mask->msk
        
        
        
        
        
        original
        original
        
        
        
        res
        
        0000xxxx
        
        
        
        original->res
        
        
        
        
        
        and
        &
        
        
        
        ori->and
        
        
        
        
        
        r1
        )
        
        
        
        msk->r1
        
        
        
        
        
        and->msk
        
        
        
        
        
        eq
        =
        
        
        
        eq->res
        
        
        
        
        
        l1
        (
        
        
        
        l1->ori
        
        
        
        
        
        r1->eq
        
        
        
        
        
        
        • *dest = original | (data << write_rhs) 這行是將 data 複製到 dest 中,由於 data 的左邊 write_lhs 個 bit 已複製完成,故現在把剩下的 bit 資料複製給 dest
        
        
        
        
        
        
        G
        
        
        
        original
        original
        
        
        
        ori
        
        0000xxxx
        
        
        
        original->ori
        
        
        
        
        
        data
        data
        
        
        
        dat
        
        01101100
        
        
        
        data->dat
        
        
        
        
        
        result
        dest(+ 1 過後)
        
        
        
        res
        
        0110xxxx
        
        
        
        result->res
        
        
        
        
        
        write_rhs
        write_rhs
        
        
        
        srl
        3
        
        
        
        write_rhs->srl
        
        
        
        
        
        and
        &
        
        
        
        ori->and
        
        
        
        
        
        sr
        <<
        
        
        
        dat->sr
        
        
        
        
        
        r1
        )
        
        
        
        srl->r1
        
        
        
        
        
        l2
        (
        
        
        
        and->l2
        
        
        
        
        
        sr->srl
        
        
        
        
        
        eq
        =
        
        
        
        eq->res
        
        
        
        
        
        l1
        (
        
        
        
        l1->ori
        
        
        
        
        
        r2
        )
        
        
        
        r1->r2
        
        
        
        
        
        l2->dat
        
        
        
        
        
        r2->eq
        
        
        
        
        
        
        • 結果如下
        
        
        
        
        
        
        g
        
        
        
        destptr
        
        _dest
        
        
        
        node1
        
        ...
        
        
        
        destptr->node1
        
        
        
        
        
        dest1
        dest
        
        
        
        d1
        
        xxxxx011
        
        
        
        dest1->d1
        
        
        
        
        
        dest2
        dest(+ 1 過後)
        
        
        
        d2
        
        0110xxxx
        
        
        
        dest2->d2
        
        
        
        
        
        d1->d2
        
        
        
        
        node4
        
        ...
        
        
        
        d2->node4
        
        
        
        
        node2
        
        ...
        
        
        
        node1->node2
        
        
        
        
        node3
        
        ...
        
        
        
        node2->node3
        
        
        
        
        node3->d1
        
        
        
        
        node5
        
        ...
        
        
        
        node4->node5
        
        
        
        
        node6
        
        ...
        
        
        
        node5->node6
        
        
        
        
        
      • 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