---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < `ray90514` >
## 測驗1
以 `GENMASK(6, 4)` 為例， `0b01111111 & 0b11110000 = 0b01110000` ，也就是我們需要兩個數，一個數是最高到 `h + 1` 為 0 其餘為 1 ，另一個是最低位到 `l - 1` 為 0 其餘為 1 。可以位移全為 1 的數也就是 `(~0UL)` 來產生。位移的量為一個右移 `63 - h` 一個左移 `l` 。
## Linux 核心的 `GENMASK` 實作
若依照上述想法寫出的 `GENMASK` 如下，也就是 Linux 核心一開始的實作
```c
(((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
這與題目以及現有實作略有不同， [c32ee3d](https://github.com/torvalds/linux/commit/c32ee3d9abd284b4fcaacc250b101f93829c7bae) 提到了 `(~0UL) << (l)` 會導致 unsigned interger overflow ，在 Clang 會產生 warning ，題目給的解決方法是先右移再向左移，而 Linux 核心則是採用只要一次位移的做法
```c
(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
```
將一個全為 1 的數，減去第 `l` 位為 1 的數，產生一個除了第 `l` 位為 0 其他位為 1 的數
${11111111 - 00010000 = 11101111}$
再將這個數加一，結果為低 `l` 位為 0 的數，也就是我們要的數
${11101111 + 1 = 11110000}$
接下來 [95b980d](https://github.com/torvalds/linux/commit/95b980d62d52c4c1768ee719e8db3efe27ef52b2) 將 `1UL` 替換成 `UL(1)` 以相容於組合語言程式中使用該巨集
```c
(((~UL(0)) - (UL(1) << (l)) + 1) & (~UL(0) >> (BITS_PER_LONG - 1 - (h))))
```
最後是加入編譯時期的檢查
```c
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
#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))
```
`BUILD_BUG_ON_ZERO` 要求傳入編譯時期可得知且為 0 的值，否則會產生 error
`__builtin_choose_expr(const_exp, exp1, exp2)` 語意同 const_exp ? exp1 : exp2
`__is_constexpr` 是用來判斷是否為 constant expression
綜合上述三項，若 `h` 和 `l` 是編譯時期可得知的值，`GENMASK_INPUT_CHECK` 會檢查 `h` 要大於等於 `l` ，若不成立則編譯時會產生錯誤。
### `GENMASK` 於 `bitfield.h` 的應用
`GENMASK` 用來產生指定 bitfield 的 mask ，用於 bitfield.h 所定義的巨集。
像是若第 6 ~ 2 位是我們要操作的 bitfield，則定義一個 mask 為 `GENMASK(6, 8)`
將其傳入`FIELD_GET(_mask, _reg)` 可以取得 `_reg` 中該 bitfield 的值。
### `GENMASK` 於 `find.h` 的應用
這段程式碼在 tools/include/linux/find.h
```c
static inline
unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
unsigned long offset)
{
if (small_const_nbits(size)) {
unsigned long val;
if (unlikely(offset >= size))
return size;
val = *addr & GENMASK(size - 1, offset);
return val ? __ffs(val) : size;
}
return _find_next_bit(addr, NULL, size, offset, 0UL, 0);
}
```
這個函式是用來找出對於指定的記憶體區域，第一個被設置的位，在呼叫 helper function `_find_next_bit` 前，判斷 `size` 是否為編譯時期常數且小於 `long` 的大小且非 0 ，也就是一個 `long` 的變數可以處理的範圍，則直接計算。
使用 bitmask `GENMASK(size - 1, offset)` 取得 `*addr` 所需範圍的值
若是該值為 0 則依照函式定義回傳 0 ，否則用 `__ffs` 找出第一個被設置的位
### `GENMASK` 於 `kvm_host.h` 的應用
這段程式碼位於 include/linux/kvm_host.h
```c
#define KVM_REQUEST_MASK GENMASK(7,0)
```
這裡的 request 是用來發送給 VCPU，依照 request's number 作出相應的處理，[KVM VCPU Requests](https://github.com/torvalds/linux/blob/master/Documentation/virt/kvm/vcpu-requests.rst) 提及了 request's number 只有低八位元，高位元則用於 flag ，若要將 request 用於 bitops 要搭配 `KVM_REQUEST_MASK` ，如下所示
```c
static inline void kvm_clear_request(int req, struct kvm_vcpu *vcpu)
{
clear_bit(req & KVM_REQUEST_MASK, (void *)&vcpu->requests);
}
```
這裡的 `req` 只保留 request's number 的低八位元。
值得注意的是一樣在 include/linux/kvm_host.h ，有幾處的值是寫成一般的形式，而不是用 `GENMASK` 或是 `BIT` 相關的巨集
```c
#define KVM_MEMSLOT_INVALID (1UL << 16)
#define KVM_PFN_ERR_MASK (0x7ffULL << 52)
#define KVM_PFN_ERR_NOSLOT_MASK (0xfffULL << 52)
#define KVM_PFN_NOSLOT (0x1ULL << 63)
#define KVM_MEM_MAX_NR_PAGES ((1UL << 31) - 1)
```
改寫如下
```c
#define KVM_MEMSLOT_INVALID BIT(16)
#define KVM_PFN_ERR_MASK GENMASK_ULL(62, 52)
#define KVM_PFN_ERR_NOSLOT_MASK GENMASK_ULL(63, 52)
#define KVM_PFN_NOSLOT BIT_ULL(63)
#define KVM_MEM_MAX_NR_PAGES (BIT(31) - 1)
```
---
## 測驗 2
將 `v` 對 4 個位元組進行向下對齊，所以是清空低兩位，保留其他位，可以用 `v & ~3` 來取得。
### Forward Declaration
在 include/linux/file.h ， `struct fd` 定義了 `struct file *` 的變數，但 file.h 只有 `struct file` 的宣告
```c
struct file;
struct fd {
struct file *file;
unsigned int flags;
};
```
`struct file` 的定義則是在 include/linux/fs.h
```c
struct file {
...
};
```
---
## 測驗 3
如果要將一數做位元反轉，可以先將該數看成左右兩半邊，先將兩半邊對調，在將兩半邊視為另一數分別做位元反轉。而這個位元反轉也可以將該半邊分成兩個更小的半邊，重複同樣的動作，一直做下去直到不能再分。
所以該段程式碼一開始是將左右 4 bits 對調，接下來將這兩個 4 bits 分成一半的兩兩 2 bits 對調 `0xCC` 二進位表示為 `0b11001100` 也就是左半邊 2 bits 的 bitmask ，所以另一半要的 bitmask 為 `0b00110011` 也就是 `0x33` 。依此類推 `0xAA` 二進位表示為 `0b10101010` ，因此另一半 bitmask 為 `0b01010101` 也就是 `0x55` 。
### Linux 核心的 bits reversing
在 include/linux/bitrev.h 有定義 bit reversing 相關的巨集，如下為與題目類似的實作
```c
#define __constant_bitrev8(x) \
({ \
u8 ___x = x; \
___x = (___x >> 4) | (___x << 4); \
___x = ((___x & (u8)0xCCU) >> 2) | ((___x & (u8)0x33U) << 2); \
___x = ((___x & (u8)0xAAU) >> 1) | ((___x & (u8)0x55U) << 1); \
___x; \
})
```
實際使用上是使用 `bitrev8(x)`
```c
#define bitrev8(x) \
({ \
u8 __x = x; \
__builtin_constant_p(__x) ? \
__constant_bitrev8(__x) : \
__bitrev8(__x) ; \
})
```
該巨集會先判斷 `x` 是否為編譯時期常數，若是則使用 `__constant_bitrev8(x)` 直接計算出反轉後的值，若不是則採用查表的方式。
在 include/linux/crc32.h 有一處使用到 bits reversing
```c
#define ether_crc(length, data) bitrev32(crc32_le(~0, data, length))
```
根據註釋這是用於計算 Ethernet 的冗餘校驗，又因為 Ethernet 是 big-endian 且傳遞順序為每個位元組的最低位開始，使用 `crc32_le` 產生 little-endian 的 crc32 的值，搭配 bits reversing，這樣結果才會正確， bits reversing 相當於將兩個 endian 互換再將位元組內的位元順序反轉。
---
## 測驗 4
對於一個 function-like macro
```c
#define identifier( parameters, ... ) replacement-list
#define identifier( ... ) replacement-list
```
`...` 可以接受任意數量的參數，在 replacement-list 以 `__VA_ARGS__` 表示，如以下巨集
```c
#define debug(format, ...) fprintf (stderr, format, __VA_ARGS__)
```
使用 `debug("error: %d %d", 0, 0)` 就會被替換為
```c
fprintf (stderr, "error: %d %d", 0, 0)
```
`__VA_ARGS__` 被展開為 `0, 0`
若參數的類型都相同，可以將其宣告為陣列，因而可以得知參數的數量以及利用索引存取參數，題目為類似的用法，在 replacement-list 使用以下的程式碼
```c
int array[] = {__VA_ARGS__};
int array_size = sizeof(array) / sizeof(int);
array[0]; // indexing
```
`foreach` 巨集用以走訪給定的參數，因此我們會需要一個變數 `i` 用來存目前存取到的值，以及一個索引 `_foreach_i` 。這段程式碼是用來初始化這兩個變數。
```c
(unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0);
```
迴圈的條件是 `_foreach_i` 小於給定值的數量。
```c
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)
```
`i` 每次迴圈結束會需要設成下一個值且 `_foreach_i` 會需要加一，由此可知 `EXP4` 為 `++_foreach_i` 。
```c
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
```
第二個巨集 `foreach_ptr` 是用來逐一走訪給定的指標範圍。
```c
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, NULL})[EXP5],
```
這裡也是同樣的道理所以 `EXP5` 為 `++_foreach_i` 。
`_foreach_no_nullval` 是用來確保 `_foreach_i` 不會超過指標的數量以及指標不得有 `NULL` 。
## indirect call
在 [include/linux/indirect_call_wrapper.h](https://github.com/torvalds/linux/blob/master/include/linux/indirect_call_wrapper.h) 有以下巨集
```c
#define INDIRECT_CALL_1(f, f1, ...) \
({ \
likely(f == f1) ? f1(__VA_ARGS__) : f(__VA_ARGS__); \
})
```
該巨集判斷函式指標 `f` 是否為內建函式 `f1` ，如果相同則直接呼叫內建函式， `__VA_ARGS__` 作為函式的參數傳入。
這樣做可以減少開啟 retpoline 後在呼叫內建函式的開銷， retpoline 是緩解 Spectre v2 的方法，詳情可見 [retpoline-a-branch-target-injection-mitigation](https://www.intel.com/content/dam/develop/external/us/en/documents/retpoline-a-branch-target-injection-mitigation.pdf?source=techstories.org)
Indirect function call 會被替換成下圖的程式碼
查看以下程式在 gcc 使用參數 `-mindirect-branch=thunk` 產生的組合語言
```c
void f1(void)
{
}
int main(void)
{
void (*f)() = f1;
f();
f1();
}
```
對於 `f()` 產生的程式碼為
```cpp
call __x86_indirect_thunk_rax
__x86_indirect_thunk_rax:
call .LIND1
.LIND0:
pause
lfence
jmp .LIND0
.LIND1:
mov QWORD PTR [rsp], rax
ret
```
而對於 `f1()` 產生的程式碼為
```cpp
call f1()
```
確實符合前述所說之 retpoline
---
## 測驗5
整段程式碼相當於以二進位的形式做長除法，重複以下動作，如果被除數減掉除數乘上某個數大於，就將商加上該數，然後被除數設為減掉後的結果，這裡的某數採用 2 的冪，所以相乘可以用位移來處理。
除此之外先將兩個有號數轉乘無號數，最後再補上正負號。
```c
while (dvd > (EXP6))
shift++;
```
這裡是要找出那個某數的最大可能值，所以 `EXP6` 是某數與除數相乘的結果，又因為是儲存位移的量， `EXP6` 為 `dvs << shift` 。
```c
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
```
`EXP7` 也就是前述的將被除數設成相減後的結果 `dvd -= dvs << shift` 。
## 改進
結果正負號的取得可以寫成 branch-less 。
```c
int signal = 1 - (dividend ^ divisor < 0) << 1;
```
`shift` 一開始的值可以直接用 `fls` 算出來。
```c
int shift = fls(dvd) - fls(dvs);
```
加速除數為 2 的冪時的計算。
```c
if(fls(divisor) == ffs(divisor))
return signal * (divided >> ffs(divisor) - 1);
```
約掉 2 的冪的公因數。
```c
int cd = min(ffs(dvd), ffs(dvs));
dvd >>= cd;
dvs >>= cd;
```
---
## 測驗6
程式運作邏輯如下，迭代存取任兩點的組合，根據斜率將該組合加入至 hashtable ，將垂直、水平、重複點做特例處理，最後統計最大值。因此 `EXP9` 是 `list_add(pn, &heads[hash])` 。
### 缺陷和改進
根據原本給的解答， `can_insert` 為
```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;
}
```
意思為要求加入的組合為同一直線，但實際上無法處理有平行線的情況，除此之外也不能處理 hash 碰撞的情況。
對於以下的輸入，在要插入`(1, 0),(2, 1)` 時因為已經有一個 `(0, 0), (1, 1)` 在，因為 `(1, 0)` 與 `(0, 0)` 不是同一個點， `return p1 == pn->p1` 會回傳 `false` ，而實際上對於兩平行線是後者點的數量較多，因此答案有誤。
```
(0, 0)
(1, 1)
(1, 0)
(2, 1)
(3, 2)
```
改進如下，將其改為以點和斜率表示唯一的直線，然後紀錄直線上點的數量。
```c
struct point_node {
int point;
int dx, dy;
int count;
struct list_head link;
};
```
以及加入了三個判斷， 第一個是 `max` 若大於等於點數量的一半一定是最大值
```c
if (max >= (pointsSize + 1) / 2)
return max;
```
另外一個則是存取至第 i 個點時，最大值只會是 `pointsSize - i` 因此 `max` 一定是最大值。
```c
if (max >= pointsSize - i)
return max;
```
以及當存取點 i 計算到點 j 時，最大值的上限為當前最大值加上未被統計的點的數量
```c
if(local_max + (pointsSize - j) <= max)
break;
```
### 針對記憶體開銷的改進
基於上述的改進，在計算下一個點時，前一個點所用的 hashtable 可不必保留，因此可以將已存在的節點重用於下一個點的計算。
也因此對於第 i 個點的 hashtable 至多需要 `pointsSize - i` 個節點，hashtable 的大小從原先的 `pointsSize * pointsSize / 2 + 133` 縮小到 `pointsSize * n` 。
判斷重用的程式如下，如果遇到節點儲存的點是不同的，代表可以重用
```c
for(pn = head; *pn; pn = &(*pn)->next) {
if (point == (*pn)->point) {
if(dx == (*pn)->dx && dy == (*pn)->dy) {
return ++(*pn)->count;
}
}
else {
(*pn)->point = point;
(*pn)->dx = dx;
(*pn)->dy = dy;
(*pn)->count = 2;
return 2;
}
}
```
統計 malloc 的次數，`pointsSize` 為 1000 時，修改前的使用了 499100 次，修改後的減少到 5962 次。
加入統計因為 hash 衝突導致的走訪次數，還有重用的次數
```
point_size: 10000 max: 25
malloc: 67947, collision: 23430327, hit: 0.003815, reuse: 0.994821, time: 9.673239
```
調整原本的 hash function
```c
int old_hash = dx * dy - 1333 * (dx + dy);
int new_hash = (dx * 31 + dy) * 0x61C88647;
```
走訪次數變為原本的 62%
```
point_size: 10000 max: 25
malloc: 76831, collision: 14675709, hit: 0.003817, reuse: 0.994641, time: 9.697280
```
儘管重用的比例已經很高，但還是有不可忽視多達 `pointsSize` 7.6 倍的節點數，原因在每次加入 hashtable 僅僅是檢查 hash 衝突的節點是否可重用，實際上節點最多只需要 `pointsSize - 1` 個。
因此引入了一個儲存可用節點的佇列
```c
static struct point_node * reuse_head = NULL;
static struct point_node * reuse_tail = NULL;
static int insert_point_node(struct table_head *head, int point, int dx, int dy)
{
...
if(reuse_head->point != point) {
*pn = reuse_head;
reuse_head = reuse_head->reuse_next;
reuse_tail = reuse_tail->reuse_next;
}
else {
*pn = (struct point_node *)malloc(sizeof(struct point_node));
reuse_tail->reuse_next = *pn;
(*pn)->reuse_next = reuse_head;
reuse_tail = *pn;
}
...
}
```
以及一個在 hashtable 的 head 加入一個變數判斷第 i 個點的節點是否已經加入
```c
struct table_head
{
int point;
struct point_node *head;
};
```
比較修改前後的資訊，修改前為
```
point_size: 10000 max: 31
malloc: 76683, collision: 14857871, time: 4.541836
memory usage: 2160392
```
修改後為
```
point_size: 10000 max: 31
malloc: 9933, collision: 14857871, time: 3.804567
memory usage: 637856
```
記憶體使用量降為原本的 29% ，效率提昇 19% ，且 malloc 次數有個上限在。
---
## 測驗 7
此題相當於要找出最高位的 1 的位置加一，使用二分搜尋法，先確定最高位在左半邊還是右半邊，若在左半邊，將其位移靠右對齊，再將同樣的方法套用在被分為一半的數。
`EXP10` 為要確定最高位是在 8 bits 的哪半邊，所以是 `m = (v > 0x3) << 1` 。
`EXP11` 則是將 `m = v > 0x1` 跟 `ret += m` 合併，所以是 `ret += v > 0x1` 。之所以用加的是因為 `ret` 一開始的值為 `v > 0`。
### Linux 核心的 ilog32
在 include/linux/log2.h
```c
#define ilog2(n) \
( \
__builtin_constant_p(n) ? \
((n) < 2 ? 0 : \
63 - __builtin_clzll(n)) : \
(sizeof(n) <= 4) ? \
__ilog2_u32(n) : \
__ilog2_u64(n) \
)
```
n 為 32 位元的情況下會呼叫 `__ilog2_u32(n)`
```c
static inline __attribute__((const))
int __ilog2_u32(u32 n)
{
return fls(n) - 1;
}
```
在 include/asm-generic/bitops/fls.h 提供了一個實作
```c
static __always_inline int fls(unsigned int x)
{
int r = 32;
if (!x)
return 0;
if (!(x & 0xffff0000u)) {
x <<= 16;
r -= 16;
}
if (!(x & 0xff000000u)) {
x <<= 8;
r -= 8;
}
if (!(x & 0xf0000000u)) {
x <<= 4;
r -= 4;
}
if (!(x & 0xc0000000u)) {
x <<= 2;
r -= 2;
}
if (!(x & 0x80000000u)) {
x <<= 1;
r -= 1;
}
return r;
}
```
### 針對無 ctz/clz 指令的常數時間複雜度 ilog 實作
求 ilog2 相當於將 fls 的結果減一， [Using de Bruijn Sequences to Index a 1 in a Computer Word](https://) 提出一個基於 de Bruijn 序列的方法求得 fls 或 ffs 。
#### de Bruijn 序列
對於一個 B(k, n) 的 [de Bruijn 序列](https://en.wikipedia.org/wiki/De_Bruijn_sequence)，序列的元素為 k 種，且長度為 n 的子序列的每一種組合，剛好在 de Bruijn 序列中只出現一次，如以下的一個 B(2, 3) de Bruijn 序列
${00010111}$
其中長度為3的子序列的每一種組合(000, 001, 010...)都只在其中出現一次。
${(000)10111}$
${0(001)0111}$
${000(101)11}$
${0001(011)1}$
${00010(111)}$
${0)00101(11}$
${00)01011(1}$
共 ${2^3=8}$ 種。
#### Hashing
另外一個想法是 find last set 實際上我們只需要最高位的 1 ，因此我們可以先將該位分離出來，如 `00101101` 只需要保留 `00100000` ，這個值會是 2 的冪。
這樣的處理將所有 n 位元的數映射到 n 個數，也就是 ${2^0, 2^1, ..., 2^{n-1} }$，接下來要找到一個 hash function，將這 n 個數一對一映射到 0 ~ (n - 1) ，就可查表得到 fls 值。
已知將任一數乘上 2 的冪相當於向左位移，這裡要利用 de Bruijn 序列，若 n 為 ${2^k}$ ，將這些 2 的冪乘上 de Bruijn 序列，我們可以在固定位置的 k 位取得一對一映射的結果。
```c
(x * 0x06EB14F9U) >> 27
```
其中 `0x06EB14F9U` 為其中一個 B(2, 5) de Bruijn 序列， `x` 為任意 32 位元的數分離出的最高位， `>>27` 保留相乘後的最高 5 位，因為 de Bruijn 序列的性質所以結果與 `x` 是一對一映射。
#### 實作
修改自[Finding least- or most-significant set bit in a word](https://en.wikipedia.org/wiki/De_Bruijn_sequence#Finding_least-_or_most-significant_set_bit_in_a_word) ，先分離出最高位的 1 ，其中的運算可以將最高位以下的位全部填為 1 ，如 `01010010` 得到 `01111111` ，然後 `x - (x >> 1)`將最高位以下的位清除，這裡有一個替代作法是使用 `x + 1` ，得到結果會是最高位分離後向左位移一位，只要在建表時調整順序即可。
```c
static inline uint32_t keepHighestBit(uint32_t x)
{
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return x - (x >> 1);
}
```
以下為前面提到之運算與查表，因為 ilog2 要將 fls 的結果減一，可以直接將表中的值減一得到 ilog2 的結果。
```c
static inline uint8_t ilog2(uint32_t x)
{
static const uint8_t BitPositionLookup[32] = { // hash table
0, 1, 16, 2, 29, 17, 3, 22, 30, 20, 18, 11, 13, 4, 7, 23,
31, 15, 28, 21, 19, 10, 12, 6, 14, 27, 9, 5, 26, 8, 25, 24,
};
return BitPositionLookup[(keepHighestBit(x) * 0x06EB14F9U) >> 27];
}
```
---
## 測驗8
使用指向指標的指標走訪二元搜尋樹，若是要往左走，也就是要將走訪的指標指向指標所指的節點的 `left` ，反之，若是要向右走。就要將走訪的指標指向指標所指的節點的 `right` 。
因此 `EXP12` 為 `p = &(*p)->left` ， `EXP13` 為 `p = &(*p)->right` 。
找到節點後接下來要移除它，如果左右節點其一不存在，就將另一節點替補即可，若兩個都存在，則找出左子樹最大節點或右子樹最小節點替換，因此 `EXP14` 為 `&(*r)->left` ，也就是找出右子樹的最大節點。
### 改進
`struct tnode` 的結構如下， `child[0]` 為 left child ， `child[1]` 為 right child 。
```c
struct tnode {
int data;
struct tnode *child[2];
};
```
`remove_data` 做了兩個修改，一個在走訪要被刪除的節點，利用左右子節點的 indexing 省去一個分支。
```c
while (*p != 0 && (*p)->data != d) {
p = &(*p)->child[d > (*p)->data];
}
```
另一個在刪除找到的節點時，將子節點若有 `NULL` 的兩個分支合併為一個。
```c
if (q->child[0] && q->child[1]) {
tnode **r = &q->child[1];
while ((*r)->child[0])
r = &(*r)->child[0];
q->data = (*r)->data;
q = *r;
*r = q->child[1];
}
else {
*p = (uintptr_t)q->child[0] | (uintptr_t)q->child[1];
}
```
修改後與原始的寫法的比較如下，約提升 4%
## 測驗9
`x` 加上 `MAX_ALIGNMENT - 1` 會在 `MAX_ALIGNMENT` 的位加一，使用 `~(MAX_ALIGNMENT - 1)` 的 bitmask 將 `MAX_ALIGNMENT`以下的位清除。
### ROUND_DOWN
```c
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
((x) & ~(MAX_ALIGNMENT - 1))
```
## 測驗10
考慮到 a / b = x.n ，若將此數加上 0.5 後，整數部分為原本 x.n 最接近的數，加上 0.5 相當於 (a + b / 2) / b 。
當除數與被除數為有號數且被除數小於零時，會是 `((SSS) / (__d))` ，因此要減掉 0.5 所以 `SSS` 為 `(__x) - ((__d) >> 1)` ， `RRR` 是加上 0.5 所以是 `(__x) + ((__d) >> 1)` 。
## 測驗11
Sign in with Wallet
Connect another wallet