# 2018q3 Homework3 (review)
contributed by <`krimson8`>

## 第二週測驗 q2

### 解讀

void (*signal(int sig, void (*handler)(int))) (int);

根據之前自己整理出來的口訣
* `*f()` 是function returning a pointer
* `(*f)()` 是pointer to a function

因此根據上面的程式碼，可以一步一步分析出來
* `void (*handler)(int)`
* `handler` 是pointer to a function，此 function 有一個 `int` 的 parameter
* 此 function 將 return `void`
* `*signal()`
* 是一個function，他將會 return 一個 pointer
* `void (*signal()) (int)`
* `*signal()` 回傳的 pointer 會指向另外一個 function，此 function 有一個 `int` 的 parameter
* 此 function 將 return `void`

[Stack Overflow](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype)上的一篇回覆有更好的解釋

### signal 的功用
這裏列出 man signal（7） 的 standard signal，有多個value 的signal 名字意味着在不同的架構下又不一樣的value，中間的多數實作於x86 與 arm，右邊的是 mips 用
| Signal | Value | Action| Comment |
|-- | --| --| --|
|SIGHUP | 1 | Term | Hangup detected on controlling terminalor death of controlling process|
|SIGINT | 2 |Term |Interrupt from keyboard|
|SIGQUIT | 3 |Core |Quit from keyboard|
|SIGILL | 4 |Core |Illegal Instruction|
|SIGABRT | 6 |Core |Abort signal from abort(3)|
|SIGFPE | 8 |Core |Floating-point exception|
|SIGKILL | 9 |Term |Kill signal|
|SIGSEGV | 11 |Core |Invalid memory reference|
|SIGPIPE | 13 |Term |Broken pipe: write to pipe with no readers; see pipe(7)|
|SIGALRM | 14 |Term |Timer signal from alarm(2)|
|SIGTERM | 15 |Term |Termination signal|
|SIGUSR1 |30,10,16 |Term |User-defined signal 1|
|SIGUSR2 |31,12,17 |Term |User-defined signal 2|
|SIGCHLD |20,17,18 |Ign |Child stopped or terminated|
|SIGCONT |19,18,25 |Cont |Continue if stopped|
|SIGSTOP |17,19,23 |Stop |Stop process|
|SIGTSTP |18,20,24 |Stop |Stop typed at terminal|
|SIGTTIN |21,21,26 |Stop |Terminal input for background process|
|SIGTTOU |22,22,27 |Stop |Terminal output for background process|

上表中我們較爲熟悉的是 `SIGINT` 和 `SIGSEGV`，前者是在linux 終端執行程式的時候按下 ctrl+c 會給出的訊號，後者是發生 segmentation fault 系統給出的訊號

這裏附上一個範例程式，說明signal 的用法，執行的時候可以使用 ctrl+z 來退出程式
[來源](https://www.thegeekstuff.com/2012/03/catch-signals-sample-c-code/)

#include <stdio.h>
#include <signal.h>
#include <unistd.h>

void sig_handler(int signo)
{
    if (signo == SIGINT)
        printf("received SIGINT\n");
}

int main(void)
{
    if (signal(SIGINT, sig_handler) == SIG_ERR)
        printf("\ncan't catch SIGINT\n");
    // A long long wait so that we can easily issue a signal to this process
    while(1) 
        sleep(1);
        
    return 0;
}

這個程式碼示範了如何使用 `signal（）` 建立 signal handler
根據 man signal

`sighandler_t signal(int signum, sighandler_t handler);`
:::success
signal() **sets the disposition（部署） of the signal signum to handler**, which
is either **SIG_IGN, SIG_DFL**, or the address of a **programmer-defined
function (a "signal handler")**.

If the signal signum is delivered to the process, then one of the
following happens:

* If the disposition is set to **SIG_IGN, then the signal is ignored**.

* If the disposition is set to **SIG_DFL, then the default action**
associated with the signal (see signal(7)) occurs.

* If the disposition is set to a function, then first either the
disposition is reset to SIG_DFL, or the **signal is blocked (see
Portability below), and then handler is called with argument
signum**. If invocation of the handler caused the signal to be
blocked, then the signal is unblocked upon return from the
handler.

The signals **SIGKILL and SIGSTOP cannot be caught or ignored**.

**signal() returns** the **previous value of the signal handler**, or **SIG_ERR on error**. In the event of an error, errno is set to indicate the cause.
:::

因此程式碼首先將 `SIGINT` （ctrl+c）部署給 自行定義的 `sig_handler()`，`sig_handler` 內檢測收到的 signal 是不是 `SIGINT`，若是的話則執行程式碼。我們也可以設定多種signal handler 給不同的signal 使用，像是 ctrl+z 會觸發的 `SIGTSTP`。

根據man page 的解釋，`sighandler_t` 這個 type 的使用是一種 GNU 的extension，而題目所問的 `void ( *signal(int signum, void (*handler)(int)) ) (int);` 則是沒有使用上述的type 的時候 signal 的定義方法。

## 第二週測驗 q3
`for (pos = (head)->prev; pos != (head); pos = pos->prev)`
每一次 `head` 的使用都要先加上（）的原因
根據 [C Operator Precedence](https://en.cppreference.com/w/c/language/operator_precedence)
"`*`"（dereference） 的 precedence level 是要低於 "`->`"（member access）的，因此若有需要 derefer `head` 的時候，若不加上括號，程式碼的行爲就會和預想中的不一樣

例子：與`*head->next` 相等的表達式 `*(head->prev)`

尋找 [linux/list.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/tools/include/linux/list.h) 內相似的程式碼實作

#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)

與 `list_for_each_prev` 的原理差不多，從 `head->next` 開始進行 list 的尋訪

#define list_for_each_safe(pos, n, head) \
	for (pos = (head)->next, n = pos->next; pos != (head); \
		pos = n, n = pos->next)

這裏 safe 的意思是 safe against removal of list entry，因爲使用多一個 list 結構 `n`作爲暫存點，所以可以在程式碼內進行 `pos` 點的removal，remove 完了 list 的探訪還能繼續下去

## 第一週測驗 q1

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); 
}

把OP 都補上，完整程式碼-

int my_xor(int x, int y) { return (x | y) & (~x | ~y); }
int main() {
    int x = 3, y = 5;
    return my_xor(x, y); 
}

這一題的概念在大二上的數位電路課有教過，推理的原理如下
* 首先我們有 `x | y`，表示說x 的位元和 y 的位元其一爲一即可，那麼會有一下幾種情況
* x | y 的結果是 0
* 這邊就可以推敲出 OP1 是 `&` 因爲在這種情況下，`x ^ y` 的結果一定是0，若不看後面的結果的話那就用 `&`
* x | y 的結果是 1，那麼又有下面兩個情況
* x 和 y 皆是 1，則後面的判斷式必須回傳 0
* x 和 y 分別是0 和1，則需要確保後面的判斷式也回傳1
若要後面的判斷式回傳1，，且 OP2 和 OP4 都必須填上的情況（OP2 和 OP4 皆爲 `~`）則確定了 OP3 是 `|`，這樣也能滿足 x 和 y 皆是1 的情況

翻閱以前的學到的公式，xor 也可透過一下的方式呈現
* `return (x & ~y) | (~x & y)`
* `return (x | y) & ~(x & y)`

## 第一週測驗 q2

這一題當天在做的時候其實用了很取巧的方式去想這個問題，並沒有深入理解程式碼實作的內容

當天的想法:

int max = 16;

while (max >= 8) {
    num = num ^ (num >> max);
    max /= N;
}

看到這邊很自然的就覺得這個程式碼不會只跑一次，因此2,4,8 這三個選項 裏面只有 2 有可能

分析了程式碼和瞭解了 parity bit 的做法過後，嘗試解釋這份程式碼

#include <stdio.h>

/* Generate look-up table while pre-processing */
#define P2(n) n, n ^ 1, n ^ 1, n
#define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
#define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
#define LOOK_UP P6(0), P6(1), P6(1), P6(0)

/* LOOK_UP is the macro expansion to generate table */ 
unsigned int table[256] = { LOOK_UP };

int parity(int num) {
    /* Number is considered to be of 32 bits */
    int max = 16;

    // Dividing the number into 8-bit 
    // chunks while performing XOR 
    while (max >= 8) {
        num = num ^ (num >> max);
        max /= N;
    }
    // Masking the number with 0xff (11111111) 
    // to produce valid 8-bit result 
    return table[num & 0xff];
}

int main() {
    unsigned int num = 1742346774;
    /* Result is 1 for odd parity, 0 for even parity */
    int result = parity(num);
    printf("%s parity\n", parity(num) ? "odd" : "even");

    return 0;
}

* 首先我們看到了程式碼一開始建立了一個 大小爲 256 的 `table[]`，爲什麼是256 呢？ 因爲在`int parity()` 裏面 return 了一個值，值是 `table` 裏的某一個元素，而該index 與 0xff mask，意味着是一個8bit 的數字，而 2 的 8次方就是 256
* 那麼他是怎麼判斷parity bit 的呢？原理如下：
* 把 32-bits 的int 分割成四個等分，從左到右我們標記爲 p1, p2, p3, p4
* 把 p1 和 p2 做 xor，p3 和 p4 做 xor ，經過這一步所出來的結果
* 1 的話，代表 0 和 1 的存在，需要繼續進行下一步判斷
* 0 的話，代表 0 和 0 或 1 和 1
然後吧兩組結果標記爲 t1 和 t2 繼續進行下一步
* 讓 t1 和 t2 進行 xor，經過這一步所出來的結果
* 1 的話，代表 0 和 1 的存在，也就是說p1, p2, p3, p4中，出現了奇數的1
* 0 的話，代表 0 和 0 或 1 和 1 , 0 和 0 的話可能是p1, p2, p3, p4中有 0 個 1 或者4 個 1, 1 和 1 的話則是剛好 p1, p2, p3, p4 中有 2 個 1

* 再來我們看看 `table[256]` 張開的結果

    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1
    0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

就是2 進制下，8-bit 的 `00000000` ，不斷+1 的parity bit 首四個元素 0 1 1 0 對應如下
* 00000000 -> 0
* 00000001 -> 1
* 00000010 -> 1
* 00000011 -> 0
從 0 1 1 0 開始，我們可以看到有以下的規律，以四個元素爲單位，不是 1001 就是 0110，並且根據2進位下不斷的+1 所形成。因此

    #define P2(n) n, n ^ 1, n ^ 1, n
    #define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n)
    #define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n)
    #define LOOK_UP P6(0), P6(1), P6(1), P6(0)

就是對應上述的規律所產生的

### CRC 程式碼

## 第三週測驗 q2
原題程式碼

int main() {
    union { int a; char b;
    } c = { .a = K1 };
    return c.b == K2;
}

K1 和 K2 都是 1，可分爲以下兩種情況
* little endian
假設4 byte 的地址編號如下，則 `int a` 在系統內的存放方式如下
|Address|0x0A|0x0B|0x0C|0x0D|
|-- |-- |-- |-- |-- |
|Value |0x01|0x00|0x00|0x00|

因此存取 b 的時候，b 和 a 共享的空間是 0x0A，因此會return 1

* big endian
`int a` 在系統內的存放方式如下
|Address|0x0A|0x0B|0x0C|0x0D|
|-- |-- |-- |-- |-- |
|Value |0x00|0x00|0x00|0x01|

因此存取 b 的時候，b 和 a 共享的空間是 0x0A，因此會return 0

### 類似的判斷big endian 或是 little endian 的程式碼
[來源](https://stackoverflow.com/questions/12791864/c-program-to-check-little-vs-big-endian#)

#include <inttypes.h>
int main(int argc, char ** argv){
    volatile uint32_t i=0x01234567;
    // return 0 for big endian, 1 for little endian.
    return (*((uint8_t*)(&i))) == 0x67;
}

這段程式碼若運行在 little endian 的機器上 輸出結果爲 1，反之則爲 0
i 在 little endian 系統內的存放

|Address|0x0A|0x0B|0x0C|0x0D|
|-- |-- |-- |-- |-- |
|Value |0x67|0x45|0x23|0x01|

因此若把他 cast 成只有 8-bits 的integer，將會只剩下 0x0A 的內容