# 2018q3 Homework4 (assessment)
contributed by <[`yungchuan`](https://github.com/yungchuan)>

## 測驗一
### 題目

考慮以下求絕對值的程式碼:

#include <stdint.h>
int64_t abs64(int x) {
    if (x < 0) return -x;
    return x;
}

移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼:

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x A1 (A2 - 1);
    return (x A3 y) - y;
}

==作答區==

A1 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>

A2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 61
* `(d)` 62
* `(e)` 63
* `(f)` 64

A3 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>
請補完，其中 `A1` 和 `A3` 都是 operator。

### 想法
* 求二補數的方法：取補數後 +1 。
* 取補數的方法：對 1 做 xor (1-bit) ，所以多位元則對 -1 (所有 bit 皆 1) 做 xor 即可。

### 解題
有這兩個想法後，看了一下題目的程式碼，一開始覺得混亂，毫無地方下手，畢竟要不用分支完成正數不變、負數變二補數這件事好像有點困難。參考了一下選項，想到了如果要確認正負數的話最快的方法就是利用 sign bit，也就是最高位的值。要取得 sign bit 的值就是要跟最高 bit 跟 1 做 and 運算，可是參考了一下選項後發現好像無法達成，但是看到另一個出路，就是用右移 (>>) 運算獲得最高位 bit 的值。
而右移運算，並不只單純把二進位數往右移動而已，它會根據數值的正副，而決定右移後高位的值。若是正數，右移一個 bit 最高位 bit 就會補 0， 而負數的話，最高位 bit 則會補 1，維持數值的正負號。所以，若我們將 64 bit 的整數位移 63 bit 以上的話，正數會變成 0 ，負數則會變成 -1。所以 A1 為右移運算 A2 為 64 的話可以達到獲得 0 (正數) 或 -1 (負數) 兩種結果。
接著利用想法中第 2 點，用 xor 計算補數需要的 -1 已經得到了，而如果用正數得到的 0 去做 xor 的話，會使得結果不變，也就是說 A3 若是 xor 的話將能導致獲得原數的補數或是不變兩種結果，很接近我們的目標，接著看到後續的敘述： -y 。也就是說，若是正數，做了 xor 運算後會減 0 ，無論跟 0 做 xor 或是減 0 都不會改變數值，所以若輸入是正數的話結果不變。
若輸入是負數的話，則會先跟 -1 做 xor 運算，獲得補數，接著減 -1 ，也就是 +1 ，剛好符合二補數的需求，所以負數的輸入會得到其二補數的結果。如此，即完成了一個無分支的絕對值函式。

## 測驗二
### 題目
考慮測試 C 編譯器 [Tail Call Optimization](https://en.wikipedia.org/wiki/Tail_call) (TCO) 能力的程式 [tco-test](https://github.com/sysprog21/tco-test)，在 gcc-8.2.0 中抑制最佳化 (也就是 `-O0` 編譯選項) 進行編譯，得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                no TCO
One argument:                                no TCO
Additional int argument:                     no TCO
Dropped int argument:                        no TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          no TCO

而在開啟最佳化 (這裡用 `-O2` 等級) 編譯，會得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                TCO
One argument:                                TCO
Additional int argument:                     TCO
Dropped int argument:                        TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          TCO

注意 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 是 gcc 的內建函式:
> This function returns the return address of the current function, or of one of its callers. The level argument is number of frames to scan up the call stack. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function, and so forth. When inlining the expected behavior is that the function returns the address of the function that is returned to. To work around this behavior use the noinline function attribute.
> The level argument must be a constant integer.

從實驗中可發現下方程式無法對 `g` 函式施加 TCO:

void g(int *p);
void f(void) {
    int x = 3;
    g(&x);
}
void g(int *p) { printf("%d\n", *p); }

因為函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack。考慮以下程式碼:

int *global_var;
void f(void)
{
    int x = 3;
    global_var = &x;
    ...
    /* Can the compiler perform TCO here? */
    g();
}

思考程式註解，在第 8 行能否施加 TCO 呢？選出最適合的解釋。

==作答區==

* `(a)` 編譯器不可能施加 TCO
* `(b)` 編譯器一定可施加 TCO
* `(c)` 只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會

### 想法
題目提到，區域變數在返回後就不存在 stack 中，所以不能使用 TCO 最佳化。也就是說，因為把 x 的位址傳遞出去，有可能使用到 x 值，所以就要維持 x 在 stack 中，而造成無法最佳化。

### 解題
這次的程式是使用全域變數來儲存位址，所以並不需要傳遞位址。也就是說，不確定在 g 函式中是否會使用到 f 函式裡的區域變數。因為區域變數的位址存在全域變數 global_var 裡面，若在 g 對 global_var 做 dereference 的話，則會需要用到 f 函式裡的區域變數，此時就不能做 TCO。
但如果 g 並沒有對 global_var 做 dereference 的話，就不需要特別留 f 的區域變數，如此即可對此程式做 TCO 最佳化。

## 測驗三
### 題目
以下程式碼編譯並執行後，在 x86_64 GNU/Linux 會遇到記憶體存取錯誤:

$ cat ptr.c
int main() {
    int *ptr = 0;
    return *ptr;
}
$ gcc -o ptr ptr.c
$ ./ptr
Segmentation fault: 11

分別考慮以下 4 個程式，探討其行為。
- [ ] `ptr1.c`

int main() { return *((int *) 0); }

- [ ] `ptr2.c`

int main() { return &*((int *) 0); }

- [ ] `ptr3.c`

#include <stddef.h>
int main() { return &*NULL; }

- [ ] `ptr4.c`

#include <stddef.h>
int main() {
    return &*(*main -  (ptrdiff_t) **main);      
}

==作答區==

K1 = ?
* `(a)` `ptr1.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr1.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr1.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

K2 = ?
* `(a)` `ptr2.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr2.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr2.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

K3 = ?
* `(a)` `ptr3.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr3.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr3.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

K4 = ?
* `(a)` `ptr4.c` 在執行時期會造成 Segmentation fault
* `(b)` 對於 `ptr4.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤
* `(c)` `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`

### 想法
* 由題目一開始的例子可以知道，直接提取記憶體位址 0 (null pointer) 的資料是會造成記憶體存取錯誤的，也就是說是個不能存取的記憶體位址。
* 而從 C99 規格書中：
* C99 [6.5.3.2-3]: The unary **&** operator yields the address of its operand. If the operand has type ‘‘*type*’’, the result has type ‘‘pointer to *type*’’. If the operand is the result of a unary __*__ operator, neither that operator nor the **&** operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue.
* C99 [6.5.3.2-4]: 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.
* C99 [ 84) ]: 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__.
* C99 [7.17-2]: The types are __ptrdiff_t__ which is the signed integer type of the result of subtracting two pointers;

由以上觀念開始解題

### 解題
K1：由想法第 1 點知道，對 null pointer 做 value of 運算會造成非法記憶體存取，而 ptr1.c 將 0 轉型成 int*，再做 value of 運算，是一樣的意思，所以會造成 Segmentation fault。
K2, K3：接著看 ptr2.c 以及 ptr3.c ，會發現它們其實是一樣的程式。因為對 0 轉型成 int* 就等同於 NULL，也就是說它們都是 null pointer，而從 C99 規格數註解 84 可以知道，即使是 null pointer，使用 &* 運算的話會等價於沒有進行運算。所以這兩個程式都是可以運行的。
K4：由規格書知道，不管使用多少個 __*__ 對 function 做運算，其結果跟使用一個 __*__ 是一樣的，變成 function designator ，因為接著的運算並非 __sizeof__ 或 __&__ 所以又變回 function return type ，且因為 __&*__ 是可以忽略的，所以最後程式會被簡化為： `return (main - (ptrdiff_t)main); ` 為一合法程式。
:::info
不太懂在此加入 `ptrdiff_t` 的目的
:::

## 心得
閱讀完 [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) 之後，心裡的想法是：跟很多勵志文章大同小異，但是更貼近我現在的現實生活。
其實整體來說，這篇文章裡面寫了很多製作的過程，而那對我來說其實有點乏味，基本上只是透漏了「這個東西很難做，很複雜」的訊息。但是，如果沒有寫上這些，那讀者應該也很難在看到最後有種「終於完成了，恭喜」的想法。而且說到底這篇比較像是他們的回顧記錄，記錄製作過程也是理所當然的。
起初我以為最後是失敗告終，文章是要表達現實的殘酷之類的訊息。而且說到底，其實這篇的結局並沒有完全成功，飲料機還必須改良，成本是否有符合效益也很難說。但是，他們起初有了想法，決定實作的時候，我心中其實相當敬佩他們，他們擁有我心中最缺乏的決心以及行動力，我可能在期初就會因為各種成本分析以及可能遭遇的問題而放棄吧，更別說後面又遇到一堆問題。
看完了這篇文章，我發現其實我真正在想的並不是什麼「不要想太多，做就對了」、「想做就做，不要害怕失敗」或是「把握年輕，去做各種嘗試」之類的想法，而是最赤裸的回顧自僅的人生。我到底把我的青春歲月用在哪了？仔細想想我根本在浪費。讀書考試就算了，還一直在打電動，想一些沒意義的事。我總不希望成年後回顧我的青春時只有滿滿的後悔吧？看完這篇文章，我心中漸漸有了一點要好好把握青春的想法，但能不能實踐還是要看我的決心吧，其實之前也有很多類似的想法但都是因為沒有決心而不了了之，而這次又萌生這種念頭，希望可以好好把握。