# 2025q1 Homework (lab0)
contributed by <`Andrewtangtang`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## 開發環境
```
$ 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: 40 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: QEMU Virtual CPU version 2.5+
CPU family: 15
Model: 107
Thread(s) per core: 1
Core(s) per socket: 16
Socket(s): 1
Stepping: 1
BogoMIPS: 5199.99
Flags: fpu de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx lm constant_tsc nopl xtopology cpuid
tsc_known_freq pni ssse3 cx16 sse4_1 sse4_2 x2apic popcnt aes hypervisor lahf_lm cpuid_fault pti
```
## 佇列操作的程式碼實作
### q_new
#### 目標
創建節點，當作整個鏈結串列串的開頭
#### 實作細節
先使 `malloc` 分配一塊記憶體空間給該 `list_head` 指標，接下來使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 內部定義的 macro `INIT_LIST_HEAD` 初始化該節點使節點中的 `next`、`prev` 都指向自己
#### 程式碼
```diff
- return NULL;
+ struct list_head *head = malloc(sizeof(struct list_head));
+ if (head == NULL) {
+ return NULL;
+ }
+ INIT_LIST_HEAD(head);
+ return head;
```
### q_free
commit:[c4e246f](https://github.com/sysprog21/lab0-c/commit/c4e246ff30a95ff65309d7fa8c15c2bb7e85b1e9)
#### 目標
釋放掉所有被佇列使用到的記憶體空間
#### 實作細節
先檢查傳入函數的參數 head 是不是NULL指標以及該條鏈結串列是不是沒有節點的，如果是則直接釋放掉 head 指標，否則創建兩個 element 型別的指標 *entry 以及 *safe 使用 [list.h](https://github.com/sysprog21/lab0-c/blob/master/list.h) 內部定義的 macro `list_for_each_entry_safe` traverse 並取出嵌入 list_head 的真正 struct element_t 釋放掉該結構體的記憶體空間，`list_for_each_entry_safe` 會檢查下一個節點是不是 head pointer 來確保安全釋放記憶體空間。
#### 遇到的問題
commit:[d8bd4e9](https://github.com/sysprog21/lab0-c/commit/d8bd4e9aa1738abfdd8b0992994bde84ef00e79e)
在初始版本中，程式碼未先檢查佇列是否為空或 head 是否為 NULL，就直接使用 list_for_each_entry traverse 並釋放記憶體，導致 Segmentation Fault。這是因為 list_for_each_entry 假設鏈結串列至少包含一個有效節點，如果 head 為 NULL 或鏈結串列為空，則會存取非法記憶體區域。在更新版本中，增加了適當的條件檢查，並改用 list_for_each_entry_safe，這個 macro 在遍歷的過程中，會先記錄下一個節點，確保當前節點釋放後不會影響鏈結串列的完整性。
#### 程式碼
```diff
- struct list_head *current;
- list_for_each (current, head)
- q_release_element(list_entry(current, element_t, list));
+ element_t *entry, *safe;
+ // cppcheck-suppress unknownMacro
+ list_for_each_entry_safe (entry, safe, head, list)
+ q_release_element(entry);
free(head);
```
### q_insert_head, q_insert_tail
commit:[8bd3921](https://github.com/sysprog21/lab0-c/commit/8bd39213b4c1b9b1b91efdb60c1bcb195531a227)
#### 目標
創建一個新的佇列元素，將傳入的 string 複製一份到該元素的`value` 中，最後根據要求將該元素插入鏈結串列的頭部或尾部
#### 實作細節
函式在執行時必須先做例外檢查，如果 `head` 是 NULL 值必須回傳 false
```c
if (!head) {
return false;
}
```
接下來要為佇列元素以及其中的 `value` 分配記憶體，而這個分配記憶體與檢查的操作在 `q_insert_head` 、`q_insert_tail` 都會使用到，因次我將這個部分的操作創建一個函數 `new_element()` 來完成。而這裡需要注意的是記憶體分配失敗時的處理機制。當 malloc 無法成功分配記憶體時，函式應該回傳 NULL，以通知上層調用者發生了錯誤。因此，所有透過 malloc 取得記憶體空間的指標都應該進行例外檢查，確保可以處理記憶體分配失敗的情況。
```c
static inline element_t *new_element(char *s)
{
element_t *e = malloc(sizeof(element_t));
if (!e)
return NULL;
e->value = strdup(s);
if (!e->value) {
free(e);
return NULL;
}
return e;
}
```
最後將成功被創建 element 根據要求，使用macro`list_add` `list_add_tail` 插入 `head` 與 `head->next`(q_insert_head)， `head->prev` 與 `head` (q_insert_head)中間
```c
bool q_insert_head(struct list_head *head, char *s)
{
// other code
list_add(&element->list, head);
}
bool q_insert_tail(struct list_head *head, char *s)
{
// other code
list_add_tail(&element->list, head);
}
```
#### 遇到的問題
這兩項測試在測試 trace-17-complexity 一直通過不了測試測試的結果認為我的操作時間完成不是常數時間，但目前還找不到解決的方法，或許得做更多的研究看我這兩個操作的細節可能會花超過常數時間的操作。(已在 dudect 部分修正完成)
### q_remove_head, q_remove_tail
commit:[4ff4b46](https://github.com/sysprog21/lab0-c/commit/4ff4b4680df3c59d1b8dee08651dc8307fb496f1)
#### 目標
根據函數的要求將佇列中的第一個元素或最後一個元素從鏈結串列中移除，並將`element_t->value` 的 string 複製到 `buffer` 的起始位置 `sp` 的地方，供外部調用函數者去做檢查與目標移除的 string 是否相同。
#### 實作細節
首先還是必須先對佇列進行例外檢查，假設佇列是空的則必須回傳NULL讓上層調用者得知
```diff
+ if (list_empty(head)) {
+ return NULL;
+ }
```
接著使用 macro 中提供的 `list_first_entry` 取得佇列中的第一個元素的指標， `list_last_entry` 取得佇列中的最後一個元素的指標
```diff
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
//other code
+ element_t *entry = list_first_entry(head, element_t,
}
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
//other code
+ element_t *entry = list_last_entry(head, element_t,
}
```
將該元素的 value 值使用 `strncpy` 最多複製 bufsize-1 個字元 到 sp 指標指向的記憶體區域，確保不會超過 bufsize 限制，並在最後補上 `\0` 來確保字串終止。接著，使用 macro `list_del_init` 將該元素從佇列中安全移除
```diff
+ if (sp && entry->value) {
+ strncpy(sp, entry->value, bufsize - 1);
+ sp[bufsize - 1] = '\0';
+ }
+ list_del_init(&entry->list);
```
### q_size
commit:[86b19d3](https://github.com/sysprog21/lab0-c/commit/86b19d3cc35e6719fe66be29a30b7b53c9e82098)
#### 目標
計算出佇列元素個數
#### 實作細節
創建一個臨時的指標變數 `current` 並使用 macro `list_for_each(current, head)` ，他會使current指向 `head->next` ，若 `current` 不等於 `head` 則持續 traverse 移到下一個節點上
```diff
+ int len = 0;
+
+ struct list_head *current;
+ list_for_each (current, head)
+ len++;
+ return len;
```
### q_delete_mid
commit:[3996f11](https://github.com/sysprog21/lab0-c/commit/3996f1180785eede2efac00d7291d0bb7ffa0c6c)
#### 目標
假設佇列的元素個數為 n 則必須找到 $\lfloor \frac{n}{2} \rfloor th$ 的node 將其從佇列中移除移除並釋放其記憶體空間
#### 實作細節
---
一開始的想法是利用已經實作的 q_size() 來計算佇列的長度，接著透過迴圈遍歷，判斷是否到達 $\lfloor \frac{n}{2} \rfloor$th 的節點。然而，在閱讀了教材中〈[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT)〉後，我了解到，雖然「單一指標」與「快慢指標」在時間複雜度上相同，且對空間局部性的影響也相近，但考慮到時間局部性，當佇列長度夠長時，使用「快慢指標」能夠提高快取命中率。這是因為慢指標能在較短的時間內再次訪問到快指標曾經訪問過的記憶體位置，從而提高 Cache 的效能。基於這個考量，我決定使用「快慢指標」來實作該功能。
---
因為題目中的要求是找到 $\lfloor \frac{n}{2} \rfloor th$ 的節點，而鏈結串列的 `head` 本身是不會被嵌入的，因此真正有被嵌入的第一個節點為`head->next` ，初始化兩個 list_head 指標 `fast`、`slow` 指向 `head->next` 接著每一次的疊代 `fast` 往後走兩個 `node`、`slow` 往後走一個 `node`，直到 `fast` 或 `fast->next` 走到 `head` 為止，從佇列中刪除 `slow` 指標並使用 macro `q_release_element` 釋放元素結構的記憶體空間。
```c
struct list_head *slow = head->next;
struct list_head *fast = head->next;
while (fast != head && fast->next != head) {
slow = slow->next;
fast = fast->next->next;
}
```
#### 遇到的問題
在一開始的版本中我把 `fast` 指向 `head->next->next` 、`slow` 指向 `head->next` 但因為此題目是以 zero-based indexing 這樣在偶數時我真正刪除的元素是 index $\lfloor \frac{n}{2} \rfloor-1 th$ 的節點，在 commit [[cada3638fd297f64e1afdb374d1b33b5359ffe48](https://github.com/Andrewtangtang/lab0-c/commit/cada3638fd297f64e1afdb374d1b33b5359ffe48)] 已修正
```diff
- struct list_head *fast = head->next->next;
+ struct list_head *fast = head->next;
```
### q_delete_dup
commit:[3996f11](https://github.com/sysprog21/lab0-c/commit/3996f1180785eede2efac00d7291d0bb7ffa0c6c)
#### 目標
如過佇列中的元素中的字串值有連續重複的則將這些重複的節點從佇列中刪除
#### 實作細節
這邊我嘗試使用課堂上介紹的 indirect pointer 寫法，初始化一個 pointer to pointer 變數 `indirect`，讓它指向每次檢查的 duplicate nodes 前一個節點的 next 指標的記憶體位置。這樣可以直接修改 next 指標來刪除節點，避免額外維護 prev 指標來記錄當前檢查的string以及與前一個節點的連接關係。
```c
struct list_head **indirect = &head->next;
```
##### 遍歷佇列，尋找重複節點
- 使用 strcmp() 比較 cur_value 與 (*indirect)->next->value，判斷是否有連續相同的元素。
- 若相同，則標記 dup = true，並移除所有與 cur_val 相同的節點
```c
const char *cur_val = list_entry(*indirect, element_t, list)->value;
bool dup = false;
while ((*indirect)->next != head &&
strcmp(cur_val,
list_entry((*indirect)->next, element_t, list)->value) ==
0) {
dup = true;
struct list_head *dup_node = (*indirect)->next;
list_del(dup_node);
q_release_element(list_entry(dup_node, element_t, list));
```
##### 刪除重複節點並更新 indirect
若 dup == true，則刪除 `*indirect`，並釋放記憶體，若當前節點無重複，則移動 `indirect`，移動到下一個節點的 next 指標所在的記憶體位址
```c
if (dup) {
struct list_head *temp = *indirect;
list_del_init(*indirect);
q_release_element(list_entry(temp, element_t, list));
} else {
indirect = &(*indirect)->next;
}
```
### q_reverse
commit:[e6792c9](https://github.com/sysprog21/lab0-c/commit/e6792c92fe7a07bf144208e30f2e9d98ff246faf)
#### 目標
將鏈結串列內部元素的順序顛倒過來
#### 實作細節
使用一個臨時時的指標 curr 來 traverse 這個鏈結串列並將下一個元素的 pointer 存下來，該指標的 `next`、`prev` pointer 互相交換，traverse 一圈後即可翻轉順序
```c
struct list_head *curr = head;
do {
struct list_head *tmp = curr->next;
curr->next = curr->prev;
curr->prev = tmp;
curr = tmp;
} while (curr != head);
```
### q_reverseK, q_swap
commit:[4bf9dbc](https://github.com/sysprog21/lab0-c/commit/4bf9dbc71b5f6715afa3f83bffafc3c569e8a50d)
#### 目標
可以根據輸入的 argument k，k個數字組成一組進行組內的鏈結串列順序反轉。因為 `q_swap` 其實是 `q_reverseK(K=2)` 的特例，因此我先實作 `q_reverseK` 函數，在 `q_swap` 內部在呼叫他，來實現相同邏輯。
#### 實作細節
##### `reverse_segment(head, tail)`: 反轉指定區間
- reverse_segment(head, tail) 負責反轉 `[head, tail)` 範圍內的節點，並確保鏈結仍然保持正確的連結。
- 具體步驟：
記錄 head 之前的節點 `before_head`，避免丟失對原鏈結的訪問。
```diff
+ struct list_head *before_head = head->prev;
```
traverse `[head, tail)`，對每個節點交換 `next` 和 `prev`，實現區間內的順序反轉。
```c
void reverse_segment(struct list_head *head, struct list_head *tail)
{
struct list_head *curr = head;
struct list_head *prev = tail;
while (curr != tail) {
struct list_head *next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
}
```
重新連接反轉後的區段，使其與原鏈結串列保持一致。
```clike
before_head->next = prev;
prev->prev = before_head;
head->next = tail;
tail->prev = head;
```
##### `q_reverseK(head, k)`: 以 k 為單位反轉鏈結串列
從 `head->next` 開始遍歷鏈結，每次尋找 k 個節點組成的區段，若長度不足 k 則保持不變
```c
while (count < k && tail != head) {
count++;
tail = tail->next;
}
if (count < k)
break;
```
對每個符合 k 長度的區段，呼叫 `reverse_segment` 進行反轉，並移到下一個區段繼續檢查
```c
reverse_segment(curr, tail); // reverse the segment [curr, tail)
curr = curr->next;
```
### q_ascend, q_descend
commit:[b0790a3](https://github.com/sysprog21/lab0-c/commit/b0790a3e0c161db8c276fc25c04909f5060151c0)
#### 目標
根據鏈結串列的排序規則，移除右側存在比當前節點更大（或更小）值的節點：
- `q_ascend`：移除右側有更小值的節點，最終保留遞增（非嚴格）排序的鏈結。
- `q_descend`：移除右側有更大值的節點，最終保留遞減（非嚴格）排序的鏈結。
#### 實作細節
這兩個函式的核心邏輯相同，主要差異在於判斷條件的不同
##### 使用 Stack 儲存目前有效的節點
- 由於決策依賴於右側的節點值，因此需要一個 stack 來追蹤當前鏈結中仍然有效的節點
- 透過traverse `curr`，我們可以檢查 `stack[top]` 是否仍符合 ascend/descend 條件
```c
struct list_head *curr = head->next;
struct list_head **stack =
malloc(sizeof(struct list_head *) * q_size(head));
int top = -1;
```
##### 移除不符合條件的節點
- 若 `stack[top]` 不符合排序規則（q_ascend 需要刪除右側更小的節點、q_descend 需要刪除右側更小的節點），則透過 macro `list_del_init()` 將其從鏈結串列中移除，並釋放記憶體。
- 這個過程持續 pop stack，直到 `stack[top]` 符合條件為止。
- 當 curr 經過判斷後，確定它仍然是有效節點，則將其加入 Stack 以便後續比較。
```clike
while (curr != head) {
while (top >= 0 &&
((is_ascend &&
strcmp(list_entry(stack[top], element_t, list)->value,
list_entry(curr, element_t, list)->value) > 0) ||
(!is_ascend &&
strcmp(list_entry(stack[top], element_t, list)->value,
list_entry(curr, element_t, list)->value) < 0))) {
list_del_init(stack[top]);
q_release_element(list_entry(stack[top], element_t, list));
top--;
}
stack[++top] = curr;
curr = curr->next;
}
```
因為這兩個函式的主要核心邏輯相同我將其提出來放在 `q_filter(struct list_head *head, bool is_ascend)` function ，q_ascend, q_descend 可以透過傳入布林值來調整 `q_filter` 的行為。
commit [[00f16088f8929961dc9ccda94411239b3d784c1b](https://github.com/Andrewtangtang/lab0-c/commit/00f16088f8929961dc9ccda94411239b3d784c1b)]
```diff
+ int q_ascend(struct list_head *head)
+ {
+ return q_filter(head, true);
+ }
+ int q_descend(struct list_head *head)
+ {
+ return q_filter(head, false);
+ }
```
### q_sort
commit:[dfc0d4b](https://github.com/sysprog21/lab0-c/commit/dfc0d4b8515c3fff40fb04bbf375424ecdc5367f)
#### 目標
將佇列可以可以按照升序或者是降序排序，並須是stable sort([Stable sort algorithms sort equal elements in the same order that they appear in the input](https://en.wikipedia.org/wiki/Sorting_algorithm))，且必須在時間複雜度 $O(N \log N)$ 下完成
#### 實作細節
由於 Merge Sort 具有 穩定排序（Stable Sort）的特性，並且在各種情況下都能保證 $O(N \log N)$ 的時間複雜度，因此選擇該演算法來實現 `q_sort`。
基本流程如下：
- 切割鏈結串列：使用 find_mid() 劃分鏈結串列的前半部分與後半部分，並不斷遞迴分割，直到每個子鏈結僅剩下一個節點。
- 合併已排序的子鏈結串列：利用 merge() 函數，將排序後的左右子鏈結串列合併，保持 升序/降序 並確保穩定性。
##### 1.切割環狀雙向鏈結串列
在進行 Merge Sort 時，遇到一個 **特殊問題**：`head` 節點不應該被拆分和排序，但它仍然存在於原始環狀雙向鏈結中。因此，遞迴切割前，需要先將 head 從環狀鏈結串列中暫時移除，避免影響排序邏輯，
等到最後排序完後再接上。
```c
void q_sort(struct list_head *head, bool descend)
{
// temporary remove the head
struct list_head *first = head->next;
struct list_head *last = head->prev;
first->prev = last;
last->next = first;
struct list_head *sorted = merge_sort_recursive(first, descend);
// restore the head
sorted->prev->next = head;
head->prev = sorted->prev;
head->next = sorted;
sorted->prev = head;
}
```
##### 2.find_mid() 找到中間節點
由於雙向鏈結串列無法直接存取長度，我們可以利用雙向鏈結串列的特性，使用兩個標從頭尾一起 traverse，找到中間節點，來將鏈結切割成左右兩部分
```c
while (left != right) {
right = right->prev;
if (left == right)
break;
left = left->next;
}
return left;
```
##### 3.merge() 合併已排序的子鏈結串列
在 merge() 過程中，為了方便比較 `left` 和 `right` 的節點，我們先將環狀鏈結暫時斷開
```c
left->prev->next = NULL;
right->prev->next = NULL;
```
這樣 `left` 和 `right` 就變成了 非環狀的鏈結串列，可以透過參考教材 〈[你所不知道的 C 語言: linked list 和非連續記憶體](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 來 merge 兩條 sorted list的方式，但需要額外處理雙向 `prev` 指標維護。`compare`是設計好來回傳比較結果的函式：
```c
while (L1 && L2) {
if (compare(L1, L2, descend)) {
*ptr = L1;
L1 = L1->next;
} else {
*ptr = L2;
L2 = L2->next;
}
(*ptr)->prev = prev;
prev = *ptr;
ptr = &(*ptr)->next;
}
```
最後，將 L1 或 L2 剩餘的部分直接連接到合併後的鏈結中
```c
*ptr = L1 ? L1 : L2;
(*ptr)->prev = prev;
```
##### 4.merge_sort_recursive() 遞迴處理
`merge_sort_recursive()` 是主要的遞迴函式，負責：
- 分割鏈結串列
- 遞迴排序左右兩個子鏈結
- 合併排序結果
```c
struct list_head *mid = find_mid(head, head->prev);
struct list_head *right = mid->next;
// initialize the right list
right->prev = head->prev;
head->prev->next = right;
// initialize the left list with the head
mid->next = head;
head->prev = mid;
struct list_head *left_sorted = merge_sort_recursive(head, descend);
struct list_head *right_sorted = merge_sort_recursive(right, descend);
return merge(left_sorted, right_sorted, descend);
```
### q_merge
commit:[dfc0d4b](https://github.com/sysprog21/lab0-c/commit/dfc0d4b8515c3fff40fb04bbf375424ecdc5367f)
#### 目標
將多條已經排序的佇列，根據指定的升序 (`ascend`) 或降序 (`descend`) 規則，合併為單一排序佇列，確保最終仍維持穩定的排序結果。
#### 實作細節
在這個實作中，每一條待合併的佇列都有一個 `head`，這與一般的鏈結串列合併有所不同。因此，我特別撰寫了一個函式 `merge_lists_with_sentinel_node()` 來處理含 `head` 的雙向環狀鏈結串列的合併，使 `q_merge()` 可以順利進行多條佇列的合併。
##### `merge_lists_with_sentinel_node()`
這邊與上述的 `merge` 函數重複使用的程式碼很多，不同之處在於初始化不用將頭尾斷開，中間迴圈的判斷方法改成是不是已經走回 head 了，之後在把剩餘的部分接上去即可
```diff=
+void merge_lists_with_sentinel_node(struct list_head *l1,
+ struct list_head *l2,
+ bool descend)
+{
+ struct list_head *curr = l1->next;
+ struct list_head *next = l2->next;
+ struct list_head *head = l1, **ptr = &(head->next), *prev = head;
+ while (curr != l1 && next != l2) {
+ // remain code
+ }
```
- 定義一個新的 macro `element_next(pos, member)` 用來取出佇列中下一個元素
```clike
#define element_next(pos, member) \
list_entry((pos)->member.next, typeof(*(pos)), member)
```
- traverse `queue_contex_t` 清單並合併所有佇列，利用 `next` 有沒有回到 `head` 來看合併完成了沒
```clike
for (next = element_next(entry, chain); &next->chain != head;
next = element_next(next, chain)) {
merge_lists_with_sentinel_node(curr, next->q, descend);
}
```
#### 可改進的地方
這裡的許多程式碼與 `q_sort()` 中 `merge` 的函式有許多相同的地方，這兩者的主要區別在於 `sublist`
- `q_sort()` 的 `merge()` 處理的是沒有 head 節點的子鏈結串列，直接進行合併。
- `q_merge()` 的 `merge_lists_with_sentinel_node()` 處理的是每條鏈結都有 head 節點的情況，因此需要特殊處理 head 的連接與初始化。
目前的設計導致了重複的合併邏輯，可以考慮統一 merge 操作，設計一個更通用的函式提高可讀性，也能確保合併邏輯在一致
## 提供新的命令 shuffle
commit:[f135e76](https://github.com/sysprog21/lab0-c/commit/f135e76cf22d65e2d0830bbd2e4c0b4c1b0a9296)
### 實作目標
在 `qtest.c` 中新增 `shuffle` 命令，並實作 Fisher–Yates shuffle 演算法來隨機打亂佇列的節點順序。
### 實作細節
#### 產生隨機數
在洗牌過程中，每次都需要在 1 ~ len 範圍內產生一個隨機索引，來決定要交換的節點。我發現專案內的 `random.c` 提供了一個函式：
```c
int randombytes(uint8_t *buf, size_t n);
```
`randombytes(uint8_t *buf, size_t n)` 這個函式可以產生 n 個 bytes 的隨機數，而其底層通常透過系統呼叫（system call） 來獲取安全隨機數。
因此我創建了一個大小為 8 bytes 的 `uint8_t` 陣列，呼叫 `randombytes()` 來填充這個陣列，將隨機數 byte 陣列轉換成 size_t 型態，取直後對當前長度 size 取 mod 運算，以確保索引值落在合理範圍內
```c
uint8_t random_bytes[8];
randombytes(random_bytes, sizeof(random_bytes));
size_t j = *((size_t *) random_bytes) % size;
```
最後 traverse 整個佇列一次來確保每個點都有被實作隨機交換。
```diff
+ while (curr != head) {
+ //above code
+ size_t j = *((size_t *) random_bytes) % size;
+ struct list_head *target = head->next;
+ for (size_t i = 0; i < j; i++) {
+ target = target->next;
+ }
+ if (curr != target)
+ swap_nodes(curr, target);
+ curr = curr->prev;
+ size--;
+ }
```
### 驗證亂度
commit:[31ff6fc](https://github.com/sysprog21/lab0-c/commit/31ff6fc6ff95a11303474a8ab1ab741ecd9ec2c0)
這裡使用 Pearson's chi-squared test 來檢驗我們實驗所觀察出來的結果是否與理論的亂度相符合，這次的實驗我選擇 `1`、`2`、`3` 三個字串來進行 shuffle洗牌，假設shuffle 是公平的，即由 `1`、`2`、`3` 所排列出來的 6 種排列組合出現的機率應該要相同且加起來合為 1 ，因此我們可以定義虛無假說。
- $H_0$ : shuffle 的結果發生的機率相同，遵守 Uniform distribution
- $𝐻_1$（對立假說）: shuffle 的結果發生的機率至少有一個不同
接下來使用 Pearson's chi-squared test 來驗證 該 shuffle 是否符合 Normal distribution。
#### 計算 _chi-squared test statistic_ $(X^2)$
$$
X^2 = \sum_{i=1}^{n} \frac{(O_i - E_i)^2}{E_i}
$$
- $(X^2)$: Pearson's cumulative test statistic
- $(O_i)$: the number of observations of type \(i\)
- $(E_i)$: the expected count of type \(i\)
- shuffle 結果:
```
total count of results: 100000
Chi-squared values for each permutation:
Permutation | Observation | Expected | Chi-squared
--------------------------------------------------
123 | 16699 | 16666 | 0.0653
132 | 16693 | 16666 | 0.0437
213 | 16575 | 16666 | 0.4969
231 | 16646 | 16666 | 0.0240
312 | 16653 | 16666 | 0.0101
321 | 16734 | 16666 | 0.2775
--------------------------------------------------
Total chi-square sum: 0.9176
Degrees of freedom: 5
Expectation: 16666
Chi-square sum: 0.9175567022680907
```
#### 決定自由度
根據自由度所代表的意義
> Degrees of freedom are the number of independent variables that can be estimated in a statistical analysis and tell you how many items can be randomly selected before constraints must be put in place.
因此在此處，自由度（Degrees of Freedom, df）為 5，表示在這 6 種可能的 shuffle 結果中，我們可以自由選擇 5 個結果的觀察頻率，而第 6 個結果的頻率則必須由前 5 個結果推導而出（因為總數固定，所有機率加總必須為 1）。
#### 選擇顯著水準
顯著水準 $α$ 是統計檢定中設定的錯誤拒絕虛無假設 $H_0$ 的機率，即當即當
$H_0$ 其實是對的時候，我們卻錯誤地拒絕它的機率，一般我們會選擇 5%。接著考慮 $P_{value}$ ，$P_{value}$ 是統計檢定中用來衡量「在虛無假設（$H_0$）為真的情況下，觀察到這種結果的機率」。接著查表發現，我們觀察到的結果 $k=5$ 且 $X^2=0.9175567022680907$，所以 $1>P_{value}>0.95$。
#### 統計檢定的結果不拒絕虛無假說
因為假設要推翻虛無假設 $H_0$ ，則觀察到的結果必須有統計顯著性，即 $P_{value}$ 必須小於顯著水準 $\alpha=0.05$，但從結果來看 $P_{value}>0.95>\alpha$ ，所以統計檢定的結果不拒絕虛無假說 $(H_0)$，也就是說樣本資料不拒絕 shuffle 的結果遵循 Uniform distribution，因為沒有足夠證據推翻。相關測試程式碼與結果放在 [/lab0-c/tests/](https://github.com/Andrewtangtang/lab0-c/tree/master/tests) 中。
## 閱讀論文〈Dude, is my code constant time〉
### Problem
時序攻擊（timing attack）是一種透過觀察程式執行時間，對原本加密的訊息進行反向破解的攻擊方式。然而，以往對程式碼安全性的檢查，大多只能仰賴耗時的人工檢視或使用特定套件來進行評估，而這些檢查方法通常需要針對特定的硬體 CPU 建立模擬環境。但由於 CPU 廠商很少公開其內部運作的詳細資訊，因此要為特定硬體建立一個準確的測量模型是相當困難的。有鑑於此，作者提出了一種名為 `dudect` 的工具，它透過量測程式碼實際的執行時間，並利用統計方法來驗證該段程式碼的執行時間是否符合「constant time」的要求。
### Methods
該方法總共使用三個步驟來測量與統計來得出結論。
#### Step1 Measure execution time
在執行時間測試中，使用兩類資料：Fix（每次輸入固定值）和 Random（每次隨機生成）。Fix 資料通常選擇容易觸發邊緣情況的值，Random 則模擬實際多樣性。每次測量隨機選擇資料類別，並使用 cpucycle counter 或高解析度計時器記錄執行時間。資料準備在測試前完成，確保一致性。
#### Step2 Apply post-processing
在統計分析之前，通常需要對測量數據進行後處理。由於測量過程可能會受到作業系統或其他非相關活動的干擾，導致執行時間的分布偏向執行時間較長的的一邊(正偏向分布)。因此，我們會針對數據進行 cropping 處理，捨棄超過特定閾值的極端數據，以降低測量誤差對分析結果的影響。
#### Step3 Apply statistical test
使用統計的測試來嘗試去拒絕虛無假設(兩組時間數據的分布會相同)
#### (a) t-test
Welch's t-test 是用於檢測兩組資料均值是否相等的簡單統計檢定方法，若檢定失敗，則表示存在均值的資訊洩漏。當 t-test 結合裁剪（cropping）預處理時，由於裁剪屬於非線性轉換，不僅能檢測均值差異，還能捕捉更高階的統計洩漏。
#### (b) Non-parametric tests
非參數檢定（如 Kolmogorov-Smirnov 檢定）對數據分佈的假設較少，適用於分佈未知的情況，優點是靈活且適用範圍廣，但缺點是收斂較慢且需要更多樣本數才能得出穩定結果。
### lab0 dudect程式碼的缺陷
#### 未正確取樣正確範圍內的數據
commit:[b3400ff](https://github.com/sysprog21/lab0-c/commit/b3400ff868cfc92c8a252cbdccedb0b62df31bba)
原本的程式碼想要對測量數據的前後幾筆資料做捨棄，但應該是要跑完 N_MEASURES 次後，沒有在取樣範圍內的數據再做捨棄，而不是直接跑
N_MEASURES -2*DROP_SIZE 的次數。
```diff
- for (size_t i = DROP_SIZE; i < N_MEASURES - DROP_SIZE; i++) {
+ for (size_t i = 0; i < N_MEASURES; i++) {
- before_ticks[i] = cpucycles();
+
+ int64_t beforeticks = cpucycles();
- after_ticks[i] = cpucycles();
+ int64_t afterticks = cpucycles();
int after_size = q_size(l);
dut_free();
+ if (i < DROP_SIZE || i >= N_MEASURES - DROP_SIZE) {
+ continue;
+ }
+ before_ticks[i] = beforeticks;
+ after_ticks[i] = afterticks;}
```
而我認為可以直接需要取樣的資料直接從 `ticks` 陣列的起始開始放即可，這樣之後做 percentile 操作時我們需要去做對執行時間做排序可以從陣列的起始開始排序 N_MEASURES -2*DROP_SIZE 更方便操作，因此我更改為以下版本。
commit:[b08bab1](https://github.com/sysprog21/lab0-c/commit/b08bab11a1c0a47c3198aff2f3be21ebf6502799)
```diff
- for (size_t i = 0; i < N_MEASURES; i++) {
+ for (size_t i = 0, j = 0; i < N_MEASURES; i++) {
// remain code
- before_ticks[i] = beforeticks;
- after_ticks[i] = afterticks;
+ before_ticks[j] = beforeticks;
+ after_ticks[j] = afterticks;
+ j++;
+static void init_percentiles(const int64_t *exec_times)
+ {
+ int64_t *sorted_exec_times =
+ malloc((N_MEASURES - 2 * DROP_SIZE) * sizeof(int64_t));
+ memcpy(sorted_exec_times, exec_times,
+ (N_MEASURES - 2 * DROP_SIZE) * sizeof(int64_t));
+ qsort(sorted_exec_times, N_MEASURES - 2 * DROP_SIZE, sizeof(int64_t),
+
```
#### 並未具備 percentile 驗證方法處理
commit:[b3400ff](https://github.com/sysprog21/lab0-c/commit/b3400ff868cfc92c8a252cbdccedb0b62df31bba)
原始 lab0 程式碼僅對未經裁剪（crop）的原始數據進行檢驗，並未具備像論文中根據不同剪裁區間的百分位數（percentile）內數據去做檢測的驗證方法。參考論文作者提供的 [dudect](https://github.com/oreparaz/dudect) 原始碼，我額外加入了 100 個 percentile 測試點，並透過指數轉換的方式抽取出 100 個不同百分比的裁剪區間。
```diff
+#define DUDECT_NUMBER_PERCENTILES 100
+#define DUDECT_TESTS \
+ (1 + DUDECT_NUMBER_PERCENTILES + 1) // 102 tests percentiles
+
+static t_context_t *ttest_ctxs[DUDECT_TESTS];
+static int64_t *percentiles;
+static void init_percentiles(int64_t *exec_times)
{
- for (size_t i = 0; i < N_MEASURES; i++) {
+ qsort(exec_times, N_MEASURES - 2 * DROP_SIZE, sizeof(int64_t),
+ (int (*)(const void *, const void *)) cmp);
+ for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
+ double p =
+ 1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES));
+ percentiles[i] = percentile(exec_times, p, N_MEASURES - 2 * DROP_SIZE);
+ }
+}
```
這邊我犯了一個錯，我直接對 `exec_times` 做排序會導致原資料順序改變，與 `classes` 陣列的 label 無法對應上。因此我在 commit:[1cc896f](https://github.com/sysprog21/lab0-c/commit/1cc896f382f82f4276a220891c3a7d7b3a5482c5) 做了修正
```diff
-static void init_percentiles(int64_t *exec_times)
+static void init_percentiles(const int64_t *exec_times)
{
- qsort(exec_times, N_MEASURES - 2 * DROP_SIZE, sizeof(int64_t),
+ int64_t *sorted_exec_times =
+ malloc((N_MEASURES - 2 * DROP_SIZE) * sizeof(int64_t));
+ memcpy(sorted_exec_times, exec_times,
+ (N_MEASURES - 2 * DROP_SIZE) * sizeof(int64_t));
+ qsort(sorted_exec_times, N_MEASURES - 2 * DROP_SIZE, sizeof(int64_t),
- percentiles[i] = percentile(exec_times, p, N_MEASURES - 2 * DROP_SIZE);
+ percentiles[i] =
+ percentile(sorted_exec_times, p, N_MEASURES - 2 * DROP_SIZE);
}
+ free(sorted_exec_times);
}
```
透過這項新增的 percentile 檢測方法，能夠更有效地比較分析不同裁剪區間下，測試數據的分布是否符合我們的統計假設。
假設有足夠多的資料，可以從這102筆測試數據中看看最大的 t 有沒有超過我們的threshold，來判斷該程式是否為 constant time。
```diff
+static t_context_t *max_test(t_context_t **ttest_ctxs)
+{
+ int max_index = 0;
+ double max_value = 0;
+ for (size_t i = 0; i < DUDECT_TESTS; i++) {
+ if (ttest_ctxs[i]->n[0] > ENOUGH_MEASURE) {
+ double x = fabs(t_compute(ttest_ctxs[i]));
+ if (x > max_value) {
+ max_value = x;
+ max_index = i;
+ }
+ }
}
+ return ttest_ctxs[max_index];
```
Sign in with Wallet
Connect another wallet