---
tags: linux2022
---
# 2022q1 Homework (quiz2)
contributed by <`ibat10clw`>
> [quiz2](https://hackmd.io/@sysprog/linux2022-quiz2#2022q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
## 測驗1
### 程式碼運作原理
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
觀察上述程式碼, ` a >> 1 ` 和 ` b >> 1` 可視為除以 2 的運算, 但當 a 以及 b 為奇數時回傳值會與正確結果差 1
因此 EXP1 需要在 a 和 b 都是奇數的情況下為 1, 其餘情況為 0
在二進位下判斷奇偶的方法可以透過確認 LSB 來做判斷, 若 LSB = 1 為奇數, LSB = 0 為偶數
所以可以將 a 和 b 與 1 做 bitwise and 來確認 LSB 的結果
* `EXP1 = a & b & 1`
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
從加法器的角度切入 sum 和 carry 分別能以下列操作表示:
* sum: `x ^ y`
* carry: `(x & y) << 1`
把上面兩者的結果相加等同於 (x + y), 回到題目部份剛好也是兩個運算式相加, 但其中有一個 right shift, 可判斷為 (sum + carry) >> 1 後變成的結果
嘗試將 sum 和 carry 相加後做 right shift
* `(((x ^ y) + (x & y) << 1)) >> 1`
`= (((x ^ y) >> 1) + (x & y))`
`= (x & y) + ((x ^ y) >> 1)`
最後便可推得下列結果
* `EXP2 = (x & y), EXP3 = (x ^ y)`
### 觀察編譯器行為
```shell
0000000000000000 <average>:
0: f3 0f 1e fa endbr64
4: 55 push %rbp
5: 48 89 e5 mov %rsp,%rbp
8: 89 7d fc mov %edi,-0x4(%rbp)
b: 89 75 f8 mov %esi,-0x8(%rbp)
e: 8b 45 fc mov -0x4(%rbp),%eax
11: 23 45 f8 and -0x8(%rbp),%eax
14: 89 c2 mov %eax,%edx
16: 8b 45 fc mov -0x4(%rbp),%eax
19: 33 45 f8 xor -0x8(%rbp),%eax
1c: d1 e8 shr %eax
1e: 01 d0 add %edx,%eax
20: 5d pop %rbp
21: c3 retq
```
* 上面是 -O0 產生的組合語言程式碼
* 組合語言指令解析:
* `push src:` 將 src 的資料 push 進 stack
* `mov dest src:` 將 src 的資料搬到 dest
* `xor dest src:` 將 dest 與 src 做 XOR 後存回 dest
* `add dest src:` 將 dest 與 src 做 ADD 後存回 dest
* `shr:` shift right
* `pop dest:` 將 stack 的資料 pop 給 dest
```shell
0000000000000000 <average>:
0: f3 0f 1e fa endbr64
4: 89 f8 mov %edi,%eax
6: 31 f0 xor %esi,%eax
8: d1 e8 shr %eax
a: 21 f7 and %esi,%edi
c: 01 f8 add %edi,%eax
e: c3 retq
```
* 上面是 -O1 產生的組合語言程式碼
* 與 -O0 最大的差別是少了 stack 相關的操作
```shell
0000000000000000 <average>:
0: f3 0f 1e fa endbr64
4: 89 f8 mov %edi,%eax
6: 21 f7 and %esi,%edi
8: 31 f0 xor %esi,%eax
a: d1 e8 shr %eax
c: 01 f8 add %edi,%eax
e: c3 retq
```
* 上面是 -O2 和 -O3 產生的組合語言程式碼
* 與 -O1 的差別運算順序有些許不同
## 測驗2
### 程式碼運作原理
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
* 解題靈感來自於 [LeetCode 136. single number](https://leetcode.com/problems/single-number/), 透過 XOR 能夠找出 single number 的特性來做思考
* 由於程式碼左半邊的 `a ^` 的部份以固定, 因此想令括號內的結果等價為下列情形:
* `a ^ b`: 當 b 比較大的時候, `a ^ a ^ b` 能夠將 a 消掉, 正好將 b 作為回傳值
* `a ^ a`: 當 a 比較大的時候, `a ^ a ^ a` 由於 a ^ a 的結果是 0, a ^ 0 後又會恢復為 a, 將 a 回傳正好也是最大值
1. 首先根據提示 EXP5 為一個 logical 的運算, 根據 C 語言規格, 邏輯運算結果只會是 0 或 1, 在灌上一個負號後的最後能產生的結果只會是 `0xffffffff` 或 `0x00000000`
1. 再來考慮 & 的特性
* `x & 1 = x`: 不變
* `x & 0 = 0`: 強制歸零
可以根據上述兩種可能的結果繼續推測 EXP4 的可能
1. 回到第一點的討論, EXP4 根據提示為 bitwise 的操作, 而我們希望能夠產出一個 XOR 的結果, 因此這邊填入 `a ^ b`
1. 由於 EXP4 也已經做選擇, 根據 & 運算性質的討論可得最後結論:
* `a ^ ((a ^ b) & -(1))`: 由於 `a ^ b` 不變最後結果剩下 b
* `a ^ ((a ^ b) & -(0))`: 由於括號內被歸零最後結果剩下 a
也就是當實際狀況 a > b 時, 我們希望 EXP5 的結果為 false, 最後結果才能將 a 留下, 因此 EXP5 可填入 `a < b`
同樣的驗證實際情況為 a < b 時, 因 EXP5 的結果為 true, 括號內不變而兩個 a 抵銷後最後留下了 b
整理上述的原理後可得下列結果
* `EXP4 = a ^ b`, `EXP5 = a > b`
## 測驗3
### 程式碼運作原理
```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 (COND);
return RET;
}
```
以上的程式碼其實就是老師測驗題上提供的演算法的實作
* 程式的最一開始先判斷特例情況, 若有任一數字為 0 則可以直接得到 GCD
* 當兩個數字都為偶數的情況下, $GCD(u, v)$ 可化簡為 $2 * GCD( \frac{u}{2} , \frac{v}{2})$, 第 6 行的迴圈便是為了簡化而做紀錄, u 和 v 每除了一次 2, 最後就要乘回來一次, 把次數紀錄在變數 shift
* 根據演算法提示, 只要 u 和 v 為一奇一偶的情況則可以進一步化簡
* if u is odd and v is even, then $GCD(u, v) = GCD(u, \frac{v}{2})$
* else if u is even and v is odd, then $GCD(u, v) = GCD(\frac{u}{2}, v)$
* 第 9 和 12 行的 while 是在找尋進一步化簡的可能
* 14 至 19 行則是在實現減法版本的 Euclidean algorithm, 並在每次 do-wile 的開頭嘗試化簡的可能
* if u < v, then $GCD(u, v) = GCD(u, v - u)$
* else $GCD(u, v) = GCD(v, u - v)$
* `COND = u != 1 && v` 根據 Euclidean algorithm 的終止條件而設立
* 其中 `u != 1` 是因為當 `u == 1` 時 u 的值就不會在改變了
* `RET = u << shift` 根據前面推導若在 for 迴圈的階段有做化簡則最後要乘回來
## 測驗4
### 程式碼運作原理
```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;
}
```
上面的程式碼能夠找出在二進位表示中 bitset 的 bit 為 1 的位置, 並且將其紀錄在 out 裡面, 最後能夠根據回傳的 pos 在 out 中取出有效的紀錄
```c
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 = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
* 使用 __builtin_ctzll 改寫後的結果如上, 只要當前的 bitset 不為 0, 就透過 __builtin_ctzll 從右往左找出第一個 bit 為 1 的位置
* 透過 left shift 將 1 移動到 __builtin_ctzll 回傳的位置, 最後在根據 XOR 的特性將對應位置的 bit 化為0, 而其他 bit 不變, 直到 bitset 歸零為止
綜合上述整理可得結果
* `EXP6 = 0b1L << __builtin_ctzll(bitset)`
## 測驗5
### 程式碼運作原理
```c=
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;
}
long long n = numerator;
long long d = denominator;
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++ = '.';
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 (PPP > 0)
*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;
MMM(&node->link, &heads[EEE]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
```
* 程式的計算方法是模擬手算長除法時的情況
* 其中 24 ~ 33 行的部份為處理除數或被除數為零的特例, 可以直接得到結果
* 43 ~ 44 行透過將兩數相除判斷是否需要在最後結果加上負號
* 47 ~ 52 行進行了第一輪計算, 並透過 sprintf 將結果 int 的資料轉為 string 放入 result 中, 同時檢查 remainder 是否為 0, 若可以整除的話可以直接得出結果
* 54 ~ 55行透過 result 的整數部份找出放置 `'.'` 的位置後將其置入
* 57 ～ 64 行在為了後續計算建立一個 hash table, 其中 size 為 bucket 的數量
* 66行開始為長除法的計算, 長除法中判斷循環小數的方式為出現了重複的餘數
每次 for 迴圈的開始都會透過 hash 回傳的 pos 確認是否餘數已經出現過了
* 當 `pos >= 0` : 代表已能確認循環的部份, 透過回傳的 pos 先將 decimal 不循環的部份複製到 p, 之後擺上 `'('` , 把 decimal 剩下的部份還有 `')'` 跟 null terminator 放入後回傳結果
* 當 `pos == -1` : 代表尚未發現循環的部份, 因此將該輪的結果放入 hash list 中
* 84 ~ 85 行為長除法每次都需要將數字最後補零的操作
* 88 ~ 89 若能成功將餘數清為零, 則將 decimal 整個複製給 p, 最後將結果回傳
綜合上述整理可得結果
* `PPP = pos--`
* PPP 會影響擺放 `'('` 的位置, 這取決於回傳的 pos, 而 pos 又紀錄了該個 remainder 是第幾 `n` 計算的結果, 因此需要在小數後 `n` 位補上 `'('`
* `MMM = list_add, EEE = size % remainder`
* MMM 和 EEE 為在 hash list 中新增資料的方式, 由於 hash function 為計算傳入參數 `key % size` 的結果, 而在程式碼 67 行傳入的各是 size 和 remainder, 因此加入時同樣加入在 `size % remainder` 個 bucket, 另外由於是 circular doubly linked list, 因此加在尾巴或頭都可以
### 可改進之處
TODO
## 測驗6
### 程式碼運作原理
```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)->M) - (char *)X)
```
* `__alignof__` 計算的是若想對齊某資料需要花的 byte 數量
* 根據 macro 定義傳入的參數 `t` 以及 `struct` 內會將 `t` 代換掉並同時以 `t` 的資料型態宣告變數 `_h`
* 同時使用一個 literal `0` 來當載體並且計算 `_h` 與這個 `struct` 自身的差距有多少作為對齊所需的 byte 數
根據上述整理可得結果
* `M = _h`
* 因為想計算的是 `t->_h` 與 `t` 的差距, 因此填入 `_h`
* `X = 0`
* 由於前面是用 `0` 來當載體, 後面也要一致
## 測驗7
### 程式碼運作原理
```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 << KK1) << KK2;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
首先看過整個主程式的執行流程
* 12 ~ 13 行的 is_divisible 用來測試是 i 否為 3 或 5 的倍數, 之後根據測試結果來設定 length
* is_divisible 回傳的值為 0 或 1, 因此 14 行的操作也能看為根據測試結果將 length 乘以 2
* 17 行的部份透過 div5 和 div3 的結果取出 `"FizzBuzz%u"` 中的一部分並將複製到 fmt 中
* 剩下的部份為加入 NULL terminator 以及將其印出
可以發現關鍵在於:
* is_divisible 的實作
* 如何透過 length, div3, div5 取出 `"FizzBuzz%u"` 的片段
#### is_divisible
在閱讀了 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 網頁中提出的方法後得知若想計算除法可以透過乘法的模擬得出
* $\Large \frac{n}{d} = n * \frac{2^N}{d} * \frac{1}{2^N}$
* 其中 $\Large \frac{2^N}{d}$ 是需要預計算的部份, $\Large \frac{1}{2^N}$ 可以透過 shift 得出, 因此往後我們便能只透過乘法來得出除法的結果
* 餘數的部份可從上述公式中的 LSB 乘上 d 後做 right shift 獲得
#### 控制 `"FizzBuzz%u"` 的片段
由於 `"FizzBuzz%u"` 會需要印出的片段分別為:
* Fizz: 位移量 0, 長度 4
* Buzz: 位移量 4, 長度 4
* `%u`: 位移量 8, 長度 2
* FizzBuzz: 位移量0, 長度8
需要控制的變數皆為 powers of 2, 因此可以用 8 為底搭配 right shift 的操作來取出所需片段
綜合上述討論可得：
* `KK1 = div3, KK2 = div5`
* length 是以 2 為底來做 shift 的, 而當 div3 或 div5 的值為 1 時便可以透過 left shift 變為 4 或 8
* `KK3 = div3 << 2`
* 題目已知的部份有 `(8 >> div5) >>` 先討論 div5 為 1 的情況, 結果會變成 `4 >> (KK3)`, 而這時 div3 還沒有用上, 且希望透過 div3 來控制要印出 `FizzBuzz` 或是 `Buzz`
* 這兩者的位移量分別是 0 以及 4, 所以 `KK3` 需要在真的時候產出 2 ,假的時候產出 0 的結果, 以便讓`(8 >> div5) >> (KK3)`能夠符合預期行為
* 因此 KK3 填入 `div3 << 2`
Sign in with Wallet
Connect another wallet