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

## 第 4 週測驗題

### 測驗 `1`

#### 題目
:::info
考慮以下求絕對值的程式碼:

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

移除分支並善用二補數特性，改寫為下方程式碼:

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

請補完，其中 A1 和 A3 都是 operator。
:::

#### 想法
這段程式碼的目的是求取絕對值，且題目提示要利用二補數的性質，而二補數的其中一個性質就是只要取其一補數，亦即所有的位元 1、0 互換之後，再加上 1 就可以得到直接變換正負號後出來的結果，由此我們可以判斷最後的回傳值 `(x A3 y) - y` 應該就是執行同樣的過程。

假如原數是負數的話必須要取其一補數並加 1，相當於與 -1 做 XOR 並減去 -1，因為 -1 利用二補數表示的話每個位元都是 1；另外如果是 0 或者正數這種絕對值與原數相同的情況，那就只要讓它與 0 做 XOR 並減去 0 的話，就可以維持原樣了。由此推出我們必須要在上一行程式碼設法讓 `y` 在 `x` 為負數時是 -1，其餘情況為 0，且 A3 這個 operator 實際上就是 `^`。

而要讓 `y` 符合我們的期待其實並不困難，因為我們需要的其實就是讓 `y` 的每一個位元都等同於 `x` 的 sign bit，所以只需要讓 `y` 等於 `x` 右移直到所有位元都自動被補為 sign bit 的結果就行了。由此我們可以推出 A1 這個 operator 實際上就是 `>>`，而 A2 就是 32。

### 測驗 `2`

#### 題目
:::info
考慮測試 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 呢？選出最適合的解釋。
:::

#### 想法
在無法施加 TCO 的範例程式中，g 函式中包含了對指向 `x` 的指標做 dereference 的行為，然而 `x` 是 f 函式中的區域變數，如果施加 TCO 取代了 f 原本的 stack frame 的話，`x` 便不復存在並導致程式行為錯誤，因此無法施加 TCO。

因此回到原本的題目上，要決定可否使用 TCO 就要確定 g 函式是否使用了 `global_var` 的 dereference。如果沒有的話，即便 `x` 已經不存在 stack 之中也不會發生錯誤，因此可以施加 TCO；反之，若使用了 `global_var` 的 dereference，則必須保留 f 函式的 stack frame ，也因此就無法施加 TCO 。

### 測驗 `3`

#### 題目
:::info
以下程式碼編譯並執行後，在 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);                                                                                                                  
}

:::

#### 想法
* `ptr1.c`
* 將 0 轉型為 pointer to int 之後再 dereference。
* 由於指標指向的位址為 0 ，會產生 Segementation fault。
* `ptr2.c`：
* 將 0 轉型為 pointer to int 之後 dereference，並且再取 address of 。
* 在編譯過程中 `&` 與 `*` 會相互抵銷，使得最後回傳位址本身，也就是 0。
* `ptr3.c`：
* `NULL` 是一個 macro，通常定義為 `((char *) 0)`，也就是指向在位址 0 的 `char`。
* 在編譯過程中 `&` 與 `*` 會相互抵銷，使得最後回傳位址本身，也就是 0。
* `ptr4.c`：
* `main` 是 function designator，且會自動被轉為 pointer to function，因此無論在前面加上多少 `*` 做 dereference，最後都會再被自動被轉為 pointer to function。
* `*main` 與 `**main` 都是指向相同的位址，因此相減後結果為 0，又因為在編譯過程中 `&` 與 `*` 會相互抵銷，最後會回傳 0。

## 閱讀啟發 — [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)
靠著雙手獨立開發出實際可用的產品從來不會是一件簡單的事，學校裡學到的專業知識並非毫無用武之地，但是當面對現實世界的問題時，必然會發現一個領域連接著一個領域，沒有融會各方面的知識與工具，實在很難創造出實際的成果。而更艱難的是，面對包括金錢、技術上的種種困難，仍決心要投身自己一年時光在這上面毅力，儘管實踐過程中必然會獲得許多可貴的經驗，但我很難想像自己能夠承受這種忙到最後可能只是一場空的煎熬。
回顧這堂課一開始，老師就向我們揭示了要誠實面對自己，即便是自認為已經熟習的 C 語言都藏著一大堆不曾想像過的細節，也讓我深切體認到連規格書都不會讀的自己簡直如同井底之蛙一般。然而意識到是一回事，能不能走出自己的舒適圈又是另一回事，期許自己能在這學期內，鍛鍊自己成為一個真正有價值、有產出的工程師。