2024q1 Homework1 (lab0)

contributed by < SuNsHiNe-75 >

Reviewed by `teresasa0731`

關於函式的參考資料盡量以原始來源/官方為主（如strncpy 可以查閱 strncpy）

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.

$ lscpu
Architecture:            x86_64
CPU op-mode(s):          32-bit, 64-bit
Address sizes:           45 bits physical, 48 bits virtual
Byte Order:              Little Endian
CPU(s):                  4
On-line CPU(s) list:     0-3
Vendor ID:               GenuineIntel
Model name:              Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
CPU family:              6
Model:                   158
Thread(s) per core:      1
Core(s) per socket:      1
Socket(s):               4
Stepping:                10
BogoMIPS:                5184.00
Caches (sum of all):     
  L1d:                   128 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    1 MiB (4 instances)
  L3:                    48 MiB (4 instances)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-3

針對佇列操作的程式碼實作

`q_new`

commit 65ec12a。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

收到，~~已修改~~。
不要急著說「已修改」，你的行文真的做到「清晰、明確，且流暢」嗎？這是很困難的事，值得我們反覆推敲。

此函式的定義為－建立新的「空」佇列。

我的初步想法是，配置一塊記憶體，將所有指標都指向此「記憶體」。注意其資料結構為環狀雙向鏈結串列。

實作上，我使用 malloc 來配置記憶體空間，檢查空間是否配置成功，若配置失敗則回傳 NULL。最後透過 The Linux Kernel API 中的 INIT_LIST_HEAD API 來初始化 list_head。

不能用 calloc，其會配置連續記憶體空間，通常為陣列應用。
Description of INIT_LIST_HEAD：Initializes the list_head to point to itself. If it is a list header, the result is an empty list.

`q_free`

commit bcb223f。

此函式的定義為－釋放佇列所佔用的記憶體，若 head 原已指向 NULL，則無影響。

我的初步想法是，走訪所有節點（list_for_each），一個一個釋放（free）其佔用的記憶體。

然而，後來細讀 list.h 後，發現若使用 list_for_each 來釋放記憶體會有問題，原因為「其沒有紀錄下一個節點的資訊」，其原文註解也提到：

"The nodes and the head of the list must be kept unmodified while iterating through it. Any modifications to the the list will cause undefined behavior."

因此需另尋走訪所有節點的方法。

實作上，改用 list_for_each_entry_safe 來走訪節點，循序釋放記憶體空間。另需使用 queue.h 中定義的 element_t 結構體，來協助實作 safe 及 entry 的相關操作。

list_for_each_entry_safe 的介紹提到了 "…allow deletes" 及 "The current node (iterator) is allowed to be removed from the list."，是因為多了 safe 指標來儲存下一個 entry 的資料。

// 240226
...
+ q_release_element(entry);
-if (entry->value) {
-        free(entry->value);
-    }
-    free(entry);
...

用巨集 q_release_element 來釋放記憶體即可。

// 240226
...
-if (!(l && !list_empty(l)))
+if (!l)
    return;
...

空佇列也會佔記憶體空間！因此也要釋放掉。

`q_insert_head`

commit bea9db3。

此函式的定義為，在佇列開頭 (head) 插入 (insert) 給定的新節點 (以 LIFO 準則)，若成功則回傳 "true"；否則表配置失敗或佇列為空，回傳 "false"。

我的初步想法是，配置一記憶體空間，先將此新節點的 next 指到舊 head 節點；將此新節點的 prev 指到舊 head 節點的 prev 所指之節點；變更舊 head 節點的 prev 指向新節點；將舊 head 節點的 prev 所指之節點的 next 指向新節點，最後將 head 指標指向此新節點，並將字串丟入新節點即可。

後來發現 list.h 中的 list_add 已實作此過程。

程式實作上，先用 malloc 去配置一 element_t 的空間大小，使用 string.h 中的 strdup 函式，將字串內容複製進新節點，最後使用 list_add將新節點插入佇列頭。

呼叫 strdup 時，其會自動配置該字串大小的記憶體空間，再將該字串複製進去此記憶體之位址，最後回傳的是該「位址」。要注意的是，需使用 free 來釋放。

關於 strdup，應援引 Linux man-page 作為第一手材料，也就是說，該提及 https://man7.org/linux/man-pages/ 的超連結。

收到，已更改。

240226，Test 11 有錯。

// 240227
...
+if (!new->value) {
+	free(new);
+	return false;
+}
...

注意 s 為 NULL（沒傳入資料），會導致 new->value 也為 NULL，需要直接釋放記憶體並中斷執行！

改進你的漢語表達，工程人員說話要精準，什麼叫做「沒東西」和「沒吃到資料」？

收到。

`q_insert_tail`

commit bea9db3。

此函式的定義為，在佇列尾端 (tail) 插入 (insert) 給定的新節點 (以 FIFO 準則)，若成功則回傳 "true"；否則表配置失敗或佇列為空，回傳 "false"。

我的初步實作概念同 q_insert_head。

實作上，概念同 q_insert_head，差別在要用 list_add_tail 將新節點插到佇列尾。

240226，Test 12 有錯。

// 240227
...
+if (!new->value) {
+	free(new);
+	return false;
+}
...

注意 s 為 NULL（沒傳入資料），會導致 new->value 也為 NULL，需要直接釋放記憶體並中斷執行！

`q_remove_head`

commit 79df68a。

此函式的定義為，在佇列開頭 (head) 移去 (remove) 給定的節點，與 delete 不同的是，remove 只需 "unlink" 該節點，用於該元素及字串的空間不能被釋放。另外，若 sp 為 non-NULL 且有元素被 remove，要將該被 removed 的字串複製進 *sp。

一開始我想的是，要先把資料先複製過去，否則調整完指標後，會抓不到該資料，之後就先調整「舊 head 節點的前一個節點」的 next 指標，再調整「舊 head 節點的下一個節點」的 prev 指標，最後將 head 指標指到其下一個節點成為 head，即可進一步將 links 斷乾淨。

list.h 中有巨集 list_del 可執行 unlink！

實作上，先用 list.h 中的 list_first_entry 去找要被移除的頭節點，並用 string.h 的 strncpy 來複製字串進 sp，最後用 list_del 來 unlink 即可。

為何不用 strcpy？
因會有 "Buffer overflow" 的問題，詳細可參考上方strncpy 之超連結。

// 240226
...
+sp[bufsize-1] = '\0';
...

否則若 strncpy 兩字串的長度不同，後面會有多餘的字串殘留。
240227，Test 17 有錯：Segmentation fault occurred. You dereferenced a NULL or invalid pointer.

// 240227
...
+    if (sp != NULL) {
        strncpy(sp, rmv_element->value, bufsize);
        sp[bufsize - 1] = '\0';
+    }
...

要看一下 sp 到底有沒有資料，沒有的話就不用複製了。
Test 17 終於過了！

`q_remove_tail`

commit 79df68a。

此函式的定義為，在佇列尾端 (tail) 移去 (remove) 給定的節點。

想法概念同 q_remove_head。

實作方式同 q_remove_head，差別在要用 list_last_entry來找要被移除的尾節點。

// 240226
...
+sp[bufsize-1] = '\0';
...

否則若 strncpy 兩字串的長度不同，後面會有多餘的字串殘留。

// 240227
...
+    if (sp != NULL) {
        strncpy(sp, rmv_element->value, bufsize);
        sp[bufsize - 1] = '\0';
+    }
...

要看一下 sp 到底有沒有資料，沒有的話就不用複製了。
Test 17 終於過了！

`q_size`

commit 75b9ff4。

此函式的定義為，計算目前佇列的節點總量，若佇列為空或 NULL 的話，回傳 0。

初步的想法是，使用一指標從 head 開始走訪所有節點，設定一變數紀錄節點總數，走回 head 時結束並回傳總數。

若要判斷佇列是否為空，可用 list_empty 巨集。這裡走訪節點用 list_for_each 即可，畢竟沒有要修改節點。搭配 cnt 變數計算節點總數。

`q_delete_mid`

commit 063c865。

移走佇列中間的節點。設佇列長度為 n，則中間的節點即為 $⌊ \frac{n}{2} ⌋$ 索引的點（假設索引從 0 開始）。成功則回傳 "true"；佇列為空或 NULL 則回傳 "false"。

詳見 LeetCode 2095. Delete the Middle Node of a Linked List。

何謂「LeetCode 解法」？你打開 LeetCode 網站，就會出現「解法」嗎？

確實闡述得不好，之後注意！

~~與 LeetCode 解法類似~~ ，先走訪整條 List，數長度 = n；算 $⌊ \frac{n}{2} ⌋$ 來抓中間節點，調整其「前/後節點」的指標，最後釋放其記憶體。

函式實作上，呼叫先前已定義好的 q_size 來得知節點總數，使用 list_for_each_entry_safe 來走訪所有節點，若找到中間節點時，透過 list_del 調整 link，並使用 free 將中間節點的資料及記憶體位置釋放掉。

有一些更好的解法是應用快/慢指標（Fast-slow Pointers）或是頭尾設兩個指標來互相接近以尋找中間節點，能進一步降低時間複雜度。
~~我目前的解法比較土法煉鋼。~~
明確闡述現有作法的缺失，不要濫用成語。 jserv

`q_delete_dup`

commit 17ba18c。

此函式的定義為，在已經排序的狀況，移走佇列中具備重複內容的節點。只能留「資料不重複」的節點。

詳見 LeetCode 82. Remove Duplicates from Sorted List II。

解完 LeetCode 的題目再來實作此函式－不另外先建一個 Dummy node 了；走訪所有節點，透過兩個「一前一後的指標」來檢查資料有無重複，若發現重複了，則直接斷掉目前的節點並釋放其記憶體。

使用 list_for_each_entry_safe 來走訪節點，因 entry 即當前節點；safe 即下一個節點，所以有利於我們執行比較。而字串的比較則使用 string.h 中的 strcmp 即可。值得注意的是，還需一變數 dup 來紀錄是否重複。

後來發現 queue.h 有 q_release_element 的巨集可以協助釋放記憶體。

`q_swap`

commit 8d3ad73。

交換佇列中鄰近的節點。

詳見 LeetCode 24. Swap Nodes in Pairs。

LeetCode 的題目談到不能動到節點的資料，故還是只能動指標。那大致作法就是要去找看看有無已定義好的巨集，以更方便地執行兩個節點間的指標調整。

參照 fewletter 的 q_swap 圖片分析，可以透過 list.h 提供的 list_del 及 list_add 巨集來迭代調整 links，簡潔有力。

之後又發現此二巨集已被整合為 list_move 巨集，但需注意參數的使用。

`q_reverse`

commit 73c77b2。

以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列節點，換言之，它只能重排已經存在的節點。

想法是走訪所有節點，一個一個調整其指標，最後移動 head 指標即可。

即透過 list_move 逐一將節點加到佇列頭即可。

注意不能用 list_for_each_entry 來走訪節點，因其不允許當前節點的修改。

`q_reverseK`

commit abd5209。

類似 q_reverse，但指定每 k 個節點為一組，進行反向順序排列。

詳見 LeetCode 25. Reverse Nodes in k-Group (Hard)。

用兩個指標指在「要反轉的佇列頭」及「要反轉的佇列尾」，呼叫 q_reverse 來反轉此段佇列，以此類推。

問題：q_reverse 是固定 head 的，在呼叫它之前，要先調整先前的兩個指標所指向節點的 next 與 prev，使其成為一 Circular Linked List。

可用 list_cut_position 將該段要反轉的佇列先丟到另一空佇列（透過 LIST_HEAD），再行 q_reverse 以解決要調整指標的繁瑣問題（如此，head 指標也不用動來動去）。反轉好的佇列段先使用 list_splice_tail_init 暫存到另一個佇列的後端，待 head 佇列清空後，再將整個暫存佇列以 list_splice_init 丟回 head 佇列。

截至 240227，該功能是最後一個寫的，測試的分數為 94 分。





Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		94/100
make: *** [Makefile:60: test] Error 1
ss75@ss75:~/linux2024/lab0-c$

文字訊息請避免用圖片來表示，否則不好搜尋和分類

收到。

`q_sort`

commit 3391913。

以遞增順序來排序鏈結串列的節點。若佇列為空或 NULL，此排序無影響；若佇列只有一個元素，無事發生。透過傳入的 Descend 參數來判斷要遞增/遞減排序。

可參閱 Linked List Sort 得知實作手法。
（Bubble sort、Insertion sort、Selection sort、Merge sort）

鑒於上文提到的前三種排序法的時間複雜度的 Average case 皆要 $O (n^{2})$ ；因此選擇 Merge sort（時間複雜度 Average case 僅為 $O (n l o g_{2} n)$ ）。上文的 Merge sort 實作架構是透過遞迴，其中使用快慢指標來分割串列（slow 抓到串列中間節點後，fast = slow->next 來當右邊串列的新 head，以此類推）；另撰寫一 merge 遞迴地將分割好的串列逐步 merge 起來。

要注意的是，該 Merge sort 實作的是遞增順序的串列。

在 q_sort，分割串列的部分透過快慢指標協助實作－找到中間節點後，先用 LIST_HEAD 建兩個 next 與 prev 都指向自己的 head，接著透過 list_splice_tail_init 及 list_cut_position 將原串列拆成兩條串列（函式內都將指標調整好了）。接著即可遞迴執行 q_sort，最後合併。決定升序/降序的地方在 merge2list 函式，值得注意的是用 strcmp 比較數值大小時，要小心誰比較小的時候先放入 list 的順序，可用 list_move_tail 將節點放到尾端。最後若左/右某邊的 list 已清空，剩下的 list 即是以排好且比已完成的 list 都還大的數，直接透過 list_splice_tail_init 將整串 list 插到尾端即完成排序。

參考 @itiscaleb 的想法。

qtest 中測試 sort 時，會報錯：Segmentation fault (core dumped)！報錯原因待釐清…

//240226
void merge2list(struct list_head *l_head,
            struct list_head *r_head,
            struct list_head *head)
{
    ...
+        if (strcmp(ele1->value, ele2->value) <= 0)
+            list_move_tail(l_head->next, head);
+        else
+            list_move_tail(r_head->next, head);

-        int cmp_result;
-        if (descend)
-            cmp_result = strcmp(ele1->value, ele2->value);
-        else
-            cmp_result = strcmp(ele2->value, ele1->value);

-        if ((descend && cmp_result >= 0) || (!descend && cmp_result <= 0))
-            list_move_tail(l_head->next, head);
-        else 
-            list_move_tail(r_head->next, head);
    ...
}

void q_sort(struct list_head *head, bool descend)
{
+    if (!head || list_empty(head) || list_is_singular(head))
-    if (!head || list_empty(head))
        return;
    ...
+    if (descend)
+        q_reverse(head);
}

找出問題為無判斷「是否為單元素串列」，此種串列不能執行 q_sort 遞迴。
修改遞減順序的實作方法，原程式單純實作遞增順序，若判斷為 descend，則用 q_reverse 反轉即可。

//240227
+void q_sort_asc(struct list_head *head)
+{
+    ...
+}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
+    q_sort_asc(head);
    
    if (descend)
        q_reverse(head);
}

錯誤執行 q_reverse，因此先包裝前置 ascending 演算法，不讓 q_reverse 也進去遞迴。

`q_ascend`

commit 22ef866。

以遞增順序來排序鏈結串列的節點。最後要回傳佇列長度。

實作概念同 q_descend，差別在要調整字串比較大小於方向。

`q_descend`

commit b181b2e。

以遞減順序來排序鏈結串列的節點。最後要回傳佇列長度。

參閱 LeetCode 2487. Remove Nodes From Linked List。

標註你參考標的的人名或代稱，不要說「別人」

收到。

參考 Not In My Back Yard 網友的 LeetCode 解題思維。

簡單來說：每個節點往右邊所有節點看，若有任一比自己的值還大的節點值，則該節點要被刪除。將串列反轉，是因為由右往左走訪單向連結串列有其不方便性，且該題也能視為「由右往左來數的嚴格遞增串列」。在實作上，就是以由右往左的方式移除較小的元素，最後再反轉回來即為所求。

何謂「白話來說」？難到原本文章用文言文書寫嗎？

用詞不佳，會再注意。

由尾端往後找，找到下一個更大的節點值後，替換目前最大節點值，並將中間的節點全部刪除掉。最後即會留下一嚴格遞減串列。

在作答 LeetCode 題目的當下，誤解題目意思，因此想出的方法都會 WA，故尋求網友大神的解答紀錄，以便學習。閱讀理解完後，才過來想 q_descend 的實作。理解題目的能力有待加強。

實作原理其實就是在實作反方向的 list_for_each_entry_safe 的概念。字串數值的比較，需使用 strcmp 函式來實作。最後可直接用先前定義的 q_size 來回傳節點數。

`q_merge`

commit e930c65。

合併所有已排序的佇列，並合而為一個新的已排序佇列。

詳見 LeetCode 23. Merge k Sorted Lists (Hard)。

240310 回頭寫完此最後一函式，測試的分數已 100 分。






Probably constant time
Probably constant time
Probably constant time
Probably constant time
---     trace-17-complexity     5/5
---	TOTAL		100/100

使用 `select` 改善 Web 與 Linenoise 之衝突問題

linenoise 理解

ChatGPT 適合用來改進你的書寫內容，但不該拿來查詢專業議題。

了解。

它是一個簡單的 C 函式庫，用來處理命令列單行輸入。其還支援自動補齊命令和命令歷史記錄功能，間接讓命令列應用程式的開發變得更便利。此外，其還支援跨平台使用，包括 Linux、macOS 和 Windows 等作業系統。

套用到我們現時的使用場景，簡單來說，我們在 Linux 終端命令列進行命令操作時，會一直使用到 linenoise 函式庫，最常見的就是「命令的輸入」、「按 Tab 鍵自動補全檔案名稱」與「按上/下箭頭鍵來查找曾經輸入過的命令」等…

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

收到。

linenoise.c 中，相關重要函式之深入理解：

*linenoise：linenoise 函式庫的主要 API。它首先透過檢查「Stupid terminals 的黑名單」來檢查終端是否具有基本功能。根據結果，擇一執行下二動作：
1. 呼叫「行編輯函式」（即下方 line_edit）
2. 使用一個 dummy fgets 函式，確保在最不利的情況下，使用者還是能輸入命令。
line_raw：這個函式使用「設置為 raw mode 的 STDIN 檔案描述子」來呼叫行編輯函式 line_edit。

Raw mode：輸入的資料將不會被緩衝，而是直接傳遞給應用程序，同時輸出的資料會直接發送到終端，而不經過作業系統的進一步處理。
STDIN_FILENO：即 stdin 的檔案描述子，其值為 0。
STDOUT_FILENO：即 stdout 的檔案描述子，其值為 1。
呼叫 line_edit(STDIN_FILENO, STDOUT_FILENO, buf, buflen, prompt)。
line_edit：行編輯能力的核心。它期望 'fd' 已經處於 "raw mode"，這樣每按一個鍵都會立即回傳給 read 函式。當使用者輸入 enter 或 ctrl+d 時，「結果字串」將被放入 'buf' 中，最後回傳「當前緩衝區的長度」。

write(l.ofd, prompt, l.plen) 參考 write(2)，其將資料寫入到檔案描述子對應的檔案，可在終端機代替 printf 輸出對應 prompt。
read(l.ifd, &c, 1) 參考 read(2)，其在檔案描述子對應的檔案中讀取資料，可取代 scanf 在命令列讀取資料。

`select` 理解

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

收到。

閱讀 select(2) 後，理解如下。

select 允許程式監視多個檔案描述子，等待其中一個或多個檔案描述子「就緒」，以進行 I/O 操作。如果可以執行相應的 I/O 操作（例如，read(2) 或足夠小的 write(2)）而不會被阻擋，則檔案描述子就是「就緒」的狀態。

fd_set 是一種能夠表示一組檔案描述子的結構類型。

File descriptor sets 相關－select 函式的主要參數是「三個檔案描述子」的集合（用 fd_set 宣告），允許呼叫者等待「特定檔案描述子集合上的三種事件」。如果不需要監視某種事件，可以將該 fd_set 參數設成 NULL。

FD_ZERO：該巨集移除所有檔案描述子。可初始化檔案描述子集合。
FD_SET：該巨集將檔案描述子 fd 添加到集合中。
FD_CLR：該巨集從集合中移除檔案描述子 fd。
FD_ISSET：該巨集用來測試檔案描述子是否仍存在於集合中。若存在，回傳非零值；如果不存在，則回傳 0。

而 select 的參數理解如下。

readfds：此集合中的檔案描述子用於檢查它們是否「準備好進行讀取（讀取時不會被阻擋）」。另外，檔案描述子在達到檔案結尾時也會「就緒」。在 select 回傳後，readfds 會清除所有「未準備好被讀取」的檔案描述子。
writefds：此集合中的檔案描述子用於檢查它們是否「準備好進行寫入（寫入時不會被阻擋）」。但是，即使檔案描述子顯示為可寫入，一個 "Large write" 仍可能會被阻擋。在 select 回傳後，writefds 會清除所有「未準備好寫入」的檔案描述子。
exceptfds：此集合中的檔案描述子用於檢查是否存在「異常條件（參閱 poll(2) 中有關 POLLPRI 的討論）」。在 select 回傳後，exceptfds 會清除所有「未發生異常」的檔案描述子。
nfds：此參數應設置為任一集合中「最大檔案描述子的數字加 1」。
timeout：此參數是一個 timeval 結構，可設定 select 應該被阻檔，且「等待檔案描述子變為就緒」的間隔。阻擋直到發生以下條件之一：
1. 檔案描述子變為「就緒」
2. 呼叫被信號處理程式中斷
3. timeout 過期

最後，回傳值方面：
若成功，回傳 readfds、writefds 和 exceptfds 中被設置的檔案描述子數量。如果在任何檔案描述子變為就緒之前「timeout 過期」，則回傳值可能為 0；失敗的話，回傳 -1，且檔案描述子集保持不變，timeout 變為未定義。

使用繁體中文和台灣慣用詞彙！
參見：

收到。

console.c 理解

整理 console.c 的函式功能後，可大概看出，與命令列及 linenoise 互動相關的函式可能為 do_web、cmd_select、completion、run_console。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

收到。

以下針對這些函式作深入理解：

do_web：首先預設 port 為 9999，呼叫 web.c 中的 web_open 函式來建立網頁伺服器，若成功，則輸出相關訊息、設定 web_fd 為 '1'，並「設定 use_linenoise 參數為 false」，失敗則 perror("ERROR")。
cmd_select：用 select 執行命令處理。類似 select，但會先檢查命令輸入是否「存在於內部緩衝區」或「從命令輸入中可讀取」。如果沒被阻擋的話，把緩衝區中的 fd 加入到 select 的 readset 中，如果 web 還沒準備好監聽，也把 web_fd 加入到 readset 中，最後調整 nfds 參數。呼叫 select 函式指定給 result 參數，然後看一下哪個檔案運算子還在 readset 中，分別執行對應操作，最後回傳 result 值。
completion：（大致瀏覽後，發現此函式在該題的討論中較不重要。）
run_console：該函式會呼叫一堆 linenoise.c 中定義的 API，值得注意的是也會判斷先前定義的 use_linenoise 參數的布林值，若為 "true"，才會進一步提供命令自動補齊、歷史紀錄等操作。

那麼重點來了，難道開啟網頁伺服器（do_web）時，順手將 use_linenoise 參數設定為 "false" 的操作，就是 run_console 時，終端命令列端無法執行 linenoise 的元兇嗎？若是，在 do_web 函式將 use_linenoise 參數設定為 "false" 的用意為何？能否強制將其設為 "true" 並執行成功？

嘗試將 use_linenoise 設為 true 後，發現 qtest 端終端機能正常運行 linenoise 套件；然而若在另一終端機執行 curl http://localhost:9999/命令 則會發現發送 HTTP request 給 Web server 的過程直接卡住了。
此外，若將 run_console 中 while 判斷中的 use_linenoise 參數移除，也會有如上結果。

解決 linenoise 與 socket 之衝突





























bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        char *cmdline;
        while (use_linenoise && (cmdline = linenoise(prompt))) {
            interpret_cmd(cmdline);
            line_history_add(cmdline);       /* Add to the history. */
            line_history_save(HISTORY_FILE); /* Save the history on disk. */
            line_free(cmdline);
            while (buf_stack && buf_stack->fd != STDIN_FILENO)
                cmd_select(0, NULL, NULL, NULL, NULL);
            has_infile = false;
        }
        if (!use_linenoise) {
            while (!cmd_done())
                cmd_select(0, NULL, NULL, NULL, NULL);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

這邊把 run_console 之原程式碼秀出來以方便對照理解。
先討論一下哪邊在作 socket；哪邊在作 stdin。
前面 do_web 的時候把 use_linenoise 設成 false，所以此處第 19 行在處理 socket；第 10 行的 while 則在處理命令列輸入。










































































int web_connfd;
static int cmd_select(int nfds,
                      fd_set *readfds,
                      fd_set *writefds,
                      fd_set *exceptfds,
                      struct timeval *timeout)
{
    int infd;
    fd_set local_readset;

    if (cmd_done())
        return 0;

    if (!block_flag) {
        /* Process any commands in input buffer */
        if (!readfds)
            readfds = &local_readset;

        /* Add input fd to readset for select */
        infd = buf_stack->fd;
        FD_ZERO(readfds);
        FD_SET(infd, readfds);

        /* If web not ready listen */
        if (web_fd != -1)
            FD_SET(web_fd, readfds);

        if (infd == STDIN_FILENO && prompt_flag) {
            printf("%s", prompt);
            fflush(stdout);
            prompt_flag = true;
        }

        if (infd >= nfds)
            nfds = infd + 1;
        if (web_fd >= nfds)
            nfds = web_fd + 1;
    }
    if (nfds == 0)
        return 0;

    int result = select(nfds, readfds, writefds, exceptfds, timeout);
    if (result <= 0)
        return result;

    infd = buf_stack->fd;
    if (readfds && FD_ISSET(infd, readfds)) {
        /* Commandline input available */
        FD_CLR(infd, readfds);
        result--;

        set_echo(0);
        char *cmdline = readline();
        if (cmdline)
            interpret_cmd(cmdline);
    } else if (readfds && FD_ISSET(web_fd, readfds)) {
        FD_CLR(web_fd, readfds);
        result--;
        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        web_connfd =
            accept(web_fd, (struct sockaddr *) &clientaddr, &clientlen);

        char *p = web_recv(web_connfd, &clientaddr);
        char *buffer = "HTTP/1.1 200 OK\r\nContent-Type: text/plain\r\n\r\n";
        web_send(web_connfd, buffer);

        if (p)
            interpret_cmd(p);
        free(p);
        close(web_connfd);
    }
    return result;
}

再把 cmd_select 之原程式碼秀出來以方便對照理解。
第 47 行這邊的 if 是在判斷是否有 input 的檔案描述子，若有，則作 stdin；第 56 行這邊的 if 則在檢查有無 web 檔案描述子，有的話才作 socket。

將這兩函式重點列出並理解後，想說能否嘗試解決 linenoise 與 socket 的衝突：
原本流程是這樣－do_web 把 use_linenoise 設 "false" 了，所以 run_console 那邊（上述第 19 行）會作 socket 的相關操作，也就不會有 linenoise 的運作了。
那既然 stdin 及 socket 都會執行 cmd_select，那我在 cmd_select 中直接引入 linenoise 套件，說不定就能同時運作了？

試試看這樣：




...
-    char *cmdline = readline();
+    char *cmdline = linenoise(prompt);
...

發現如此更改，在 line_edit 中的 read 被阻塞時，linenoise 套件會不能運作。
實驗中會變成：輸入 web 命令後，會先不能用 linenoise，待另一終端機下任一 curl 命令後，回原終端機按 Enter 後，linenoise 方可運作。

參考 vax-r 的詮述－
若將 linenoise 擺在 select 之後才執行，也就是確認是 std input file descriptor 變為 ready 時才使用，則會導致我們必須按下兩次 ENTER 才能正確執行一次命令，因為第一次 ENTER 用來通知 select 這個 fd 的狀態改變，第二次 ENTER 則是用來跳出 line_edit 函式。

想法可以這樣變，既然最後一步都是 line_edit，何不將 select 挪到該函式中，同時監控 stdin 之檔案描述子或 socket 之檔案描述子就好？在 cmd_select 端只需要將兩方命令傳入 linenoise 函式，最後送進 line_edit 處理 select 即可。

GitHub 之 commit 紀錄：Integrate the linenoise function with socket。

參考自 @vax-r
將原 cmd_select 下面的 select socket 相關操作概念移到 line_edit 執行，先判斷如果有 Web 在監聽，就直接作 socket 操作並回傳即可；若無，則繼續執行 line_edit 下方原有的行編輯操作。
如此，實驗中，若命令列端有任何字元輸入（未 Enter），Web 端 curl 後則會等待命令列端完成原命令輸入後，才會執行 Web curl。

TODO：探尋將 linenoise 之歷史紀錄功能整合進 Web server 的方法。

目前是 qtest 後，只會記錄到輸入 web 命令前的命令歷史紀錄。

命令 shuffle 之實作

Fisher–Yates Shuffle 演算法

僅參考 Fisher–Yates Shuffle 及相關介紹影片。
其分為 Original version 及 Modern version，下面以陣列運作的例子解說：

Original version：設今有一陣列 arr = {1, 2, 3, 4} 及一空陣列 rst = {}，要作 Fisher–Yates Shuffle，首先因目前有 4 個數字仍未洗牌，因此每個數字的選取機率皆為 $\frac{1}{4}$ ，設選中 2，則將其從 arr 移除，並插到 rst[0] 的位置：rst = {2}；繼續，目前 arr 剩 3 個數字，則每個數字的選中機率為 $\frac{1}{3}$ ，設選中 4，比照辦理操作，陣列變為 rst = {2, 4} 及 arr = {1, 3}；以此類推，直到 arr 陣列為空，則洗牌完成。
Modern version：同上例子，只是實作方式變為「只用 arr，首輪隨機選取完數字後，將其與 arr[0] 之數字交換，接著進入第二輪循環（隨機選完數字後，與 arr[1] 交換）」。Modern version 比起 Original version 的優點在於時間/空間複雜度的降低－時間複雜度由 $O (n^{2})$ 降為 $O (n)$ ；空間複雜度則由 $O (n)$ 降為 $O (1)$ 。

根據在 qtest 提供新的命令 shuffle ，本次作業即要實作 Modern version 的 Fisher–Yates Shuffle 演算法。

實作

查看 qtest.c 中的 console_init 發現其還未包含 shuffle 命令，若要在 qtest 實作 shuffle 命令，需要將其加入到命令列表中。

觀察 console.h 中有這段描述：

/* Add a new command */
void add_cmd(char *name, cmd_func_t operation, char *summary, char *parameter);
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)

所以我們要在 console_init 中新增命令 shuffle，並建立 do_shuffle 函式，以偵錯並呼叫在 shuffle.h 中的 q_shuffle 函式：

static void console_init()
{
    ...
    ADD_COMMAND(reverseK, "Reverse the nodes of the queue 'K' at a time",
                "[K]");
+   ADD_COMMAND(shuffle, "Do the Fisher–Yates Shuffle algorithm", "");
    add_param("length", &string_length, "Maximum length of displayed string",
              NULL);
    ...
}

static bool do_shuffle(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }
    
    if (!current || !current->q)
        report(3, "Warning: Calling shuffle on null queue");
    error_check();
    if (q_size(current->q) < 2)
        report(3, "Warning: Calling shuffle on single queue");
    error_check();
    if (exception_setup(true))
        q_shuffle(current->q);
    q_show(3);
    return !error_check();
}

若「佇列為空」或「佇列只有一個元素」，會跳警告。
沒問題則呼叫 q_shuffle。

鑒於 queue.h 修改後會無法 commit，故建兩新檔案 shuffle.c 及 shuffle.h，來實作 shuffle 命令，並將其一 include 到 qtest.c 中，詳細程式碼請看下方的 commit 紀錄。

GitHub 之 commit 紀錄：Implement a new command - shuffle

q_shuffle：運作原理即我上面分析的 Modern version 演算法，唯要注意實作場景改為 Circular Linked List 資料結構。先用 q_size 算佇列長度，然後 rand 一個隨機數。使用一 *current 指向「已完成 shuffle 佇列的下一個元素」、一 *selected 指向「選定要 swap 的隨機數」、用一 *completed 指向「已完成 shuffle 佇列的尾端」方便調整 *current 的位置。基本上就是先將 *selected 指到 rand 到的索引元素，並 swap *current 與 *selected 所指元素，調整 *completed 及佇列長度變數，直到佇列長度變數為 0，即完成洗牌。
swap：使用 list_move_tail 去實作。特別注意「兩節點相同」及「兩節點相鄰」的特殊情況即可。

測試程式分析

前置步驟要先安裝 python3, pip, matplotlib。

使用測試程式中的 driver.py 去分析我的 shuffle 實作，測試 shuffle 次數為 1,000,000 次，根據下方之輸出及直方圖的呈現結果可知，Fisher–Yates Shuffle 演算法是 Uniform Distribution 的。

Expectation:  41666
Observation:  {'1234': 41550, '1243': 41713, '1324': 41566,
'1342': 41736, '1423': 41914, '1432': 41481, '2134': 41399,
'2143': 41589, '2314': 41535, '2341': 41490, '2413': 41668,
'2431': 41962, '3124': 41953, '3142': 41714, '3214': 42001,
'3241': 41723, '3412': 41644, '3421': 41679, '4123': 41759,
'4132': 41634, '4213': 41600, '4231': 41478, '4312': 41762,
'4321': 41450}
chi square sum:  15.487783804540873

引入 `lib/list_sort.c`

本處與 @jujuegg 協作。

解釋 Linux 核心的 `lib/list_sort.c`

`merge`

在 merge 函式中，我上面的方法是使用 list_move 來移動比較過後的節點，但 Linux 卻只使用了三行程式碼來完成，且運用到了 pointer to pointer 的概念。且它並不是一次只移動一個節點到 head，而是將該節點所在串列移動到 head 的尾端。以下是部分程式碼：

struct list_head *head, **tail = &head;

// a and b are two sotred list heads
if (cmp(priv, a, b) <= 0) {
    *tail = a;
    tail = &a->next;
    a = a->next;
    if (!a) {
        *tail = b;
        break;
    }
}

我們是需要自己去定義 cmp 的。而對於 priv 的解釋則是參考 vax-r 同學的解釋：

可以注意到函式的第一個參數 priv ，可以在 /lib/test_list_sort.c 當中看到 priv 是用來使得 check 這個函式經過 KUnit 測試後可以 failed。

`merge_final`

再來看到 merge_final，他比起 merge 多了下面這個步驟，b 是當其中一個串列為空時，剩下的串列所在的位置。這看起來是很沒必要的行為，因為是拿同一個節點進行比較，但凡事都有原因。

do {
    if (unlikely(!++count))
        cmp(priv, b, b);
    b->prev = tail;
    tail = b;
    b = b->next;
} while (b);

註解提到：

If the merge is highly unbalanced (e.g. the input is already sorted), this loop may run many iterations. Continue callbacks to the client even though no element comparison is needed, so the client's cmp() routine can invoke cond_resched() periodically.

如果其中一個串列還剩很多節點，持續呼叫 cmp 可以週期性的呼叫 cond_resched，這個函式與 Kernel 安排 CPU time 有關。

`list_sort`

如果有兩個尚未合併的 $2^{k}$ 大小的串列，等到下一個也是 $2^{k}$ 大小的串列出現，前兩個就會合併。
只要這 $3 * 2^{k}$ 個節點可以全部放到快取中，就可以避免 cache thrashing，簡單來說就是一直重複替換快取中某個地方的資料，非常浪費時間。

count 會持續記錄尚未合併的節點數量，當達到 $2^{k}$ 的奇數倍時，就會啟動合併。

發生 2 次合併後，所產生的 2 個 $2^{k + 1}$ 大小的串列會在第 3 個串列出現前合併，所以永遠不會有過多沒有合併的串列。

程式碼分析：

變數結構：
- *list = head->next：要排序的串列的第一個節點
- *pending = NULL ：還沒合併的串列
- count = 0：pending 中節點的數量
- **tail = &pending：指向 pending 指標的指標，它的作用是尋找 pending 中要做合併的位置，並且會指向該合併點尾端的指標

在整個過程中，list->prev 會持續指向 pending。

有趣的是，在第一行，程式就把串列變為暫時的單向鏈結串列。但卻沒有更動頭的 prev。

/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;

當 count 的 LSB 是 1 的時候，才會進入迴圈，並且持續右移，直到有 0 出現。這邊在尋找要合併的位置。

/* Find the least-significant clear bit in count */
for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;

這邊的意思是，如果 bits 裡面還有剩餘的 1 的話，就會啟動合併。換言之，如果目前 count + 1 為 2 的冪，則不合併。合併後的串列會儲存在 a，後續再修改 pending (*tail) 來指到剛合併完的串列。

一開始在追蹤程式碼的時候可能會覺得很奇怪，因為 pending 一開始是只有藉由 prev 連接的單向鏈結串列，而下面是將 tail 所在位置與 tail->prev 進行合併，而在第一次呼叫 merge 之後才會將 pending 中的 next 指標接好。

if (likely(bits)) {
    struct list_head *a = *tail, *b = a->prev;

    a = merge(priv, cmp, b, a);
    /* Install the merged result in place of the inputs */
    a->prev = b->prev;
    *tail = a;
}

推論：

使用 bottom up 的方法實作 merge sort 相較於 top down 方法省去了 partition 的步驟，由於合併的過程是與相鄰的串列進行，這方法會讓最近被合併過的資料，在不久後馬上跟附近的串列合併，在快取中的使用率會相對地頻繁。

引入 `list_sort` 到 lab0-c 當中

`list_sort.c`

修改 include

  #include <linux/kernel.h>
- #include <linux/bug.h>
- #include <linux/compiler.h>
- #include <linux/export.h>
  #include <linux/string.h>
- #include <linux/list_sort.h>
- #include <linux/list.h>
+ #include <list_sort.h>
+ #include "queue.h"

新增 likely 與 unlikely 巨集

# define likely(x)	__builtin_expect(!!(x), 1)
# define unlikely(x)	__builtin_expect(!!(x), 0)

把變數型態宣告 u8 改成 uint8_t

- u8 count = 0;
+ uint8_t  count = 0;

新增 cmp 函式，把 priv 移除，並加入指定 descend 功能，記得要修改 nonnull 的變數位置

int cmp(const struct list_head *a, const struct list_head *b, bool descend)
{
    element_t *a_entry = list_entry(a, element_t, list);
    element_t *b_entry = list_entry(b, element_t, list);
    
    if (!descend)
    	return strcmp(a_entry->value, b_entry->value) < 0 ? 0 : 1;
    else
    	return strcmp(a_entry->value, b_entry->value) > 0 ? 0 : 1;
}

把最後面的 EXPORT_SYMBOL 移除，暫時用不到

`q_test.c`

新增標頭檔

+ #include "queue.h"
+ #include "list_sort.h"

新增 do_lsort 命令，我是直接參考裡面的 do_sort 寫法，沒有更改太多東西。

`Makefile`

OBJS := qtest.o report.o console.o harness.o queue.o \
        random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
        shannon_entropy.o \
-       linenoise.o web.o
+       linenoise.o web.o list_sort.o

比較效能落差

我們可以藉由三種數據來比較各個排序演算法之間的差異：

Execution time
The number of comparisons
Cache miss ratio

我選擇比較執行時間的差距，在 Dude, is my code constant time? 中提到，可以測量程式的 CPU cycle 來做為時間的依據。但我就沒有再執行後續更嚴謹的步驟，也就是設立虛無假說和計算 F 值。

使用 Linux 效能分析工具 perf 進行計算

以下設計是參考去年 chiangkd 同學的方法，我預計使用隨機生成且不同大小的測資，測量 10 次來取平均。大概測到 500 萬左右個節點的時候就滿了。

command 是「命令」，而非「指令」(instruction)

收到。

執行以下命令：

$ sudo perf stat --repeat 10 ./qtest -f traces/trace-sort.cmd

自己實作的 `q_sort`

Data Size	Average Time (Sec)
50000	0.0206
100000	0.0632
500000	0.5023
1000000	1.0857

Linux 的 `list_sort`

Data Size	Average Time (Sec)
50000	0.0169
100000	0.0586
500000	0.4323
1000000	0.9429

確實有比較快的趨勢。

研讀論文〈Dude, is my code constant time?〉

本處與 @jujuegg 協作。

在一些已經存在的方法中，需以某種方式對硬體進行模擬，而 CPU 的訊息並不是完全公開的，在實現上難度很高，這是它們共同的缺點。
而 dudect 是基於 leakage 偵測，來判斷程式碼的複雜度是否為 constant time 的一種工具。

解釋 Simulation

當設定 simulation 為 1 後，在呼叫 it, ih, rt, rh 這 4 種命令時，會呼叫相對用來測試是否為 constant time 的函式：

bool ok = pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();

if (!ok) {
    report(1, "ERROR: Probably not constant time or wrong implementation");
    return false;
}
report(1, "Probably constant time");
return ok;

但我怎麼都找不到這些函式被定義在哪邊，直到我看到 var-x 同學提到它寫在 fixure.h 中才知道。

參閱課程教材！

#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

總歸來說，最終呼叫的是 test_const 這個函式，並用 mode 來區分目前是測試哪個命令。其中會持續的使用 doit 來測試，只要有一次通過，程式就會中斷並判定為 constant time。相對的，如果跑了足夠多次並且都沒有成功，則宣布不是 constant time。

static bool test_const(char *text, int mode)
{
    bool result = false;
    t = malloc(sizeof(t_context_t));

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        init_once();
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }
    free(t);
    return result;
}

在 doit 裡面，以下為主要測試區塊的程式碼

bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
update_statistics(exec_times, classes);
ret &= report();

measure ：被定義在 constant.c 中，它的測量方法是先插入一個字串，之後再測量插入/刪除另一個字串的時間。
differentiate：計算 before_ticks 與 after_ticks 的差值。
update_statistics：檢測測量數據的平均值。
report：藉由檢查 t 統計值 max_t 是否超過閾值來判斷

解釋 Student's t-distribution

新增 percentile 處理

仿照 dudect.h 對 lab0-c 做處理。詳細程式碼請見 Apply percentiles to make dudect better。

在 t_context_t 結構中新增 percentiles，方便統一管理。
捨棄第一次測量的 batch，並執行 prepare_percentile。
在 update_statistics 中，這個迴圈省去了前面 10 筆的資料，我也仿照它的作法。

Tic-tac-toe

引入 hlist.h

參照 linux/list.h，透過 Ctrl + F 搜尋 hlist 相關程式碼，將他們複製到新建的 hlist.h 內即可。

注意包含相關函式庫。

新增 `ttt` 命令

在 qtest.c 中的 console_init 新增 ADD_COMMAND ，並另寫一函式 do_ttt 以呼叫主要執行函式。另需包含 game.h 以獲取相關函式之訊息。最後，在 Makefile 也須新增編譯 game.o。

在實作 shuffle 命令已練習過。
此時，我在 do_ttt 中先呼叫 game.c 中的 draw_board 函式來測試。

至此步驟，已可運行 ttt 命令，並產生棋盤；但打如 a3 等命令仍未定義。

整合 jserv/ttt 完畢

commit afe377f。

先將 mt19937-64.[ch]、zobrist.[ch]、negamax.[ch] 整合到 lab0-c 中，qtest 中記得包含 negamax.h，另外 Makefile 需新增編譯上述檔案。
其中 main 的運作過程寫在 do_ttt 內，以完善程式運作，並成功整合運行。。

其中 mt19937-64 是 Mersenne Twister 偽隨機數生成器的 64 位元版本。
參考 Zobrist Hashing。zobrist 實現了一個基於 Zobrist key 的 hash table，用來儲存棋譜或遊戲狀態的得分及最佳下法。該檔案提供了初始化、查找、插入和清空的功能。
參照 Negamax。negamax 是一種用在賭博遊戲中的 Minimax 搜尋演算法，特別適用於雙人遊戲的 zero-sum 特性。

commit 過程發現很多 cppcheck 錯誤，需一一自行修正。

zobrist.c:64:21: error: Null pointer dereference: (struct zobrist_entry_t*)0 [nullPointer]
            entry = hlist_entry(hash_table[i].first, zobrist_entry_t, ht_list);
                    ^
nofile:0:0: information: Cppcheck cannot find all the include files (use --check-config for details) [missingInclude]

因一直無法解決此 cppcheck 報錯，故直接將其忽略檢查，在 pre-commit.hook 檔案中加上 --suppress=nullPointer:zobrist.c 即可。

用定點數取代浮點數運算

Monte Carlo Tree Search（MCTS）理解

參照 Monte Carlo Tree Search 解說及 Monte Carlo Tree Search - Tic-Tac-Toe Visualization。

以下黑白棋為例，套用 Monte Carlo Tree Search 讓電腦在下每一步棋時都會去估算其「下哪步棋勝率最高（即最佳解，但要注意的是，執行此演算法時不會算出全部行動的所有延伸結果，所以此最佳解不是實質意義上的最佳解！）」，簡介步驟如下（節點有「勝率」及「比賽場數」等參數）：

Select Leaf Node：往當前 Upper Confidence Bound (UCB) 最高的節點方向找（若 UCB 相同，則按左到右的順序找），直到找到的點沒有左/右子點。

UCB 可達成 Exploitation（選擇已知最好策略）與 Exploration（選擇探索其他路線）的平衡，有興趣的可再自行深入了解。

Expand / Rollout：
- 若為新節點（尚未更新過），則執行 Rollout－以該節點為起點，模擬完整場遊戲直到結束，並獲得比賽結果。
- 若該節點已更新過，則執行 Expand－往下生成兩個新節點。
BackPropagate：Rollout 結束後，往上更新所有相關節點的結果。

可看出，雖然對比 DFS 等演算法，運算資源及時間都優化很多；但是其算出的只是「還不錯的結果」來操作下一步棋，因此若對手故意引導電腦往較差的結果下，電腦是有機率輸的。

其實作在 agents/mcts.c 中。

浮點數之深入探討

研讀 agents/mcts.c 可發現，其 double score 相關的操作皆為浮點數運算，我首先想針對它，進行定點數運算的取代。

實作前，需先理解浮點數與定點數「對電腦來說的位元儲存方式」等的區別。
double 本身是 64-bit 的雙精度浮點數資料型態，參考 IEEE 754 的「64位元雙精度」小節與雙精度浮點數，雙精度浮點數的格式呈現如下：

其有 1-bit 的符號位、11-bit 的指數位及 52-bit 的有效數位。

要特別注意的是，為了方便比較大小，其指數部分是使用「偏正值」形式表示；而非使用「二補數」表示。如此，指數部分通常用一個無符號的正數值儲存。

偏正值 = 實際的指數大小 + 固定值（64-bit 為 1023）。

定點數之深入探討

定點數方面，參照 Linux 核心的浮點數運算－定點數及定點數運算。

首先我們要知道，為何 Linux 核心會偏好定點數的實作－定點數的運算比浮點數要快，需要的硬體也比較少。假如要計算的數值範圍事先就已知道，而且限制在較小的範圍內，定點數運算可以有效的使用其位元（誤差較小）。

另外，使用定點數運算的程式，不會受到是否有浮點運算器（FPU）的影響，可移植性比浮點數要高；且並非所有 Linux 支援的硬體都具備 FPU… 種種因素，使 Linux 核心在實務上，較建議使用定點數運算。

定點數表示法中，小數部份和整數部份一樣，也會表示為進制底數 $b$ 的冪次，不過是以負數冪次來表示。即若儲存了 n-bit 的小數，其數值一定是 $b^{- n}$ 的整數倍。

定點數類型的值其實就是個整數，但需要額外作比例進位，而進多少位，則需要根據具體的定點數類型決定。如二進制定點數下的負數常常會用二補數型式下的有號整數表示，其中隱含著縮放係數（或小數長度）。

舉個例子，8-bit 二進制有號整數 $(11110101)_{2} = - 11$ ，若分別配合 -3, +5 及 +12 的縮放位元，它們的數值即為 $\frac{- 11}{2^{- 3}} = - 88$ 、 $\frac{- 11}{2^{5}} = - 0.34375$ ，和 $\frac{- 11}{2^{12}} = - 0.002685546875$ 。

這也印證了作業文獻中，定點數運算的常見規格：

定點數加法與減法 - 可直接進行
定點數乘法 - 結果須再除 $b^{n}$ (b 為進制，n 為小數位數)
定點數除法 - 結果須再乘 $b^{n}$ (b 為進制，n 為小數位數)

縮放係數（Scaling Factor）的討論及選擇

縮放係數簡單來說，就是用來確定「小數點的位置在該整數型態的哪一位」，即 fractional bits。其是沒有標準格式的，需要因應系統需求，由開發人員自行設定。

一般來說，我們會希望縮放係數越大越好，因為這樣可以增加定點數的範圍和精度。但同時，縮放係數越大，「可以表示的小數部分就越少」，這可能會導致運算過程中的精度損失。

以十進制來舉個例子：假設我們需要處理一組數據，這些數據的範圍在 0 到 1000 之間，並且需要保留至小數點後兩位。我們可以把這些數據「乘以 100」來將它們轉換為定點數，這樣可以將小數點移動兩位，讓數據成為整數。
– 設縮放係數為 100，那把原始數據乘以 100 後，好處是可以保留到小數點後兩位的精度；但同時，整數部分的範圍是 0 到 100000，如果超出了這個範圍，則會造成溢位。
– 設縮放係數為 1000，那把原始數據乘以 1000 後，雖然擴大整數部分的範圍；但同時，我們只能保留到小數點後一位的精度，因為我們將小數點向右移動了一位。

鑒於 double 為 64-bit，且定點數即為整數型態，實作上我想用 stdint.h 中定義的 uint64_t 型態來取代原 score 的 double 型態。另設定縮放位元有 12-bit，即縮放係數為 $2^{12}$ 。

前面提到，縮放係數越大越好，且觀察了相關運算函式（uct_score 及其中的 log 等）後，覺得這樣設定的精度已很夠用，且不會有溢位的問題。

實作定點數操作

首先要先引入 stdint.h，並將相關變數設為 uint64_t。

之後在 game.h 中定義「縮放位元」。

+ #define FIXED_SCALING_BITS 12

先改 game.c 中的 calculate_win_value 函式，其本來的功能很簡單－贏了回傳 1；輸了回傳 0；否則平手，回傳 0.5。只需將其改成定點數的表示數值即可。注意函式回傳值為 uint64_t。

uint64_t calculate_win_value(char win, char player)
{
    if (win == player)
+       return 1ULL << FIXED_SCALING_BITS;
-       return 1.0;
    if (win == (player ^ 'O' ^ 'X'))
+       return 0ULL;
-       return 0.0;
+   return 1ULL << (FIXED_SCALING_BITS - 1);
-   return 0.5;
}

commit 4978029。

接著分別將 select_move、simulate、backpropagate 及 mcts 等函式之 double 相關變數改為 uint64_t。

最後來處理最麻煩的 uct_score 的相關定點數運算－最主要是需要實作定點數的 sqrt 及 log 函式。

sqrt

該函式我用「二分搜尋（逼近）法」來實現。
作法如下：

uint64_t fixed_sqrt(uint64_t x)
{
    if (x <= 1)
        return x;

    uint64_t low = 0ULL;
    uint64_t high = x;
    uint64_t precision = 1ULL << (FIXED_SCALING_BITS - 2);

    while (high - low > precision) {
        uint64_t mid = (low + high) / 2;
        uint64_t square = (mid * mid) >> FIXED_SCALING_BITS;

        if (square < x) {
            low = mid;
        } else {
            high = mid;
        }
    }

    return (low + high) / 2;
}

log

實作 log 的方法有很多種，鑒於不可能用查表法，只能使用相關的近似算法，如牛頓插值法、或泰勒級數展開等。

我使用較廣為使用也較易實現的「泰勒級數展開」來實作定點數的 log 運算。

泰勒展開式，是將一個函數「以多項式來表示」的一種方式。
一多項式函數 $f (x)$ 在 $x = a$ 時， $n$ 階的泰勒展開式 $P_{n} (x)$ 是：
$P_{n} (x) = f (a) + \frac{f^{(1)} (a)}{1!} (x - a)^{1} + \frac{f^{(2)} (a)}{2!} (x - a)^{2} + . . . + \frac{f^{(n)} (a)}{n!} (x - a)^{n} + R_{n} (x)$

而對於對數函數，我們可以使用「自然對數」的泰勒展開式來近似計算。

$l n (1 + x) = x - \frac{x^{2}}{2} + \frac{x^{3}}{3} - \frac{x^{4}}{4} + . . . . . .$

static uint64_t fixed_log(uint64_t x)
{
    uint64_t fixed_x = x << SCALING_BITS;

    if (x == 0) return UINT64_MAX;

    if (x == 1) return 0ULL;

    uint64_t result = 0;

    for (int i = 1; i <= 16; ++i) {
        if (i % 2 == 0) {
            result -= fixed_power_int(fixed_x, FIXED_SCALING_BITS, i) / i;
        } else {
            result += fixed_power_int(fixed_x, FIXED_SCALING_BITS, i) / i;
        }
        fixed_x = (fixed_x * (x << SCALING_BITS)) >> SCALING_BITS;
    }

    return result;
}

對於「 $x$ 的冪次部分」，我借用 fixed_power_int 函式來實現，並修改為 64-bit 的版本以符合情境。

commit 2cd0bf3。

TODO: 驗證其正確性，並與 negamax 比較。

測試後發現我的定點樹版本 MCTS 有問題，沒有實作完全 MCTS 的邏輯，在猜想是否為「變數型態（位元數）」的問題？

電腦 vs. 電腦

在 qtest 中加入藉由 option 命令來調整為電腦 vs. 電腦的選項：

// global variable
int ai_vs_ai = 0;
// in console_init()
add_param("AI_vs_AI", &ai_vs_ai, "Let AI and AI play Tic-Tac-Toe", NULL);

在原本是玩家的回合中，檢測目前是否為電腦 vs. 電腦，如是，則讓 AI 決定下一步：

if (turn == ai) {
    int move = negamax_predict(table, ai).move;
    if (move != -1) {
        table[move] = ai;
        record_move(move);
    }
} 
else 
{
+   if (ai_vs_ai) {  // AI vs. AI
+       int move = negamax_predict(table, turn).move;
+       if (move != -1) {
+           table[move] = turn;
+           record_move(move);
+       }
    } else {  // Player vs. AI
        draw_board(table);
        int move;
        while (1) {
            move = get_input(turn);
            if (table[move] == ' ') {
                break;
            }
            printf("Invalid operation: the position has been marked\n");
        }
        table[move] = turn;
        record_move(move);
    }
}

經過我反覆測試發現，每次的電腦 vs. 電腦對局的過程都會一模一樣。為了讓此對局有變化性，我決定讓先手的電腦隨機選擇第一步。
由 get_input 函式可以知道，玩家輸入的英文字母及數字會被轉變為 { 0 ~ BOARD_SIZE * BOARD_SIZE - 1 } 之間的數字，所以我讓電腦在第一步時隨機選擇範圍內的數字。

bool first_move = true;

if (first_move) {
    move = rand() % (BOARD_SIZE * BOARD_SIZE - 1);
    first_move = false;
}

最後再加入顯示時間的功能，此部分參考 vax-r 同學的程式碼：

draw_board(table);
time_t timer = time(NULL);
struct tm *tm_info = localtime(&timer);

char buffer[26];
strftime(buffer, 26, "%Y-%m-%d %H:%M:%S", tm_info);
puts(buffer);

SuNsHiNe-75

2024/02/24 07:17:08

list_for_each()

/** * list_for_each - Iterate over list nodes * @node: list_head pointer used as iterator * @head: pointer to the head of the list * * The nodes and the head of the list must be kept unmodified while * iterating through it. Any modifications to the the list will cause undefined * behavior. */ #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next)

2024/02/24 07:25:49

list_for_each_entry_safe()

/** * list_for_each_entry_safe - Iterate over list entries and allow deletes * @entry: pointer used as iterator * @safe: @type pointer used to store info for next entry in list * @head: pointer to the head of the list * @member: name of the list_head member variable in struct type of @entry * * The current node (iterator) is allowed to be removed from the list. Any * other modifications to the the list will cause undefined behavior. * * FIXME: remove dependency of __typeof__ extension */ #define list_for_each_entry_safe(entry, safe, head, member) \ for (entry = list_entry((head)->next, __typeof__(*entry), member), \ safe = list_entry(entry->member.next, __typeof__(*entry), member); \ &entry->member != (head); entry = safe, \ safe = list_entry(safe->member.next, __typeof__(*entry), member))

2024/02/24 07:36:04

element_t

/** * element_t - Linked list element * @value: pointer to array holding string * @list: node of a doubly-linked list * * @value needs to be explicitly allocated and freed */ typedef struct { char *value; struct list_head list; } element_t;

修但幾嘞

2024/02/26 11:36:14

if (!(l && !list_empty(l)))

empty queue != NULL queue，所以 empty queue也需要 q_free

2024/02/26 11:38:20

strncpy(sp, rmv_element->value, bufsize);

需在 bufsize 處新增 '\0'

2024/03/02 08:06:36

. - char *cmdline = readline(

從輸入檔案中讀取命令。

2024/03/12 12:11:52

INIT_LIST_HEAD

static inline void INIT_LIST_HEAD(struct list_head *head) { head->next = head; head->prev = head; }

2024/03/12 12:20:39

list_add

static inline void list_add(struct list_head *node, struct list_head *head) { struct list_head *next = head->next; next->prev = node; node->next = next; node->prev = head; head->next = node; }

2024/03/12 12:24:04

list_del

static inline void list_del(struct list_head *node) { struct list_head *next = node->next; struct list_head *prev = node->prev; next->prev = prev; prev->next = next; #ifdef LIST_POISONING node->prev = (struct list_head *) (0x00100100); node->next = (struct list_head *) (0x00200200); #endif }

2024/03/12 12:24:38

list_first_entry

#define list_first_entry(head, type, member) \ list_entry((head)->next, type, member)

2024/03/12 12:26:23

list_last_entry

#define list_last_entry(head, type, member) \ list_entry((head)->prev, type, member)

2024/03/12 12:27:50

list_empty

static inline int list_empty(const struct list_head *head) { return (head->next == head); }

2024/03/12 12:32:11

q_release_element

static inline void q_release_element(element_t *e) { test_free(e->value); test_free(e); }

2024/03/12 12:33:44

list_move

static inline void list_move(struct list_head *node, struct list_head *head) { list_del(node); list_add(node, head); }

2024/03/12 12:39:39

LIST_HEAD

#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

2024/03/12 12:39:57

list_splice_tail_init

static inline void list_splice_tail_init(struct list_head *list, struct list_head *head) { list_splice_tail(list, head); INIT_LIST_HEAD(list); }

2024/03/12 12:41:09

list_cut_position

static inline void list_cut_position(struct list_head *head_to, struct list_head *head_from, struct list_head *node) { struct list_head *head_from_first = head_from->next; if (list_empty(head_from)) return; if (head_from == node) { INIT_LIST_HEAD(head_to); return; } head_from->next = node->next; head_from->next->prev = head_from; head_to->prev = node; node->next = head_to; head_to->next = head_from_first; head_to->next->prev = head_to; }

2024/03/12 12:41:28

list_move_tail

static inline void list_move_tail(struct list_head *node, struct list_head *head) { list_del(node); list_add_tail(node, head); }

2024q1 Homework1 (lab0)

Reviewed by teresasa0731

開發環境

針對佇列操作的程式碼實作

q_new

q_free

q_insert_head

q_insert_tail

q_remove_head

q_remove_tail

q_size

q_delete_mid

q_delete_dup

q_swap

q_reverse

q_reverseK

q_sort

q_ascend

q_descend

q_merge

使用 select 改善 Web 與 Linenoise 之衝突問題

linenoise 理解

select 理解

console.c 理解

解決 linenoise 與 socket 之衝突

命令 shuffle 之實作

Fisher–Yates Shuffle 演算法

實作

測試程式分析

引入 lib/list_sort.c

解釋 Linux 核心的 lib/list_sort.c

merge

merge_final

list_sort

推論：

引入 list_sort 到 lab0-c 當中

list_sort.c

q_test.c

Makefile

比較效能落差

使用 Linux 效能分析工具 perf 進行計算

自己實作的 q_sort

Linux 的 list_sort

研讀論文〈Dude, is my code constant time?〉

解釋 Simulation

解釋 Student's t-distribution

新增 percentile 處理

Tic-tac-toe

引入 hlist.h

新增 ttt 命令

整合 jserv/ttt 完畢

用定點數取代浮點數運算

Monte Carlo Tree Search（MCTS）理解

浮點數之深入探討

定點數之深入探討

縮放係數（Scaling Factor）的討論及選擇

實作定點數操作

sqrt

log

電腦 vs. 電腦

Read more

Building a TCP Server with eBPF

Tracing with Ftrace

Assignment1: RISC-V Assembly and Instruction Pipeline

RISC-V Procedures

Reviewed by `teresasa0731`

`q_new`

`q_free`

`q_insert_head`

`q_insert_tail`

`q_remove_head`

`q_remove_tail`

`q_size`

`q_delete_mid`

`q_delete_dup`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`q_ascend`

`q_descend`

`q_merge`

使用 `select` 改善 Web 與 Linenoise 之衝突問題

`select` 理解

引入 `lib/list_sort.c`

解釋 Linux 核心的 `lib/list_sort.c`

`merge`

`merge_final`

`list_sort`

引入 `list_sort` 到 lab0-c 當中

`list_sort.c`

`q_test.c`

`Makefile`

自己實作的 `q_sort`

Linux 的 `list_sort`

新增 `ttt` 命令