2018q3 Homework4 (assessment)
===

Contributed by < [Jyun-Neng](https://github.com/Jyun-Neng) >

---

### 測驗 `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 >> (64 - 1);
    return (x ^ y) - y;
}

第二行程式碼類似 signed extension，`y` 為 `x` 的 signed bit extend 的結果，也就是說，若 `x` 是負數 signed bit = 1 則 `y` 的所有 bit 都為 1; 若 `x` 是正數 signed bit = 0 則 `y` 的所有 bit 都為 0。

正負數的表示是以 2's complement 的方法來做正負數互換的，而 2's complement 會等價於 1's complement 再加 1。程式碼第四行便是利用這個特性，先對 `x` 與 `y` 做 XOR 再與 `y` 相減，其可能發生的情況有兩種:

1. `y` 為 0，則 `x` 的值不變。
2. `y` 的所有 bit 為 1，則 `x ^ y` 等同於做 1's complement，而 `y` 的有號數表示為 -1，所以 `-y = +1`，等同於對 `x` 做了 2's complement。

這樣的作法是否存在 overflow 的問題，以 4-bit 運算為例: 當 `x=-8 x=7` 時，

x = -8

  x 1000     x^y 0111
  y 1111      -y 0001
---------    ---------
x^y 0111         1000

x = 7
  
  x 0111     x^y 0111
  y 0000      -y 0000
---------    ---------
x^y 0111         0111

在 corner case 下，也不會發生 overflow/underflow。

:::danger
是會有 overflow 問題，`x=-8` 無法得到 `abs(x) = 8` 的結果。 n-bit 有號數表示的區間是坐落在 $[-2^{n-1},2^{n-1}-1]$，負數是比正數多一個的，若負數為 $-2^{n-1}$ 則無法在 n-bit 表示下求出絕對值。
:::

搭配下方 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);
}

:::info
對於測試程式沒什麼概念，我的理解是只要亂數產生輸入並觀察輸出是否正確就好，但要把 64-bit 的值都產生並測試，光是產生所有值 for 迴圈就要跑 $2^{64}$。所以可能的做法應該是針對 bit 做測試，也就是說當某個 bit 變動並測試正確後，該 bit 就不須再變動，這樣就只需要產生 65 種值。以 4-bit 為例:

 x = 0000
   = 0001
   = 0011
   = 0111
   = 1111

只需要測這五個值的結果即可?
:::

---

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

---

### 測驗 `3`

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

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

:::success
[In C, why initializing pointer to 0 doesn't give compile time error?
](https://stackoverflow.com/questions/38816850/in-c-why-initializing-pointer-to-0-doesnt-give-compile-time-error)`int *ptr = 0;` 這行程式碼是沒有問題的，它指派 `ptr` 為 NULL pointer，會產生記憶體存取錯誤是因為試圖回傳 NULL pointer `ptr` 的值。

:::

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

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

這段程式碼將 0 cast 成 pointer to int 而其為 NULL pointer，所以無法存取 NULL pointer 的值。

- [ ] `ptr2.c`

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

在編譯時會產生 warning 因為 function type 是 int 但回傳值是 pointer to int，但是可以成功執行的，回傳的是 NULL pointer。

- [ ] `ptr3.c`

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

在編譯時會產生 warning 因為 function type 是 int 但回傳值是 pointer to void，但是可以成功執行的，回傳的是 NULL pointer。

- [ ] `ptr4.c`

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

在編譯時會產生 warning 因為 function type 是 int 但回傳值是 pointer to function，但是可以成功執行的。

---

### [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)及課程感想

> 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》

所以我現在必須付出四倍的代價，甚至超越。

自認為自己喜歡寫程式，但到了這門課我才真正開始正視記憶體存取的問題 ! 還有更我多以前從沒注意或者忽略的問題，例如:測試程式。