---
tags: linux2022
---
# 2022q1 Homework2 (quiz2)
contributed by < `KatherineHuangg` >
* [作業要求](https://hackmd.io/@sysprog/BybKYf5xc)
## **測驗一 :**
### 題目:
考慮以下對二個無號整數取平均值的程式碼:
```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);
}
```
我們再次改寫為以下等價的實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
:::info
延伸問題:
- [x] 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)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
### 1. 解釋上述程式碼運作的原理：
#### EXP1:
* 看到 (a >> 1) 以及 (b >> 1) 可以想到都是把 a 和 b 除以2，但會無條件捨去掉最後一個 bit ，因此知道 `EXP1` 就是彌補了 a、b 無條件捨去相加後 與 (a + b) / 2 的差異。
* 而我們可以知道，若 a 、b 的第 0 個 bit 都是 1 則 `EXP1` 為 1 ；若其中一個為 0 或兩者皆為 0 則 `EXP1` 為 0 。根據這些條件我們可以知道 `EXP1` 為 **`a & b & 1`**
#### EXP2 、EXP3:
* 根據下圖的半加器可以得知 `a + b = ((a & b) << 1) + a ^ b` ，而又題目的要求為 (a + b) / 2 (不考慮 overflow 的情況下)，因此可以得知只要將 `((a & b) << 1) + a ^ b` bitwise 右移一位即為答案，因此 `EXP2 = a & b` ，`EXP3 = a ^ b`
#### 總結：
* EXP1 = a & b & 1
* EXP2 = a & b
* EXP3 = a ^ b
---
## **測驗二 :**
### 題目:
改寫[〈解讀計算機編碼〉](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 這三個運算子。
`EXP5` 為 `a` 和 `b` 的比較操作，亦即 logical operator，限定用 `>`, `<`, `==`, `>=`, `<=`, `!=` 這 6 個運算子。
:::info
延伸問題:
- [x] 1. 解釋上述程式碼運作的原理
- [ ] 2. 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
- [ ] 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 檢索。
:::
### 1. 解釋上述程式碼運作的原理：
#### EXP4 、 EXP5:
* 本題是要取兩數中較大的值，因此根據題目現有的程式碼可以知道： 若 a 較大則回傳結果會類似於 `a ^ 0` ； 若 b 較大則回傳結果會類似於 `a ^ (a ^ b)` ，因此可以知道:
1. 若 a >= b ，`((EXP4) & -(EXP5)) = 0`
2. 若 a < b ，`((EXP4) & -(EXP5)) = a ^ b`
* 根據上述，可以猜測出 `EXP4 = a ^ b` ，而 `-(EXP5)` 的結果為：
1. 若 a >= b ，`((a ^ b) & -(EXP5)) = 0` ，所以 `-(EXP5) = 0` ，`EXP5 = 0`
2. 若 a < b ，`((a ^ b) & -(EXP5)) = a ^ b` ，所以 `-(EXP5) = 0xFFFFFFFF = -1` ，`EXP5 = 1`
* 因此 `EXP5 = a < b`
#### 總結：
* EXP4 = a ^ b
* EXP5 = a < b
---
## **測驗三 :**
### 題目:
考慮以下 64 位元 GCD (greatest common divisor, 最大公因數) 求值函式:
#### 原始程式碼:
```c=1
#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 演算法
#### 後來的程式碼:
改寫為以下等價實作:
```c=1
#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;
}
```
:::info
延伸問題:
- [x] 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)，請解釋其實作手法和探討在核心內的應用場景。
:::
### 1. 解釋上述程式碼運作的原理：
#### COND 、 RET:
* 上述的**原始程式碼**是透過輾轉相除法來找到最大公因數，而根據[維基百科](https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)中所描述:
> 輾轉相除法基於如下原理：兩個整數的最大公因數等於其中較小的數和兩數相除餘數的最大公因數。
例如，252 和 105 的最大公因數是 21（252 = 21 * 12, 105 = 21 * 5）
因為 252 − 105 = 21 × (12 − 5) = 147 ，所以 147 和 105 的最大公因數也是 21。
在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數為零。
這時，所剩下的還沒有變成零的數就是兩數的最大公因數。
因此我們可以開始分析:
**`第 4 行:`** 若 u 或 v 其中一個為 0 ，則回傳另一個數；若兩者皆 0 ，則回傳 0。
**`第 5 ~ 9 行:`** 利用 while loop 實作輾轉相除法，透過除數和餘數的交替，每次都將較大的數存成 u 。因此當 v = 0 時，代表前一個數 u 是最大公因數，最後再做回傳。
* 而在後來改寫的程式碼中:
**`第 4 行`:** 一樣是判斷是否為 0 ，
**`第 6 ~ 8 行`:** 判斷 u 和 v 是否皆為 2 的倍數，若是則將 u 和 v都除以 2 ，並將 shift + 1。
**`第 9 ~ 21 行`:** 而後的程式碼則是改進了輾轉相除法，由於已經在 for loop 確保兩者之間已經沒有 2 的公因數了，因此為了更快速的找到剩下的公因數，在進行輾轉相除法的同時把 2 除掉。 在`第 14 ~ 20 行` 的 if - else 是為了確保 v 是較小的數而後進行輾轉相除。
* 因此同理，當 `v = 0` 時，代表前一個數 u 是最大公因數，離開 do - while。
* 而又因為在`第 6 ~ 8 行` 有紀錄兩數之間的 2 次方公因數，因此最後 return 的值是 `u << shift`
#### 總結：
* COND = v
* RET = u << shift
----
## **測驗四 :**
### 題目:
在影像處理中，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=1
#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 ，那 `t` 就會變成 000001 ，接著就可以透過 XOR 把該位的 `1` 清掉，其他保留 (此為 XOR 的特性)。
若 bitmap 越鬆散 (即 `1` 越少)，於是 `improved` 的效益就更高。
:::info
延伸問題:
- [x] 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 的案例;
:::
### 1. 解釋上述程式碼運作的原理：
#### EXP6:
* 由於題目有說到需考慮到 `-bitwise` 的特性，因此推測答案可能會跟 `-bitset` 有關。
* 以 `bitset = 00001100` 為例， `-bitset = 11110100` ，又 `t` 只保留最低位元的 `1`，因此 `t = 00000100` 。根據上述可以推測出 `EXP6 = bitset & -bitset`
#### 總結：
* EXP6 = bitset & -bitset
---
## **測驗五 :**
### 題目:
以下是 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;
}
```
:::info
延伸問題:
- [ ] 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 操作的程式碼案例，予以探討和解說其應用場景
:::
### 1. 解釋上述程式碼運作的原理：
#### EXP6:
Sign in with Wallet
Connect another wallet