# 2022q1 Homework3 (quiz3)
contributed by < [2020leon](https://github.com/2020leon) >
## [作業要求](https://hackmd.io/@sysprog/BJJMuNRlq)
- [ ] 重新回答[第 3 周測驗題](https://hackmd.io/@sysprog/linux2022-quiz3)^從測驗一到測驗十一^，附帶的「==延伸問題==」也需要完成
- 解釋程式運作原理時，應提供對應的 [Graphviz](https://graphviz.org/) 圖例，可參照 [Linked List 題目 1 + 分析](https://hackmd.io/@sysprog/linked-list-quiz)
- [ ] 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb), [Linked list 題目分析](https://hackmd.io/s/HyELy5bTz) 和 [參考題解](https://hackmd.io/@RinHizakura/BysgszHNw) 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。
- [x] 將你的共筆加到 [2022q1 Homework3 (作業區)](https://hackmd.io/@sysprog/linux2022-homework3)
## [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
### 測驗 `1`
#### 測驗 `1` 填空
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
首先 `~0UL` 為在二進位中全是 `1` 的數，在 64 位元中即 `0xffffffffffffffff` 。若要達到題目要求，須對該數位移。其中 `(~0UL) >> (LEFT)` 的目的為製造在較高位元的 `0` ，故填入 `63 -h` ；而 `(~0UL) >> (l) << (RIGHT)` 則是空出較低位元的 `0` ，故填入 `l` 。
| 陳述式 | 答案 |
| ------- | -------- |
| `LEFT` | `63 - h` |
| `RIGHT` | `l` |
:::info
注：事實上如下便可達到要求。
```c
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) << (l)))
```
:::
### 測驗 `2`
#### 測驗 `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};
}
```
觀察結構成員型態，因此賦值時須轉換型態為 `struct foo *` 以避免編譯器警告。再依據題目要求「對 4 個位元組進行向下對齊」，須清空所傳進之 `v` 參數之最低二位元，即將 `v` 和一特定遮罩進行 AND 運算。而最容易製作遮罩的方式即對 3 進行一補數運算。因此空格需填入 `(struct foo *) (v & ~3)` 。
| 陳述式 | 答案 |
| ------ | ------------------------- |
| `EXP1` | `(struct foo *) (v & ~3)` |
### 測驗 `3`
#### 測驗 `3` 填空
```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;
}
```
逐一位元反轉可見於[課程說明](https://docs.google.com/presentation/d/1B80k91_3_XuZ0zMzfdgS-D1I29VaHxZTg3XD3bok0io/edit#slide=id.g4f2b7eb495_0_12)，其原理便是從「大單位」逐漸反轉至「小單位」，直至全部反轉完畢。
| 陳述式 | 答案 |
| ------ | ----------------- |
| `EXP2` | `(x & 0x33) << 2` |
| `EXP3` | `(x & 0x55) << 1` |
### 測驗 `4`
#### 測驗 `4` 填空
```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` 巨集均是對 `__VA_ARGS__` 進行遍歷，而 `i` 為遍歷時儲存遍歷值的變數，真正的索引變數為 `_foreach_i` 。在進行遍歷時，須對 `_foreach_i` 做累加，並取其值作為索引。在此為 `++_foreach_i` 而非 `_foreach_i++` 的原因為 `i` 所要儲存的應為下一個元素，因此先加一後再取其值。
| 陳述式 | 答案 |
| ------ | -------------- |
| `EXP4` | `++_foreach_i` |
| `EXP5` | `++_foreach_i` |
### 測驗 `5`
#### 測驗 `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;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
| 陳述式 | 答案 |
| ------ | --------------------- |
| `EXP6` | `dvs << shift` |
| `EXP7` | `dvd -= dvs << shift` |
### 測驗 `6`
#### 測驗 `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 EXP8;
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;
EXP9;
}
}
}
}
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;
}
```
| 陳述式 | 答案 |
| ------ | ----------------------------------- |
| `EXP8` | `p1 == pn->p1` 或 `pn->p1 == p1` |
| `EXP9` | `list_add(&pn->link, &heads[hash])` |
### 測驗 `7`
#### 測驗 `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 = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
| 陳述式 | 答案 |
| ------- | ------------------ |
| `EXP10` | `m = (v > 3) << 1` |
| `EXP11` | `ret += v > 1` |
### 測驗 `8`
#### 測驗 `8` 填空
```cpp
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;
}
```
| 陳述式 | 答案 |
| ------- | ------------------ |
| `EXP12` | `p = &(*p)->left` |
| `EXP13` | `p = &(*p)->right` |
| `EXP14` | `&(*r)->left` |
### 測驗 `9`
#### 測驗 `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))
```
| 陳述式 | 答案 |
| ------ | ------------------- |
| `MMM` | `1` |
| `NNN` | `MAX_ALIGNMENT - 1` |
### 測驗 `10`
#### 測驗 `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)); \
})
```
| 陳述式 | 答案 |
| ------ | ---------------------- |
| `RRR` | `(__x) + ((__d) >> 1)` |
| `SSS` | `(__x) - ((__d) >> 1)` | <!-- (__x) + (__d) -->
### 測驗 `11`
#### 測驗 `11` 填空
```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;
}
unsigned long i_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (fls(x) & ~1UL);
while (m) {
b = y + m;
XXX;
if (x >= b) {
YYY;
y += m;
}
ZZZ;
}
return y;
}
```
| 陳述式 | 答案 |
| ------ | --------- |
| `XXX` | `y >>= 1` |
| `YYY` | `x -= b` |
| `ZZZ` | `m >>= 2` |
Sign in with Wallet
Connect another wallet