# c-review
contributed by <`afcidk`>
## [第四週測驗題(一)](https://hackmd.io/s/SyK-WApKM#%E6%B8%AC%E9%A9%97-1)
先觀察 struct node，發現有 data, prev, next 成員，可以猜測資料結構是 linked list。
* #### `FunA` 的作用
看到 `if (!*start)` 區塊，這個區塊會配置新空間給 `*start`，再將 value 放進去，next/prev pointer 指向自己，代表在一個 node 的時候會是雙向的 circular linked list。
再往下看，這個部份屬於 `*start ！= NULL` 。從
```
new_node->next = *start;
(*start)->prev = new_node;
new_node->prev = last;
```
可以知道新的 node 會插在 `*start` 前面，但是 `*start` 並沒有被更改，所以可以看成在 linked list 最後面插入數字。
因此 `FunA` 的作用是在 linked list 最後面插入 node ，如果 `*start 為 NULL`，則配置空間給他。
* #### `FunB` 的作用
和 `FunA` 很像，但是是插入在 `*start` 前面，最後再將 `*start` 指派給新配的 node ，所以可以看成在 linked list 最前面插入 node。
沒有處理 `*start==NULL` 的情形，改善方法參考 `FunA`。
* #### `FunC` 的作用
會先把 `value1` 放到 new_node 裏面，再從 linked list 裏面找到 value 為 `value2` 的 node，在後面插入。但是 `FunC` 並沒有處理到找不到 `value2` 的狀況，若發生會進入無窮迴圈
改善方法:
```
struct node *start_addr = *start; // record the first address
while (temp->data != value2) {
temp = temp->next;
if (temp == start_addr){ // break if met previous address
puts("Cannot find value, FunC failed and did not insert number.");
break;
}
}
```
:::info
發現 malloc 呼叫完不用轉型也可以 assign 給變數，編譯參數加上 `-Wall` 也不會跳出警告，但是如果加上 `-Wc++compat` 就會警告我們必須要轉型，因為在 C+\+ 中這是不允許的。為什麼在 C 裡面允許的方式 C\++ 要禁止？或是說為什麼 C 可以允許這種寫法？
:::
::: warning
或許是因為 C 假設寫程式碼的人都知道自己在做什麼，所以限制比較小？這樣可以增進效能或是有什麼優點嗎？
C 和 C++ 是不同的程式語言，去比較兩者對 type 的定義差別 :notes: jserv
:::
* #### Z1 ~ Z10
由上面對 `Fun[ABC]` 的分析，再一步一步跑 main 裡面的程式
* 插入 51， 現在是 51(s)
* 插入 48， 現在是 48(s), 51
* 插入 72， 現在是 48(s), 51, 72
* 插入 86， 現在是 48(s), 51, 72, 86
* 在 51 之後插入 63，現在是 48(s), 51, 63, 72, 86
觀察 `display()` ， traverse in forward direction 就是一直往後面找，當指標等於 `*start` 的時候就停止，也就是依序印出內容。
traverse in reverse direction 的迴圈會往前找，因為是雙向的 linked list，所以不會有指標為 `NULL` 的情形發生
## [第四週測驗題(二)](https://hackmd.io/s/SyK-WApKM#%E6%B8%AC%E9%A9%97-2)
* #### `FunX` 的作用
`FunX` 會順著 linked list 走下去。當發現是 circular 或是走到底的時候就會停下來，最後再回傳 node-head，可以用來判斷是不是 circular linked list，如果是會回傳 0 ，否則回傳非 0 數值。
在 for 迴圈裡面的 `data++` 沒有任何用途，猜測原本的用途應該是要在 `FunX` 裏面修改 `data` 的數值，程式碼應該要修改成 `(*data)++`，並且在函數一開始讓 `*data = 0`
* K1~K5 和 count 的數字
這段程式碼先建立基本的 linked list
```
struct node *head = node_new(0); // A(head)
head->next = node_new(1); // A->B
head->next->next = node_new(2); // A->B->C
head->next->next->next = node_new(3); // A->B->C->D
head->next->next->next->next = node_new(4); // A->B->C->D->E
```
然後檢查是不是 circular linked list，回傳非 0 ，輸出 YES
`head->next->next->next->next = head;`
現在結構變成 `A->B->C->D->A (circular)`，輸出 NO
`head->next->next->next->next->next = head->next;`
結構變成 `A->B->C->D->A (circular)`，輸出 NO
`head->next = head->next->next->next->next->next->next->next->next`
結構變成 `A->A (circular)`，輸出 NO
最後要輸出 `head->next->data`，這是 `A->data = 0`
因為剛才在 `FunX` 提到的缺陷，讓 count 無法更改數值，所以一直維持 0。
## [第五週測驗題(上1)](https://hackmd.io/s/SynmEVIqG)
考慮以下程式碼，推敲其作用
```clike
uint8_t Func32(uint32_t x) {
return x ? Func32(x >> 1) - 1 : 32;
}
```
先檢查 x 是不是 0 ，再將 x 向右位移 1 bit繼續遞迴下去。
直接從遞迴的最尾端往上想，最後一次遞迴一定是回傳 32，然後每次往回跑的時候都會遞減 1 ，因此可以判斷這個函式是用來 count leading zero。
將 `Func32` 改寫為以下功能等價的程式碼:
```
uint8_t FuncI(uint32_t x)
{
if (!x) return 32;
int n = 1;
if (!(x >> 16)) { n += 16; x <<= 16; }
if (!(x >> M1)) { n += 8; x <<= 8; }
if (!(x >> M2)) { n += 4; x <<= 4; }
if (!(x >> M3)) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
知道這個函式在算 clz 之後，再看就很容易了。
4 個 for 迴圈使用二分搜尋法來查看前 n bit 是不是 0 (有沒有 1 )，第一次找 16 bit ，第二次 8 bit... 依序這樣下去，可以推得 M1=24(16+8), M2=28(16+8+4), M3=30(16+8+4+2)。
如果沒有找到區間內存在 1 的話，就把範圍縮小（`x <<= n` 那部份）
最後面的 `n = n - (x >> 31);` 也可以按照上面四個判斷式的寫法寫成 `if (!(x >> 31)) {...}`，只是少了判斷式可以讓程式快一點而已，並且一開始 n 需要初始化為 0 。
### 在 x86_64/Aarch32/Aarch64 ISA 中找出對應於 `Func32` 的指令，隨後在 GitHub 專案中找到 3 個應用案例並解說
### 回顧 Week1 到 Week5 的教材和作業，提出可用對應於 `Func32` (或下方 `Func64`) 的指令加速的案例
## [第五週測驗題(上2)](https://hackmd.io/s/SynmEVIqG#%E6%B8%AC%E9%A9%97-2)
先了解各個函式和資料結構的功能或實現的原理
* `union u_word`: 用來儲存把 64-bit 數字拆成兩個 32-bit 的 struct 和用 64-bit 儲存的 union，兩者記憶體空間共享（大小一樣）。
```clike
union u_qword {
struct {
uint32_t low;
uint32_t high;
} dwords;
uint64_t qword;
};
```
* `struct udiv_result`: 儲存運算完的結果，分成商和餘數。
```clike
struct udiv_result {
union u_qword q;
union u_qword r;
};
```
* `int Func64()`: `Func32()` 的擴展版本，先把數字拆成兩個 32-bit 資料，再利用原本的 `Func32()` 找出 leading zero。
```clike
static inline int Func64(uint64_t val)
{
uint32_t lo = (uint32_t) val;
uint32_t hi = (uint32_t) (val >> 32);
return hi ? Func32(hi) : 32 + Func32(lo);
}
```
* `int do_udiv32()`: 計算 32-bit 無號除法
首先，mask 會計算 divisor 和 dividend 的 leading zero 相差多少，計算 mask 的用意是知道商會有幾位數，後面我們可以利用到 mask 來判斷是否不能再繼續算下去。（mask 每次都要右移 1 bit，並決定是否要紀錄到商數，有紀錄就是 1 ，沒有就是 0）
二進位除法可以免除掉計算倍數的問題（一定是 0 或是 1 倍），只要用減的就可以完成除法。
在註解裡面的 align xxx 意思是把被除數 align 成我們計算的形式。回想長除法，除數是從 MSB 除到 LSB，所以要先把 divisor 往左"推"，讓 divisor 和 dividend 的 MSB 是對齊的。
如果當前 dividend 大於 divisor，代表可以除一次，就利用 bitwise or 把 mask 的當前位數 set 上去，不能除的話商就是 0 ，只要把 mask 右移一次就好。
每次做完 divisor 都要左移一次，可以看成是往下一位繼續作除法。
#### 寫出來長這樣：
```
dividend: 0101010, divisor: 0101
| 代表對齊的地方
[] 代表右移後補上的 0
第一次
0|101010 / 0101[000]
第一次
01|01010 / 00101[00]
第一次
010|1010 / 000101[0]
第一次
0101|010 / 0000101
```
```clike
static int do_udiv32(uint32_t dividend,
uint32_t divisor,
struct udiv_result *res)
{
/* Ensure dividend is always greater than or equal to the divisor. */
uint32_t mask = Func32(divisor) - Func32(dividend);
divisor <<= mask; /* align divisor */
mask = 1U << mask; /* align dividend */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.dwords.low |= mask;
}
divisor >>= 1;
} while ((P1) && dividend);
res->r.dwords.low = dividend;
return 0;
}
```
* `int udiv64()`: 計算 64-bit 無號除法，裏面有使用到 `do_udiv32()`。
注意到 `divisor == 0` 那邊有一個數字 `0xfff.....full`，那不是什麼很潮的寫法，只是在說有一個數字 `0xffffffffffffffff`，型態是 unsigned long long 而已。
基本上 64-bit 的版本和 32-bit 版本差不多，但是 64-bit 多了很多判斷的條件，包括：除以 0 ，除數被除數相等，除數大於被除數，只需要使用 32-bit 版本就可以實作...等，為什麼 32-bit 沒有考慮到這些問題呢？
如果我們會在 `udiv64()` 以外（像是 `main()` )呼叫到 `do_udiv32()`，就必須也加入 除以 0 等特殊情況的判斷式，但是現在我們很確定不會發生這種事情，因為這些特殊情況在呼叫前都被前面的判斷式過濾掉了。
和 32-bit 不同的地方在於 64-bit 多了一個變數 bits ，將原本 mask 的工作用兩個變數來完成。
bits 負責計算還有多少位數還沒除，每次會減 1 。
mask 負責當作 set bit 時用的 mask，每次都會左移一位元。
這樣就可以知道 bits 等於 0 的時候要離開迴圈。
:::info
感覺這樣做才是正確的，為什麼 32-bit 的版本可以讓 mask>>=1 來替代 bits 的工作呢？
:::
> 32-bit 版本的實作並不完整，其作用只是 helper function，用來實作 64-bit 版本，實際上也只有後者真的被使用
> [name=jserv]
```clike
int udiv64(uint64_t dividend, uint64_t divisor, struct udiv_result *res)
{
uint64_t mask;
uint64_t bits;
res->q.qword = res->r.qword = 0;
if (divisor == 0) { /* division by 0 ? */
res->q.qword = 0xffffffffffffffffull;
return -1;
}
if (divisor == dividend) {
res->q.qword = 1;
return 0;
}
if (divisor > dividend) {
res->r.qword = dividend;
return 0;
}
/* only 32 bit operands that the preconditions are fulfilled. */
if (!(divisor >> 32) && !(dividend >> 32))
return do_udiv32((uint32_t) dividend, (uint32_t) divisor, res);
bits = Func64(divisor) - Func64(dividend);
divisor <<= bits; /* align divisor and dividend */
mask = 1ULL << bits;
/* division loop */
do {
if (dividend >= divisor) {
dividend -= divisor;
res->q.qword |= mask;
}
divisor >>= 1;
mask >>= 1;
} while ((P2) && dividend);
res->r.qword = dividend;
return 0;
}
```
P3 和 P5 是用來改最後輸出的結果的，因為在函式裏面我們都是用數字來表示，想要印出字元的話就要將原本的數字加上 48 （ascii: '0'）。
P4 那部份是用十進位來處理數字，所以答案是 10。
>可是 ASCII 0 好像是 48?
[name=e94046165][color=green]
> > 已更正，把解法寫出來就直接寫答案上去了Orz，下次不再犯QQ[name=afcidk]
### 將 10 進位輸出改為 16 進位
### 上方程式碼的 `0xCAFEBABE` 為 [magic number](https://en.wikipedia.org/wiki/Magic_number_(programming))，舉出在真實世界中程式的實際作用 (提示: 如 malloc)
## [第五週測驗題(中)](https://hackmd.io/s/HkQjgqI5G)
先理解為什麼下面程式碼輸出會是 `jserv++C`
```clike
#include <stdio.h>
int main() {
puts((char *) &(double []){ 3823806048287157.0, 96 });
}
```
把 `m` 轉成二進位形式表現，得到 `01000011 00101011 00101011 01110110 01110010 01100101 01110011 01101010`，再將每個位元組轉成字元表示，得到 `C++vresj`。
但是因為我們機器的儲存方式是 little-endian，因此顯示的會是相反過來的 `jserv++C`。
再看到真正的程式碼，可以看到原本的數字 m[0] 會乘上 $2^{96}$，我們將 exponent 的部份加上 96 ，得到 `0[1001001 0010]1011 00101011 01110110 01110010 01100101 01110011 01101010`，再轉換成字元表示，得到 `jserv++I`
### 修改程式，允許輸出 Github 帳號名稱
修改程式碼輸出 Github 帳號名稱
先把想要修改的字元寫出來，轉成二進位，用 0 把 bits 補齊，但是不能夠直接用 `00000000` 補，因為 0 是 termination character。
```clike
#include <stdio.h>
double m[] = {2.09703464477855301570627215629e209};
int main() { puts((char*)m); return 0; }
// output: afcidk
```
### 修改 gen() 函式，將 m[] 的內容變為英文姓氏
我先將二進位表示分成三個部份： sign bit, exponent, mantissa
（之所以不直接減他們的差是為了減少誤差導致的錯誤。）
原本 v.s. 修改後
`0[1101011 0110][0100 01101001 01100011 01100110 01100001 00000001 00000001]`
`0[1100111 0110][1110 01110101 01001000 00000001 00000001 00000001 00000001]`
* #### sign bit
沒有更動
* #### exponent
11010110110 -> 11001110110 ，差了 64 倍。
* #### mantissa
數字可以額外寫一個程式，利用 bitwise operator 來 clear/set bit ，再直接印出兩者的差
算出數字 `1.03214314438870169274345588995E209`
需要注意到的是如果先更改 exponent，mantissa 也要跟著乘上更改的數字。避免處理麻煩，我先加上 mantissa 才更動 exponent。
```clike
#include <stdio.h>
double m[] = { 2.09703464477855301570627215629E209, 64};
void gen() {
// original output: afcidk
m[0] += 1.03214314438870169274345588995E209;
while (m[1]--) {
m[0] /= 2;
}
puts((char *) m); // output:Hung
}
int main() { gen(); return 0; }
```
### 在 big-endian 的環境中，要如何改寫
在 little-endian 中，每 8 byte 為單位，最高位元會放在 LSB。而在 big-endian 中，最高位元會放在 MSB。
要改寫到 big-endian 環境使用，需要注意以 8 byte 為單位反向放資料。
舉例來說：`0x01234567 0x9abcdefa`
在 little-endian 要放 `67 45 23 01 fa de bc 9a`
而在 big-endian 要放 `01 23 45 67 9a bc de fa`
## [第五週測驗題(下)](https://hackmd.io/s/Sk30MXDqM)
Sign in with Wallet
Connect another wallet