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

## 回顧第 4 週課程內容
### [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X)

#### 測驗 `1`

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

#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` 和 `A3` 都是 operator。

==作答區==

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)` >>

:::success
延伸問題:
1. 解釋運作原理，並探討可能的 overflow/underflow 議題;
2. 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

static uint64_t r = 0xdeadbeef
int64_t rand64() {
    r ^= r >> 12;
    r ^= r << 25;
    r ^= r >> 27;
    return (int64_t) (r * 2685821657736338717);
}

3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
:::

---
* 解題想法
* 要對負數取絕對值 : 做反相運算然後加上 1
* 將 x 向右 shift 63 位，產生一個 mask y，如果 x 是負數，則 y = 1...1；如果 y 是正數，則 y = 0...0

        y = x >> 63

* 對 x 和 y 作 XOR，如果 x 是負數，會是反相運算；如果 x 是正數，則不變

        x ^ y

* 若 x 是負數，則做完反相運算要再加上 1；如果 x 是正數，則不加。可以表示成減去 mask y，因為如果 x 是負數，則 y = 1...1 = -1；如果 x 是正數，則 y = 0...0 = 0

        (x ^ y) - y

* 延伸問題
1. 解釋運作原理，並探討可能的 overflow/underflow 議題;
* 當 x = 1000...000 時，x 的對應的正數則無法用已有位元數量內的可用二補數來表示
2. 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

        static uint64_t r = 0xdeadbeef
        int64_t rand64() {
            r ^= r >> 12;
            r ^= r << 25;
            r ^= r >> 27;
            return (int64_t) (r * 2685821657736338717);
        }

* 234
3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
* 123
* 參考
* [wiki 二補數](https://zh.wikipedia.org/wiki/%E4%BA%8C%E8%A3%9C%E6%95%B8)
* [Compute the integer absolute value (abs) without branching](https://www.geeksforgeeks.org/compute-the-integer-absolute-value-abs-without-branching/)

### [第 4 週測驗題(中)](https://hackmd.io/s/Syl6me49Q)

#### 測驗 `2`

考慮測試 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 就有機會==

:::success
延伸問題:
1. 探討 TCO 和遞迴程式的原理
2. 分析上述實驗的行為和解釋 gcc 對 TCO 的操作
3. 在 [Android 原始程式碼](https://android.googlesource.com/) 裡頭找出 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 的應用並解說
:::

---
* 解題想法
*
* 延伸問題

### [第 4 週測驗題(下)](https://hackmd.io/s/By7Lwz4qm)

#### 測驗 `3`

以下程式碼編譯並執行後，在 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`==

:::success
延伸問題:
1. 參照 C 語言規格書，充分解釋其原理
2. 解析 clang/gcc 編譯器針對上述程式碼的警告訊息
3. 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler
:::

---
* 解題想法
*
* 延伸問題

---

## 誠實面對自己
* 紀錄閱讀 [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) 的啟發
* 實作的精神
* 要產出一個穩定的系統，需要非常多的實驗和測試
* 很多時候要解決一個問題，需要有不同專長、不同領域的人合作才能有效率的解決
* 學習本課程 4 週之後的感想
* 原本以為有學過 C++，就可以很容易了解 C 語言，經過這四週的課程，了解到其實 C 跟 C++ 差很多，而且有個第一手資料 -- 規格書的存在。了解底層的運作原理，才能完全掌握自己寫的程式碼。