# 2022q1 Homework3 (quiz3)
contributed by < `Kevin-Shih` >
## 測驗 1
**題目**
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`，其作用是依據給定的範圍，產生連續的 bitmask，例如:
- `GENMASK(6, 4)` 產生 01110000~2~
- `GENMASK(39, 21)` 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
請補完，使其行為符合預期。
#### 運作原理與解題
`AND` 的左邊可以看出是要透過 `~0UL` 右移產生低位的 `h` bits 均為 1 的 `unsigned long`，而右側則是以左移產生低位 `l` bits 均為 0 的 `unsigned long` 接著就可以用 `AND` 運算得到 `h` 至 `l` 之間的 bits 均為 1 的 bitmask。
因此 `LEFT` 應為 `63 - h`，以產生低位 `h` bits 均為 1 的 `unsigned long`， `RIGHT` 應為 `l` 以產生低位 `l` bits 均為 0 的 `unsigned long`。
> 由於左移超過變數長度時，其結果在 c 屬於未定義行為，因此先左移 `l` bits 再右移 `l` bits 以避免此情形發生。
:::warning
TODO
- 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量
- 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
:::
#### 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量
#### 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
## 測驗 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](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。其中 `struct foo;` 運用〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧，可在實作階段才提供具體 `struct foo` 的定義。
請補完，使其行為符合預期。
#### 運作原理與解題
由於 `fd` 結構體的第一個成員是指向 `struct foo` 結構體的指標，因此 `EXP1` 肯定要將 `unsigned long` 型態的 `v` casting 成指向 `struct foo` 型態的指標，即 `EXP1` 前面一定包含 `(struct foo *)`。
接著由於要作 4 byte 的 align down 因此代表 2^1^, 2^0^ 的最低位 2 bits 應設為 0 (低位的 log~2~(4) 個 bits 設為 0)，而這可以透過 `AND` 一個最低 2 位為 0 的 bitmask 達成，最簡潔的寫法是透過取 `3` 的 1 補數達成。
因此 `EXP1` = `(struct foo *)(v & ~3)`
:::warning
TODO
- 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
:::
#### 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
## 測驗 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;
}
```
請補完，使其行為符合預期。
#### 運作原理與解題
進行 `rev8` 前的一個 `uint8_t` 示意圖
```graphviz
digraph "reverse-bits" {
node [shape=record];
rankdir=LR;
a [label="{ 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 }"];
}
```
> 為求方便辨識原本的 0 到 7 bit 分別以 0 到 7 標注
#2 將高位 4 bits 與低位 4 bits 對調後
```graphviz
digraph "reverse-bits" {
node [shape=record];
rankdir=LR;
a [label="{ 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 }"];
}
```
#3 左半邊可以看出是將 4 bits 內的高位 2 bits 調至低位 2 bits，因此不難猜出 `EXP2` 是將 4 bits 內的低位 2 bits 調至高位 2 bits，調換後的示意圖如下
```graphviz
digraph "reverse-bits" {
node [shape=record];
rankdir=LR;
a [label="{ 1 | 0 | 3 | 2 | 5 | 4 | 7 | 6 }"];
}
```
#4 的左半邊當然就是將 2 bits 內的高位 bit 調至低位 bit，因此 `EXP3` 是將 2 bits 內的低位 bit 調至高位 bit，調換後的示意圖如下
```graphviz
digraph "reverse-bits" {
node [shape=record];
rankdir=LR;
a [label="{ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 }"];
}
```
由上面的步驟得出答案為
- `EXP2` = `(x & 0x33) << 2`
- `EXP3` = `(x & 0x55) << 1`
> `0x33` = `0b00110011`, `0x55` = `0b01010101`
:::warning
TODO
- 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
#### 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
## 測驗 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);
}
```
預期輸出如下:
```
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`, `foreach_ptr` 中的 `_foreach_i` 都是用來標示讀到第幾個 `__VA_ARGS__` 的，因此每次迴圈 `foreach_int` 應加 1，而由於每次迴圈的更新要對 `i` 賦值，使其值等於下個 `__VA_ARGS__` 中的值，因此 `EXP4`, `EXP5` = `++_foreach_i`，而非 `_foreach_i++`。 (先更新 `foreach_int` 再對 `i` 賦值)
:::warning
TODO
- 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
#### 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
## 測驗 5
**題目**
針對 [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```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;
}
```
請補完，使其行為符合預期。
#### 運作原理與解題
#5 ~ #15 用於處理當除數或被除數有負值的時候將其轉為正值後存入對應的 `unsigned int`，並將其正負號紀錄於 `signal` 變數，方便後續運算。
#18 則是當被除數大於除數乘上 2^shift^ 時，代表商的最高位的 1 (first set bit) 至少在第 `shift` bit。 就像十進位除法 900 除 10 我們會移到百位數後發現 9 < 10 最後從十位數開始寫商，而更大的位數則留下 0。
> 實際上跳出迴圈時 `shift` 會比商的 first set bit 的 index 多 1 但會在後續的 while loop handle
因此 `EXP6` = `dvs << shift`
#22 開始的 while loop 是整個除法的主體，內層的 while loop 就是在處理先前比喻的 9 < 10 的情形下商會退 1 位再繼續寫若退 1 位後還是被除數還是小於位移後的除數就退到不小於為止。 當被除數不小於位移後的除數時就將 1 紀錄到 `res` 中對應的 bit，並將被除數減去位移後的除數的值，因此 `EXP7` = `dvd -= dvs << shift`，而 while loop 會進行到剩下的 `dvd` 小於 `dvs` 為止。
最後將 `res` 乘上先前紀錄的正負號 `signal` 即為答案。
:::warning
TODO
- 指出上述程式碼可改進之處，並予以實作
- 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論
:::
#### 指出上述程式碼可改進之處，並予以實作
#### 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論
## 測驗 6
**題目**
針對 [LeetCode 149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```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;
}
```
請補完，使其行為符合預期。
#### 運作原理與解題
:::warning
TODO
- 指出上述程式碼可改進之處，並予以實作
- 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
:::
#### 指出上述程式碼可改進之處，並予以實作
#### 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行
## 測驗 7
**題目**
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```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;
}
```
請補完，使其行為符合預期。
#### 運作原理與解題
#3 當 `v` 是非零的值就至少需要 1 bit 紀錄，故 `ret = v > 0`
#4 ~ #6 當 `v` 的 first set 在高位的 16 bits 中， `v` 會右移 16 bits 並在剩下的 16 bits 繼續找 first set ， `ret` 則加上 16。 若不是的話， `m` 會為 0 不影響後續步驟。 (會變成找低位的 16 bits 中使否有 first set)
#7 ~ #9 則是找在剩下的 16 bits 中 `v` 的 first set 是否在較高的 8 bits 中，若有 `v` 會再右移 8 bits 並在剩下的 8 bits 繼續找 first set ， `ret` 則加上 8。
後面依此類推，`EXP10` 是在最後 4 bits 中找 `v` 的 first set 是否在較高的 2 bits 中，因此 `EXP10` = `(v > 3) << 1`。 `EXP11` 是在最後 2 bits 中找 `v` 的 first set 是在較高的 bit 中或是較低的那個，若是在較高的就將 `ret += 1` 若不是就不用加，因此 `EXP11` = `ret += v > 1`。
> `EXP11` 已經是最後一步了，所以直接改 `ret` 就好，不須再對 `v` 做位移或先紀錄到 `m` 。
:::warning
TODO
- 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
- 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
- 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作
:::
#### 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
#### 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
#### 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作
## 測驗 8
**題目**
考慮以下 C++ 二元搜尋樹的程式:
```cpp
typedef struct tnode *tree;
struct tnode {
int data;
tnode *left;
tnode *right;
tnode(int d)
{
data = d;
left = right = 0;
}
};
void remove_data(tree &t, int d)
{
tnode *p = t;
tnode *q;
while (p != 0 && p->data != d) {
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
}
if (p != 0) {
if (p->left == 0)
if (p == t)
t = p->right;
else if (p == q->left)
q->left = p->right;
else
q->right = p->right;
else if (p->right == 0)
if (p == t)
t = p->left;
else if (p == q->left)
q->left = p->left;
else
q->right = p->left;
else {
tnode *r = p->right;
while (r->left) {
q = r;
r = r->left;
}
p->data = r->data;
if (r == p->right)
p->right = r->right;
else
q->left = r->right;
p = r;
}
delete p;
}
}
```
函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
```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;
}
```
請補完，使其行為符合預期。
#### 運作原理與解題
前面的 while loop 是在找要刪除的 node 依據二元搜尋樹的特性當要刪除的 node `d` 小於當前的 node 的 data，應向 left child 繼續搜尋，大於時則向 right child 搜尋。 因此 `EXP12` = `p = &(*p)->left`, `EXP13` = `p = &(*p)->right`。
> 將 indirect pointer `p` 指向 `*p` 的 left 或 right 所在的記憶體位置
當要移除的 node 存在時 `*p` 會指向該 node，若否則 `*p` 會等於 `null`，而 `p` 則是指向該 node 的 parent 的 left 或 right 所在的記憶體位置。 因此接下來只須將 `*p` 指向接替 node `d` 的 node 就完成 remove 了。
**沒有左子樹或右子樹時**
```cpp
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
```
當被移除的 node 沒有左子樹時直接以右子樹取代該 node。 反之若沒有右子樹時直接以左子樹取代該 node。
**左右子樹都存在時**
```cpp
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
```
這邊是從右子樹中找最小的 node 取代要移除的 node。 先以 `r` 指向要移除的 node 的 right，當該 node 有左子葉時 `r` 就指向 `(*r)->left` 所在的記憶體位置，一路找到沒有左子葉時就是右子樹中最小的 node。 接著將這個 node 的 data 複製到要刪除的 node 中取代要被刪除的值，並將 `q` 指向該 node，並將 `*r` 指向 `q` 的右子樹。 因此 `EXP14` = `&(*r)->left`。
最後刪除 `q` 即可。
:::warning
TODO
- 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
- 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
:::
#### 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
#### 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
Sign in with Wallet
Connect another wallet