---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < [Duodenum](https://github.com/Duodenum87) >
> [作業要求](https://hackmd.io/@sysprog/linux2022-quiz3)
## 2022q1 第 3 週測驗題
### 測驗 `1`
在 Linux 核心原始程式碼，include/linux/bitfield.h 提及一個巨集 GENMASK，其作用是依據給定的範圍，產生連續的 bitmask
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
輸入為 h, l 合理推斷為兩段 bitset 最後 & 出所求，兩段分別為 `h 到 LSB` 以及 `l 到 MSB` 。 例如: 00011111~2~ & 11110000~2~ = 00010000~2~
因為 UL 為 64 bits ， (~0UL) 需要右移 `64 - 1 - h` bits ，`LEFT` = `63 - h`
而後者先右移 `l` 後再左移 `l` 後即可將後 `l` bits 設為 `0` ， `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};
}
```
由上方 `fd` 結構體可知 `EXP1` 前綴應為 `(struct foo *)` 指向 `foo` 的指標
因題目要求做 4 byte alignment ，其指標位址需要可以整除 4 ，也就是說最後的兩個 bit 清零。 再根據題目中的 `flags` 給予靈感，直接 `v & ~3` 即可達到此效果。 `EXP1` = `(struct foo *)(v & ~3)`
### 測驗 `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-bit 分為前後兩段，並且前後交換
第二行中 `0xCC` = 11001100~2~ ，可以看出為了將 1 與 0 位置交換，所以可以仿照其寫出 `(EXP2)` 為 00110011~2~ 再左移 2bit ， `EXP2` = `(x & 0x33) << 2`
第三行則再細切成相鄰兩位元交換，如同 `0xAA` = 10101010~2~ 。`EXP3` 取 01010101~2~ 再左移 1bit ， `EXP3` = `(x & 0x55) << 1`
### 測驗 `4`
嘗試將 foreach 巨集 予以擴充，使得支援以下寫法:
```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
#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__})))
```
`TODO`
### 測驗 `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;
}
```
前兩個 if 迴圈分別判斷除數與被除數的正負，如其中有負數，則以 `signal` 紀錄之，並將負數取絕對值以實現除法。接下來的演算法概念則與長除法相似，首先將除數提高至被除數的最高位數，再逐位數算出商數。第一個 while 迴圈就是在做提高位數的部分，其判斷式即為將除數乘上 2 的冪直到大魚被除數為止， `EXP6` = `dvs << shift` 。
第二個 while 迴圈即為對每個位數計算對映的商，並將被除數減去所消去之值， `EXP7` = `dvd -= dvs << shift` 。
### 測驗 `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;
}
```
`TODO`
### 測驗 `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;
}
```
Sign in with Wallet
Connect another wallet