--- tags: linux2022 --- # 2022q1 Homework3 (quiz3) contributed by < `eric88525` > > [第 3 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz3) # Q1 ```c #define GENMASK(h, l) \ (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))) // (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) ``` 1. 從最低位元到 `l` 位元需要為 0，可判斷 shift left 應該為 `l` 次，先 shift right 2. ～0UL 為 0XFFFFFFFFFFFFFFFF 且是無號數，右移 63-h 位元可讓 h 到最高位元為0 3. 做 and 運算可留下左右方的 0 ， 並保留共通的 1 + 仔細思考後認為 `(~0UL) >> (l) << (l))` 可以寫成 `(~0UL) << (l)` ，原因是 `(~0UL) >> (l) << (l))` 後，結果為最低位元到 `l` 為 0 其餘為 1，跟`(~0UL) << (l))` 的結果一樣的 # Q2 ```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}; // return (struct fd){EXP1, v & 3}; } ``` + 向下對齊 4 bytes 規律： + 0～3 對齊到0 + 4～7 對齊到4 + 8～11 對齊到 8 + 可以觀察到只要把最後兩個位元設成0即可對齊，因此要 `&~3` 並轉形成struct 定義的型態 # Q3 ```c #include <stdint.h> uint8_t rev8(uint8_t x) { x = (x >> 4) | (x << 4); x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); // x = ((x & 0xCC) >> 2) | (EXP2); x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); // x = ((x & 0xAA) >> 1) | (EXP3); return x; } ``` ``` abcd efgh // x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2) efgh abcd // ((x & 0xCC) >> 2) | ((x & 0x33) << 2) ghef cdab // x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1) hgfe dcba ``` + 透過 & mask 來讓特定位元交換 # Q4 ```c #include <stdio.h> #include <stdarg.h> #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__}))) int main() { int i; char *p; foreach_int(i, 0, -1, 100, 0, -99) printf("i is %i\n", i); foreach_ptr(p, "Hello", "world") printf("p is %s\n", p); return 0; } ``` + `__VA_ARGS__` 用於將 macro 中的 `...` 展開 + 在 for 迴圈中： + 用於遍歷的變數為 `_foreach_i` ， 因此要在每次迴圈結束都+1，也就是 `++_foreach_i` + `_foreach_i` 上限為 `sizeof((int[]){__VA_ARGS__}) / sizeof(int);` ，求得整個 int 陣列的元素數量 + 編譯時在預處理停止，可以看到 macro 會有以下展開，在宣告 `_foreach_i` 時很巧妙的透過 () 和 ＝ 的特性，先讓 i 等於陣列的第 0 元素，接著把 0 指派給 _foreach_i ```c for (unsigned _foreach_i = (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); (i) = ((int[]){0, -1, 100, 0, -99, 0})[_foreach_i++]) printf("i is %i\n", i); ``` # Q5 ```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; } ``` # Q6 # Q7 ```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 > 0x3) << 1; v >>= m; ret |= m; ret += v > 1; return ret; } ``` 32 bit 為 0x0000 0000 ~ 0xFFFF FFFF , 0~31 bit + binary search 的概念，每次都先檢查 v 是否大於\$n/2\$的位元數，確認是否在0~n-1 或是 n~最高位元。 n 初始為32，每當檢查完一輪 ， n 都會除以2 + line `4-6` `7-9` `10-12` `13-15` 是做相同的事情，先檢查 v 所含位元，是否大於 v 可能有的最高位元數的一半，舉例： + 第4行先檢查 v 有無大於 32bits 的一半，也就是 0xffff ，第7行檢查 v 有無大於 16bits 的一半，也就是 0xff + 每次檢查完如果有大於一半的位元數，用 ret 來紀錄至少含有的位元數: + line 4 `v > 0xFFFF` 可確定最高位元至少會大於 1<<4 bit，也就是 16 bit，用 ret 紀錄下來 # Q8 ```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; // r = EXP14; q->data = (*r)->data; q = *r; *r = q->right; } delete q; } ``` + 根據二元樹的規則，節點右側會大於當前節點，左邊則是小於。因此在 `line:5` 比較完數值後，要選擇往右或是往左走 + EXP14 為讓 **r 在 d 節點右邊 subtree 中，往走找到最小值 + 假設 d 為15，15 右邊 subtree 的最小數值為18 ```graphviz digraph{ 10->5; 10->15; 15->14; 15->20; 20->18; 20->33; 15[color=blue]; 18[color=red]; } ``` + 把目標替換成 subtree 的最小數值 ```graphviz digraph{ 10->5; 10->18; 18->14; 18->20; 20->33; 18[color=red] } ``` # Q9 ```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 - 1u) & ~(MAX_ALIGNMENT - 1u)) ``` + 題目要求為 roundup + ROUND_UP_TO_ALIGNMENT_SIZE(1~16) = 16 + ROUND_UP_TO_ALIGNMENT_SIZE(17~32) = 32 + ROUND_UP_TO_ALIGNMENT_SIZE(33~48) = 48 MAX_ALIGNMENT 的二進位為 `0x10000` ，減一後 `0x1111`，可以把不足16的部分強制進位 進位後需要保留 `0x10000` 以後的資訊，因此要 `& ~(MAX_ALIGNMENT - 1u)` ，讓0~3bit 為0，4bit 以上保留 ``` 0x0000100 + 0x0001111 ----------- 0x0010011 & 0x1110000 ------------- 0x0010000 ``` # Q10 ```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)); \ }) ``` + line 3-4: + 先用暫存變數存 x 數值，避免在後續展開時被更動，例如輸入 x++，在後續每次被使用時數值都會變動 + line 5: 檢查 signed 或是 unsigned，如果 unsigned 條件會為 true + signed int -1 = -1 + unsigned int -1 = 4294967295 + line 6: + 判斷正負號是否相同 + line 7-8: 這段可視為 (__x / __d) +- 0.5 + 如果 x / divisor 為負，-0.5 來達到四捨五入 + 如果 x / divisor 為正，+0.5 來達到四捨五入