---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `hsuedw` >
* [作業需求](https://hackmd.io/@sysprog/BybKYf5xc)
* [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz2#2022q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
* [作業繳交區](https://hackmd.io/@sysprog/linux2022-homework2)
---
# 測驗 1
## 題目
* 以 bitwise 操作對兩個無號整數取平均值。
* 也就是撰寫程式碼 2 中的 `EXP1` 使其功能等價於程式碼 1。
* 也就是撰寫程式碼 3 中的 `EXP2` 與 `EXP3` 使其功能等價於程式碼 1。
* 程式碼 1
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a + b) / 2;
}
```
* 程式碼 2
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
* 程式碼 3
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
## 作答
* `EXP1` = `a & b & 1`
* 假設 $b \ge a$
* `EXP2` = `a & b`
* `EXP3` = `a ^ b`
## 延伸問題 1. 解釋上述程式碼運作的原理
* 程式碼 2 運作的原理
* 在 bitwise 運算中，向左位移一個 bit 就相當於 $\lfloor x \rfloor$，其中 $x = \dfrac{a}{2}$
* 雖然在數學上 $\dfrac{a+b}{2}$ = $\dfrac{a}{2}$ + $\dfrac{b}{2}$，但是在 C 語言中，當 a 與 b 皆為奇數時，因為 a 與 b 皆個別先除以 2 再相加，所以平均值會少 1。假設 a = 3，b = 5。
* (a + b) / 2 = 4
* a / 2 + b / 2 = 3
* 若 a 與 b 為一奇一偶或皆為偶數，則沒有這個現象。
* 一個奇數的二進為編碼中，LSB 必為 1。若 `a & b` 的 LSB 為 1，表示 a 與 b 皆為奇數。所以將 EXP1 實作為 `a & b & 1` 可補上當 a 與 b 皆為奇數時，各別先除二再相加所少掉的那個 1。
* 程式碼 3 運作的原理
* AND 與 XOR 的真值表如下所示。
| | | AND | XOR |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
* 一個位元的加法運算如下所示。觀察後可發現進位 (carry) 那一欄就是 AND 運算。 bit sum 那一欄就是 XOR 運算。所以可以用 AND 與 XOR 進行加法運算。
| | carry | bit sum |
| ------ | ----- | ------- |
| 0 + 0 | 0 | 0 |
| 0 + 1 | 0 | 1 |
| 1 + 0 | 0 | 1 |
| 1 + 1 | 1 | 0 |
* 對兩個整數 a 與 b 做加法。 `a ^ b` 就是每個位元的各別位元和。 `(a & b) << 1` 就是兩數相加後，各別位元的進位狀況。所以，C 語言程式碼中， `a + b` 可改寫為 `(a ^ b) + ((a & b) << 1)`。
* `(a + b) / 2` 就是 `(a + b) >> 1`。
* 所以， `(a + b) >> 1` 就是 `((a ^ b) + ((a & b) << 1)) >> １`。展開後就可以得到 `(a & b) + (a ^ b) >> 1`。
* 所以，`EXP2` 可實作為 `a & b` ， `EXP3` 可實作為 `a ^ b`。
* 參考資料:
* [解讀計算機編碼](https://hackmd.io/vOjbtew3Tn2aA0uDrmUL4Q?view#%E8%A7%A3%E8%AE%80%E8%A8%88%E7%AE%97%E6%A9%9F%E7%B7%A8%E7%A2%BC)
* [你所不知道的 C 語言：數值系統篇, 運用 bit-wise operator](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)
* [以 C 語言實作二進位加法 (Binary Addition)](https://kopu.chat/%e4%bb%a5c%e5%af%a6%e4%bd%9c%e4%ba%8c%e9%80%b2%e4%bd%8d%e5%8a%a0%e6%b3%95/)
## 延伸問題 2. 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
* working
## 延伸問題 3. 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
> 移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
> 移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
* working
---
# 測驗 2
## 題目
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
## 作答
* `EXP4`: `a ^ b`
* `EXP5`: `a < b`
## 延伸問題 1. 解釋上述程式碼運作的原理
* 列舉部分 AND 與 XOR 運算的特性。
* a ^ a = 0
* a ^ 0 = a
* a ^ 0xffffffff = 0 (假設 a 為 32 位元整數)
* a & a = a
* a & 0 = 0
* a & 0xffffffff = a
* 為了說明方便，把程式碼補齊，如下所示。
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
* 假設 a > b
* `a ^ ((a ^ b) & -(a < b))`
* ⇒ `a ^ ((a ^ b) & -(0))`
[C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 6.5.8 Relational operators
> Each of the operators < (less than), > (greater than), <= (less than or equal to), and >= (greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.) The result has type int.
* ⇒ `a ^ ((a ^ b) & 0)`
* ⇒ `a ^ (0)`
* ⇒ `a`
* 假設 a < b
* `a ^ ((a ^ b) & -(a < b))`
* ⇒ `a ^ ((a ^ b) & -(1))`
* ⇒ `a ^ ((a ^ b) & 0xffffffff)`
* ⇒ `a ^ (a ^ b)`
* ⇒ `(a ^ a) ^ b`
* ⇒ `(0) ^ b`
* ⇒ `b`
* 假設 a = b
* `a ^ ((a ^ b) & -(a < b))`
* ⇒ `a ^ ((a ^ a) & -(a < a))`
* ⇒ `a ^ ((0) & -(1))`
* ⇒ `a ^ (0x00000000 & 0xffffffff)`
* ⇒ `a ^ (0)`
* ⇒ `a`
* 參考資料:
* [Compute the minimum or maximum of two integers without branching](https://www.geeksforgeeks.org/compute-the-minimum-or-maximum-max-of-two-integers-without-branching/)
## 延伸問題 2. 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
* working
## 延伸問題 3. Linux 核心也有若干 branchless / branch-free 的實作，例如 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 ∗ gcd(\dfrac{x}{2},\dfrac{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(\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;
}
```
## 作答
* `COND` = `v`
* `RET` = `u << shift`
## 延伸問題 1. 解釋上述程式運作原理
* 就是題目附註裡寫的 GCD 演算法。
## 延伸問題 2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
* working
## 延伸問題 3. Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
* working
---
# 測驗 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 extenstion 的 [__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 的特性
* 不要包含任何小括號，即 ( 和 )
* 以最精簡的形式撰寫程式碼
## 作答
* `EXP6` = `-bitset & bitset`
## 延伸問題 1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中
* 運作原理
* 假設 `bitset` 的二進位表示法中，由 LSB 往 MSB 數，遇到第一個 `1` 前，有 x 個 `0`。目標就是保留位元 x 為 1。其餘位元皆設為 `0`。
* 假設 `bitset` = 1312~10~ = 0000010100100000~b~
* 則 `-bitset` = -1312~10~ = 1111101011100000~b~
* 所以， `-bitset & bitset` 結果如下。
```
1111101011100000
& 0000010100100000
---------------------
0000000000100000
```
* 用在哪些真實案例中
* working
## 延伸問題 2. 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density
* working
## 延伸問題 3. 思考進一步的改進空間
* working
## 延伸問題 4. 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例
* working
---
# 測驗 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;
}
```
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
PPP = ? (表示式)
MMM = ? (巨集)
EEE = ? (表示式)
## 作答
* `PPP` = `pos--`
* `MMM` = `list_add`
* `EEE` = `&heads[remainder % size]`
## 延伸問題 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)
* 第 26~24 行。
* 用 `malloc` 動態宣告一個長度為 1024 bytes 的記憶體空間。用這個記憶體空間存字串。並用 `result` 這個指標指向這個記憶體空間的起始位址。然後再宣告一個指標 `p` 用來操作 `result` 所指向的記憶體空間。原則上，就是用 `result` 所指向的記憶體空間做出一個 C sytle string。
* 根據題意，將計算結果表示為字串，此字串長度小於 10^4^。所以，將變數 `size` 初始化為 1024 並以此宣告記憶體大小，顯然有問題。
:::info
It is guaranteed that the length of the answer string is less than 10^4^ for all the given inputs.
:::
* 若考慮 C style string 的 null terminator。 `size` 應初始化為 10001 較為恰當。
* 第 30~32 行。
* 若 `denominator` (分母)為 0，則回傳空字串。
* 事實上，這個判斷可以刪除，不需要實作這三行。因為題目的 constraints 中已經明白的說明了分子與分母的數值範圍。根據題意，分母不可能為 0。
:::info
Constraints:
* -2^31^ <= numerator, denominator <= 2^31^ - 1
* denominator != 0
:::
* 第 35~39 行。
* 若 `numerator` 為 0，則計算結果必為 0。所以直接在 `result` 所指向的記憶體空間的第一個字元填 `0`，第二個字元填 `\0` (null terminator)。並回傳此 C style string。
* 第 41~53 行。
* 用兩個型態為 `long long` 的變數 `n` 與 `d` 分別儲存 `numerator` 與 `denominator` 的數值。並對 `n` 與 `d` 取絕對值。若 `numerator` 除以 `denominator` 是負數，在第 51~53 行中，把負號填入 `result` 所指向的記憶體空間的第一個字元。然後，指標 `p` 往後移一個 byte。
* 第 51~53 行中判斷最後的答案是否有負號，可改為下列的實作。因為 `numerator` 和 `denominator` 不同時為正數或不同時為負數，最後的答案就會有負號。所以可用 XOR 實作。
```c=51
bool sign = (numerator < 0) ^ (denominator < 0);
if (sign)
*p++ = '-';
```
* 第 55~63 行。
* 分別把 `n` 除以 `d` 的餘數與商數指派給 `remainder` 與 `division` 兩個變數中。
* 以指標 `p` 所指的記憶體位址為起始，用 `sprintf` 與格式化字串把 `division` 列印到 `result` 所指向的記憶體空間。
* 因為第 46~53 已經處理了正負號的問題，所以執行到第 58 行時， `division` 必為正數。第 58 行應改為:
```c=58
sprintf(p, "%ld", (long) division);
```
* 若 `remainder` (餘數)為 0 ，表示整除。可以直接回傳 `result` 所指向的記憶體空間內的字串。
* 若 `remainder` (餘數)不為 0 ，表示有小數位數。所以將指標 `p` 移到字串的尾端(第 62 行)後，在字串尾端加入小數點。
* 第 68~70 行。
* 以指標 `decimal` 指向以 `size` 為大小所動態宣告的記憶體空間。並將此記憶體空間的內容清為 0。
* 以指標 `q` 為操作 `decimal` 所指向的記憶體空間。
* 因為題目已經保證最後的答案部會超過 10^4^，所以第 68~69 行可以改為
```c=68
char *decimal = malloc(size - strlen(result));
memset(decimal, 0, size - strlen(result));
char *q = decimal;
```
* 第 72~75 行。
* 建立並初始化一個有 1333 個 bucket 的 hash table (指標 `heads` 所指的記憶體空間)。每個 bucket 都是一個環狀雙向鏈結串列。
* 不了解為什麼要 1333 個 bucket。
* 第 77~97 行。
* 這個 `for` 迴圈會一直執行到 `remainder` 等於 0 為止。
* `for` 迴圈的 i 等於 0，表示小數點後第一位；i 等於 1，表示小數點後第二位
* 若在 hash table 中找到 `remainder`，代表發生循環小數。
* 透過指標 `p` 的操作，把 `decimal` 裡的資料複製到 `result` 所指向的記憶體空間中。 (第 80~81 行)
* pos 是循環小數開始的位置，所以先將尚未循環的小數位數填到 `result` 所指向的記憶體空間中。
* 透過指標 `p` 的操作，在字串最後加上 open parenthesis。(第 82 行)
* 透過指標 `p` 的操作，再把 `decimal` 中剩下的循環小數填到 `result` 所指向的記憶體空間中。(第 83~84 行)
* 透過指標 `p` 的操作，在字串最後加上 closing parenthesis。(第 85 行)
* 最後，透過指標 `p` 的操作，填上 `'\0'` (null terminator)。然後回傳結果(就是 result` 所指向的記憶體空間中的 C style string)。 (第 86~87 行)
* 若在 hash table 中找不到 `remainder`，代表沒有發生循環小數。
* 用動態記憶體宣告產生一個 `struct rem_node` 型態的 object，並以指標 `node` 指向它。利用此物件把這一次的 `numerator` 與 `i` 記錄在 hash table (指標 `heads` 所指的記憶體空間)中。 (第 89~91 行)
* 透過指標 `q` 的操作，將小數點後的第一位寫入 `decimal` 所指向的記憶體空間中的字串的尾端。 (第 95 行)
* 更新 `remainder` 。 (第 96 行)
* 第 99~100 行
* 若第 77~97 行的 `for` 迴圈結束(`remainder` 歸 0)，表示沒有循環小數發生。把 `decimal` 裡的所有字元全部複製到 `result` 所指向的記憶體空間中的字串的尾端。
* 回傳最後結果。
:::spoiler 完整程式碼
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#define list_entry(node, type, member) container_of(node, type, member)
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member))
#define list_for_each_entry(entry, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member); \
&entry->member != (head); \
entry = list_entry(entry->member.next, __typeof__(*entry), member))
#define list_last_entry(head, type, member) \
list_entry((head)->prev, type, member)
typedef struct {
int capacity, count;
struct list_head dhead, hheads[];
} LRUCache;
typedef struct {
int key, value;
struct list_head hlink, dlink;
} LRUNode;
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
static inline void list_add(struct list_head *node, struct list_head *head)
{
struct list_head *next = head->next;
next->prev = node;
node->next = next;
node->prev = head;
head->next = node;
}
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
static inline void list_move(struct list_head *node, struct list_head *head)
{
list_del(node);
list_add(node, head);
}
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 = 10001;
char *result = malloc(size);
char *p = 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 = (numerator < 0) ^ (denominator < 0);
if (sign)
*p++ = '-';
long long remainder = n % d;
long long division = n / d;
sprintf(p, "%ld", (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 - strlen(result));
memset(decimal, 0, size - strlen(result));
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 (pos-- > 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;
list_add(&node->link, &heads[remainder % size]);
*q++ = (remainder * 10) / d + '0';
remainder = (remainder * 10) % d;
}
strcpy(p, decimal);
return result;
}
```
:::
## 延伸問題 2. 在 Linux 核心原始程式碼的 `mm/` 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
* working
---
# 測驗 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__ 等價。
請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫
M = ?
X = ?
## 作答
* `M` = `_h`
* `X` = `0`
* test my answer
```c
#include <stdio.h>
#include <stddef.h>
//#define ALIGNOF(t) \
// ((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)(&((struct { char c; t _h; } *)0)->c))
#define ALIGNOF(t) \
((char *)(&((struct { char c; t _h; } *)0)->_h) - (char *)0)
int main()
{
printf("char, %ld\n", __alignof__(char));
printf("unsigned char, %ld\n", __alignof__(unsigned char));
printf("int, %ld\n", __alignof__(int));
printf("long, %ld\n", __alignof__(long));
printf("long long, %ld\n", __alignof__(long long));
printf("unsigned ing, %ld\n", __alignof__(unsigned int));
printf("unsigned long, %ld\n", __alignof__(unsigned long));
printf("unsigned long long, %ld\n", __alignof__(unsigned long long));
printf("double, %ld\n", __alignof__(double));
printf("float, %ld\n", __alignof__(float));
printf("---------------\n");
printf("char, %ld\n", ALIGNOF(char));
printf("unsigned char, %ld\n", ALIGNOF(unsigned char));
printf("int, %ld\n", ALIGNOF(int));
printf("long, %ld\n", ALIGNOF(long));
printf("long long, %ld\n", ALIGNOF(long long));
printf("unsigned ing, %ld\n", ALIGNOF(unsigned int));
printf("unsigned long, %ld\n", ALIGNOF(unsigned long));
printf("unsigned long long, %ld\n", ALIGNOF(unsigned long long));
printf("double, %ld\n", ALIGNOF(double));
printf("float, %ld\n", ALIGNOF(float));
return 0;
}
```
* output
```
char, 1
unsigned char, 1
int, 4
long, 8
long long, 8
unsigned ing, 4
unsigned long, 8
unsigned long long, 8
double, 8
float, 4
---------------
char, 1
unsigned char, 1
int, 4
long, 8
long long, 8
unsigned ing, 4
unsigned long, 8
unsigned long long, 8
double, 8
float, 4
```
* 參考資料:
* [Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
* [kevinshieh0225](https://hackmd.io/@Masamaloka/linux2022-quiz2#%E6%B8%AC%E9%A9%97-6%EF%BC%9A__alignof__)
* [6.44 Determining the Alignment of Functions, Types or Variables](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html)
* [offsetof - wikipedia](https://en.wikipedia.org/wiki/Offsetof)
## 延伸問題 1. 解釋上述程式碼運作原理
* `(char *)(&((struct { char c; t _h; } *)0)->_h)`
* 先將 `struct { char c; t _h; }` 型態結構體的位址變更為 0。
* 然後再提取型態為 `t` 的成員 `_h` 的記憶體位址。
* 然後再轉成 `char *` ，也就是由位址 0 到成員 `_h` 的 offset。
* [The (char *) casting in container_of() macro in linux kernel](https://stackoverflow.com/questions/20421910/the-char-casting-in-container-of-macro-in-linux-kernel)
* 同理，`(char *)0` 就是取得位址 0 。
* 兩者相減就是型態 `t` 的 alignment。
* 編譯器處理 `&((TYPE *)0)->MEMBER` 時，不會真正去存取地址為 0 的記憶體區段，只是將 0 看做指標操作的一個運算元。也就是說，編譯器只是把記憶體位址拿來當數字一樣做運算。並不會真的對記憶體位址所表示的記憶體區間做存取的動作。
## 延伸問題 2. 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
* working
## 延伸問題 3. 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
* working
---
# 測驗 7
## 題目
```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;
}
```
## 作答
* `KK1` = `div3`
* `KK2` = `div5`
* `KK3` = `div3 << 2`
* note: 第 17 行應改為
```c=17
strncpy(fmt, &"FizzBuzz%u"[(8 >> div5) >> (KK3)], length);
```
否則，當 i 不為 3、5 或 15 的倍數時，無法印出 i 的值。
:::spoiler 完整程式碼
```c
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.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"[(8 >> div5) >> (div3 << 2)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
:::
## 延伸問題 解釋上述程式運作原理並評估 `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 核心的空間，請充分討論
---
# 答案卷
* [2022 年 Linux 核心設計第 2 週隨堂測驗 (A)](https://docs.google.com/forms/d/e/1FAIpQLSf80zijSR-BFkgmQULgOS2-6m0HhFkJ7XYN85kpeUtzxd0rdg/viewscore?viewscore=AE0zAgDzT6wysm6S4xl0rhDlzL2X9oj48eZNmUq7-egYf88J6ELqWB1Zrid3MRr6SQ)
* [2022 年 Linux 核心設計第 2 週隨堂測驗 (B)](https://docs.google.com/forms/d/e/1FAIpQLScn1eavQ3ecWxw3pfujjm_6ENGDC3uo8Ks3smTfT0dMhaHHBw/viewscore?viewscore=AE0zAgDJguT91rKdx6Unrl9LdaESpf-9Q58JRUFNCcXc0W9xGEh-1z_XXWPZj-gL2w)
Sign in with Wallet
Connect another wallet