2018q3 Homework4 (assessment)
===
contributed by < ChingChieh >

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

#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。
### 想法
因為要用到二補數的概念把負的數變成正的所以應該會想到對負數取二補數然後再加 1 因此 return 那邊會是 (x ^ 0xFFFFFFFFFFFFFFFFFF) - 0xFFFFFFFFFFFFFFFFFF ，因為 - (-1) 等於＋1 ，於是再看上一行要怎麼得到64bits的1，我們知道負數最左邊的signed bit一定會是1所以只需要 right shift 63次就可以讓得到 64bits 的1。當傳入的 x 是正數時 y 的值就是 0 這樣在 return 時就還會是 x 自己。

但需要注意的是在規格書裡面有提到對signed integer 的 right shift 究竟是補1還是0是 implementation define ，也就是說看compiler怎麼實做。
### 延伸問題
## 問題二
### 題目
考慮測試 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

從實驗中可發現下方程式無法對 `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 呢？選出最適合的解釋。
### 想法
* __builtin_return_address用法

__builtin_return_address(0):當前function的return address
__builtin_return_address(1):當前function的caller的return address
__builtin_return_address(2):當前function的caller的caller的return address
以此類推

### 延伸問題
## 問題三
### 題目
以下程式碼編譯並執行後，在 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`
根據規格書6.5.3.3下面有寫
**Among the invalid values for dereferencing a pointer by the unary * operator are a null pointer**, an address inappropriately aligned for the type of object pointed to, and the address of an object after the end of its lifetime.
所以 null pointer 不能用 * operator 來 dereference ，所以這樣在執行時期會造成 Segmentation fault

- `ptr2.c` `ptr3.c`
根據規格書6.5.3.3下面有寫
**Thus, &*E is equivalent to E (even if E is a null pointer)**, and &(E1[E2]) to ((E1)+(E2)).
所以可以看成 return NULL ，所以是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0

- `ptr4.c`
可以先看成 return *main - (ptrdiff_t) ** main，而在[前幾禮拜的作業](https://hackmd.io/dC5Hcrb1T82ElEhQynasgg#function-designator-amp-function-pointer)中我們知道可以化簡成 return main - (ptrdiff_t)main ，而ptrdiff只是把function pointer 看成不同的 type 裡面的存的還是指標，所以相減還是 0 因此又可以看成 return NULL ，所以是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0

### 延伸問題
* 解析 clang/gcc 編譯器針對上述程式碼的警告訊息

warning: incompatible pointer to integer conversion returning 'int *'

根據規格書5.1.2.2.1
It shall be defined with a return type of int
The function called at program startup is named main. The implementation declares no prototype for this function. **It shall be defined with a return type of int** and with no parameters:
int main(void) { /* ... */ }
or with two parameters (referred to here as argc and argv, though any names may be
used, as they are local to the function in which they are declared):
int main(int argc, char *argv[]) { /* ... */ } or equivalent;10) or in some other implementation-defined manner.
所以回傳 pointer 的 type 和 int 是 imcompatible 的所以會有warning