# 2018q3 Homework4 (assessment)
<contributed by < [`siahuat0727`](https://github.com/siahuat0727) >
[作業 E05: assessment](https://hackmd.io/s/HJ236XI57)
### [第 4 週測驗題 (上)](https://hackmd.io/s/HyyxpJE5X)
考慮以下求絕對值的程式碼:
```C
#include <stdint.h>
int64_t abs64(int x) {
if (x < 0) return -x;
return x;
}
```
Q：移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼:
```C
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x A1 (A2 - 1);
return (x A3 y) - y;
}
```
A：
```C
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
```
這裡假設了 C 語言的 `>>` 是 [arithmetic right shift](https://en.wikipedia.org/wiki/Arithmetic_shift)。（C 語言標準沒有明確定義對於有符號數應該使用哪種右移，然而實際上幾乎所有編輯器都對其使用 arithmetic right shift）
#### 分析
+ 若 `x` 爲非負，則 `y` 爲 `0`，
`(x ^ y) - y`
= `(x ^ 0) - 0`
= `(x) - 0`
= `x`
+ 若 `x` 爲負，則 `y` 在二進制表示時全爲 `1`，或者十進制的 `-1`，
`(x ^ y) - y`
= `(~x) - (-1)`
= `~x + 1`
= `x` 的一補數 + `1`
= `x` 的二補數
= `-x`
#### overflow/underflow 議題
當 `x` 爲最小值 $-2^{-63}$ 時，`x` 沒有對應的正值表示，無論用 `-x` 或是 `x` 的二補數的方法都會得到 `x` 自己。
#### 撰寫 `abs64` 的測試程式
我想測試應該是針對例外（`x` 爲最小值）以外的情況。
要測試 $2^{64}$ 種情況太久，如 CSAPP 練習題 2.35，我們可以測試 `abs8` 來取代測試 `abs64` 。
```C
#include <stdio.h>
#include <stdint.h>
int8_t abs8_true(int x) {
if (x < 0) return -x;
return x;
}
int8_t abs8(int8_t x) {
int8_t y = x >> (8 - 1);
return (x ^ y) - y;
}
int main()
{
for (int i = -0x80; i <= 0x7F; ++i) {
if (abs8_true(i) != abs8(i)) {
fprintf(stderr, "wrong when calling abs8(%d)\n", i);
}
}
return 0;
}
```
:::info
不太懂 PRNG 是不是要以隨機取樣的方式來測試，如果真的有例外情況感覺被測到的機率很小？
:::
### [第 4 週測驗題 (中)](https://hackmd.io/s/Syl6me49Q)
`void *__builtin_return_address(unsigned int level)`
+ 若 level 爲 0，取得這個 function 的 return address
+ 若 level 爲 1，取得上一層 function 的 return address
+ 以此類推...
這裡以比較 caller（first_xxx）和 callee（second_xxx）的 return address，來判斷是否發生 TCO。（若兩者相同則表示呼叫 function 時沒有創建新的 stack frame => 發生 TCO）
---
1. :heavy_check_mark: TCO
```C
void second_zero (void) {
second_ra = __builtin_return_address(0);
}
void first_zero (void) {
first_ra = __builtin_return_address(0);
second_zero();
}
```
TCO 之前：(optimization flag `-O`)
```
<first_zero>:
sub $0x8,%rsp
mov 0x8(%rsp),%rax
mov %rax,0x20083d(%rip) # 201018 <first_ra>
callq 88e <second_zero>
add $0x8,%rsp
retq
```
可以看到 function call 之後就是 pop stack frame(`add $0x8, %rsp`) 然後 return (`retq`)，因此若重用 stack frame（只存了 return address），結果如下：(optimization flag `-O2`)
```
<first_zero>:
mov (%rsp),%rax
mov %rax,0x2007ad(%rip) # 201018 <first_ra>
jmpq 910 <second_zero>
```
---
2. :heavy_check_mark: TCO
```C
void second_one (int a) {
second_ra = __builtin_return_address(0);
}
void first_one (int a) {
first_ra = __builtin_return_address(0);
second_one(0);
}
```
```
<first_one>:
mov (%rsp),%rax
xor %edi,%edi
mov %rax,0x20079b(%rip) # 201018 <first_ra>
jmpq 920 <second_one>
```
---
3. :heavy_check_mark: TCO
```C
void second_zero_one (int a) {
second_ra = __builtin_return_address(0);
}
void first_zero_one (void) {
first_ra = __builtin_return_address(0);
second_zero_one(0);
}
```
```
<first_zero_one>:
mov (%rsp),%rax
xor %edi,%edi
mov %rax,0x20077b(%rip) # 201018 <first_ra>
jmpq 930 <second_zero_one>
```
---
4. :heavy_check_mark: TCO
```C
void second_one_zero (void) {
second_ra = __builtin_return_address(0);
}
void first_one_zero (int a) {
first_ra = __builtin_return_address(0);
second_one_zero ();
}
```
```
<first_one_zero>:
mov (%rsp),%rax
mov %rax,0x20075d(%rip) # 201018 <first_ra>
jmpq 940 <second_one_zero>
```
---
5. :x: TCO
```C
char second_ret_int_char (void) {
second_ra = __builtin_return_address(0);
return 0;
}
int first_ret_int_char (void) {
first_ra = __builtin_return_address(0);
return second_ret_int_char ();
}
```
```
<first_ret_int_char>:
sub $0x8,%rsp
mov 0x8(%rsp),%rax
mov %rax,0x200748(%rip) # 201018 <first_ra>
callq 950 <second_ret_int_char>
add $0x8,%rsp
movsbl %al,%eax
retq
```
這裡因爲 return type 的不同，導致 function call 之後不只是 pop stack frame 和 return，還有轉型 `movsbl %al,%eax` （根據 signed bit 設置 `%eax` 的高 24 位），所以沒辦法 TCO。
這是因爲若直接 `jmpq <second_ret_int_char>`，`second_ret_int_char` 只會設定 `%eax` 的低 8 位 `%al`，但 `first_ret_int_char` 的 caller 可以使用整個 `%eax`。
---
6. :x: TCO :question:
```C
int second_ret_char_int (void) {
second_ra = __builtin_return_address(0);
return 0;
}
char first_ret_char_int (void) {
first_ra = __builtin_return_address(0);
return second_ret_char_int ();
}
```
```
<first_ret_char_int>:
sub $0x8,%rsp
mov 0x8(%rsp),%rax
mov %rax,0x200728(%rip) # 201018 <first_ra>
callq 960 <second_ret_char_int>
add $0x8,%rsp
retq
```
:::info
這裡是 int 轉 char，不需要額外的指令轉型（直接讀 `%eax` 的低 8 位 `%al`），所以我想其實是可以進行 TCO 的？
:::
---
7. :heavy_check_mark: TCO
```C
int second_ret_void_int (void) {
second_ra = __builtin_return_address(0);
return 0;
}
void first_ret_void_int (void) {
first_ra = __builtin_return_address(0);
second_ret_void_int ();
}
```
```
<first_ret_void_int>:
mov (%rsp),%rax
mov %rax,0x20070d(%rip) # 201018 <first_ra>
jmpq 970 <second_ret_void_int>
```
`first_ret_void_int` return type 爲 `void`，所以可以 TCO。（無視 `second_ret_void_int` 的 return value）
---
```
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
```
[Tail Calls and C](https://david.wragg.org/blog/2014/02/c-tail-calls-1.html)
Sign in with Wallet
Connect another wallet