2018q3 Homework3 (review)

# 2018q3 Homework3 (review) contributed by < `kevin110604` > ###### tags: `2018q3` ## 第 1 週測驗 1 ### 題目考慮以下程式碼: ```C int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); } int main() { int x = 3, y = 5; return my_xor(x, y); } ``` `my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算，其中 OP1, OP2, OP3, OP4 都是 operator，請補完實作。 ==作答區== OP1 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP2 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP3 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP4 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * ### 想法 & 思考 | x | y | x ⊕ y | | -------- | -------- | -------- | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | XOR 運算是當輸入 x, y 不一樣的時候（一個為 0 一個為 1 ）輸出為 1 。 OR 運算只要輸入有一個 1 輸出就是 1 ，所以只要相對應的 bit 至少有一個 1 ，程式碼 `(x | y)` 就會把該 bit 變成 1 。因為我們的輸出目標是找到 x, y 不一樣的那些 bit ，然後把它們變成 1 ，所以，仔細想想就會發現，只要知道了哪些 bit 至少有一個 1 ，和哪些 bit 至少有一個 0 ，它們的交集就是只有一個 1 和一個 0 的集合。至少有一個 0 就是 `(~x|~y)` ，交集就是對應得運算就是 AND ，所以答案就是 `return (x|y) & (~x|~y);` 。 ### 延伸問題無 ### 參考資料 * [邏輯異或](https://zh.wikipedia.org/wiki/%E9%80%BB%E8%BE%91%E5%BC%82%E6%88%96) --- ## 第 2 週測驗 2 ### 題目 [指標篇](https://hackmd.io/s/HyBPr9WGl) 提到 signal 系統呼叫的原型宣告: ```C void (*signal(int sig, void (*handler)(int))) (int); ``` 該如何解析呢？提示: 參閱 manpage: [signal(2)](http://man7.org/linux/man-pages/man2/signal.2.html) :::success 延伸問題: 解釋 signal(2) 的作用，並在 GitHub 找出應用案例 ::: ### 想法 & 思考 `signal()` 有兩個參數，第一個是叫 `sig` 的 `int` （第一個 `int` 的意思），第二個是叫 `handler` 的 function pointer ，而這個 function 有一個 `int` 的參數（第二個 `int` 的意思），然後回傳的型態是 `void` （也就是沒有回傳值）。`signal()` 的回傳型態是一個 function pointer ，然後這個 function 有一個 `int` 參數（第三個 `int` 的意思），並且回傳的型態是 `void` 。如果我們有以下 type define: ```c typedef void (*sighandler_t)(int); ``` 也就是定義 `sighandler_t` 是一個指向『有一個 `int` 參數的 function 』的 function pointer 的型態，那麼我們可以將 `signal()` 的原形宣告改寫成一個或許比較好懂的樣子： ```c sighandler_t signal(int sig, sighandler_t handler); ``` ### 延伸問題 `signal()` 是用來設定當我們收到哪一個 signal 時，該呼叫哪一個 function (handler) 進行適當的處理（或不處理）。在第二次作業裡的 [qtest.c](https://github.com/sysprog21/lab0-c/blob/master/qtest.c) 就有使用到 `signal()` ```c=472 /* Signal handlers */ void sigsegvhandler(int sig) { trigger_exception( "Segmentation fault occurred. You dereferenced a NULL or invalid " "pointer"); } void sigalrmhandler(int sig) { trigger_exception( "Time limit exceeded. Either you are in an infinite loop, or your " "code is too inefficient"); } static void queue_init() { fail_count = 0; q = NULL; signal(SIGSEGV, sigsegvhandler); signal(SIGALRM, sigalrmhandler); } ``` ### 參考資料 * [How to read this prototype?](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype) * [Understanding typedefs for function pointers in C](https://stackoverflow.com/questions/1591361/understanding-typedefs-for-function-pointers-in-c/1591492#1591492) * [SIGNAL(2) ](http://man7.org/linux/man-pages/man2/signal.2.html) --- ## 第 2 週測驗 3 ### 題目 Linux 核心程式碼 [include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 提到以下程式碼，為何每個 `head` 使用時都要先加上 `()` 呢？ ```C #define list_for_each_prev(pos, head) \ for (pos = (head)->prev; pos != (head); pos = pos->prev) ``` :::success 延伸問題: 在 Linux 核心原始程式碼找出類似上述「走訪節點」的片段，討論其實作技巧和考量點 ::: ### 想法 & 思考如果我們不替 `head` 加上 `()` ，那麼在一些特定的情況下程式可能會出錯。例如我們如果寫： ```c list_for_each_prev(pos, &first) ``` 實際上展開會變成： ```c for (pos = &first->prev; pos != &first; pos = pos->prev) ``` 因為 `->` 的 precedence 比 `&` 還高，所以這樣程式碼就會變成`pos = &(first->prev)` 而不是我們原本希望的 `pos = (&first)->prev` 。 ### 延伸問題 ### 參考資料 --- ## 第 3 週測驗 1 ### 題目考慮以下程式碼: ```C= #include <stdio.h> #include <stdint.h> struct test { unsigned int x : 5; unsigned int y : 5; unsigned int z; }; int main() { struct test t; printf("Offset of z in struct test is %ld\n", (uintptr_t) &t.z - (uintptr_t) &t); return 0; } ``` 在 GNU/Linux x86_64 環境中執行，得到以下輸出: ``` Offset of z in struct test is 4 ``` 倘若將第 10 和第 11 換為以下: ```C=10 printf("Address of t.x is %p", &t.x); ``` 會發生什麼事？ ==作答區== * `(a)` 印出類似 `0x7ffd144e8ad4` 的輸出，也就是 `t` 結構物件的位址; * `(b)` 印出類似 `0x7ffd144e8ad4` 的輸出，和 `t` 結構物件差距 4 bytes; * `(c)` 可以印出數值，但這與編譯器實作有關，不能解讀; * `(d)` 編譯失敗，不能這樣宣告結構體的成員; * `(e)` 編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員; 參考資料: [Portable Bit Fields in packetC](https://link.springer.com/content/pdf/10.1007/978-1-4302-4159-1_34.pdf) :::success 延伸問題: 解釋原因，並且找出 C99/C11 規格書對應的描述 ::: ### 想法 & 思考這題答案為 (e) 由於 bit-fields 在 memory 裡不以尋常的方式排列，所以 C 禁止我們對它取 `&`. 實際編譯上述程式碼會得到以下結果： ``` test3-1.c: In function 'main': test3-1.c:11:36: error: cannot take address of bit-field 'x' printf("Address of t.x is %p", &t.x); ``` ### 延伸問題 §6.7.2.1 > 106)The unary `&` (address-of) operator cannot be applied to a bit-field object; thus, there are no pointers to or arrays of bit-field objects. ### 參考資料 * [規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) --- ## 第 3 週測驗 2 ### 題目考慮以下程式碼，在 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 :::success 延伸問題: 解釋運作原理，並找出類似的程式碼 ::: ### 想法 & 思考這題答案是 (b) (b) 程式中的 union 在 memory 的排列情形如下圖（假設 `int` 占 4 bytes ）（假設最左邊的地址最低） ```graphviz digraph grapghname{ node[shape=record] lb1 [label="int a", shape=plaintext] lb2 [label="char b", shape=plaintext] m1 [label="<1> |<2> |<3> |<4> "] lb1 -> m1:1:nw lb1 -> m1:4:ne lb2 -> m1:1:nw lb2 -> m1:1:ne } ``` 所以 `c.a = 1;` 會導致在 little-endian 和 big-endian 的硬體上有不一樣的結果 big-endian ```graphviz digraph grapghname{ node[shape=record] lb3 [label="MSB", shape=plaintext] lb4 [label="LSB", shape=plaintext] m1 [label="<1> 00000000 |<2> 00000000|<3> 00000000 |<4> 00000001 "] lb3 -> m1:1:nw lb4 -> m1:4:ne } ``` little-endian ```graphviz digraph grapghname{ node[shape=record] lb3 [label="MSB", shape=plaintext] lb4 [label="LSB", shape=plaintext] m1 [label="<1> 00000001 |<2> 00000000|<3> 00000000 |<4> 00000000"] lb4 -> m1:1:ne lb3 -> m1:4:nw } ``` 所以如果是 little-endian ， `return c.b == 1;` 會 return 1 ，如果是 big-endian 會 return 0 。 ### 延伸問題 ### 參考資料 * [位元組順序](https://zh.wikipedia.org/wiki/%E5%AD%97%E8%8A%82%E5%BA%8F)

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.