# 2025q1 Homework1 (lab0)
contributed by < [Mike1117](https://github.com/Mike1117/) >

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          48 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   16
  On-line CPU(s) list:    0-15
Vendor ID:                AuthenticAMD
  Model name:             AMD Ryzen 7 8845HS w/ Radeon 780M Graphics
    CPU family:           25
    Model:                117
    Thread(s) per core:   2
    Core(s) per socket:   8
    Socket(s):            1
    Stepping:             2
    Frequency boost:      enabled
    CPU(s) scaling MHz:   29%
    CPU max MHz:          ha5137.0000
    CPU min MHz:          400.0000
    BogoMIPS:             7585.59

## 進度記錄
### 以下複製自「[作業要求](https://hackmd.io/@sysprog/linux2025-lab0-f#-%E4%BD%9C%E6%A5%AD%E8%A6%81%E6%B1%82)」
- [x] 在 GitHub 上 [fork](https://github.com/sysprog21/lab0-c) `lab0-c`
- [x] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 `make test` 自動評分系統的所有項目。
- [x] ⚠️ 在提交程式變更前，務必詳閱 [如何寫好 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)
- [x] 詳閱 [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list) 並應用裡頭提及的手法，例如 pointer to pointer (指向某個指標的指標，或說 indirect pointer)，讓程式碼更精簡且有效
- [ ] 參閱 [2023 年 Linux 核心設計課程第一次作業檢討](https://hackmd.io/@sysprog/linux2023-lab0-review)，留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越四千萬行的 Linux 核心
- [ ] 研讀 [Linux 核心原始程式碼](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
- [ ] 詳閱 [改進 `lib/list_sort.c`](https://hackmd.io/@sysprog/Hy5hmaKBh)（含解說錄影）
- [x] 在 `qtest` 提供新的命令 `shuffle`，允許藉由 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) 演算法，對佇列中所有節點進行洗牌 (shuffle) 操作，需要以統計的原理來分析你的實作，探究洗牌的「亂度」
- [ ] 在 `qtest` 中執行 `option entropy 1` 並搭配 `ih RAND 10` 一類的命令，觀察亂數字串的分布，並運用「資訊與熵互補，資訊就是負熵」的觀念，設計一組新的命令或選項，得以在 `qtest` 切換不同的 PRNG 的實作（可選定 [Xorshift](https://en.wikipedia.org/wiki/Xorshift)），搭配統計分析工具，比較亂數產生器 (如 Xorshift vs. 內建) 的品質
- [x] 參見: [由大數法則理解訊息熵 (entropy) 的數學意義](https://hackmd.io/@8dSak6oVTweMeAe9fXWCPA/ryoegPgw_)
- [x] 參見: [The Linux Pseudorandom Number Generator Revisited](https://eprint.iacr.org/2012/251.pdf)
- [x] 研讀論文 [Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)，解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析，達到驗證時間複雜度，需要解釋 [Student's t-distribution](https://en.wikipedia.org/wiki/Student%27s_t-distribution) 及程式實作的原理。
- [ ] 指出現有程式的缺陷或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API)，嘗試實作並提交 pull request
- [ ] 除了修改程式，也要建立 HackMD 筆記，增添開發紀錄和 GitHub 連結，除了提及你如何逐步達到自動評分程式的要求外，共筆也要涵蓋以下:
- [ ] 詳閱第 1 週所有教材及作業描述 [(一)](/@sysprog/linux2025-lab0-a), [(二)](/@sysprog/linux2025-lab0-b), [(三)](/@sysprog/linux2025-lab0-c), [(四)](/@sysprog/linux2025-lab0-d), [(五)](/@sysprog/linux2025-lab0-e)，記錄你的啟發和疑惑
- [ ] 開啟 [Address Sanitizer](https://github.com/google/sanitizers/wiki/AddressSanitizer)，修正 `qtest` 執行過程中的錯誤
- [ ] 運用 Valgrind 排除 `qtest` 實作的記憶體錯誤，並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量，需要設計對應的實驗
- [ ] 解釋 [select 系統呼叫](http://man7.org/linux/man-pages/man2/select.2.html) 在本程式的使用方式，並分析 [console.c](https://github.com/sysprog21/lab0-c/blob/master/console.c) 的實作，說明其中運用 CS:APP [RIO 套件](http://csapp.cs.cmu.edu/2e/ch10-preview.pdf) 的原理和考量點。可對照參考 [CS:APP 第 10 章重點提示](https://hackmd.io/@sysprog/CSAPP-ch10)
- [ ] 填寫 [Google 表單](https://forms.gle/) 提交程式碼和開發紀錄，當系統檢查完畢時，預期將在 [作業區](https://hackmd.io/@sysprog/linux2025-homework1) 見到登記的 HackMD 與 GitHub 超連結
- [ ] 截止日期：Mar 11, 2025 (含) 之前
- 越早在 GitHub 上有動態並及早接受 code review 且持續改進者，評分越高
:::spoiler 檢查事項
### N03 作業要求
- [ ] 檢查事項 1: 確認分析 Linux 核心的 lib/list_sort.c 實作並評估其效益、針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式，該設計對應的排序測試實驗方案
- [ ] 檢查事項 2: 閱讀指定的論文〈Dude, is my code constant time?〉及列於 lib/list_sort.c 修改紀錄 (即 commit b5c56e)中的 3 篇論文，闡述你的洞見，需要指出論文和現有 Linux 核心原始程式碼不同的地方，並予以討論，過程中該有對應的效能分析實驗。參考 CPython 的 listsort 的說明文件，對不同的資料分佈進行測試
- [x] 檢查事項 3：請先詳讀〈Git 教學與 GitHub 設定指引〉（包含解說錄影），接著使用 git fetch 命令以取得 sysprog21/lab0-c 的最新更新，並利用 git rebase 將你已提交的 commit 移至 3 月 18 日或之後的更新之上。注意：在操作過程中可能會出現衝突，需自行解決。此外，請確保所有 commit 訊息皆符合〈How to Write a Git Commit Message〉的規範，必要時可使用 git rebase -i 命令進行修改，最終再以 git push --force（請務必謹慎操作）將更新公開推送至 GitHub。確保你在 rebase 時，基底包含 commit 4a2ff9f
- [ ] 檢查事項 4: 確保符合指定的書寫規範，技術用語依循〈資訊科技詞彙翻譯〉，並針對授課教師的要求，以清晰、明確，和流暢的漢語書寫。倘若你選擇用英語書寫開發紀錄，則依正式英語技術報告慣例。
- [ ] 檢查事項 5: 針對現有 (及自己的) 程式碼，提出可重用程度更高、效能更好，且更安全的實作，過程中應有對應的實驗及分析。過程中，應查閱 C 語言規格書 (原文) 及 The Linux Programming Interface
- [ ] 檢查事項 6: 研讀 select(2) 並探討 sysprog21/lab0-c 如何偵測程式執行的超時、現有的網頁伺服器如何與 linenoise 並存，以及相關的 signal(7) 使用方式。
- [ ] 檢查事項 7: 使用 valgrind, massif, gdb, perf 等課程提及的開發量化程式碼執行時期的資訊，應分析記憶體開銷、執行的指令 (instruction) 數量、cache 表現，和程式熱點 (hotspot)，並予以改進，過程中應有充分的實驗紀錄及討論。
- [ ] 檢查事項 8: 紀錄研讀第 1 到第 4 週課程教材的發現和疑惑，描述於上述開發紀錄，之後授課教師和其他學員會參與討論。
- [ ] 檢查事項 9: 改寫 lab0-c 既有的 shannon_entropy.c 和 log2_lshift16.h，採用更有效、
- [ ] 檢查事項 10: 針對 sysprog21/lab0-c 專案，提交 pull request 以修正你在作業過程中發現的缺失和提出改進，並於 GitHub 進行 code review
- [ ] 檢查事項 11: 詳閱〈Teach Yourself Programming in Ten Years〉，闡述你的認知和發現，並描述你在本課程發現可對應到該文章的觀點。
:::
## 實作 `queue.[ch]`

#### q_new()
>[Commit fc2f58c
](https://github.com/sysprog21/lab0-c/commit/fc2f58c5a0a4e747f5d1c9514a25404dce09ff22)

使用 `malloc()` 為 list 的 Dummy head 配置記憶體空間，若成功則呼叫 `INIT_LIST_HEAD` 初始化並回傳，失敗則回傳 `NULL` 。
#### q_free()
>[Commit a0800a1](https://github.com/sysprog21/lab0-c/commit/a0800a108d17709062ef63ab07611f047a7203e3)

使用 `list_for_each_entry_safe` 逐一走訪每個節點，再呼叫 `q_release_element` 釋放每一節點的記憶體空間，最後釋放 `head` 之記憶體空間。

#### q_insert_head() & q_insert_tail()
>[Commit 5a1e92d](https://github.com/sysprog21/lab0-c/commit/5a1e92d204b5e8928ff35a078b09700f774d8126)
>>[Commit 6825af7](https://github.com/sysprog21/lab0-c/commit/6825af7373616fe436d08a3e5fe378e7278c339b)

此二函式為插入一個新的節點至 list 的頭部或尾端。
首先需要為新節點配置記憶體空間，再用 strdup() 將節點的值設為傳入之字串 s 。
再呼叫 API 將這個節點插入頭部或尾端。

#### q_remove_head() & q_remove_tail()
>[Commit d53fd2d](https://github.com/sysprog21/lab0-c/commit/d53fd2da61e6b3fa292589b991f7a6abf2658d9a)

`queue.h` 中的描述提到 `"remove" is different from "delete"` 。
故此處僅需將節點從頭部或尾部 unlink ，同時回傳節點的值即可。
首先透過 API 獲得首個或尾端節點的指標，再利用 `list_del` 將其 unlink ，再將節點的值 copy 至傳入之字串 sp 。
需要注意的是，此處傳入之字串 s 有規定大小 bufsize ，故 copy 後需要根據 bufsize 截斷字串，使其符合大小。

#### q_size()
>[Commit d6f9638](https://github.com/sysprog21/lab0-c/commit/d6f9638e705c670715652a5d791e46641dbfebce)
>
呼叫 `list_for_each ` 來逐一走訪每個節點，並以一 Counter 計算迴圈的次數，最後回傳該 Counter 的值就是此 queue 的 size 。

#### q_delete_mid()
>[Commit c9df97d](https://github.com/sysprog21/lab0-c/commit/c9df97dba49749f23417d693cb98a487b30a453c)

在第一次實作時，我選擇先以 `q_size` 獲取 queue 的長度，再除以 2 以獲得中間節點的 index ，最後 unlink 及 free 該節點。
>>[Commit 612841d](https://github.com/sysprog21/lab0-c/commit/612841ddd41e810a9ac838010a643d404256826b)

在第一次實作中我發現我的 `+1` 放錯位置，故修改。
>>>[Commit 9e4c835](https://github.com/sysprog21/lab0-c/commit/9e4c8352c2910c81a4c309fc4072a8b54bc539f3)

在閱讀了 [案例探討: Leetcode 2095. Delete the Middle Node of a Linked List](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-Leetcode-2095-Delete-the-Middle-Node-of-a-Linked-List) 後，我將原本的實作改為透過快慢指標來獲取 `mid` 節點的指標。
兩種實作方法獲得 `mid` 節點的時間複雜度其實相同，但第一次實作中實際上多了 O(n) 的複雜度來獲取 queue 的長度，故此處還是選擇更有效率的實作方法。
#### q_delete_dup()
>[Commit 1fa55a2](https://github.com/sysprog21/lab0-c/commit/1fa55a287a564107604fd37bc95db7550c422142)

此 Function 的作用為移除 `連續` 的重複節點，而非整個 queue 中的重複節點。
故此處我以 `list_for_each_entry_safe` 來走訪節點，同時以一 Boolean 變數來記錄目前是否有 `dup` 的情況。
若 `curr` 與 `safe` 的 `value` 相同，則刪除 `curr` 這個節點，並將 `dup` 設為 `true`。
若 `curr` 與 `safe` 的 `value` 不相同，且 `dup` 為 `true` ，則同樣刪除 `curr` 這個節點，再將 `dup` 設為 `false`。
#### q_swap()
>[Commit 7efe286](https://github.com/sysprog21/lab0-c/commit/7efe2862b0b79d59b1ef881acec524aac3d3319a)

此Function為交換queue中的每兩個節點。
故我以 `list_for_each_entry_safe` 來走訪節點，swap curr 與 safe的value後將curr指向safe，如此即可跳過safe，繼續交換下兩個節點。
#### q_reverse()
>[Commit 798bd06](https://github.com/sysprog21/lab0-c/commit/798bd061f4da333da173fb47e3d99d7bcf33615c)

以一 tmp 節點記錄原節點的 next ，再逐一反轉每一節點的 prev 及 next 。
#### q_reverseK()
>[Commit 82e077d](https://github.com/sysprog21/lab0-c/commit/82e077dbaf938a456cc0c75e859e69480d418f09)
>
該函式其實與 q_swap 類似， q_swap 為每兩個節點 swap 一次，而該函式則為每 k 個節點進行一次 reverse， q_swap 本質上為 k = 2 時的特例。
而我的想法是在該函式內複用 q_reverse 函式，每次依序取 k 個節點作為子串列，並給他們一個臨時的 Dummy Head ，再呼叫 q_reverse 對該子串列進行 reverse 的操作即可。
假設我們目前的 queue 有 7 個節點，k = 3 。

在第一輪的外層迴圈中，臨時 dummy head `tmp_h` 會指向 `head` ，當前子串列的第一個節點 `curr_head` 則會指向 tmp_h->next。

而內層迴圈會以一 Counter i 記錄目前走訪的節點數，當 i==k 時，表示當前蒐集的節點數已滿足 k ，需要呼叫 q_reverse 作 reverse 的操作。
但 q_reverse 需要串列是雙向鏈結串列，所以在呼叫前我們需要先做一些操作，使子串列符合雙向鏈結串列的性質。
這邊由於 k == 3 ，故我們的子串列會是 Node 1 ~ Node 3 ，我們需要將尾端節點的 next 指標指向 tmp_h ， tmp_h 的 prev 指向尾端節點。同時將 tmp_h 的 prev 作記錄，以便 reverse 完後接回原串列。

此時呼叫 q_reverse(tmp_h) ， 傳入值為 tmp_h ，即可完成對子串列的 reverse 。

最後將原先子串列的第一個節點(目前子串列的尾節點) curr_h 的 next 指向 safe ， safe 的 prev 指向 curr_h ， 臨時 dummy tmp_h 的 prev 指向原 prev o_prev ，最後需要將 tmp_h 設為 curr_h 當做下一輪子串列的 dummy ，這樣即可在保持原鏈結串列完整的情況下對 k 個節點完成 reverse 。

後續幾輪也是相同作法，直至 safe == head 時便會跳出迴圈 ， 剩餘節點若數量不足 k ，則維持原樣。

#### q_sort()
>[Commit d8d9a73]([d8d9a73](https://github.com/sysprog21/lab0-c/commit/d8d9a73c86d41a0689f290af679f02bba81502c0))
>>[Commit bd4808a](https://github.com/sysprog21/lab0-c/commit/bd4808ad115bfaa42d6043c541b0f1ba70c6a7cf)
>>>[Commit ]()
#### q_ascend() & q_descend()
>[Commit e5d71b3](https://github.com/sysprog21/lab0-c/commit/e5d71b3f8cb0068d86f205d45e3b371868670044)
>>[Commit c6a7eee](https://github.com/sysprog21/lab0-c/commit/c6a7eee72fdbbf2ec90fe0f9b9579ce0d1b09593)

參考 [LeetCode]([https:/](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)/) 中的 hint ：`Iterate on nodes in reversed order.` 。
在要求節點排列為 descend 時 ，應該從尾往頭進行 traverse ， 移除比當前最大值小的節點。
在要求節點排列為 ascend 時 ，應該從頭往尾進行 traverse ， 移除比當前最小值大的節點。

在此處僅概述於 q_descend 中的實作 ， q_ascend 因高度相似故不多作贅述。
這裡舉 LeetCode 中的 Example 1 為例，鏈結串列會如下所示：

而根據 hint ，我們需要從尾部開始 traverse ， 所以宣告一指標 curr = head->prev ，而此時前一個節點就是 curr->prev 。

只需比較 curr 及 curr->prev 的節點值大小，若 curr 值較大(此時的情況)，則呼叫 list_del unlink 該curr->prev，再透過 q_release_element 釋放其記憶體空間。
移除 curr->prev 點後，串列會變成下面這樣：
同樣只需比較 curr 及 curr->prev 的節點值大小，
但此時就會出現一個小問題，可以看到在 [LeetCode]([https:/](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)/) 中，該題目之 ListNode 結構儲存 value 的方法為 int val ，故 value 是整數，可以簡單地用運算子(> < ==)來比較。但在 lab0 中，value 是 char *value ，為一字串，故需要用 strcmp 來比較字串的大小。
而在 strcmp 中，是依照字典序來比較字串之大小， 8 會比 13 大，在此處直接舉 LeetCode 中的例子效果不彰，所以我們可以做一點簡單的調整，將 13 替換為 9：
那此時 8 < 9 ，我們要做的僅是移動 curr 指標，使其指向值為 9 的這個節點，繼續下一輪操作。
而當 curr->prev == head 時，便會停止操作，此時串列如下所示：
這樣便完成了使鏈結串列變為 descend 形式的操作。
#### q_merge()
>[Commit 61e586a](https://github.com/sysprog21/lab0-c/commit/61e586aa3962260a2ad04dc0dc802bca37951c2f)
>>[Commit cdcd9cd](https://github.com/sysprog21/lab0-c/commit/cdcd9cd17f152f99b960a514db6c6d9662d40bbe)

要撰寫 q_merge 這個函式，首先要做的就是理解 queue_contex_t 這個結構是如何存放多條 queue 的。可以看到結構的定義如下：

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;

閱讀 queue.h 中的注釋，我們可以知道 q 存放的是指向每一條 queue 的 head 之指標， chain 則是用來鏈接每一條 queue 的 head 。
size 則是當前節點指向之 queue 的大小，而 id 為每一條 queue 的 identification number 。
閱讀完上述結構之定義，我們可以知道 queue_contex_t 的結構會如下所示，因 size 及 id 在我的實作中並未使用，此處省略繪製：

而在 q_merge 中，傳入參數是這個存放 queue 的鏈結串列的 head 以及布林函數 descend 。
我們需要做的就是將不同條的 queue 依 descend 或 ascend 合併為一條，並放入鏈結串列的第一個節點中，同時其他節點的 q 需要被設定為 `NULL`：

觀察這個函式的實作要求，我們可以先簡單拆分成兩個子問題：
如何挑選將要被合併的兩條 queue ？
如何撰寫合併函式，使其可以以 ascend / descend 的形式合併兩條 queue ？

針對第一個問題，在 [你所不知道的 C 語言: linked list 和非連續記憶體 - 案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) 中，老師已有做過詳細的探討，我在這邊選擇的方法是將鏈結串列中的 queue `頭跟尾兩兩合併`，這樣在多數的情況下兩條串列的長度比較平均，合併會比較快。
（思考：若透過存取 queue_contex_t 中的 size ，以 queue 的 size 大小作為挑選基準進行合併，是否會比較快？ `TBD` ）
基於此方法，我在 q_merge 中宣告了三個指標， `ptr_first` 、 `ptr_i` 以及 `ptr_j` 。其中 `ptr_first` 指向鏈結串列中的第一個 queue ，也就是最後合併完成的 queue 需要存放的位置，而 `ptr_i` 以及 `ptr_j` 分別用來指向鏈結串列的頭及尾，用以挑選待合併的 queue 。
在函式的內層迴圈中，會呼叫 `merge_two_sorted_queue` 來合併 `ptr_i` 及 `ptr_j` ,並將合併完成的 queue 放入 `ptr_i` ，之後將 `ptr_i` 向後移一個節點，而 `ptr_j` 向前移一個節點，繼續合併，直至兩指標相遇後退出內層迴圈。
而外層迴圈則是將 `ptr_i` 重新設定為 `ptr_first` 的下一個節點， `ptr_j` 重新設定為尾端節點，再繼續執行合併，直至 `ptr_i` 及 `ptr_j` 都指向串列的第二個節點，即代表此時只剩下最後兩條 queue ，退出外層迴圈後完成最後兩條 queue 的合併即可。
以下是具體例子，這是一個有四條 queue 的鏈結串列：
此時合併 `ptr_i` 及 `ptr_j` ， `ptr_j` 所指向的串列會變成 `NULL` 。
移動 `ptr_i` 及 `ptr_j` ，兩指標相遇：
將 `ptr_j` 設為`ptr_i` ，此時的 `ptr_j` 會指向串列中最後一個不為 `NULL` 的 queue；將 `ptr_i` 重新設定為 `head->next->next` ，即指向串列中第二條 queue 之 head 。
同樣合併 `ptr_i` 及 `ptr_j` ：
移動 `ptr_i` 及 `ptr_j` ，兩指標相遇，重設`ptr_j` 為`ptr_i` ， `ptr_i` 為 `head->next->next` ，此時會發現兩指標仍相遇，代表目前的鏈結串列中只剩下最後兩條 queue ：
退出迴圈，此時作最後的合併，合併 `ptr_first` 及 `ptr_i` ：
至此即完成合併鏈結串列中的所有 queue 為一條，並存放在第一條 queue 中。
此處合併最後兩條 queue 時，才會根據傳入參數 desend 來決定合併的方式，為何如此實作在第二個子問題會再提到。

針對第二個子問題，同樣參考 [你所不知道的 C 語言: linked list 和非連續記憶體 - 案例探討: LeetCode 21. Merge Two Sorted Lists](https://hackmd.io/@sysprog/c-linked-list#%E6%A1%88%E4%BE%8B%E6%8E%A2%E8%A8%8E-LeetCode-21-Merge-Two-Sorted-Lists) ，使用 indirect pointer 的技巧來解決。
這邊用一個實際的例子來作解釋，現有兩條 sorted 的 queue ，宣告兩個指標 L1 及 L2 來指向他們各自的 `head`。因為函式的目的是 `合併兩個 queue 並存入第一個 queue `，故我此處將 L1 的 `head` 作為最後要回傳的 `head` ，宣告間接指標 ptr 指向 L1 的 `head` 以及另一個間接指標 `node` 。
首先將 L1 及 L2 都指向他們的 `next` ，即 queue 中第一個節點，此處會進入迴圈，用以比較 L1 及 L2 所指向之節點的大小，將節點陸續放入合併後的串列中，直至有一條原始串列為空。
此處我們用 `strcmp` 比較節點值的大小， `node` 會指向值較小的指標，而 `ptr` 則會指向
`head->next` 。
由於此處 L1 所指向之節點值較小，需要先將他放到合併後的陣列中，透過 `*ptr = *node` ，即可將 `head->next` 指向目前被 `node` 指向之指標 `L1` 所指向的節點(紅色表示新連結的 chain)。此處再透過 `*node = (*node)->next` 將 L1 指向原節點的下一個節點，`prev` 指向原節點， `ptr` 則指向 `prev` 的 `next` 。
`node` 則會在第二輪迴圈中因 `2 < 3` ，被設定為指向 `L2` 。
此處重複前述操作，將目前合併串列尾端接上 `node` 所間接指向的節點。
此處為了方便區分原本的 L1 及 L2，將前一張圖中的灰色箭頭隱藏（實際執行過程中是仍然連結的）。此處接上 `node` 所間接指向的節點後，再繼續前述過之指標調整。
經過幾輪類似的操作後，可以看到 L1 的節點已被全數合併入新的串列，僅剩 L2 仍有剩餘節點。由於兩個被合併的串列本身就是 sorted 的，我們只需將剩下那條串列直接接入新串列的尾部即可完成合併，可以看到原先 L1 的 head 所連結的串列是 sorted 的。
但此時還不能直接回傳原 L1 之 `head` ，首先需要 traverse 剩下那條串列的節點至尾部，將其與原 L1 之 `head` 相連，才算是一條完整的雙向鏈結串列。
而更需要注意的時，原 L2 之 `head` 仍然指向原先的 `next` 與 `prev` ，但此時實際上他應該為指向自己的 Singular head ，故需要呼叫 `INIT_LIST_HEAD` 來使其指向自己。
至此便完成了兩條 sorted 雙向鏈結串列的 `ascend` 合併。

至於如何合併為 `descend` 的串列，實作方法其實跟 `ascend` 大同小異，但經過仔細思考跟實作後發現有一些潛在的問題：
一開始的想法是統一從串列尾端往頭部開始合併，但實作後發現合併完的串列時常與預期不符，後來才想到若有多條串列需要合併，合併後的串列就已經是 `descend` 的了，若此時再從尾端開始合併，就不符合所有串列都是 `ascend` 的假設了。
但若加上當前串列是 `ascend` 還是 `descend` 的判斷，整體的實作會變得非常複雜，也會增加非常多不必要的計算，所以我最後採用的做法是先將所有串列都以 `ascend` 的形式合併，最後在合併 `ptr_first` 及 `ptr_i` 時，再採用從串列尾端往頭部合併的方法合併為 `descend` 的形式。
以下是截取的部分實作程式碼，可以看到在迴圈中合併串列時，都採 `ascend` 的形式，直至最後合併 `ptr_first` 及 `ptr_i` 時，再傳入 `q_merge` 的 parameter `descend` 。
這樣實作上既降低了複雜度，也減少了不必要的計算開銷。

while (ptr_i != ptr_j) {
    while (ptr_i != ptr_j && ptr_j->next != ptr_i) {
        list_entry(ptr_i, queue_contex_t, chain)->q =
            merge_two_sorted_queue(
                list_entry(ptr_i, queue_contex_t, chain)->q,
                list_entry(ptr_j, queue_contex_t, chain)->q, 0);
        ptr_i = ptr_i->next;
        ptr_j = ptr_j->prev;
    }
    ptr_i = head->next->next;
}
list_entry(ptr_first, queue_contex_t, chain)->q = merge_two_sorted_queue(
    list_entry(ptr_first, queue_contex_t, chain)->q,
    list_entry(ptr_i, queue_contex_t, chain)->q, descend);

## 比較自己實作的 merge sort 和 Linux 核心程式碼之間的效能落差
:::success
Temp
研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
詳閱改進 lib/list_sort.c含解說錄影
確認分析 Linux 核心的 lib/list_sort.c 實作並評估其效益、針對 Linux 核心風格的鏈結串列開發 Timsort 排序程式，該設計對應的排序測試實驗方案。
:::
### 分析 Linux 核心的 lib/list_sort.c 實作並評估其效益
觀察 list_sort.c ，其與我實作的 merge sort 差異主要有以下幾點：
· 在一開始時會斷開尾部與頭部的鏈接，使其變為單向的鏈結串列，並且在合併的過程中都只維持單向的鏈接，直至最後一次 merge 才會將各節點之 `prev` 連上。而我的實作全程都維持雙向的鏈接。
· 不同於傳統的透過遞迴分割子串列再合併的方法，而是透過一種 bottom-up 的方法，將所有節點都視為單個的節點，再依節點數作合併。而我則是採用傳統的遞迴方法實作。
### 開發 Timsort 排序程式
>[Commit 4338368](https://github.com/sysprog21/lab0-c/commit/43383682b5f9061016b9b70039ed298b1193ee03)

由於無法修改 `queue.h` ，所以我新增了兩個檔案 `sort.h` 及 `sort.c` 用以實作 Timsort 及將 `lib/list_sort.c` 整合進我的程式碼。
同時兩種 sort 都有提供對應的 command: `timsort` 及 `linuxsort` ，在 qtest 中只需輸入這兩個 command 即可呼叫對應的實作對目前的 queue 進行 sort。

### 設計對應的排序測試實驗方案
排序測試要測什麼，我覺得主要有以下幾個方面
·正確性
是否嚴格按照 ascend/descend 進行排序
·穩定性
是否 stable
·結構完整性
排序完的鏈結串列是否還有維持雙向
·效能
排序的速度

而在 qtest 中，前三項都已有對應的測試程式(但我認為對於 `結構完整性`，只透過 `is_circular()` 作驗證是不夠的，可以考慮添加正向反向對串列進行 traverse 時，結果是否相反的驗證)。

所以此處我打算以 Python 撰寫自動測試函式，僅針對三個 sort 實作方法的效能進行測試。
最初的想法是以 `ih RAND` 來生成不同的來進行測試，但考慮到這樣每輪針對不同 sort 無法以同一串列進行測試，所以最後改為用 Python 先生成測試資料後，在每次呼叫不同 sort 前以 `ih` 插入，再配合內建的 command `time` 來量測時間，這樣就可以保證三個 sort 所使用的測試資料是同一筆。
但這樣同樣會出現一個目前我無法解決的問題，就是在實際的測試過程中，實際 sort 操作佔用時間很短，但 `ih` 的操作會佔用大量時間，所以導致整個測試流程較長，會再思考如何解決這個問題。

## 設計一組新的命令或選項，在 qtest 切換不同的 PRNG 的實作
>[Commit 08d5927](https://github.com/sysprog21/lab0-c/commit/08d5927d7dd022c295ccc2b0797962116fc0d177)
在設計新的命令前，需要先了解原來的實作做了什麼。
在 `qtest` 中輸入 `option entropy 1` 以及 `ih RAND 10` 後，可以看到如下輸出：

cmd> option entropy 1
cmd> ih RAND 10
l = [odghcw(29.69%) cmtyo(26.56%) oqakef(29.69%) lzqxsrxr(29.69%) katvnsnl(32.81%) zwfpg(26.56%) rcgfkfps(32.81%) hyugosvr(35.94%) fyuztwwal(35.94%) hyatn(26.56%)]

`option entropy 1` 為將顯示 `shannon entropy` 開啟，
`ih RAND 10` 為在 queue 中插入十個長度及內容隨機的字串，字串後的括號內就是計算出的 `shannon entropy` 。
根據 entropy 的公式：
$$
\mathrm{H}(X) = \sum_i \mathrm{P}(x_i)\,\mathrm{I}(x_i) = -\sum_i \mathrm{P}(x_i) \log_b \mathrm{P}(x_i)
$$

我們可以知道，越隨機，也就是每個事件出現的機率越平均，熵就會越大，而看到我們 `ih RAND` 時所使用的 chaset 為：

static const char charset[] = "abcdefghijklmnopqrstuvwxyz";

小寫的英文字母共26個，所以此時我們的最大熵為
log26 = 4.7
我們所期望的便是隨機生成字串時，他的熵可以貼近這個最大值。當熵貼近最大值時，代表我們生成的字串中，每個字母出現的機率越平均，字串的品質越好。
那為什麼這裡的熵值是一個 % 數而不是一個具體的值呢，我們需要看到具體的計算函式，位於 `shannon_entropy.c` 中。
可以看到在

const uint64_t entropy_max = 8 * LOG2_RET_SHIFT;

這一行中，定義了 `entropy_max` 為 8
而最後

return entropy_sum * 100.0 / entropy_max;

表示最終值是以 entropy_max 為基準的一個比例值。
由此我們可以知道，在完全隨機的情況下，最大可以達到的 % 數會是log26/8，也就是58.76%左右，而目前實作方法的熵以肉眼觀察，平均大概落在30%左右，明顯低於剛剛計算出的 58.76%。
那麼為什麼會這樣呢？可以看到

#define MIN_RANDSTR_LEN 5
#define MAX_RANDSTR_LEN 10

將隨機生成的字串之長度限制在 5 ~ 10 之間，而在熵值的計算中，最大值是跟事件的數量相關的，而在字串長度為 5 時，不同事件的數量最多只能為 5 個，那麼此時的熵最大只能為
log5 = 2.32
以 entropy_max 為基準時，大概就是 29 % 左右
所以我們需要將生成字串的長度增加，至少需要 >= 26 ，才有機會使熵接近 58.76% 。

#define MIN_RANDSTR_LEN 50
#define MAX_RANDSTR_LEN 100

將字串長度設定為 50 ~ 100 ，再重複之前操作

cmd> ih RAND 10
l = [hahxsxqaviyyrsbitipdvklsmypxjagtuxaiwqavrqbhjqvrpnivfdpjimytnjkdtljcjvhdyqnnqiscugposndgzzwbenayghk(54.69%) rjswadgiltuaixwixuboiriuytivulzowwjirmwbacpoqjmfrsvssfazxvhvlthoicqzmbskct(53.12%) zrycnlydohlnqmrhorsuhbzddqgariykehygufwlnzmblupiekvyngkliozdzscxtafjfnxxfxkvsh(54.69%) axtqqqpbqybevjzreeqldmdkdjcojkksiwuoitrjjfbufwqnwmmylmddszftvjbmbdacqodxigtfnl(54.69%) qnqqljjrnadcajmrryswfqzzrifewjxoyldlxsxlrxsxznyyhi(50.00%) hlocfgmuizhqqyjyvqcljgujegbrbawxglisekzmtcvnavcvyoepeequdqjbqesulptsyolhtivsvjasgbap(54.69%) jbvucvrsakbggwwxocibloydfwylccniponmjxiwxaommawbvxpkruqnjihjpwzqfkijtcoyisrgvoce(54.69%) hbcekyszmjauvkfkjolhxwkthjjamovccerxoxvexfzjwxlciqaytaglhvvgklscfrwsgawxymvhxvrjhgbeijstzd(53.12%) yblpwedtmnivlpdmrlzehanqrkglucskxtijxteltbinureilckqchgsxhqzkngogppwrruugdzmcwjcrjuhofbpeg(54.69%) mzrlqpbwzcqzboirbjdvdpvrbwbgoypzeldfzwgfwwcbzywfaqpgkfxjsgqtbbskbbhmmrbvsk(51.56%)]

此時可以看到計算出的平均熵值已經很接近 58.76% 。
那麼，了解了熵的意義以及目前是如何實作、如何計算相對熵值之後，我們就需要設計新的實作方法以及切換不同實作方法的 command 。

static int prng_mode = 0;
static bool do_switchPRNG(int argc, char *argv[])

首先定義一個全域變數 `prng_mode` ，用以記錄目前的實作模式， 0 代表原實作， 1 則代表新的實作模式。然後透過 `ADD_COMMAND` 將 `do_switchPRNG` 加入到 qtest 的命令中。使用者可以透過 `switchPRNG 0` 或 `switchPRNG 1` 來切換不同的 PRNG 實作模式。
接下來就是在 `fill_rand_string` 中添加新的實作模式，這邊選擇的實作方法為作業要求中提到的 `Xorshift`

## 在 `qtest` 提供新的命令 `shuffle`
### 實作 `Fisher–Yates shuffle` 演算法
>[Commit 8b93d77](https://github.com/sysprog21/lab0-c/commit/8b93d77b8dc4d18d51a1d062af3c77f5b1f21ebb)

### 以統計的原理來分析實作，探究洗牌的「亂度」
前面已經簡單討論過熵的意義，此處我也會以熵值的大小，來衡量洗牌的「亂度」。
對於一個鏈結串列，有 n 個節點時，其排列的方式就會有 n! 種(相同值節點也視為相異節點)，那麼它所對應之熵的理論最大值就會是 $\log_2(n!)$ 。
所以我們可以寫一個簡單的 script ，以不同節點數進行一定次數的 shuffle ，統計他們的 `Shannon Entropy` 與最大值之間的差異。
>[Commit ]()

這是我所撰寫的 script ，他會呼叫 qtest 之後以 new 、 數次 ih 完成串列的初始化，隨後重複 shuffle 、 記錄 shuffle 的結果、 sort 這三個動作，最後輸出各排列情況出現的次數，計算 `Shannon Entropy` 與最大值的差異。
首先是一個簡單的小範例，我們以 `[1 2 3]` 作為原始串列進行 10000 次 shuffle ，可以看到如下輸出：

=== Shuffle Distribution ===
123: 1667 (16.6700%)
132: 1672 (16.7200%)
213: 1669 (16.6900%)
231: 1640 (16.4000%)
312: 1676 (16.7600%)
321: 1676 (16.7600%)

=== Shannon Entropy ===
Entropy: 2.5849 bits
Max entropy: 2.5850 bits
Ratio: 100.00%

可以看到 `[1 2 3]` 的熵最大值約為 2.585 ，而目前 shuffle 10000 次後的分佈熵值為 2.5849 ，已非常接近最大熵值。
接下來我們以不同長度的串列分別 shuffle 100000 次，統計結果如下：

| 原始串列 | 理論熵最大值 | 實際熵值 | 比率 |
|------------|--------------|------------|----------|
| 1 2 3 | 2.5850 | 2.5850 | 100.00% |
| 1 2 3 4 | 4.5850 | 4.5849 | 100.00% |
| 1 2 3 4 5 | 6.9069 | 6.9068 | 100.00% |
| 1 2 3 4 5 6| 9.4919 | 9.4913 | 99.99% |
| 1 2 3 4 5 6 7| 12.2992 | 12.2957 | 99.97% |
| 1 2 3 4 5 6 7 8| 15.2992 | 15.2701 | 99.81% |
| 1 2 3 4 5 6 7 8 9| 18.3739 | 18.1786 | 98.94% |
| 0 1 2 3 4 5 6 7 8 9| 19.7378 | 19.6715 | 99.66% |

## 研讀論文 Dude, is my code constant time?
一開始看到作業要求中的 `注意：現有實作存在若干致命缺陷，請討論並提出解決方案` 時，我並沒有將他與自動評分系統關聯起來，所以在 `實作 queue.[ch]` 這一部分卡了很久，因為我無論如何都過不了 `trace-17-complexity` 。
於是我便去翻閱其他 checks 已經為 √ 的同學 lab0 的 Actions 部分，後來看到 [salmoniscute](https://github.com/salmoniscute/lab0-c) 這位同學的 Actions 中，經過 `Add percentile processing in dudect fixture` 這一 Commit 後，就成功通過評分系統，我才知道原來要先改進 dudect 的實作，才能通過最後一個 trace 。

要想改進 dudect 的實作，首先要閱讀論文及其 Source code，要完成的目標有二：
理解 dudect 的實作原理並解釋
分析目前 lab0 的實作與原實作有何差異，如何改進。
### 目的
透過閱讀論文，我們可以知道論文作者開發這個工具的作用是 `Assess
whether a piece of code runs in constant time or not on a given
platform.`，也就是判斷一段程式碼是否為 constant time 。
根據定義，若一段程式碼的運行時間在常數時間內，則它不論輸入資料的量大或小，執行時間都應保持一致。而在密碼學中，若加解密的演算法之執行時間非常數，則很容易受到 `Timing Attacks` ，即透過執行時間反推密碼。
所以本篇的目的在於透過一些統計及分析，可以在不依賴硬體模型的情況下，判斷一段程式碼是否為 constant time ，從而降低受到 `Timing Attacks` 的風險。

### 實作方法概述
根據論文的 II ，該工具的實現方法可以分為三步：
測量執行時間
該工具首先會定義兩種不同的輸入數據， fix 以及 random ，即固定以及隨機的測試數據，針對這兩種數據交錯執行程式，記錄他們執行所花費的 CPU cycles 。
對測量結果進行後處理
因為程式的執行時間可能受到 OS 的影響，所以對於測量結果需要進行一定裁剪，刪去 outliers 。
套用統計檢定
利用 T-test 來判定針對測試數據的不同，執行時間的分佈是否相似，若相似，則代表程式是 constant time ，反之若 T 值過大，則可能存在 timing leakage 。

### T-test
可以看到該工具實作方法的核心便是通過統計及 T-test 分析的方法來判定程式是否是 constant time 。所以想要更好的理解這篇論文，就有必要先了解什麼是 T-test 。
論文中提到在該工具中所使用的 T-Test 為 Welch’s t-test，根據[維基百科](https://en.wikipedia.org/wiki/Welch%27s_t-test)，Welch’s t-test 是 Student's t-test 的一個 adaptation ，即改編版。而 Student's t-test 則是 T-test 的最原始方法。
#### Student's t-test
#### Welch’s t-test

### lab0 中的實作與原實作的差異
目前 lab0 現有實作存在若干致命缺陷，我們需要分析原實作方法，找出目前 lab0 的實作缺陷並修復。，
#### 原實作方法分析
首先看到 dudect 的主函式

dudect_state_t dudect_main(dudect_ctx_t *ctx) {
  prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
  measure(ctx);

  bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;

  dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
  if (first_time) {
    // throw away the first batch of measurements.
    // this helps warming things up.
    prepare_percentiles(ctx);
  } else {
    update_statistics(ctx);
    ret = report(ctx);
  }

  return ret;
}

主函式會先呼叫 `prepare_inputs` 準備輸入資料，這個函式的輸入包含三個參數：
· ctx->config

dudect_config_t *config;
typedef struct {
  size_t chunk_size;
  size_t number_measurements;
} dudect_config_t;

為一 struct ，包含兩個 size_t， chunk_size 以及 number_measurements，分別表示每輪要測多少筆資料以及要測多少輪。
· ctx->input_data

uint8_t *input_data;

· ctx->classes

uint8_t *classes;

為一 8 bit 無號整數，將資料以 0 或 1分為兩個 classes，即前面提到的 fix 及 random。
該函式的作用為準備 fix 及 random 兩組輸入資料，此處並無具體實作，需要根據具體程式碼設計輸入資料。
接著函式會呼叫 `measure(ctx)` ，測量不同輸入資料下所需的 cycle ，此處同樣無具體實作。
而在測量完 cycle 後，會進入套用統計檢定的環節。
看到如下程式碼

bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;

dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
}

主函式會在首次被呼叫時，呼叫 `prepare_percentiles(ctx)` ，具體程式碼如下：

static void prepare_percentiles(dudect_ctx_t *ctx) {
  qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
  for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
    ctx->percentiles[i] = percentile(
        ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
        ctx->config->number_measurements);
  }
}

percentiles 意為 百分位數，具體解釋可參考[維基百科](https://zh.wikipedia.org/zh-tw/%E7%99%BE%E5%88%86%E4%BD%8D%E6%95%B0)：
若將一組數據從小到大排序，並計算相應的累計百分點，則某百分點所對應數據的值，就稱為這百分點的百分位數。
可以看到該函式首先呼叫 `qsort` 針對 `exec_times` 進行排序，再在下方的 for 迴圈中，計算每個百分位的值，並存入 percentiles[] 中。
需要注意的是，此處的 `DUDECT_NUMBER_PERCENTILES` define 為 `100` ，但在計算百分位時並不是線性的 1 - 100 ，我們可以看到他所使用的公式為：
`1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES`
即
$$
1 - \left(0.5^{\frac{10(i + 1)}{100}}\right)
$$

這個公式會生成一個偏高的百分位數，我們可以畫一張圖來直觀地展示：
可以看到 percentile 大致會在前 40 個 index 迅速上升，並在趨近 100 % 時逐漸放緩，這樣是為了
若函式不是第一次被呼叫，則會進入分析的環節，看到程式碼：

update_statistics(ctx);
ret = report(ctx);

其中， `update_statistics` 為主要的分析函式，因篇幅問題就不貼上[完整函式](https://github.com/oreparaz/dudect/blob/master/src/dudect.h#L302)。
我們可以看到該函式主要為一個 for 迴圈，會先捨棄前面數筆資料，再針對每筆 `exec_times` 更新現有的 T 值。

t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);
這個函式會以目前的 `difference` ，根據 `ctx->classes[i]` （即 `difference` 對應的輸入資料為 fix 還是 random），更新當前 `ctx->ttest_ctxs[0]` 中的平均值 `mean[clazz]` 以及變異數的累積值 `m2[clazz]`。
此處 `ctx->ttest_ctxs[0]` 中的 [0] 代表是由未經 crop 的資料計算出的值。
而在下方的內層 for 迴圈中，會再根據剛剛計算出的 percentile，計算出不同裁切百分比下的對應值，存入 `ttest_ctxs[crop_index + 1]` 中。
而在函式的最後，若當前 measurements 的次數超過 10000 次，則會額外針對整筆資料計算變異數(centered * centered)的平均值以及變異數的變異數累積值，即

所以經過整個 `update_statistics` ，fix 及 random 分別會有 1 + 100 共 101 個針對不同裁切百分比的平均值以及變異數累積值，以及額外一筆變異數的平均值以及變異數的變異數累積值，最後一步就是將這 102 筆資料傳入 `report` 函式，分析具體的 `leak` 情況。
針對傳入的資料，`report` 函式會先用 `max_test` 找出所有數據中的最大的 t 值並對其取絕對值得到 `max_t`，再計算出 tau。
而最後依靠 `max_t` 來判斷目前是否有洩漏的情況，從而判定程式碼是否為 constant time 。
#### lab0 的實作及其與原實作的差異
再回來看到 lab0 中的實作，
lab0 中的實作是為了測量` `四個函式是否為 constant time ，與 dudect 之主函式所對應的為以下程式碼：

static bool doit(int mode)
{
    int64_t *before_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *after_ticks = calloc(N_MEASURES + 1, sizeof(int64_t));
    int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
    uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
    uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));

    if (!before_ticks || !after_ticks || !exec_times || !classes ||
        !input_data) {
        die();
    }

    prepare_inputs(input_data, classes);

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

    free(before_ticks);
    free(after_ticks);
    free(exec_times);
    free(classes);
    free(input_data);

    return ret;
}

僅從該程式碼塊中即可看出實作中缺少了 `prepare_percentiles` 的實作，而再看到 `update_statistics` 的程式碼：

static void update_statistics(const int64_t *exec_times, uint8_t *classes)
{
    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)
            continue;

        /* do a t-test on the execution time */
        t_push(t, difference, classes[i]);
    }
}

可以看出不同於 dudect 的實作，該函式沒有針對 percentiles 計算不同組的 `ttest_ctxs` ，同時也沒用針對變異數進行二次統計，導致無法排除 outlier 所帶來的影響，故在後續的 `report` 中無法做出正確的判斷。

#### 改進 lab0 中的 dudect 實作
>[Commit 696fdc3](https://github.com/sysprog21/lab0-c/commit/696fdc39327de1e660c324af45391627e9f56423)

基於 `實作方法概述` 一節，我先簡單修改了 lab0 的實作，只需先排序，然後移除一定比例執行時間過長或過短的 "outliers" ，即可順利通過 trace 。
但這樣的實作僅僅是用一種暴力的方法去除 outlier 帶來的影響，對比 dudect 的原始實作仍然過於簡陋，且缺乏嚴謹性。

所以我按照 dudect 的原始實作，完整補全了 lab0 中的 dudect 實作：
>[Commit 1d0d2a5](https://github.com/sysprog21/lab0-c/commit/1d0d2a5bb5c765abd063694c5a462fd90ba05157)

首先需要 define 期望的 percentile 筆數，及最後總共的 t 值筆數：

#define NUMBER_PERCENTILES (100)
#define NUMBER_TESTS (1 + NUMBER_PERCENTILES + 1)

同時，基於原實作，需要有一陣列存放計算出的 percentile 之 index：

static int64_t *percentiles;

`t_context_t` 應宣告為陣列，才能存放不同 percentile 下所對應的 `mean` 及 `m2` ：

static t_context_t *t[NUMBER_TESTS];

在 `init_once` 中，需要初始化 percentile 及 t_context_t ：

static void init_once(void)
{
    init_dut();
    percentiles = (int64_t *) calloc(NUMBER_PERCENTILES, sizeof(int64_t));
    for (int i = 0; i < NUMBER_TESTS; i++) {
        t[i] = (t_context_t *) calloc(1, sizeof(t_context_t));
        assert(t[i]);
        t_init(t[i]);
    }
}

計算 percentile 之實作與原實作幾乎完全相同，此處不過多贅述，我們需要做的是在 `doit` 中加入`prepare_percentiles` 的實作，於第一次呼叫 `doit` 時計算 percentile ：

 bool first_time = percentiles[NUMBER_PERCENTILES - 1] == 0;
 if (first_time) {
     prepare_percentiles(exec_times);
 } else {
     update_statistics(exec_times, classes);
     ret &= report();
 }

至此， lab0 中的實作就已經與 dudect 中的實作幾乎一致，但 make test 之後發現仍無法通過 test ，於是我做了如下修改：
>[Commit 1c05e9e](https://github.com/sysprog21/lab0-c/commit/1c05e9e83f89497002a9d0bd8e6564ac6f3b830d)

-    bool first_time = percentiles[NUMBER_PERCENTILES - 1] == 0;
-    if (first_time) {
-        prepare_percentiles(exec_times);
-    } else {
-        update_statistics(exec_times, classes);
-        ret &= report();
-    }
+    prepare_percentiles(exec_times);
+    update_statistics(exec_times, classes);
+    ret &= report();

在此 commit 中，我將 `doit` 中呼叫 `prepare_percentiles` 的邏輯從第一次呼叫 `doit` 時才計算 percentile 改為每次呼叫 `doit` 時都會計算 percentile 。
至此即可順利通過自動評分系統的所有項目。
##
##
##