2024q1 Homework1 (lab0)

contributed by < shiang1212 >

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

Reviewed by `ssheep773`

這四個 commit 都是使用相同的 commit message "Add files via upload"
commit 3085d94 、 commit 7cfd185 、 commit fdd430b 、 commit 21feb34 ，使用相同的名稱且並未說明實際的更改內容，會導致後續維護困難

Reviewed by `SimonLee0316`

在 git commit 時，不同功能建議分開，這樣才好維護

明確指出是哪幾個 git commits，既然你認為這位學員做不好，那就做出一次好的給他看，這樣才有討論和學習的效果。

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

Reviewed by `stevendd543`

在你比較 malloc 與 calloc 差異時，你將未初始化的 malloc 印出 0 的原因在於，讀取未被初始化的記憶體在 C 語言中屬於未定義的行為，因此在印出來的值是 garbage value 剛好是 0。參考資料
不必列出完整程式碼，我也是被老師提醒過，但後來發現不如把遇到的問題分析條列出來，不僅提醒自己，讀者也能學到東西。

首先宣告一個 element_t，並為其配置記憶體，若配置失敗則回傳 false。接著為該 element_t 的 char *value 配置記憶體，注意 malloc 的記憶體大小為 strlen(s) + 1，應該是考慮到字串結束符號 '\0。此時如果配置失敗，在則回傳 false 之前，記得要把剛剛配置好的記憶體釋放掉。接著使用 strcpy 將字串內容 s 複製給該 element_t 的 char *value，這樣就完成了新節點的宣告。

舉例這段來說，其實你想表達在配置記憶體的流程與注意事項，這是好的探討，但在漢語上有些不通順，當你回頭看自己的筆記時，會發現自己把簡單的邏輯敘述的太雜亂。

開發環境

$ 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):                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 max MHz:           4100.0000
CPU min MHz:           800.0000
BogoMIPS:              4399.99
Virtualization:        VT-x
Caches (sum of all):     
L1d:                   192 KiB (6 instances)
L1i:                   192 KiB (6 instances)
L2:                    1.5 MiB (6 instances)
L3:                    9 MiB (1 instance)

指定的佇列操作

先備知識

`element_t`

typedef struct {
    char *value;
    struct list_head list;
} element_t;

`list_head`

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

element_t 作為佇列中的基本元素（節點），該結構體的成員有 char *value 與 struct list_node list，前者用來表示該節點裝著什麼字串，後者為一結構體裝著兩個 struct list_head 的指標，用來表示該元素的前一個與後一個節點記憶體位置。

改進你的漢語表達。

整體架構如下圖：

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

參考~~其他同學~~ 的圖後，發現製圖方法仍有錯誤，

明確標注同學的 GitHub 帳號名稱。

應使用 HackMD 中的程式碼區塊，如下

```graphviz

(程式碼)

```

待修改

使用 Graphviz 製圖，並嵌入到 HackMD
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。

`q_new`

程式碼註解一律用美式英語書寫。

struct list_head *q_new()
{
    struct list_head *head = malloc(sizeof(struct list_head));
+    if(!head)
+        return NULL;
    INIT_LIST_HEAD(head); // prev and next point to head
    return head;
}

用語要精準，「正常」和「不正常」的分野對應於記憶體配置是如何？

已修正

第 3 行使用到 malloc 配置記憶體給 head，在記憶體空間充足且先前行為不存在記憶體越界存取的情況，malloc 會配置一個大小為 struct list_head 位元組 (Byte) 的記憶體，並回傳一個指標指向該記憶體，但並不是每次 malloc 都會那麼順利。

access 的翻譯是「存取」，而非「訪問」(visit)。
改進你的漢語表達。

~~已修正~~
沒做到的事，不要輕易宣告。你認為上述是清晰、明確，且通順的漢語表達嗎？

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

前後關聯是什麼？

以下節錄自 cmd 執行 $ man malloc 之結果：

RETURN VALUE

The malloc() and calloc() functions return a pointer to the allocated memory, which is suitably aligned for any built-in type. On error, these functions return NULL. NULL may also be returned by a successful call to malloc() with a size of zero, or by a successful call to calloc() with nmemb or size equal to zero.

使用 malloc 配置記憶體，在成功配置的情況下，malloc 會回傳一個指標指向對應大小的記憶體位置；在配置失敗或 size 為 0 的情況下，malloc 會回傳 NULL。所以需要用第 4～5 行。

此外，malloc 的 man page 提到：

The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

The calloc() function allocates memory for an array of nmemb elements of size bytes each and returns a pointer to the allocated memory. The memory is set to zero. If nmemb or size is 0, then calloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

相比使用 calloc，在使用 malloc 配置記憶體時，該記憶體不會被初始化成 0。

好奇 malloc 丟出來的未初始化記憶體長怎樣，所以我寫了以下程式測試： (test.c)

#include <stdio.h>
#include <stdlib.h>

int main() 
{
    int *arr = malloc(sizeof(int) * 16);
    for(int i = 0; i < 16; i++)
        printf("%d ", *(arr + i));

    return 0;
}

編譯並執行：

$ gcc test.c`
$ ./a.out`

得到的結果：
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

工程人員說話要精準，避免說「好像」。

不知道為什麼~~看起來好像~~初始化過，在猜會不會是沒被修改過的記憶體都是初始化為 0，或是 OS 和編譯器的關係，待研究。
sbrk()?
program break?

`q_free`

void q_free(struct list_head *head) 
{
    if (!head)
        return;
    element_t *entry, *safe;
    list_for_each_entry_safe (entry, safe, head, list)
        q_release_element(entry);
    free(head);

    return;
}

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

已修正

若 head 為空，則代表沒有記憶體需要被釋放，所以 return。接下來使用 list.h 裡面提供的 list_for_each_entry_safe 走訪每個節點。再使用 q_release_element 回收該節點的記憶體。最後回收掉 head 本身。

不該先列出程式碼，相反的，你該先探討自己的想法、考慮因素，具體實施的方案，過程中可能會有副作用 (side effect)，這都要涵蓋。這是工程素養之一，即有效的溝通。

`q_insert_head`

bool q_insert_head(struct list_head *head, char *s)
{
    element_t *new = malloc(sizeof(element_t));
    if(!new)
        return false;
    new->value = malloc(strlen(s) + 1);
    if(!new->value)
    {
        free(new);
        return false;
    }
    
    strcpy(new->value, s);
    list_add(&new->list, head);

    return true;

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

~~已修正~~
沒做到的事，不要輕易宣告。你認為這份筆記以清晰、明確，且通順的漢語書寫嗎？

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

jserv

首先宣告一個 element_t，並為其配置記憶體，若配置失敗則回傳 false。接著為該 element_t 的 char *value 配置記憶體，注意 malloc 的記憶體大小為 strlen(s) + 1，應該是考慮到字串結束符號 '\0。此時如果配置失敗，在則回傳 false 之前，記得要把剛剛配置好的記憶體釋放掉。接著使用 strcpy 將字串內容 s 複製給該 element_t 的 char *value，這樣就完成了新節點的宣告。

準備好要新增的節點之後，使用 list.h 提供的 list_add，將該element_t 串在 head 的前面，達到新增 element_t 於佇列前端之效果。

參考 wanghanchi，在執行字串複製時，他使用 memcpy 取代 strcpy。

我查看 strcpy 的 man page

char *strcpy(char *dest, const char *src);

DESCRIPTION

The strcpy() function copies the string pointed to by src, including the terminating null byte ('\0'), to the buffer pointed to by dest. The strings may not overlap, and the destination string dest must be large enough to receive the copy. Beware of buffer overruns! (See BUGS.)

BUGS

If the destination string of a strcpy() is not large enough, then anything might happen. Overflowing fixed-length string buffers is a favorite cracker technique for taking complete control of the machine. Any time a program reads or copies data into a buffer, the program first needs to check that there's enough space. This may be unnecessary if you can show that overflow is impossible, but be careful: programs can get changed over time, in ways that may make the impossible possible.

總而言之，strcpy 會走訪 src 指向的字串的每個字元，在碰到空字元 '\0' 之前，逐 Byte 寫入 dest。但 strcpy 缺乏寫入合法性的判斷，影響程式的穩健性 (robustness)。

而 string.h 裡有一個與 strcpy 相似的函式：char *strncpy(char *dest, const char *src, size_t n)，以下為 strncpy 的 man page 提供的實作範例：

char *strncpy(char *dest, const char *src, size_t n)
{
    size_t i;

    for (i = 0; i < n && src[i] != '\0'; i++)
        dest[i] = src[i];
    for ( ; i < n; i++)
        dest[i] = '\0';
    return dest;
}

這個函式相較 strcpy 多了一個 size_t n 參數，用來表示要寫入 dest 的字元數量，在呼叫函式的時候就先決定好要寫入的字元數量，確保不會有 overflow 的情況發生。

`q_insert_tail`

如 q_insert_head ，把 list_add(&new->list, head) 改成 list_add_tail(&new->list, head)即可。

`q_remove_head`

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;
    element_t *remove = list_entry(head->next, element_t, list);
    if (bufsize)
    {
        strncpy(sp, remove->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&remove->list);
    return remove;
}

`q_remove_head`、`q_remove_tail`

宣告一個 element_t 指標指向要刪除的節點 (head->next 或 head->prev)。確認 bufisze != 0並將該節點的字串內容複製給 sp，最後用 list_del 將該節點從鏈結串列中移除。

`q_size`

先判斷該鏈結串列是否為空，是的話 return 0。接著走訪該鏈結串列的每個節點並累計長度。

`q_delete_mid`

bool q_delete_mid(struct list_head *head) 
{
    if (!head)
        return false;
    struct list_head *fast = head->next->next, *slow = head->next;
    while (!(fast == head->prev) && !(fast == head))
    {
        fast = fast->next->next;
        if (fast == head->prev || fast == head) {
            break;
        }
        slow = slow->next;
    }
    element_t *node = list_entry(slow->next, element_t, list);
    list_del(&node->list);
    q_release_element(node);
    return true;
    // https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/
}

7cfd185 中的 q_delete_mid，成功通過 2095. Delete the Middle Node of a Linked List，但完全無法應用在環狀雙向鏈結的場景下，於是我參考 wanghanchi 以及你所不知道的 C 語言: linked list 和非連續記憶體中的龜兔賽跑 (快慢指標) 方法。

什麼「核心」？本課程叫什麼名字，你還記得嗎？

已修正

想法如下：

慢指標 slow 一次走一步，快指標 fast 一次走兩步，fast 走的步數會是 slow 的兩倍，所以當 fast 走完鏈結串列的總長時，這時的 slow 只走了鏈結串列長度的一半，也就是走到鏈結串列的中間節點，正好是 q_delete_mid 所要刪除的節點。

而判斷 fast 是否走到環狀鏈結串列的尾端可以分成兩個情況：

鏈結串列的長度為奇數：

fast 從 head 出發後，每次走兩步，只會停在 head 和 Even 節點，而 fast 在走完鏈結串列的總長時，會剛好回到 head，判斷 fast == head 即可確認fast 是否走到該環狀鏈結串列的尾端。
鏈結串列的長度為偶數：

這個情況 fast 只會停在 Even 節點，而最後一個 Even 節點正是 head->prev，所以判斷 fast == head->prev。

`q_swap`

參考 wanghanchi 的程式碼，兩個節點位置交換，簡單來說就是把後者取出，放到前者的前面，且因為是每兩個節點的交換，所以執行完交換後指標要往前兩個節點。

`q_reverse`

void q_reverse (struct list_head *head) 
{
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) 
        list_move(node, head);
}

參考 randv 的程式碼，使用 list_for_each_safe 走訪每個節點，用 list_move 將每個節點移除並放在 head 前端。

`q_reverseK`





















void q_reverseK(struct list_head *head, int k)
{
    // https://leetcode.com/problems/reverse-nodes-in-k-group/
    if (!head || list_is_singular(head))
        return;
    struct list_head tmp_head;
    INIT_LIST_HEAD(&tmp_head);
    int ct = 0;
    int size = q_size(head);
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        ct += 1;
        if (ct % k == 0 || ct == size) {
            list_cut_position(&tmp_head, head, node);
            q_reverse(&tmp_head);
            list_splice_tail(&tmp_head, head);
        }
        if (ct == size)
            break;
    }
}

參考 ShchangAnderson 的作法，走訪每個節點，每 k 個節點作一次 q_reverse，並用 list_splice_tail 從尾端存進一個新的串列。考慮到串列長度可能不整除 k，所以在判第 13 行加入 ct == size，保證剩餘的節點也能被處理到。

`q_sort`

參考 WangHanChi 的程式碼，採用 MergeSort 實作排序。

`merge_two_nodes`

struct list_head *merge_two_nodes(struct list_head *left,
                                  struct list_head *right)
{
    struct list_head *new_head = NULL, **indirect = &new_head, **iter = NULL;
    for (; left && right; *iter = (*iter)->next) {
        iter = strcmp(list_entry(left, element_t, list)->value,
                      list_entry(right, element_t, list)->value) >= 0
                   ? &right
                   : &left;
        *indirect = *iter;
        indirect = &(*indirect)->next;
    }
    *indirect = (struct list_head *) ((uint64_t) left | (uint64_t) right);
    return new_head;
}

使用間接指標，iter 負責找出目前擁有最小字串的節點是屬於哪個串列 (left or right)，indirect 負責將 iter 指的節點存進 new_head。

`merge_divide`

struct list_head *merge_divide(struct list_head *head)
{
    if (!head || !head->next)
        return head;
    struct list_head *rabbit = head, *turtle = head, *middle;

    for (; rabbit && rabbit->next;
         rabbit = rabbit->next->next, turtle = turtle->next)
        ;
    middle = turtle;
    // cut off the link
    turtle->prev->next = NULL;
    struct list_head *left = merge_divide(head);
    struct list_head *right = merge_divide(middle);

    return merge_two_nodes(left, right);
}

利用快慢指標找出鍊結串列中點，找到後從中點將串列切開，變成 head 和 middle 兩條串列，再遞迴將這兩條串列從中點切開，直到每條串列只剩一個節點。

`q_sort`
















void q_sort(struct list_head *head, bool descend) 
{
    if (!head || list_empty(head))
        return;
    // cut off the link
    head->prev->next = NULL;
    head->next = merge_divide(head->next);

    struct list_head *before = head, *after = head->next;
    for (; after != NULL; after = after->next) {
        after->prev = before;
        before = after;
    }
    before->next = head;
    head->prev = before;
}

第 6、7 行將 head 與原本為排序的串列斷開，並使用 merge_divide 得到排序好的串列。但因為 merge_divide 回傳的串列為單向鏈結串列，所以必須走訪每個節點，建構其 *prev。

`q_ascend`、`q_descend`

int q_ascend(struct list_head *head)
{
    // https://leetcode.com/problems/remove-nodes-from-linked-list/
    if (!head || list_empty(head))
        return 0;

    element_t *right = list_entry(head->prev, element_t, list);
    element_t *left = list_entry(head->prev->prev, element_t, list);
    while (&left->list != head) {
        if (strcmp(right->value, left->value) > 0) {
            left = list_entry(left->list.prev, element_t, list);
            right = list_entry(right->list.prev, element_t, list);
        } else {
            list_del(&left->list);
            free(left->value);
            free(left);
            left = list_entry(right->list.prev, element_t, list);
        }
    }
    return q_size(head);
}

該函式目的為刪除節點使該串列成為嚴格遞增/遞減串列。

這裡提到的數值遞增遞減，是指字串中逐字元的 ASCII 值，使用 strcmp 可以很好得到兩字串間字元的大小關係。

用兩個指標由後往前尋訪每個節點，當 strcmp(right->value, left->value) > 0 發生時，代表後節點的字串大於前節點的字串，兩節點為遞增關係。反之，當 strcmp(right->value, left->value) < 0 發生，代表前節點的字串大於後節點的字串，兩節點為遞減關係。

`q_merge`

int q_merge(struct list_head *head, bool descend)
{
    if (!head || list_empty(head)) {
        return 0;
    }
    if (list_is_singular(head)) {
        return list_entry(head->next, queue_contex_t, chain)->size;
    }
    queue_contex_t *merged_list = list_entry(head->next, queue_contex_t, chain);
    for (struct list_head *p = head->next->next; p != head; p = p->next) {
        queue_contex_t *node = list_entry(p, queue_contex_t, chain);
        list_splice_init(node->q, merged_list->q);
    }
    q_sort(merged_list->q, descend);

    return q_size(merged_list->q);
}

參考 Kuanch 以及 WangHanChi 的說明。

根據要求，傳入的 head 為 queue_contex_t 的 head ，因此也會需要將節點往 next 移動一格才開始存取每個 queue 的 head。

首先來看 queue_contex_t 是什麼東西

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

q 用來指向佇列的 head
chain 用來串連多個佇列的 head
id、size 紀錄該佇列的資訊

TODO: 增加 *q 指向雙向鏈結串列

用 p 走訪這個 chain 的每個節點，合併每個節點指向的雙向鏈結串列至首個節點，最後再用 q_sort 將首個節點排序，實現合併並且排序的效果。

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」。
不要說「寫得很醜」這樣不明確的話語，你乾脆說「因為我的母語不是英語，所以我不適合寫程式」？我們在工程領域要知道哪裡做不好，才可改進，列出明確的改進事項。
不要說「優化一下」，工程追求持續的演化和改進。

知道了!

使用 valgrind 排除 qtest 記憶體問題

在終端機執行

make valgrind

trace-17 跑了很久，執行結果尚無找到記憶體問題。

TOTAL           100/100

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

論文介紹

這篇論文提出時序洩漏檢測 (timing leakage detection) 工具 dudect，用以評估程式碼在特定平台上是否能在常數時間內運行完畢。

現有的方法大多需要模擬硬體行為，而硬體製造商釋出的硬體資訊卻少之又少，十分不利於檢測工具的開發。這篇論文基於以上問題提出改善方案，提出的 dudect 檢測工具不使用靜態程式分析 (static analysis)，而是使用對於時間的統計分析 (statistical analysis)，藉此避免測量時間的方法對於硬體產生依賴性。

時序攻擊

時序攻擊 (timing attack) 是旁路攻擊的一種，攻擊者透過加密算法所需的執行時間推斷敏感訊息，導致安全漏洞。舉例來說，若加密算法在判斷密碼是否正確時，是使用逐字元的判斷並在偵測字元不匹配時回傳，攻擊者在多次嘗試並觀察演算法的執行時間，判斷輸入字元是否匹配成功，進而推得出密碼。

為了避免時序攻擊，可以使用時序洩漏偵測工具，或是使用常數時間演算法來處理敏感資訊，將時間差異最小化，甚至可以引入隨機元素，使攻擊者難以通過觀察時間模式來推斷信息。

時序洩漏偵測

時序洩漏偵測 (Timing leakage detection) 用於檢測演算法是否存在時序洩漏的風險，以此防止時序攻擊。通常會分析程式的執行模式，包括時間消耗、記憶體存取模式、CPU使用率等。透過觀察這些模式的變化，以發現可能存在的時序泄漏漏洞。

論文方法步驟介紹

Measure execution time

測量兩個不同類別的輸入資料在加密函式上的執行時間，並得到兩個數據分布。
- a) Classes definition
  使用兩種不同類別的輸入資料，反覆進行測驗，這篇論文採用 fix-vs-random 測驗方式，第一組輸入資料使用特定常數 (通常第一類會觸發 corner-case)，第二類則隨機產生。
- b) Cycle counters
  使用 CPU 提供的 cycle counter，以獲得更精準的執行時間。
- c) Environmental conditions:
  原文提到，為了最小化環境的差異，每次測量都對應到一個隨機的類別。

疑問：不清楚 c) 的每個測量都對應一個隨機的類別是什麼意思，目前想法是每次測量都使用隨機的輸入資料類別，但這又和減少環境差異有什麼關係呢？

Apply post-processing

得到數據分布後，可以對其進行資料後處理。
- a) Cropping
  對於較長的執行時間，大部分的時間分佈都是呈 positively skewed distribution，可能是因為測量誤差 (measurement artifacts)，測量函式會受到 OS 或者外部程式影響。這種情況下，可以裁剪特定測量值以便後續檢定。
- b) Higher-order preprocessing
  依照不同的假說檢定應用，使用更高階的資料預處理。
Apply statistical test

使用假說檢定試圖推翻虛無假說：「兩個數據分布是相同的」，驗證對立假說：「兩個數據分布不是相同的」，藉此判斷該加密函式是否存在時序洩漏問題。
- a) t-test
  採用的假說檢定方法是 Welch-test。

Student's t-distribution

介紹

Student's t-distribution，簡稱 t 分布，t 分布為一連續對稱分布，t 分布與期望值為0變異數為1常態分布特徵相似(鐘形、對稱於平均數 0、數值向兩側延伸)。在樣本數小或母體標準差未知的情況下，使用樣本標準差取代母體標準差，並使用 t 分布進行推論。

t 分布定義了一個參數：自由度(degrees of freedom)，隨著自由度越大，t 分布的分布狀況越接近常態分布，當自由度逼近無限時，t 分布就會退化成常態分布。

用途

Student's t-distribution 可以用於假設檢定上，在樣本數過小或母體標準差未知的情況下，通常會比常態分布更適合用於假設檢定。

沒做到的事，不用裝忙。

simulation 運作

參考 jimmylu890303 的作法，在 trace-17 中，會檢查 q_insert_head、q_insert_tail、q_remove_head、q_remove_tail 是否能在常數時間內完成。

首先，在 fixture.h ，可以看到 is_##x##_const() 的宣告：

/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _

查閱 C 語言規格書，針對 Concatenation 進行解說，使用規格書裡頭的術語。

TODO：C99 6.10.3.3 The ## operator

在 ~~#define 中~~ ，"##" 表示的是連接運算子。以下為例子：

#define Conn(x, y) x##y

int num = Conn(123, 456);
    // num = 123456

char *str = Conn("abc","def");
    // str = "abcdef"

其中的 DUT_FUNCS 又可以在 constant.h 裡看到：

#define DUT_FUNCS  \
    _(insert_head) \
    _(insert_tail) \
    _(remove_head) \
    _(remove_tail)

在 qtest.c 中，當 simulation == 1 時會呼叫 is_##x##_const。

static bool queue_insert(position_t pos, int argc, char *argv[])
{
    if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok =
            pos == POS_TAIL ? is_insert_tail_const() : is_insert_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
    }
    ...
}

static bool queue_remove(position_t pos, int argc, char *argv[])
{
    if (simulation) {
        if (argc != 1) {
            report(1, "%s does not need arguments in simulation mode", argv[0]);
            return false;
        }
        bool ok =
            pos == POS_TAIL ? is_remove_tail_const() : is_remove_head_const();
        if (!ok) {
            report(1,
                   "ERROR: Probably not constant time or wrong implementation");
            return false;
        }
        report(1, "Probably constant time");
        return ok;
    }
    ...
}

又可以在 fixture.c 看 is_##x##_const() 的實作，發現最後會呼叫 test_const(#op, DUT(op))

#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 _

使用 test_const(#op, DUT(op)); 進行測試。

static bool test_const(char *text, int mode)
{
    bool result = false;
    t = malloc(sizeof(t_context_t));

    for (int cnt = 0; cnt < TEST_TRIES; ++cnt) {
        printf("Testing %s...(%d/%d)\n\n", text, cnt, TEST_TRIES);
        init_once();
        for (int i = 0; i < ENOUGH_MEASURE / (N_MEASURES - DROP_SIZE * 2) + 1;
             ++i)
            result = doit(mode);
        printf("\033[A\033[2K\033[A\033[2K");
        if (result)
            break;
    }
    free(t);
    return result;
}

更改 deduct

在 oreparaz/dudect 的程式碼具備 percentile 的處理，但在 lab0-c 則無。

TODO：參考 willwillhi、Wufangni

Fisher-Yates Shuffle 實作

Fisher-Yates Shuffle 是由 Fisher 和 Yates 提出的亂序演算法，該演算法的實作概念：從最後一個元素開始，將每個元素與其前面隨機一個元素交換。

要在 lab0-c 裡實作 Fisher-Yates Shuffle，首先我們需要做出 swap function，這裡的 swap function 跟佇列操作裡的 q_swap 不同，q_swap 做的是前後兩個元素的交換，swap function 要做的是任意兩個節點的交換。

2024q1 Homework1 (lab0)

Reviewed by ssheep773

Reviewed by SimonLee0316

Reviewed by stevendd543

開發環境

指定的佇列操作

先備知識

element_t

list_head

q_new

RETURN VALUE

q_free

q_insert_head

char *strcpy(char *dest, const char *src);

DESCRIPTION

BUGS

q_insert_tail

q_remove_head

q_remove_head、q_remove_tail

q_size

q_delete_mid

q_swap

q_reverse

q_reverseK

q_sort

merge_two_nodes

merge_divide

q_sort

q_ascend、q_descend

q_merge

使用 valgrind 排除 qtest 記憶體問題

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

論文介紹

時序攻擊

時序洩漏偵測

論文方法步驟介紹

Student's t-distribution

介紹

用途

simulation 運作

更改 deduct

Fisher-Yates Shuffle 實作

Read more

資訊科技產業專案設計課程作業 4

Linux 期末專題

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz3+4)

Reviewed by `ssheep773`

Reviewed by `SimonLee0316`

Reviewed by `stevendd543`

`element_t`

`list_head`

`q_new`

`q_free`

`q_insert_head`

char strcpy(char dest, const char *src);

`q_insert_tail`

`q_remove_head`

`q_remove_head`、`q_remove_tail`

`q_size`

`q_delete_mid`

`q_swap`

`q_reverse`

`q_reverseK`

`q_sort`

`merge_two_nodes`

`merge_divide`

`q_sort`

`q_ascend`、`q_descend`

`q_merge`