---
tags: linux2022
---
# 2022q1 Homework (quiz2)
contributed by < `hankluo6` >
> [第 2 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗 `1`
### 運作原理
將兩數 $x, y$ 分成，整數部分及小數部分：
$$
\begin{equation}
\frac{x}{2}=\lfloor{\frac{x}{2}}\rfloor+frac(\frac{x}{2}) \\
\frac{y}{2}=\lfloor{\frac{y}{2}}\rfloor+frac(\frac{y}{2}) \\
\end{equation}
$$
就能列出算式：
$$
\begin{equation}
\begin{aligned}
avg(x, y) &= \lfloor \frac{x+y}{2}\rfloor \\
&= \lfloor \lfloor{\frac{x}{2}}\rfloor + \lfloor{\frac{y}{2}}\rfloor + frac(\frac{x}{2}) + frac(\frac{y}{2}) \rfloor \\
&= \lfloor{\frac{x}{2}}\rfloor + \lfloor{\frac{y}{2}}\rfloor + \lfloor frac(\frac{x}{2}) + frac(\frac{y}{2}) \rfloor
\end{aligned}
\end{equation}
$$
$$
\lfloor frac(\frac{x}{2})+frac(\frac{y}{2}) \rfloor=
\begin{cases}
1, & \text{if $x$ and $y$ are odd} \\
0, & \text{else}
\end{cases}
$$
求出 $x$ 與 $y$ 皆為奇數時需要加一，`EXP1 = a & b & 1`。
根據加法器原理可得：$a + b=a \oplus b +(a \land b)<<1$
所以：$\begin{equation}
(a+b)>>1 = (a \oplus b)>>1 + a \land b
\end{equation}$
得出 `EXP2 = a & b`，`EXP3 = a ^ b`。
### 對應組合語言輸出
* Target: x86_64-w64-mingw32
* Compiler: gcc
```c
uint32_t averagev1(uint32_t low, uint32_t high)
movl %edx, %eax // $eax = high
subl %ecx, %eax // $eax = high - low
shrl %eax // $eax = (high - low) / 2
addl %ecx, %eax // $eax = low + (high - low) / 2
ret
uint32_t averagev2(uint32_t low, uint32_t high)
movl %ecx, %eax // $eax = high
movl %edx, %r8d // $r8d = low
andl %edx, %ecx // $ecx = low & high
shrl %eax // $eax = high >> 1
shrl %r8d // $r8d = low >> 1
andl $1, %ecx // $ecx = low & high ^ 1
addl %r8d, %eax // $eax = low >> 1 + high >> 1
addl %ecx, %eax // $eax = low >> 1 + high >> 1 + (a & b & 1)
ret
uint32_t averagev3(uint32_t low, uint32_t high)
movl %ecx, %eax // $eax = high
andl %edx, %ecx // $ecx = low & high
xorl %edx, %eax // $eax = low ^ high
shrl %eax // $eax = (low ^ high) >> 1
addl %ecx, %eax // $eax = low & high + (low ^ high) >> 1
ret
```
TODO
### EWMA
```c
#define DECLARE_EWMA(name, _precision, _weight_rcp) \
struct ewma_##name { \
unsigned long internal; \
};
...
```
* name: 決定宣告的 structure 和 function 名稱
* \_precision: 決定需要用幾個 bit 來表示[定點數小數](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)
* \_weight_rcp: EWMA 中的 $\frac{1}{\alpha}$
```c
static inline void ewma_##name##_init(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
/* \
* Even if you want to feed it just 0/1 you should have \
* some bits for the non-fractional part... \
*/ \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
e->internal = 0; \
}
```
檢查輸入的數值是否合法，`_precision` 及 `_weight_rcp` 必須為編譯時期能決定的常數、`_precision` 不能大於 30、_weight_rcp` 須為 2 的倍數，因為 `add` 是用 shift 實作，最後初始化 `internal`。
```c
static inline unsigned long \
ewma_##name##_read(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
return e->internal >> (_precision); \
}
```
`read` 數值時沒有將小數部分印出。
```c
static inline void ewma_##name##_add(struct ewma_##name *e, \
unsigned long val) \
{ \
unsigned long internal = READ_ONCE(e->internal); \
unsigned long weight_rcp = ilog2(_weight_rcp); \
unsigned long precision = _precision; \
\
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
\
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision)); \
}
```
根據目前 `internal` 的數值分成兩部分：
* `internal > 0`:
$$
\begin{equation}
\begin{aligned}
internal &= \frac{(internal \times \frac{1}{\alpha} - internal) + (val \times 2^{precision})}{\frac{1}{\alpha}} \\
&= \frac{(internal \times (\frac{1}{\alpha} - 1)) + (val \times 2^{precision})}{\frac{1}{\alpha}} \\
&= (internal \times (1 - \alpha)) + (val \times 2^{precision})\times \alpha
\end{aligned}
\end{equation}
$$
* `internal <= 0`
$$
\begin{equation}
\begin{aligned}
internal = val \times 2^{precision} \\
\end{aligned}
\end{equation}
$$
---
## 測驗 `2`
### 運作原理
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
`EXP5` 為 boolean 運算，可知結果只可能為 `0x0000` 及 `0xFFFF`，當為 `0x0000` 時，回傳 `a ^ 0 = a`，當為 `0xFFFF` 時，回傳 `a ^ EXP4`。
所以當 `a > b` 時，`EXP5 = 1` 才能滿足條件，得出 `EXP5 = a > b`。
而當 `b >= a` 時，`a ^ EXP4 = b`，可得 `EXP4 = a ^ b` (根據 XOR 的特性 `a ^ a = 0`)。
### 32 位元有號數 branchless 實作
改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」
```c
int32_t max(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & ~(diff >> 31));
}
```
只需在判斷大小的 `diff >> 31` 加上 `NOT` 運算，相反大小判斷便能改成回傳 `max`。
這實作僅在 `INT32_MIN` <= (a - b) <= `INT32_MAX` 成立時，才會發揮作用。
---
## 測驗 `3`
### 運作原理
根據[輾轉相除法](https://en.wikipedia.org/wiki/Euclidean_algorithm) 的演算法可求出答案：
* `COND = v`
* `RET = u << shift`
在每次回圈中，持續保持 `v` 為最小值，當 `v` 為 0 時，表示無法再提出公因數，便跳出迴圈。而在函式剛開始時，透過迴圈將最大公因數的 2 的次方提出，記錄在 `shift` 當中，故最後回傳時需再將次方乘回去。
### 透過 `__builtin_ctz` 改寫 GCD
* 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
int a = __builtin_ctzl(u), b = __builtin_ctzl(v);
shift = b ^ ((a ^ b) & -(a < b));
u >>= shift, v >>= shift;
int bit;
if (bit = __builtin_ctzl(u))
u >>= bit;;
do {
if (bit = __builtin_ctzl(v))
v >>= bit;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
效能分析：
隨機產生 64 bit 的資料，並測量 1000000 次的運行時間
| gcd64 | __builtin_ctz gcd64 |
|:----------:|:-------------------:|
| 0.667711 s | 0.425873 s |
可發現效能有有效的提昇，約提昇 $\frac{0.667711-0.425873}{1000000} = 2.4 * 10^{-7}$ 秒。
- [2020q3 quiz3](https://hackmd.io/@hankluo6/B17jPGv8D#%E5%BB%B6%E4%BC%B8%E5%95%8F%E9%A1%8C3)
---
## 測驗 `4`
### 運作原理
根據提示找出目前最低位元的 1 即為 `bitset & (-bitset)`，因為 `-bitset = ~bitset + 1`，`~bitset` 將所有位元反轉，`+1` 會將位元為 1 的部分 (原本為 0) 往 MSB 進位，直到位元為 0 (原本為 1) 的位元，AND 運算後該位元為唯一與 `bitset` 相同的位元，故能找到最低位元的 1。
### `ctz/clz` 效能比較
其中 bit ratio 為 bitmap 中為 bit 為 `true` 的比率，可以發現原本的方法不管 bit 數多寡，其運行效率大致相同；而使用 `ctz` 的方法會受到 bit 數量，當 bit 數量越多，就執行越多次 `__builtin_ctzll`，在 bit 比率大約 50% 時為分水嶺。故可以得出結論：bit 比率小於 50% 時 `__builtin_ctzll` 效率較好，反之則為原本的方法較好。
---
## 測驗 `5`
### 運作原理
根據[長除法](https://en.wikipedia.org/wiki/Long_division)演算法，可利用當前餘數 $\times 10$ 求出下個位數的數字及對應的餘數。程式內的 `char *p` 即指向一個 1024 bytes 空間的指標，在迴圈內會紀錄對應的商。
當出現重複的小數數值時，表示構成循環小數，便能直接從 hash table 中取出剩下的數字，並加上 `(` 以及 `)` 後回傳。
所以 `MMM` 應為將有存放小數數字的節點加入到 hash table 中的操作，即為 `list_add`，`EEE` 決定該節點插入的是 hash table 中的第幾個 bucket，從 `find` 中可以知道 hash function 為 `number % size`，所以 `EEE` 為 `&heads[remainder % size]`，當找到重複的數字時，`pos >= 0` 進到條件式中，`while` 迴圈將非循環的小數部分存到 `p` 中，而 `node->index` 紀錄數字為小數點後第幾個數，所以 `PPP` 應為 `pos--`。
---
## 測驗 `6`
```c
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
```
```graphviz
digraph G {
rankdir=LR
tee [shape=none margin=0 label=
<<table border="0" cellspacing="0" cellborder="1">
<tr>
<td port="f1" width="55" height="22" fixedsize="true">char c</td>
</tr>
<tr>
<td port="f2" width="55" height="66" fixedsize="true">padding</td>
</tr>
<tr>
<td port="f3" width="55" height="88" fixedsize="true">t _h</td>
</tr>
</table>>]
start [label="0", shape=plaintext];
start->tee:f1:nw
alignment [label="alignment", shape=plaintext];
alignment->tee:f3:nw
}
```
根據[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory?type=view#data-alignment)在成員位址不能整除時，會自動加入 padding 做 alignment。`&((struct { char c; t _h; } *)0)->_h` 取出 `_h` 成員相對於 0 的位址，相減便能求出 alignment 的位址。
---
Sign in with Wallet
Connect another wallet