---
tags: linux2022, linux
---
# 2022q1 Homework3 (quiz3)
contributed by < `AmyLin0210` >
> [2022q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)
----
## 測驗 1
### 解釋程式碼運作原理
```c
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))
```
首先我們看到 `(~0UL) >> (63 - h)` 的部份，這裡代表將左側非一的位置清零，
在後面 `(~0UL) >> (l) << (l)` 則是將右側非一的位置清零，
兩者再做 **and** 的操作，便可以只留下中間需要為 1 的數字。
下方我以 8 bit 作為示意圖
```
GENMASK(6, 4) 01110000
11111111 >> (7 - 6) --> 01111111
11111111 >> (4) << (4) --> 11110000
------------------------------------
01111111 & 11110000 --> 01110000
```
## 測驗 2
### 解釋程式碼運作原理
```c=
struct foo;
struct fd {
struct foo *foo;
unsigned int flags;
};
enum {
FOO_DEFAULT = 0,
FOO_ACTION,
FOO_UNLOCK,
} FOO_FLAGS;
static inline struct fd to_fd(unsigned long v)
{
return (struct fd){(struct foo *)(v & ~3), v & 3};
}
```
由題目敘述可以得知，我們想要針對 `foo` 這個指標以四個位元組為單位，進行向下對齊。
在一般的想法上，就是直接將該位置除以四，但由於 4 是二的倍數，所以我們可以使用 binary operation 來達成，答案是 `(struct foo *)(v & ~3)`
## 測驗 3
### 解釋程式碼運作原理
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
return x;
}
```
以下是整個流程的示意圖：
每 4 個 bits 為一組，做 reverse
```
x = (x >> 4) | (x << 4)
1 2 3 4 | 5 6 7 8 -> 5 6 7 8 | 1 2 3 4
```
再來由於 0xCC 為 `1100 1100` 若有一個數字與它做 and 操作，並往右位移兩位，那便會有共 4 個位元，以兩個位元為一組，向右位移兩位。
類似的，由於 0x33 為 `0011 0011` ，若有數字與它做 and 操作，並往左位移兩位，那便會有共 4 個位元，以兩個位元為一組，向左位移兩位。
```
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
5 6 | 7 8 | 1 2 | 3 4 -> 7 8 | 5 6 | 3 4 | 1 2
```
最後兩個兩個位元一組左右互換
```
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1)
7 | 8 | 5 | 6 | 3 | 5 | 1 | 2 -> 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1
```
### 測驗 4
首先，我們先來看 `__VA_ARGS__` 到底是什麼。
在 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) 這份文件中，有解釋到他是一個可以被宣告為可變參數的 macro，以下方的程式碼為例
```c=
#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})[++_foreach_i])
int main () {
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
printf("i is %i\n", i);
}
}
```
第 8 行的地方使用了上方定義的 foreach_int 巨集 (macro)，`__VA_ARGS__` 將會是該巨集第二個之後的參數們，若是將它展開，會等同於下方的程式碼：
```c=
for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); \
_foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); \
(i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i]) {
printf("i is %i\n", i);
}
```
- 一步一步的拆解上方程式碼，首先是 `(int[]){0, -1, 100, 0, -99})` ，這代表了一個陣列，裡面的元素分別為 `0, -1, 100, 0, -99` 。
- `((i) = ((int[]){0, -1, 100, 0, -99})[0])` 表示將該陣列第 0 個元素的值賦值給 `i`
- 最後有運用到 [comma operator](https://www.geeksforgeeks.org/comna-in-c-and-c)，也就是假設現在有以下的程式碼：`int i = (exp1, exp2)` ，程式執行時會先執行 exp1 再值執行 exp2 ，並回傳出 exp2 的結果給 `i`。在上面的程式碼，則代表把 `0` 這個數字賦值給 `_foreach_i`。
- 在這個 for 迴圈的中止條件是 `_foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int);`，所以推測 _foreach_i 儲存的資訊是已經遍歷到陣列的哪個位置
- 最後看到 `(i) = ((int[]){0, -1, 100, 0, -99, 0})[++_foreach_i])` ，表示要把 i 更新為新的陣列內位置的值，`++_foreach_i` 是先加一再回傳，因此可以拿到原陣列位置加一後的資料。
在 `foreach_ptr` 裡面的邏輯大致與 `foreach_int` 類似，同樣套用範例將它展開：
```c=
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
const char *p;
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){"Hello", "world"})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){"Hello", "world", \
NULL})[++_foreach_i], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){"Hello", "world"})))
```
我們可以看到在上面第 9 行的程式碼部份，在陣列的最後一個位置塞入 NULL 表示結束。
來看看 `_foreach_no_nullval` 這個巨集內是如何判斷該陣列正確。
- 在裡面的 `(i) >= sizeof(arr) / sizeof(arr[0])` ，由於 `||` 的特性，當 `(exp1 || exp2)` 時，只有在 exp1 為 `false` 的狀況下，才會去執行 `exp2`
- 在這裡的話，`sizeof(arr) / sizeof(arr[0])` 算出的數字為該陣列內有幾個元素，當 i 還小於等於那個元素，我就去檢查 `p` 是否為 `NULL` ，若 `p` 為 `NULL` ，`assert` 內的判斷式為 `false` ，表示我會在 `stderr` 內輸出錯誤訊息並結束程式。
## 測驗 5
```c=
#include <limits.h>
int divide(int dividend, int divisor)
{
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;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
dvd -= dvs << shift;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
同樣一行行的來看程式碼，
- 第 4 到第 15 行，做的事情都是去判斷 `dividend` 和 `divisor` 是否為負數，若是負數，則利用二補數的特性，將它轉為正數，並且在 signal 這個參數儲存他是正數或者負數的資訊。
- 在第 17 到 20 行，由於在二進制的 shift 等同於乘以二的冪次，所以就是找到 dvd 大於 dvs 的多少二的冪次。
- 第 22 到第 27 行，在 `dvd` 仍大於 `dvs` 的狀況下，相減他們，並使用 `res` 來記住已經減了多少，一次就是減 `dvs` 乘以二的冪次，使用 shift 來紀錄是要 shift 多少位。
## 測驗 6
```c=
#include <stdbool.h>
#include "list.h"
struct Point {
int x, y;
};
struct point_node {
int p1, p2;
struct list_head link;
};
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return p1 == pn->p1;
return true;
}
static int gcd(int x, int y)
{
while (y) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}
static int maxPoints(struct Point *points, int pointsSize)
{
if (pointsSize <= 2)
return pointsSize;
int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
int *dup_cnts = malloc(pointsSize * sizeof(int));
int *hori_cnts = malloc(pointsSize * sizeof(int));
int *vert_cnts = malloc(pointsSize * sizeof(int));
int *slope_cnts = malloc(slope_size * sizeof(int));
memset(hori_cnts, 0, pointsSize * sizeof(int));
memset(vert_cnts, 0, pointsSize * sizeof(int));
memset(slope_cnts, 0, slope_size * sizeof(int));
for (i = 0; i < pointsSize; i++)
dup_cnts[i] = 1;
struct list_head *heads = malloc(slope_size * sizeof(*heads));
for (i = 0; i < slope_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (i = 0; i < pointsSize; i++) {
for (j = i + 1; j < pointsSize; j++) {
if (points[i].x == points[j].x)
hori_cnts[i]++, hori_cnts[j]++;
if (points[i].y == points[j].y)
vert_cnts[i]++, vert_cnts[j]++;
if (points[i].x == points[j].x && points[i].y == points[j].y)
dup_cnts[i]++, dup_cnts[j]++;
if (points[i].x != points[j].x && points[i].y != points[j].y) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int tmp = gcd(dx, dy);
dx /= tmp;
dy /= tmp;
int hash = dx * dy - 1333 * (dx + dy);
if (hash < 0)
hash = -hash;
hash %= slope_size;
if (can_insert(&heads[hash], i, j)) {
struct point_node *pn = malloc(sizeof(*pn));
pn->p1 = i;
pn->p2 = j;
list_add(&pn->link, &heads[hash]);
}
}
}
}
for (i = 0; i < slope_size; i++) {
int index = -1;
struct point_node *pn;
list_for_each_entry (pn, &heads[i], link) {
index = pn->p1;
slope_cnts[i]++;
}
if (index >= 0)
slope_cnts[i] += dup_cnts[index];
}
int max_num = 0;
for (i = 0; i < pointsSize; i++) {
if (hori_cnts[i] + 1 > max_num)
max_num = hori_cnts[i] + 1;
if (vert_cnts[i] + 1 > max_num)
max_num = vert_cnts[i] + 1;
}
for (i = 0; i < slope_size; i++) {
if (slope_cnts[i] > max_num)
max_num = slope_cnts[i];
}
return max_num;
}
```
在這份程式碼裡的想法是去分別計算對於一個點來說，與他處在相同 x 軸、y 軸、擁有相同斜率的點有哪些。
- 在第 63 到 79 行的地方，做的事情就是去找到相同斜率的點。
- 由於在電腦中，儲存浮點數很容易會有精度上的的問題，所以選擇算出兩點之間 x 軸與 y 軸之間的距離，再去找到他們的最大公因數，除以最大公因數後，以此紀錄他們的斜率。
- 在第 73 行呼叫了 `can_insert`，這個函式的內容定義在第 13 行，可以看到當中的做的事情是，只去記錄相同斜率狀況下，從同一個點出發的次數以避免重複呼叫。這個想法很類似於數學上的點斜式，也就是給定一個點，給定一個向量，就可以求出一個直線。
- 但是在目前的程式碼中，我發現可能會出現一個狀況，就是有機會非共線但相同斜率的狀態下，有些點會被捨棄掉。因此應該要重新設計演算法，將從哪些位置出發也列入考量。
## 測驗 7
```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 = (v > 0x3U) << 1;
v >>= m;
ret |= m;
ret |= v > 0x1U;
return ret;
}
```
在這裡，基本上是去找到最高位元是哪一個，以上的實作方式的優點是當中沒有 branch，若直觀的使用 for 迴圈去找出最高的位元在哪裡的話，就無可避免地會有 branch 的發生。
- 第 4 行的地方，去看有沒有超過 $2^{2^{4}}$ ，如果有就把結果儲存到 ret 裡，並向右 shift 相對應的位元。
- 第 10 行的地方，同上面的步驟，看看有沒有超過 $2^{2^{3}}$。
- 第 13 與第 16 行皆是相同的邏輯。
## 測驗 8
在本測驗裡，主要是要將程式碼使用指標的指標來簡化。
```c=
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
p = &(*p)->left;
else
p = &(*p)->right;
}
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 = &(*r)->left;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
程式碼的第 4 到第 8 行的部分，是找到想要移除的結點在哪裡，若想移除的節點值較目前節點的小往左走，反之往右走。
在第 14 行，若找到的節點左邊已經沒有節點了，那直接將右邊的整個結構往上挪
假設我現在想要移除的 data 是 10 ，那我只需要把該節點替換為該節點的 right 即可
```
13 13
/ \ / \
10 15 11 15
\ --> \
11 12
\
12
```
在 16 行做的事情與上述的相似，差別只在於若現在是右邊沒有節點了，那我直接把左邊的結構網上挪。
第 18 到第 25 行處理的狀況為，若左右都有節點，那我先找到該節點右邊子樹中最小的 (也就是子樹中最左邊的 leaf)，將他的值替換至想要被取代的節點。
第 24 行做的事情就是將該子樹最左邊的 leaf 的右子樹往上挪，以下圖範例來看，就是將 `16` 挪至原本 `15` 的位置
假設我們現在想要取代的的數字是 13
```
13 15
/ \ / \
10 18 10 18
/ --> /
15 16
\ \
16 17
\
17
```
## 測驗 9
```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))
```
首先我們可以看到以上的程式碼，和測驗 2 有些相似之處。
首先看到 `NNN` 的部分，因為我們會希望可以對齊 16，所以會想要把最後面的 4 個位元做 mask 處理掉，因此在這邊會是 `MAX_ALIGNMENT - 1` ，也就等同於 `0xFU`。
再來是 `MMM` 的部分。在題目裡，會希望可以做到向上對齊，但是如果直接將最後的四個位元給歸零，做的事情是向下對齊。因此我們可以將他們加上一個數字，向上位移至上一個位元組，再向下對齊。
在這裡的 `MMM` 是 `1` ，我們討論一下邊界的狀況，當原先的位置最後 4 個位元就是 0 時，對齊結果應該要是和原先相同的。在這裡要將 `x` 加上 `MAX_ALIGNMENT` 後再扣掉一就是考量這個原因。
## 測驗 10
```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)); \
})
```
在這裡我參考了 [NOVBobLee](https://hackmd.io/@at0mCe11/linux2022-quiz3#%E6%B8%AC%E9%A9%97-10) 同學的筆記，當中有對於在不同型態下，進行除法運算時的不同結果。
除了在不同型態下的除法運算邏輯外，主要應用到的邏輯與測驗 9 的向上位移相似，所以 RRR 是 `__x + ((__d) >> 1)`
而 SSS 處理的為 x 是負數的狀況，因此是加減正好顛倒， `__x - ((__d) >> 1)`
## 測驗 11
Sign in with Wallet
Connect another wallet