2025q1 Homework1 (lab0)

contributed by <Huadesuwa>

作業書寫規範:

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
避免使用不必要的 emoji 字元

開發環境

$ uname -a
Linux hua-GV72-8RD 6.11.0-17-generic #17~24.04.2-Ubuntu SMP PREEMPT_DYNAMIC Mon Jan 20 22:48:29 UTC 2 x86_64 x86_64 x86_64 GNU/Linux

$ 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:          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-8750H CPU @ 2.20GHz
    CPU family:           6
    Model:                158
    Thread(s) per core:   2
    Core(s) per socket:   6
    Socket(s):            1
    Stepping:             10
    CPU(s) scaling MHz:   33%
    CPU max MHz:          4100.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4399.99

指定的佇列操作

q_new

commit： 5e8635d

目的
提供建立空佇列的統一介面

請求 head 大小的記憶體空見(透過 malloc )
檢查記憶體配置是否成功，並在失敗時返回 NULL
若檢查成功，則使用 INIT_LIST_HEAD 初始化 struct list_head

記錄!：用Graphviz畫個list_head包裹的示意圖

q_free

commit： 5e8635d

目的
釋放佇列已配置的所有元素 ( element_t ) 記憶體空間，釋放的順序依序為字串陣列 ( value 指向的地址) 與佇列節點 ( element_t ) ，以及佇列 ( head )

ERROR
原先的程式碼只會釋放 ( head ) 的記憶體空間，然而 head 就但這是錯誤的，導致執行後仍有尚未釋放的記憶體空間被提醒錯誤：

There is no queue, but 4 blocks are still allocated.

改進

commit： aad9894

使用 Linux 核心 API list_for_each_safe 逐步走訪整個鏈結串列，並連帶釋放其記憶體空間:

+    if (!head)
+        return;
+    if (list_empty(head)) {
+        free(head);
+        return;
+    }
+    element_t *entry, *safe;
+    list_for_each_safe (entry, safe, head, list)
+        q_release_element(entry);
     free(head);

q_insert_head & q_insert_tail

commit： 0a7aebb

目的

建立新的佇列元素 ( element ) ，將給定的字符串複製至 value
將配置並賦值完的元素 ( element ) 插入至 head 與 head->next 之間
若為插入佇列尾巴，則將配置並賦值完的元素插入至 head 與 head->prev 之間

佇列使用的鏈結串列為雙向環狀鏈結串列

特殊狀況

當透過 malloc 申請配置失敗時: 返回false
當傳入的佇列是 NULL : 返回 false

實作流程

配置記憶體流程: 配置佇列元素、字元陣列 -> 確保皆有效 -> 將佇列元素的 value 指向字元陣列。
配置失敗發生時，要將已配置的記憶體空間釋放。

ERROR
進行測試時，發現在佇列中新增兩個 element 後，當要釋放出去時，產生了錯誤，與記憶體分配有關。

ERROR：Corruption detected in block with address 0x6271a022e290 when attempting to free it.

使用 Valgrind 來進一步調查，問題如下：

$ make valgrind 
# Test of malloc failure on insert_head
==12268== Invalid write of size 1
==12268==    at 0x10FE6F: q_insert_head (queue.c:58)
==12268==    by 0x10CEDB: queue_insert (qtest.c:234)
==12268==    by 0x10D0AC: do_ih (qtest.c:282)
==12268==    by 0x10E74D: interpret_cmda (console.c:181)
==12268==    by 0x10ED12: interpret_cmd (console.c:201)
==12268==    by 0x10EFA1: cmd_select (console.c:593)
==12268==    by 0x10F87F: run_console (console.c:673)
==12268==    by 0x10DB3C: main (qtest.c:1444)
==12268==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

問題出現在使用 malloc 配置的記憶體空間是錯誤的，依照題目敘述，應當分配的是輸入 string 大小的記憶體空間才對。

調整為正確的記憶體分配：

commit： 7f06702

-    char *str_copy = (char *) malloc(sizeof(char));
+    node->value = malloc(strlen(s) + 1);

q_remove_head & q_remove_tail

commit： afefac4

目的

移除佇列第一個/最後一個元素，並返回該元素的地址
若使用者給定一有效字元，且 目的(1) 已完成，則複製移出的元素值到 sp 中，能夠允許的最大長度為 buffsize - 1 並確保字串結尾總是 /0。

ERROR
執行 make test 發現的錯誤：














$ make test   
  CC	queue.o
  LD	qtest
scripts/driver.py -c
---	Trace		Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
---	trace-01-ops	5/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
`ERROR`: Removed value gerbil != expected value bear
`ERROR`: Removed value meerkat != expected value gerbil
`ERROR`: Removed value bear != expected value meerkat
---	trace-02-ops	0/6

在測試 Remove 操作時，發現實際移除的節點與預期要移除的節點不一致。從 qtest 可見，rh 和 rt 命令的後續參數 str 是可選的。由此可推斷，錯誤的原因在於 rh 命令從佇列頭部移除節點時，結果與預期值不符。

在對 traces/trace-02-ops.cmd 中的命令進行圖形化呈現時，發現執行錯誤的原因是 delete_middle 功能尚未實作，導致整段命令無法正常運行。

只有正確刪除中間的節點時，第9行後的命令在執行時才會正確

insert of head & tail

remove tail - tiger

delete mid twice

insert tail - meerkat

rh dolphin、bear、bear、gerbil、meerkat

q_size

commit： e3ea447

目的
逐步走訪整個佇列，以統計目前佇列的元素數量

特殊狀況
若 head 指向 NULL : 返回 0

實作流程
透過 list_for_each 逐步走訪整個佇列中的所有元素的，每當其與 head 地址不同，就將佇列大小加上 1 ，直到再次碰見 head 。

q_delete_mid

commit: c424903

目的
刪除(含記憶體)佇列中第

⌊ n + 1 ⌋

個元素，以

0^{t h}

作為元素的第一個索引。

特殊狀況
head 是 NULL 或空佇列：返回 false

實作流程

使用快慢指標( fast 、 slow ) 指向 head->next 、 head->next>next 作為起點，朝前移動。
當快指標( fast )跑完一圈時，慢指標( slow )正好會在中間(
$⌊ n + 1 ⌋$ )。

記錄!：以圖來表達快慢指標的前進方式

q_delete_dup

commit: aeb064c

目的
比較佇列元素與兩側的字串是否重複，如果重複就刪除。

特殊狀況

若 head 指向 NULL 或空佇列: 返回 false
當下一個元素的 list 就是 head : 判斷字串是否重複，會用到下個元素的成員 value 。

實作流程

list_for_each_entry_safe 的停止條件是當當前元素的 list 與 head 地址相同時。
若目前元素的字串和下個元素的字串相同，則先移出當前元素，並釋放其記憶體。
同時記住當前元素是否已經是重複元素，若是，則移動至下一個元素前要先刪除該元素。

list_for_each_entry_safe (entry, safe, head, list) {
     bool cur = (&safe->list != head && !strcmp(entry->value, safe->value));
     // head -> A -> A -> A -> B -> C -> ... -> head
     // head -> A(entry, last) -> A -> B -> C -> ... -> head
     // head -> A -> B -> C -> ... -> head
     if (cur || last) {
         list_del(&entry->list);
         q_release_element(entry);
         last = cur;
     }
 }

q_swap

commit: dbd0b19

目的:
以兩個元素為一組交換位置，完成後換下一組，直到下一個元素是未成對節點或是佇列的 head。

特殊狀況:
head 指向 NULL 、空佇列或 singular 時: 直接返回。

實作流程:
list_for_each_entry_safe 的停止條件是當當前元素的 list 與 head 地址相同時。

檢查當前節點指向的下一節點( safe )的地址不是 head，否則結束。
將當前節點指向的下一節點( safe )，移到當前節點的前方 each->prev
此時佇列的順序為 safe -> each -> ...
接著將 safe 指向 each 後面繼續下一循環

// head(each->prev) -> each -> safe -> ... -> head
// head             -> safe -> each -> ... -> head
list_head *each, *safe;
list_for_each_safe (each, safe, head) {
    if (safe != head) {
        list_move(safe, each->prev);
        safe = each->next;
    }
}

q_reverse

commit： 5d1a49f

目的:
反轉佇列內所有元素的順序。

特殊狀況:
若 head 是 NULL，或元素數量是 0 或者 1: 直接返回。

實作流程:
我們知道只要最後一個元素的 list 地址 ( tail )，就能通過 list_for_each_safe 重複將節點移動到 tail 的下一個元素就好了。

// head -> A -> B -> ... -> Z(tail) -> head
// head -> Z(tail) <- ... <- B <- A <- head
const struct list_head *tail = head->prev;
for (each = head->prev, safe = each->prev; each != head;
     each = safe, safe = each->prev) {
     if (each == tail)
         continue;
     list_move_tail(each, head);
}

q_reverseK

commit: e932a9a

void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    int turn = q_size(head) / k;
    list_head *front = head->next->next;
    list_head *last = head->next;

    for (size_t i = 0; i < turn; i++) {
        list_head *ll = last->prev;
        // Head -> A(last) -> B(front) -> C -> D -> E -> F -> Head
        // Head <- B(front) <- A(last) <- Head
        for (size_t j = 0; j < k; j++) {
            last->next = last->prev;
            last->prev = front;
            front = front->next;
            last = last->prev;
        }
        list_head *ff = last;
        last = ll->next;
        front = ff->prev;
        last->next = ff;
        ff->prev = last;
        front->prev = ll;
        ll->next = front;
        last = ff;
        front = ff->next;
    }
}

q_ascend

commit: 1f0dbff

目的
透過刪除佇列中的元素達到升冪排列，並釋放被刪除節點所配置的記憶體空間。

特殊狀況

前一個元素須嚴格小於後面所有的元素，以符合題幹:

has a node with a strictly less value anywhere to the right side of it.

表示要有嚴格小於當前元素的值才需刪除當前節點。換句話說，若右邊的值與當前值相同，不用刪除。
2. 若 head 指向 NULL 或空佇列，直接返回 0 ;若是單一元素佇列返回 1 。

實作流程

根據特殊狀況(1)，透過 list_for_each_entry_safe 來逐步走訪整個佇列
若當前節點( each ) 大於下一個節點( safe ) 就刪除 safe 。

element_t *each, *safe;
list_for_each_entry_safe (each, safe, head, list) {
    count++;
    if (&safe->list != head && strcmp(each->value, safe->value) > 0) {
        list_move(&safe->list, pending);
        safe = each;
        count--;
    }
}
q_free(pending);

q_descend

commit: 1f0dbff

目的:
要求前一個元素不可小於後面任一元素

特殊狀況:
若 head 指向 NULL 或空佇列，直接返回 0 ;若是單一元素佇列返回 1 。

實作流程:
根據目的，我們應該從佇列的尾巴( prev )開始，於迴圈中逐步向前搜尋。當目前節點( prev )的值大於下一節點( prev->prev )，則移除 prev->prev 。

初始化 prev 為佇列的尾巴，以及 pending 用來保存即將被刪除的節點。
迴圈的中止條件為下一節點( prev->prev )不是 head
若下一節點( prev->prev )不是 head ，則透過 strcmp 比較其與目前節點( prev )大小
當下一節點( prev->prev )小於目前節點( prev )，就將其移至 pending 並刪除；否則繼續向前移動。

if (strcmp(list_entry(prev, element_t, list)->value,
           list_entry(prev->prev, element_t, list)->value) > 0) {
    pending = prev->prev;
    list_del(pending);
    element_t *str = list_entry(pending, element_t, list);
    q_release_element(str);
} else {
    prev = prev->prev;
}

q_merge_two

commit: a19e22a

目的
該函式是 q_sort 與 q_merge 的輔助函式，專注於合併兩個佇列，並確保返回時，是第一個佇列擁有所有元素。

特殊狀況
在 qtest.c 中可以看到在合併佇列時，需要注意排序的穩定性：

ERROR: Not stable sort. The duplicate strings "%s\ are not in the same order.

實作流程

不允許heap allocation
- 檢查要合併的兩個佇列是否為 NULL 或空佇列
- 如果其中一個是或者皆是，則直接返回，並回傳佇列大小

 if (!ll1 || !ll2)
     return q_size(ll1 ? ll1 : ll2);

 // {ll1, ll2} = 2'b00, 2'b01, 2'b10
 if (list_empty(ll1) || list_empty(ll2)) {
     if (list_empty(ll1))
         list_splice(ll2, ll1);
     return q_size(ll1);
 }

透過 for 迴圈取得要合併的佇列元素，停止條件為當任一佇列為空時。
- descend 判斷合併後佇列以升冪還是降冪排列
- 根據特殊狀況使用三元條件運算子，判斷 strcmp 比較兩佇列內的元素結果:
  - 首先，判斷是否為 0 ，若兩佇列元素相等，則維持其輸入結果
  - 其次，判斷 descend ，決定升冪或降冪排列

 element_t *entry = list_first_entry(ll1, element_t, list);
 element_t *safe = list_first_entry(ll2, element_t, list);
 int cmp = strcmp(entry->value, safe->value);
 element_t *next = !cmp ? entry
                        : (descend ? (cmp > 0 ? entry : safe)
                                   : (cmp > 0 ? safe : entry));
 list_move_tail(&next->list, &dummy);

q_sort

commit: a19e22a

目的
排序給定佇列，順序依照 descend 的值決定。

特殊狀況

時間複雜度須在
$O (n \log n)$ 級別以通過 100, 000 個元素的測試。
若 head 指向 NULL、空佇列、或 singular : 直接返回。
為了穩定性而使用merge sort

實作流程
由於已經實作了 q_merge_two 用來合併兩個佇列。我們能基於此函式實作 merge sort

流程如下:

使用快慢指標方式找到佇列的中間節點，並以 list_cut_position 將佇列的一半切給 left
right 則以 list_splice_init 獲取佇列剩餘的一半，並以 INIT_LIST_HEAD 初始化 head
接著，透過遞迴將佇列的節點逐一切分成 singular ，此時會觸發特殊狀況(2) 返回
使用 q_merge_two 函式合併兩個佇列(left 、 right) ，並以 descend 決定最終排列方式
最後，將left 合併移至 head 裡，並返回

q_merge

commit: a19e22a

目的
將 head 所指向的佇列鏈 (queue chain) 中所有的佇列，按給定的規則 (升/降冪) 合併至該佇列鏈的第一個佇列中。佇列鏈中所有元素都被保證是依給定的規則排列。

特殊狀況

若佇列鏈中佇列個數 ( q_contex_t 實例個數) 為 1，則直接返回該佇列的元素個數。
若 head 指向的是 NULL 或空佇列: 直接返回 0。
需統計合併完後的總元素數量，並返回。

 if (!head || list_empty(head))
     return 0;
 if (list_is_singular(head))
     return q_size(list_first_entry(head, queue_contex_t, chain)->q);

實作流程
q_merge 可以使用 q_merge_two 函式將兩佇列給合併。

list_head *first = head->next;
queue_contex_t *first_q = list_entry(first, queue_contex_t, chain);
for (list_head *next = first->next; next != head; next = next->next) {
   queue_contex_t *next_q = list_entry(next, queue_contex_t, chain);
   count = q_merge_two(first_q->q, next_q->q, descend);
}

新增 shuffle 命令與 prng 選項

在本節中，預計達成以下目標:

新增 shuffle 命令，使當前佇列進行洗牌。
新增 prng 選項，讓使用 ih RAND xx 時，使用者可選擇調用預設的 syscall
或是分析不同 PRNG 對 ih RAND 指令的影響，指標可使用香農熵 (Shannon entropy) 評估。

以下先探討 lab0-c 如何新增命令，接著探討 Fisher–Yates shuffle 和 PRNG，並了解目前 lab0-c 預設的隨機字串是如何產生的。了解後研討如何設計相關介面來達成上述目標，最終透過香農熵輔以其他統計手段分析結果與差異性。

如何在 lab0-c 增加新的命令?

在 console.h 中，提供了 ADD_COMMAND 巨集用於新增命令，並對應至 add_cmd 函式，其宣告如下：

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)

關鍵在於 operation ，透過連接運算子 ## 會自動展開為 do_<cmd> 。因此，一旦事先提供 do_* 函式，並在 console_init 中呼叫 add_cmd("<instruction>", <do_*>, "<documentation>") ，即可增加新命令！

cmd_func_t 的定義是:

typedef bool (*cmd_func_t)(int argc, char *argv[]);

命令的解析與執行由 interpret_cmd 負責，其中實際調用 do_* 的部分則由 interpret_cmda 處理。 interpret_cmda 會在 cmd_list 鏈結串列中搜尋對應的命令並執行。

Fisher–Yates shuffle

Fisher-Yates 演算法最初於 1938 年提出，並在 1964 年針對計算機應用進行改良。隨後，它以 Algorithm P 的形式收錄於《 The Art of Computer Programming 》。該演算法的設計目標是確保所有排列結果的機率均勻且一致。

以長度為 n 的陣列 a 為例，演算法步驟如下：

初始化變數 i = n - 1，並隨機產生索引 j，範圍介於 0 到 i 之間，作為交換對象。
交換 a[i] 和 a[j]，將選出的元素 a[i] 移至陣列尾端。
將 i--，然後重複步驟 1，直至 i < 0 為止。

需要注意的是，Wiki 中的範例是以陣列為例進行說明。然而，在鏈結串列中，訪問第 n 個節點的時間複雜度為

O (n)

，而陣列僅為

O (1)

。因此，基於鏈結串列的洗牌演算法，其時間複雜度為

O (n^{2})

級別。

從大數法則理解訊息熵 (Entropy) 的數學意義

熵可以這樣解釋：對於某個在

1

附近的下界

1 - ϵ

，我們都可以找到一個
$ϵ$ -high-probability set，這是一個字元集

S^{n}

的子集，使得在

S^{n}

中，根據特定機率分佈選取的序列落入該集合的機率大於

1 - ϵ

。

選擇該集合的方法是基於函數 $ \log∘P$（其中

\log

以

2

為底，而

P

是機率質量函數）。根據 弱大數法則，如果一個函數從

S

映射到實數，且對於特定機率分佈的期望值為有限實數，那麼當取樣數量

n

趨近無限時，該函數的樣本平均值會趨近於期望值。

因此，對於任意的

δ

，總能找到一個

n_{0}

，使得當

n \geq n_{0}

時，

\log \circ P

的樣本平均值與

E [f (S)]

的距離小於

δ

的機率大於

1 - ϵ

。

為何使用
$\log \circ P$ 來選擇集合？

這是因為 獨立事件的機率是相乘的，如果對個別的機率取對數再取平均，則相乘關係轉換為加法，這剛好對應於從字元集

S

取長度為

n

的字串

s^{n}

出現的機率。

\begin{array}{r} E [\log P (s)] - δ \leq \frac{1}{n} \sum_{i} \log P (s_{i}) = \frac{1}{n} \log (\prod_{i} P (s_{i})) = \frac{1}{n} \log P (s^{n}) \end{array}

變數說明

$s$ ：一個從字元集
$S$ 以機率質量函數
$P$ 分佈的隨機變數。
$P (s_{i})$ ：特定變數
$s_{i}$ 出現的機率，即
$P (s = s_{i})$ 。
$P (s^{n})$ ：長度為
$n$ 的字串
$s^{n}$ 出現的機率。

訊息壓縮與解碼準確性的權衡

當資料表達過度簡化時，可能會導致解碼困難。例如，若將字母 a、b、c 均編碼為

0

，其餘字母編碼為

1

，則 "cat" 的編碼結果為

001

。然而，由於 "bar" 也會得到相同的編碼，解碼器將無法正確區分這兩個單詞，最終導致訊息還原錯誤。

因此，我們可以得出兩點結論：

當訊息呈現某種規則或模式時，資料是可能被壓縮的。
訊息壓縮的程度與還原準確性之間存在 trade-off，過度壓縮可能會影響解碼的準確性。

這與熵的概念密切相關——熵描述的是最優壓縮的極限，而避免過度壓縮則確保了訊息能夠準確還原。

結論

這個證明說明了兩點：

如何選擇
$ϵ$ -high-probability set：對於
$S^{n}$ 中的某個元素，如果它的每個字元經過 $ \log∘P$ 處理後的平均值與
$E [f (s)]$ 的距離小於
$δ$ ，則它屬於
$ϵ$ -high-probability set，並且這樣選取的集合確實符合該集合的定義。
熵作為單位資訊量的極限：
- 從
  $S^{n}$ 中隨機選擇一個字串時，特定字串出現的機率，當
  $n$ 足夠大時，會接近
  $2^{n E [\log P (s)]}$ 。
- 如果假設所有結果的機率相等，則總共有
  $2^{- n E [\log P (s)]}$ 種可能的結果。
- 換句話說，
  $n$ 個字元總共的資訊量是
  $- n E [\log P (s)]$ 位元，因此 單個字元的資訊量為

\begin{array}{r} E [\log P (s)] = - \sum_{i} P (s_{i}) \log P (s_{i}) \end{array}

這 正是 Shannon entropy 的定義公式！

直覺解釋

高機率出現的序列占據大部分總機率，因此壓縮時應優先考慮這些序列。
- 這樣的作法，比起
熵描述的是「資訊的平均不確定性」或「最優壓縮極限」：
- 如果某個字元的出現機率較為平均（例如公平擲骰子），則熵較高，需要更多位元來表示。
- 如果某些字元明顯比其他字元常見（例如英文文本中的 "e" 出現頻率較高），則熵較低，可以用較少位元來表示常見字元。
大數法則提供了數學基礎，說明當序列長度夠大時，實際樣本的行為會趨近於 Shannon entropy 的理論極限。

實作

隨機數產生功能獨立封裝至 random.[ch] ，使其與主程式分離。這樣一來，q_shuffle 和隨機字串生成函式 fill_rand_string 皆可重複使用，減少程式碼冗餘。可選的實作方式目前包含預設方法與 Xorshift。此外，所有隨機數函式的接口應統一為：

typedef int (*rand_func_t)(uint8_t* buf, size_t len);

此接口與現有的 randombytes 保持一致（亦相容於 getrandom），提升兼容性，並允許未來擴展以支援不同的 PRNG 選項：

extern int randombytes(uint8_t *buf, size_t len);
const rand_func_t prng_func[] = {&randombytes, &xorshift, ...};

commit: 62b173f

Shuffle

commit: 41157a5

目的
對佇列中所有節點進行洗牌 (shuffle) 操作

實作方法
以 Fisher–Yates shuffle 演算法完成

同時，為確保 q_shuffle 能夠放在 queue.h，更新了 chechsum.sh 中 queue.h 的 sha1sum。

PRNG

commit: 62b173f

目前可透過 option prng 1 設定為 Xorshift，0 則為預設模式，使用 getrandom。並未修改原程式中的 randombytes，因此不受 prng 設定影響。該選項僅影響 fill_rand_string 和 q_shuffle 的行為。

統計方式驗證 shuffle

這裡使用範例所提供的 python 程式碼進行實驗，分析 4 個元素進行 shuffle 是否符合 Uniform distribution，也就是分佈是平均的。首先提出須假說：

$𝐻_{0}$ （虛無假說）: shuffle 的結果發生的機率相同，遵守 Uniform distribution
$𝐻_{1}$ （對立假說）: shuffle 的結果發生的機率至少有一個不同
此為資料適合度分析，測試資料是否符合某種比例:

先計算 chi-squared test statistic
$X^{2}$

$\begin{array}{r} X^{2} = \sum_{i = 1}^{n} \frac{(O_{i} - E_{i})^{2}}{E_{i}} \end{array}$
其中，
$𝑂_{𝑖}$ 表示的是此種結果的實際觀察值，
$𝐸_{𝑖}$ 表示的是在假設的比例上，此種結果數量的期望值。

這裡是做了 1000000 次 shuffle 後，所得到的期望值與卡方值：

Expectation:  41666
Observation:  {'1234': 41741, '1243': 41591, '1324': 41783, '1342': 41839, '1423': 41720, '1432': 41518, '2134': 41748, '2143': 41752, '2314': 41360, '2341': 41598, '2413': 41552, '2431': 41628, '3124': 41767, '3142': 41554, '3214': 41992, '3241': 41523, '3412': 41662, '3421': 41653, '4123': 41858, '4132': 41443, '4213': 41813, '4231': 41579, '4312': 41436, '4321': 41890}
chi square sum:  13.80046080737292

總共有

4!

種結果，可以發現

41666

$實際上就是

⌊ \frac{1000000}{4!} ⌋

。

對於

N

個隨機樣本，自由度為

N - 1

。在隨機排列 4 個數字時，共有

4!

種排列方式，因此自由度為 23。以顯著水準 0.05 查表可得

χ_{23, 0.05}^{2} = 35.1725

，而

13.8005 < 35.1725

，所以不拒絕虛無假說

H_{0}

從圖表來看 shuffle 的頻率是大致符合 Uniform distribution 的。
Figure_1

閱讀〈 Dude, is my code constant time? 〉

為了防範 Timing Attack，必須測試程式對不同輸入的執行時間穩定性，以避免資訊透過執行時間洩漏。傳統的分析方式通常需要對硬體建模，然而這並不容易。因此，本文提出了一種基於洩漏測試與統計分析的方法，以評估執行時間的穩定性。

定義 Fix 與 Random 類別
- Fix：一種極端特例，輸入固定不變。
- Random：輸入為隨機值，每次測量皆不同。
時間測量與預處理
- 測量執行時間，並去除受外部因素中斷或執行時間過長的數據。
- 使用 higher-order pre-processing 技術提高數據的次方數，使其非線性化。
去除異常數據
- 依據某個百分位數
  $p$ 去除右尾的數據，以減少外部因素（如背景程序）對結果的影響。
- 使用不同的
  $p$ 值進行測試，以評估結果的穩健性。
統計
- 虛無假設
  $H_{0}$ : 兩組數據的分佈相同，執行時間無資訊洩漏。
- 對立假設
  $H_{1}$ : 兩組數據的分佈不同，存在潛在資訊洩漏。
- 由於兩組數據為獨立樣本，且僅知道樣本標準差，因此使用 t-test 進行檢定。

這種方法透過統計分析來評估 Timing Attack 風險，避免繁瑣的硬體建模，並提供更直觀的評估方式。

程式碼分析

在 trace-17-complexity 中，首先輸入 option simulation 1，啟用該選項後，即可使用 GDB 進行動態分析。在 simulation 1 模式下，設置斷點於 interpret_cmda，並執行 it 命令。

(gdb) break console.c:204
Breakpoint 1 at 0x6ae2: file console.c, line 205.
(gdb) run
cmd> option simulation 1
(gdb) continue 
Continuing.
cmd> it
214	        ok = next_cmd->operation(argc, argv);

程式會持續執行，直到執行 next_cmd->operation，接著依序執行 do_it 和 queue_insert。在 simulation 1 模式下，會呼叫 is_insert_tail_const，

顯然，is_insert_tail_const 的目的即在驗證 q_insert_tail 的執行時間是否為
$O (1)$ 。

在裡面會去呼叫 test_const，第一個參數是 "insert_tail" 字串，第二個參數是 1

► 0x57fdbab0a13b <is_insert_tail_const+20>    call   test_const                  <test_const>
    rdi: 0x57fdbab0d725 ◂— 'insert_tail'
    rsi: 1

在 constrant.h 中，定義了:

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)
    
#define DUT(x) DUT_##x

enum {
#define _(x) DUT(x),
    DUT_FUNCS
#undef _
};

在 fixture.c 中定義了：

#define DUT_FUNC_IMPL(op) \
    bool is_##op##_const(void) { return test_const(#op, DUT(op)); }

#define _(x) DUT_FUNC_IMPL(x)
DUT_FUNCS
#undef _

展開後等同於:

bool is_insert_head_const(void) { return test_const("insert_head", 0); }
bool is_insert_tail_const(void) { return test_const("insert_tail", 1); }
bool is_remove_head_const(void) { return test_const("remove_head", 2); }
bool is_remove_tail_const(void) { return test_const("remove_tail", 3); }

接下來是 doit 中呼叫的函式：

measure：執行程式，測量開始與結束時間
differentiate：計算執行時間
update_statistics：更新各類別資料
report: 進行統計

這裡來看看拿來統計的函數 t_push 和 t_compute 是怎麼計算的。
首先是 t_push，這個平均數更新的方式實際上就是將每個變數減掉原本的平均數後，做平均，再把舊的平均數加回來，這樣的好處是原本的數在計算時能變 0：

\begin{array}{r} {\overset{―}{X}}_{n e w} = {\overset{―}{X}}_{o l d} + \frac{0 \times n_{o l d} + (x - {\overset{―}{X}}_{o l d})}{n_{n e w}} \end{array}

double delta = x - ctx->mean[clazz];
ctx->mean[clazz] = ctx->mean[clazz] + delta / ctx->n[clazz];
ctx->m2[clazz] = ctx->m2[clazz] + delta * (x - ctx->mean[clazz]);

而 m2 指的就是離均差平方和
$S_{X X}$

然後是 t_compute，可以發現，t 值是

\frac{\overset{―}{X_{1}} - \overset{―}{X_{2}}}{\sqrt{\frac{S_{1}^{2}}{n_{1}} + \frac{S_{2}^{2}}{n_{2}}}}

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;

make test

最終結果：通過 trace-01-ops ~ trace-16-perf ，未通過 trace-17-complexity，得分： 95/100 (回歸測試結果)。

在 3/18 的課堂問答中，老師與 BennyWang1007 討論了本文及其程式碼，並提及在原先 lab0 專案的實作中，函式 percentiles 已被移除。

檢視 update_statistics 時可以發現，lab0 中的 update_statistics 並未執行 crop 和 second-order test，但在 GitHub 上的專案中卻包含了這些步驟。此外，ttest_ctxs 在 GitHub 專案中包含多組資料，包括：

未經任何預處理的數據
經過 crop 預處理的數據（共 DUDECT_NUMBER_PERCENTILES 組）
完成 second-order test 的數據

根據作業提示：

注意：現有實作存在若干致命缺陷，請討論並提出解決方案。
在 oreparaz/dudect 的程式碼中具備 percentile 處理，但在 lab0-c 中則無。當你改進後，可提交 pull request，並務必提供對應的數學分析。

原始實作的問題

最初的實作將所有測量數據納入統計，但由於中斷（interrupt）、分頁錯誤（page fault）、I/O 延遲、CPU 排程等因素，可能會出現異常值，導致錯誤判定，使程式看起來不像常數時間（constant-time）實作。

改進方式

為解決此問題，在測量初始化時新增了一個 percentiles[NUM_PERCENTILES] 陣列，用於儲存應捨棄的百分位數。隨著測量進行，我們應逐漸減少捨棄的數據，因此使用以下公式來判定是否納入統計：

\begin{array}{r} threshold (x) = 1 - {(0.5)}^{\frac{10 \cdot x}{N U M_P E R C E N T I L E S}} \end{array}

其中，NUM_PERCENTILES 設為 100，得到以下曲線：

來源: 2025-03-18 問答簡記

**同樣地，我注意到 rota1001 和 weiso131 也進行了相關實驗與討論。

從結果來看，可以推斷 CPU cycle 較長的部分，其比例差異主要來自環境因素（如中斷（interrupt）、分頁錯誤（page fault）、I/O 延遲、CPU 排程等）。此外，由於兩者在 CPU cycle 較短的部分呈現明顯相似的分佈，因此我們可以透過 排除某個百分位數以上的數據來進行比較。

然而，若依照文中的方法，較大的差異將導致更高的 t 值，最終選取的 t 值 會對應到較高的 p 值，使得 右尾數據保留較多。因此，我選擇 取 50 百分位數作為閾值。在此情境下，即便是 do_nothing 也開始出現分叉，顯示 環境因素已經對執行時間產生影響。

由此可見，對異常值進行過濾是相當必要的。此外，藉由這次測試，我也成功獲得了一隻卡比。

Linux 核心的鏈結串列排序

首先，我們來理解 Linux 中的 list_sort 是怎麼做的:

操作流程

陣列 pending 一開始是空的，每次 count+1，即每新增一個元素時，count 會遞增。當 count 遞增至

2^{k}

時，對應的位元會從 0 變為 1。然而，只有在 第一次 遞增到

2^{k}

時，我們不進行合併，而是等待更多元素的加入。

隨著 count 進一步增長，當它達到

$3 \times 2^{k}$ 時，代表目前有三個大小為
$2^{k}$ 的子列表。此時，我們合併前兩個

2^{k}

的子列表，使其成為一個大小為

2^{k + 1}

的子列表，而第三個
$2^{k}$ 的子列表則保持不變。

這樣的機制確保了合併與不合併始終維持 2:1 的比例，又可以避免 cache thrashing 的風險。以下舉例子：

2025q1 Homework1 (lab0)

開發環境

指定的佇列操作

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_ascend

q_descend

q_merge_two

q_sort

q_merge

新增 shuffle 命令與 prng 選項

如何在 lab0-c 增加新的命令?

Fisher–Yates shuffle

從大數法則理解訊息熵 (Entropy) 的數學意義

為何使用 log∘P 來選擇集合？

變數說明

訊息壓縮與解碼準確性的權衡

結論

直覺解釋

實作

統計方式驗證 shuffle

閱讀 〈 Dude, is my code constant time? 〉

程式碼分析

make test

原始實作的問題

改進方式

Linux 核心的鏈結串列排序

操作流程

Read more

2025q1 Homework2 (quiz1+2)

Git fork & upstream & projects

2025q1 Homework1 (ideas)

為何使用
$\log \circ P$ 來選擇集合？

閱讀〈 Dude, is my code constant time? 〉