# 2022q1 Homework3 (quiz3)
contribute by < `Korin777` >
## 測驗一
在 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)` 產生 $01110000_{2}$
* `GENMASK(39, 21)` 產生 0x000000ffffe00000 (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) >> (63 - h)) & ((~0UL) >> (l) << (l)))
```
* `~0UL` 每個位元皆為 1,而 `GENMASK` 則會將 h ~ l 以外的位元都變為 0
* 先將一個 `~0UL` 的 63 ~ h 位元(不包括 h)變為 0 => `(~0UL) >> (63 - h)`
* 再將另一個 `~0UL` 的 l ~ 0 位元(不包括 l)變為 0 => `(~0UL) >> (l) << (l)`
* 對前兩數做 & 運算即可獲得題目所求 => `((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))`
## 測驗二
```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};
}
```
* [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down) : A value at or before value that is a multiple of alignment.
* 題目要求第一個成員的地址對 4 個位元組進行向下對齊 , 所以該地址必為 4 的倍數且比 v 小 , 即 v 的最後兩個 bit 應為 0
* `~3` 二進位表示中 , 第 0 及第 1 個 bit 為 0 其餘皆為 1 , 因此 `v & ~3` 能夠確保地址為 4 的倍數且比 v 小
## 測驗三
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);
return x;
}
```
* `0xCC = 11001100` `0x33 = 00110011`
* `0xAA = 10101010` `0x55 = 01010101`
1. 先將 `x` 分為兩半 , 左半邊的 bit 與右半邊互換 , 此時 `x` 被分為兩塊
2. 將分出來的兩塊在各別切為兩半 , 左半邊的 bit 與右半邊互換 , `x` 被分為四塊 `0xCC = 11001100` `0x33 = 00110011`
3. 將分出來的四塊在各別切為兩半 , 左半邊的 bit 與右半邊互換 , `x` 被分為八塊 , 而各塊皆為 1 bit , 反轉完成
e.g : 11010010
1101 | 0010 => 00101101
00|10 11|01 => 10000111
1|0 0|0 0|1 1|1 => 01001011
## 測驗四
```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})[++_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__})))
```
* `foreach_int` 即 `foreach_ptr` 為 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) 可以傳入可變數量的參數(即 `...` 可為零或多個) , 而在最後被命名的 argument(即 `i`) 後的所有 argument(包含他們之間的逗號) 會被前處理器展開到有 `__VA_ARGS__` 的地方
* `(((int[]){__VA_ARGS__})[0])` 即展開為 `(((int[]){0, -1, 100, 0, -99})[0])` 也就是 array `((int[]){0, -1, 100, 0, -99})` index 0 的值
* `_foreach_i` 會被 assign 成 `(((i) = ((int[]){__VA_ARGS__})[0]), 0)` 括號中最後的那個值 , 也就是 0
* for 迴圈每跑完一次 `i` 就要改為 array 下一個 index 的值 , 因此 `_foreach_i` 要先加 1(即 `++_foreach_i`)
## 測驗五
```c
#include <limits.h>
// dividend / divisor
int divide(int dividend, int divisor)
{
int signal = 1; // 商的正負
// 確保 dvd dvs 為正數 dvd / dvs
unsigned int dvd = dividend;
if (dividend < 0) { // 被除數為負數
signal *= -1;
dvd = ~dvd + 1; // dvd = -dvd
}
unsigned int dvs = divisor;
if (divisor < 0) { // 除數為負數
signal *= -1;
dvs = ~dvs + 1; // dvs = -dvs
}
int shift = 0;
while (dvd > (dvs << shift)) // 找出 divisor 乘以 2 的多少次方後會大於 dividend
shift++;
unsigned int res = 0;
while (dvd >= dvs) { // 找出 dividend 除以 divisor 的商之二進位表示中 bit 為 1 的位元 , 並將 res 對應的位元設成 1
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
dvd -= dvs << shift;
}
if (signal == 1 && res >= INT_MAX) // 避免 -2147483648 / -1 = 2147483648 => overflow
return INT_MAX;
return res * signal;
}
```
* 找出 `dividend` 除以 `divisor` 的商之二進位表示中 bit 為 1 的位元 , 並將 `res` 對應的位元設成 1
e.g : $101 \div 5 = 20 = 5 \times 2 ^ 4 + 5 * 2 ^ 2 = 10100_{2}$ = `res`
## 測驗六
```c
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return p1 == pn->p1;
return true;
}
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;
list_add(&pn->link, &heads[hash]);
}
}
}
}
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;
}
```
* `hori_cnts[i]` : 用來記錄與點 i 在同一個水平線上的點數量
* `vert_cnts[i]` : 用來記錄與點 i 在同一個鉛直線上的點數量
* `dup_cnts[i]` : 用來記錄與點 i 重複的點數量
* `slope_cnts[i]` : 用來記錄與點 i 在同個斜率 m 之線上的的點數量
* `heads[i]` : 用來連結某個斜率下的所有點 `point_node`
* `static bool can_insert(struct list_head *head, int p1, int p2)` : 用來判斷一個點該不該被加到 `list_head[i]`
* 每個 `list_head[i]` 一開始都可以插入點
* 當有一點插入 `list_head[i]` 後 , 除非 `p1` 為第一個插入的點 , 否則就不允許插入 , 這是因為 `maxPoints` 會先將 `points[1~pointsSize-1]` 中與 `points[0]` 斜率為 m 的點加入對應的 `list_head[i]` , 再來換看 `points[1]` , 而 `points[1]` 與 `points[2~pointsSize-1]` 一樣有斜率為 m 的點且對應到同一個 `list_head[i]` , 這時要是允許插入 , 就會出現點重複的情況
* maxPoints : 求出 `hori_cnts`、`vert_cnts`、`slope_cnts` , 當中最大的即為 Max Points on a Line
註:
1.`int hash = dx * dy - 1333 * (dx + dy)` 應改為 `int hash = dx * dy - 1333 * (dx - dy);` , 否則 (0,0)、(3,4)、(4,3) 會被判斷再同意條線上 , 因 (0,0)、(3,4) 及 (0,0)、(4,3) `hash` 值相同
2.同樣斜率的多條不同的線只有第一條會被記錄
3.題目的點都是唯一的 , 所以可以不用計算 `dup_cnts`
## 測驗七
```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 > 3) << 1;
v >>= m;
ret |= m;
ret += v > 1;
return ret;
}
```
* 題目要求最少需要多少位元才可儲存 , 即 32 位元中最高位元的 1 出現在哪一個 bit
* `ret` : 最少需要多少位元才可儲存
1. 每次將 `v` 尚未檢查的 bits 分為兩半 , 並看左半邊是否有值
2. 有的話表示最高位元的 1 在左半邊 , 且我們需要右半邊的 bit 來儲存 `v` , 這時右半邊查看完畢 ; 沒有則表示最高位元的 1 在右半邊 , 這時左半邊查看完畢 , 重複步驟 1 直到剩兩個尚未檢查的 bit
3. 最後兩個尚未檢查的 bit 會分別在 `ret = v > 0;` 及 `ret += v > 1;` 被檢查到
* e.g : v = 01110010
v > 0 => ret = 1
0111 | 0010 => 0111 、 ret = 1 + 4
01 | 11 => 01 、 ret = 1 + 4 + 2
01 <= 1 => ret = 1 + 4 + 2 = 7
## 測驗八
```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; // EXP14
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
* 題目為[二元搜尋樹](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9) , 可知樹的 left child 比 parent 小 , 而樹的 right child 比 parent 大
* EXP12 及 EXP13 為二元搜尋樹尋找 data 的過程 , 根據 if 條件可知是要往左還往右 , 而 `p` 為 pointer to pointer 所以應該 assign 成 pointer 的地址 e.g:`&(*p)->left`
## 測驗九
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```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 - 1) & ~(MAX_ALIGNMENT - 1))
```
* 由題目及程式碼可以推測 ， 此巨集的功能為將給定的記憶體以 16 個 bit向上對齊
* `(((x) + MAX_ALIGNMENT - 1)` 確保新的記憶體位置大於等於原本的記憶體位置 ， 達成向上對齊
* `& ~(MAX_ALIGNMENT - 1)` 將低位的 4 個 bit 清為 0 ， 確保記憶體位置為 16 的倍數
撰寫出對應 ROUND_DOWN 巨集:
```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_DOWN_TO_ALIGNMENT_SIZE(x) \
(x & ~(MAX_ALIGNMENT - 1))
```
* 只要將 `x` 低位的 4 個 bit 清為 0 就能確保記憶體位置為 16 的倍數 ， 且新的記憶體位置也小於等於原記憶體位置 ， 達成向下對齊
## 測驗十
```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)); \
})
```
* DIVIDE_ROUND_CLOSEST 巨集會得到 `x` 除以 `divisor` 四捨五入後的結果
* 加上 `(__d >> 1)` 相當於讓 `(__x)/(__d)` 四捨五入 ， 當 `(__x) >= 0.5*(__d)` 則 `(__d)-(__x)%(__d) <= (__d >> 1)` => 進位 ， 又整數除法會無條件捨去小數
* `(((__x) > 0) == ((__d) > 0)))` 判斷結果為正或負 ， 負數捨去小數點相當於取大的數 ， 因此要改成減 `((__d) >> 1)`
* `(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0` 判斷 `x` 或 `divisor` 是否為無號數 ， 若有無號數 ， 因另一數也會被轉型成無號數 ， 所以結果必為正數
## 測驗十一
```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;
y >>= 1; //xxx
if (x >= b) {
x -= b; //yyy
y += m;
}
m >>= 2; //zzz
}
return y;
}
```
* 參考 [kdnvt 的筆記](https://hackmd.io/@kdnvt/linux2022-quiz3) ， 將 `x` 拆為以下形式:
* $x = (000b_0b_1b_2\cdots b_{n-1}b_{n})^2$
* $000b_0b_1b_2\cdots b_{n-1}b_{n}$ 為 bits pattern ， $b_0$ 為最高位的 1 ， $b_1$~$b_n$ 為 0 或 1 ， $(000b_0b_1b_2\cdots b_{n-1}b_{n})$ 即所求的平方根 `y`
* `fls` : 找出某數最高位的 bit 1 ， 最低為 0 最高為 63
* `m = 1UL << (fls(x) & ~1UL)` : 題目平方根為向下取整 ， 又 `y` 的平方最小一定為奇數個 bits ， 因此當 `x` 最高位的 1 在偶數 bit 時( fls(x) 為奇數) ， 要將 fls(x) 減一( `fls(x) & ~1UL`) ， 確保 `y` 平方小於等於 `x`
* while 迴圈為求得 `y` = $(b_0b_1b_2\cdots b_{n-1}b_{n})$ 的過程 ， 從 $b_0$ 找到 $b_n$ ， 其中 m 為 $b_i^2$ ， y 為 $2*b_i*(b_{i-1} + \cdots + b_0)$(假設目前已找出$(b_0\cdots b_{i-1}xxx)$ , x為尚未找出的bit) ， 而 `b = y + m` 則為 $b_i$ 為 1 時當前 $y_i^2$$(b_0\cdots b_{i-1}1000)$ 會多出上一個 $y_{i-1}^2$$(b_0\cdots b_{i-1}0000)$ 的值 ， 當這個值大於 `x` 表示該 bit 應為 0 ， 反之將 `x` 減去 `b` , `y` 加上 `m`
* `m` 為 $b_i^2$ ， 要找下一個 bit $b_{i+1}^2$ 會右移兩位 ， `y` 為 $2*b_i*(b_{i-1} + \cdots + b_0)$ 要找下一個 bit $2*b_{i+1}*(b_{i} + \cdots + b_0)$ 會右移一位
*註 : $b_i$ >> 1 = $b_{i+1}$
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-7)
Sign in with Wallet
Connect another wallet