---
tags: linux kernel
---
# 2022q1 Homework2 (quiz2)
contributed by < `jimmyliu-1021` >
## 測驗 1
考慮以下對2個無號整數取平均值的程式碼：
```c
#include <stdint.h>
uint32_t average(uint_t a, uint_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;
}
```
接著我們用 bit-wise operation 可改寫為以下等價的實作：
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
:::info
這段程式碼將 a, b 都先右移 1 bit ，相當於除2
考慮 a, b 的 least significant bit ( LSB ) 皆為 1 時，應該要進位
故 `EXP1` 為 `(a & b & 1)` ，其中 `&1` 相當於 bit-mask ，用於取得 LSB
:::
我們再次改寫為以下等價的實作：
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
:::info
[數值系統的 bit-wise operator 筆記](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator) 中，提及加法器思考 `(x & y) << 1` 是進位值， `x ^ y` 是不進位的位元和，其中使用 `^` (XOR) 可以避免 overflow
:::
因此 `x + y` 等同於 `x ^ y + (x & y) << 1`
這段程式碼要取 a, b 的平均，所以可寫成 `(a ^ b + (a & b) << 1) >> 1`
再簡化後可得 `(a & b) + (a ^ b) >> 1`
`EXP2` = `a & b`
`EXP3` = `a ^ b`
:::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)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
---
## 測驗 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));
}
```
:::info
查閱 `min`程式碼：
```c
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
其中關鍵在於 `& (diff >> 31)` 這個操作
由於 `diff` 是一個32位元有號整數，在[C99定義 : C99 Standard - 6.5.7.5](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)中提到負整數右移是 implementation-defined ，所以在不同環境下可能會有不同結果。
>The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
(詳細可閱讀[解讀計算機編碼](/vOjbtew3Tn2aA0uDrmUL4Q)常數時間實作)
此處假設右移時採用 arithmetic shift
- 當 a > b 時， `diff` 為正整數，右移31位可得 `0x000000000` =>`0`
所以 `(diff & (diff >> 31)` 值為 `0`
- 當 a < b 時， `diff` 為負整數，右移31位可得 `0xfffffffff` => `-1`
所以 `(diff & (diff >> 31)` 值為 `diff` =>`a - b`
:::
改寫 `max`程式碼：
由函式行為反推
- 當 a > b 時， `(EXP4 & -(EXP5))` 應該是 `0`
- 當 a < b 時， 由於要 return `b`
故 `a` 應該先與自己做 `XOR`運算得出 `0`
再與 `b` 做`XOR` 即可得到 `b`
此時 `(EXP4 & -(EXP5))` 應該是 `a ^ b`
結合老師的提示：
- `EXP4` 為 `a` 和 `b` 的特別bitwise操作，限定用 `OR`, `AND`, `XOR` 三種運算子
- `EXP5` 為 `a` 和 `b` 的比較操作，限定用 `>`, `<`, `==`, `>=`, `<=` ,`!=` 六種運算子
由於`EXP5` 是比較式，只回傳 1 跟 0
與上述 `min` 的關鍵操作比較，可得知 `EXP4`是 `a ^ b`
而 `EXP5` 則是 `a < b`
:::success
延伸問題
解釋上述程式碼運作的原理
針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作
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), 最大公因數) 求值函式:
```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;
}
```
註：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 \times gcd(\dfrac{x}{2},\dfrac{y}{2})$ because $2$ is a common divisor. Mulitplication with $2$ can be done with bitwise shift operator.
4. If x is even and y is odd, $gcd(x, y) = gcd(\dfrac{x}{2}, y)$.
5. On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \dfrac{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 (COND);
return RET;
}
```
請補完程式碼。書寫規範:
- 運算子和運算元之間用一個半形空白區隔，如: `u | v`
- 不要包含任何小括號，即 `(` 和 `)`
- 以最精簡的形式撰寫程式碼
題目要填入 `COND` 與 `RET` ，而後半的 if else 是根據輾轉相除法實作的結果：
```c
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
```
:::info
輾轉相除法運算至最後一個步驟時，所剩兩數分別是 `GCD` 及 `0`
:::
1. 從此段程式碼可以分析出，由於 `v` 必須比 `u` 小，因此最後變成 `0` 的變數是 `v`，也因此跳出輾轉相除法的條件 `COND` = `v`
2. `u` 便是此函式該回傳的值，也就是 `GCD` ，然而根據題目給的提示：
**gcd演算法，若 u, v 皆為偶數： gcd(u, v) = 2 * gcd(u/2, v/2)**
```c
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
在這段 for 迴圈中，`u` 與 `v` 將不斷同除以 2 ，直至其中一者不為 2 的倍數，並將除以 2 的次數記錄在 `shift` 中，因此需要將 `u` 左移 `shift` 個 bits 還原，所以 `RET` = `u << shift`
:::success
延伸問題:
1. 解釋上述程式運作原理;
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
/*
* 根據gcd演算法： gcd(u, 0) = u; gcd(0, v) = v
*/
if (!u || !v) return u | v;
/*
* 根據gcd演算法，若 u, v 皆為偶數： gcd(u, v) = 2 * gcd(u/2, v/2)
* 並將除以2的次數(右移次數)記錄在shift
*/
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
/*
* 經過上述的for迴圈，u 跟 v 必有其中一個是 odd number
* 根據gcd演算法： gcd(even, odd) = gcd(even/2, odd)
* 將 u 跟 v 持續除以2直到兩者皆為 odd
* 再以輾轉相除法計算 u 與 v 的最大公因數
* 算出來後左移shift次數才是原始的最大公因數
*/
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;
}
```
2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
3. Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
:::
---
## 測驗 4
在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 `bitset`) 廣泛使用，考慮以下程式碼:
```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;
}
```
考慮 GNU extension 的 [`__builtin_ctzll`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
> 範例: 當 a = 16
16 這個十進位數值的二進位表示法為 00000000 00000000 00000000 00010000
從低位元 (即右側) 往高位元，我們可發現0→0→0→0→1，於是 ctz 就為 4，表示最低位元往高位元有 4 個 0
用以改寫的程式碼如下:
```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` 為 $000101_b$，那 `t` 就會變成$000001_b$，接著就可以透過 XOR 把該位的 `1` 清掉，其他保留 (此為 XOR 的特性)。
若 bitmap 越鬆散 (即 `1` 越少)，於是 `improved` 的效益就更高。
請補完程式碼。書寫規範:
- bitwise 運算子和運算元之間用一個半形空白區隔，如: `bitset | 0x1`
- 考慮到 `-bitwise` 的特性
- 不要包含任何小括號，即 `(` 和 `)`
- 以最精簡的形式撰寫程式碼
根據提示第九行要做的事是找出最低位的 `1`
而在 [How can I get the value of the least significant bit in a number?](https://stackoverflow.com/questions/18806481/how-can-i-get-the-value-of-the-least-significant-bit-in-a-number#:~:text=To%20be%20sure%20you%20get,log2(x%20%26%20%2Dx)) 此篇中的討論可見，答案應該是 `bitset & -bitset`
其實就是把 bitset 與其二進位補數作 bitwise 的 AND 運算，這使得 bitset 僅保留最低位數的 1，等同於將 `1 << __builtin_ctz(bitset)`
:::success
延伸問題:
1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
2. 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
3. 思考進一步的改進空間;
4. 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;
:::
---
## 測驗 `5`
以下是 LeetCode [166. Fraction to Recurring Decmial](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;
}
```
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
作答區
`PPP` = ? (表示式)
`MMM` = ? list_add_tail(&node->link, result)(List API 函式)
`EEE` = ? (表示式)
---
## 測驗 `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) 等價
作答區：
在理解 `ALIGNOF` 以前，先理解 [`offsetof macro`](https://www.embedded.com/learn-a-new-trick-with-the-offsetof-macro/)
```c
// Keil 8051 compiler
#define offsetof(s,m) (size_t)&(((s *)0)->m)
// Microsoft x86 compiler (version 7)
#define offsetof(s,m) (size_t)(unsigned long)&(((s *)0)->m)
// Diab Coldfire compiler
#define offsetof(s,memb) \
((size_t)((char *)&((s *)0)->memb-(char *)0))
/*
* (size_t)( ...6
* (char *) ...4
* &( ...3
* ((s *)0) ...1
* )->memb ...2
* - (char *)0 ...5
* )
* 1: takes the integer zero and casts it as a pointer to s .
*
* 2: dereferences that pointer to point to structure member memb .
* 3: computes the address of memb .
* # the priority of -> is higher than &
*
* 4: casts the result as a pointer to char.
* 5: minus a pointer to char which is casting from 0
*
* 6: return an appropriate data type
*/
```
- 1.先將 `0` 轉型為 `struct *` ，這麼做是在將此結構的起始位址定在 `0` ，以便後續對齊並得出該結構成員 `memb` 的地址位移 `offset`。
- 2.3.指向成員 `memb` 並取得地址
- 4.5.將 `memb` 和 `0` 的地址相減取得 `offset`。並且，此處將地址轉型成 `(char *)` ，意思是以一個字節 `sizeof(char) = 1 byte` 作為單位來算 `offset`
- 6.取得 `memb` 在結構中的位置，並回傳 `size_t` 型態的值。
理解後再來解析 `ALIGNOF`：
```c
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)
/*
* (
* (char *) ...4
* &( ...3
* (struct {char c; t _h;} *)0 ...1
* )->M ...2
* - (char *)X...5
* )
```
- 1. 將 `0` 轉型為 `struct *` 並且 struct 包含成員 `char c` 與 `t _h`，此表示將 `0` 視為該結構的起始位址，其中 `c` 作為第一個成員，其起始位址與結構體相同。
- 2.3. 將此 `struct *` 指向 M 並取出其地址，所以根據上面的經驗可以得知，M 為要測試的成員，所以是 `_h`
- 4.5. 減去 X 的位址，並且單位是 `size of char`，由 `1.` 可以得知此處應該是 `0`
所以此 `macro` 功能為計算 `type t` 在當前環境的 `alignment`
:::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`
```c
#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
考慮下方程式碼:
```c
char fmt[M9];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意：
```c
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: `bitwise.c`
```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;
}
```
Sign in with Wallet
Connect another wallet