---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `bebo1010` >
## 測驗一
### 作答思路
#### EXP1
原本程式碼為`return (a >> 1) + (b >> 1) + (EXP1);`
我注意到`a >> 1`和`b >> １`會導致最後一位元的資料損失
因此EXP1的目標是找回最後一位元的資料
因此我列出底下的truth table
如果a和b都是奇數時，應該要進位上去
如果其中一個不是奇數，不會有進位
根據 truth table 找到應該至少會有`a & b`
接下來再補上`& 1`讓位元對齊最後一位
| a | b | result |
| - | - | ------ |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
a & b & 1
#### EXP2
a & b & 1
正確答案: a & b
我個人認為，EXP2 和 EXP3 題目出得不是很好
題目本身的提示太少，很難找出一個答題的線索
舉例 EXP1 的題目，給的提示就足夠讓我推敲出可能的答案
EXP4 和 EXP5 ，雖然提示沒有很多，但也可以稍微猜測個可能性
相較之下，EXP2 和 EXP3 的提示非常的少
我下課額外詢問教授為何答案是如此，教授也沒有提到解題的思路
因此我才覺得這兩個題目不是那麼恰當
#### EXP3
a & b
正確答案: a ^ b
### 延伸問題 -- 編譯器開啟優化
#### 第一版本
針對第一版本的 average 我大致撰寫了以下程式
```c
// q1_1.c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
int main(){
int low = 5;
int high = 6;
printf("%d\n", average(low,high));
return 0;
}
```
接著把這段程式碼進行編譯，但只做到轉換為組合語言的步驟
編譯方式為: `gcc -O3 -S q1_1.c -masm=intel`
編譯器優化使用 `-O3` ，把組合語言轉成 `intel` 格式
以下內容摘錄 average function 內容
```
// q1_1.s
average:
.LFB39:
.cfi_startproc
endbr64
lea eax, [rdi+rsi]
shr eax
ret
.cfi_endproc
...
```
`lea` 會把 `[rdi+rsi]` 記憶體位置複製進 `eax`
`shr` 會把 `eax` 內的值向右位移
`ret` 是 `return` instruction
這樣看下來真的有點奇怪，`shr` 似乎並沒有特別指出要向右位移幾位
那這樣它是怎麼正確計算 average 的?
接著我開始嘗試不同的編譯器優化，發現 `-O1`、`-O2` 的結果都和 `-O3` 完全相同
直到測試到 `-O0` 才看出變化
```
average:
.LFB6:
.cfi_startproc
endbr64
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
mov DWORD PTR -4[rbp], edi
mov DWORD PTR -8[rbp], esi
mov edx, DWORD PTR -4[rbp]
mov eax, DWORD PTR -8[rbp]
add eax, edx
shr eax
pop rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
...
```
整體看下來是先把原本的兩個值暫存到一個空間後，把這兩個值相加後再向右位移的作法
只是我不了解為何編譯器要做這麼多的 `mov` instruction，找不到一個理由去解釋這個狀況
#### 第二版本
接著針對第二版本的程式碼去了解組合語言的版本
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
第一次測試一樣先使用 `-O3` 進行測試
```
average:
.LFB0:
.cfi_startproc
endbr64
mov eax, esi
sub eax, edi
shr eax
add eax, edi
ret
.cfi_endproc
...
```
組合語言做出的方法和原本 C 的程式碼看起來是完全相同，沒有任何變化
接著我也測試了 `-O2` 和 `-O1`，和 `-O3` 完全相同
`-O0` 的結果則是有些變化
```
average:
.LFB0:
.cfi_startproc
endbr64
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
mov DWORD PTR -4[rbp], edi
mov DWORD PTR -8[rbp], esi
mov eax, DWORD PTR -8[rbp]
sub eax, DWORD PTR -4[rbp]
shr eax
mov edx, eax
mov eax, DWORD PTR -4[rbp]
add eax, edx
pop rbp
.cfi_def_cfa 7, 8
ret
.cfi_endproc
...
```
雖然說 `-O0` 的是有些變化，但是只是多了一些 `mov` 指令
程式核心完全沒有變化，我可能接下來不會再測試 `-O0` 了
#### 第三版本
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (a & b & 1);
}
```
一樣透過 `-O3` 進行編譯
```
average:
.LFB0:
.cfi_startproc
endbr64
mov eax, edi
mov edx, esi
and edi, esi
shr eax
shr edx
and edi, 1
add eax, edx
add eax, edi
ret
.cfi_endproc
...
```
假設 `edi` 是 `a`；`esi` 是 `b`
一開始把兩個值先暫存到 `eax` 和 `edx`
接著先做 `and` ，也就是 C 程式碼內的 `(a & b & 1)` 的前半
剩下的部分就只是把其他的計算做完而已
接著也測試了 `-O2` 和 `-O1`，`-O2` 和 `-O3` 的結果相同
`-O1` 的結果則是稍微不同
```
average:
.LFB0:
.cfi_startproc
endbr64
mov eax, edi
shr eax
mov edx, esi
shr edx
add eax, edx
and edi, esi
and edi, 1
add eax, edi
ret
.cfi_endproc
...
```
說是稍微不同，但實際上只是把程式順序稍微對調而已
本質上是沒有差異的
#### 第四版本
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
先使用 `-O3` 測試
```
average:
.LFB0:
.cfi_startproc
endbr64
mov eax, edi
and edi, esi
xor eax, esi
shr eax
add eax, edi
ret
.cfi_endproc
...
```
組合語言內容和 C 的程式碼幾乎是同個模子刻出來的
接著也測試了 `-O2` 和 `-O1` ，得到和第三版本時完全同樣的結果
以下放上 `-O1` 的內容
```
average:
.LFB0:
.cfi_startproc
endbr64
mov eax, edi
xor eax, esi
shr eax
and edi, esi
add eax, edi
ret
.cfi_endproc
...
```
很單純的把執行順序對調，本質上完全沒有差異
### Exponentially weighted moving average (EWMA)
首先我先去查詢這個演算法的細節是什麼([link](https://corporatefinanceinstitute.com/resources/knowledge/trading-investing/exponentially-weighted-moving-average-ewma/))
裡面寫到這個算法是一個遞迴式，算式如下
$EWMA_t = \alpha * r_t + (1 - \alpha) * EWMA_{t-1}$
其中 $\alpha$ 是一個常數(衰退係數，數值為 `0 ~ 1`)
$r_t$ 是當下時間的資料數值
但是 [linux](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 的程式碼我真的沒有能力看懂，有著太多不理解的地方
## 測驗二
### 作答思路
#### EXP4
a ^ b
EXP4 和 EXP5 我是用 trial and error 得知
我一開始先測試 EXP5 為`a > b`後再測試 EXP4 可能的內容
直覺猜測 EXP4 可能為`a ^ b` (考量到進行 XOR 後對於原本資料的損失很小)
發現此時回傳值剛好為較小值
因此把 EXP5 改為`a < b`就得到答案
#### EXP5
a < b
### 延伸問題 -- 有號數的 branchless max
一開始我在嘗試寫的時候，在思考主體應該用 $a > b$ 還是 $a - b$
針對 $a > b$ 的，我有想出一個 `(a > b) << 31 >> 31`
這個做法可以在 $a > b$ 時讓每個 bit 都設為 1
那接下來再想辦法讓回傳值變成 $a$ 或是 $b$
因此我撰寫出了以下程式
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b){
return b + ((a - b) & (a > b) << 31 >> 31);
}
```
在 $a > b$ 時，加號右邊的數值會留下 $a - b$ ，再加上 $b$ 就能回傳 $a$
在 $a < b$ 時，加號右邊的數值會變為 $0$，因此直接回傳 $b$
用同樣的概念，我也寫出了以下以 $a - b$ 為主體的程式碼
程式碼核心和上面的完全相同
```c
#include <stdint.h>
int32_t max(int32_t a, int32_t b){
return a - ((a - b) & (a - b) >> 31);
}
```
## 測驗三
### 作答思路
#### COND
v > 0
這個位置是輾轉相除的中止條件
輾轉相除的中止條件是較小的數(餘數)等於零
因此直接填入`v > 0`
正確答案是`v`，因為`v`的型態是 unsigned int
對於 unsigned int 來說 `v > 0` 和 `v` 是等價的
#### RET
u << shift
達成終止條件後的`u`為最大公因數
因此可得知回傳值必定含有`u`
而程式碼前段有針對`u`和`v`縮小數值(持續除以二)
要在這個位置補回去
### 程式碼解讀
> 註 : GCD 演算法
> 1. If both $x$ and $y$ are $0$, gcd is zero. $\gcd(0,0) = 0$
> 2. $\gcd(x,0) = 0$ and $\gcd(0,y) = 0$ because everything divides $0$.
> 3. If x and y are both even, $\gcd(x,y) = \gcd(\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor.
> Multiplication with $2$ can be done with bitwise shift operator.
> 4. If $x$ is even and $y$ is odd, $\gcd(x,y) = \gcd(\frac{x}{2}, y)$.
> 5. On similar lines, if $x$ is odd and $y$ is even, $\gcd(x,y) = \gcd(x, \frac{y}{2})$.
> it is because $2$ is not a common divisor.
```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);
return u << shift;
}
```
第四行的 if 條件對應註釋第一條及第二條，如果兩者其中一個為0，直接 return 0
第五行到第八行對應註釋第三條的前半段，如果兩者皆為偶數就可以把數值縮小並且記錄下目前已經位移幾次
第九行到第十行對應註釋第四條，如果 $u$ 是偶數則做 $u / 2$
第十二到第十三行對應註釋第五條，如果 $v$ 是偶數則做 $v / 2$
第二十二行對應註釋第三條的後半段，將原先向右位移掉的數值在這裡用向左位移補回去
## 測驗四
### 作答思路
#### EXP6
bitset & -bitset
根據題目的提示
> 其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 `t` 變數。
從這裡我知道我想要的是什麼，然後從教授提供的資源找到我要的程式碼
我找到了`Bit Hack #7. Isolate the rightmost 1-bit.`
這個資料和我想要的程式碼是相同的
因此修改這份資料提供的程式碼後再輸入進去即完成作答
> 引用資源：[Introduction to Low Level Bit Hacks](https://catonmat.net/low-level-bit-hacks)
## 測驗五
### 作答思路
#### PPP
這位置應該是放入非循環小數部分的判定式，但是我目前找不出判定條件應該是什麼
後來再仔細想想後，發現了一點細節
`int pos = find(heads, size, remainder);`
這行程式碼會回傳第一個重複的小數位置在哪裡，沒有重複就回傳 $-1$
因此 pos 之前的部分都是非重複的小數，可以使用 pos 當成這個迴圈的計數器
PPP 應該填入 `pos--`
#### MMM
list_add_tail
#### EEE
heads
MMM 和 EEE 看起來是把當前的小數點數值存入 linked list 的地方
因此 MMM 填入 list_add_tail 讓新的 node 可以放入 list
EEE 填入 list 的頭
### 延伸問題
我想對於處理負數這塊的程式碼進行改進
```c=
/* deal with negtive cases */
if (n < 0)
n = -n;
if (d < 0)
d = -d;
bool sign = (float) numerator / denominator >= 0;
if (!sign)
*p++ = '-';
```
針對第二行到第五行，或許可以改成以下
使用 bitwise operator 去處理
```c
if(n & (1 << 31))
n = ~n + 1;
if(d & (1 << 31))
d = ~d + 1;
```
而第七行到第九行或許也可改為以下
直接透過 bitwise operator 取得被除數和除數的 sign bit，進而節省掉除法的使用
```c
uint32_t sign = ((numerator & denominator) & (1 << 31));
if(sign)
*p++ = '-';
```
接著這份程式還有個問題，decimal 和 heads 的記憶體空間配置後沒有被釋放掉
```c
char *decimal = malloc(size);
```
```c
struct list_head *heads = malloc(size * sizeof(*heads));
```
## 測驗六
### 作答思路
最內層的 `(struct { char c; t _h; } *)` 應該是宣告一個 struct
裡面包含一個字元和一個傳入的 datatype t (可能是 int, double 等等的)
再往外一層的 `((struct { char c; t _h; } *)0)` 我就不理解為何這裡有個 0
最外層的 `(&((struct { char c; t _h; } *)0)->M)` 這裡我也不理解，剛宣告的 struct 為何可以使用 -> ，是不是暗示著這邊的 M 是填入 `c` 或是 `_h`。
接著是 `(char *)(&((struct { char c; t h; } )0)->M)` ，為何這裡又要 cast 成 character pointer? 這個題目對我目前整個就是一個謎團
## 測驗七
### 作答思路
#### KK1 和 KK2
KK1 = div3，KK2 = div5
兩者都是用來調整接下來的 strncpy 要使用多少字元
如果不整除 3 也不整除 5 ，length 為 2
如果整除 3 或整除 5 ，length 為 4
如果兩者都整除，length 為 8
#### KK3
div3 << 2
KK3 用來調整 `FizzBuzz%u` 的字串要從哪裡開始複製到 `fmt` 內
要調整的目標為 `(9 >> div5) >> (KK3)`
(判定優先順序由上到下)
如果整除 3 ，數值應為 0
如果整除 5 ，數值應為 4
如果不整除 3 也不整除 5 ，數值應該為 8
### 延伸問題 -- 程式碼解讀
以下為原程式碼加回去答案後的內容
```c=
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdbool.h>
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;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
奇怪的問題是，這份程式碼我實際拿去執行後發現在不整除 3 也不整除 5 的狀況下輸出是 u ，而不是原本預期的原數字
進一步測試後發現是程式碼內第二十一行有出錯，把起始點的 9 改為 8 即可正常輸出原數字內容
```c
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (div3 << 2)], length);
```
Sign in with Wallet
Connect another wallet