---
tags: linux, kernel
---
# 2022q1 Homework2 (quiz2)
contributed by < `Destiny0504` >
> [題目連結](https://hackmd.io/@sysprog/linux2022-quiz2)
## 測驗一
``` c
uint32_t average(uint32_t a, uint32_t b)
{
// 判斷 a 和 b 都是奇數的情況下，才加一
return (a >> 1) + (b >> 1) + (a & b & 1);
}
```
用 a & b 來實現 a - b 的操作，
``` c
uint32_t average(uint32_t a, uint32_t b)
{
return (a & b) + ((a | b) >> 1);
}
```
### 兩種實作方式的組合語言比較
- 第一種實作方式的 x86 組合語言版本
```objectivec
average(unsigned int, unsigned int):
// 將 edi 的值複製到 eax
mov eax, edi
// 將 esi 的值複製到 edx
mov edx, esi
// edi = edi & esi
and edi, esi
// eax = edi >> 1
shr eax
// edx = esi >> 1
shr edx
// edi = edi & exi & 1
and edi, 1
// eax = (esi >> 1) + (edi >> 1)
add eax, edx
// eax = (esi >> 1) + (edi >> 1) + (edi & exi & 1)
add eax, edi
ret
```
- 第二種實作方式的 x86 組合語言版本
```objectivec
average(unsigned int, unsigned int):
// 將 edi 的值複製到 eax
mov eax, edi
// edi = edi & esi
and edi, esi
// eax = edi | esi
or eax, esi
// eax = (edi | esi) >> 1
shr eax
// eax = ((edi | esi) >> 1) + (edi & esi)
add eax, edi
ret
```
||第一種實作方式|第二種實作方式|
|-|-|-|
|register 使用數量|4|3|
|add指令數|2|1|
|and指令數|2|1|
|mov指令數|2|1|
|shr指令數|2|1|
|or指令數|0|1|
### 結論
第一種實作方式需要用到 a 、b 個別的值，所以需要花費額外的 register 將它存起來，所以在實作的要盡量避免這種所有要加起來的值都有關係的情況。
### Exponentially weighted moving average ( EWMA )
#### 優點
- 只要紀錄上一次的值就可以得到下一項應該是多少，能減少使用的記憶體空間。
- 可以動態的計算結果，不需要一次就看完所有的資料。
#### 在 linux kernel 中的實作
- linux kernel 中是以一個 pointer 指向一個 unsigned long 的變數，而這個變數就是用來儲存過去計算過得結果的。
- 考慮以下實作的方法，internal 先乘以 2 的 weight_rcp 次方減去原本的 internal，相當於 $\text{internal}\times\frac{1}{2^{weight\_rcp}}$，在加上新的 val 。
- e.g. 如果 weight_rcp = 8 ，相當於每次把過去運算的結果乘以 $\frac{7}{8}$，再加上新的 val 乘以 $\frac{1}{8}$ 。
``` c
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision));
```
## 測驗二
由 a <= b 來判斷我們應該回傳 a 還是 b
- 當 a > b 的時候 -(a <= b) 會得到零，所以可以直接無視 (b ^ a) 會得到的值，而零跟 a 做 XOR 則會得到 a ，所以回傳值為 a
- 當 a > b 的時候-(a <= b) 會得到 1 ，所以可以直接視為回傳的值為 a ^ (b ^ a)，而 a 跟 b ^ a 做 XOR 則會得到 b ，最後得到的回傳值為 b
``` c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((b ^ a) & -(a <= b));
}
```
- 正確答案是給 a ^ b 和 a < b, 但我想我的實作也可以達到同樣的效果。
### Branch-free 版本
利用 a < b 時，a - b 會 overflow 的特性，所以只要判斷是否有 overflow 的情況即可。
- 因為 a 和 b 都是 unsigned int，所以不能只由最高位來判斷是否出現 overflow，還要接著判斷 a 的最高位是否大於 $2^{31} - 1$，如果兩者皆符合，才能判斷為遇到 overflow
``` c
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((b ^ a) & (-((a - b) >> 31) ^ -(a >> 31)));
}
```
## 測驗三
以下程式碼的運作原理為 Euclidean algorithm ，差別只在於每一步找都先把 v 換成奇數而已。而之所以可以只留下奇數的部份，是因為我們前面已經把 u 跟 v 所擁有的 2 的倍數的公因數都去除掉了。( 可以參考 reference 提到的演算法 ）
``` c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
// 如果 u 跟 v 其中一個是 0，直接回傳不為 0 的那一個
if (!u || !v) return u | v;
int shift;
// 用來找出 u 跟 v 公因數有 2 的幾次方
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 (v);
// 最後回傳的時候要把前面除去的 2 的次方的公因數乘回來
return u << shift;
}
}
```
### 用 ```__builtin_ctz``` 改寫 GCD 的版本
``` c
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift = min(__builtin_ctz(u) , __builtin_ctz(v));
u >>= shift, v >>= shift;
u >>= __builtin_ctz(u);
do {
v >>= __builtin_ctz(v);
if (u < v) {
v -= u;
printf("%ld %ld\n",u, v);
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
### Reference
[GCD 演算法](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-3)
## 測驗四
- 因為 2 complement 的編碼特性，所以一個數字 ```a``` 在跟 ```-a``` 取 bitwise and 會剛好找出目前最低位元的 1 。
- e.g. a = 12 轉換為二進位 = ```01100``` , -a 轉換為二進位 = ```10100```，取 bitwise and 之後剛好等於 ```00100```
``` 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 = bitset & -bitset;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
## 測驗五
``` 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 (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;
}
```
## 測驗六
- 我們在測驗中所作的版本能夠直接回傳 _h 的 datatype 在 memory 中所佔有的 byte 數量。
- 運作的方式是先拿到 _h 的記憶體位置，減去 char 的 pointer 的位置。
- 作法有點類似 container_of，差別在於一個是加上 offset 得到指向某一個變數的 pointer，而 alignof 是算出 offset
- 注意：這邊 char c 要擺在 t _h 前面，否則無法算出 t 的記憶體大小。（ 因為 struct 為連續的記憶體區塊的關係 ）
``` 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)->_h) - (char *)0)
```
### align function 說明
- ALIGN(x, a) 要拿 x 以 a 作為對齊的基準進行向上對齊
- e.g. a = 128, x = 12 會回傳 128
- 注意：這個 function 只有 a 為 2 的整數次方算出來的對齊結果才是對的。因為這個 function 通常是用來計算記憶體的位置的，所以只有在上述的情況下算出來的結果才是對的也沒問題。
``` c
#define ALIGN(x, a) __ALIGN_KERNEL((x), (a))
```
- ALIGN_DOWN(x, a) 要拿 x 以 a 作為對齊的基準進行向下對齊
- e.g. a = 128, x = 12 會回傳 0
- 注意：這個 function 跟 ALIGN(x, a) 的使用條件一樣
``` c
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
```
### Reference
[linux 實作的 align](https://github.com/torvalds/linux/blob/master/include/linux/align.h)
[linux 實作的 align_kernel](https://github.com/torvalds/linux/blob/master/tools/firmware/ihex2fw.c)
``` c
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
```
## 測驗七
因為在 compile 的時候 M3 、M5 都已經被計算好，而且乘法的運算速度又比除法快，所以會比[另一種](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-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 << div3) << div5;
char fmt[9];
strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (div3 << 2)], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
}
return 0;
}
```
### 兩種方法的時間比較
- 用 linux 的 time 指令進行測量，且迴圈執行 ```100000``` 次
- 方法一為題目中的 [naive.c](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-7) ，方法二為上面的程式碼
- 從下方的結果來看，方法二確實有更好的 performance
||方法一|方法二|
|-|-|-|
|實驗一|0.438|0.330|
|實驗二|0.442|0.445|
|實驗三|0.478|0.447|
|實驗四|0.427|0.464|
|實驗五|0.457|0.478|
|實驗六|0.494|0.451|
|實驗七|0.518|0.303|
|實驗八|0.480|0.375|
|實驗九|0.394|0.447|
|實驗十|0.586|0.269|
|average|0.4714|0.4009|
|max|0.586|0.478|
|min|0.394|0.269|
Sign in with Wallet
Connect another wallet