# 2018q3 Homework3(review)
contributed by < `type59ty` >
###### tags: `sysprog2018`, `hw3`, `review`
---
# 1
### (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 = ==&==
OP2 = ==~==
OP3 = ==|==
OP4 = ==~==
## 解題思路
題目要求做出 xor 等效運算，所以可以從邏輯閘的角度去想，用 and, or gate 組出 xor gate
xor 真值表如下
| A | B |$A \oplus B$|
|--|--|---|
| 0 | 0 | 0|
| 0 | 1 | 1|
| 1 | 0 | 1|
| 1 | 1 | 0|
根據真值表寫成布林代數表示式：$A \oplus B$ = $\overline{\rm A}B + A\overline{\rm B}$
:::info
運用 [demorgan's law](https://zh.wikipedia.org/wiki/%E5%BE%B7%E6%91%A9%E6%A0%B9%E5%AE%9A%E5%BE%8B) ，可以對原本的 xor 做等效電路
:::
簡單來說： **先相乘再反相 ＝ 先反相再相加，先相加再反相 ＝ 先反相再相乘**
- 而反相再反相，不會改變原本電路
$\overline{A}B + A\overline{B}$ $=$ $\overline{{\overline{\overline{\rm A}B + A\overline{B}}}}$
$=$ $({\overline{\overline{\overline{A}B})({\overline {A\overline{B}}}}})$
- 再根據 demorgan's law ，將第一個 bar 後面的 A,B 化成
$=$ ${(\overline{A+\overline{B}) (\overline{A}+B})}$
- 將裡面的 A,B 乘開
$=$ ${(\overline{\rm \overline{A}.\overline{B}) + (AB})}$
- 最後再將第二個 bar 後面化成
$=$ $(A+B) (\overline{A}+\overline{B})$
- 所以原本的 xor： $\overline{\rm A}B + A\overline{\rm B}$ 可以等效化成 $(A+B) (\overline{\rm A}+\overline{\rm B})$
補上測試程式碼:
```C
#include <stdio.h>
int my_xor(int x, int y) { return (x | y) & (~ x | ~ y); }
int main() {
int x = 3, y = 5;
printf("xor(%d, %d) = %d\n", x, y, my_xor(x, y));
return 0;
}
```
測試結果:
```shell
$ gcc -o test_xor test_xor.c
$ ./test_xor
xor(3, 5) = 6
```
---
# 2
### (2018q3 第 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 函式接受兩個參數： int 和 function pointer ( sig and handler )
- handler 接受 int 並回傳 void (沒有回傳值)
- 而 signal 本身也是一個 function pointer 回傳給一個接受 int 的函式，這個函式沒有回傳值
在 [stack overflow](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype) 上有個更清楚的解釋方式：
```c
signal -- signal
signal( ) -- is a function
signal( sig ) -- with a parameter named sig
signal(int sig, ) -- of type int
signal(int sig, handler ) -- and a parameter named handler
signal(int sig, *handler ) -- which is a pointer
signal(int sig, (*handler)( )) ) -- to a function
signal(int sig, (*handler)(int)) ) -- taking an int parameter
signal(int sig, void (*handler)(int)) ) -- and returning void
*signal(int sig, void (*handler)(int)) ) -- returning a pointer
( *signal(int sig, void (*handler)(int)) )( ) -- to a function
( *signal(int sig, void (*handler)(int)) )(int) -- taking an int parameter
void ( *signal(int sig, void (*handler)(int)) )(int); -- and returning void
```
作用：
在 linux 系統中， signal 用於 process 之間的訊號傳遞，概念像是作業系統中的 interrupt ，當使用者使用 kill 指令， kernel 就會調用此函式發送訊號給 process ，通知 process 目前發生某個事件。
案例：[signal.c](https://github.com/torvalds/linux/blob/master/kernel/signal.c)
---
# 3
### 測驗 `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 核心原始程式碼找出類似上述「走訪節點」的片段，討論其實作技巧和考量點
:::
**解釋：**
這邊定義了一個 macro ，在 preprocess 階段會先被執行，然後在 compile 階段裡面的變數才會代換成真正要執行的值，其中 head 是一個 pointer ，假設它為 *q ，如果沒加`()`就會變成：
```c
pos = *q->prev;
```
其中`->`的[優先權](https://zh.wikipedia.org/zh-tw/C%E5%92%8CC%2B%2B%E9%81%8B%E7%AE%97%E5%AD%90)大於`*` ，所以執行順序會變成
```c
pos = *(q->prev);
```
這跟原本預期的結果不同，所以加`()`是為了防止執行順序出錯
---
# 4
### 測驗 `7`
推敲以下程式碼的作用:
```C=
void hex2(unsigned int x) {
do {
char c = "0123456789abcdef" [x & 0xf];
printf("char %c for %d\n", c, x);
x >>= 4;
printf("char %c for %d\n", c, x);
} while (x);
}
```
:::success
延伸問題: 在 [glibc](https://www.gnu.org/software/libc/) 原始程式碼找出類似作用和寫法的程式碼，並探討其實作技巧
:::
**解釋：**
x 為一個 32 bit 整數，每次取最後4個 bits 的值當作 index ，取出字串 "0123456789abcdef" 中對應的值，取完後右移 4 個 bits，取下次的最後 4 個 bits 為 index，直到 x 為0才停止
e.g
```c
hex2(127)
則 x = 0x0111 1111
執行第3行後
c = "0123456789abcdef"[0x1111] = 'f'
再來執行 x>>=4 後
x = 0x0111
c = "0123456789abcdef"[0x1111] = '7'
再執行 x>>=4 後
得到 x = 0
下一次判斷就直接跳出 while 迴圈
```
---
# 5
### (2018q3 第 3 週測驗題)
### 測驗 `2`
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```C
int main() {
union { int a; char b;
} c = { .a = K1 };
return c.b == K2;
}
```
補完上述程式碼。
==作答區==
K1 = 254
K2 = 254
:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::
---
Sign in with Wallet
Connect another wallet