# 2022q1 第 3 週測驗題
contributed by < `rickywu0421` >
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗 `1`
### 題目
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`，其作用是依據給定的範圍，產生連續的 [bitmask](https://en.wikipedia.org/wiki/Mask_(computing))，例如:
- `GENMASK(6, 4)` 產生 011100002$_2$
- `GENMASK(39, 21)` 產生 0x000000ffffe00000$_2$ (64 位元)
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
### 解題
我們以 `GENMASK(6, 4)` 為例, 其可以由以下 bitwise and 操作生成：
```c
01111111 (A)
& 11110000 (B)
-------------
01110000
```
其想法就是：生成一個 bitmask A, 其在 bit 6 以下都是 1, 其他為 0; 再生成一個 bitmask B, 其在 bit 4 以上都是 1, 其他為 0。最後將 `A & B` 即可圍出想要的 bitmask。
故 `LEFT = 63 - h`, `RIGHT = l`。
## 測驗 `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){EXP1, v & 3};
}
```
函式 fo_fd 接受指定的地址 v，填入一個 fd 結構體，並確保第一個成員的地址得以依據〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 align_down)。其中 `struct foo` 運用〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧，可在實作階段才提供具體 `struct foo` 的定義。
## 解題
`(struct fd){EXP1, v & 3}` 用到 [compound literal](https://gcc.gnu.org/onlinedocs/gcc/Compound-Literals.html) 的技巧, 其可作為 lvalue (因為其作為一個 object)。
若要判斷一個 bit stream 是否對 4 個位元組對齊, 則最後兩個 bit 必須都被 clear。因此向下對齊 4 個位元組也就是把 bit stream 的最後兩個 bit clear 掉。舉例來說, `0b11001001` 沒有對 4 個位元組對齊, 我們可以透過以下操作達成向下對齊：
```c
11001001 (original)
& 11111100 (bit mask)
-----------------
11001000
```
而 `0b11111100` 也就是 `0b00000011(0x3)` 做位元反轉得到的結果。
故 `EXP1 = (struct foo *)(v & ~3)`。
另外, 我們也可以看出, `flag` 為 `v & 3` 的目的為儲存原本的第一個元素相對向下對齊的位址的偏移量, 故 `(char *)fd.foo + fd.flags` 可以存取到原本的第一個元素。
## 測驗 `3`
### 題目
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```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;
}
```
### 解題
反轉 8 位元無號整數的方法就是不斷的將隔板的左右反轉並逐漸縮小範圍, 需要反轉的次數為 $log_28 = 3$, 如以下舉例 (以 `0b11010100` 為例)
1. 第一次反轉, 隔板間隔為 `4` 個 bit：
```c
1101|0100
0100|1101
```
此操作對應得程式碼片段如下：
```c
x = (x >> 4) | (x << 4);
```
2. 第二次反轉, 隔板間隔為 `2` 個 bit：
```c
01|00 11|01
00|01 01|11
```
此操作對應得程式碼片段如下：
```c
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
```
故 `EXP2 = (x & 0x33) << 2`。
3. 第三次反轉, 隔板間隔為 `1` 個 bit:
```c
0|0 0|1 0|1 1|1
0|0 1|0 1|0 1|1
```
此操作對應得程式碼片段如下：
```c
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
```
故 `EXP3 = (x & 0x55) << 1`。
## 測驗 `4`
### 題目
延伸〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉，我們嘗試將 [foreach 巨集](https://en.wikipedia.org/wiki/Foreach_loop) 予以擴充，使得支援以下寫法:
```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);
}
```
預期輸出如下:
```c
i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world
```
對應的巨集定義:
```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__})))
```
### 解題
#### foreach_int
for loop 可分為：
#### 1. 起始條件
```c
unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)
```
將 `i` 賦值為陣列索引值 `0` 的元素, 並將 `_foreach_i` 賦值為 `0`。
#### 2. 測試條件
```c
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)
```
判斷索引值 `_foreach_i` 是否小於陣列的元素個數。
#### 3. 更新條件
```c
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
```
將 `i` 更新為下一個陣列的元素。故 `EXP4 = ++_foreach_i`。
#### foreach_int
#### 1. 起始條件
```c
unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)
```
將 `i` 賦值為陣列索引值 `0` 的元素, 並將 `_foreach_i` 賦值為 `0`。
#### 2. 測試條件
```c
(i)
```
判斷 `i` 是否不為 `NULL`。
#### 3. 更新條件
```c
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
將 `i` 更新為下一個陣列的元素。故 `EXP5 = ++_foreach_i`。並透過 `_foreach_no_nullval` 巨集確認 `i` 是否為 NULL：
#### _foreach_no_nullval
```c
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
```
這是為了檢查當 `_foreach_i < (陣列元素個數)`時 `p` 是否不等於 `NULL`。
Sign in with Wallet
Connect another wallet