# 2022q1 Homework3 (quiz3) contributed by < `cy023` > > [測驗題](https://hackmd.io/@sysprog/linux2022-quiz3) ## 測驗 `1` ```c #define GENMASK(h, l) \ (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT))) ``` ```c #define GENMASK(h, l) \ (((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l))) ``` <!-- Why `>> (l) << (l)`, instead of `<< (l)` --> :::success 延伸問題: - [ ] 1. 解釋上述程式碼運作原理 - [ ] 2. 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量 - [ ] 3. 舉出 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}; } ``` :::success 延伸問題: - [ ] 1. 解釋上述程式碼運作原理 - [ ] 2. 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說 ::: ## 測驗 `3` ```c 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; } ``` :::success 延伸問題: - [ ] 1. 解釋上述程式碼運作原理 - [ ] 2. 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景 ::: ## 測驗 `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__}))) ``` ### 參考 C99 規格書 > 6.10.3 Macro replacement > Constraints > ... > 5 The identifier \_\_VA_ARGS\_\_ shall occur only in the replacement-list of a function-like macro that uses the ellipsis notation in the parameters. > 6.10.3.1 Argument substitution > ... > 2 An identifier \_\_VA_ARGS\_\_ that occurs in the replacement list shall be treated as if it were a parameter, and the variable arguments shall form the preprocessing tokens used to replace it. ## 測驗 `5` `dvs << shift` `dvd -= dvs << shift` ## 測驗 `6` ## 測驗 `7` ## 測驗 `8` ## 測驗 `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 - 1) & ~(-MAX_ALIGNMENT)) /* Given a size, round down to the next multiple of sizeof(void *) */ #define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \ ((x) & ~(-MAX_ALIGNMENT)) ``` ## 測驗 `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)); \ }) ``` ## 測驗 `11` `fls()` 函式用來找 64 bits 變數中最靠近 ```c // find left set static inline unsigned long fls(unsigned long word) { int num = 64 - 1; if (!(word & (~0ul << 32))) { // focus on bit63 ~ bit32 num -= 32; word <<= 32; } if (!(word & (~0ul << (64 - 16)))) { // focus on bit63 ~ bit48 num -= 16; word <<= 16; } if (!(word & (~0ul << (64 - 8)))) { // focus on bit63 ~ bit56 num -= 8; word <<= 8; } if (!(word & (~0ul << (64 - 4)))) { // focus on bit63 ~ bit60 num -= 4; word <<= 4; } if (!(word & (~0ul << (64 - 2)))) { // focus on bit63 ~ bit62 num -= 2; word <<= 2; } if (!(word & (~0ul << (64 - 1)))) // focus on bit63 num -= 1; return num; } ``` ```c 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; if (x >= b) { x -= b; y += m; } m >>= 2; } return y; } ``` - [lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/master/lib/math/int_sqrt.c) :::success 延伸問題: - [ ] 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫 - [ ] 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景 :::