# 2018q3 Homework4(assessment)
contributed by < `type59ty` >
###### tags: `sysprog2018`, `hw4`, `assessment`

---

## 2018q3 第 4 週測驗題 (上)
### 測驗 `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 = >>

A2 = 64

A3 = ^

:::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 找出類似用法的專案並探討，提示：密碼學相關
:::

### 想法：
原始程式碼非常直觀， input x 小於0 的話就加個負號，讓它變成正數，但這必須用到判斷式 if ，如果要拿掉判斷式該怎麼改呢？
題目給了提示： 用二的補數，因為我們的目標是要檢查正負號，所以可以從 ==sign bit== 下手
- 先從 function 內的第一行開始看

int64_t y = x A1 (A2 - 1);

y 是一個 64 bit 整數，其內容是由 x 作某些操作而得到的，推測這個動作是要取 sign bit，而 sign bit 就是第 63 個 bit ，因此 A2 = 64，那又該如何從 x 身上取出這個 bit 呢？ 這邊就可以用 bit-wise operation，直接將 x 右移63次，剩下的就只有 sign bit ，如此就可以把它存入 y

- 第二行

return (x A3 y) - y;

>x: input
y: 64 bit 的 sign bit ( 11...111 或 00...000 )

x 和 y 作某種運算，出來的結果再減掉 y ，根據題目的線索，這邊應該要用二的補數來處理

二的補數其實就是先做一的補數，結果出來再加1，參考 [有號數字表示法 — 2 的補數、1 的補數 與 符號大小](https://notfalse.net/20/signed-number-representations)
- 1 的補數 (Ones’ Complement)，又稱 反碼 ，欲計算負值:
藉由 反轉/反向 ( inverse ) 每一個位元，原本是 『 1 』 就變 『 0 』，『 0 』就變 『 1 』
- 2 的補數 (Two’s Complement)，或稱 補碼:
1 的補數 + 1

因此推測 A3 應該用 ==^== ( xor ) operator
xor 真值表：
| $x$ | $y$ |$x \oplus y$|
|-- |-- |--|
| 0 | 0 | 0|
| 0 | 1 | 1|
| 1 | 0 | 1|
| 1 | 1 | 0|

考慮以下兩種情況：
1. $x > 0$
則 y = 00....000 ( 64 bit )
則 x ^ y = x
( $\because$不管 x 是0或1，跟0作 xor 運算結果都不會改變 )
而後面減 y 也不會變
$\therefore$ $x = x$

2. $x < 0$
則 y = 11....111 ( 64 bit )
則 x ^ y = $\overline x$
( 從真值表可看得出來 )
後面減掉 y 其實等同於 + 1
( $\because$ 負負得正 -(-1)=+1 )
$\therefore$ $x = -x$

到這邊就完成我們的目標了

### 延伸：
1. 0

2. 0

3. 0

---

## 2018q3 第 4 週測驗題 (中)
### 測驗 `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) 的應用並解說
:::

### 解釋：

### 延伸：

---

## 2018q3 第 4 週測驗題 (下)
### 測驗 `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)之啟發

部分節錄自原文：
> 當時許多創業團隊都在做網站平台和app，希望能成為下一個uber或airbnb，但我們從過去的經驗知道，平台比什麼都難做，想成為一個平台，需要撮合供給方和需求方，並且從中抽成獲得利潤。這是一個雞生蛋蛋生雞的問題，沒有人供給，就沒有需求方願意上來，沒有需求，就沒有供給方願意提供服務，平台必須要兩邊燒錢，燒到兩邊的人數大到能夠養活公司，才有可能做起來。
- 看到這段感觸很深，當初大三的時候因為專題製作 ( android app ) 接觸了學校的創新創業相關比賽，也有一段時間在我們學校的創夢工廠 (專門處理創業相關業務、培育創業團隊進駐) 工讀，過程中參與了很多創業相關的課程、各種團隊的簡報，有的天馬行空、有的看似很有搞頭，也聽了不少成功案例的分享，說們他們如何規劃商業模式、如何打破現實困境，讓我曾一度懷上了創業的夢想，但我最終並沒有跨出去，當時覺得自己技術能力不夠，且創業成功率極低，根本**沒有勇氣跟別人不一樣**，所以我走上跟多數人一樣的路：考研究所、準備未來到公司上班。

> 大多數人一直活在本來就應該這樣嗎的童話世界裡，電視打開就可以看，機車買來就可以騎，手機買來就可以用，一切都理所當然，本來就應該這樣。偶爾買到不好用的商品我們就抱怨幾句，丟掉換其他更好用的牌子，卻很少意識到那個本來就該這樣，背後需要經過多少人月的投入與研發。
- 這就是現實！

雖然不知道作者後來有沒有回收成本，但我想那已經不重要了，這種經驗絕對不是一般人能擁有的，想必要有相當大的勇氣跟毅力，面對自己不熟悉的領域與未知的結果，還能毅然決然做下去，真的是讓我非常佩服，因為有太多人都是紙上談兵，真的敢嘗試的且堅持到最後的人不多，也讓我再一次反省，之前浪費了多少青春。

::: info
「Jserv說你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已。」
:::
遇到困難要想辦法克服，現在遇到的困難也絕不會是這輩子最大的困難，如果選擇逃避，未來只會重蹈覆徹，所以我想告訴自己：勇敢克服問題吧！

## 課程感想

作業很難，但人生更難，這點小困難跟作者做飲料機過程遇上的困難應該不足為道吧，何況這些都是自己領域的東西，更不該逃避！