2018q3 Homework4 (assessment)

# 2018q3 Homework4 (assessment) ###### tags: `System-Software-2018` Contributed by <[`DyslexiaS`](https://github.com/DyslexiaS)> ## 開發環境 ``` Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 2 Core(s) per socket: 2 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 61 Model name: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz Stepping: 4 CPU MHz: 1536.107 CPU max MHz: 2700.0000 CPU min MHz: 500.0000 BogoMIPS: 4389.96 Virtualisation: VT-x L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K NUMA node0 CPU(s): 0-3 ``` ## [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X) ### 題目與解答 + 利用**二補數**特性完成無分支版本的 `abs()` (取絕對值) ```c #include <stdint.h> int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } ``` ### 想法 1. 對一個數做絕對值之前，要先得知此數的正負號， `int64_t y` 就是取得 `x` 的 sign bit - 正整數： `y = 0b0000...0000` - 負整數： `y = 0b1111...1111` >規格書 **6.5.7 Bitwise shift operators** >The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of $\frac{E1}{ 2^{E2}}$. If E1 has a signed type and a negative value, the resulting value is implementation-defined. 由以上描述得知，若 E1 是 signed 且 negative ，會是 implemnetation-defined 。顯然，如果以上函式在對 `-1` 做 Right shift ，會將前面補 `0` 的情況下就會錯誤。 2. 接著，`x` xor `y` :`(x^y)` 對於原本就是正整數的數值不會有影響 3. 對於原本是負數的數值，在二補數的機制下，**x + ~x = -1** ，因此 **-x = ~x + 1** ，就是函式最後 `(x^y)-y` （將 bits 反轉再 $- (-1)$ ### 延伸問題 #### 1. overflow/underflow 問題要探討 overflow/underflow 的情況，通常都在數值為極端值時才會發生。 **Code：** ```clike #include <stdio.h> #include <stdint.h> #include <inttypes.h> int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } int main(void){ printf("INT_64MAX: %+"PRId64"\n", INT64_MAX); printf("abs(INT_64MAX): %+"PRId64"\n", INT64_MAX); printf("INT64_MIN: %+"PRId64"\n", INT64_MIN); printf("abs(INT64_MIN): %+"PRId64"\n", INT64_MIN); return 0; } ``` **Output:** ```shell INT_64MAX: +9223372036854775807 abs(INT_64MAX): +9223372036854775807 INT64_MIN: -9223372036854775808 abs(INT64_MIN): -9223372036854775808 ``` 和原先預想的結果一樣，在數值為負最小時會出現 underflow 的問題。 --- #### 2. pseudo-random number generator (PRNG) 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 abs64 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？) - 概念 PRNG都是通過一個內部狀態來進行運算，生成一個**看似隨機**的數列。常見的PRNG算法分為加密和不加密兩類，不加密算法一般比加密算法更快，但是不能在需要安全的情況下使用。各種算法的[優劣比較](http://gad.qq.com/article/detail/10069)，現在最廣泛被應用的算法為[線性同餘法（LCG）](https://blog.csdn.net/dukai392/article/details/71155740) - 利用 xorshift64 方式快速產生亂數 ```C static uint64_t r = 0xdeadbeef int64_t rand64() { r ^= r >> 12; r ^= r << 25; r ^= r >> 27; return (int64_t) (r * 2685821657736338717); } ``` >[code 說明](https://forum.mikrotik.com/viewtopic.php?t=100868) >constant 2685821657736338717LL which has a hex representation of 2545f491 4f6cdd1d where the space indicates the 32 bit boundary. This means that the largest multiplication result within a "32bit half" is 4f6cdd1d * (2**32 -1 ) < 4f6cdd1d00000000. Thus overflow will never occur. Note that additions are done only using 32-bit halves thus overflow can never occur. :::info 提問：看完對上面 code 的原理也還不是很了解，為什麼乘上 `0x2545f4914f6cdd1d` 可以預防 overflow，**[看不懂 xorshift generators](http://vigna.di.unimi.it/ftp/papers/xorshift.pdf)** ::: - 實做 **Code：** ```clike= #include <stdio.h> #include <stdint.h> #include <inttypes.h> #include <time.h> #define check_abs(x){ \ if (abs64(x)<0) \ printf("Overflow: %+"PRId64"\n", x); \ } int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } static uint64_t r = 0xdeadbeef; uint64_t rand64() { r ^= r >> 12; r ^= r << 25; r ^= r >> 27; return (uint64_t) (r * 2685821657736338717LL); } int main(){ time_t t1 = clock(); for(long long i=0; i<INT32_MAX; ++i){ check_abs(rand64()); } time_t t2 = clock(); printf("Time : %lf sec\n", (t2 - t1)/(double)(CLOCKS_PER_SEC)); return 0; } ``` **Output：** ```shell gcc int64_abs.c -o int64_abs ./int64_abs Time : 37.095627 sec ``` **gcc 優化：** ```shell gcc int64_abs.c -o int64_abs -O3 ./int64_abs Time : 19.307838 sec ``` 改成 Unrolling： ```clike= for(long long i=0; i<UINT32_MAX; i+=4){ check_abs(rand64()); check_abs(rand64()); check_abs(rand64()); check_abs(rand64()); } ``` ```shell ./int64_abs Time : 12.868990 sec ``` 測試 Unrolling 次數 ```shell ./int64_abs unrolling 4, Time : 12.868990 sec unrolling 8, Time : 12.193703 sec unrolling 16, Time : 11.810844 sec unrolling 32, Time : 11.615933 sec ``` Unrolling 的次數在數度上的提昇很有限 - 推測： `UINT32_MAX` 到 `UINT64_MAX` 還需要乘上 $2^{32}$ ，因此取秒數 $12*2^{32}$ 得出 51539607552 sec，換算一下大約為 1634 年，上面驗證絕對值的 `check_abs()` 也寫得很簡略，所以實際上會花更多時間來測試所有數值。 #### 3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關 ## [第 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` 編譯選項) 進行編譯，得到以下執行結果: ```shell $ 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` 等級) 編譯，會得到以下執行結果: ```shell $ 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: ```C void g(int *p); void f(void) { int x = 3; g(&x); } void g(int *p) { printf("%d\n", *p); } ``` 因為函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack。考慮以下程式碼: ```C= int *global_var; void f(void) { int x = 3; global_var = &x; ... /* Can the compiler perform TCO here? */ g(); } ``` ==答案==：只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會 ### 想法 - TCO：這種做法不只加快效率，也避免了可能 Stack Overflow 等問題。使用尾遞歸可以帶來一個好處：因為進入最後一步後不再需要參考外層函數（caller）的信息，因此沒必要保存外層函數的 stack，遞歸需要用的 stack 只有目前這層函數的，因此避免了 Stack Overflow 風險。 - 解釋因為在做 TCO 時會把 caller 的 stack 捨棄掉，但如果函式 `g` 對 `global_var` 指標作 dereference ，也就表示會用到函式 `f` 裡的變數 `x` ，若使用到外部變量將無法做 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 會遇到記憶體存取錯誤: ```shell $ cat ptr.c int main() { int *ptr = 0; return *ptr; } $ gcc -o ptr ptr.c $ ./ptr Segmentation fault: 11 ``` 分別考慮以下 4 個程式，探討其行為。 - [ ] `ptr1.c` ```C int main() { return *((int *) 0); } ``` ==答案：== `ptr1.c` 在執行時期，對 NULL pointer 做 derefrence 操作，會造成 Segmentation fault - [ ] `ptr2.c` ```C int main() { return &*((int *) 0); } ``` ==答案：== `ptr2.c` 是合法 C 程式，`&*` 抵銷回傳 `(int *) 0` ，故回傳為 `0`，在執行後可透過 `echo $?` 得到 exit code 為 `0` - [ ] `ptr3.c` ```C #include <stddef.h> int main() { return &*NULL; } ``` ==答案：== `ptr3.c` 是合法 C 程式，`&*` 抵銷回傳 `NULL` ，因此在執行後可透過 `echo $?` 得到 exit code 為 `0` - [ ] `ptr4.c` ```C #include <stddef.h> int main() { return &*(*main - (ptrdiff_t) **main); } ``` ==答案：== - `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` - `**main` ， `main` 本來是一個 function designator ，但因為不是搭配 `&`， `sizeof` 使用，所以會被轉成為 pointer to function，再被 * 轉成 function designator，然後又和 `*` 重複做一次上述步驟，最後才被 compiler 轉成 pointer to function - `ptrdiff_t` 是二個指標相減結果所擁有的有符號整數類型 - `&*` 抵銷，`(*main - (ptrdiff_t) **main)` 都是指向 `main` 的指標，因此相減為 `0` ### 延伸問題 #### 1. 參照 C 語言規格書，充分解釋其原理 - 對於一個無效的值做 dereference 是個為定義的行為 >C99[6.5.3.2] >If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined. :::success - 對一個數同時做 dereferencd 和 reference `&* x` ，可以將兩個一起抵銷，但是省略之後原本的數會變成 **lvalue** ::: - `(int *)0` is not an integer constant expression, although it is a constant expression. >C99 [6.5.3.2] >If the operand is the result of a unary * operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue. #### 2. 解析 clang/gcc 編譯器針對上述程式碼的警告訊息 **Code：** ```C int main() { return &*((int *) 0); } ``` **Output：** ```shell warning: return makes integer from pointer without a cast [-Wint-conversion] int main() { return &*(int *) 0; } ^~~~~~~~~~~ ``` **Analysis：** `&*` 抵銷之後，剩下的 `(int *) 0` 是 pointer，但回傳型態是 `int` ，把回傳型態改成 `int*` 便不會出現 warning --- **Code：** ```C #include <stddef.h> int main() { return &*NULL; } ``` **Output：** ```shell warning: dereferencing ‘void *’ pointer int main() { return &*NULL; } ^ warning: return makes integer from pointer without a cast [-Wint-conversion] int main() { return &*NULL; } ^ ``` **Analysis：** 第一個 warning，`void *` is called a null pointer constant，不可以對 `void*` 取值，因此需要先做 cast 第二個 warning 和上面那題一樣，把回傳型態 `int` 改成 `int*` ```clike #include <stddef.h> int* main() { return &*(int *)NULL; } ``` #### 3. 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler --- ## [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) ## Reference [隨機數常見算法優劣剖析](http://gad.qq.com/article/detail/10069) [Pseudo Random Number Generator Script (xorshift64* )](https://forum.mikrotik.com/viewtopic.php?t=100868) [尾調用優化](http://www.ruanyifeng.com/blog/2015/04/tail-call.html) [NULL與0的區別](https://kknews.cc/zh-tw/other/jvbymy.html)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.