---
tags: linux kernel, linux2022
---
# 2022q1 Homework3 (quiz3)
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗 `1`
### 程式碼運作原理
#### 功能
產生連續的 bitmask
- `GENMASK(6, 4)` 產生 01110000~2~
- `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)
#### GENMASK 巨集定義
首先，我們可以看到巨集內有兩個 `~0UL` (0xFFFFFFFFFFFFFFFF) 先做 shift 操作，接著做 AND
因此，可以推測其作法是將
* `~0UL` 右移產生高位 `63 - h` bits 為 0 的 `unsigned long`
* `~0UL` 左移產生低位 `l` bits 為 0 的 `unsigned long`
所以 `LEFT = 63 -h` 用以產生高位 `63 - h` bits 個 0 ，而 `RIGHT = l` 用以產生低位 `l` bits 個 0
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
## 測驗 `2`
### 程式碼運作原理
#### 功能
將 `fd`結構體的第一個成員的地址對 4 個位元組進行向下對齊。
```graphviz
digraph G {
rankdir = LR;
splines = false;
node[shape = "record"]
address[label ="<h>Memory address|<a1>0x0|<a2>0x1|<a3>0x2|<a4>0x3|<a1>0x4|<a2>0x5|<a3>0x6|<a4>0x7",width = 1.8]
space_before[label ="<h>Memory space before||<d1>data|<d2>data|<d3>data|<d4>data|||",width = 2.5]
space_after[label ="<h>Memory space after|<d1>data|<d2>data|<d3>data|<d4>data||||",width = 2.5]
address->space_before->space_after[weight = 10, style = invis]
space_before->space_after
}
```
> 圖片參考 [jim12312321](https://hackmd.io/NJrI-98tT4i0B_Ri-BMXsw?view#%E6%B8%AC%E9%A9%97-2-%EF%BC%9A-%E8%A8%98%E6%86%B6%E9%AB%94%E5%90%91%E4%B8%8B%E5%B0%8D%E9%BD%8A)
#### 記憶體向下對齊實作
首先，從結構體 `fd` 包含 `struct foo *foo` 以及 `unsigned int flags`。
接著可以根據 `fd` 推測 `EXP1` 應該包含 `struct foo *`。
```c
struct foo;
struct fd {
struct foo *foo;
unsigned int flags;
};
```
因為要作 4 `bytes` 的的向對齊，低位 2 `bits` clear，所以用 bitmask 的方式讓 `v` 與 `~3` 作 AND。
因此 `EXP1 = (struct foo *)(v & ~3)`
```c
enum {
FOO_DEFAULT = 0,
FOO_ACTION,
FOO_UNLOCK,
} FOO_FLAGS;
static inline struct fd to_fd(unsigned long v)
{
return (struct fd){EXP1, v & 3};
}
```
## 測驗 `3`
> Leetcode [190. Reverse Bits](https://leetcode.com/problems/reverse-bits/)
### 程式碼運作原理
#### 功能
輸入的 8 位元無號整數逐一位元反轉。
- Input = 00100101
- Output = 11011010
#### 實作
利用 AND 與 Shift 達到高位移到低位；低位移到高位，接著將兩者用 OR 合併。
1. 將高位 4 `bits` 與低位 4 `bits` 交換
2. 將高、低位 4 `bits` 內的高位 2 `bits` 與低位 2 `bits` 交換
3. 將高、低位 2 `bits` 內的高位 1 `bits` 與低位 1 `bits` 交換
`EXP2`、`EXP3` 為負責處理低位 4 `bits` 的部份，所以
* `EXP2 = (x & 0x33) << 2`
* `EXP3 = (x & 0x55) << 1`
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | (EXP2);
x = ((x & 0xAA) >> 1) | (EXP3);
return x;
}
```
## 測驗 `4`
### 程式碼運作原理
#### foreach 巨集
遍歷集合中每個成員。
```c
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
printf("i is %i\n", i);
}
const char *p;
foreach_ptr(p, "Hello", "world") {
printf("p is %s\n", p);
}
```
預期輸出：
```
i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world
```
foreach 與 for 不相同的地方是 foreach 通常不維護明確的計數器
#### 擴充 foreach 巨集定義
foreach 的巨集定義為 for 迴圈的實做，因此 `EXP4`, `EXP5` 的部份應該是更新 `_foreach_i` (index)。
由於每次迴圈都要對 `i` 賦值，因此要先更新 `foreach_i` 接著再對 `i` 賦值，所以：
* `EXP4 = ++_foreach_i`
* `EXP5 = ++_foreach_i`
```c
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
#define foreach_int(i, ...) \
for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
## 測驗 `5`
> LeetCode [29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)
### 程式碼運作原理
#### 規則
輸入兩正整數，將兩數相除，並將成果無條件捨去。
#### 沒有除法的實做
先處理兩數處法的 sign bit， 用 `signal` 紀錄 sign bit，若 `dividend < 0` 則對 `dvd` 作二的補數，接著若 `divisor < 0` 則對 `dvs` 作二的補數。sign bit 用 `signal *= -1` 來處理，若只有一者為負，則 `signal = -1`，若兩者皆為負或皆不為負，則 `signal = 0`。
```c
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
```
`shift` 負責將 `dvs` 的最高位元對齊 `dvd` 的最高位元。
所以 `EXP6 = dvs << shift`
```c
int shift = 0;
while (dvd > (EXP6))
shift++;
```
`res` 負紀錄商，而 `EXP7` = `dvd -= dvs << shift` 將被除數減去除數。
```c
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
```
先判斷 `res` 是否 overflow，最後將 `res` 乘上 `signal` 即為兩數相除的商。
```c
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
```
## 測驗 `6`
> LeetCode [149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)
### 程式碼運作原理
#### 規則
## 測驗 `7`
### 程式碼運作原理
#### 功能
針對給定的 32 位元無號數，計算扣除開頭的 0，最少需要多少位元才可儲存
#### 實作
利用 Binary Search 的方式，判斷最高位的 1 的位子。
比教最高位的 1 是否在前半部，若在前半部，將後半部 shift 掉。
可知 `EXP10` = `(v > 3) << 1`
而 `EXP11` 只有一行，負責處理最後兩個 bits。
所以 `EXP11` = `ret += v > 1`
```c
int ilog32(uint32_t v)
{
int ret = v > 0;
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;
m = (v > 0xFU) << 2;
v >>= m;
ret |= m;
m = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
## 測驗 `8`
### 程式碼運作原理
#### 用 indirect pointer 改寫 `remove_data`
在第一個 while loop 的地方，他是負責 binary search 部份，因此 `EXP12` 與 `EXP13` 應該是根據判斷 `d` 與 `(*p)->data` 的大小進行向下搜尋。
因此：
* `EXP12` = `p = &(*p)->left`
* `EXP13` = `p = &(*p)->right`
```c
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
## 測驗 `9`
### 程式碼運作原理
#### 記憶體地址對齊 (alignment) 的巨集
先對地址加上對齊大小（16），因此 `MMM` = `16`
接著捨去最低 4 位元，因此應該要與最低 4 位元皆為 0 其餘皆為 1 的數進行 AND 運算，所以 `NNN` 為 `MAX_ALIGNMENT - 1`。
```c
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
## 測驗 `10`
### 程式碼運作原理
#### 功能
處理二個表示式進行整數除法操作時，最接近的整數值。
參考執行成果：
* `DIVIDE_ROUND_CLOSEST(7, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(6, 3) = 2`
* `DIVIDE_ROUND_CLOSEST(5, 3) = 2`
#### 巨集實作
$round(a/b) = (a+b/2)/b$
分為兩種情況：
1. `x` 或 `divisor` 為 unsigned 或同號
- `RRR` = `(__x)+(__d)>>1`
2. `x` 與 `divisor` 為異號
- `SSS` = `-(__x)+(__d)>>1`
```c
#define DIVIDE_ROUND_CLOSEST(x, divisor) \
({ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
(((__x) > 0) == ((__d) > 0))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
## 測驗 `11`
### 程式碼運作原理
#### 不用除法的開平方根實作
返回 `word` 的最高有效位元的位置。
```c
static inline unsigned long fls(unsigned long word)
{
int num = 64 - 1;
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
if (!(word & (~0ul << (64 - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (64 - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (64 - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (64 - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (64 - 1))))
num -= 1;
return num;
}
```
```c
m = 1UL << (fls(x) & ~1UL);
```
```c
while (m) {
b = y + m;
XXX;
if (x >= b) {
YYY;
y += m;
}
ZZZ;
}
```
Sign in with Wallet
Connect another wallet