D06: c-review - HackMD

# D06: c-review contributed by < `e94046165` > ## [第 4 週測驗題](https://hackmd.io/s/SyK-WApKM) ### 測驗 `1` 首先分別解出 FuncA、B、C 的功能： ##### 1. FuncA 功能 ```C= void FuncA(struct node **start, int value) { if (!*start) { struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = new_node->prev = new_node; *start = new_node; return; } struct node *last = (*start)->prev; struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = *start; (*start)->prev = new_node; new_node->prev = last; last->next = new_node; } ``` If 處理的是當串列為空的時候的動作，因此直接跳到第九行進行觀察，可以看到使用了 *last 指向 *start 的前一個，也就是最後一個節點。而 new_node 插入的位置可由 new_node->next = *start 判斷出是串列末端。13~15行就是處理因應在串列末端插入節點改變的指標。 Ans: `(e)` 建立新節點，內容是 `value`，並安插在結尾 ##### 2. FuncB 功能 ```C= void FuncB(struct node **start, int value) { struct node *last = (*start)->prev; struct node *new_node = malloc(sizeof(struct node)); new_node->data = value; new_node->next = *start; new_node->prev = last; last->next = (*start)->prev = new_node; *start = new_node; } ``` FuncB 乍看之下跟 FuncA 的功能很像，但是它沒有處理 *start 為空的情況，因此很直覺的認為它包含了決定開頭的功能。第八行正好驗證了這個直覺。 Ans: `(d)` 建立新節點，內容是 `value`，並安插在開頭 ##### 3. FuncC 功能 ```C= void FuncC(struct node **start, int value1, int value2) { struct node *new_node = malloc(sizeof(struct node)); new_node->data = value1; struct node *temp = *start; while (temp->data != value2) temp = temp->next; struct node *next = temp->next; temp->next = new_node; new_node->prev = temp; new_node->next = next; next->prev = new_node; } ``` 這個函式除了指派給 new_node->data 的 value1 外還多了一個參數 value2，5、6 行用來在串列中找出 data == value2 的 Node。找到之後第八行 temp->next = new_node 也就是將新的節點插入到 data == value2 的節點之後。 Ans: `(e)` 找到節點內容為 `value2` 的節點，並在之後插入新節點，內容為 `value1` 但這個 Function 沒有防呆機制，也就是沒有考慮串列中沒有 data == value2 的情況，當此情況發生時，while 迴圈將沒辦法達到終止條件 ##### 4. Traversal in forward direction 輸出結果 ```C= void display(struct node *start) { struct node *temp = start; printf("Traversal in forward direction \n"); for (; temp->next != start; temp = temp->next) printf("%d ", temp->data); printf("%d ", temp->data); printf("\nTraversal in reverse direction \n"); struct node *last = start->prev; for (temp = last; temp->prev != last; temp = temp->prev) printf("%d ", temp->data); printf("%d ", temp->data); printf("\n"); } int main() { struct node *start = NULL; FuncA(&start, 51); FuncB(&start, 48); FuncA(&start, 72); FuncA(&start, 86); FuncC(&start, 63, 51); display(start); return 0; } ``` main() 中執行了五次插入，最後形成的串列為 48->51->63->72->86 Traversal in forward direction 做的事情是： ```C for (; temp->next != start; temp = temp->next) printf("%d ", temp->data); ``` 從 start 往後走訪串列並輸出，直到走訪到最後一個節點為止（temp->next == start）因此依序輸出 48 51 63 72 86 ##### 5. Traversal in reverse direction 輸出結果 ```C for (temp = last; temp->prev != last; temp = temp->prev) printf("%d ", temp->data); ``` 從 last 往前走訪串列並輸出，直到走訪到第一個節點為止（temp->prev == last）輸出結果： 86 72 63 51 48 ### 測驗 `2` ##### 1. `FuncX` 的功能 ```C= int FuncX(struct node *head, int *data) { struct node *node; for (node = head->next; node && node != head; node = node->next) data++; return node - head; } ``` for 迴圈的的初始值令 node = head 的下一個，終止條件則為 node = head 或 node = node->next 為 NULL，每一次都會執行 data++ 的敘述，但由於 data 只有 call by value 所以不論在此 Funcx 裡對 data 做什麼操作，從 FuncX 看到的都還是原本的 data 的初始值 0。(第一次作答的時候被騙了....直到看到最後那題答案的選項沒有足夠大的值才發現) 最後是 FuncX 的回傳值 return node - head 在 for 遇到的終止條件是 node = NULL 的時候回傳值是非`0` 而當遇到的終止條件是 node = head 時，回傳值則是 `0`因此 FuncX 可以用來判斷串列是否為環狀串列。 Ans: (e) 判斷是否為 circular linked list，若為 circular 則回傳 0，其他非零值 p.s. 沒有計算走訪的節點數的功能。接著進入 main() 裡頭觀察串列建立與判斷是否為環狀： ```C= int main() { int count = 0; struct node *head = node_new(0); head->next = node_new(1); head->next->next = node_new(2); head->next->next->next = node_new(3); head->next->next->next->next = node_new(4); printf("K1 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next->next->next->next = head; printf("K2 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next->next->next->next->next = head->next; printf("K3 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); head->next = head->next->next->next->next->next->next->next->next; printf("K4 >> %s\n", FuncX(head, &count) ? "Yes" : "No"); printf("K5 >> %d\n", head->next->data); printf("count >> %d\n", count); return 0; } ``` 上列 3~7 行建立一個如下的串列 ``` 3 0 4 0->1 5 0->1->2 6 0->1->2->3 7 0->1->2->3->4 ``` 上面的數字是每個結點的 data 值，0 是 head 的 data 值，此時的串列並非環狀，因此第 8 行 FuncX(head, &count) 的回傳值是非 0 所以結果是 K1 = Yes ```C= head->next->next->next->next = head; ``` 第九行將本來第四個 node (head為第一個)的 next 指標指向 head 至此串列變成 ``` ->0->1->2->3- |___________| ``` 現在再跑一次 FuncX ，由於輸入的串列是環狀串列，所以回傳值 = 0 ，K1 = No 下兩行敘述： ```C= head->next->next->next->next->next = head->next; printf("K3 >> %s\\n", FuncX(head, &count) ? "Yes" : "No"); ``` 延續剛剛的結果 head->next->next->next->next = head 因此（head->next->next->next->next)->next = head->next 等同於 head->next = head->next 也就是說串列沒有做任何改變，K3 = No ```C= head->next = head->next->next->next->next->next->next->next->next; printf("K4 >> %s\\n", FuncX(head, &count) ? "Yes" : "No"); printf("K5 >> %d\\n", head->next->data); ``` 因為 head = (head->next->next->next->next)->next->next->next->next 所以上面第1行敘述等同於 head->next = head 至此串列剩下一個指向自己的 head ，仍舊是 circular list 而 data 值 = 0，也就是 K4 = No , K5 =0 最後是 count，因為在 FuncX 裡是 call by value 不是 call by reference 所以 count 仍等於初始值 0。 ## [第 5 週測驗題 (上)](https://hackmd.io/s/SynmEVIqG) ### 測驗 `1` 考慮以下程式碼，推敲其作用 (選出最符合行為的描述) ```clike uint8_t Func32(uint32_t x) { return x ? Func32(x >> 1) - 1 : 32; } ``` 將 `Func32` 改寫為以下功能等價的程式碼: ```C= uint8_t FuncI(uint32_t x) { if (!x) return 32; int n = 1; if (!(x >> 16)) { n += 16; x <<= 16; } if (!(x >> M1)) { n += 8; x <<= 8; } if (!(x >> M2)) { n += 4; x <<= 4; } if (!(x >> M3)) { n += 2; x <<= 2; } n = n - (x >> 31); return n; } ``` ##### 1. `Func32` 的功能 Func32 會不斷的 recursive call 自己，並且每一次都將參數 x 向右 shift 一位，直到 x = 0 則會回傳 32。最後傳回的值為 32 - 遞迴呼叫的次數 -1，遞迴呼叫的次數又取決於 x 向右 shift 幾次會等於 0，也就是最高位的 `1` 所在的 bit 數+1，可以決定出這個 function 的功能是計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 32 ##### 2. M1、M2、M3=? 在解此題的時候參考了 [rex662624](https://hackmd.io/xeUp2C6_R_OpDQgeiI5Kxg?view) 的共筆，他提到只要加上 if(x>>31==1)retrun 0 就可以刪除第九行的 n = n - (x >> 31); 一開始我也以為這行只是處理開頭沒有 0 的情況，但是發現只是這樣的話這個函式根本無法回傳偶數的 n。這題第一次在作答的時候是代入邊界值來取得 M1、M2、M3 的值，但這其實是偷吃步，要是這串 code 實際上跑不出正確的結果或是有什麼陷阱應該很容易 GG 所以這次試著從頭理解這串程式碼的觀念：首先確定所有情況(開頭有0~32)個 0 的情況都被妥善考慮，當 x = 0 時由第3行的 if 判斷式成立回傳 32 開頭有 1 個 0 所有 if 判斷式均不成立 n = 1 ==>M1,M2,M3<31 2 個 0 第八行的 if 判斷式必須成立(才可能使 n = 2) ==>M3 = 30 ... 如此推下去可以得出 M1 = 24, M2 = 28, M3 = 30; ### 測驗 `2` ##### Func64 的作用為？ ```C= union u_qword { struct { uint32_t low; uint32_t high; } dwords; uint64_t qword; }; static inline int Func64(uint64_t val) { uint32_t lo = (uint32_t) val; uint32_t hi = (uint32_t) (val >> 32); return hi ? Func32(hi) : 32 + Func32(lo); } ``` 這題相對來說挺簡單的，先將一個 64 bits 的數拆成 hi = 左邊的 32 bits，與 lo = 右邊 32 bits，若 hi 不為零就不用考慮 lo 為何，只要 return Func32(hi) 就好，當 hi == 0 表示開頭的 32 個位元全為 0，return 32 + Func32(lo) 如此一來便能計算開頭有幾個 0 Ans: (c) 計算輸入數值 x 的二進位表示中，回傳開頭 (從高位到低位元) 有幾個 0，倘若 x 為 0x0，則輸出 64 ##### do_udiv32 的作用為？ ```C= static int do_udiv32(uint32_t dividend, uint32_t divisor, struct udiv_result *res) { /* Ensure dividend is always greater than or equal to the divisor. */ uint32_t mask = Func32(divisor) - Func32(dividend); divisor <<= mask; /* align divisor */ mask = 1U << mask; /* align dividend */ do { if (dividend >= divisor) { dividend -= divisor; res->q.dwords.low |= mask; } divisor >>= 1; } while ((P1) && dividend); res->r.dwords.low = dividend; return 0; } ``` 首先，由函式名稱 do_udiv32 與 argument dividend, divisor 等等可猜出這是一個除法的 function。那麼它是採取什麼樣的方式呢？稍微瀏覽了一下，發現這與我之前作除法的想法有些相似[第2周作業](https://hackmd.io/s5qyemoWSUKynwvIUFOcog)==>不斷將被除數與除數對齊並相減，細看程式碼可以發現一開始 mask = 除數與被除數 Leading 1 相差的位數，在利用 mask 將 divisor 與 dividend 對齊後(第 8 行) mask = 1U << mask 之後用來控制商數的位數。之後的 while 迴圈內的動作是： ``` 11 若 dividend > divisor : 12 dividend 減去 divisor 13 將原來的商數加上對應位元的`1` 15 divisor right shift 一位直到商數夠長 or dividend==0(被整除)為止 ``` 最後將餘數儲存所以 P1 應為 mask>>=1 理解了 do_udiv32 後繼續往下到 udiv64 ```C= int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res) { uint64_t mask; uint64_t bits; res->q.qword = res->r.qword = 0; if (divisor == 0) { /* division by 0 ? */ res->q.qword = 0xffffffffffffffffull; return -1; } if (divisor == dividend) { res->q.qword = 1; return 0; } if (divisor > dividend) { res->r.qword = dividend; return 0; } /* only 32 bit operands that the preconditions are fulfilled. */ if (!(divisor >> 32) && !(dividend >> 32)) return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res); bits = Func64(divisor) - Func64(dividend); divisor <<= bits; /* align divisor and dividend */ mask = 1ULL << bits; /* division loop */ do { if (dividend >= divisor) { dividend -= divisor; res->q.qword |= mask; } divisor >>= 1; mask >>= 1; } while ((P2) && dividend); res->r.qword = dividend; return 0; } ``` 這個 function 與 do_udiv32 的概念基本上一樣，只是拓展成 64 位元版本並加上一些 do_udiv32 沒有的偵錯敘述，如第 7 行防止除以 0 的判斷式、第 22 行若除數被除數皆小於等於 32 位元就丟給 do_udiv32 做。還有，udiv64 除了 mask 以外還宣告了新的變數 bits 來紀錄商數的位數，並以它作為終止 while 迴圈的條件，也就是P2 = bits-\- 。這部份與 32 位元版本的想法其實一樣，但是可讀性變高了(一個變數如果擔任太多角色會令可讀性變低，我第一次作答是看得霧煞煞啦...) 最後來到 main() ```C= int main() { char digitbuff[20]; char *pos = digitbuff + sizeof(digitbuff); union u_qword v; /* current value */ union u_qword nv; /* next value */ struct udiv_result d; int64_t value = 0xCAFEBABE; /* Java classfile magic number */ v.qword = (unsigned long long) value; while (v.dwords.high != 0) { /* process 64 bit value as long as needed */ /* determine digits from right to left */ udiv64(v.qword, 10, &d); *--pos = d.r.dwords.low + P3; v.qword = d.q.qword; } do { /* process 32 bit (or reduced 64 bit) value */ nv.dwords.low = v.dwords.low / P4; *--pos = (v.dwords.low - (10 * nv.dwords.low)) + P5; } while ((v.dwords.low = nv.dwords.low) != 0); int len = digitbuff + sizeof(digitbuff) - pos; char *p = pos; while (len--) putchar(*p++); printf("\n"); return 0; } ``` 首先是 P3 和 P5，看了其他人的共筆，發現這兩個數是為了讓後來的 putchar 可以輸出正確的數字。當 P3 = P5 = 48 (ASCII 0)可以使數字輸出正確，但是答案給的是 0x31 也就是 49。本來以為是自己哪裡想錯了，但是實際上跑過發現似乎是答案給錯了？ ``` //P3 = P5 = 48 root@acnes-X550JX:~#./div 3405691582 //P3 = P5 = 49 root@acnes-X550JX:~#gcc -o div div.c root@acnes-X550JX:~#./div 45167:2693 ``` 可以看到當 P3 = P5 = 49 時，輸出的字元超出了數字的範圍，而出現了 ":"，所以可以斷定P3 = P5 = 0x30 才對 ## [第 5 週測驗題 (中)](https://hackmd.io/s/HkQjgqI5G) ### 測驗 `1` 已知在 x86_64 架構，以下程式碼的執行輸出是 jserv++C: ```C= #include <stdio.h> int main() { puts((char *) &(double []){ 3823806048287157.0, 96 }); } ``` 一開始先試著理解這段又短又奇妙的東西，從這一段程式碼不難猜出這是將一個設計好的 double 強制轉型成字串 char* 這串 double 用二進位表示是： ``` 01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010 ``` 又 sizeof(char) = 1 bytes 所以會將這 64 個 bits 拆成 8 個 8 bits 的字元來讀取，查了 ASCII 表後可以發現上列了數字依序代表了 C+\+vresj，但這是 big-endian 的規則下的輸出，在 little-endian 下則會是 jserv+\+C。有了上面的概念之後再來考慮以下程式碼，假設 puts 函式總是可正確運作，那麼程式輸出為何？ ```C= #include <stdio.h> double m[] = { 3823806048287157.0, 96 }; void gen() { if (m[1]--) { m[0] *= 2; gen(); } else puts((char *) m); } int main() { gen(); return 0; } ``` 可以看到 gen 是個遞迴呼叫的 function，最終將本來的 double *2^96^，那麼這串新的 double 再用 (char\*)強制轉型會輸出什麼呢？這牽涉到 IEEE 754 所規範的浮點數表示法，當一個浮點數乘上 2^n^ 實際上只有表示 exponent 的 bits 會更動而已，以下是經過計算之後的數 0**1001001 0010**1011 00101011 01110110 01110010 01100101 01110011 01101010 粗體的部份為改變的位元，查 ASCII 表可得到新的字串為： jserv++I ### 延伸題目 #### 修改程式，允許輸出你的 GitHub 帳號名稱我的 id 為 e94046165 ，因為超過 8 個字元，由上述的論述可以知道，一個 double 因為只有 64 bits 所以強迫轉型成 char* 時最多只能表示 8 個字元。因此必須把 id 拆成兩個 double 來表示。但在與 [blake11235](https://hackmd.io/s/Hy9pIxk2M) 討論的時候發現了一些問題：若用 double 表示 8 個字元的字串，在 printf 輸出的時候可能因未讀到 "\0" 而使輸出結果出錯，下面為例子： ```clike int main(){ double x[] = {1.17767461839090865360653786975E-47 }; double y[] = {2.6185479229586066841358146022E-322 }; printf("%s", (char *) x); printf("%s", (char *) y); printf("\n"); return 0; } ``` 其中 double x 以二進位表示為 00110110 00110001 00110110 00110100 00110000 00110100 00111001 01100101 由高位往低位元每 8 bits 輸出為 6164049e 其中 double y 則是 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00110101 由高位往低位元每 8 bits 輸出為 NULL....NULL 5 接著 Printf 以 little endian 規則讀取並輸出的話應該會得到 e94046165 但以下為輸出結果： ``` e9404616�@5 ``` 在兩個輸出之間出現了不屬於兩個 double 裡的資料，這代表了兩件事： 1.x 與 y 的記憶體位置不連續 2.printf 因為沒有讀到 NULL 所以輸出超過 x 所涵蓋的記憶體範圍以下驗證這兩個想法：首先是先分別 printf 出 x 與 y 的記憶體位置 ```C int main(){ double x[] = {1.17767461839090865360653786975E-47 }; double y[] = {2.6185479229586066841358146022E-322 }; printf("&x =%p\n", &x); printf("&y =%p\n", &y); printf("%s", (char *) x); printf("%s", (char *) y); printf("\n"); return 0; } ``` 輸出結果： ``` root@acnes-X550JX:~/tests#./aaaa &x =0x7ffc54823830 &y =0x7ffc54823840 e9404616�@5 ``` 果然，可以看到兩者差了 8 bytes(x 的結尾到 y 的開頭之間) 然後試著加入以下程式碼，一個一個 bytes 印出字元： ```C p = &x; for(i=0; i<24; i++){ printf("%p ", p); putchar(*p++); printf("\n"); } ``` 結果 ``` &x =0x7ffe6a4dd5d0 &y =0x7ffe6a4dd5e0 e9404616�@5 0x7ffe6a4dd5d0 e 0x7ffe6a4dd5d1 9 0x7ffe6a4dd5d2 4 0x7ffe6a4dd5d3 0 0x7ffe6a4dd5d4 4 0x7ffe6a4dd5d5 6 0x7ffe6a4dd5d6 1 0x7ffe6a4dd5d7 6 0x7ffe6a4dd5d8 � 0x7ffe6a4dd5d9 0x7ffe6a4dd5da @ 0x7ffe6a4dd5db 0x7ffe6a4dd5dc 0x7ffe6a4dd5dd 0x7ffe6a4dd5de 0x7ffe6a4dd5df 0x7ffe6a4dd5e0 5 0x7ffe6a4dd5e1 0x7ffe6a4dd5e2 0x7ffe6a4dd5e3 0x7ffe6a4dd5e4 0x7ffe6a4dd5e5 0x7ffe6a4dd5e6 0x7ffe6a4dd5e7 ``` 在印出 x 的時候居然印了不在 x 記憶體空間裡的東西 (註：0x7ffe6a4dd5d9 裡有一個亂碼，無法複製貼上但該記憶體位置不為空) 那麼該如何解決呢？只要使 x 與 y 記憶體位置相連就行了： ```C int main(){ double x[] = {1.17767461839090865360653786975E-47,2.6185479229586066841358146022E-322 }; printf("%s", (char *) x); printf("\n"); return 0; } ``` ``` root@acnes-X550JX:~/tests#./aaaa e94046165 ``` 那為什麼範例沒有遇到這個問題呢？ ```C char *p; int main(){ double x[]= { 3823806048287157.0, 96 }; puts((char *) &x); printf("\n"); p = &x; for(i=0; i<15; i++){ printf("%p ", p); putchar(*p++); printf("\n"); } return 0; } ``` 稍微修改 code 讓它 printf 出整個 array 裡的 data: 輸出 ``` jserv++C 0x7ffceeeb2380 j 0x7ffceeeb2381 s 0x7ffceeeb2382 e 0x7ffceeeb2383 r 0x7ffceeeb2384 v 0x7ffceeeb2385 + 0x7ffceeeb2386 + 0x7ffceeeb2387 C 0x7ffceeeb2388 0x7ffceeeb2389 0x7ffceeeb238a 0x7ffceeeb238b 0x7ffceeeb238c 0x7ffceeeb238d 0x7ffceeeb238e X ``` 可以看到因為 array 中第二個值為 96 所以前 7 個 bytes 皆為零(ASCII 96 = X)，而在puts 的時候 puts 出最後一個字元(C)就遇到了 NULL 因此不會繼續 puts 出其他不該出現的結果。不知道這部份是不是在撰寫程式碼的時候就考慮到的，不過就此看來如果對不同的 datatype 做強制轉型，而不考慮其他 function 的運作機制的話，可能會有不堪設想的後果。 ## [第 5 週測驗題 (下)](https://hackmd.io/s/Sk30MXDqM) 計組太爛。。。。。先緩緩

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.