# 2018q3 Homework4 （assessment）
contributed by <`krimson8`>
## 開發環境
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 6
On-line CPU(s) list: 0-5
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 158
Model name: Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz
Stepping: 10
CPU MHz: 800.012
CPU max MHz: 4000.0000
CPU min MHz: 800.0000
BogoMIPS: 5616.00
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 9216K
NUMA node0 CPU(s): 0-5
```
## 2018q3 第 4 週測驗題 (上)
### 測驗 `1`
```clike
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x A1 (A2 - 1);
return (x A3 y) - y;
}
```
* A1: >>
* A2: 64
* A3: ^
#### 解題思路
首先很直覺的認爲 A2 是 64，因爲要取絕對值於 sign-bit 一定有關係
這裏先附上3-bit 的 signed integer 列表
|decimal |binary |
|-- |-- |
|3 |011 |
|2 |010 |
|1 |001 |
|0 |000 |
|-1 |111 |
|-2 |110 |
|-3 |101 |
|-4 |100 |
照着這個思路，要提取出這個 sign-bit 應該是要用 shift ，那麼sign bit 就會出現在 第一個 bit 內，但是那時候考慮到 sign extension (6.5.7 - 5: If E1 has a signed type and a negative value, the resulting value is implementation-defined.) 會讓前面的所有bit 都變得跟 第一個bit 一樣，一時緊張選擇了錯誤的答案 `&`.
其實前面的所有bit 和 sign bit 一樣正是想要的結果，繼續探討 A3，使用排除的方式，根據兩種情況的結果
* 若原本傳入的值就是正數，則與 `000` 進行 `|` 和 `^` 能保持原本的數值
* 若是負數，`return` 哪一行的 `-y` 實際意義就是 `+1`，從上表得知，將負數 -n 的後兩個位元與 11 做 `^` 的結果便是位元提換，替換的結果剛好是 n-1，因此 `+1` 便可以得到正確的數值
根據 C 語言規格書，對有號數做 right-shift 都是 implementation-defined，但是目前看到大多數的 compiler 支援的都是 arithmetic shift，也就是對空白處補上 sign-bit。
#### 潛在的 underflow/ overflow 問題
因爲在 64-bit 有號數裏面的有效表示範圍爲 $-2^{64}$ 到 $2^{64} - 1$ 因此若傳入進去的值是$-2^{64}$ 時，則程式的執行結果不正確，但是考量下列情況
```
x = -4
100
^ 111
------
011
+ 001
------
100 (-4)
```
並沒有發生 overflow/underflow 的情況
#### 探討 pseudo-number generator 與 上述程式的可行性
```clike
static uint64_t r = 0xdeadbeef
int64_t rand64() {
r ^= r >> 12;
r ^= r << 25;
r ^= r >> 27;
return (int64_t) (r * 2685821657736338717);
}
```
使用這隻程式應該是可以在有限的時間內窮舉所有的可能，但是所耗費的時間實在是太長，因此目前的想法是帶入幾個 corner case 來測試
## 2018q3 第 4 週測驗題 (中)
#### 探討 TCO
參考自己的 [hw1](https://hackmd.io/c/H1-NYOEFX/%2Fs%2FHkCht_EtX)↓↓↓
遞迴函式每一次的函式呼叫都會建立 **stack** 並且把 **{參數，區域變數，返回位置}** 這些 **原函式的執行狀態** 保存起來，再把他推到 **系統堆疊** 的頂端。
**理論上的尾端遞迴的優化** - （[來源](https://stackoverflow.com/questions/19854007/what-is-the-advantage-of-using-tail-recursion-here)）
其中有一片解答說明 tail recursion 可以很輕易的 轉化爲 iterative 的形式，也就是說編譯器有進行優化的話可以不佔用更多的 stack frame，但是其實很多編譯器並沒有這麼做
另一篇解答更好的說明了 TCO 的原理
```
This optimization is possible because the compiler knows that once the
tail recursive call is made, no previous copies of variables will be
needed, because there is no more code to execute. If, for instance, a
print statement followed a recursive call, the compiler would need to know
the value of the variable to be printed after the recursive call returns,
and thus the stack frame cannot be reused.
```
也就是說若是像計算 費氏數列 的 recursive 函式若是 tail recursion 的話是可以優化成iterative 的形式的，而老師原本的例子
```clike=
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) { printf("%d\n", *p); }
```
此段程式碼不能夠被優化的原因是因爲 x 原本存在於 `f()`的 stack frame 內，但是若要優化的話則表示 `g()` 將繼續使用那個 stack，因此 x 的位址內的內容將不再是 x，導致程式出錯
參考 [這篇文章](https://david.wragg.org/blog/2014/02/c-tail-calls-1.html)
```clike=
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* The compiler cannot perform TCO here,
* unless it can establish that g does not
* dereference the pointer in global_var. */
g();
}
```
```
......it's possible that the compiler can perform some analysis to
establish that the called function does not in fact dereference the
pointer to the local variable. But given the compilation model typically
used by C compilers, it is optimistic to expect them to perform such
analysis.
```
也就是說，如果我們使用的編譯器有辦法去判定 `g()` 內有沒有去做對 `global_var` 的 dereference，就有辦法在這裏施加 TCO
#### gcc 的 TCO 行爲
改寫實驗的程式，讓 `g()` 沒有去做 x 的 dereference
```clike=
#include <stdio.h>
void g();
void f(void) {
int x = 3;
g();
}
void g() { int a = 1; printf("hello %d\n", a); }
int main() {
f();
return 0;
}
```
編譯時期打開 先是 -O0，查看 .s 檔 [線上看](https://godbolt.org/z/AmZQQb)
```
f:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $3, -4(%rbp)
movl $0, %eax
call g
nop
leave
ret
.LC0:
.string "hello %d\n"
g:
pushq %rbp
movq %rsp, %rbp
subq $16, %rsp
movl $1, -4(%rbp)
movl -4(%rbp), %eax
movl %eax, %esi
movl $.LC0, %edi
movl $0, %eax
call printf
nop
leave
ret
main:
pushq %rbp
movq %rsp, %rbp
call f
movl $0, %eax
popq %rbp
ret
```
可以看到 f 和 g 的呼叫都有牽涉到
```
pushq %rbp
movq %rsp, %rbp
...
ret
```
也就證明了 GCC 在沒有優化的時候是有讓每一個 function call 都建立一個 stack frame 的
若開啓 -O2
```
.LC0:
.string "hello %d\n"
f:
movl $1, %esi
movl $.LC0, %edi
xorl %eax, %eax
jmp printf
g:
movl $1, %esi
movl $.LC0, %edi
xorl %eax, %eax
jmp printf
main:
subq $8, %rsp
movl $1, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
addq $8, %rsp
ret
```
f 和 g 內都沒有繼續做 新增 stack frame 的動作
:::warning
疑問
code [線上看](https://godbolt.org/z/S9Vi07)
題目原本的例子
```clike=
#include <stdio.h>
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) {
printf("%d\n", *p);
}
int main() {
f();
}
```
編譯出來的結果如下
```
.LC0:
.string "%d\n"
f:
movl $3, %esi
movl $.LC0, %edi
xorl %eax, %eax
jmp printf
g:
movl (%rdi), %esi
xorl %eax, %eax
movl $.LC0, %edi
jmp printf
main:
subq $8, %rsp
movl $3, %esi
movl $.LC0, %edi
xorl %eax, %eax
call printf
xorl %eax, %eax
addq $8, %rsp
ret
```
看起來是有進行 TCO ！！
然而若修改程式碼內的 `g()`
```clike=
void g(int *p) {
printf("%d\n", *p);
printf("%d\n", *p);
}
```
則從新編譯的結果變成
```
.LC0:
.string "%d\n"
g:
pushq %rbx
movl (%rdi), %esi
movq %rdi, %rbx
xorl %eax, %eax
movl $.LC0, %edi
call printf
movl (%rbx), %esi
movl $.LC0, %edi
xorl %eax, %eax
popq %rbx
jmp printf
f:
subq $24, %rsp
leaq 12(%rsp), %rdi
movl $3, 12(%rsp)
call g
addq $24, %rsp
ret
main:
subq $24, %rsp
leaq 12(%rsp), %rdi
movl $3, 12(%rsp)
call g
xorl %eax, %eax
addq $24, %rsp
ret
```
突然就沒有 TCO 了
因此這裏的猜測是，當`g()` 內只有一個 `printf()` 的時候，程式碼的流程如下
* `main` 呼叫 `f()`
* `f()`的stack frame 被建立出來
* 到了呼叫 `g()` 的時候，編譯器判斷 `g()` 內只需要 dereference `x` 一次，因此直接把 `f()` 的 stack frame 重用，也就是做 TCO，變成 `printf` 使用的stack frame，結束了也是return 回一樣的地址，也就是 `main()`
當`g()` 內有兩個 `printf()` 的時候，程式碼的流程如下
* `main` 呼叫 `f()`
* `f()`的stack frame 被建立出來
* 到了呼叫 `g()` 的時候，編譯器判斷 `g()` 內需要 dereference `x` 兩次，而且第一個 `printf()` return 的地址是 `g()` 內，然後再一次dereference `x`，也就是說 `f()`的stack frame 並沒有重用，而且編譯器額外建立了 `g()` 和 第一個`printf()` 的 stack frame，第二個 `printf()` 的 stack frame 與 `g()` 共用，結束後直接 jump 回 `f()`
感謝`aben20807` 發現這個問題並且一起探討
:::
#### __builtin_return_address
持續更新中
## 2018q3 第 4 週測驗題 (中)
#### 原題目
```clike
int main() {
int *ptr = 0;
return *ptr;
}
```
根據 6.3.2.3 -- 3
>An integer constant expression with the value 0, or such an expression cast
to type void *, is called a null pointer constant.
If a null pointer constant is converted to a pointer type, the resulting
pointer, called a null pointer, is guaranteed to compare unequal
to a pointer to any object or function.
>
（[維基](https://en.wikipedia.org/wiki/Null_pointer)）對 null pointer 做 dereference 是 undefined behaviour。找不太到C 規格書內這一段的定義。
#### 題目一
```clike=
int main() { return *((int *) 0); }
```
根據 6.6 - 9
>An address constant is a null pointer, a pointer to an lvalue designating an object of static storage duration, or a pointer to a function designator; it shall be created explicitly using the unary & operator or an integer constant cast to pointer type, or implicitly by the use of an expression of array or function type. The array-subscript [] and member-access . and -> operators, the address & and indirection * unary operators, and pointer casts may be used in the creation of an address constant, but the value of an object shall not be accessed by use of these operators.
>
:::info
疑問
這一段有一句 it shall be created explicitly using the unary & operator or an integer constant cast to pointer type，所以上述程式碼其實是可行的，只是因爲 0 是 null constant，被cast 成 pointer 了過後成了 null pointer，不知道這樣的解釋對不對？
:::
#### 題目二
```clike=
int main() { return &*((int *) 0); }
```
根據 6.5.3.3 註解 84
> ...&*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. If *P is an lvalue and T is the name of
an object pointer type, *(T)P is an lvalue that has a type compatible with that to which T points.
>
因此若題1 的解釋成立的話，就代表這段程式碼只是在return 一個 null pointer，並沒有對 null pointer 做 dereference
```
test.c: In function ‘main’:
test.c:1:21: warning: return makes integer from pointer without a cast [-Wint-conversion]
int main() { return &*((int *) 0); }
^~~~~~~~~~~~~
```
因爲是return 一個 null pointer，且 constant value 爲0，但是main 的 return type 是int，因此顯示形態錯誤
#### 題目三
```clike=
#include <stddef.h>
int main() { return &*NULL; }
```
根據 6.5.3.3 註解 84
> ...&*E is equivalent to E (even if E is a null pointer),...
因此只是return NULL，跟題2 一樣
#### 題目四
```clike=
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
:::warning
更新中
:::
Sign in with Wallet
Connect another wallet