# 2019q3 Homework1 (review)
contributed by < `davinais` >
###### tags: `sysprog` `sysprog2019`
## 作業要求
* 從 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing), [第 1 週測驗題](https://hackmd.io/@sysprog/HksKVpUIr) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」
* 應當包含 [課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing) 的 Page 9 到 Page 16 裡頭的 C 語言程式設計議題
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗==
* 閱讀 [第一週課程進度](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 所有材料，記錄所見所聞並提問，若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::
## 問題討論
### 問題 1
[課程簡介和注意須知](https://docs.google.com/presentation/d/1Wo22s5aYuuyry97-z2MMmUmdxhjD0wKTdhxIW5oqjvo/edit?usp=sharing) Page 11
考慮以下程式碼：
```c
#include <stdio.h>
int main() {
return (*******puts)("Hello");
}
```
能否編譯執行？若可，為什麼？
#### 初步思考
說來慚愧，雖然以前就有先讀了一些 [你所不知道的C語言](/@sysprog/HJpiYaZfl?type=view) ，也知道 Function Pointer，但是一開始看到還是傻住了。只能說沒有讀得很精熟，必須要再重新複習一遍。
回歸正題，當我們直接拿去編譯後，我們發現編譯是會正確通過的，也能夠正常執行，顯然 `(*******puts)("Hello")` 應該是與 `puts("Hello")` 等價的。
可以拿以下的例子來實驗，我們直接印出 `func` 等，看看能不能編譯以及會出現什麼結果：
```c
#include <stdio.h>
void func() {
printf("In func!\n");
}
int main(void) {
printf(" func: %p\t\t *func: %p\n", func, *func);
printf("**func: %p\t\t***func: %p\n", **func, ***func);
func();
(*func)();
//*func(); /* error: indirection requires pointer operand ('void' invalid) */
return 0;
}
```
結果編譯正常，而且印出來的位址都一樣，看起來我們不管加了幾個`*`，都可以呼叫到同個函式。不過加上 `*` 後在呼叫時如果沒有補上括號將 `func` 包起來，那麼就會因為結合順序的關係先與後方的括號結合，
至於為什麼呢？不妨讓我們看看原本的規格書標準吧。
#### Function designator
首先，先來讓我們了解一下 function designator ，函式指定符，其實就是函數的名字啦。在 C99 規格書裡面其實是有詳細規範 function designator 的：
> A function designator is an expression that has function type.
> Except when it is the operand of the `sizeof` operator or the unary `&` operator, **a function designator with type ‘‘*function returning type*’’ is converted to an expression that has type ‘‘*pointer to function returning type*’’.**
> [name=［6.3.2.1-4］ in C99 ]
也就是說除了 單元 `&` 取址運算以及 `sizeof` 運算，所有的 function designator with type 'function returning type' 都會被轉成 pointer to function 的表達式。
我們現在知道了函數名稱代表了什麼，那麼我們在前面加上一堆 `*` ，或者是在 function designator 經過 單元 `&` 運算子運算之後會變成什麼呢？於是我們勢必也得熟悉一下這兩個運算子。
#### Address and indirection operators
> #### Constraints
> 1. The operand of the unary `&` operator shall be **either a function designator, the result of a `[]` or unary `*` operator,** or an lvalue that designates an object that is not a bit-field and is not declared with the `register` storage-class specifier.
> 2. The operand of the unary `*` operator **shall have pointer type**.
>
> [name=［6.5.3.2］ in C99 ]
首先我們得知了 單元`&`運算子 可以接受 function designator 以及 單元`*`運算子的結果 作為運算元，而 單元`*`運算子 則只接受 pointer type 作為運算元。
再來看看他們代表的意義，以及他們的運算結果會是什麼：
> #### Semantics
> 3. The unary `&` operator yields the address of its operand. **If the operand has type ‘‘*type*’’, the result has type ‘‘pointer to *type*’’.** **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.** Similarly, if the operand is the result of a `[]` operator, neither the `&` operator nor the unary `*` that is implied by the `[]` is evaluated and the result is as if the `&` operator were removed and the `[]` operator were changed to a `+` operator. Otherwise, the result is a pointer to the object or function designated by its operand.
> 4. The unary `*` operator denotes indirection. **If the operand points to a function, the result is a function designator**; if it points to an object, the result is an lvalue designating the object. If the operand has type ‘‘pointer to *type*’’, the result has type ‘‘*type*’’. If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined.
>
> [name=［6.5.3.2］ in C99 ]
有點多，不過基本上有關於本題的部分只要看粗體就可以了。
首先規格書提到了 單元`&`運算子 結果將產生其運算元的位址，即為取址。如果該運算元有 ‘‘*type*’’ 型態，則結果將會有 ‘‘pointer to *type*’’ 型態；而如果運算元是 單元`*`運算子 的結果，那麼基本上 `&` 跟 `*` 都不求值，類似於直接忽略，但是結果不會是 lvalue。
:::info
我原本以為是抵銷的，結果才發現結果有些差異，並不是完全相等，像是這樣一來他就沒辦法再用 `&` 取址。
:::
再來 單元`*`運算子 代表的是 indirection，也有人稱他為 dereference。這裡提到如果運算元 points to a function 的話，那麼結果會是 function designator。
如此一來便可以解釋 `(*******puts)("Hello")` 的運作邏輯了，首先我們必須先對 `(*******puts)` 求值，而我們能將該段程式碼看成 `(*(*(*(*(*(*(*(puts))))))))` 來依序拆解：
1. `(puts)`： `puts` 是 function designator，根據 C99［6.5.3.2-4］，我們可以將它轉換成 pointer to function return type。
2. `(*(puts))`： 單元`*`運算子碰到了 points to a function，結果輸出 function designator，能被轉換成 pointer to function return type。
3. `(*(*(*(*(*(*(*(puts))))))))`： 後面就是一直重複第二步，因此最後輸出的還是 function designator。
可以知道 `(*******puts)` 跟 `puts` 的結果輸出並沒有什麼不同，因此可以正常被呼叫。
解決了 `(*******puts)` 的問題，不過其他情況下會如何呢？稍微做一點實驗試試看：
```c=
#include <stdio.h>
int times = 0;
void func() {
printf("[%d] In func!\n", ++times);
}
int main(void) {
func();
(*func)();
(&func)();
(&*func)();
(*&func)();
//(&&*func)(); /* error: expected identifier */
(&*&func)();
(&***func)();
(****&func)();
(*&*&*&func)();
(&*&*&*&func)();
void (*fptr)(void);
fptr = func;
fptr();
(*fptr)();
//(&fptr)(); /* error: called object type 'void (**)(void)' is not a function or function pointer */
(&*fptr)();
(*&fptr)();
void (**fptrptr)(void);
fptrptr = &fptr;
//(fptrptr)(); /* error: called object type 'void (**)(void)' is not a function or function pointer */
(*fptrptr)();
(********fptrptr)();
return 0;
}
```
我們可以發現雖然 `(&*&func)()` 可以被正確的解讀（因為`&*`大致上可視為忽略，剩下`(&func)()` 視為 pointer to function，但不可作為 lvalue ）；但是 `(&&*func)()` 右側的 `(&*func)()` 雖然可以當作 function designator，但是無法當作 lvalue，因此無法再用 `&` 取址，跳出 expected identifier 的錯誤。
:::info
不過其實我沒有很明白為什麼是 expected identifier，因為規格書好像沒有特別寫到 `&` 不能接受 lvalue ？
:::
### 測驗 2
#### 題目
考慮以下 C 程式可取得以 `sizeof(int)` 為 alignment 基礎的整數空間，也就是說，當 `sizeof(int)` 為 `4` 的時候:
* 給定 `char arr[13];`，`INT_SIZE_OF(arr)` 要得到 `16`;
* 給定 `short int s;`，`INT_SIZE_OF(s)` 要得到 `4`
```c
#include <stdint.h>
#define INT_SIZE_OF(n) \
((sizeof(n) + sizeof(int) + X) & ~(sizeof(int) + Y))
```
`X` = ? `Y` = ?
:::warning
`X` = -1, `Y` = -1
:::
#### 運作原理
這其實與測驗的第1題 `align4(x)` 有些關係，雖然我一開始以為 round-up 是一捨二入所以選了 `K` = 2，~~真是可惜~~。
原本第1題的 align 巨集長的像下面這樣：
```c
#define align4(x) (((x) + 3) & (-4))
```
沒辦法直觀看出來，沒關係，把他轉成二進位來看看。
- $-4_{10} = 11...1100_{2}$ （二補數情況下）
從 -4 已經能看出，其實這就是一個 mask ，除去後面兩位數字只保留前面的部分，與先右移兩位再左移兩位的情況相同。至於為什麼要 +3 ？這是為了讓後面兩位在 1 以上時直接進位（$1+3=4$，所以只要在 1 以上就會進位），最後我們再去除後面兩位數字，便可以得到 align 過後的數字了。
那麼在這裡的 `INT_SIZE_OF(n)` 能否依樣畫葫蘆呢？當然是可以！
#### 依樣畫葫蘆
先觀察 `align4(x)` ，這個巨集的目的是要做 4-byte alignment，因此只要 $x \mod 4 \gt 0$ 的話就需要多一個 4-byte 來儲存，以至於會進位。為了讓他在 $\gt 0$ 時會進位，我們可以加上一個數字，讓 $x \div 4$ 的餘數與他相加之後能夠進位，最後捨棄末兩位便能達成效果。
因此：
- 選擇 $+3$ ， 為了使餘數不為 0 時進位，只要確保餘數在 1 以上時會進位即可，**選擇 $4-1=3$ ，意即 $+3$ 即可達成效果**。
- Mask 選擇 $-4$ 作 AND，這是因為 $-4_{10} = 11...1100_{2}$，拿來做 AND 運算剛好就能捨棄掉末兩位，**其中 $-4$ 其實就是我們要做的 N-byte alignment 中的 N 取負數**。
依此類推，我們這裡要以 `sizeof(int)` 作為 alignment 基礎，也依照上述方式選擇 `X` 與 `Y` 即可：
- `X`： 需確保餘數在 1 以上會進位，選擇 $\text{sizeof(int)}-1$ ，因此 `X` = -1。
- `Y`： 將 `sizeof(int)` 取負數作為 Mask，二補數的計算方式為 $\neg x+1$ 或者是 $\neg(x-1)$，對照可知 `Y` = -1。
### 測驗 3
#### 題目
考慮以下 C 程式碼:
```c
#include <stdbool.h>
bool func(unsigned int x) {
return x && ((x & (~x + 1)) == x);
}
```
可改寫為以下等價的程式碼：
```c
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
請補完程式。
:::warning
Ans: Z = 1
:::
#### 初步思考
每次當我看到關於 bitwise 的應用或題目，只要不是能直觀理解用途的，都感到傻眼以及讚嘆「這種東西到底是怎麼想出來的？」
回到正題，剛開始看到 bitwise 的部份，我只知道 `~x + 1` 是將 `x` 取 2 補數。在什麼情況之下 `x` 自身與他的 2 補數做 AND 運算會與自身相等，最後再判斷 `x` 是否非 0 後輸出結果？
在考試當下感到相當慌張，代了幾個數字都是 `False` 於是憑藉著一點對於補數的印象「碰巧」猜到了答案，事後檢討才發現實際上到底是在算什麼。
#### 代入數字
既然完全看不出來在幹嘛，那就直接代數字來看看吧，代多一點總能知道他在幹嘛了吧？
試著將 `x` 代入由 0 到 16 的數字
| $x_{10}$ | $x_2$ | $(\neg x+1)_2$ | $x_2 \wedge (\neg x+1)_2$ |
| ---:|:-------:|:-------:|:-------:|
| 0 | $00000$ | $00000$ | $00000$ |
| 1 | $00001$ | $11111$ | $00001$ |
| 2 | $00010$ | $11110$ | $00010$ |
| 3 | $00011$ | $11101$ | $00001$ |
| 4 | $00100$ | $11100$ | $00100$ |
| 5 | $00101$ | $11011$ | $00001$ |
| 6 | $00110$ | $11010$ | $00010$ |
| 7 | $00111$ | $11001$ | $00001$ |
| 8 | $01000$ | $11000$ | $01000$ |
| 9 | $01001$ | $10111$ | $00001$ |
| 10 | $01010$ | $10110$ | $00010$ |
| 11 | $01011$ | $10101$ | $00001$ |
| 12 | $01100$ | $10100$ | $00100$ |
| 13 | $01101$ | $10011$ | $00001$ |
| 14 | $01110$ | $10010$ | $00010$ |
| 15 | $01111$ | $10001$ | $00001$ |
| 16 | $10000$ | $10000$ | $10000$ |
我們可以發現，當 `x` 為 2 的指數倍時，`x` 自身與 2 補數做 AND 的結果會與自身相同，而最後再判斷 `x` 是否為 0 將 0 剔除。可以大膽猜測本函數便是判斷「`x` 是否為 2 的非 0 指數倍」。
#### 原理探討
原理到底是什麼呢？我並不是很確定，但是當數字是 2 的正指數倍時，除了代表該數字的 bit 為 $1$ ，其他都會是 $0$ ；而其的 2 補數則是位於該位（含自身）左方所有的 bit 都會是 $1$ ，兩者做 AND 剛好就只剩下原本數字的 bit。
其他的數字則不盡然，如**奇數的話最低位必定為 1** （因為原本的數字最低位就是$1$，做 NOT 之後再加 `1` 最低位仍然會是 $1$），因此除了 `1` 以外的數字都不會與自身相等，而 `1` 恰好為 2 的指數倍。
**偶數的話則會出現的是該數字擁有的為 2 指數倍之最大因數**，如 `14` 的話會出現 `2` ， `12` 的話會出現 `4`，這可以直接的從二進位理解，當從某位數到最低位的數值皆為 $0$ 時，代表右移並不會有餘數，那麼我們便能知道他擁有的為 2 指數倍的最大因數了。我們也能發現當 `x` 自身即為 2 的指數倍時，剛好便是特例，最大因數即為自身。
#### 適用負數？
那麼負數能否正確判斷呢？原本的 `x` 我們使用 `unsigned int` ，代表我們不必在意正負，但是如果只能用在正數未免有點侷限。這裡直接用正數的表即可反推負數的表，畢竟負數的 2 補數就是他的正數表示方式，很遺憾的是並沒有辦法，光是正數的 sign bit 必定為 0 就代表一定會失敗了。不過如果改成：
1. 採用 OR 而非 AND；或
2. AND 完的結果與其 2 補數比較而非與自身比較
應該就有辦法判斷負數了，因此我們若將原函數改成（採用第二種方法）：
```c
#include <stdbool.h>
bool func(unsigned int x) {
return x && (((x & (~x + 1)) == x) || (x & (~x + 1)) == (~x + 1));
}
```
應該就能將適用範圍擴展到負數。
#### 改寫
回到改寫後的程式碼：
```c=
bool func(unsigned int x) {
unsigned int unknown = 0;
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
return (unknown == 1);
}
```
如何找到 `Z` 讓它也能判斷 `x` 是否為非 0 的 2 指數倍？我們先發現到我們回傳的值：
```c=8
return (unknown == 1);
}
```
發現 `unknown` 為 1 時將會回傳 `true`，而同時我們知道在 2 的指數倍中，只有一個位數會是 $1$。那麼或許 `unknown` 代表的就是 $1$ 的個數？（這不就是 pop-count 嗎？）
```c=3
while (x && unknown <= 1) {
if ((x & Z) == 1)
unknown++;
x >>= 1;
}
```
觀察迴圈，當 `x` 為 0 以及 `unknown` 超過 1 時會中止迴圈，並且 `unknown` 只會在 `((x & Z)) == 1` 時增加，那麼這行一定就是關鍵判斷式了，由於後面我們能看到每次迭代中， `x` 都被右移一位，可以猜測該行便是用來判斷目前的最低位是否為 $1$。
經過這樣簡單推理之後，即可得出 `Z` 應該要是 `1` 才能在最末位為 $1$ 時「必定」輸出 `1` 的結果。
#### 以 const-time 實作 popcount
既然剛剛都提到了 pop-count，那麼就以 pop-count 作為例子吧。
pop-count，全名是 population count，是拿來計算二進位下一個數字有多少個 0 問題，在計算 0-1稀疏矩陣或者是[字串間的漢明距離](https://zh.wikipedia.org/wiki/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB)等場合下十分有用。
最簡單的實作方法其實就像是題目改寫之後的那樣：
```c=
int popcount(unsigned int x) {
unsigned int ones = 0;
while (x) {
if ((x & 1) == 1)
ones++;
x >>= 1;
}
return ones;
}
```
這方法相當的直覺，但是有非 constant-time 的 loop 存在，可能會因為 side-attack 等造成一些資安威脅。
讓我們試著將 popcount 改寫成 constant-time 看看：
1. constant-time 有一種最簡單的方式，直接做一個 look-up table，用空間換取時間：
```c
#define CHAR_BIT 8 // 依照 char 的位元數
#define BIT2(n) n, n+1, n+1, n+2
#define BIT4(n) BIT2(n), BIT2(n+1), BIT2(n+1), BIT2(n+2)
#define BIT6(n) BIT4(n), BIT4(n+1), BIT4(n+1), BIT4(n+2)
#define BIT8(n) BIT6(n), BIT6(n+1), BIT6(n+1), BIT6(n+2)
#define TBL_LEN (1<<CHAR_BIT)
static const unsigned char TABLE[TBL_LEN] = {
#if (CHAR_BIT==8)
BIT8(0)
#elif (CHAR_BIT==7)
BIT6(0), BIT6(1)
#else
# error "BITX to be added here."
#endif
};
#undef TBL_LEN
int lookup_popcnt(unsigned int n) {
return TABLE[n & UCHAR_MAX]+
TABLE[(n>>CHAR_BIT) & UCHAR_MAX]+
TABLE[(n>>(CHAR_BIT*2)) & UCHAR_MAX]+
TABLE[(n>>(CHAR_BIT*3)) & UCHAR_MAX];
}
```
2. 也能夠運用平行加法的技巧來實現：
```c=
#define POW2(c) (1u<<(c))
#define MASK(c) (((unsigned int)(-1))/(POW2(POW2(c))+1u))
#define COUNT(x,c) ((x)&MASK(c)) + (((x)>>(POW2(c)))&MASK(c))
int parallel_popcnt(unsigned int n)
{
n=COUNT(n,0);
n=COUNT(n,1);
n=COUNT(n,2);
n=COUNT(n,3);
n=COUNT(n,4);
/* n=COUNT(n,5); for 64-bit integers */
return n ;
}
```
由2位1組開始，分別取出每組的高位與低位並且相加，再將1的個數直接存放在該組的位置。隨後合併相鄰的兩組繼續進行迭代，直到完成為止。
以下作為示範，假設原本有 8 位元數字 $10110101$，這裡以 $\hat x$表示高位， $\check x$ 表示低位：
1. 先兩兩分組： $\hat1\check0|\hat1\check1|\hat0\check1|\hat0\check1$
2. 以遮罩取出高位以及低位： $1|1|0|0$ 與 $0|1|1|1$
3. 兩者相加，代表該組 1 的個數： $01|10|01|01$
4. 重新迭代，四四分組： $\hat0\hat1\check1\check0|\hat0\hat1\check0\check1$
5. 以遮罩取出高位以及低位： $01|01$ 與 $10|01$
6. 兩者相加，代表該組 1 的個數： $0011|0010$
7. 再次迭代，八八分組： $\hat0\hat0\hat1\hat1\check0\check0\check1\check0$
8. 以遮罩取出高位以及低位： $0011$ 與 $0010$
9. 相加，代表該組 1 的個數： $00000101$
10. 迭代完成，因此 $10110101$ 總共有 $00000101_2=5_{10}$ 個 1
若數字是 $2^k$ 位元，則只需要 $k$ 次迭代必定可完成。
*本方法的圖解，圖片引用自[1]*
3. 不過現在部份 CPU 也已經有 popcnt 指令了，可以直接在組語呼叫就好了
Sign in with Wallet
Connect another wallet