# 2025q1 Homework2(quiz1+2)
**contributed by <`leonnig`>**
## Quiz 1
[第一周測驗題](https://hackmd.io/@sysprog/linux2025-quiz1)
### 測驗1
```c
static inline void list_insert_before(list_t *l, list__item_t *before, list_item_t *item)
{
list_item_t **p;
for (p = AAAA; *p != BBBB; p = CCCC)
;
*p = item;
DDDD = before;
}
```
此 function 的功能是將`item`插入到 list 中 `before`指向的節點的位置。
如果要達成這個功能，勢必要從頭 traverse 過 list 以找到該插入的位置，可以從程式碼中發現，宣告了一個`p` pointer to pointer 去做 traverse，`p`一開始要指向的要是一個指標，並且是從開頭的位置，所以`AAAA`要是整個串列的起點，也就是 `&l->head`。
而中止條件`*p != BBBB`，可以看出對`p`做 value of，又功能的要求是要插入到`before`的位置，因此可以判斷當`*p`指向的不為`before`時都要繼續前進，`BBBB` = `before`。
每次前進時，指標的指標`p`會指向下一個節點中的`next`的位置，這樣在搜尋時可以利用 address of 直接取得要插入的目標位置，`CCCC` = `&(*p)->next`。
找到插入的位置後，`*p = item`就是將`before`的前一點的`next`指向`item`，最後必須將`item`與後面的list連接起來，所以`DDDD` = `item->next`。
#### 延伸問題: 解釋程式碼運作原理
其實整段程式碼就是在對 list 的一些操作做測試。
先來說明以下 function 功能
**my_assert**
```c
#define my_assert(test, message) \
do { \
if (!(test)) \
return message; \
} while (0)
```
這段程式在判斷給定的 test 是否通過，若未通過則回傳一段訊息通知。
**list_reset**
```c
static list_t *list_reset(void)
{
for (size_t i = 0; i < N; i++) {
items[i].value = i;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
```
這段程式將一條 list 內的連接都斷開，也就是將`list_item_t`的`next`都設為 NULL，head也設為 NULL。
而在 **test_list** 則是最主要做測試的部分，其中又分為3段測試。
首先對 list 做 reset，然後去測試看 list 是否有被正常 reset 成功。
```c
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
```
並且從 `l->head` 插入 N 個數，測試從開頭插入的操作。
並且插入方式如下:
```c
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
```
可以發現他的第二個 argement 給的是`l.head`，代表說他的迴圈會馬上停在第一個位置，而`item`插入的位置就都會在最前面，也就是數字越大的節點會在越前面。
----
----
然後再去檢查插入完成後的 list 大小是否為 N，並且逐一檢查每個節點的 vlaue 是否有符合順序。
```c
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k--;
cur = cur->next;
}
```
再來是測試從 list 尾部插入的操作
終止條件改成了`NULL`，也就是會往後找到最後一個節點的`next`為止，將`item`插入。
所以數字越大的節點會出現在越後方。
```c
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
```
然後執行跟前面一樣的測試。
最後則是做 list 的 reset，完成後再做從 list 尾部的插入。
補完 `list_size` 功能
```c
static int list_size(list_t *l)
{
if (!l->head)
return 0;
int cnt = 0;
list_item_t *cur = l->head;
while (cur) {
cur = cur->next;
cnt++;
}
return cnt;
}
```
#### 延伸問題: 在現有的程式碼基礎上，撰寫合併排序操作
首先撰寫 merge 的操作
```c
list_item_t *mergeTwo(list_item_t *L1, list_item_t *L2)
{
list_item_t *head;
list_item_t **ptr = &head;
for (; L1 && L2; ptr = &(*ptr)->next) {
if (L1->value < L2->value) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
}
*ptr = L1 ? L1 : L2;
return head;
}
```
再來遞迴做 divide
```c
list_item_t *mergesort(list_item_t *head)
{
if (!head->next || !head)
return head;
list_item_t *slow = head;
for (const list_item_t *fast = slow->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
list_item_t *new_l = malloc(sizeof(list_item_t));
new_l = slow->next;
slow->next = NULL;
list_item_t *left = mergesort(head), *right = mergesort(new_l);
mergeTwo(left, right);
}
```
加入測試
```c
static list_t *list_reset_random(void)
{
srand(time(NULL));
for (size_t i = 0; i < N; i++) {
size_t num = (size_t) (rand() % 100 + 1);
items[i].value = num;
items[i].next = NULL;
}
l.head = NULL;
return &l;
}
static char *test_list(void)
{
/* Test inserting at the beginning */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, l.head, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
size_t k = N - 1;
list_item_t *cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k--;
cur = cur->next;
}
/* Test inserting at the end */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "Final list size should be N");
k = 0;
cur = l.head;
while (cur) {
my_assert(cur->value == k, "Unexpected list item value");
k++;
cur = cur->next;
}
/* Reset the list and insert elements in order (i.e. at the end) */
list_reset();
my_assert(list_size(&l) == 0, "Initial list size is expected to be zero.");
for (size_t i = 0; i < N; i++)
list_insert_before(&l, NULL, &items[i]);
my_assert(list_size(&l) == N, "list size should be N");
list_reset();
return NULL;
}
```
```
---=[ List tests
Before sorting: 99 92 61 11 58 54 16 83 94 11
After sorting: 11 11 16 54 58 61 83 92 94 99
ALL TESTS PASSED
Tests run: 2
```
### 測驗2
```c
/* Find the in-order predecessor:
* This is the rightmost node in the left subtree.
*/
block_t **pred_ptr = &(*node_ptr)->l;
while (EEEE)
pred_ptr = FFFF;
```
根據註解，這段程式碼的目的是要找出二元搜尋樹中的 in-order predecessor ，而註解有說明了是要左子樹中最右邊的節點。
所以會一直往右子樹的節點去搜尋，直到某個節點的右子樹為 NULL
所以`EEEE` = `(*pred_ptr)->r`
而這就代表該節點為左子樹中最右邊的節點
`FFFF` = `&(*pred_ptr)->r`
#### 延伸問題: 解釋程式碼運作原理，並嘗試補完程式碼，使其可獨立執行。
根據程式中的敘述可以得知，目的是想要實作一個`memory allocator`，並且以二元搜尋樹的資料結構去存放那些可用、閒置的記憶體區塊。
首先來分析一下`remove_free_tree`，根據敘述，我認為此函式的功能主要是移除那些準備要被使用或配置的記憶體區塊，
使用`find_free_tree`先找出要拿來使用的區塊
```c
block_t **node_ptr = find_free_tree(root, target);
```
`node_ptr`為指標的指標，是指向存放`target`的指標變數，也就是某個父節點的`l`或`r`。
而根據找的目標節點狀態不同，也會有不同的處理方式。
**1. 當要移除的節點有左子節點及右子節點時:**
這時不能直接刪除，需要找到一個替代的節點，就是目標節點的左子樹中最右邊的節點。
```C
block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
pred_ptr = &(*pred_ptr)->r;
```
而這時又分為兩種情況
當替代的節點就是欲移除的節點的左子節點時:
先用`old_right`指標指向欲移除節點的右子節點，在對`node_ptr`做 dereference 得到指向目標的指標，在將其指向替代節點，再將新的目標節點的右子節點指標指向`old_right`，維持二元搜尋樹的結構。
---
替代的節點位於左子樹的深處:
必須把替代節點先移除原本的位置，所以這邊需要呼叫`remove_free_tree(&old_left, *pred_ptr)`移除替代節點，再將其接回正確的位置。 這邊利用`pred_node`指標來保存被移除的替代節點。
```c
/* Remove the predecessor from its original location. */
remove_free_tree(&old_left, *pred_ptr);
/* Replace the target node with the predecessor. */
*node_ptr = pred_node;
(*node_ptr)->l = old_left;
(*node_ptr)->r = old_right;
assert(*node_ptr != (*node_ptr)->l);
assert(*node_ptr != (*node_ptr)->r);
```
---
---
**2. 當要移除的節點只有左子節點或右子節點時(只有一個子節點):**
判斷移除節點的子節點是左還是右，將那個子節點連結回去原本的二元樹。
```c
block_t *child = ((*node_ptr)->l) ? (*node_ptr)->l : (*node_ptr)->r;
*node_ptr = child;
```
**3. 當要移除的節點沒有任何子節點時:**
直接將指向`target`的指標設為 NULL ，段開連接。
將`target`移除後，要將目標節點指向右子樹和指向左子樹的指標設為 NULL，避免 dangling reference。
#### 補完 `find_free_tree` 及 `find_predecessor_free_tree`
`find_free_tree` 的功能是要找出目標節點:
```c
block_t **find_free_tree(block_t **root, block_t *target)
{
if (!*root)
return NULL;
if (*root == target){
printf("Find target, size is %zu\n", target->size);
return root;
}
block_t *node = *root;
if (target->size > node->size){
return find_free_tree(&node->r, target);
}
else
return find_free_tree(&node->l, target);
}
```
`find_predecessor_free_tree`是要找出替帶的節點(目標節點的左子樹中的最大節點)
```c
block_t *find_predecessor_free_tree(block_t **root, block_t *node)
{
block_t *pre = node;
if(!pre)
return NULL;
if (pre->l)
pre = pre->l;
while(pre->r){
pre = pre->r;
}
printf("%zu's pred is %zu\n", node->size, pre->size);
return pre;
}
```
為了測試功能，在補上一些函式
```c
block_t *create_tree(size_t size)
{
block_t *node = malloc(sizeof(block_t));
node->size = size;
return node;
}
void free_tree(block_t *root)
{
if (!root)
return;
free_tree(root->r);
free_tree(root->l);
free(root);
}
void insert(block_t **root, block_t *new_node)
{
if(!*root)
return ;
block_t **node = root;
while (*node){
if (new_node->size > (*node)->size)
node = &(*node)->r;
else
node = &(*node)->l;
}
*node = new_node;
}
void show_tree(block_t *root, int space)
{
if (!root)
return;
const int SPACING = 5;
show_tree(root->r, space + SPACING);
for (int i = 0; i < space; i++)
printf(" ");
printf("%zu\n", root->size);
show_tree(root->l, space + SPACING);
}
```
測試功能
```c
int main()
{
block_t *node = create_tree(10);
root = &node;
block_t *node_1 = malloc(sizeof(block_t));
node_1->size = 5;
insert(root, node_1);
block_t *node_2 = malloc(sizeof(block_t));
node_2->size = 15;
insert(root, node_2);
block_t *node_3 = malloc(sizeof(block_t));
node_3->size = 7;
insert(root, node_3);
block_t *node_4 = malloc(sizeof(block_t));
node_4->size = 17;
insert(root, node_4);
block_t *node_5 = malloc(sizeof(block_t));
node_5->size = 13;
insert(root, node_5);
block_t *node_6 = malloc(sizeof(block_t));
node_6->size = 12;
insert(root, node_6);
block_t *node_7 = malloc(sizeof(block_t));
node_7->size = 14;
insert(root, node_7);
show_tree(*root, 0);
printf("------------------------\n");
remove_free_tree(root, node_5);
show_tree(*root, 0);
free_tree(*root);
*root = NULL;
}
```
#### 延伸問題: 參閱 [memory-allocators](https://github.com/mtrebi/memory-allocators)，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現
>Todo
### 測驗3
```c
static void rebuild_list_link(struct list_head *head)
{
if (!head)
return;
struct list_head *node, *prev;
prev = head;
node = head->next;
while (node) {
node->prev = prev;
prev = node;
node = node->next;
}
prev->next = head;
/* GGGG */;
}
```
這是一個將雙向鏈結串列節點的 `prev` 指標給重建的函式，中間的 `while` 迴圈就是在遍歷並重建鏈結，迴圈結束後，`prev` 會指向串列的最後一個節點，再來則是要將 `head` 和 `prev` 給連接，所以 `GGGG` = `head->prev=prev`。
---
以下是quick sort的主程式
```c
{
int n = list_length(list);
int value;
int i = 0;
int max_level = 2 * n;
struct list_head *begin[max_level];
struct list_head *result = NULL, *left = NULL, *right = NULL;
begin[0] = list->next;
list->prev->next = NULL;
while (i >= 0) {
struct list_head *L = begin[i], *R = list_tail(begin[i]);
if (L != R) {
struct list_head *pivot = L;
value = /* HHHH */
struct list_head *p = pivot->next;
pivot->next = NULL; /* break the list */
while (p) {
struct list_head *n = p;
p = p->next;
int n_value = /* IIII */;
if (n_value > value) {
n->next = right;
right = n;
} else {
n->next = left;
left = n;
}
}
begin[i] = left;
begin[i + 1] = /* JJJJ */;
begin[i + 2] = /* KKKK */;
left = right = NULL;
i += 2;
} else {
if (L) {
L->next = result;
result = L;
}
i--;
}
}
list->next = result;
rebuild_list_link(list);
}
```
在最外層的 `while` 迴圈內做的事情就跟一般的 quick sort 很像，決定 pivot 後，去跟 pivot 的值比大小，並將區分出來大於該值的放進 `right` 內，而小於該值的放進 `left` 內，而迴圈內的 value 代表的正是 pivot 的值，但沒辦法直接由 `list_head` 取得 `value`，所以應當需要利用 linux 風格的 API 來取得，因此 `HHHH` = `list_entry(pivot,node_t,list)->value` ，而在 `while(p)` 內 `n` ，正是要去跟 `pivot` 比較的，所以 `IIII` = `list_entry(n,node_t,list)->value`，而根據題目前段的描述:
> 指標 p 會一直往右走，將大於 pivot 的節點存入 right ， 小於的存入 left
接著可得到三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2
可以發現正是對應到 `begin[i]` = `left` ，`begin[i+1]` = `JJJJ` = `pivot` , `begin[i+1]` = `KKKK` = `right`。
#### 延伸問題: 解釋上述程式碼運作原理
此程式碼是有別於一般採用遞迴方式的 quick sort，並不是採用 swap 的方式，一開始先和 `pivot` 比較，然後將其他節點分到 left 和 right ，並且三組分割 left pivot right，其對應的分割編號分別為 i i+1 i+2，而再來就是這步 `i += 2` ， 這代表說我下次的 i 會為 2 ， 所以我再次進行分割的時候，會先從 right 指向的那部份開始做，可以想為先從大的那條開始做排序，一開始其實看不懂這個程式碼為甚麼最後可以排序成功，直到我親手下去帶數字一步步 trace 才發現，正是因為 `i += 2`，所以我優先處理的一定是比較大的節點，所以當分割到只剩兩個單獨的節點(`begin[i] 內剩一個節點`)的時候，`L` 會指向較大的那個節點，這時又因為不滿足 `if (L != R) `，而執行以下程式碼:
```c
if (L) {
L->next = result;
result = L;
}
```
所以大的節點會優先被加入 `result` 內，而這樣依序加入剩下的節點，已達成由小到大排序，最後再將串列內的節點的 `prev` 連接起來即可完成。
示意範例:
做完第一次分割後
---
---
以 5 ,4 來示範排序 , **i = 2**
---
---
---
---
**i = 4**, ` struct list_head *L = begin[4] = NULL = *R = list_tail(begin[4])`, `i--;`
**i = 3**
---
**i = 2**
---
即完成4 ,5 的排序，後面也是一樣的步驟。
#### 延伸問題: 研讀〈[A comparative study of linked list sorting algorithms](https://dl.acm.org/doi/pdf/10.1145/225890.225893)〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作
> **Todo**
## Quiz 2
[第二周測驗題](https://hackmd.io/@sysprog/linux2025-quiz2)
### 測驗1
題目為 linked-list 版本的 quicksort
首先宣告在快速排序中會用到的
```c
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
```
`list_less` 和 `list_greater` 用來放置 list 中小於和大於 `pivot` 的節點。
```c
pivot = AAAA(head, struct listitem, list);
BBBB(&pivot->list);
```
這邊的 quicksort 是使用 list 的第一個節點作為 `pivot`，但因為我們要取的第一個節點實際上是 `head->next` ，我們可以用到一個方便的 macro 來幫我們取到串列中的第一個節點的結構體，`AAAA` = `list_first_entry`。
再來為了後續在做比較時遍歷的方遍，將 `pivot` 從原串列中先移除，所以`BBBB` = `list_del`。
---
```c
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
CCCC(&item->list, &list_greater);
}
```
再來就是要進行 quicksort 中的比較環節，要遍歷串列中的節點，跟 `pivot` 比較大小，小於 `pivot` 則使用 `list_move_tail` 將該節點移動到 `list_less` 的尾部，反之則移動到 `list_greater` 的尾部，所以 `CCCC` = `list_move_tail`。
節點都分類完之後，在各自遞迴下去排序
```c
list_quicksort(&list_less);
list_quicksort(&list_greater);
```
___
```c
DDDD(&pivot->list, head);
EEEE(&list_less, head);
FFFF(&list_greater, head);
```
最後各自排序完之後，要加入到原本的 `head` 之中，那首先要先加入 `pivot`，而因為 `pivot->list` 只有自己本身一個節點，所以直接將他加入進去即可，`DDDD` = `list_add`。
加入後應該是 `head->pivot` 的結構，那下一個要加入的是 `list_less`，必須得在 `pivot` 的前方，並且 `list_less` 可能會有負數個節點，所以 `EEEE` = `list_splice`。
這時 `head->[list_less]->pivot`，最後則是要將 `list_greater` 加入，由於其內的節點都大於 `pivot`，並且可能有負數個節點，所以 `FFFF` = `list_splice_tail`，完成排序，`head->[list_less]->pivot->[list_greater]`。
#### 延伸問題: 改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting
首先看到以下程式碼
```c
static inline uint8_t getnum(void)
{
static uint16_t s1 = UINT16_C(2);
static uint16_t s2 = UINT16_C(1);
static uint16_t s3 = UINT16_C(1);
s1 *= UINT16_C(171);
s1 %= UINT16_C(30269);
s2 *= UINT16_C(172);
s2 %= UINT16_C(30307);
s3 *= UINT16_C(170);
s3 %= UINT16_C(30323);
return s1 ^ s2 ^ s3;
}
```
[UINT16_C](https://www.qnx.com/developers/docs/6.4.1/dinkum_en/c99/stdint.html#UINT16_C) : 將常數轉換為 uint16_t 的資料型態。
可以看到原本的 shuffle
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = 0; i < len; i++) {
/* WARNING biased shuffling */
uint16_t j = get_unsigned16() % (i + 1);
operations[i] = operations[j];
operations[j] = i;
}
}
```
在 `operations[j] = i;` 這行會導致 i 寫進陣列中，覆蓋掉原本的資料，可以將其改為 `Fisher-Yates` 的洗牌方式。
```c
static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
for (uint16_t i = len - 1; i > 0; i--) {
uint16_t j = get_unsigned16() % (i + 1);
uint16_t tmp = operations[i];
operations[i] = operations[j];
operations[j] = tmp;
}
}
```
---
為何將 list_for_each_entry_safe 建構的迴圈中的 list_move_tail 換為 list_move，會造成 unstable ?
因為如果換成 `list_move` ，那要被移動的節點都會加入到另一條串列的前面，所以原本順序是 1 -> 1* 會變成 1* -> 1，又因為是必較的條件是 `<0` 而不是 `<=0`，所以兩個一樣大小的節點在比較時也不會還原成原來的順序。
---
#### 延伸問題: 將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋
> **Todo**
---
### 測驗2
實作一個遞迴版本的 count leading zero
```c
static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};
unsigned clz2(uint32_t x, int c)
{
if (!x && !c)
return 32;
uint32_t upper = (x >> (16 >> c));
uint32_t lower = (x & (0xFFFF >> mask[c]));
if (c == JJJJ)
return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}
```
這邊基本上就是每次將輸入進來的 bits 數對半切，然後再去判斷切出來的左半邊(也就是 upper )的部分是否為0，因為 clz 目的是要計算從最大位元(leading)開始往右邊計數，直到出現 1 為止，中間出現了幾個 0，那如果已知切出來左半邊為 0，代表第一個 1 一定出現在右半邊，所以就把右半邊拿來做下一輪的遞迴，反之如果左半邊不為 0 ，那麼就代表第一個 1 肯定在左半部，所以就拿左半部來遞迴下去，所以可以看到最後一行的回傳，就是在進行我上面的描述，若 `upper` 不為 0， ``` return clz2(upper, c + 1) ```，至於為何 c 要加1，等等在解釋，所以反之，則遞迴右半部( lower )，除此之外還要加上前面 upper 的 bits 數(代表左半邊有幾個 0 也要算進去)，所以 `return (16 >> (c)) + clz2(lower, c + LLLL);`， `LLLL` = 1，c 是去紀錄每一次遞迴應該要對半切的位置，所以她每次回傳時都要加 1 ，代表下一輪輸入的位元數總共要對半切幾次。
再來我們看到他裡面到底做了甚麼，`uint32_t upper = (x >> (16 >> c));`，這句是要取到左半邊的位置，又因為 c 為慢慢增加，所以這個 16 會慢慢變小，也對應取到左邊的 bits 會越來越小，16 -> 8 -> 4 -> 2，再來是右半邊 `uint32_t lower = (x & (0xFFFF >> mask[c]));`，因為是要取到右半邊，所以這邊用了 0xFFFF 搭被往右 shift 的方式，來跟 x 做 and ，這樣就能取到右半邊的值了，這時候就可以來探討這個 `mask[c]`了。
可以先觀察一下這個 `mask[] = {0, 8, 12, GGGG};`，按照這個順序去取 lower，當 c=0 時，lower 可以取到原本 32 bits 輸入的一半，再來當 c=1 時，mask 為8，也就是 0xFFFF 往右 shift 8 bits，剩下 `1111 1111`，也就是原本 16 bits 的一半，再來當 c=3 時，mask 為 12，多右移了 4bits，從原本的 8 bits 在切一半，剩下 `1111`，而最後一次切割，也就是取到剩 2 個 bit 的時候，所以我們 mask 的位元數要再多2，所以 `GGGG` = `14`。
而當最後剩下 2 個位元時，也就是 c=3 時，我們除了前面加總起來 0 的數量，剩下最後的 2 個位元也要去計算 clz ，但因為剩兩個位元，所以可以直接地去判斷剩下的4種位元組合，其中只有 `00` 和 `01` 會有 leading zero，這個 `magic[] = {HHHH, 1, 0, IIII};` 代表的是 {0,1,2,3} 所對應的 leading zero 數，所以 `HHHH` = `2`, `IIII` = `0`。
而最後若 upper 為 0，則計算右半部時也要加上左半部的 2 個 0，所以 `kkkk` = `2`。
___
再來將其應用到開平方根
```c
uint64_t sqrti(uint64_t x)
{
uint64_t m, y = 0;
if (x <= 1)
return x;
int total_bits = 64;
/* clz64(x) returns the count of leading zeros in x.
* (total_bits - 1 - clz64(x)) gives the index of the highest set bit.
* Rounding that index down to an even number ensures our starting m is a
* power of 4.
*/
int shift = (total_bits - 1 - clz64(x)) & MMMM;
m = 1ULL << shift;
while (m) {
uint64_t b = y + m;
y >>= NNNN;
if (x >= b) {
x -= b;
y += m;
}
m >>= PPPP;
}
return y;
}
```
這邊的開平方根實作是參考使用 **Digit-by-digit Method** ，而在 linux kernel 的原始程式碼中也有使用到此技巧 [lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/master/lib/math/int_sqrt.c) ， 其核心精神是利用二進位的系統去做逼近，證明和推倒過程可參考 [Digit-by-digit Method](https://hackmd.io/l4--gpsZQBiEI5LKS1lDvg#%E6%AA%A2%E8%A8%8E%E7%AC%AC%E4%BA%8C%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)，裡面舉例中提到一個重要的逼近判斷:
$P_m=
\begin{cases}
P_{m+1}+2^{m}, &\text{if }P_m^2 \leq N^2,\\
P_{m+1}, &\text{otherwise.}
\end{cases}$
它的作法其實就像我從我最高的位元開始代入去測試，先看到這行，$P_{m+1}=a_n+a_{n-1}+\dots+a_{m+2}+a_{m+1}$，在例子中 $N^2 = 10$，那我知道 $(10)_2 = (1010)_2$，最高位元 $b_3$ 從 $m=3$ 開始，所以帶回前面，$P_3 = a_3，P_2 = a_3 + a_2,....$，在根據我們的判斷開始逐位元測試，看這個位元帶入不是有小於我們的 $N^2$ ， 若沒有，就代表太大了，還需要在往後做逼近，所以 $N^2=(10)_{10}=(1010)_2=(b_3\times2^3+b_1\times 2^1)$，從最高位開始，依據 $P_m=P_{m+1}+a_{m}=P_{m+1}+b_{m}\times 2^{m}$，$P_3 = P_4 + a_3$，但最高位為 3 ，所以忽略 $P_4$，$P_3 = a_3 = b_3 \times 2^3$，又$P_3^2 =a_3^2$，所以 $P_3^2 = (2^3)^2 = 64$，而 $64 > 10$，所以需要在往下逼近，直到 $m=1$，$P_1^2 = (a_3+a_2+a_1)^2 = (2^1)^2 = 4 < 10 =N^2$，代表說 $P_3$ 是小於 $N^2$ 的，但前面說到了是要逼近，所以說既然都小於了，那勢必要在加上後面的位元看能否更逼近，最後得到，$N=P_0= a_1 + a_0 = 2^1+2^0= 3$，這就是這個演算法的核心精神。
文中裡面提到 $X_m=N^2-Y_m$ 為差值表實際值與逼近值的誤差，所以 $Y_m$ 為逼近值，也就是我們要求的，而參考文中的推導，可以得出 $Y_m =
\begin{cases}
c_m+d_m, &\text{ if }a_m =2^m, \\
0, &\text{ if } a_m = 0.
\end{cases}$
又 可以找到迭帶關係可以找到迭代關係 $c_{m-1} =
\begin{cases}
c_m/2 +d_m, &\text{ if } a_m\neq 0, \\
c_m/2, &\text{ if } a_m = 0.
\end{cases}$ 和
$d_{m-1} = d_m/4$，題目中的程式其實就是在做這件事。
註解中有說到
> Rounding that index down to an even number ensures our starting m is a power of 4.
因此找到 index of the highest set bit ，並且要將它向下取偶數，可以跟 -1 (xxx1111110) 去做 and 運算即可達成，所以 `MMMM` = `~1`，而根據上面的迭代， y 就相當於 $c_m$ ， 每次要除以2，所以 `NNNN` = `1`，往右位移來達到除以2的效果，而 m 則相當於 $d_m$，每次迭代都除以4，所以 `PPPP` = `2`。
#### 延伸問題: 解釋上述程式碼，並探討擴充為 $\lceil \sqrt{x}) \rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作
可以發現，在迴圈中，若 X 是完全平方數，則在最後跳出迴圈的時候，X 應該會剛好為 0，所以其實只需要在最後判斷說，X 最後的值是否等於 0，若否的話則代表有與真實值的誤差 (非完全平方數)，則讓它加上 1，以下更改一下回傳值:
```c
return (x == 0) ? y : y + 1;
```
參考執行結果：
- 輸入: 63，得到 8
- 輸入: 37，得到 7
#### 延伸問題: 參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly
> **TODO**
#### 延伸問題: 參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能
> **TODO**
---
### 測驗3
`find_key` 函式目的為在 hashmap 中找到指定的 `key` 的 `hash_key` 結構體並回傳。
```c
static struct hash_key *find_key(map_t *map, int key)
{
struct hlist_head *head = &(map->ht)[hash(key, AAAA)];
for (struct hlist_node *p = head->first; p; p = p->next) {
struct hash_key *kn = container_of(p, struct hash_key, node);
if (kn->key == key)
return kn;
}
return NULL;
}
void *map_get(map_t *map, int key)
{
struct hash_key *kn = find_key(map, key);
return kn ? kn->data : NULL;
}
```
而要找出對應的 `key`，可以觀察一下程式碼，推測它應該是需要透過雜湊函數去找到 `key` 值對應的 index，而我們可以根據題目中 hashfunction 的定義:
```c
#define GOLDEN_RATIO_32 0x61C88647
static inline unsigned int hash(unsigned int val, unsigned int bits)
{
/* High bits are more random, so use them. */
return (val * GOLDEN_RATIO_32) >> (32 - bits);
}
```
可以發現它是透過 bit-shifting 的方式去實作 Multiplication Method，詳細可以參考 [Linux 核心的雜湊函數](https://hackmd.io/@sysprog/linux-hashtable#Linux-%E6%A0%B8%E5%BF%83%E7%9A%84%E9%9B%9C%E6%B9%8A%E5%87%BD%E6%95%B8)，而這個函數就會需要 `bits`，這個參數代表的意義就是 $2^{bits}$，也就是 bucket 數量，所以 `AAAA` = `map->bits`。
再來是新增的操作
```c
void map_add(map_t *map, int key, void *data)
{
struct hash_key *kn = find_key(map, key);
if (kn)
return;
kn = malloc(sizeof(struct hash_key));
kn->key = key, kn->data = data;
struct hlist_head *h = &map->ht[hash(key, BBBB)];
struct hlist_node *n = &kn->node, *first = h->first;
n->next = first;
if (first)
CCCC = &n->next;
h->first = n;
DDDD = &h->first;
}
```
新增的方式是先使用 `find_key` 找出 key 對應的 index 是在哪個 bucket，如果有找到，則直接返回，不用新增了，否則的話，就需要自行新增到正確位置。
那一樣需要先利用雜湊函數去尋找應該放入的 bucket，方法同上，所以 `BBBB` = `map->bits`，並且使用 `h` 指向找到的 `hlist_head`。
接下來，將新的 key 插入到雙向鏈結串列的前方，而這個新的 key 我們用 `n` 指著，我們讓 `n` 的 next 指向 first ，也就是原本串列中的第一個節點，並且也要讓第一個節點的 `pprev` 指向 `&n->next`，所以 `CCCC` = `first->pprev`，這時 `n` 已經插入並成為串列中第一個節點，所以我們要將 `h->first` 改為指向 `n`，而 `n->pprev` 也要指向 `&h->first`，`DDDD` = `n->pprev`。
再來是刪除
```c
void map_deinit(map_t *map)
{
if (!map)
return;
for (int i = 0; i < MAP_HASH_SIZE(map->bits); i++) {
struct hlist_head *head = &map->ht[i];
for (struct hlist_node *p = head->first; p;) {
struct hash_key *kn = container_of(p, struct hash_key, node);
struct hlist_node *n = p;
p = p->next;
if (!n->pprev) /* unhashed */
goto bail;
struct hlist_node *next = n->next, **pprev = EEEE;
*pprev = next;
if (next)
next->pprev = pprev;
n->next = NULL, n->pprev = NULL;
bail:
free(kn->data);
free(kn);
}
}
free(map);
}
```
其中 `n` 是要被釋放的節點，所以要先把該節點前後的連結給儲存起來，以便等等移除後可以接上，next 指向 n 的 next，而 **pprev 就指向原本 n 的 pprev 所指向的位置，所以 `EEEE` = `n->pprev`
Sign in with Wallet
Connect another wallet