2024q1 Homework1 (lab0)

conftributed by < marvin0102 >

開發環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0

$lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 1600 Six-Core Processor
    CPU family:          23
    Model:               1
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            1
    Frequency boost:     enabled
    CPU max MHz:         3200.0000
    CPU min MHz:         1550.0000
    BogoMIPS:            6387.26

指定的佇列操作

q_new

使用 malloc 配置 struct list_head 的記憶體空間並使用指標 head 來記錄其位置，同時使用 INIT_LIST_HEAD() 來初始化這個佇列的頭部。

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

q_free

使用list_for_each_entry_safe()逐一走訪佇列中的所有entry，並逐個將其刪除，如果佇列的head為NULL則不作任何事，if (entry->value)判斷value是否為空字串，如果value非空字串，則使用free()將其記憶體釋放。

list_for_each_entry_safe(entry,safe,head,member):歷遍佇列中的所有entry並且接受刪除entry

q_insert_head 與 q_insert_tail

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

使用 malloc() 配置記憶體給指標 entry 以及字串 entr->value ，其中 entry->value 的記憶體大小與字串 s 一致，使用 strncpy() 複製 s 到 entry->value 中，並且使用 list_add() 將 entry->list 插置佇列第一個位置。

if (!entry), if (!entry->value) : 檢查 malloc 是否有成功配置記憶體，其中 free(entry) 則是防止 memory leak。

if (!entry->list.next || !entry->list.prev):再提交 git commit 時， Cppcheck 仍檢測出 memory leak，經排查後發現，還需檢查 entry 是否有被成功的新增進佇列中，如果沒有，在離開 function 時，區域指標 entry 會消，但其指向的記憶體並不會，因此造成 memory leak。

bool q_insert_head(struct list_head *head, char *s)
{
    ...
    entry->value[len - 1] = '\0';
    list_add(&(entry->list), head);
+   if (!entry->list.next || !entry->list.prev) {
+       q_release_element(entry);
+   }
    return true;
}

由於功能 q_insert_head() 與 q_insert_head() 相同，只是插入位置不同，因此可以直接呼叫 q_insert_head() ，並將插入位置改為佇列的尾部

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
-   if (!head || list_empty(head))
-       return NULL;
+   return q_remove_head(head->prev->prev, sp, bufsize);
}

q_remove_head 與 q_remove_tail

移除佇列的第一個元素:
將指標 entry 指向佇列的第一個元素，使用 list_del() 將 entry 從佇列中移除(移除予刪除不同，並不會釋放記憶體)，memcpy() 的作用則是將 entry 中字串的內容複製到 sp 中。

strlen() 並不會將'\0'加入字串長度的計算中，因此在最後要自行加入'\0'，同時在作bufsize比較運算的時候也要預留'\0'的位置。

if (entry->value && sp) :在複製字串時，需先檢查字串是否為空，否則會發生複製錯誤。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *entry = list_entry(head->next, element_t, list);
    if (!entry)
        return NULL;
    list_del(&(entry->list));
+   if (entry->value && sp) {
-        strncpy(sp, entry->value, bufsize);
+        size_t len = strlen(entry->value) > (bufsize - 1)
+                        ? (bufsize - 1)
+                        : strlen(entry->value);
+       memcpy(sp, entry->value, len);
+       *(sp + len) = '\0';
+   }
    return entry;
}

q_remove_tail 實作與作與 q_remove_head 相同，只是移除位置不同，因此可以直接呼叫q_insert_head() ，並將移除位置改為佇列的尾部。

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
-   if (!head || list_empty(head))
-       return NULL;
+    return q_remove_head(head->prev->prev, sp, bufsize);
}

q_size

返回佇列的長度:
使用 list_for_each() 逐一走訪佇列，並指用計數器 count 紀錄長度。

if (!head || list_empty(head)) :使用 list_empty() 檢查佇列是否為空或是接收到空指標，如果是，則直接返回。

q_delete_mid

使用快、慢指標找出佇列中的中間元素，當快指標 fast 走訪佇列一次時，慢指標 slow 及為佇列的中間元素，使用 list_del() 將 slow 從佇列中移除， list_entry() 取得佇列的中間元素 entry ，並使用 q_release_element() 將 entry 的記憶體釋放。

q_delete_dup

刪除佇列中重複得元素:
先使用 q_sort() 將佇列排序，這樣相同字串的元素就會被排在一起，只需比對鄰近的元素即可得知元素是否重複。
由於每次比對只會刪除一個元素，當重複的元素只剩一個時，無法透過元素間的相互比對檢查出來，因此須由字串 sp 紀錄重複的字串，並在重複的元素剩最後一個時，將其刪除。

直接使用 list_for_each_safe 逐一走訪佇列。

bool q_delete_dup(struct list_head *head)
{
    ...
-   for (; safe != head; node = safe, safe = node->next) {
+   list_for_each_dafe(node, safe, head){
    ...

    return true;
}

q_swap

交換兩個鄰近node的位置:
使用 pair1 、 pair2 兩個指標指向佇列中的倆個鄰近的 (struct list_head *) node ，並且在走訪佇列的過程中使用 list_move() 交換 pair1 、 pair2 在佇列中的位置。
pair1 = pair1->next, pair2 = pair1->next 則會將 pair1 、 pair2 指向下倆個鄰近的node。

q_reverse

反轉整個佇列:
逐一走訪佇列並且將每個元素分別移至佇列的頭部，在歷遍佇列之後，整個佇列鳩會反轉。
因為需要移動佇列中的元素，因此需要 node 、 safe 兩個指標，並使用list_for_each_safe() 移動佇列中的元素。

list_for_each_safe() :逐一走訪佇列中 (struct list_head *)node ，並且接受刪除

q_reverseK

以k個 node 為一組子佇列，反轉佇列中所有擁有k個 node 的子佇列:
建立一個新的佇列 group ，將原佇列中的元素照順序移入佇列 group 中。
當 group 大小為k時，使用 q_reverse() 將其反轉，並且將整個佇列 group 接回原佇列中。
在走訪佇列所有元素後，將未滿k個元素的 group 接回原佇列中，即完成 q_everseK 的實作。

list_splice_tail_init(List,head) :接收兩個佇列 List 、 head ，將佇列 List 的所有元素插至佇列 head 的尾部，並且初始化佇列 List 。

在此實作中，將指標 safe 作為佇列的起始指標(head of queue)，將 group_head 、 safe 合併，實際上就是將佇列 group 接回原本移出的位置。

q_sort

佇列排序:
此實作以 merge sort 作為主要的排序演算法。
將佇列尾部與佇列起始指標斷開，使其成為單向 linked list，並將其送入 q_divide_helf

q_divide_helf : 遞迴函式，主要作用是將佇列拆解後，送入 merge_two_q() 做排序

merge_two_q : 作用為將兩以排序的佇列合併，使其成為一個以排序的佇列

struct list_head *q_divide_helf(struct list_head *head, bool descend)
{
    ...
    struct list_head *left = q_divide_helf(head, descend);
    struct list_head *right = q_divide_helf(slow, descend);
    return merge_two_q(left, right, descend);
}

/* Sort elements of queue in ascending/descending order */
void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    head->prev->next = NULL;
    head->next = q_divide_helf(head->next, descend);
    struct list_head *node = head, *safe = node->next;
    for (; safe != NULL; node = safe, safe = node->next) {
        safe->prev = node;
    }
    node->next = head;
    head->prev = node;
}

q_acend 與 q_descend

移除比右邊任意元素大(小)的元素，使佇列變為升(降)序:
因為 q_acend 與 q_descend 的功能相同，所以額外社一個函式 descend_ascend()。

由於在逐一走訪佇列時，有可能一次刪除多個元素，因此使用 list_for_each_safe() 有可能會發生 segmentation fault。

int descend_ascend(struct list_head *head, bool ascend)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
-   struct list_head *node, *safe;
+   struct list_head *node = head->next, *safe = node->next;
-   list_for_each_safe(node, safe, head){
+   for (; safe != head; node = safe, safe = node->next) {
    ...
}

在 review <marsh-fish> 時，發現了可改進之處。
在原本的實作中，因為逐一走訪佇列的方向固定，因此當發現不符合 ascned 或 descned 得節點時，除了刪除此點外，還須反向走訪佇列確認以往的節點符合 ascned 或 descned，但此種實作方法會使迴圈複雜度變為

O (n^{2})

。

而<marsh-fish>的實作方法則是因應 ascned 或 descned ，順巷或是反向走訪佇列，使迴圈只須走訪一次即可。
詳細更動在 commit 42a280a

q_merge

合併所有已排序佇列至第一個佇列，並回傳佇列長度:
定義兩個指標 main_q 與 ptr_q，其中 main_q 為主要合併佇列，也就是佇列串中的第一個佇列，而 ptr_q 則指向被合併佇列的 queue_contex_t 指標。

因為佇列起始指標(head of queue)無法比較，且為了在合併時，方便判斷佇列尾部，
main_q->prev->next = NULL; 與 list_entry(ptr_q, queue_contex_t, chain)->q->prev->next = NULL; 的作用就是將佇列尾部與佇列起始指標斷開。

使用 merge_two_q() 將佇列 main_q->next 與佇列 list_entry(ptr_q, queue_contex_t, chain)->q->next 合併，並接回佇列起始指標 main_q 中，完成後將 ptr_q 指向下一個 queue_contex_t 直到所有佇列都被合併。

最後再將佇列尾部與佇列起始指標相連接，即完成所有佇列的合併。

研讀並引入`lib/list_sort.c`

參考筆記

chiangkd

引入`linux/lib/list_sort.c`

因為 lab0-c 缺乏 Linux 核心原始程式碼所需要的標頭檔，所以需要新增標頭檔以及一些相關的巨集。

step 1:
將 list_sort.h、list_sort.c 引入 lab0-c，並刪除無法使用的前置處理指令。

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

step 2:
因為會使用到 likely(x) 、 unlikely(x) 以及 u8 ，因此需要新增定義。

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

struct list_head;
+typedef unsigned char u8;

在 list_sort() 中，需要自定義 compare function cmp。

+int cmp(void *priv, const struct list_head *a, const struct list_head *b)
+{
+    return strcmp(list_entry(a, element_t, list)->value,
+                  list_entry(b, element_t, list)->value);
+}

step 3:
為了要比較實作的 merge sort 與 linux 中的 list_sort() 的效能差異，新增了一個 parameter 使 q_sort() 可以在 merge_sort 與 list_sort() 之間切換。

+ add_param("linuxsort", &linuxsort, "chose q_sort or list_sort", NULL);

將 dudect/cpucycle.h 引入以方便計算不同 sort 之間 cpucycles 的差異。

-if (current && exception_setup(true))
-   q_sort(current->q, descend);
+if (current && exception_setup(true)) {
+    before_ticks = cpucycles();
+    linuxsort ? list_sort(NULL, current->q, &cmp)
+              : q_sort(current->q, descend);
+    after_ticks = cpucycles();
+    report_noreturn(0, "cpucycles : %d", after_ticks - before_ticks);
+    report_noreturn(0, "\n");
+}

最後在 Makefile 中新增 compile file 即完成指令的新增。

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

詳細更改在commit

實驗數據比較

sort	cpu cycles	list length
merge sort	1224608	1000
list sort	465344	1000
merge sort	19797184	10000
list sort	7777664	10000
merge sort	178024288	100000
list sort	170589856	100000

Tim sort 實作與比較

詳細原始碼 commit c78ee94

將 list sort 與 Tim sort 針對不同種類的測資進行較能比較。

使用完全隨機生成的陣列進行排列，結果如下:
接著測試在排序好的陣列中隨機插入一些資料，形成部分排序的資料，結果如下:
使用降續資料進行測試，結果如下:
在資料分佈為 worst case （也就是陣列排序為大小相互間隔時）：

總結

在亂序分佈與 worst case 時，因為 Tim sort 的合併採用 Galloping mode ，期望在 A B 兩 runs 中，找出遺 run 的開頭在另一 run 中的位置，然而在兩 run 的每個節點大小交錯時，會出現多餘的比較次數，因此在排序時間上，效能比 list sort 差。

在資料分佈為部份排序的情況下， Tim sort 能很好的發揮期優勢，無論是升序或是降序排列，Tim sort 在 runs 的分割過程中，能很好的將以排序的子陣列分配到同一 run 當中，從而減少合併次數，達到效能提昇的效果。

沒充分探討，怎麼會有結論？

linenoise 與網頁伺服器的並存原理:

linenoise可做許多行編輯處理，如使用 <tab> 自動補齊命令，歷史命令處理等。

在原作業的敘述中， linenoise 與 cmd_select 分開執行，當程式沒有連接 web 時， stdin 的資料處理是交由 linenoise 處理，然而當開啟 web 連接時，資料的輸入則轉交由 cmd_select 負責。其原因為當開啟 web 時， line_edit 中接收輸入訊息的函式 read 的阻塞會造成程式無法接收 web 訊息的情況。解決辦法為使用函式 cmd_select 中的
select 同時監聽 stdin 、 wedin 的資訊。

從stdin(3) 的敘述：

On program startup, the integer file descriptors associated with
the streams stdin, stdout, and stderr are 0, 1, and 2,
respectively. The preprocessor symbols STDIN_FILENO,
STDOUT_FILENO, and STDERR_FILENO are defined with these values in
<unistd.h>.

以及 read(2)的敘述：

read() attempts to read up to count bytes from file descriptor fd
into the buffer starting at buf.

可以得知， STDIN_FILENO 為 file descriptors ，其資料型別為 int ，可以呼叫函式 read ，以 STDIN_FILENO 作為引數，讀取 stdin 的資料。

select(2)中：

select() allows a program to monitor multiple file descriptors,
waiting until one or more of the file descriptors become "ready"
for some class of I/O operation (e.g., input possible). A file
descriptor is considered ready if it is possible to perform a
corresponding I/O operation (e.g., read(2), or a sufficiently
small write(2)) without blocking.

可以知道， select()允許程式監聽多個 file descriptors。

而管理 file descriptors 則是透過下面定義的聚集來完成：
FD_ZERO()：清空
FD_SET()：新增
FD_CLR()：移除
FD_ISSET()：確認 file descriptor 是否仍被監聽

但這位造成一個問題，就是當 web 連結時，及失去 linenoise 的行編輯處理功能。

在這一次的作業更新中，將 linenoise 與 cmd_select 結合，其實作原理如下：

將 linenoise 移入 cmd_select ，在 cmd_select 中呼叫函式 linenoise ，其返回值為經過處理的命令字串 cmdline，再交由 interpret_cmd 執行命令。
在呼叫 linenoise 之後，程式會陸續呼叫 linenoise -> line_raw -> line_edit ，最後由 line_edit 接收字串並做處理。

同時，因為函式 read 試是在 linenoise 中的 line_edit 等待使用者輸入，因此，select 也必須移入 line_edit 中，作法為使用函數指標。當程式連接 web 時，會呼叫函數 do_web ，在函式 do_web 中，line_set_eventmux_callback 的作用就是將函數指標 web_eventmux 傳入 linenoise 中。

static bool do_web(int argc, char *argv[])
{
    ...
    if (web_fd > 0) {
        printf("listen on port %d, fd is %d\n", port, web_fd);
        line_set_eventmux_callback(web_eventmux);
        use_linenoise = false;
    } 
    ...
}

而函數 web_eventmux 所負責的事情就是使用 select 監聽 file descriptors。

int web_eventmux(char *buf)
{
    fd_set listenset;

    FD_ZERO(&listenset);
    FD_SET(STDIN_FILENO, &listenset);
    int max_fd = STDIN_FILENO;
    if (server_fd > 0) {
        FD_SET(server_fd, &listenset);
        max_fd = max_fd > server_fd ? max_fd : server_fd;
    }
    int result = select(max_fd + 1, &listenset, NULL, NULL, NULL);
    if (result < 0)
        return -1;

    if (server_fd > 0 && FD_ISSET(server_fd, &listenset)) {
        FD_CLR(server_fd, &listenset);
        struct sockaddr_in clientaddr;
        socklen_t clientlen = sizeof(clientaddr);
        int web_connfd =
            accept(server_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);
        strncpy(buf, p, strlen(p) + 1);
        free(p);
        close(web_connfd);
        return strlen(buf);
    }

    FD_CLR(STDIN_FILENO, &listenset);
    return 0;
}

shuffle 指令實作

Fisher–Yates shuffle

Fisher-Yates 演算法主要分三部：

step 1:
在串列中，隨機從[0]~[size-2]中選取一個元素。
step 2:
將選中的元素與最後一個元素([size-1])交換。
step 3:
將串列的長度減1，使隨機選取範圍變成[0]~[size-3]，最後一個元素為[size-2]

重複上述三個步驟直到串列長度變為0，及完成shuffle。

在 `queue.c` 中實現 shuffle:

static inline void swap(struct list_head *node1, struct list_head *node2)
{
+   if (node_1 == node_2)
+       return;
-   struct list_head *node1_prev = node1->prev;
    struct list_head *node2_prev = node2->prev;
-   list_move(node1, node2_prev);
-   list_move(node2, node1_prev);
+   list_del_init(node_2);
+   list_splice_init(node_1, node_2);
+   list_add(node_1, node_2_prev);

}

在原本的 swap() 的實作中，使用兩次 list_move() 須考慮當兩個欲交換的 node 是否為相鄰的 node ，如果是，會因為 list_move() 中的 list_del() 、 list_add() 的位置為同一個 node 而造成 node 無法被成功移入佇列中。

使用 list_splice_init() 實作 swap() 則可以避免個問題。

bool q_shuffle(struct list_head *head)
{
    if(!head || list_empty(head) || list_is_singular(head))
        return false;
    struct list_head *ptr = head;
    int len = q_size(head);
    while(len>0){
        int rindex = rand() % (len);
        struct list_head *last = ptr->prev;
        struct list_head *node = head->next;
        while(rindex--){
            node = node->next;
        }
-       swap(node, last);
+       swap(last, node);
        ptr = ptr->prev;
        len--;
    }
    return true;
}

在使用 swap() 時，須注意交換節點的先後順序問題，避免出現 swap() 時 node 消失的問題。

統計方法測試 shuffle 亂度：

使用 lab0-b測試腳本測試 shuffle() 亂度。

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

〈Dude, is my code constant time?〉

論文中提出了一個工具 dudect ，主要適用於測試 function 執行時間是否為常數時間。

Introduction
Timing attacks 是個利用時間作為媒介的攻擊手法，藉由程式在不同輸入下的執行時間不同，攻擊者便有可能從中洩漏一些重要資訊，像是密碼或是密鑰。因此程式的執行時間是否為常數尤為重要。

時間洩漏測試:

測試執行時間:

Classes definition:
洩漏檢測的方法是將程式執行兩組不同的資料並分別記錄執行時間，再檢查兩組執行時間在統計學上是否存在差異。洩漏檢測有許多不同的類型，主要差異在於兩種不同的輸入資料類別定義。本論文選用固定與隨機資料作為洩漏測試的測資。
固定與隨機洩漏測試將資料分為兩組，第一組是固定不變的常數資料，第二組則是每次測試都不同的隨機資料。固定測試可以用於觸發特定的極端狀況。

Cycle counters:
執行時間需要透過記錄 Cpu cycles 計算，現今的 CPU 都配備了週期計數器，可提供準確的執行時間測量值，而低階處理器可以使用計時器或外接設備。

Environmental conditions:
為了將環境因素的影響降到最低，在每次測試對應一個隨機選擇的類別序列。

資料前處理:

在進行統計分析前，對測試資料進行後處理是常見的步驟。

資料裁切:
執行時間分布會呈現正偏態 (positively skewed) ，這有可能是因為作業系統或是其他執行序所引起的中斷所致。在這種情況下，裁切測量值是一種處理方式，可刪除超過特定、與類別無關的閾值的測試值。

Higher-order preprocessing:
在統計測試時，可以使用高階預處理方法（例如，中心化乘積，模擬高階DPA攻擊）

統計分析測試:

使用統計分析測試資料事是否推翻虛無假說(null hypothesis)，這裡是指兩時間分布是否相同，論文中提及的統計模型有兩種。

t-test:
司徒頓t 檢定(student t-test) ，此論文使用Welch's t-test實作。

無母數統計測試 ( Non-parametric tests ):
無母數統計測試通常使用的統計量的抽樣分配與母體分配無關，不必假設資料的特定分佈，適用於母體分布未知、樣本數小、母體分佈不為常態或不易轉換為常態的情況。

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

解釋 simulation 運作原理

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

在常數時間測試 trace-17-complexity.cmd 中，會透過 option simulation 1 將測試模式打開。
隨後透過 it、ih、rh、rt 命令，分別測試 q_insert_tail、q_insert_head、q_remove_head、 q_remove_tail 是否為常數執行時間。

我們可以先從 qtest.c 中的 do_ih 函數得知，在執行 ih 指令時，會呼叫 queue_insert() 函數。
其測試的運作是透過呼叫 is_insert_head_const() 函數以檢驗測試是否通過。

/* insert head */
static bool do_ih(int argc, char *argv[])
{
    return queue_insert(POS_HEAD, argc, argv);
}

在 queue_insert() 可以得知，當全域變數 simulation 為1時，開啟測試模式，
其測試的運作是透過呼叫 is_insert_head_const() 函數以檢驗測試是否通過。

static bool queue_insert(position_t pos, int argc, char *argv[])
{
    if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        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;
    }

在 constant.h、fixture.h 中，使用了聚集( Macro)定義了此類函數。
（#）的功能是將其後面的巨集引數進行字串化操作，而(##)的作用是字串的銜接。

constant.h

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

fixture.h

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

在 constant.c 中，measure() 函數的作用是測試指令 it、ih、rh、rt 是否運作正常，
而主要的測試則是在 fixture.h 的 report() 函數中。

    /* Definitely not constant time */
    if (max_t > t_threshold_bananas)
        return false;

    /* Probably not constant time. */
    if (max_t > t_threshold_moderate)
        return false;

    /* For the moment, maybe constant time. */
    return true;

透過檢查 t 統計值 max_t 是否超過閾值來判斷

Student's t distribution 原理及實作:

關於Welch's t-test的實作被寫在ttest.c。
按照 Welch's t-test 中 t-value 的計算公式如下:

t = \frac{Δ \bar{X}}{s_{Δ \bar{X}}} = \frac{{\bar{X}}_{1} - {\bar{X}}_{2}}{\sqrt{s_{{\bar{X}}_{1}}^{2} + s_{{\bar{X}}_{2}}^{2}}} $ $ s_{{\bar{X}}_{1}} = \frac{s_{i}}{\sqrt{N}} $ 其 中 $ {\bar{X}}_{i} $ 、 $ s_{{\bar{X}}_{i}}

分別為第

i

比測資的平均值和標準差
t-value 值越小，代表兩組測試分布越接近

在 ttest.h 定義了結構體 t_context_t

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
} t_context_t;

並且，使用 t_push() 函數在每筆測試結束時更新兩組測試分布的平均值和標準差，
最後，使用 t_compute() 函數計算 t-value。

double t_compute(t_context_t *ctx)
{
    double var[2] = {0.0, 0.0};
    var[0] = ctx->m2[0] / (ctx->n[0] - 1);
    var[1] = ctx->m2[1] / (ctx->n[1] - 1);
    double num = (ctx->mean[0] - ctx->mean[1]);
    double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
    double t_value = num / den;
    return t_value;
}

測試時，會透過 fixture.c 中 test_const() 進行 TEST_TRIES = 10 輪的測試，呼叫doit() ，在 doit() 中每次測試會經由 measure() 執行程式並且記錄下執行時間。

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():

            before_ticks[i] = cpucycles();
            dut_insert_head(s, 1);
            after_ticks[i] = cpucycles();

最後會在 report() 中，計算 t-value 並透過 fabs() 取絕對值成為 max_t ，當max_t 大於特定閾值時，及判定程式的執行時間並非常數時間。

percentile implement

在 oreparaz/dudect 中，所有的測資都是一起處理，在最後檢查是否為常數時間時才會區分測資的類別，而 lab0-c 中從一開始就分開處理，因此 struct t_context_t 需要做些微更改。

    typedef struct {
        double mean[2];
        double m2[2];
        double n[2];
+       int64_t *percentiles;
    } t_context_t;

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

在 fixture.c 中新增 percentile() 函式，並且 updeate_statistics() 中做 croping 分離極端值。

    for (size_t i = 0; i < N_MEASURES; i++) {
        int64_t difference = exec_times[i];
        /* CPU cycle counter overflowed or dropped measurement */
-       if (difference <= 0)
+       if (difference >= t->percentiles[i])
            continue

詳細改動在commit

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

留意詞彙的使用：

書寫規範：

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

~~好的老師，我再改進~~

沒做到的事，不要輕易宣稱。

shannon entropy 與亂度產生器:

"亂數" 是指一種無法預測其結果的事件或數值序列。在統計學中，我們可以通過機率分佈來描述隨機事件的結果，以及事件在某個範圍內發生的機率。另一方面，我們也可以通過資訊量來評估隨機性，即在某個事件發生時所包含的信息量。

資訊本體(Information content)，又稱為 self-information，指的是當我們接收到一個消息時所獲得的資訊量，當機將發生的事件機率為 100% 那麼這個事件的資訊量極為 0 ，相反的，當事件的發生機率越低，那麼該事件的資訊量則越高，因此一個隨機事件

x

只與事件發生的機率相關。因為隨機事件彼此獨立，又資訊本體只與機率相關，因此資訊本體是可以相加的。

當我們觀察資訊本體時，發現他有兩特性：

當事件發生機率越低，資訊本體所獲得的資訊量越高
資訊本體是可以相加的

而對數函數

l o g

恰好符合這個特性，因此我們可以將資訊本體函數定義為：

I (P (x)) = l o g (1 / P (x))

其中，

I

為資訊本體函數、

P

為機率函數、

x

為隨機事件，此定義符合

資訊本體與機率成反比，且當機率為 1 時，資訊本體為 0
兩隨機事件 a 與 b 的交集 c ，其資訊本體為
$I (P (c)) = I (P (a)) + I (P (b))$

而熵（Entropy），其實就是資訊本體的期望值，代表所接收的每則消息平均的資訊量（也可以理解為亂度，當一則訊息越混亂，期熵越高）。

H (X) = \sum_{x \in X} P (x) * I (P (x))

我們可以由熵來計算亂亂度，由上面公式可知，熵最大的情況為，所有隨機事件都是平均分佈，也就是 uniform distribution ，此時

H (X) = 1 / n * P (x_{1}) + 1 / n * P (x_{2}) + . . . + 1 / n * P (x_{n})

極為最大值。

我們也可由編碼與資料壓縮的較度來理解熵，在熵的維基百科中有舉一個例子：

Example
Information theory is useful to calculate the smallest amount of information required to convey a message, as in data compression. For example, consider the transmission of sequences comprising the 4 characters 'A', 'B', 'C', and 'D' over a binary channel. If all 4 letters are equally likely (25%), one can not do better than using two bits to encode each letter. 'A' might code as '00', 'B' as '01', 'C' as '10', and 'D' as '11'. However, if the probabilities of each letter are unequal, say 'A' occurs with 70% probability, 'B' with 26%, and 'C' and 'D' with 2% each, one could assign variable length codes. In this case, 'A' would be coded as '0', 'B' as '10', 'C' as '110', and 'D' as '111'. With this representation, 70% of the time only one bit needs to be sent, 26% of the time two bits, and only 4% of the time 3 bits. On average, fewer than 2 bits are required since the entropy is lower (owing to the high prevalence of 'A' followed by 'B' – together 96% of characters).

當初在看這個例子的時候讓我聯想到 Optimal Code Tree ，因此我想用 Optimal Code Tree 來解釋這個例子。

假設今天有四個字元需要編碼，分別為 'A' 、 'B' 、 'C' 、 'D'，且出現的機率分別為 70%、26%、2%、2%，當我們依照這個機率建構出一個 Optimal Code Tree 時，如下：

當我們依照 Optimal Code Tree 進行編碼， Tree 的左邊為 '0' ，右邊為 '1' ，編碼過後，'A' = '0' 'B' = '10' 'C'='110' 'D'='111'，因為 'A' 的出現機率最高，為了解碼的效率，會盡量讓 'A' 的編碼長度越短越好，相反的 'C' 與 'D' 的出現機率非常低，因此編碼長度較長。
從熵的角度來看的話，因為'0'和'1'所能攜帶的訊息量相同，因此我們可以從編碼長度看出每個字元之熵的大小，因為 'C' 與 'D' 出現的機率非常小，因此資訊量較多，編碼也較長。

然而，當 'A' 、 'B' 、 'C' 、 'D' 出現的機率均為 0.25 時，此時的 Optimal Code Tree 如下：

四個字元的編碼長度均為 2 ，code tree 搜尋成本為

2 * 0.25 + 2 * 0.25 + 2 * 0.25 + 2 * 0.25 = 2

，與上個例子的鄒尋成本 1.34 比，搜尋成本明顯較高。
以熵值得角度，與上個例子相比，這個例子的熵值較高。

當資料的熵越高時，我們需要足夠多的位元來攜帶這些資訊，也就較難壓縮，相反的，當一組資料非常有規律時，這組資料的熵就會很低，我們就可以用這些規律進行編碼與資料壓縮。

程式原理：

在 shannon_entropy.c 中，函式 shannon_entropy 的作用是接受一字串作為引數，計算該字串的熵值，原理為：

藉由 count 紀錄該字串的長度，並使用 bucket 紀錄字串中的每個字元出現的次數，最後 p 則為該字元出現的機率。

            uint64_t p = bucket[i];
            p *= LOG2_ARG_SHIFT / count;

shannon_entropy 的機率計算類似於定頂數計算，LOG2_ARG_SHIFT = (1<<16) 的作用是將機率 bucket[i]/count 左移 16 位元，目的是不希望計算機率時出現小數，期結果等於獲得一個精確度為 16 位元的定點數。

entropy_sum /= LOG2_ARG_SHIFT;

在熵計算完成後，結果除以 LOG2_ARG_SHIFT 將定點數轉換回浮點數。

實驗：

l = [aaabbccccc(17.19%) aaaaaaa(0.00%) bajhgeidcf(39.06%) abcdefghij(39.06%)]

從實驗可知， shannon entropy 的大小只跟字元的出現頻率有關，與出現順序無關。
當每個字元的平均出現頻率越低時，熵值越高。

疑問：

從函式 log2_lshift16 的註解可知，函式的作用是對定點數作以 2 為底的對數運算，但是實際帶值計算後，所得出的結果並不是 2 的對數。從原始碼分析，函式的原理為 Binary Search Tree ，且符合對數函

l o g

規則：

當輸入是 1 的定點數時，返回的結果為 0
定點數越小，返回的負值就越大

此規則符合熵的計算需求。

從使用 Binary Search Tree 可以得知此函式只能估算對數，且搜尋條件的多寡及範圍決定對數的精確程度。從實驗可以得知此函式並非計算以 2 為底的對數，但實際運作原理仍尚待釐清。

number p : 0.125000
fix point : 8192
log of p : -23

tic-tac-toe

詳細原始碼請見 commit ec39e6e

Monte Carlo tree search

MCTS 通常被應用於零和博弈（zero-sum games），其中兩個對手互相競爭，並且每個玩家的利益是對方的損失，反之亦然。該算法被廣泛應用於象棋、圍棋、五子棋等棋類遊戲，以及其他類型的博弈遊戲。

在 MCTS 中，通常使用 playout 評估一個遊戲狀態的價值（獲勝機率），playout 的作法為模擬在給定的局面下進行一系列的隨機走法，直到遊戲結束，隨後我們就可以通過遊戲結果（勝、負、和）來評估這個局面的優劣。

MCTS 在每一次的疊代一共會有 4 步，分別為：

Selection
Expansion
Simulation
Backpropagation

選擇節點 Selection：

從根節點開始，按照一定策略選擇一個子節點，直到達到葉節點。根節點為現在的遊戲狀態，葉節點為其中一個可能的遊戲局面，且尚未經過 playout。節點的選擇非常重要，如果單純只選擇獲勝機率高的節點走訪，則有可能忽略掉其他獲勝的可能性，因此需要在走訪獲勝機率最高的節點與探索其他未走訪過得節點中做平衡。

UCT (Upper Confidence Bound 1 applied to trees) 為其中一種平衡方法，通過計算 UCB 值並且走訪 UCB 值教高的節點來搜索遊戲樹，USB 計算公式如下：

\frac{w_{i}}{n_{i}} + c \sqrt{\frac{l n N_{i}}{n_{i}}}

其中，

w_{i}

為從

i

節點出發的獲勝次數，

n_{i}

為從

i

節點出發的 Simulation 次數，

N_{i}

為從根節點出發的 Simulation 次數，

c

為常數，通常為

\sqrt{2}

。

從公式中我們可以得知，UCB 結合了兩個因素：節點被訪問的次數（用於評估節點的探索度）和節點的平均獲勝率（用於評估節點的價值）。當該節點的探索次數越多，UCB值就越低，從而導向去走訪那些尚未探索的節點。通過綜合考慮這兩個因素，UCT算法能夠在探索未知節點和利用已知節點之間找到平衡，從而幫助 MCTS 更有效地搜索遊戲樹。

擴展節點 Expansion：

當被選中的節點已經進行過 playout 時，我們節可對該節點進行擴展，作法為列出該節點下一步的所有可能，並紀錄為該節點的子節點。

模擬 Simulation：

如果被選中的節點尚未進行 playout ，則對該節點進行 playout ，即模擬在給定的局面下進行一系列的隨機走法，直到遊戲結束。

回傳 Backpropagation：

如果被選中的節點進行了 playout ，則從葉節點至跟節點更新模擬結果。

通過反復執行這四個步驟，MCTS 可以在有限的時間內對可能的行動空間進行有效的搜索，並找到最優的決策。

定點數運算:

定點數運算中， Q notation 是一種指定二進制定點數參數的方法。

Qf：稱作「Q 格式」，Q15 表示 15 個小數位。這樣的記法存在歧義，因為沒有包含字長，但實際使用時一般可以根據目標處理器平台判斷字長為 16 或者 32 位。
Qm.f：無歧義的 Q 格式，因為整個字是二補數，所以符號位長度可以根據其它資訊推導而來。例如 Q1.30 表示該數有 1 個整數位、30 個小數位，是 32 位二補數。

假設我們將 fraction bit 設為

d

，則一定點數

N

的實際值為

\frac{N}{d}

因此當我們在做頂點數的加減時可以直接相加。

(N_{1} + N_{2}) \div d = \frac{N_{1} + N_{2}}{d}

(N_{1} - N_{2}) \div d = \frac{N_{1} - N_{2}}{d}

但是如果對於定點數的乘除不多加處理的話，結果會變為：

(N_{1} * N_{2}) \div d = \frac{N_{1} * N_{2}}{d}

(N_{1} / N_{2}) \div d = \frac{N_{1} / N_{2}}{d}

顯然與預期的結果不同，因此在計算完定點樹的乘除之，需要額外對積數與商數右移或左移

d

位

\frac{(N_{1} * N_{2})}{d} \div d = \frac{N_{1} * N_{2}}{d^{2}} = \frac{N_{1}}{d} * \frac{N_{2}}{d}

\frac{(N_{1})}{N_{2} * d} * d = \frac{N_{1}}{N_{2}} = \frac{N_{1}}{d} / \frac{N_{2}}{d}

定點數的log計算：

定點數計算 UCB 時，因為會對走訪次數做對數與平方根計算，因此須設計 log 與 sqrt 的定點數運算。

嘗試使用泰勒展開實作自然對數的計算，公式如下：

l n (x) = 2 \cdot ((\frac{x - 1}{x + 1}) + \frac{1}{3} (\frac{x - 1}{x + 1})^{3} + \frac{1}{5} (\frac{x - 1}{x + 1})^{5} \dots)

但在實驗時發現使用泰勒展開，當數字越大時，誤差越大，且需要越多的項次才能做精準的估算，
且經過實驗，fraction bits 的精度會很大影響泰勒展的準確度。

上圖為使用 Q23.8 實作泰勒展開求自然對數的實驗結果。

上圖為使用 Q15.16 實作泰勒展開求自然對數的實驗結果。

實際實驗，將 UCB 去除無限大之後，最大值約為 3.537272，而總訪問次數

N_{i}

最大為 99999。
因此，當計算 UCB 時最大會需要對 99999 取 log ，因此，使用泰勒展開出現的誤差極大。

上圖為使用 Q15.16 實作泰勒展開求 1~1000 的自然對數的實驗結果。

為了改善泰勒展開數字越大時誤差越大的問題，嘗試改用歐拉方法（Euler method）求 log 的近似值，歐拉方法是對於

l o g (x)

，使用兩的近似的數

l o g (A)

、

l o g (B)

，求其近似值，其中

A <= x <= B

，方法如下：

我們計算

C = \sqrt{A B}

，因為

l o g (C) = l o g (\sqrt{A B}) = \frac{1}{2} (l o g (A) + l o g (B))

，因此我們可以的到

l o g (C)

為

l o g (A)

、

l o g (B)

的平均。

接著比較

x

與

C

，如果

x = C

及得到我們所求，如果

x < C

，我們則將

B

替換成

C

，如果

x > C

，我們則將

S A

替換成

C

，繼續下一輪的求近似。

因為求近似值時，須先知道

l o g (A)

、

l o g (B)

的實際值，因此實作時，將以

l o g_{2} (x)

做計算，且

A

B

分別為

2^{m}

2^{(} m + 1)

，其中

2^{m} <= x <= 2^{(} m + 1)

。

實作如下：

Q23_8 fixed_log(int input)
{
    if (!input || input == 1)
        return 0;

    Q23_8 y = input << Q;  // int to Q15_16
    Q23_8 L = 1L << ((31 - __builtin_clz(y))), R = L << 1;
    Q23_8 Llog = (31 - __builtin_clz(y) - Q) << Q, Rlog = Llog + (1 << Q), log;

    for (int i = 1; i < 20; i++) {
        if (y == L)
            return Llog;
        else if (y == R)
            return Rlog;
        log = fixed_div(Llog + Rlog, 2 << Q);

        int64_t tmp = ((int64_t) L * (int64_t) R) >> Q;
        tmp = fixed_sqrt((Q23_8) tmp);

        if (y >= tmp) {
            L = tmp;
            Llog = log;
        } else {
            R = tmp;
            Rlog = log;
        }
    }

    return (Q23_8) log;
}

上圖為使用 Q23.8 實作歐拉方法的結果

上圖為使用 Q15.16 實作歐拉方法的結果

上圖為使用 Q23.8 實作泰勒展開求 1~1000 的自然對數的實驗結果。

從實驗結果可以看出，使用歐拉方法時，定點數的精度並不會影響其準確度，且不會有隨著數字越大誤差越大的缺點。

但因為在求近似時，會先經過

A B

的計算，當

A

、

B

數字及大時，會存在 overflow 的問題。

定點數的sqrt計算：

此處，利用第三周測驗一的方法實作，並且轉為定點數。
實作如下：

Q23_8 fixed_sqrt(Q23_8 x)
{
    if (x <= 1 << Q) /* Assume x is always positive */
        return x;

    Q23_8 z = 0;
    for (Q23_8 m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;
    }
    z = z << Q / 2;
    return z;
}

以下為實驗結果：

實作程式碼 commit 1104fb1
參考筆記 vax-r

電腦對電腦：

一開始先使用參考並行程式設計: 排程器原理中，coro.c 的實作方式，使用 setjmp 、 longjmp 的方式實作排程器，並設定了三個任務進行排程， task1 為 mcts 演算法、 task2 為 negamax 演算法、 task3 則隨時監聽鍵盤輸入，在接收到輸入為 ctrl-p 、 ctrl-q 時，暫停輸出或結束對弈。

閱讀 Details of Non-Local Exits 後，了解 setjmp 與 longjmp 的運作原理。setjmp 與 longjmp 都接收一個 Data Type jmp_buf 的參數，當地一次呼叫 setjmp 時，函式會將目前程式的狀態存入 jmp_buf 中，並且回傳 0 ，而 longjmp 的作用是恢復 jmp_buf 所除存的程式狀態，並且呼叫 setjmp 繼續執行該程，當 setjmp 被 jmp_buf 呼叫時，回傳非 0 值。

實作模仿 coro.c 的方式，先使用 schedule() 呼叫每個任務，而函式使用 task_add 將函式的 jmp_buf 排程陣列中，最後使用 task_switch 執行排程陣列中的函式。

但在顯示時間時，因為 setjmp 、 longjmp 為協同式多工，無法符合時間顯示的即時需求，因此後來改用 preempt coroutine 的方式實作排程器。實作參考 task_sched.c 。

疑問：
驗研讀完程式碼後，理解程式是利用 ualarm 在固定時間區間觸發檢查點，實現程式搶佔，但仍不清楚程式如何決定函式的優先權即函式如何發出搶佔請求？

將顯示時間作為第四個任務，加入排程器中，並且在輸入指令與顯示時間時，參考Build Your Own Text Editor ，使用 RawMode 對輸入輸出進行調整。











void enableRawMode()
{
    tcgetattr(STDIN_FILENO, &E.orig_termios);
    struct termios raw = E.orig_termios;
    atexit(disableRawMode);
    raw.c_iflag &= ~(IXON);
    raw.c_lflag &= ~(ECHO | ICANON);
    raw.c_cc[VMIN] = 0;
    raw.c_cc[VTIME] = 1;
    tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
}

RawMode 的具體調整如下，將 ECHO 取消，使鍵盤輸入不會直接顯示在 terminal 中，取消 ICANON 使得 read() 不必等待 '\n' 即可直接接收字元， raw.c_iflag &= ~(IXON); 的作用是取消控制字元 ctrl-q ，使 read() 可以接收到字元 ctrl-q。

在時間顯示的實作中，主要的流程如下：

使用 getCursorPosition 獲取目前函式在 terminal 中的座標
snprintf(buf, sizeof(buf), "\x1b[%d;%dH", E.cy + 1, 0); 的作用為將游標移至該列的最左邊
abAppend(ab, "\x1b[2K", 4); 將游標右方的內容刪除
最後顯示目前時間

詳細程式碼 commit 0a3c37b