# [2022q1](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 2 週測驗題
###### tags: `linux2022`
:::info
目的: 檢驗學員對 **[數值系統](https://hackmd.io/@sysprog/c-numerics), [linked list](https://hackmd.io/@sysprog/c-linked-list), [bitwise](https://hackmd.io/@sysprog/c-bitwise)** 的認知
:::
==[作答表單: 測驗 1-4](https://docs.google.com/forms/d/e/1FAIpQLSf80zijSR-BFkgmQULgOS2-6m0HhFkJ7XYN85kpeUtzxd0rdg/viewform)== (Linux 核心設計)
==[作答表單: 測驗 5-7](https://docs.google.com/forms/d/e/1FAIpQLScn1eavQ3ecWxw3pfujjm_6ENGDC3uo8Ks3smTfT0dMhaHHBw/viewform)== (Linux 核心實作)
### 測驗 `1`
考慮以下對二個無號整數取平均值的程式碼:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
接著我們可改寫為以下等價的實作:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
其中 `EXP1` 為 `a`, `b`, `1` (數字) 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:
* 運算子和運算元之間用一個半形空白區隔，如: `a | b ^ 1`
* `EXP1` 必定包含 `a`, `b`, 及 `1` (數字) 等字元
* 總是先寫 `a` 再寫 `b`
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
我們再次改寫為以下等價的實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
其中 `EXP2` 和 `EXP3` 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:
* 運算子和運算元之間用一個半形空白區隔，如: `a | b`
* `EXP2` 和 `EXP3` 必定包含 `a` 和 `b` 字元
* 總是先寫 `a` 再寫 `b`
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
> 延伸閱讀: [Introduction to Low Level Bit Hacks](https://catonmat.net/low-level-bit-hacks)
==作答區==
`EXP1` = ?
`EXP2` = ?
`EXP3` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作的原理
2. 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 [CS:APP 第 3 章](https://hackmd.io/@sysprog/CSAPP-ch3))
3. 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)，探討其 [Exponentially weighted moving average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) (EWMA) 實作，以及在 Linux 核心的應用
> 移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
> 移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的[閾值](https://terms.naer.edu.tw/detail/1085244/)取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
---
### 測驗 `2`
改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 `min`，我們得到以下實作 (`max`):
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
其中 `EXP4` 為 `a` 和 `b` 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子。書寫規範:
* 運算子和運算元之間用一個半形空白區隔，如: `a | b ^ 1`
* `EXP4` 必定包含 `a` 和 `b` 字元
* 總是先寫 `a` 再寫 `b`
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
`EXP5` 為 `a` 和 `b` 的比較操作，亦即 logical operator，限定用 `>`, `<`, `==`, `>=`, `<=`, `!=` 這 6 個運算子。書寫規範:
* 運算子和運算元之間用一個半形空白區隔，如: `a > b`
* `EXP5` 必定包含 `a` 和 `b` 字元
* 總是先寫 `a` 再寫 `b`
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
> 延伸閱讀:
> * [That XOR Trick](https://florian.github.io/xor-trick/)
> * video: [Branchless Programming: Why "If" is Sloowww... and what we can do about it!](https://youtu.be/bVJ-mWWL7cE)
> * [Making Your Code Faster by Taming Branches](https://www.infoq.com/articles/making-code-faster-taming-branches/)
==作答區==
`EXP4` = ?
`EXP5` = ?
:::success
延伸問題:
1. 解釋上述程式碼運作的原理
2. 針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作
3. Linux 核心也有若干 branchless / branch-free 的實作，例如 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c):
```c
/*
* Logically, we're doing "if (i & lsbit) i -= size;", but since the
* branch is unpredictable, it's done with a bit of clever branch-free
* code instead.
*/
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
i -= size;
i -= size & -(i & lsbit);
return i / 2;
}
```
請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 `git log` 檢索。
:::
----
### 測驗 `3`
考慮以下 64 位元 GCD ([greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), 最大公因數) 求值函式:
```cpp
#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;
}
```
註: GCD 演算法
1. If both x and y are 0, gcd is zero $gcd(0, 0) = 0$.
2. $gcd(x, 0) = x$ and $gcd(0, y) = y$ because everything divides $0$.
3. If x and y are both even, $gcd(x, y) = 2*gcd(\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor. Multiplication with $2$ can be done with bitwise shift operator.
3. If x is even and y is odd, $gcd(x, y) = gcd(\frac{x}{2}, y)$.
4. On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \frac{y}{2})$. It is because $2$ is not a common divisor.
改寫為以下等價實作:
```cpp
#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;
}
```
請補完程式碼。書寫規範:
* 運算子和運算元之間用一個半形空白區隔，如: `u | v`
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
==作答區==
`COND` = ?
`RET` = ?
:::success
延伸問題:
1. 解釋上述程式運作原理;
2. 在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升;
3. Linux 核心中也內建 GCD (而且還不只一種實作)，例如 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c)，請解釋其實作手法和探討在核心內的應用場景。
:::
---
### 測驗 `4`
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 `bitset`) 廣泛使用，考慮以下程式碼:
```cpp
#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;
}
```
考慮 GNU extension 的 [`__builtin_ctzll`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 `0` 才碰到 `1`。
> 範例: 當 `a = 16`
> `16` 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
> 從低位元 (即右側) 往高位元，我們可發現 $0 \to 0 \to 0 \to 0 \to 1$，於是 ctz 就為 4，表示最低位元往高位元有 4 個 `0`
用以改寫的程式碼如下:
```cpp=
#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` 為 $000101_b$，那 `t` 就會變成 $000001_b$，接著就可以透過 XOR 把該位的 `1` 清掉，其他保留 (此為 XOR 的特性)。
若 bitmap 越鬆散 (即 `1` 越少)，於是 `improved` 的效益就更高。
請補完程式碼。書寫規範:
* bitwise 運算子和運算元之間用一個半形空白區隔，如: `bitset | 0x1`
* 考慮到 `-bitwise` 的特性
* 不要包含任何小括號，即 `(` 和 `)`
* 以最精簡的形式撰寫程式碼
==作答區==
`EXP6` = ?
:::success
延伸問題:
1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
2. 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
3. 思考進一步的改進空間;
4. 閱讀 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 並舉出 Linux 核心使用 bitmap 的案例;
:::
---
### 測驗 `5`
以下是 LeetCode [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作:
```cpp
#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;
}
```
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
作答區
`PPP` = ? (表示式)
`MMM` = ? (List API 函式)
`EEE` = ? (表示式)
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出其中不足，並予以改進
> 例如，判斷負號只要寫作 `bool isNegative = numerator < 0 ^ denominator < 0;`
> 搭配研讀 [The simple math behind decimal-binary conversion algorithms](https://indepth.dev/posts/1019/the-simple-math-behind-decimal-binary-conversion-algorithms)
2. 在 Linux 核心原始程式碼的 `mm/` 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
:::
---
### 測驗 `6`
[`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 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)
```
請補完上述程式碼，使得功能與 [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 等價。
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
作答區
M = ?
X = ?
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼中找出 [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 的使用案例 2 則，並針對其場景進行解說
3. 在 Linux 核心源使程式碼找出 `ALIGN`, `ALIGN_DOWN`, `ALIGN_UP` 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
:::
---
### 測驗 `7`
考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3的倍數，印出 "Fizz"
* 如果是 5 的倍數，印出 "Buzz"
* 如果是 15 的倍數，印出 "FizzBuzz"
* 如果都不是，就印出數字本身
直覺的實作程式碼如下: (`naive.c`)
```cpp
#include <stdio.h>
int main() {
for (unsigned int i = 1; i < 100; i++) {
if (i % 3 == 0) printf("Fizz");
if (i % 5 == 0) printf("Buzz");
if (i % 15 == 0) printf("FizzBuzz");
if ((i % 3) && (i % 5)) printf("%u", i);
printf("\n");
}
return 0;
}
```
觀察 `printf` 的(格式)字串，可分類為以下三種:
1. 整數格式字串 `"%d"` : 長度為 2 B
2. "Fizz" 或 "Buzz" : 長度為 4 B
3. "FizzBuzz" : 長度為 8 B
考慮下方程式碼:
```cpp
char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
```cpp
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
```cpp
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;
}
```
其中 `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/)，甚至 gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
對於處理器來說，每個運算所花的成本是不同的，比如 `add`, `sub` 就低於 `mul`，而這些運算的 cost 又低於 `div` 。依據〈[Infographics: Operation Costs in CPU Clock Cycles](http://ithare.com/infographics-operation-costs-in-cpu-clock-cycles/)〉，可發現整數除法的成本幾乎是整數加法的 50 倍。
所以如何處理 `div` 運算是每個編譯器最佳化都關注的議題。考慮 $\dfrac{n}{d}$，$d$ 是一個 constant，除式可以表示成 $n \times (\dfrac{2^n}{d}) \times \dfrac{1}{2^n}$，若 $d$ 是 2 的冪，可以將除法轉換成乘法跟位移，cost 會比 `div` 少很多，如果除數 $d$ 不是 2 的冪，則 $\dfrac{2^n}{d}$ 需要做一些特別的處理，在若干微處理器架構中，若 $n$ 足夠大，其實 $\dfrac{2^n}{d}$ 可事先預估。
文章中還有介紹一些其他的除法如下:
* [Division by invariant integers using multiplication](https://dl.acm.org/doi/10.1145/773473.178249), by Granlund and Montgomery (1994)
* [Hacker's Delight](https://www.amazon.com/Hackers-Delight-2nd-Henry-Warren/dp/0321842685/), by Warren
* [N-Bit Unsigned Division via N-Bit Multiply-Add](https://www.computer.org/csdl/proceedings-article/arith/2005/23660131/12OmNyQYt7U), by Robison
作答區
`KK1` = ? (變數名稱)
`KK2` = ? (變數名稱)
`KK3` = ? (表示式，不包含小括號)
:::success
延伸問題:
1. 解釋上述程式運作原理並評估 `naive.c` 和 `bitwise.c` 效能落差
* 避免 stream I/O 帶來的影響，可將 `printf` 更換為 `sprintf`
2. 分析 [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/) 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 `bitwise.c` 程式碼，試圖運用更少的指令來實作出 branchless;
* 參照 [fastmod: A header file for fast 32-bit division remainders on 64-bit hardware](https://github.com/lemire/fastmod)
3. 研讀 [The Fastest FizzBuzz Implementation](https://tech.marksblogg.com/fastest-fizz-buzz.html) 及其 [Hacker News 討論](https://news.ycombinator.com/item?id=29413656)，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
4. 解析 Linux 核心原始程式碼 [kernel/time/timekeeping.c](https://github.com/torvalds/linux/blob/master/kernel/time/timekeeping.c) 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 `kernel/time/` 目錄的標頭檔和程式碼)
> 過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
:::
---
Sign in with Wallet
Connect another wallet