--- tags: linux2022 --- # 2022q1 Homework2 (quiz2) contributed by < Ahsen-lab > ## 實驗環境 ```shell $ gcc --version gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0 Copyright (C) 2019 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Byte Order: Little Endian Address sizes: 39 bits physical, 48 bits virtual CPU(s): 4 On-line CPU(s) list: 0-3 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 NUMA node(s): 1 Vendor ID: GenuineIntel CPU family: 6 Model: 165 Model name: Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz Stepping: 5 CPU MHz: 2904.002 BogoMIPS: 5808.00 Hypervisor vendor: KVM Virtualization type: full L1d cache: 128 KiB L1i cache: 128 KiB L2 cache: 1 MiB L3 cache: 48 MiB NUMA node0 CPU(s): 0-3 ``` ## 作業要求 > [作業要求](https://hackmd.io/@sysprog/BybKYf5xc) ## 測驗 `1` 對二個無號整數取平均值的程式碼: ### 程式碼運作原理 #### 實作一 ```c #include <stdint.h> uint32_t average(uint32_t a, uint32_t b) { return (a >> 1) + (b >> 1) + (a & b & 1); /* EXP1 */ } ``` ==作答區== ==`EXP1 = a & b & 1`== 兩個 `uint32_t` 無號整數 `a` 與 `b` 取平均值： $$ average = {(a + b) \over 2} = {{a \over 2} + {b \over 2}} $$ 無號整數右移一個 `bit` 其實就相當於除以 `2` 的操作，所以上述算式可改寫為 `(a >> 1) + (b >> 1)`，但是這裡要處理一個例外狀況，當 `a` 與 `b` 都是奇數的時候，`a` 與 `b` 的最低位 (最右邊的位元) 的 `1` 在右移的過程中會被消去，導致平均數會等於 `(a >> 1) + (b >> 1) + 1`。 為了要處理這個例外狀況，所以在實作中 `(a >> 1) + (b >> 1)` 會加上 `(a & b & 1)`，當 `a` 與 `b` 都是奇數時，`(a & b & 1) == 1`，如此便可處理例外的情況。 #### 實作二 ```c uint32_t average(uint32_t a, uint32_t b) { return (a & b) + ((a ^ b) >> 1); /* EXP2 & EXP3 */ } ``` ==作答區== ==`EXP2 = a & b`== ==`EXP3 = a ^ b`== 當 `a` 與 `b` 都是無號整數，`a ^ b`代表相加但不進位，`(a & b) << 1`代表進位但不相加，代入到 `(a / 2) + (b / 2)`。 `(a & b)` 代表 `(a / 2)` 和 `(b / 2)` 進位但不相加。 `(a ^ b) >> 1` 代表 `(a / 2)` 和 `(b / 2)` 相加但不進位。 所以要計算 `(a / 2) + (b / 2)` 可以代換成`(a & b) + ((a ^ b) >> 1)`。 ### 組合語言輸出 1. 未開啟最佳化 **`(a >> 1) + (b >> 1) + (a & b & 1)`** ```shell= 0x000055555555530d <+0>: endbr64 0x0000555555555311 <+4>: push %rbp 0x0000555555555312 <+5>: mov %rsp,%rbp 0x0000555555555315 <+8>: mov %edi,-0x4(%rbp) 0x0000555555555318 <+11>: mov %esi,-0x8(%rbp) 0x000055555555531b <+14>: mov -0x4(%rbp),%eax 0x000055555555531e <+17>: shr %eax 0x0000555555555320 <+19>: mov %eax,%edx 0x0000555555555322 <+21>: mov -0x8(%rbp),%eax 0x0000555555555325 <+24>: shr %eax 0x0000555555555327 <+26>: add %eax,%edx 0x0000555555555329 <+28>: mov -0x4(%rbp),%eax 0x000055555555532c <+31>: and -0x8(%rbp),%eax 0x000055555555532f <+34>: and $0x1,%eax 0x0000555555555332 <+37>: add %edx,%eax 0x0000555555555334 <+39>: pop %rbp 0x0000555555555335 <+40>: retq ``` ```shell= 0x0000555555555336 <+0>: endbr64 0x000055555555533a <+4>: push %rbp 0x000055555555533b <+5>: mov %rsp,%rbp 0x000055555555533e <+8>: mov %edi,-0x4(%rbp) 0x0000555555555341 <+11>: mov %esi,-0x8(%rbp) 0x0000555555555344 <+14>: mov -0x4(%rbp),%eax 0x0000555555555347 <+17>: and -0x8(%rbp),%eax 0x000055555555534a <+20>: mov %eax,%edx 0x000055555555534c <+22>: mov -0x4(%rbp),%eax 0x000055555555534f <+25>: xor -0x8(%rbp),%eax 0x0000555555555352 <+28>: shr %eax 0x0000555555555354 <+30>: add %edx,%eax 0x0000555555555356 <+32>: pop %rbp 0x0000555555555357 <+33>: retq ``` 2. `-O1` ```shell= 0x00005555555552fe <+0>: endbr64 0x0000555555555302 <+4>: mov %edi,%eax 0x0000555555555304 <+6>: shr %eax 0x0000555555555306 <+8>: mov %esi,%edx 0x0000555555555308 <+10>: shr %edx 0x000055555555530a <+12>: add %edx,%eax 0x000055555555530c <+14>: and %esi,%edi 0x000055555555530e <+16>: and $0x1,%edi 0x0000555555555311 <+19>: add %edi,%eax 0x0000555555555313 <+21>: retq ``` ```shell= 0x0000555555555314 <+0>: endbr64 0x0000555555555318 <+4>: mov %edi,%eax 0x000055555555531a <+6>: xor %esi,%eax 0x000055555555531c <+8>: shr %eax 0x000055555555531e <+10>: and %esi,%edi 0x0000555555555320 <+12>: add %edi,%eax 0x0000555555555322 <+14>: retq ``` 3. `-O2` ```shell= 0x00005555555552e0 <+0>: endbr64 0x00005555555552e4 <+4>: mov %edi,%eax 0x00005555555552e6 <+6>: mov %esi,%edx 0x00005555555552e8 <+8>: and %esi,%edi 0x00005555555552ea <+10>: shr %eax 0x00005555555552ec <+12>: shr %edx 0x00005555555552ee <+14>: and $0x1,%edi 0x00005555555552f1 <+17>: add %edx,%eax 0x00005555555552f3 <+19>: add %edi,%eax 0x00005555555552f5 <+21>: retq ``` ```shell= 0x0000555555555300 <+0>: endbr64 0x0000555555555304 <+4>: mov %edi,%eax 0x0000555555555306 <+6>: and %esi,%edi 0x0000555555555308 <+8>: xor %esi,%eax 0x000055555555530a <+10>: shr %eax 0x000055555555530c <+12>: add %edi,%eax 0x000055555555530e <+14>: retq ``` ## 測驗 `2` 改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation#%E4%B8%8D%E9%9C%80%E8%A6%81%E5%88%86%E6%94%AF%E7%9A%84%E8%A8%AD%E8%A8%88)〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 ( max ): ```c #include <stdint.h> uint32_t max(uint32_t a, uint32_t b) { return a ^ ((a ^ b) & -(a < b)); /* EXP4 & EXP5 */ } ``` ==作答區== ==`EXP4 = a ^ b`== ==`EXP5 = a < b`== 1. 首先比較 `a` 與 `b` 的大小，若 `a < b`，`-(a < b) == -(true) == -1 == 0xffffffff`，而 `(a ^ b) & 0xffffffff == (a ^ b)`，`a ^ (a ^ b) == b`。 所以若 `a < b`，則會回傳 `b`。 2. 若 `a >= b`，`-(a < b) == -(false) == -0 == 0x0`，而 `(a ^ b) & 0x0 == 0`，`a ^ 0 == a`。 所以若 `a >= b`，則會回傳 `a`。 ## 測驗 `3` 考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式: ```c #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; while (v) { uint64_t t = v; v = u % v; u = t; } return u; } ``` 改寫為以下等價實作: ```c= #include <stdint.h> uint64_t gcd64(uint64_t u, uint64_t v) { if (!u || !v) return u | v; int shift; for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } while (!(u & 1)) u /= 2; do { while (!(v & 1)) v /= 2; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); /* COND */ return u << shift; /* RET */ } ``` ==作答區== ==`COND = v`== ==`RET = u << shift`== 程式碼解釋： ```c=4 if (!u || !v) return u | v; ``` 檢查 `u` 或 `v` 是否為 `0`，若其中一數為 `0`，回傳另一個數，任何數與 `0` 的最大公因數就是它自己本身。 ```c=6 for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } ``` 若 `u` , `v` 都為偶數，判斷兩數之間可以共同被整除的最大非零偶數，`shift` 代表除以幾次 `2`。 ```c=9 while (!(u & 1)) u /= 2; ``` 若 `u` 仍為偶數，將其重複除以 `2` 讓其變為奇數，因為前面已經找過兩數之間的最大偶數因數，所以不需要再考慮偶數的部分。 ```c=11 do { while (!(v & 1)) v /= 2; if (u < v) { v -= u; } else { uint64_t t = u - v; u = v; v = t; } } while (v); /* COND */ ``` 第 12~13 行，若 v 仍為偶數，將其重複除以 2 讓其變為奇數，因為前面已經找過兩數之間的最大偶數因數，所以不需要再考慮偶數的部分。 第 14~21 行，確保 `u` 比 `v` 大，用迴圈讓 `u` 除以 `v`，`u` 代表上一次相除的除數，`v` 代表上一次相除的餘數。當 `v==0` 時，`u` 會等於 `u` , `v` 兩數之間可以共同被整除的最大奇數。 ```c=22 return u << shift; /* RET */ ``` 某個無號整數左移一次代表乘以 `2`，兩數的最大公因數為 `u * 2 * shift` (`u` 代表兩數之間可以共同被整除的最大奇數)，可以改寫為 `u << shift`，代表 `u` 乘以 `shift` 次 `2`。 ## 測驗 `4` 在影像處理中，bit array (也稱 bitset) 廣泛使用，考慮以下程式碼: ```c #include <stddef.h> size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; for (size_t k = 0; k < bitmapsize; ++k) { uint64_t bitset = bitmap[k]; size_t p = k * 64; for (int i = 0; i < 64; i++) { if ((bitset >> i) & 0x1) out[pos++] = p + i; } } return pos; } ``` 使用 `__builtin_ctzll` 改寫的程式碼如下： ```c= #include <stddef.h> size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out) { size_t pos = 0; uint64_t bitset; for (size_t k = 0; k < bitmapsize; ++k) { bitset = bitmap[k]; while (bitset != 0) { uint64_t t = bitset & -bitset; /* EXP6 */ int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } } return pos; } ``` ==作答區== ==`EXP6 = bitset & -bitset`== 設定一個變數 `pos` 用來紀錄 `bitmap` 中非零 `bit` 的個數。 第 6~14 行，使用迴圈來遍歷 `bitmap`，`bitset` 代表 `bitmap` 中每個 `index` 的值。 ```c=8 while (bitset != 0) { uint64_t t = bitset & -bitset; /* EXP6 */ int r = __builtin_ctzll(bitset); out[pos++] = k * 64 + r; bitset ^= t; } ``` 其中第 9 行的作用是找出目前最低位元的 `1`，並紀錄到 `t` 變數。舉例來說，若目前 `bitset` 為 $000101_b$，那 `t` 就會變成 $000001_b$。在二補數中，對 `bitset` 取負號表示 `~bitset + 1`，`bitset & (~bitset + 1)` 剛好可以保留最低位元的 `1`，再將結果存入 `t`。 接著使用 `__builtin_ctzll` 找出 `t` 的 Count Trailing Zeros (ctz)，再將結果存入變數 `r`，並把每個非零 `bit` 的位置存入 `out` array 中，最後用 XOR 將 `bitset` 中最低位元的 `1` 清掉。 不斷重複上述的動作，最後 improved function 會回傳 `pos`，而 `out` 中會儲存所有非零 `bit` 的位置。 ## 測驗 `5` LeetCode [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作: ```c= #include <stdbool.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include "list.h" struct rem_node { int key; int index; struct list_head link; }; static int find(struct list_head *heads, int size, int key) { struct rem_node *node; int hash = key % size; list_for_each_entry (node, &heads[hash], link) { if (key == node->key) return node->index; } return -1; } char *fractionToDecimal(int numerator, int denominator) { int size = 1024; char *result = malloc(size); char *p = result; if (denominator == 0) { result[0] = '\0'; return result; } if (numerator == 0) { result[0] = '0'; result[1] = '\0'; return result; } /* using long long type make sure there has no integer overflow */ long long n = numerator; long long d = denominator; /* deal with negtive cases */ if (n < 0) n = -n; if (d < 0) d = -d; bool sign = (float) numerator / denominator >= 0; if (!sign) *p++ = '-'; long long remainder = n % d; long long division = n / d; sprintf(p, "%ld", division > 0 ? (long) division : (long) -division); if (remainder == 0) return result; p = result + strlen(result); *p++ = '.'; /* Using a map to record all of reminders and their position. * if the reminder appeared before, which means the repeated loop begin, */ char *decimal = malloc(size); memset(decimal, 0, size); char *q = decimal; size = 1333; struct list_head *heads = malloc(size * sizeof(*heads)); for (int i = 0; i < size; i++) INIT_LIST_HEAD(&heads[i]); for (int i = 0; remainder; i++) { int pos = find(heads, size, remainder); if (pos >= 0) { while (pos-- > 0) /* PPP */ *p++ = *decimal++; *p++ = '('; while (*decimal != '\0') *p++ = *decimal++; *p++ = ')'; *p = '\0'; return result; } struct rem_node *node = malloc(sizeof(*node)); node->key = remainder; node->index = i; list_add(&node->link, &heads[remainder % size]); /* MMM EEE */ *q++ = (remainder * 10) / d + '0'; remainder = (remainder * 10) % d; } strcpy(p, decimal); return result; } ``` ==作答區== ==`PPP = pos--`== ==`MMM = list_add`== ==`EEE = &heads[remainder % size]`== ```c=7 struct rem_node { int key; int index; struct list_head link; }; ``` 第 7~11 行，設定 list 中的 element 的結構，包含 `key` 和 `index`。 ```c=13 static int find(struct list_head *heads, int size, int key) { struct rem_node *node; int hash = key % size; list_for_each_entry (node, &heads[hash], link) { if (key == node->key) return node->index; } return -1; } ``` 第 13~22 行，這裡 `heads` 代表一個 hash table，`size` 代表 hash table 的 size，`key` 代表 list 中 element 的 `key`。在 find function 中，hasa 代表包含有 `key` 的 list 的 head，使用 `list_for_each_entry` 遍歷該 list，若 list 中的 `node->key` 與 `key` 相同，則回傳 `node->index`，若沒有相同的 `key`，則回傳 `-1`。 ```c=26 int size = 1024; char *result = malloc(size); char *p = result; ``` 第 26~28 行，`result`是一段記憶體空間，用來儲存計算的結果，`p` 指向 `result` 的第一個位置。 ```c=30 if (denominator == 0) { result[0] = '\0'; return result; } if (numerator == 0) { result[0] = '0'; result[1] = '\0'; return result; } /* using long long type make sure there has no integer overflow */ long long n = numerator; long long d = denominator; /* deal with negtive cases */ if (n < 0) n = -n; if (d < 0) d = -d; ``` 第 30~49 行，處理分子或分母等於零的狀況，若分母為零，返回 `NULL`，分子為零返回 `0`，以及處理分子或分母為負號的狀況，若是負號則轉為正號。 ```c=51 bool sign = (float) numerator / denominator >= 0; if (!sign) *p++ = '-'; long long remainder = n % d; long long division = n / d; sprintf(p, "%ld", division > 0 ? (long) division : (long) -division); if (remainder == 0) return result; p = result + strlen(result); *p++ = '.'; ``` 第 51~63 行，判斷是否為負數分數，若是，result 中第一個字元為 `-`，接著處理整數的部分，將分子除以分母，把商存入 result，並在後面加入小數點 `.`。 ```c=68 char *decimal = malloc(size); memset(decimal, 0, size); char *q = decimal; size = 1333; struct list_head *heads = malloc(size * sizeof(*heads)); for (int i = 0; i < size; i++) INIT_LIST_HEAD(&heads[i]); ``` 第 68~75 行，`decimal` 是一段記憶體空間，用來儲存小數點的部分，`q` 指向 `decimal` 的第一個位置。另外，初始化一個 size 為 1333 的 hash table，其中包含 1333 個 list。 ```c=77 for (int i = 0; remainder; i++) { int pos = find(heads, size, remainder); if (pos >= 0) { while (pos-- > 0) /* PPP */ *p++ = *decimal++; *p++ = '('; while (*decimal != '\0') *p++ = *decimal++; *p++ = ')'; *p = '\0'; return result; } struct rem_node *node = malloc(sizeof(*node)); node->key = remainder; node->index = i; list_add(&node->link, &heads[remainder % size]); /* MMM EEE */ *q++ = (remainder * 10) / d + '0'; remainder = (remainder * 10) % d; } ``` 第 77~97 行，使用迴圈來計算小數，首先將餘數傳入 find function 中查詢是否有重複出現的餘數： 1. 若 `pos >= 0` 代表從小數點後 `pos` 位開始出現循環小數，所以先用迴圈將小數點後到 `pos` 之間的數字填入 `result`，接著加入左括號，然後開始填入循環小數的數字，填完後加入右括號，並在結尾加上 `'\0'`，最後回傳 `result`。 2. 若 `pos < 0` 表示還未碰到循環小數，這時會初始化一個新的 `rem_node`，並將當前的 `remainder` 及 `i` 存入 `rem_node`，`i` 代表現在計算到小數點後幾位，接著用 `list_add` 將 `rem_node` 放入 hash table 中的第 `remainder % size` 個 list 的開頭，最後將 `(remainder * 10) / d` 的值存入 `decimal`，並將 `remainder` 更新為 `(remainder * 10) % d`。 ```c=99 strcpy(p, decimal); return result; ``` 第 99~100 行，若都沒有遇到循環小數，那就將 `decimal` 中的值複製到 `result` 中，並回傳 `result`。 ## 測驗 `6` `__alignof__` 是 GNU extension，以下是其可能的實作方式: ```c /* * ALIGNOF - get the alignment of a type * @t: the type to test * * This returns a safe alignment for the given type. */ #define ALIGNOF(t) \ ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0) /* M & X */ ``` ## 測驗 `7` 考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目: * 從 1 數到 n，如果是 3 的倍數，印出 “Fizz” * 如果是 5 的倍數，印出 “Buzz” * 如果是 15 的倍數，印出 “FizzBuzz” * 如果都不是，就印出數字本身 以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`) ```c= static inline bool is_divisible(uint32_t n, uint64_t M) { return n * M <= M - 1; } static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1; static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1; int main(int argc, char **argv) { for (size_t i = 1; i <= 100; i++) { uint8_t div3 = is_divisible(i, M3); uint8_t div5 = is_divisible(i, M5); unsigned int length = (2 << div3) << div5; /* KK1 & KK2 */ char fmt[9]; //strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length); strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], length); /* KK3 */ fmt[length] = '\0'; printf(fmt, i); printf("\n"); } return 0; } ``` ==作答區== ==`KK1 = div3`== ==`KK2 = div5`== ==`KK3 = div3 << 2`== ```c= static inline bool is_divisible(uint32_t n, uint64_t M) { return n * M <= M - 1; } static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1; static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1; ``` `is_divisible` function 是用來判斷 `M` 是否可以被 `n` 整除，或是可用來判斷 `n` 是否是某數的倍數，判斷的公式為 `n * M <= M - 1`。 若要判斷 `n` 是否為 `x` 的倍數，則 `M` 的值為 `(uint64_t 最大值) / x + 1`。假設要判斷 `n` 是否為 `3` 的倍數，`M` 就代入 `UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1`。因為 `n` 一定是正整數或零，所以只有在 `n * M == 0` 時，`n * M <= M - 1` 才會成立，也就是說 `n` 一定要是 `3` 的倍數，`n * UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1` 才會 overflow 變成 `0`，`is_divisible` 才會返回 `true`。 ```c=9 int main(int argc, char **argv) { for (size_t i = 1; i <= 100; i++) { uint8_t div3 = is_divisible(i, M3); uint8_t div5 = is_divisible(i, M5); unsigned int length = (2 << div3) << div5; /* KK1 & KK2 */ char fmt[9]; //strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length); strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], length); /* KK3 */ fmt[length] = '\0'; printf(fmt, i); printf("\n"); } return 0; } ``` 使用迴圈判斷 1~100，若是 3 的倍數 `div3 == 1`，若是 5 的倍數 `div5 == 1`。 `length` 代表輸出字串的長度： 1. 若是 3 的倍數，`length` 等於 `(2 << 1) << 0 == 4` 2. 若是 5 的倍數，`length` 等於 `(2 << 0) << 1 == 4` 3. 若是 15 的倍數，`length` 等於 `(2 << 1) << 1 == 8` 4. 如果都不是，`length` 等於 `(2 << 0) << 0 == 2` `&"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)]` 代表從第幾個字元開始的字串 (題目第 17 行的程式碼有誤，應改為上述第 18 行所示)： 1. 若是 3 的倍數，`(8 >> 0) >> (1 << 2) == 0`，也就是字串 `FizzBuzz%u`。 2. 若是 5 的倍數，`(8 >> 1) >> (0 << 2) == 4`，也就是字串 `Buzz%u`。 3. 若是 15 的倍數，`(8 >> 1) >> (1 << 2) == 0`，也就是字串 `FizzBuzz%u`。 4. 如果都不是，`(8 >> 0) >> (0 << 2) == 8`，也就是字串 `%u`。 將上述參數代入 ```c strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], length) ``` 即可得到題目所描述的結果。