# 2024q1 Homework1 (lab0)
contributed by < `Booker-Chen` >
### Reviewed by `brian049`
- 如同老師所說，要注意不要使用到遍歷兩字來代表 traverse。(`q_ascend`, `q_reverseK`, `q_reverse`)
- 在 [commit ad18a0e](https://github.com/Booker-Chen/lab0-c/commit/ad18a0eb5709b2261a70d64d860de0bab43ccc10) 詳細內容當中提到: `Remove still occur nullPointer problem while using cppcheck.`，若是不指明 `Remove` 這個字詞是 `q_remove_head` 或是 `q_remove_tail` 函式的名稱，會影響到描述內容的本意。
- 解釋函式的流程語意通順。
- commit message 的詳細內容完整。
## 誠實面對自己
打開 lab0 的 Hackmd 就直接一股腦兒地開始瞎寫，根本沒看到測試工具跟作業要求那邊，花了一堆時間在通靈，然後又超晚才交表單跟寫 Hackmd 。
commit 那邊也一堆問題真的是。
:::danger
留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。
:::
## 開發環境
```shell
$ 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: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 2
On-line CPU(s) list: 0,1
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i7-10870H CPU @ 2.20GHz
CPU family: 6
Model: 165
Thread(s) per core: 1
Core(s) per socket: 2
Socket(s): 1
Stepping: 2
BogoMIPS: 4416.01
Virtualization features:
Hypervisor vendor: KVM
Virtualization type: full
Caches (sum of all):
L1d: 64 KiB (2 instances)
L1i: 64 KiB (2 instances)
L2: 512 KiB (2 instances)
L3: 32 MiB (2 instances)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0,1
```
## 檢測工具
`cppcheck --enable=all --suppress=missingIncludeSystem <c file>`：用來檢測 `<c file>` 的靜態程式碼有沒有出錯。
`make check`：用來看函式有沒有正確執行。
`make test`：測試程式。
`clang-format -i queue.c`：`commit` 之前可以用這個指令檢查程式碼排版。
## 針對佇列操作的程式碼實作
### `q_new`
:::danger
allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯。
:::
用 `malloc` <s>分配</s> 記憶體空間，如果 `malloc` 失敗的話就回傳 `NULL`。
`malloc` 成功後用 `INIT_LIST_HEAD` 建立一個空的佇列。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
:::
### q_free
一開始的程式碼為：
```c
void q_free(struct list_head *head)
{
if (!head)
return;
struct list_head *current = head->next, *del;
while (current != head) {
del = current;
current = current->next;
free(list_entry(del, element_t, list));
}
free(current);
}
```
結果在 `commit` 的時候跳出一段關於 `[variableScope]` 的問題出來
```
Following files need to be cleaned up:
queue.c
queue.c:32:46: style: The scope of the variable 'del' can be reduced. [variableScope]
struct list_head *current = head->next, *del;
^
Fail to pass static analysis.
```
然後我用 `cppcheck --enable=all queue.c` 檢查我的程式碼又找到一個 `[nullPointer]` 的問題
```
queue.c:36:14: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
free(list_entry(del, element_t, list));
^
```
結合 `list.h` 中的 `list_for_each_entry_safe()` 和 `queue.h` 中的`q_release_element()` 做了修改之後
程式碼(修改版本一)：
```diff
void q_free(struct list_head *head)
{
if (!head)
return;
- struct list_head *current = head->next, *del;
- while (current != head) {
- del = current;
- current = current->next;
- free(list_entry(del, element_t, list));
- }
+ element_t *element, *element_safe;
+ list_for_each_entry_safe (element, element_safe, head, list)
+ q_release_element(element);
+ free(head);
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
這樣就解決了。
不知道為啥一開始那樣寫會有 `[valuableScope]` 的問題。
:::danger
翻閱 Cppcheck 的手冊。
:::
### q_insert_head
* 用 `malloc()` 完成動態分配記憶體和賦值，中間包含對分配失敗的處理。
* 透過 `memcpy()` 將字串複製進分配的記憶體，並且在結尾補上 `'\0'`。
* 將處理好的該節點透過 `list_add()` 插入佇列的首端。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element) {
free(element);
return false;
}
int n = strlen(s) + 1;
element->value = malloc(n * sizeof(char));
if (!(element->value)) {
q_release_element(element);
return false;
}
memcpy(element->value, s, n);
(element->value)[n - 1] = '\0';
list_add(&element->list, head);
return true;
}
```
### q_insert_tail
和 `q_insert_head` 雷同。
```c
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *element = malloc(sizeof(element_t));
if (!element) {
free(element);
return false;
}
int n = strlen(s) + 1;
element->value = malloc(n * sizeof(char));
if (!(element->value)) {
q_release_element(element);
return false;
}
memcpy(element->value, s, n);
(element->value)[n - 1] = '\0';
list_add_tail(&element->list, head);
return true;
}
```
`q_insert_head` 和 `q_insert_tail` 不知道為甚麼會在這個奇怪的地方有 `Memory Leak`
```
queue.c:55:5: error: Memory leak: element [memleak]
return true;
^
queue.c:75:5: error: Memory leak: element [memleak]
return true;
^
```
透過錯誤訊息發現出錯的地方應該就在 `list_add` 這裡，後來去作業區觀摩一下大家 `insert` 的部分，發現大家的寫法都是 `$element->list`。
於是我就把括號刪掉
```diff
- list_add(&(element->list), head);
+ list_add(&element->list, head);
```
```diff
- list_add_tail(&(element->list), head);
+ list_add_tail(&element->list, head);
```
再執行一次 `cppcheck queue.c` ，發現 `Memeory Leak` 的問題就被解決了。
>問題：`&(element->list)` 和 `&element->list` 是等價的嗎 ?
### q_remove_head
* 事先檢查佇列是否存在或者為空。
* 若佇列存在且不為空，則將佇列的首個節點透過 `list_del` 將其從佇列中**移除**。
* 將被移除的節點的字串透過 `strncpy` 複製進 `sp` 裡面，進行複製前先檢查 `sp` 是否存在以及 `buffsize` 是否大於 0。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element = list_first_entry(head, element_t, list);
list_del(head->next);
if (sp && bufsize) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return element;
}
```
### q_remove_tail
和 `q_remove_head` 雷同。
```c
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
element_t *element = list_entry(head->prev, element_t, list);
list_del(head->prev);
if (sp && bufsize) {
strncpy(sp, element->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
return element;
}
```
`q_remove_head` 和 `q_remove_tail` 又發生了跟 `q_free` 一樣的 `[nullPointer]` 問題。
```
queue.c:83:26: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *element = list_entry(head->next, element_t, list);
^
queue.c:97:26: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
element_t *element = list_entry(head->prev, element_t, list);
^
```
### q_size
透過 `list_for_each` <s>遍歷</s> 整個鏈結串列並且用 `len` 來記錄鏈結串列的長度。
### q_delete_mid
* 使用**快慢指標**來找到中間的節點。
* 透過 `list_del` 將該節點從佇列中**移除**。
* 透過 `q_release_element` 將其**刪除**。
### q_delete_dup
:::danger
- [x] traverse (動詞) 和 traversal (名詞)
根據 Dictionary.com 的[解釋](https://www.dictionary.com/browse/traverse
): (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)
* to pass or move over, along, or through.
* to go to and fro over or along.
其實這意思很好懂，就像我們「走過」/「穿越」校園一般，於是 traverse a linked list 就會是「(用某種手段) 存取多個鏈結串列的節點」，但這裡卻沒有必要「所有」的範圍：英語的 "move over/through" 用於某個區域時，根本沒有這樣的隱含意義。如果將 traverse 翻譯為「遍歷」，就會導致「超譯」，也就是跳脫「直譯」和「意譯」。
當我們回頭看 "traverse" 所在的技術描述內容，例如 "traverse every node"，若翻譯為「遍歷每個節點」，那麼既然都「遍」(意即「全面」、「到處」)，又何來「每個」節點呢？於是，合理的翻譯應改為「逐一走訪每個節點」 —— 差異在哪？在 "traverse every node" 的應用場景中，可能是我們嘗試在鏈結串列尋找特定的節點內含的資料，一旦找到就停止，或者我們要偵測給定的鏈結串列是否包含環狀 (circular) 結構 ，並沒有真的要「遍」(到處/全面)「歷」(意即「經過」) 每個節點。在我們的用語中，要區分「意圖」(intention) 和「實際作用」(reaction)，濫用「遍歷」會使得語意不清，從而難以推測英語原文的訴求。
還有個更重要的原因是，「遍歷」這詞已在理工領域存在，且廣泛使用，即「遍歷理論」(Ergodic theory)，後者是研究具有不變測度 (invariant measure) 的動力系統及其相關問題的一個數學分支。 遍歷理論研究遍歷變換，由試圖證明統計物理中的遍歷假設 (Ergodic hypothesis) 演進而來。
在統計學中，若單一個物理系統在不同時間內重複相同的實驗 (如丟擲一枚硬幣)，其取樣數據所得的統計結果 (如硬幣出現正面的機率) 和極多個完全相同的物理系統的系集 (如丟極多個相同的硬幣) 在同時作相同的實驗取樣數據的統計結果假設為相同時，此種假設即稱為「遍歷性假設」或「遍歷假設」。基於這個假設，對時間平均的統計方式及結果，便可由對系集的平均及統計方式得到。在一般物理系統中，尤其在統計力學範圖中，均採用此遍歷性假設為基本的假設。在流體力學中對亂流的實驗分析，亦是採用此假設。
遍歷 (Ergodic) 源於以下二個希臘詞：
* ergon (對應英語的 work)
* odos (對應英語的 path 或 way)
最初這是由奧地利物理學家波茲曼 ([Ludwig Boltzmann](https://en.wikipedia.org/wiki/Ludwig_Boltzmann)) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。
因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
* 透過 `list_for_each_entry_safe` <s>遍歷</s> 整個鏈結串列。
* 變數 `find_dup` 用來比對相鄰的兩個節點的字串，如果相同即為 `true`。
* 變數 `del_dup` 用來確保刪除掉所有重複的節點。
```c
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
element_t *element, *element_dup;
int find_dup;
bool del_dup = false;
list_for_each_entry_safe(element_dup, element, head, list) {
if (&element->list == head)
break;
find_dup = strcmp(element_dup->value, element->value);
if (find_dup == 0) {
del_dup = true;
list_del(&element_dup->list);
q_release_element(element_dup);
}
if (find_dup != 0 && del_dup) {
list_del(&element_dup->list);
q_release_element(element_dup);
del_dup = false;
}
}
if (del_dup) {
list_del(&element_dup->list);
q_release_element(element_dup);
}
return true;
}
```
這樣寫會有 `[variableScope]` 的問題
```
queue.c:151:9: style: The scope of the variable 'find_dup' can be reduced. [variableScope]
int find_dup;
^
```
前面的 `q_free` 也有出現過但是莫名其妙的就解學了。這次看不出個所以然，上網找資料看到 [CppCheck. The scope of the variable can be reduced (and loop)](https://stackoverflow.com/questions/23604699/cppcheck-the-scope-of-the-variable-can-be-reduced-and-loop)跟我遇到的問題很像，照著嘗試一下就解決了。
```diff
bool q_delete_dup(struct list_head *head)
{
...
- int find_dup;
bool del_dup = false;
list_for_each_entry_safe(element_dup, element, head, list) {
if (&(element->list) == head)
break;
- find_dup = strcmp(element_dup->value, element->value);
+ int find_dup = strcmp(element_dup->value, element->value);
...
}
```
:::danger
為何不查閱 Cppcheck 的手冊？捨近求遠。
:::
>解決方法是說這個變數如果只會在迴圈裏面用到的話那就宣告在迴圈裏面比較好。但是問題來了，為甚麼會比較好？
### q_swap
先判斷佇列是否存在、是否為空、是否只有一個節點。
設變數 `prev` 和 `curr` 分別代表相鄰兩節點，透過 `prev->next = curr->next`
、`curr->next->prev = prev` 等的操作交換相鄰節點的位置。
透過迴圈判斷 `prev` 和 `curr` 其中一人是否為 `head`，是的話代表已經<s>遍歷</s> 整個鏈結串列，迴 圈中止。
:::warning
善用 List API，撰寫出更精簡的程式碼。
:::
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *curr = head->next->next, *prev = head->next;
while (prev != head && curr != head) {
prev->next = curr->next;
curr->next->prev = prev;
curr->prev = prev->prev;
prev->prev->next = curr;
curr->next = prev;
prev->prev = curr;
prev = prev->next;
curr = prev->next;
}
}
```
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
### q_ascend
* 宣告一個布林變數 `find_greater` 用來檢查右邊是否有比自己小的節點 (自己是否比右邊的節點大)。
* 將 `find_greater` 和迴圈搭配，重複檢查直到整個佇列都是嚴格遞增的。
* 透過 `list_for_each_entry_safe` 遍歷整個佇列。
* 將 `entry` 和 `safe` 倆倆比較，當 `entry` 的字串比 `safe` 大的時候，就把 `find_greater` 設為 `true` 並且移除 `entry` ，然後跳出迴圈再重新遍歷。
```c
int q_ascend(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return q_size(head);
bool find_greater = true;
element_t *element1, *element2;
while (find_greater) {
find_greater = false;
list_for_each_entry_safe (element1, element2, head, list) {
if (&element2->list == head)
break;
if (strcmp(element1->value, element2->value) >= 0) {
find_greater = true;
list_del(&element1->list);
break;
}
}
}
return q_size(head);
}
```
### q_descend
和 `q_ascend` 雷同，只是改成**嚴格遞減**。
在執行 `trace-06-ops` 時，發現有 `Segmentation fault` 的問題。
用 `make valgrind` 檢查後發現這個錯誤訊息
```
==20643== Invalid read of size 1
==20643== at 0x484FBD7: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==20643== by 0x10FE3B: q_descend (queue.c:328)
==20643== by 0x10B939: do_descend (qtest.c:752)
==20643== by 0x10DFD1: interpret_cmda (console.c:181)
==20643== by 0x10E592: interpret_cmd (console.c:201)
==20643== by 0x10E821: cmd_select (console.c:593)
==20643== by 0x10F10D: run_console (console.c:673)
==20643== by 0x10D3C3: main (qtest.c:1258)
==20643== Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==20643==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
回去檢查之後發現是當 `element2` 指向的位置為 `head` 時，仍會與 `element1` 做 `strcmp`。但是 `head` 只是一個 `list_head` 建構子，不是 `element_t` 所以才會跳上面這個錯誤訊息。
```diff
list_for_each_entry_safe (element1, element2, head, list) {
+ if (&element2->list == head)
+ break;
...
```
只要在 `list_for_each_entry_safe` 裡面加上這行就解決了。
但是又跳出 `Memory Leak` 的問題。
```
ERROR: There is no queue, but 4 blocks are still allocated
ERROR: Freed queue, but 4 blocks are still allocated
==21352== 84 bytes in 2 blocks are still reachable in loss record 1 of 2
==21352== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21352== by 0x10F2E7: test_malloc (harness.c:133)
==21352== by 0x10F7AC: q_insert_head (queue.c:49)
==21352== by 0x10CB32: queue_insert (qtest.c:232)
==21352== by 0x10CD00: do_ih (qtest.c:280)
==21352== by 0x10DFD1: interpret_cmda (console.c:181)
==21352== by 0x10E586: interpret_cmd (console.c:201)
==21352== by 0x10E987: cmd_select (console.c:610)
==21352== by 0x10F273: run_console (console.c:705)
==21352== by 0x10D3C3: main (qtest.c:1258)
```
:::danger
清楚標註你參考的同學的 GitHub 帳號名稱。
:::
逐一檢查 `trace-06-ops` 會用到的函式以及觀摩<s>同學們</s> 這些函式的寫法後，發現在 `descend` 中移除的節點也要把其空間透過 `q_release_element` 釋放掉，但是在題目敘述中卻是寫 `remove`。
:::warning
阿這邊其實教授有講，自己沒認真聽，烙賽了。
:::
```diff
int q_dscend(struct list_head *head)
{
if (!head || list_empty(head) || list_is_singular(head))
return q_size(head);
bool find_smaller = true;
element_t *element1, *element2;
while (find_smaller) {
find_smaller = false;
list_for_each_entry_safe (element1, element2, head, list) {
if (&element2->list == head)
break;
if (strcmp(element1->value, element2->value) <= 0) {
find_smaller = true;
list_del(&element1->list);
+ q_release_element(element1);
break;
}
}
}
return q_size(head);
}
```
這樣 `trace-06-ops` 就過了。
### q_reverse
* 題目要求這個函式不能動態分配記憶體。
* 用迴圈遍歷整個佇列，將每一個節點的 `next` 和 `prev` 對調。
### q_reverseK
* 用 `q_new` 創建兩個新佇列的 `head`，分別是 `reverse_op` 和 `reverse_concat`。
* 透過迴圈將原始佇列的節點透過 `list_move` 一直移到 `reverse_op` 的首端 (這樣就等於反轉)，當迴圈跑了 `k` 次之後，就把 `reverse_op` 透過 `list_splice_tail_init` 接到 `reverse_concat` 上。
* 當原始佇列剩餘的節點數少於 `k` 之後，再把 `reverse_concat` 透過 `list_sprice_init` 接到原始佇列的首端。
* 把 `reverse_op` 和 `reverse_concat` 釋放掉。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *reverse_concat = q_new(), *reverse_op = q_new();
int n = q_size(head);
while (n >= k) {
for (int i = 0; i < k; i++) {
list_move(head->next, reverse_op);
}
list_splice_tail_init(reverse_op, reverse_concat);
n -= k;
}
while (!list_empty(head))
list_splice_init(reverse_concat, head);
free(reverse_op);
free(reverse_concat);
}
```
寫完之後測試發現...這個函式好像也不能動態分配記憶體。
```
FATAL ERROR: Calls to malloc disallowed
FATAL Error. Exiting
```
所以就只能換一種寫法了
* 透過迴圈遍歷整個佇列。
* 在遍歷的過程中，將每 `k` 個段落做一次反轉。
* 創建一個函式 `reverse_seg` 來達成每 `k` 個段落反轉一次，中間會用到前面寫好的 `reverse`。
```c
struct list_head *reverse_seg(struct list_head *start, int k) {
struct list_head *end = start, *next, *prev;
for (int i = 1; i < k; i++) {
end = end->next;
}
next = end->next;
prev = start->prev;
end->next = start;
start->prev = end;
q_reverse(start);
end->prev = prev;
prev->next = end;
start->next = next;
next->prev = start;
return start;
}
```
不用 `malloc` 的 `reverseK` ：
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head) || list_is_singular(head))
return;
struct list_head *current = head->next;
int n = q_size(head);
while (n >= k) {
current = reverse_seg(current, k);
current = current->next;
n -= k;
}
}
```
### q_sort
採用遞迴式的 `merge sort`
程式碼及架構參考 [ShallowFeather](https://hackmd.io/@ShallowFeather/lab0-2023#q_sort)。
透過**快慢指標**找到中心點。
建立兩個佇列的 `head` ，分別是 `left` 和 `right` 。透過 `list_splice_tail` 和 `list_cut_position` 將原始佇列切分成左右兩塊。
透過 `mergeTwo` 將被切分的段落比較並且合併。
```c
void mergeTwo(struct list_head *left,
struct list_head *right,
struct list_head *head,
bool descend)
{
while (!list_empty(left) && !list_empty(right)) {
element_t *element1 = list_entry(left->next, element_t, list);
element_t *element2 = list_entry(right->next, element_t, list);
if (descend) {
if (strcmp(element1->value, element2->value) >= 0)
list_move_tail(left->next, head);
else
list_move_tail(right->next, head);
} else {
if (strcmp(element1->value, element2->value) <= 0)
list_move_tail(left->next, head);
else
list_move_tail(right->next, head);
}
}
if (!list_empty(left))
list_splice_tail(left, head);
else
list_splice_tail(right, head);
}
```
:::danger
你如何確保目前的測試程式已涵蓋排序演算法最差的狀況？
:::
### q_merge
`q_merge` 是將所有已排序好的佇列合併成一個同樣排序好的佇列。
因此我們會用到 `queue_contex_t` 這個結構體。
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
因為 `chain` 連接著所有的佇列，所以我們可以用 `list_for_each_entry` 遍歷整個 `chain` ，將除了第一個佇列以外的佇列都與第一個佇列合併並且計算長度。
```c
queue_contex_t *contex = list_first_entry(head, queue_contex_t, chain), *curr;
list_for_each_entry (curr, head, chain) {
if (curr == contex)
continue;
contex->size += curr->size;
list_splice_tail_init(curr->q, contex->q);
}
```
之後再對佇列使用先前寫好的 `q_sort` 排序即可。
寫到目前這個階段在本地執行 `make test` 可以拿滿 100 分。但是推到 GitHub 上透過 Action 測試的時候發現 `trace-17-complexity` 沒過。
```error
+++ TESTING trace trace-17-complexity:
--- trace-17-complexity 0/5
--- TOTAL 95/100
make: *** [Makefile:60: test] Error 1
Error: Process completed with exit code 1.
```
## 研讀論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉
### 為什麼需要知道程式碼的運行是否為常數時間 ?
在密碼學的實作上，如果程式碼的運行不是常數時間，就能夠透過監測程式碼的執行時間進行[時序攻擊](https://en.wikipedia.org/wiki/Timing_attack)，從而取得密碼或金鑰等的機密資訊。Paul C. Kocher 在 1996 年發表的這篇論文 [Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems](https://link.springer.com/chapter/10.1007/3-540-68697-5_9) 就是透過監測執行時間進而取得私鑰破解加密系統。
### 為什麼要選擇使用 [dudect](https://github.com/oreparaz/dudect)
網路上有很多其他常數時間的檢測工具，像是 [ctgrind](https://github.com/agl/ctgrind) 和 [ctverif](https://github.com/michael-emmi/ctverif)，那為什麼我們要使用 dudect 呢 ? 因為前面提到的這些檢測工具需要模擬硬體設備，然而要模擬出一個完整並且正確的硬體設備並不是一件容易的事。反觀 dudect 則是透過 [leakage detection tests](https://dl.acm.org/doi/pdf/10.1145/1015047.1015050)，在目標平台上對一段程式碼做執行時間的統計學分析，如此一來就巧妙的規避需要模擬硬體的問題。
### [dudect](https://github.com/oreparaz/dudect) 運作原理
dudect 定義了一些 `struct` 來協助他完成 timing leakage detection。
我們拿 dudect 給我們的 [example.c](https://github.com/oreparaz/dudect/blob/master/examples/simple/example.c) 來做測試。在 example.c 中定義了 `SECRET_LEN_BYTES` 這個 `macro`。我們的目標是測試 `check_tag` 這個函式的運行是否為常數時間，`do_one_computation` 這個函式則會被一直執行。
```c
/* target function to check for constant time */
int check_tag(uint8_t *x, uint8_t *y, size_t len) {
return memcmp(x, y, len);
}
#define SECRET_LEN_BYTES (512)
uint8_t secret[SECRET_LEN_BYTES] = {0, 1, 2, 3, 4, 5, 6, 42};
/* this will be called over and over */
uint8_t do_one_computation(uint8_t *data) {
/* simulate totally bogus MAC check in non-constant time */
return check_tag(data, secret, SECRET_LEN_BYTES);
}
```
## 利用 [Fisher–Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm) 演算法實作洗牌 (Shuffle)
Sign in with Wallet
Connect another wallet