---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `Xx-oX` >
> [題目](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗 `1`
考慮對兩個無號整數取平均值的程式碼
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
可以改寫成以下等價的實作
* `A`
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
或者
* `B`
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
填入 EXPx ，並
* 解釋程式碼運作原理
* 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀
* 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
### `A`
`a >> 1` 表示 $\lfloor\dfrac{a}{2}\rfloor$
而 $\lfloor\dfrac{a}{2}\rfloor + \lfloor\dfrac{b}{2}\rfloor$ 在 $a, b$ 均為奇數時，會比預期的結果少 1
> e.g. a = 11, b = 13, 均為 unsigned (實行邏輯右移)
> ```verilog
> (11 >> 1) + (13 >> 1)
> = (b'1011 >> 1) + (b'1101 >> 1)
> = b'0101 + b'0110
> = b'1011 = 11
> ```
> 比預期的答案 (12) 少一
> 原因是右移會把 LSB 捨去，而兩個奇數 LSB 加總的進位也就被忽略了
因此，EXP1 要判斷 a, b 是否均為奇數，如果成立，則加上被捨去的 1
判斷奇數 => 判斷 LSB => 跟 1 做 `&` (AND) => `a & b & 1`
### `B`
考慮半加器
```c
s = a ^ b // 和 a XOR b
c = a & b //進位 a AND b
```
a 和 b 的平均 = $\lfloor\dfrac{a+b}{2}\rfloor$
比照 `A` 右移 s 而省略的 LSB 以及進位由 c 補上
因此
```c
s = ((a ^ b) >> 1)
c = a & b
```
EXP2 填入 `a & b`
EXP3 填入 `a ^ b`
> 以 a = 11, b = 13 驗證
> ```verilog
> (11 & 13) + ((11 ^ 13) >> 1)
> = (b'1011 & b'1101) + ((b'1011 ^ b'1101) >> 1)
> = b'1001 + (b'0110 >> 1)
> = b'1001 + b'0011 = b'1100 = 12
> ```
### 比較在編譯器最佳化開啟時的組合語言輸出
:::info
環境: gcc version 9.3.0 (Ubuntu 9.3.0-17ubuntu1~20.04)
命令: gcc -S -O3 t.c
> 之後會嘗試改用 compiler explorer，以圖方便
測試程式 `t.c`
```c
#include <stdint.h>
uint32_t ver1(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (a & b & 1);
}
uint32_t ver2(uint32_t a, uint32_t b)
{
return (a & b) + ((a ^ b) >> 1);
}
```
:::
`A` 的對應組合語言
```go
movl %edi, %eax
movl %esi, %edx
andl %esi, %edi ;// a & b
shrl %eax ;// a >> 1
shrl %edx ;// b >> 1
andl $1, %edi ;// (a & b) & 1
addl %edx, %eax ;// （a >> 1）+ (b >> 1)
addl %edi, %eax ;// 加上 (a & b & １)
ret
```
`B` 的對應組合語言
```go
movl %edi, %eax
andl %esi, %edi ;// a & b
xorl %esi, %eax ;// a ^ b
shrl %eax ;// (a ^ b) >> 1
addl %edi, %eax ;// 相加
ret
```
發現 `B` 版本相比 `A` 版本
* 少了 1 次 `mov` 操作
* 少了 2 次 `and` 操作
* 少了 1 次 `shr` 操作
* 多了 1 次 `xor` 操作
> 註: 後綴 `l` 表示是針對 32-bit 暫存器的指令
> TODO: 以第一手資料解釋
## 測驗 `2`
考慮以下程式碼
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
填入 EXPx ，並
* 解釋上述程式碼運作的原理
* 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
* Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c... 請在 Linux 核心原始程式碼中，找出更多類似的實作手法。(請善用 git log 檢索)
### 運作原理
> 參考用真假值表
> | $\oplus$ | 0 | 1 | | $\wedge$ | 0 | 1 |
> | --- | --- | --- | --- | --- | --- | --- |
> | 0 | 0 | 1 | | 0 | 0 | 0 |
> | 1 | 1 | 0 | | 1 | 0 | 1 |
先不考慮兩者相等的情形
觀察程式碼，發現回傳 a ^ (...)
根據 [XOR ($\oplus$, `c:^`)](https://en.wikipedia.org/wiki/Exclusive_or) 的特性進行判斷
* $A \oplus 0 = A$ `恆等律`
得知當 $a > b$ 時， `(EXP4 & -(EXP5))` 的值為 0
* $A \oplus B \oplus B = A$ `自反律`
> 由 $A \oplus A = 0$ `歸零律` 且 $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ `結合律` 得知
得知當 $a < b$ 時， `(EXP4 & -(EXP5))` 的值為 `a ^ b`
> `a ^ a ^ b = b`
再觀察 `(EXP4 & -(EXP5))`
根據 [AND ($\wedge$, `c:&`)](https://en.wikipedia.org/wiki/Logical_conjunction) 的特性
* 任意 bit $a \wedge 1 = a$ `保真性`
=> `A & 0xFFFFFFFF = A` 其中 `0xFFFFFFFF` 為 -1 (2's complement)
* $A \wedge 0 = 0$ `保假性`
得知應控制 EXP5 的值，使其在 $a < b$ 時為 1， $a > b$ 時為 0
而 EXP4 則填入 `a ^ b` 使得 $a < b$ 時 `a ^ (...) = a ^ a ^ b = b`
綜上所述
* EXP4 應填入 `a ^ b`
* EXP5 應填入 `a < b` 或 `a <= b` （a, b 相等時回傳何者皆可）
使得結果 `a ^ ((a ^ b) & -(a < b))` 等於 `max(a, b)`
### 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
```c
int max(int a, int b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
無號數的情形即為題目的情形 （`uint32_t`）
而有號數也可用相同的方法求最大值
驗證如下
> 取 a = -5, b = 3
> ```verilog
> a = -5 = b'1011
> b = 3 = b'0011
> a ^ b = b'0111
> a < b = b'0001 (true)
> -b'0001 = b'1111
> b'0111 & b'1111 = b'0111
> b'1011 ^ b'0111 = b'0011 = 3
> ```
> 取 a = -5, b = -3
> ```verilog
> a = -3 = b'1011
> b = -5 = b'1101
> a ^ b = b'0110
> a < b = b'0001 (true)
> -b'0001 = b'1111
> b'0110 & b'1111 = b'0110
> b'1101 ^ b'0110 = b'1011 = -3
> ```
因此使用相同的程式碼即可對有/無號數作找最大值的運算
## 測驗 `3`
考慮以下 64 位元 GCD 求值函式
```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 (COND);
return RET;
}
```
補完上述程式碼，並
* 解釋上述程式運作原理
* 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升
* Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
### 運作原理
> 註: GCD 演算法
> 以測驗題目提供的演算法為基底，並補上兩者皆為奇數的情形，參考自 [Binary GCD algorithm](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
> ```pascal
> function GCD(x, y: integer): integer;
> begin
> if x = y and x = 0 then result := 0;
> if y = 0 then result := x;
> if x = 0 then result := y;
> (*because everything divides 0*)
> if x mod 2 = 0 and y mod 2 = 0 then result := 2 * GCD(x/2, y/2);
> (*because 2 is a common divisor,
> multiplication with 2 can be done with bitwise shift operation*)
> if x mod 2 = 0 and y mod 2 = 1 then result := GCD(x/2, y);
> if x mod 2 = 1 and y mod 2 = 0 then result := GCD(x, y/2);
> (*because 2 is not a common divisor*)
> if x mod 2 = 1 and y mod 2 = 1 then result := GCD(Abs(u - v), Min(u, v));
> (*gcd(u, v) = gcd(|u − v|, min(u, v)), if u and v are both odd.*)
> end;
> ```
參考上述 GCD 演算法
並以 u 紀錄結果，搭配 do-while 迴圈將遞迴去除
第 4 行是判斷 u, v 中是否有一者（或兩者）為 0
> $A \vee 0 = A$
> $0 \vee 0 = 0$
第 6 到第 8 行的 for 迴圈是當 u, v 皆為偶數時，將兩者均除以 2 ，並用 `shift` 紀錄待會要乘以 2 的次數
第 9 到第 10 行的迴圈不斷將 u 除以 2 直到它變成奇數
第 12 到第 13 行的迴圈不斷將 v 除以 2 直到它變成奇數
第 14 到第 20 行則是兩者皆為奇數的情形，相減並對 u - v 以及 u, v 中較小者作 GCD 直到出現 0
因此 21 行的 COND 應填入 `v` 判斷被減數 v 是否不為 0
而 RET 應填入 `u << shift` 將前面沒乘上的 2 通通乘回來
### 透過 `__builtin_ctz` 改寫
> Built-in Function: int __builtin_ctz (unsigned int x)
> Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
e.g. 6 = b'0110
__builtin_ctz(6) = 1 -> 最右邊的 1 右邊有 1 個 0
將連續除 2 的動作用 `__builtin_ctz` 替代
> e.g.
> ```verilog
> 連續除以 2
> 4 = b'0100
> 2 = b'0010
> 0 = b'0001
> 使用__builtin_ctz()
> __builtin_ctz(4) = 2
> 4 >> 2 = b'0100 >> 2 = b'0010 = 0
> ```
> 本來還想把判斷 0 的動作也替換，後來發現當它為 0 時行為未定
改寫實作
> 因為是 uint64_t 故使用 __builtin_ctzll (unsigned long long 版本)
```c
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift = (__builtin_ctzll(u) > __builtin_ctzll(v)) ? __builtin_ctzll(v) : __builtin_ctzll(u);
u >>= __builtin_ctzll(u);
v >>= __builtin_ctzll(v);
do {
v >>= __builtin_ctzll(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
## 測驗 `4`
在影像處理中，bit array 被廣泛使用，如
```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 = EXP6;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 `b'000101`，那 t 就會變成 `b'000001`，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。
填入 EXP6 ，並
* 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中
* 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density
* 思考進一步的改進空間
* 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例
### 填空
3 bits 時二補數的編碼
| | 1 | 2 | 3 |
| - | --- | --- | --- |
| + | 001 | 010 | 011 |
| - | 111 | 110 | 101 |
|+&-| 001 | 010 | 001 |
可以發現將 $A \wedge (\sim A + 1)$ (`c: A & (-A)`) 會得到最低位元的 1
> 以 bitset = 20 = `b'00010100` 為例
> -bitset = ~bitset + 1 = `b'11101011` + `1` = `11101100`
> bitset & -bitset = `b'00000100` 即為所求
其中 unsigned 與 signed 僅為判讀上的差異，實際上存的 bitmap 皆相同
在 bitwise 操作時使用 unsigned 以獲得更大的可攜性 [你所不知道的 c 語言 - bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)
> printf(...) 中 %d 會以 signed 的方式判讀，而 %u 會以 unsigned 的方式判讀
因此 EXP6 應填入 `bitset & -bitset`
## 測驗 `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 (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, EEE);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
```
補完程式碼，並
* 解釋上述程式碼運作原理，指出其中不足，並予以改進
> 例如，判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
> 搭配研讀 The simple math behind decimal-binary conversion algorithms
* 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
## 測驗 `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)->M) - (char *)X)
```
補完程式碼，並
* 解釋上述程式碼運作原理
* 在 Linux 核心原始程式碼中找出 `__alignof__` 的使用案例 2 則，並針對其場景進行解說
* 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
### 填空
```graphviz
digraph g_align{
rankdir = LR
node[shape=record]
s [label="<c>char c| padding | <h>t _h "]
node[shape=plaintext]
0 -> s:c
p -> s:h
}
```
如圖，利用 struct 自動 alignment 來算出 alignment 大小
> char: 1 byte
> t: ? byte，$\geq$ 1，mod 4 = 0
> 所以會以 t 的大小作對齊
將 p 的記憶體位置減去 0 即為所求
因此 M 應填入 `_h` 以取得第三個區塊的開頭位置
而由前面 `(struct {char c; t _h} *)0` 可知 X 應填入 `0` ，才會在同個起始位置
```c
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
```
## 測驗 `7`
考慮針對 FizzBuzz
> * 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
> * 如果是 5 的倍數，印出 “Buzz”
> * 如果是 15 的倍數，印出 “FizzBuzz”
> * 如果都不是，就印出數字本身
的實作
```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"[(9 >> div5) >> (KK3)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
補完，並
* 解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
* 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
* 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
* 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
* 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
* 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)
* 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
Sign in with Wallet
Connect another wallet