# 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)
Last changed by  
 
Pei Hsuan Hung
868
Published on HackMD