---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `Chao-Shun-Cheng` >
## 測驗 `1`
### 程式碼解釋
```c=1
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
首先可以觀察到 `~0UL` 是 `0xffffffffffffffff`，另外左半邊只有邏輯右移，因此可以推斷左半邊就是製造出高位的 `bitmask`。舉例來說，假如 `h` 是 60，那就代表高位的 `bitmask` 會是 `0x0fffffffffffffff`，因此可以推測出 `LEFT` 就是 `63 - h`。再來右邊就是要製造出低位的 `bitmask`，假如說 `l` 是 5，那 `bitmask` 就是 `0xfffffffffffffff0`，因此可以推測出 `RIGHT` 就是 `l`。
::: warning
我認為右移 `l` 是多餘的，不影響結果
:::
## 測驗 `2`
### 程式碼解釋
```c=1
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};
}
```
:::info
參考 `jim12312321` 同學對於 data alignment 的解說以及[Stackoverflow](https://stackoverflow.com/questions/19190502/how-do-i-check-a-memory-address-is-32-bit-aligned-in-c) 的解說。其中有一個關鍵的地方 : ***Sequential addresses refer to sequential bytes in memory.***
還沒看到這句的時候實在不懂 `jim12312321` 同學的意思，直到看到這個才豁然開朗。
:::
主要就是要將最後兩個 bits 設為 0 ，另外可以觀察到 `EXP1` 要傳入的型態是 `struct foo *`，因此可以推測會用到型態轉換。因此可以得知 `EXP1` 就是 `(struct foo *)(v & ~3)`。
## 測驗 `3`
### 程式碼解釋
```c=1
#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 行，會把前 4 個與後 4 個 `bit` 進行交換。
```
x = 11110000
x >> 4 = 00001111
x << 4 = 00000000
(x >> 4) | (x << 4) = 00001111
```
因此可以猜測第 5 行就是兩個 `bit` 一組，去進行交換；第 6 行就是一個 `bit` 一組進行交換。另外 `0xCC` 就是 `11001100`，可以猜測出另一邊的 `bitmask` 要是 `00110011`，因此 `EXP2` 就是 `(x & 0x55) << 2`。`0xAA` 則是 `10101010`，可以猜測出另一邊的 `bitmask` 就是 `01010101`，因此 `EXP3` 就是 `(x & 0x33) << 1`。
## 測驗 `4`
### 程式碼解釋
```c=1
#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__})))
```
:::info
主要參考 `kevinshieh0225` 同學的解說
:::
不難發現 `foreach_ptr` 與 `foreach_int` 是要把所有參數的內容指定到 `i` 裡面。第 6 行把 `_foreach_i` 當作是 `index`；第 7 行則去判斷有沒有超過參數範圍；最後第 8 行就是把第 `index` 裡的值 assign 到 `i` 並且進行 `index++`，因此可以推斷出 `EXP4` 就是 `_foreach_i++`。同理，`EXP5` 也是 `_foreach_i++`。
## 測驗 `5`
### 程式碼解釋
```c=1
#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;
}
```
首先可以看到 4 ~ 15 行賄先把除數跟被除數都先轉換成正數，並將結果的正負號存在 `singal` 這個變數當中。
接下來看到第 18 行的 `while` 迴圈，會找出除數往左 `shift` 幾次後會比被除數大，因此可以推測出 `EXP6` 就是 `dvs << shift`。
第 22 行的 `while` 迴圈會去看除數是不是比被除數小，假如比較小才需要繼續計算。最後 23 ~ 26 行則是透過 `shift` 找出商，並減去轉成傷的部分。因此可以推測出 `EXP7` 就是 `dvd - dvs << shift`。
## 測驗 `7`
### 程式碼解釋
```c=1
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;
}
```
首先可以看到第 4 行，去判斷從左數來的 16 個 bits 有無 1，如果有就把結果存進去 `ret` 並且繼續看這 16 個 bits ( 對應到第 5 行)；第 7 行則是從這 16 個 bits 繼續去看從左數來的 8 個 bits，然後進行一樣的操作。因此可以推測出 `EXP10` 會是 `(v > 0x3U) << 1`。
可以觀察到 `0xFFFFU` 是 16 個 bits；`0xFFU` 是 8 個 bits；`0xFU` 是 4 個 bits；`0x3U` 是 2 個 bits。因此還要討論最後一個 bit，因此可以推測出 `EXP11` 會做出以下程式碼的行為，不過是濃縮成一行
```c
m = (v > 0x1U);
v >>= m;
ret |= m;
```
因此可以知道 `EXP11` 就是 `ret |= (v > 0x1U)`
## 測驗 `8`
### 程式碼解釋
```c=1
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;
}
```
:::info
可以先參考[二叉搜尋樹刪除](https://www.delftstack.com/zh-tw/tutorial/data-structure/binary-search-tree-delete/)所提及的刪除方法，會方便理解二元數的刪除原理。
:::
首先可以看到第 4 行的 `while` 迴圈，會在這個迴圈找到要刪除的 `node` ，這邊使用指標的指標，可以找到要刪除的 `node` 以及他的 `parent`。可以知道 `EXP12` 是要往左邊走，`EXP13` 是要往右邊走，因此 `EXP12` 就是 `p = &(*p)->left`；`EXP13` 就是 `p = &(*p)->right`。
接下來就是要討論三種刪除的可能性，首先是要刪除的 `node` 沒有左子樹；再來是要刪除的 `node` 沒有右子樹，相對應的操作在 14 ~ 17 行；最後就是有左右子樹，因此只要將右子樹中最小值搬到要刪除的 `node` 位置。可以推測出 20 行的 `while` 迴圈是要找出右子樹中的最小值，因此 `EXP14` 就是 `&(*r)->left`。
## 測驗 `9`
### 程式碼解釋
```c=1
/* 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))
```
:::info
主要參考 `kevinshieh0225` 同學的解說
:::
首先可以看到是要做出 16 的倍數，因此 address 的最後 4 個 bit 要可以為 0，因此可以先推測出 `NNN` 就是 `MAX_ALIGMENT - 1`。另外由於是向上對齊，所以不足 16 倍數的則要補上去，因此可以猜測出 `MMM` 就是 `1`。
## 測驗 `10`
### 程式碼解釋
```c=1
#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)); \
})
```
首先可以看到第 5 行的條件式，主要是用來判斷除數跟被除數是不是均為正數，另外就是利用 `typeof` 去看型態是不是 `unsigned`。假如符合條件就會進行第一個操作 `((RRR) / (__d))`，不符合的話就會進行 `((SSS) / (__d))`。
回顧本題目就是要進行四捨五入的操作，其中可以觀察到第 7 行的 `/` 在 c 語言當中是無條件捨去，因此要作一些對應的操作使其符合四捨五入的原則。
因此可以推測出 `RRR` 就是 `__x + (__d >> 1)`。另外若有負數的話就要進行減，因此 `SSS` 就是 `__x - (__d >> 1)`。
Sign in with Wallet
Connect another wallet