# 2018q3 Homework4 (assessment)
## 測驗 `1`
對於位元運算總是覺得不夠熟悉，所以決定重新整理一篇重點。
C語言中與位元相關的運算子有：
&, |, ~, ^, >>, << 。
- 其中
- ＆： and
- | ： OR
- ~ ： Not
- ^ ： Xor
- *>>： 右移（除法）
- <<： 左移（乘法）
技巧：
-
- ＆
A & 0 = 0
A & 1 = A
任一數A與0的& 運算等於0。任一數A與1的 & 運算等於A。**利用與0的 & 運算可以將某位元設成0**。(兩者之中必須皆為1才得1其他皆為0)
- ｜
A ｜ 0 = A
A ｜ 1 = 1
任一數A與0的|運算等於A。任一數A與1的 | 運算等於1。**利用與1的 | 運算可以將某位元設成1。**（兩者皆為0才為0，其他為1）
- ^
A ^ 0 = A
A ^ 1 = A = not A = A’
任一數A與0的 ^ 運算等於A。任一數A與1的 ^ 運算等於Not A = A’。**利用與1的 ^ 運算可以將某位元將某位元反相，0<=>1。**（兩者皆不同才為1，其他為0）
考慮以下求絕對值的程式碼:
```C
#include <stdint.h>
int64_t abs64(int x) {
if (x < 0) return -x;
return x;
}
```
移除分支並善用[二補數](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;
}
```
請補完，其中 `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 數值範圍測試完畢？)
```C
static uint64_t r = 0xdeadbeef
int64_t rand64() {
r ^= r >> 12;
r ^= r << 25;
r ^= r >> 27;
return (int64_t) (r * 2685821657736338717);
}
```
3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
:::
---
## 輔助工具：gdb
在GDB打印內容技巧：p/（要打印的格式） 變數
print的输出格式包括：
x 按十六進位格式顯示變量。
d 按十進位格式顯示變量。
u 按十進位格式顯示變量無符號形式。
o 按八進位格式顯示變量。
t 按二進位格式顯示變量。
a 按十六進位格式顯示變量。
c 按字符格式顯示變量。
f 按浮点數顯示變量。
在進行這個題目之前，必須先了解什麼是2補數，我們都知道1補數是指原來的數值作 `~ `的運算。然而一補數本身的結構並不完善（+0和-0），於是c語言利用2補數來完整了整個正負數的運算，概念如下：
由底下的圖我們不難發現，其實2補數就是1補數再加1。亦即：a+~a=-1，即任何數與其補數相加為 -1。
### 想法與思考
一開始拿到本題的時候，可以先用一個數值當作例子代進去作思考，例如：-96，首先由上圖可知，-96用二進位格式表示的話，會是`1111111111111111111111111111111111111111111111111111111110100000 ` （在16進制的表示中宣告方式為0x10..060)從題目的暗示中，我們必須先作到一補數才能去找2補數，也就是我們真正的答案。所以我們要想怎麼樣才能達到`~ `的效果。由上述補充我們可以知道和1去做 ^ 運算可以將某位元將某位元反相。也就是說我們要創造一個全部都是1的64位元數（亦即-1），透過位移63（因為題目強調任何數）在不管輸入任何再小的負數都可以確保所有位元皆為1，但對於對有號數進行右移或左移不免讓我產生疑惑，確認一下規格書。
[C99 3.4.1](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 對於 implementation-defined behavior 的解釋。
:::warning
Unspecified behavior where each implementation documents how the choice is made. An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.
:::
做 `>>` 運算 [C99 6.5.7](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 的解釋。
:::warning
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 $E1 / 2^{E2}$. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
亦即E1 >> E2 的值是 E1 向右移位 E2 個位元位置。 如果 E1 的類型不帶正負號，或者 E1 的類型帶正負號且具有非負數值，則結果的值會是 $E1 / 2^{E2}$ 商數的整數部分。 如果 E1 的類型帶正負號，且具有負數值，結果產生的值由實作決定。
:::
由此可知對於負數作位移是最終會產生-1。經過（x^y）運算後得出來的值為x的1補數，而由我上述所提到的，2補數為1補數+1，透過負負得正，減掉-1後即為+1。本題結束，底下是用gdb作的實驗。
```bash
(gdb) p/t x
$3 = 1111111111111111111111111111111111111111111111111111111110100000
(gdb) p/t x>>63
$14 = 1111111111111111111111111111111111111111111111111111111111111111
(gdb) p/t x^y
$11 = 1011111
(gdb) p/d x^y
$12 = 95
```
設計實驗：首先我們要先知道2的63次方為9223372036854775808，所以`int64_t`的範圍為 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807，區域為 18,446,744,073,709,551,616 。底下的實驗我們可以看到，如果我們輸出，得到的y值居然是9223372036854775807，亦即系統出現了overflow。
```clike=
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
int main()
{
int64_t x=-9223372036854775808;
int64_t y;
y=x-1;
//x=~x;
abs64(x);
}
```
gdb測試結果
```bash
Breakpoint 2 at 0x4004de: file ptr.c, line 3.
(gdb) r
Starting program: /home/iclab/ctest/ptr
Breakpoint 1, main () at ptr.c:9
9 int64_t x=-9223372036854775808;
(gdb) n
11 y=x-1;
(gdb) n
13 int64_t m = 0x0000000000000030;
(gdb) p y
$1 = 9223372036854775807
p/t y
$2 = 111111111111111111111111111111111111111111111111111111111111111
```
測試程式執行時間：
```clike=
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include<math.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
int main()
{
clock_t start, end;
// Start Record the time
start = clock();
int64_t x;
int64_t y= -pow (10.0, 10.0);
for(x=y;x<=pow (10.0, 10.0);x++){
abs64(x);
}
//x=~x;
printf("test is done\n");
end = clock();
double diff = end - start; // ms
//printf(" %f ms" , diff);
printf(" %f sec\n", diff / CLOCKS_PER_SEC );
return 0;
}
```
執行時間為：
```cmake=
iclab@iclab:~/ctest$ ./ptr
test is done
57.046893 sec
```
上述的實驗為：對於-10億到+10億進行轉換和測試，而20億筆資料中，程式執行時間為57秒將近1分鐘，對於進行完全的測試與轉換大概是需要17536.6359484年的時間。
:::info
10/22新增：
sign extension 當最高位為1時，做位移運算會受到最高位位元的影響：
```clike=
int64_t x=-95;
int64_t y= 0x8100000000001111;
```
```cmake=
(gdb) p/t y
$1 = 1000000100000000000000000000000000000000000000000001000100010001
(gdb) p/d y
$2 = -9151314442816843503
(gdb) p/t y>>1
$3 = 1100000010000000000000000000000000000000000000000000100010001000
```
:::
## 測驗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` 編譯選項) 進行編譯，得到以下執行結果:
```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();
}
```
思考程式註解，在第 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) 的應用並解說
:::
在解說TCO之前就必須先講解什麼是遞迴（recursion）。
遞迴 (Recursion)，是指 一個函式 (或操作、方法、數列、演算法)，
會 直接 或 間接 地 呼叫自己本身。
也就是:
使用相同的方法，解決重複性的問題 (Recurrent Problems)。
不同於 非遞迴的 (Non-Recursive) 做法，
[e.g., 使用 迴圈 (loop)、判斷式 (decision)、賦值/指派 (assignment) ]
遞迴 (Recursive) 往往可用簡單、優雅的方式解決複雜的問題。
其中一種遞迴程式呼叫稱為尾端遞迴(tail recursion)。
這是實務上一種重要的遞迴種類，指的是具備:
- 直接遞迴 (direct recursion)
- 線性遞迴 (linear recursion)
- 函式執行的最後一件事 為遞迴呼叫，且 只能是遞迴呼叫
#### 函式呼叫
執行 Function A( ) 時，若需呼叫 Function B( )，
這時得
程式會建立一個 被稱為 活動紀錄 (activation record) 或 堆疊框 (stack frame) 的結構，保存 Function A ( ) 目前的執行狀態，並將其資訊 push 到 系統堆疊 (System Stack) 頂端， 包含 參數、區域變數、返回位置 (return address)。 控制權轉移，且做參數傳遞 (譬如 上圖的 x 與 y)。執行 Function B( ) 。 Function B( ) 執行完成，做判斷。
但就是因為這樣，所以每次的遞迴呼叫都會需要額外的記憶體 (系統堆疊)，來記錄每個遞迴的呼叫狀態！若遞迴呼叫過量使堆疊爆了，就會造成 Stack Overflow Error 。
這時的解決辦法便是：
- 尾端遞迴：
不增加 新的系統堆疊，而是用每次執行的結果，直接更新函示內容，這樣的做法稱為:
**尾端呼叫消除 (Tail Call Elimination, TCE) 或 尾端呼叫最佳化 (Tail Call Optimization, TCO)。**
參考網址：https://david.wragg.org/blog/2014/02/c-tail-calls-1.html
對於上述網址的作者做了一個實驗，那就是對於gloabl_var進行不同的函式改變： accessible_local和nested_scope還有_inline等等....來測試TCO是否能執行，如下：
```clike=
int *global_var;
void accessible_local(void)
{
int x = 42;
first_return_address = __builtin_return_address(0);
global_var = &x;
target();
}
void nested_scope(void)
{
first_return_address = __builtin_return_address(0);
{
int x = 42;
global_var = &x;
}
target();
}
static __inline__ void inline_bit(void)
{
int x = 42;
global_var = &x;
}
void with_inline_func(void)
{
first_return_address = __builtin_return_address(0);
inline_bit();
target();
}
```
發現對於gcc和clang來說，f函式仍舊無法執行TCO。
```cmake=
Tail call with exposed local var: no TCO
Tail call with exposed local var in nested scope: no TCO
Tail call with exposed local var in inline function: no TCO
```
我認為的原因是因為，對於上述函式來說，要存取到x的值必須要將區域變數x的值儲存起來，然而這樣便無法進行TCO，因為TCO會直接更新函式的內容而啟動的條件是該呼叫者不能佔用stack的記憶體，且直接回傳呼叫者的值。但很顯然的雖然target()函式並沒有對global_var 作dereference，但是若target()函式想要存取到x的值，其所在的函式（例如：accessible_local）便會將區域變數x儲存起來。因此答案為：(c) 只要函式 g 沒有對 global_var 指標作 dereference，那麼 TCO 就有機會。
## 測驗3
## 測驗 `3`
### 題目敘述
以下程式碼編譯並執行後，在 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); }
```
- [ ] `ptr2.c`
```C
int main() { return &*((int *) 0); }
```
- [ ] `ptr3.c`
```C
#include <stddef.h>
int main() { return &*NULL; }
```
- [ ] `ptr4.c`
```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
:::
- [ ] `ptr1.c`
```C
int main() { return *((int *) 0); }
```
先從外面開始看，首先*（）便是指去對括號內的取值（dereference），而`((int *) 0)`就是將`0x0`這個位址轉型為`int`型別的指標，對於一個未進行宣告的位址進行取值，是違法的，因此會產生 segmentation fault 的錯誤。
- [ ] `ptr2.c`
```C
int main() { return &*((int *) 0); }
```
根據c99規格書：
>**C99 Standard (§ 6.5.3.2) **
Thus, &*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.<
所以說 `return &*((int *) 0); ` 就等於` return ((int *) 0); `因此是可以編譯的過得。
- [ ] `ptr3.c`
```C
#include <stddef.h>
int main() { return &*NULL; }
```
和上面一題的概念類似，同樣也是`return NULL `是合法的程式。
- [ ] `ptr4.c`
```C
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
*main 會被轉為一個pointer to function，而根據c語言規格書：
```css=
When two pointers are subtracted, both shall point to elements of the same array object,or one past the last element of the array object; the result is the difference of the subscripts of the two arrayelements. The size of the result is implementation-defined,and its type (a signed integer type) isptrdiff_tdefined in the<stddef.h>header.If the result is not representable in an object of that type, the behavior isundefined. Inother words, if the expressionsPandQpoint to,respectively,thei-th andj-th elements ofan array object, the expression(P)-(Q)has the valuei−jprovided the value fits in anobject of typeptrdiff_t. Moreover, if the expressionP
points either to an element ofan array object or one past the last element of an array object, and the expression
Qpointsto the last element of the same array object, the expression((Q)+1)-(P)has the same§6.5.6 Language 83 ISO/IEC 9899:TC2Committee Draft — May 6, 2005WG14/N1124value as((Q)-(P))+1and as-((P)-((Q)+1))
, and has the value zero if theexpression P points one past the last element of the array object, even though the expression(Q)+1 does not point to an element of the array object.
```
兩個指標相減的結果是一個 (ptrdiff_t) 類別。而&*和上題一樣故為合理的c語言程式。
- [ ] `ptr2.c`
:::warning
test.c:6:13: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*((int *) 0);
:::
因為最後回傳的值和int main的型別不相同。
- [ ] `ptr3.c`
:::warning
test.c:6:14: warning: dereferencing ‘void *’ pointer
return &*NULL;
^
test.c:6:13: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*NULL;
:::
NULL 相當於 (void *)0 ， 不能對其做 dereference而且最後回傳的值和int main的型別不相同。
- [ ] `ptr4.c`
:::warning
test.c:6:13: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*((int *) 0);
:::
因為最後回傳的值和int main的型別不相同。同第二題
https://hackmd.io/s/HyELy5bTz
https://hackmd.io/s/SJ8y82ZYQ
```css=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
unsigned int fg_r=255;
unsigned int bg_r=4;
unsigned int out_r;
unsigned int alpha = 255;
unsigned int out_r_1;
unsigned int out_r_2;
unsigned int out_r_3;
int main(void) {
out_r = (fg_r * alpha + bg_r * (255 - alpha)) / 255;
out_r_1 = fg_r * alpha + bg_r * (255 - alpha);
out_r_2 = (out_r*alpha + out_r+alpha) >> 8;
out_r_3 = (out_r_1 + 1 + (out_r_1 >> 8)) >> 8;
printf("the value_0 is %3d\n\r",out_r);// your code goes here
printf("the value_1 is %3d\n\r",((out_r_1>>8)+out_r_1+256)>>8);
printf("the value_2 is %3d\n\r",out_r_2);
printf("the value is %3d\n\r",out_r_3);
//out_r_2 =
return 0;
}
```
Sign in with Wallet
Connect another wallet