2024q1 Homework1 (lab0)

contributed by < Booker-Chen >

Reviewed by brian049

• 如同老師所說，要注意不要使用到遍歷兩字來代表 traverse。(q_ascend, q_reverseK, q_reverse)
• 在 commit ad18a0e 詳細內容當中提到: Remove still occur nullPointer problem while using cppcheck.，若是不指明 Remove 這個字詞是 q_remove_head 或是 q_remove_tail 函式的名稱，會影響到描述內容的本意。
• 解釋函式的流程語意通順。
• commit message 的詳細內容完整。

誠實面對自己

打開 lab0 的 Hackmd 就直接一股腦兒地開始瞎寫，根本沒看到測試工具跟作業要求那邊，花了一堆時間在通靈，然後又超晚才交表單跟寫 Hackmd 。
commit 那邊也一堆問題真的是。

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。

開發環境

$ 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

allocate 的翻譯是「配置」，以區隔 dispatch (分配/分發) 的翻譯。

用 malloc 分配 記憶體空間，如果 malloc 失敗的話就回傳 NULL。
malloc 成功後用 INIT_LIST_HEAD 建立一個空的佇列。

避免非必要的項目縮排 (即 * 和 - )，以清晰、明確，且流暢的漢語書寫。

q_free

一開始的程式碼為：

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() 做了修改之後

程式碼(修改版本一)：

 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);
}

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

這樣就解決了。

不知道為啥一開始那樣寫會有 [valuableScope] 的問題。

翻閱 Cppcheck 的手冊。

q_insert_head

• 用 malloc() 完成動態分配記憶體和賦值，中間包含對分配失敗的處理。
• 透過 memcpy() 將字串複製進分配的記憶體，並且在結尾補上 '\0'。
• 將處理好的該節點透過 list_add() 插入佇列的首端。

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 雷同。

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。
於是我就把括號刪掉

-    list_add(&(element->list), head);
+    list_add(&element->list, head);

-    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。

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 雷同。

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 遍歷 整個鏈結串列並且用 len 來記錄鏈結串列的長度。

q_delete_mid

• 使用快慢指標來找到中間的節點。
• 透過 list_del 將該節點從佇列中移除。
• 透過 q_release_element 將其刪除。

q_delete_dup

• traverse (動詞) 和 traversal (名詞)

根據 Dictionary.com 的解釋: (作為及物動詞和不及物動詞都有類似的意思，以下列出作為及物動詞的寓意)

• 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) 於統計力學領域 (statistical mechanics) 提出的概念，其一廣為人知的結果是：在經過長時間後，時間平均將會趨近空間平均。此事實在動力系統扮演極重要的角色，在隨機分析領域亦然。

因此，若貿然將 traverse 翻譯為「遍歷」，一來語意不清，二來增加和理工多項領域專業人員的溝通成本，實在得不償失。

$\to$ 資訊科技詞彙翻譯

• 透過 list_for_each_entry_safe 遍歷 整個鏈結串列。
• 變數 find_dup 用來比對相鄰的兩個節點的字串，如果相同即為 true。
• 變數 del_dup 用來確保刪除掉所有重複的節點。

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)跟我遇到的問題很像，照著嘗試一下就解決了。

 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);
...
}

為何不查閱 Cppcheck 的手冊？捨近求遠。

解決方法是說這個變數如果只會在迴圈裏面用到的話那就宣告在迴圈裏面比較好。但是問題來了，為甚麼會比較好？

q_swap

先判斷佇列是否存在、是否為空、是否只有一個節點。
設變數 prev 和 curr 分別代表相鄰兩節點，透過 prev->next = curr->next
、curr->next->prev = prev 等的操作交換相鄰節點的位置。
透過迴圈判斷 prev 和 curr 其中一人是否為 head，是的話代表已經遍歷 整個鏈結串列，迴 圈中止。

善用 List API，撰寫出更精簡的程式碼。

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;
    }
}

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

q_ascend

• 宣告一個布林變數 find_greater 用來檢查右邊是否有比自己小的節點 (自己是否比右邊的節點大)。
• 將 find_greater 和迴圈搭配，重複檢查直到整個佇列都是嚴格遞增的。
• 透過 list_for_each_entry_safe 遍歷整個佇列。
• 將 entry 和 safe 倆倆比較，當 entry 的字串比 safe 大的時候，就把 find_greater 設為 true 並且移除 entry ，然後跳出迴圈再重新遍歷。

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 所以才會跳上面這個錯誤訊息。

 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)

清楚標註你參考的同學的 GitHub 帳號名稱。

逐一檢查 trace-06-ops 會用到的函式以及觀摩同學們 這些函式的寫法後，發現在 descend 中移除的節點也要把其空間透過 q_release_element 釋放掉，但是在題目敘述中卻是寫 remove。

阿這邊其實教授有講，自己沒認真聽，烙賽了。

 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 釋放掉。

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。

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 ：

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。
透過快慢指標找到中心點。
建立兩個佇列的 head ，分別是 left 和 right 。透過 list_splice_tail 和 list_cut_position 將原始佇列切分成左右兩塊。
透過 mergeTwo 將被切分的段落比較並且合併。

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);
}

你如何確保目前的測試程式已涵蓋排序演算法最差的狀況？

q_merge

q_merge 是將所有已排序好的佇列合併成一個同樣排序好的佇列。
因此我們會用到 queue_contex_t 這個結構體。

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

因為 chain 連接著所有的佇列，所以我們可以用 list_for_each_entry 遍歷整個 chain ，將除了第一個佇列以外的佇列都與第一個佇列合併並且計算長度。

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 沒過。

+++ 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?〉

為什麼需要知道程式碼的運行是否為常數時間 ?

在密碼學的實作上，如果程式碼的運行不是常數時間，就能夠透過監測程式碼的執行時間進行時序攻擊，從而取得密碼或金鑰等的機密資訊。Paul C. Kocher 在 1996 年發表的這篇論文 Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems 就是透過監測執行時間進而取得私鑰破解加密系統。

為什麼要選擇使用 dudect

網路上有很多其他常數時間的檢測工具，像是 ctgrind 和 ctverif，那為什麼我們要使用 dudect 呢 ? 因為前面提到的這些檢測工具需要模擬硬體設備，然而要模擬出一個完整並且正確的硬體設備並不是一件容易的事。反觀 dudect 則是透過 leakage detection tests，在目標平台上對一段程式碼做執行時間的統計學分析，如此一來就巧妙的規避需要模擬硬體的問題。

dudect 運作原理

dudect 定義了一些 struct 來協助他完成 timing leakage detection。

我們拿 dudect 給我們的 example.c 來做測試。在 example.c 中定義了 SECRET_LEN_BYTES 這個 macro。我們的目標是測試 check_tag 這個函式的運行是否為常數時間，do_one_computation 這個函式則會被一直執行。

/* 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 演算法實作洗牌 (Shuffle)