---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `eric88525` >
> [第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)
# Q1
```c
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))) // (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
1. 從最低位元到 `l` 位元需要為 0，可判斷 shift left 應該為 `l` 次，先 shift right
2. ～0UL 為 0XFFFFFFFFFFFFFFFF 且是無號數，右移 63-h 位元可讓 h 到最高位元為0
3. 做 and 運算可留下左右方的 0 ， 並保留共通的 1
+ 仔細思考後認為 `(~0UL) >> (l) << (l))` 可以寫成 `(~0UL) << (l)` ，原因是 `(~0UL) >> (l) << (l))` 後，結果為最低位元到 `l` 為 0 其餘為 1，跟`(~0UL) << (l))` 的結果一樣的
# Q2
```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}; // return (struct fd){EXP1, v & 3};
}
```
+ 向下對齊 4 bytes 規律：
+ 0～3 對齊到0
+ 4～7 對齊到4
+ 8～11 對齊到 8
+ 可以觀察到只要把最後兩個位元設成0即可對齊，因此要 `&~3` 並轉形成struct 定義的型態
# Q3
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); // x = ((x & 0xCC) >> 2) | (EXP2);
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); // x = ((x & 0xAA) >> 1) | (EXP3);
return x;
}
```
```
abcd efgh
// x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
efgh abcd
// ((x & 0xCC) >> 2) | ((x & 0x33) << 2)
ghef cdab
// x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1)
hgfe dcba
```
+ 透過 & mask 來讓特定位元交換
# Q4
```c
#include <stdio.h>
#include <stdarg.h>
#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})[++_foreach_i])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[++_foreach_i], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
int main()
{
int i;
char *p;
foreach_int(i, 0, -1, 100, 0, -99)
printf("i is %i\n", i);
foreach_ptr(p, "Hello", "world")
printf("p is %s\n", p);
return 0;
}
```
+ `__VA_ARGS__` 用於將 macro 中的 `...` 展開
+ 在 for 迴圈中：
+ 用於遍歷的變數為 `_foreach_i` ， 因此要在每次迴圈結束都+1，也就是 `++_foreach_i`
+ `_foreach_i` 上限為 `sizeof((int[]){__VA_ARGS__}) / sizeof(int);` ，求得整個 int 陣列的元素數量
+ 編譯時在預處理停止，可以看到 macro 會有以下展開，在宣告 `_foreach_i` 時很巧妙的透過 () 和 ＝ 的特性，先讓 i 等於陣列的第 0 元素，接著把 0 指派給 _foreach_i
```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);
```
# Q5
```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;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
# Q6
# Q7
```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 > 0x3) << 1;
v >>= m;
ret |= m;
ret += v > 1;
return ret;
}
```
32 bit 為 0x0000 0000 ~ 0xFFFF FFFF , 0~31 bit
+ binary search 的概念，每次都先檢查 v 是否大於$n/2$的位元數，確認是否在0~n-1 或是 n~最高位元。 n 初始為32，每當檢查完一輪 ， n 都會除以2
+ line `4-6` `7-9` `10-12` `13-15` 是做相同的事情，先檢查 v 所含位元，是否大於 v 可能有的最高位元數的一半，舉例：
+ 第4行先檢查 v 有無大於 32bits 的一半，也就是 0xffff ，第7行檢查 v 有無大於 16bits 的一半，也就是 0xff
+ 每次檢查完如果有大於一半的位元數，用 ret 來紀錄至少含有的位元數:
+ line 4 `v > 0xFFFF` 可確定最高位元至少會大於 1<<4 bit，也就是 16 bit，用 ret 紀錄下來
# Q8
```c=
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
p = &(*p)->left; // EXP12;
else
p = &(*p)->right; // 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 = &(*r)->left; // r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
+ 根據二元樹的規則，節點右側會大於當前節點，左邊則是小於。因此在 `line:5` 比較完數值後，要選擇往右或是往左走
+ EXP14 為讓 **r 在 d 節點右邊 subtree 中，往走找到最小值
+ 假設 d 為15，15 右邊 subtree 的最小數值為18
```graphviz
digraph{
10->5;
10->15;
15->14;
15->20;
20->18;
20->33;
15[color=blue];
18[color=red];
}
```
+ 把目標替換成 subtree 的最小數值
```graphviz
digraph{
10->5;
10->18;
18->14;
18->20;
20->33;
18[color=red]
}
```
# Q9
```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 - 1u) & ~(MAX_ALIGNMENT - 1u))
```
+ 題目要求為 roundup
+ ROUND_UP_TO_ALIGNMENT_SIZE(1~16) = 16
+ ROUND_UP_TO_ALIGNMENT_SIZE(17~32) = 32
+ ROUND_UP_TO_ALIGNMENT_SIZE(33~48) = 48
MAX_ALIGNMENT 的二進位為 `0x10000` ，減一後 `0x1111`，可以把不足16的部分強制進位
進位後需要保留 `0x10000` 以後的資訊，因此要 `& ~(MAX_ALIGNMENT - 1u)` ，讓0~3bit 為0，4bit 以上保留
```
0x0000100
+ 0x0001111
-----------
0x0010011
& 0x1110000
-------------
0x0010000
```
# Q10
```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))) \
? (((__x) + ((__d) >> 1)) / (__d)) \
: (((__x) - ((__d) >> 1)) / (__d)); \
})
```
+ line 3-4:
+ 先用暫存變數存 x 數值，避免在後續展開時被更動，例如輸入 x++，在後續每次被使用時數值都會變動
+ line 5: 檢查 signed 或是 unsigned，如果 unsigned 條件會為 true
+ signed int -1 = -1
+ unsigned int -1 = 4294967295
+ line 6:
+ 判斷正負號是否相同
+ line 7-8: 這段可視為 (__x / __d) +- 0.5
+ 如果 x / divisor 為負，-0.5 來達到四捨五入
+ 如果 x / divisor 為正，+0.5 來達到四捨五入
Sign in with Wallet
Connect another wallet