2018q3 Homework3 (review)

# 2018q3 Homework3 (review) ###### tags: `C語言` contributed by < `asd757817` > ## 1. [Week 2 測驗 5](https://hackmd.io/UKpj7o20TLuLqm8t2Erv0g?both#%E6%B8%AC%E9%A9%97-1) 以下程式是合法 C99 程式嗎？ ```C #include <stdio.h> int main() { return (********puts)("Hello"); } ``` 參照 C99 規格書解釋： 6.3.2.1 - 4 :::success A function designator is an expression that has function type. Except when it is the operand of the sizeof operator or the unary & operator, a function designator with type “function returning type” is converted to an expression that has type “pointer to function returning type”. ::: 這邊指出 function designator 在進行 sizeof 運算或者是 & 運算以外都會轉換成一個 pointer to a function 的型態。 6.5.3.2 - 4 :::success The unary * operator denotes indirection. If the operand points to a function, the result is a function designator; if it points to an object, the result is an lvalue designating the object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined. ::: \* 的功用是間接取值，如果取值的對象指向一個 function 則得到的結果為 function designator；而 function designator 除了做 sizeof 跟 & 運算以外，正是指向 function 本身的指標，因此 dereference function designator 一樣是得到 funciton designator。這一行程式碼雖然有許多 \*，但最終都獲得 function designator 來呼叫 puts 函式，因此程式碼合法。繼續思考以下是否合法: ```C #include <stdio.h> int main() { return (**&puts)("Hello"); } ``` 6.5.3.2 - 4 註記 84 :::success Thus, &\*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)). It is always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, \*&E is a function designator or an lvalue equal to E. If \*P is an lvalue and T is the name of an object pointer type, \*(T)P is an lvalue that has a type compatible with that to which T points. ::: 從上述內容可知道 ```*&puts```的結果為 function designator(這個情況不會獲得 lvalue)，接著再對 function designator 取值，結果一樣是獲得 function designator 並呼叫函式，程式碼合法。繼續變形: ```C #include <stdio.h> int main() { return (&**&puts)("Hello"); } ``` 同 6.5.3.2 - 4 註記 84 敘述，```&*puts``` 的結果會是 ```puts``` (也就是 function designator)再進行取值，程式碼合法。 ## 2. [Week 3 測驗 4](https://hackmd.io/UKpj7o20TLuLqm8t2Erv0g?both#%E6%B8%AC%E9%A9%97-1) 考慮以下程式碼，在 little-endian 硬體上，會返回 1，反之，在 big-endian 硬體上會返回 0: ```C int main() { union { int a; char b; } c = { .a = K1 }; return c.b == K2; } ``` 補完上述程式碼。 K1 = ? * `(a)` 0 * `(b)` 1 * `(c)` -1 * `(d)` 254 K2 = ? * `(a)` 0 * `(b)` 1 * `(c)` 254 **解題流程** - union 的功用使 a、b 共用同一個記憶體區段，區段長度以長的一方為主 - int 的大小為 4-byte、char 的大小為 1-byte，在這一題共用 int 的 4-byte - little-endian：從最低位的 byte 開始放入數值 - big-endian：從最高位的 byte 開始放入數值當放入 1 的時候記憶體中的狀態： ``` # little-endian 放入1 的情況 # 會在最低位的 byte 開始填入數值高 0x00 0x00 0x00 0x01 低 # big-endian 放入 1 的情況 # 從最高位的 byte 開始填入數值高 0x01 0x00 0x00 0x00 低 ``` char b 在記憶體中所使用的區域為黃色部分：0x00 0x00 0x00 ==0x00== 因此若 a 有填入數值但 b 的內容等於 0 就表示這個系統是 Big-endian；反之，若系統是 little-endian 則 b 的內容應為 a 填入的數值。在 little-endian 的情況要回傳 True ，因此 K2=K1 且兩者不可等於 0 否則無法判斷；而當 K1 = 254 的時候記憶體狀況為 0x00 0x00 0x00 ==0x11111110==，這個時候 a 的數值為 254 但是 **b 的數值是 -2**，因為 b 的宣告型態為 char 只佔1個 byte 的空間，且是有號數，因此對於 b 而言最高位的 1 表示數值為負數，因此 K1=K2=254 時，不管系統是 little-endian 還是 big-endian 都會回傳 false。 ### 相關程式 Linux 系統輸入指令```lscpu``` 可以查看許多資訊，其中"Byte Order"就可以顯示當前系統是屬於 Big-endian 還是 Little-endian。 Github: [karelzak/util-linux](https://github.com/karelzak/util-linux/blob/master/sys-utils/lscpu.c) lscpu.c ```C #if !defined(WORDS_BIGENDIAN) add_summary_s(tb, _("Byte Order:"), "Little Endian"); #else add_summary_s(tb, _("Byte Order:"), "Big Endian"); #endif ``` 藉由 WORDS_BIGENDIAN 的內容判斷系統的 byte order 參考另一專案 [google/cityhash](https://github.com/google/cityhash/blob/master/config.h.in) 裡面的註解有對 WORDS_BIGENDIAN 進行解釋。 ```C /* Define WORDS_BIGENDIAN to 1 if your processor stores words with the most significant byte first (like Motorola and SPARC, unlike Intel). */ #if defined AC_APPLE_UNIVERSAL_BUILD # if defined __BIG_ENDIAN__ # define WORDS_BIGENDIAN 1 # endif #else # ifndef WORDS_BIGENDIAN # undef WORDS_BIGENDIAN # endif #endif ``` ## 3. [Week 2 測驗 1](https://hackmd.io/UKpj7o20TLuLqm8t2Erv0g?both#%E6%B8%AC%E9%A9%97-1) 考慮到以下程式碼: ```C const char *p; void dont_do_this(void) { const char c_str[] = "This will change"; p = c_str; } ``` 指出存在的問題和提出修正機制，需要用 C99/C11 規格解釋。在 dont_do_this 函式內，指標 p 獲得了 c_str 所在的記憶體位置，但因 c_str 為區域變數，生命週期只在函式內，函式結束後 c_str[] 的生命週期也結束，但 p 仍然指向原先 c_str 的位置，若對 p 取值就是一個未定義行為。 C99 規格書 6.2.4 Storage durations of objects - 2 :::success The lifetime of an object is the portion of program execution during which storage is guaranteed to be reserved for it. An object exists, has a constant address and retains its last-stored value throughout its lifetime ==If an object is referred to outside of its lifetime, the behavior is undefined.== The value of a pointer becomes indeterminate when the object it points to reaches the end of its lifetime. ::: 在規格書中雖然有明確指出這是一個未定義的行為，但值得注意的是：**這樣的程式碼在編譯的過程中是可以正常編譯的(可能有提示訊息)**，但實際上避免程式出現未定義行為的責任在於開發者本身；而對於未定義行為執行的動作會依據編譯器而有所不同，但不管編譯器做了什麼樣的動作都是合理的。相關的 CVE ： ## 4. [Week 3 測驗 3](https://hackmd.io/cCa9LSvQSey1R7XgP47Slg?both#%E6%B8%AC%E9%A9%97-3) 以下程式碼計算 parity bit: ```C= #include <stdint.h> int parity(uint32_t x) x ^= x >> 1; x ^= x >> 2; x = (x & 0x11111111U) * 0x11111111U; return (x >> P) & 1; } ``` P = 28 **原理說明：** 原 x 內各 bit 的 parity 情況為： | 32 | 31 |... |2 |1 | | -------- | -------- | -------- | -------- | -------- | | b32 | b31 | ... |b2 | b1 | bn：表示第 n 位的 parity 情況(1=奇數；0=偶數) 執行第一次 XOR 後，x 內各 bit 的 parity 情況等同於： | 32 | 31 |... |2 |1 | | -------- | -------- | -------- | -------- | -------- | | b32 | b31+b32 | ... |b2+b3 | b1+b2 | 觀察最後一個欄位 b1+b2 ，意思是原本第1位跟第2位相加的情況，因 XOR 運算會符合奇偶相加的情況，如： 1^1=0(奇數+奇數=偶數)、1\^0=1(奇數+偶數=奇數)、0\^0=0(偶數+偶數=偶數) 接著執行第二次 XOR 後，x 內各 bit 的 parity 情況為： | 32 | 31 |30 |29 |... |2 |1 | | -------- | -------- |-----------|--------|-------- | --------- | --------- | | b32 | b31+b32 |b30+b31+b32|b29+b30+b31+b32|... |b2+b3+b4+b5|b1+b2+b3+b4| 正確的 parity 應為： b1+b2+...+b32，所以目標是使第1、5、9、...、29 bit 的內容相加(或做 XOR) 執行 ```x = (x & 0x11111111U) * 0x11111111U;```，觀察第29 bit ``` xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx * 00010001 00010001 00010001 00010001 ---------------------------------------- xxx[x]xxxx xxxxxxxx xxxxxxxx xxxxxxxx 第 29 bit xxxx xxx[x]xxxx xxxxxxxx xxxxxxxx xxxx 第 25 bit xxxxxxxx xxx[x]xxxx xxxxxxxx xxxxxxxx 第 21 bit ... ... ... xxxxxxxx xxxxxxx[x] 第 1 bit ``` 以第29 bit 表示 b1+b2+b3+...+b32 的情形，return 需要取得第29 bit，因此要右移28位。延伸程式碼第5行的概念 ``` x = (x & 0x11111111U) * 0x11111111U;``` 直接獲得各 bit 並進行相加的效率會更高。 ~~SIMD 實作方式尋找中~~ 搜尋了幾份 simd 相關的程式碼，發現主要的概念是以一行指令實現 vector 各位置間的相加，設 v1、v2 都有10個元素，v1 + v2 可以直接完成 v1[0]+v2[0]、v1[1]+v2[1]...，應用 simd 的概念在 parity 檢查上就是一次對多個 bit 進行運算。 :::info :question: 已了解 SIMD 的基本概念，但不知道怎麼將記憶中各 bit 以 SIMD 方式進行運算，若是以支援 SIMD 的 vector 來儲存各 bit 數值，在轉換過程就耗費了許多時間，沒有改善效率。 ::: ## 5. [Week 3 測驗 4](https://hackmd.io/cCa9LSvQSey1R7XgP47Slg?both#%E6%B8%AC%E9%A9%97-4) 考慮以下程式碼: ```C #include <stdlib.h> #include <string.h> typedef struct rec { char *value; struct rec *next; } record; void insert_sorted(record **r, const char *value) { record *newrec = NULL; while (*r && strcmp(value, (*r)->value) > 0) r = &((F1)->next); newrec = malloc(sizeof(record)); newrec->value = F2(value); newrec->next = F3; F4 = newrec; } ``` **正確程式碼** ```C #include <stdlib.h> #include <string.h> typedef struct rec { char *value; struct rec *next; } record; void insert_sorted(record **r, const char *value) { record *newrec = NULL; while (*r && strcmp(value, (*r)->value) > 0) r = &((*r)->next); newrec = malloc(sizeof(record)); newrec->value = strdup(value); newrec->next = *r; *r = newrec; } ``` ### 程式說明： r 為指標的指標，在一呼叫 ```insert_sorted``` 時，r 會指向**指向第一個節點的指標**，如下圖所示。對 r 間接取值(\*r)會得到**指向第一個節點的指標** (下圖的 ptr) ```graphviz digraph linked_list{ node[shape=record] r->prt-> rec1:f0; rec1 [label="<f0> node1|<f1> value|<f2> next"]; rec2 [label="<f0> node2|<f1> value|<f2> next"]; rec3 [label="<f0> node3|<f1> value|<f2> next"]; rec4 [label="<f0> node4|<f1> value|<f2> next"]; rec1:f2 -> rec2:f0; rec2:f2 -> rec3:f0; rec3:f2 -> rec4:f0; } ``` 當 ptr 指到的對象 value 小於要插入的值時，r 必須移動到**指向 node2 的指標** 使得 **```*r = node1->next```** 也就是 r 存放的數值為 **```(*r)->next```** 的 address，程式碼： ```r = &((*r)->next);``` ```graphviz digraph linked_list{ node[shape=record] prt -> rec1:f0; rec1 [label="<f0> node1|<f1> value|<f2> next"]; rec2 [label="<f0> node2|<f1> value|<f2> next"]; rec3 [label="<f0> node3|<f1> value|<f2> next"]; rec4 [label="<f0> node4|<f1> value|<f2> next"]; rec1:f2 -> rec2:f0; rec2:f2 -> rec3:f0; rec3:f2 -> rec4:f0; r -> rec1:f2; } ``` 假設要插入的值位於 node2 跟 node3 間表示 \*r->value 的數值大於要加入的數值，此時 r 的位置如圖，需要將 node2->next 指向 newrec，newrec->next 指向 node3。 ```graphviz digraph linked_list{ node[shape=record] prt -> rec1:f0; rec1 [label="<f0> node1|<f1> value|<f2> next"]; rec2 [label="<f0> node2|<f1> value|<f2> next"]; rec3 [label="<f0> node3|<f1> value|<f2> next"]; rec4 [label="<f0> node4|<f1> value|<f2> next"]; newrec [label="<f0> newrec|<f1> value|<f2> next"]; rec1:f2 -> rec2:f0; rec2:f2 -> rec3:f0; rec3:f2 -> rec4:f0; r -> rec2:f2; } ``` - 先把 node3 指派給 newrec->next * 以 \*r 取得 node3 的位置並指派給 newrec->next ==(此時的 \*r 等於 node->next)== * ```newrec->next = *r``` * ==作為 rvalue 時 \*r 代表的是指標所指向的地址，也就是 node3 的地址== - 接著將 newrec 指派給 node2->next * ```*r = newrec``` * ==\*r 作為 lvalue 時代表的是要被指派數值的地址==，將 newrec 指派給 \*r 也就是 node->next **Insertion node** - 修改函式型態改為 bool，插入成功回傳 True、失敗回傳 False - 若 r 為 NULL 或 value 為 NULL 回傳 false ```C bool insert_sorted(record **r, const char *value){ /* 若 r 為 NULL 或 value 為 NULL 回傳 false */ if(!r | !value){ return false; } else{ record *newrec = NULL; /* 走訪 list 找出新節點的位置 */ while (*r && strcmp(value, (*r)->value) > 0) r = &((*r)->next); newrec = malloc(sizeof(record)); newrec->value = strdup(value); newrec->next = *r; *r = newrec; return true; } } ``` **Insertion 測試** - 建立一指標指向一個空的 list - 依序加入 c,b,a,z,y,x,g,g，依序走訪 list 觀察結果是否為 abcggxyz 新增 show() 函式，顯示 list 內容 ```C void show(record *r){ printf("List: "); while(r){ printf("%s",r->value); r = r->next; } printf("\n"); } ``` 測試程式： - 測試插入節點的 value 為 NULL 時，是否能正確回傳 false - 測試成功插入節點是否會回傳 ture - 檢查 list 結果是否有正確排序 ```C record *r = NULL; printf("======= Insert Test =======\n"); printf("Insert a NULL value tese : "); if(!insert_sorted(&r,NULL)); printf("Pass wrong parameter\n"); printf("Insert a correct case test : "); if(insert_sorted(&r,"c")) printf("insert complete\n"); insert_sorted(&r,"b"); insert_sorted(&r,"a"); insert_sorted(&r,"z"); insert_sorted(&r,"y"); insert_sorted(&r,"x"); insert_sorted(&r,"g"); insert_sorted(&r,"g"); printf("Expect order is: abcggxyz\n"); show(r); } ``` 輸出結果： ```shell $ gcc -o linked_list linked_list.c && ./linked_list ======= Insert Test ======= ======= Insert Test ======= Insert a NULL value tese : Pass wrong parameter Insert a correct case test : insert complete Expect order is: abcggxyz List: abcggxyz ``` ### Search node - 傳入 list 起點和要查詢的 value - 函式回傳的結果為一個 record - 若查詢 value 在 list 內，回傳該節點 (資料型態為 record) - 若傳入的 list 為 NULL 或要查詢的 value 是 NULL，則回傳 NULL - 若查詢的 value 不在 list 內，回傳 NULL ```C record *search_node(record **r, const char *value){ /* 如果傳入的指標為 NULL 直接回傳 NULL 並提醒*/ if(!*r | !value){ return NULL; } else{ /* 走訪節點，若查詢的 value 小於當前節點則往後尋找 */ while(*r && strcmp(value,(*r)->value)>0) r = &((*r)->next); /* 檢查走訪結果是不是符合搜尋目標，是則回傳該節點的指標 */ if(strcmp((*r)->value,value)==0){ return *r; } /* 走訪結果不符合搜尋結果，回傳 NULL 並提醒使用者 */ else{ return NULL; } } } ``` 測試程式：延續先前測試程式，目前 list 內容為：abcggxyz - 新增一個 null list ，測試傳入 NULL list 是否得到 NULL - 測試 value 為 NULL 時是否得到 NULL - 測試成功搜尋是否可以得到該節點(顯示得到的節點的 value) - 測試搜尋目標不在 list 內是否得到 NULL ```C record *null_ptr = NULL; printf("======= Search Test =======\n"); record *search; printf("Search a NULL list tese : "); if(search = search_node(&null_ptr,"b")) printf("%s\n", search->value); else printf("You can't search node in a null list ! \n"); printf("Search a NULL value tese : "); if(search = search_node(&r,NULL)) printf("%s\n", search->value); else printf("You can't search a NULL value !\n"); printf("Correct case test :"); if(search = search_node(&r,"b")) printf("Find %s !!\n", search->value); else printf("Can't find the node \n"); printf("Search a value that is not in the list : "); if(search = search_node(&r,"q")) printf("%s\n", search->value); else printf("Can't find the node \n"); ``` 測試結果： ```shell $ gcc -o linked_list linked_list.c && ./linked_list ======= Search Test ======= Search a NULL list tese : You can't search node in a null list ! Search a NULL value tese : You can't search a NULL value ! Correct case test :Find b !! Search a value that is not in the list : Can't find the node ``` ### Remove node - 函式型態為 bool，刪除成功回傳 true、失敗回傳 false - 傳入 list 起點與要刪除的節點 value - 若 list 起點是 NULL 或 value 是 NULL 則回傳 false - 刪除節點後需要把原本節點配置的空間釋放程式碼 ```C bool remove_node(record **r , const char *value){ /* 若 list 起點是 NULL 或 value 是 NULL 則回傳 false */ if(!*r | !value ){ return false; } else{ /* 走訪 list 尋找要刪除的節點 */ while(*r && strcmp(value,(*r)->value)>0) r = &((*r)->next); /* 檢查是否找到要刪除的節點 */ if(strcmp((*r)->value,value)==0){ record *to_be_removed = *r; *r = (*r)->next; // 修正 list 連接的情況 free(to_be_removed); // 釋放記憶體 return true; } else return false; } } ``` 測試程式 ==延續先前所有測試內容== - 測試從一個 NULL list 刪除節點 - 測試從 list 刪除一個 value 為 NULL 的節點 - 測試可以正確刪除時是否回傳 ture - 測試 value 不在 list 中是否會回傳 false - 顯示 list 內容 ```C printf("\n======= Remove Test =======\n"); printf("Remove node from a NULL list : "); if(remove_node(&null_ptr,"a")) printf("Remove node completed !\n"); else printf("Can not remove node from a NULL list !\n"); printf("Remove NULL value test :"); if(remove_node(&r,NULL)) printf("Remove node completed !\n"); else printf("Can not remove NULL value !\n"); printf("Remove a correct case : "); if(remove_node(&r,"b")) printf("Remove node completed !\n"); else printf("Remove node failed !\n"); printf("Remove a value that is not in list : "); if(remove_node(&r,"q")) printf("Can not remove a value that is not in the list !\n"); else printf("Removed node completed !\n"); show(r); printf("Remove \"a\" from list\n"); remove_node(&r,"a"); show(r); ``` 測試結果 ```shell $ gcc -o linked_list linked_list.c && ./linked_list ======= Remove Test ======= Remove node from a NULL list : Can not remove node from a NULL list ! Remove NULL value test :Can not remove NULL value ! Remove a correct case : Remove node completed ! Remove a value that is not in list : Removed node completed ! List: acggxyz Remove "a" from list List: cggxyz ``` 以 AddressSanitizer 觀察 remove 是否有正確釋放記憶體將上述程式```remove(&r,"a")```一行註解後記憶體配置的情況的 ```shell $ gcc -o linked_list linked_list.c -fsanitize=address -g && ./linked_list ...中間省略... SUMMARY: AddressSanitizer: 128 byte(s) leaked in 15 allocation(s). ``` 上述程式呼叫 ```remove(&r,"a")``` 後的記憶體配置情況 ```shell $ gcc -o linked_list linked_list.c -fsanitize=address -g && ./linked_list ...中間省略... SUMMARY: AddressSanitizer: 112 byte(s) leaked in 14 allocation(s). ``` 可以發現配置出的空間減少了一個，表示 remove 有正確釋放記憶體。完整測試結果 ```shell ======= Insert Test ======= Insert a NULL value tese : Pass wrong parameter Insert a correct case test : insert complete Expect order is: abcggxyz List: abcggxyz ======= Search Test ======= Search a NULL list tese : You can't search node in a null list ! Search a NULL value tese : You can't search a NULL value ! Correct case test :Find b !! Search a value that is not in the list : Can't find the node ======= Remove Test ======= Remove node from a NULL list : Can not remove node from a NULL list ! Remove NULL value test :Can not remove NULL value ! Remove a correct case : Remove node completed ! Remove a value that is not in list : Removed node completed ! List: acggxyz Remove "a" from list List: cggxyz ``` 補充： - 在程式中我規定節點的 value 不得為 NULL，不過實際上為 NULL 也可以。

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.