# 2025q1 Homework1 (lab0)
contributed by [PoChuan994](https://github.com/PoChuan994/lab0-c)

# 進度紀錄
- [x] 在 GitHub 上 fork [lab0-c](https://github.com/sysprog21/lab0-c)
- [ ] 依據上述指示著手修改 `queue.[ch]` 和連帶的檔案，測試後用 Git 管理各項修改，要能滿足 $ make test 自動評分系統的所有項目。
- [ ] 研讀 Linux 核心原始程式碼的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 並嘗試引入到 `lab0-c` 專案，比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差，也該嘗試改進針對鏈結串列排序實作的效能
- [ ] 確保 `qtest` 提供的 `web` 命令得以搭配上述佇列實作使用，目前一旦網頁伺服器啟動後，原本處理命令列操作的 `linenoise` 套件就無法使用，請提出改善機制
- [ ] 在 `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. 內建) 的品質
- [ ] 研讀論文〈[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

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          39 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
Vendor ID:                GenuineIntel
  Model name:             Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz
    CPU family:           6
    Model:                165
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   36%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             5199.98
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     1.5 MiB (6 instances)
  L3:                     12 MiB (1 instance)

# 修改 `queue.c`
## `insert_head`,`remove_head`

$ make check
# Test of insert_head and remove_head
Segmentation fault occurred. You dereferenced a NULL or invalid pointer---    trace-01--ops    0/5

- Version 1
- 問題 1: invalid pointer dereference
- [Commit 8c66e69](https://github.com/sysprog21/lab0-c/commit/8c66e6907b6f58b7e93454c3dd297978d153db89), [Commit 1612a3c](https://github.com/sysprog21/lab0-c/commit/1612a3c9a9d7865f376c7e2e69269bd9dd6565a2)
- `q_insert_head()` 執行 `q_insert()` ，而 `q_insert()` 中會去釋被以加入 list 的節點，進而導致後續產生 invalid pointer dereference 問題。

            static inline bool q_insert(struct list_head *node, const char *s)
            {
                /*
                 * Omit some code
                 * */
                list_add(&new->list, node);
                free(new);
                return true;
            }

- 問題 2: 沒有正確取得 head 節點
- [Commit 651eccd](https://github.com/sysprog21/lab0-c/commit/651eccd565f1455edf2d74e6dfb120646594a156), [Commit f45f5bb](https://github.com/sysprog21/lab0-c/commit/f45f5bbbcaf260b980ade9e765bca200e33aef76)
- 要移除的節點應該是 `head->next` 而不是 `head` 。

            static inline element_t *q_remove(struct list_head *node,
                                              char *sp,
                                              size_t bufsize)
            {
                /*
                 * Omit some code
                 * */
                element_t *element = list_entry(rmNode, element_t, list);
                /*
                 * Omit some code
                 * */
            }

- Version 2
- [Commit 3ee7e55](https://github.com/sysprog21/lab0-c/commit/3ee7e55b94b96f2d54ceceb910355c9e2f9f7fad), [Commit b25bb89](https://github.com/sysprog21/lab0-c/commit/b25bb890390c6680814e7f7fcbb1a63ab23cbe37)
- 修正 Version 1 中的問題。

       # Test of insert_head and remove_head
       ---    trace-01-ops    5/5