# 2018q3 Homework4 ([assessment](https://hackmd.io/s/HJ236XI57))
contributed by < [wingard](https://github.com/wingard) >

###### tags: `HW4`

## 作業要求

1. 重新作答 [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X), [第 4 週測驗題(中)](https://hackmd.io/s/Syl6me49Q), 和 [第 4 週測驗題(下)](https://hackmd.io/s/By7Lwz4qm) 所有題目，比照 [bit-reverse](https://hackmd.io/s/ByzoiggIb) 共筆的方式，提及你的想法、解題思緒，還有參照到的材料，需要一併作答「延伸題目」。若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::
2. 紀錄閱讀 [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) 的啟發，特別在學習本課程 4 週之後的感想

## [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X)
考慮以下求絕對值的程式碼:

#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 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` ==>>==

A2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 61
* `(d)` 62
* `(e)` 63
* `(f)` ==64==

A3 = ?
* `(a)` &
* `(b)` |
* `(c)` ==^==
* `(d)` <<
* `(e)` >>

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

---
### 想法

* 參考[ Bit twiddling hacks ](https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs)

//Compute the integer absolute value (abs) without branching
int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here 
int const mask = v >> sizeof(int) * CHAR_BIT - 1;
r = (v + mask) ^ mask;
// Patented variation:
r = (v ^ mask) - mask; 

* 由於電腦是以二補數來表示負數，表達格式是將 MSB 作為 sign bit，其餘 bit 則代表數值。二補數的好處在於：可以將減法運算（ a 減 b ）轉化成加法運算 (a 加上 b 的二補數)，同時可以直接捨棄加法過程中產生的 overflow

* mask 就是 v 的 sign bit ，存放在最低位元
* v >= 0 ： mask = 0
* v < 0 : mask = -1

* 將 v 與 mask 作 XOR 時，可以確保 MSB 的 sign bit 被消去

* 當 v 是正數時:
> `x >> 63` 是 0; `x ^ 0` 仍是 n; `x - 0` 仍是 n
* 當 v 是負數時:
> `n> > 63` 是 -1; `-1` 以 2 補數表示為 `0xFFFFFFFF`; `n ^ (-1)` 等同於 1 補數運算; 最後再減 `-1`，得到 2 補數運算的值

### 延伸問題
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);
}

程式碼使用了 [xorshift*](https://en.wikipedia.org/wiki/Xorshift#xorshift*) 的技巧，以下是簡介：

3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關

以下是使用的專案: [aiband](https://github.com/LispEngineer/aiband/blob/c29181401ba8767099aac52120651f99d36af7a3/Assets/aiband/rand-c.c)

---
## [第 4 週測驗題(中)](https://hackmd.io/s/Syl6me49Q)

考慮測試 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) 的應用並解說
:::

---

---
## [第 4 週測驗題(下)](https://hackmd.io/s/By7Lwz4qm)

以下程式碼編譯並執行後，在 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
:::

---
## 閱讀心得與啟發

1. 張同學十分有承擔風險的勇氣，願意為了實現夢想去用一年的時間實踐與驗證可行性，暫且不從延畢的世俗眼光想，這是一個完成度很高的軟硬體整合畢業專題！

3. 閱讀完之後的幾個(事後諸葛)的想法：
* 找尋學校的相關資源(育成中心之類)，多少可以申請經費或技術諮詢，實驗上比較不會被資金/技術問題限制。
* 一開始的市場研究偏向成本面(如果產品開發出來，要壓到多少成本才會有市場)，如果能多一些對於產品面的技術研究（市面上目前是否有類似的產品？市面上類似產品的核心/關鍵技術是什麼？關鍵技術是否有專利？)可以少走一些閉門造車 / try and error 的過程。
* 在工作上，會被要求做市占分析/競爭者分析/BOM Cost analysis /毛利預估

3. 關鍵的幾句話：
* 儘管世界如此殘酷，但人卻不一樣，當你真心想做到一件事，付出足夠的犧牲，這個世界會聽見並做出回應，周遭的人漸漸願意相信你、花時間幫助你，你的付出並不見得會有結果，但是加上許多人的幫助，可能一切就不一樣了。
* 對你而言真正重要的事物，會比你想得到的事物更早出現在路邊。

4. 從開課到現在，最大的感想是**自己真的有很多地方沒學懂** ，同時這門課的作業強度要求也超過我大學/碩士修過的任何一門課
* [作業一](https://hackmd.io/s/SkWIb_O_X)花的時間遠超過 35 小時(往 55 小時邁進，C 語言真的有很多我所不知道的阿...)，還有一些細節沒有理清
* 課後複習也十分吃力(例如 csapp3e 的第二章)

會繼續在工作與家庭之餘，努力抽時間寫作業(目前每份作業都只能寫一半不到阿，還是不夠努力)，讓自己再精進。