# 2022q1 Homework3 (quiz3)
contributed by < [`leewei05`](https://github.com/leewei05) >
###### tags: `linux2022`
## [測驗 1](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-1)
:::info
- [x] 解釋上述程式碼運作原理
- [ ] 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
- [ ] 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例
:::
- GENMASK(6, 4) 產生 $01110000_2$ (2 進制)
- GENMASK(39, 21) 產生 0x000000ffffe00000 (64 位元)
已知我們使用的微處理器架構為 64 位元，且 unsigned long 為 8 位元組寬度 (符合 LP64 資料模型)，以下是可能的 GENMASK 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
首先 GENMASK 代入(6, 4) 先右移 57 再左移 4
```c
result = 0x000000000000007f(01110000)
(~0UL) >> (4) = 00001111
(~0UL) >> (LEFT) = 11111111 or 01111111
LEFT = 56 or 57
(~0UL) >> (4) << (RIGHT) = 01111000 or 11110000
RIGHT = 3 or 4
// Cannot be LEFT = 56, RIGHT = 4
```
接著 GENMASK 代入(39, 21) 先右移 24 再左移 21
```c
result = 0x000000ffffe00000(24*0 19*1 21*0)
(~0UL) >> (21) = 0x000007ffffffffff (21*0 43*1)
(~0UL) >> (LEFT) = 0x000000ffffffffff (24*0 40*1)
LEFT = 24
(~0UL) >> (21) << (RIGHT) = 0xffffffffffe00000(43*1 21*0)
RIGHT = 21
```
`LEFT = 63 - h`
`RIGHT = l`
以下取自 [Linux Kernl 程式碼](https://elixir.bootlin.com/linux/latest/source/include/linux/bits.h#L37)
```c
/*
* Create a contiguous bitmask starting at bit position @l and ending at
* position @h. For example
* GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
*/
#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
* BUILD_BUG_ON_ZERO is not available in h files included from asm files,
* disable the input check if that is the case.
*/
#define GENMASK_INPUT_CHECK(h, l) 0
#endif
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
(~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
#define __GENMASK_ULL(h, l) \
(((~ULL(0)) - (ULL(1) << (l)) + 1) & \
(~ULL(0) >> (BITS_PER_LONG_LONG - 1 - (h))))
#define GENMASK_ULL(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK_ULL(h, l))
```
## [測驗 2](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-2)
:::info
- [ ] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
:::
考慮以下程式碼:
```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};
}
```
## [測驗 3](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-3)
:::info
- [x] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode 190. Reverse Bits 的描述。
前後四位元進行互換 `x = (x >> 4) | (x << 4);`。`0xCC` 的二進制為 `11001100`，`0xAA` 的二進制為 `10101010`。推斷 `EXP2 = (x & 0x33) << 2)`， `EXP3 = (x & 0x55) << 1)` 因為依序是左右互換 4, 2, 1 的位元。
```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;
}
```
## [測驗 7](https://hackmd.io/@sysprog/linux2022-quiz3#%E6%B8%AC%E9%A9%97-7)
:::info
- [ ] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
- [ ] 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
- [ ] 運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作
:::
考慮 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;
}
```
> 6.5.8 Relational operators
> Each of the operators < (less than), > (greater than), <= (less than or equal to), and >=
(greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.92)
The result has type int.
如果 `v > 0` 則 `ret` 為 1; `v <= 0` 則 `ret` 為 0。
`0xFFFFU` 全為 1 的 16 位元數
Sign in with Wallet
Connect another wallet