# 2024q1 Homework1 (lab0)
contributed by < `Wufangni` >
## 開發環境
``` 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): 16
On-line CPU(s) list: 0-15
Vendor ID: GenuineIntel
Model name: 12th Gen Intel(R) Core(TM) i5-12500H
CPU family: 6
Model: 154
Thread(s) per core: 2
Core(s) per socket: 12
Socket(s): 1
Stepping: 3
CPU max MHz: 4500.0000
CPU min MHz: 400.0000
BogoMIPS: 6220.80
```
## 針對佇列操作的程式碼實作
### `q_new`
> [commit_0f1697a](<https://github.com/Wufangni/lab0-c/commit/0f1697a110a38c743e86abb1112b0807c2cb8880>)
:::danger
allocate 的翻譯是「配置」，以區格 dispatch (分發/分配)
> 已更改
:::
先建立指向 `list_head` 結構的 head 指標，並使用 `malloc` 配置一個記憶體空間，最後回傳經由 `INIT_LIST_HEAD` 初始化後的 head 指標。
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
:::danger
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
:::
### `q_free`
> [commit_e34d5f1](<https://github.com/Wufangni/lab0-c/commit/e34d5f1ef1fb3fc3c23b87206753375cb9d0068f>)
利用 `list_for_each_entry_safe` 逐一走訪每個節點，並利用 `q_release_element` 釋放該節點的記憶體空間，最後釋放指向佇列第一個元素的 head 指標。
:::danger
無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
> 已更改
:::
### `q_insert_head`
> [commit_289d41c](<https://github.com/Wufangni/lab0-c/commit/289d41c5f2fc78f671774a4c35460a12a4d15b85>)
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
利用 `malloc` 配置記憶體空間給新增節點使用，並將欲新增的字元參數指定給新增節點的 value ,再使用 `list_add` 新增節點到 list 的前端。
### `q_insert_tail`
> [commit_9f62397](<https://github.com/Wufangni/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>)
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
與 `q_insert_head` 大致相同，差別在於 `list_add` 部份改為使用`list_add_tail`。
### `q_remove_head`
> [commit_ad185d6](<https://github.com/Wufangni/lab0-c/commit/ad185d6ed4d9e4c9191b9ab6387b96cea929b0fb>)
利用 `head->next` 建立欲刪除的 `remove_h_list`，先儲存 `remove_h_list` 的值到 `sp` 字元中，再對 `head->next` 所指節點做 `list_del`。
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
### `q_remove_tail`
與 `q_remove_head` 大致相同，差別在於 `head->next` 部份改為 `head->prev`。
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
實作程式碼在 [commit_ad185d6](<https://github.com/Wufangni/lab0-c/commit/d19396fc2ca837c6c02c1384ec371918b58cfbb0>)。
### `q_size`
新增 `node_count` 變數計數每個節點數量再做回傳。
實作程式碼在 [commit_ad4ada0](<https://github.com/Wufangni/lab0-c/commit/ad4ada0e1d27309c3716d556d04b5e97318fab18>)。
### `q_delete_mid`
使用 `q_size` 抓取 list 總節點數，新增 `*cur` 指標，並用 for 迴圈到總節點數的一半逐一往下跳到中間節點。
利用 `*cur` 建立`removed_element` ，使用 `list_del` 斷開 `*cur` 在 list 中的連結，最後用 `free` 釋放 `removed_element`。
實作程式碼在 [commit_3bb6704](<https://github.com/Wufangni/lab0-c/commit/3bb67042fe2ea86cdd983b179877dca63f048da1>)。
### `q_delete_dup`
新增 `*ori` 和 `*cur` 兩個指標，`*ori` 從第一個節點開始，`*cur` 指向 `*ori` 的下一個節點持續往下跑，直到 `*cur` 指到 head 才結束迴圈。
設置布林值 flag 判斷是否 `*ori` 的 value 為重複值（初始值為 false ），若 `*ori` 和 `*cur` 節點的 value 不相同，且 flag 判斷先前沒有與 `*ori` 重複的值被刪除，則 `*ori` 與 `*cur` 皆往下一跳節點。
``` c
if (strcmp(cur_element->value, ori_element->value) != 0 &&
flag == false) {
ori = cur;
cur = cur->next;
}
```
`*ori` 和 `*cur` 節點的 value 若相同，則刪除 `*cur` 所指節點，且 `*cur` 往下一跳節點，flag 設為 true 表示目前 `*ori` 所指節點的值有重複。
``` c
} else {
flag = true;
cur = cur->next;
element_t *tmp_element = list_entry(cur->prev, element_t, list);
list_del(&tmp_element->list);
free(tmp_element->value);
free(tmp_element);
if (cur == head) {
element_t *tmp2_element = list_entry(ori, element_t, list);
list_del(&tmp2_element->list);
free(tmp2_element->value);
free(tmp2_element);
break;
}
```
`*ori` 和 `*cur` 節點的 value 不相同且 flag 為 true，刪除 `*ori` 所指節點，將 `*ori` 指到與 `*cur` 相同節點，`*cur` 往下一節點繼續執行。
``` c
} else if (strcmp(cur_element->value, ori_element->value) != 0 &&
flag == true) {
element_t *tmp_element = list_entry(ori, element_t, list);
list_del(&tmp_element->list);
ori = cur;
free(tmp_element->value);
free(tmp_element);
cur = cur->next;
flag = false;
}
```
實作程式碼在 [commit_bcbeaf7](<https://github.com/Wufangni/lab0-c/commit/bcbeaf7b677f45a7b756db8f4b29b75dfc4142fa>)。
### `q_swap`
新增 `*front` 和 `*behind` 兩指標對兩兩節點做互換。
``` c
while (true) {
if (front == head || behind == head)
break;
(front->prev)->next = behind;
behind->prev = front->prev;
(behind->next)->prev = front;
front->next = behind->next;
front->prev = behind;
behind->next = front;
front = front->next;
behind = front->next;
}
```
實作程式碼在 [commit_f6ddd47](<https://github.com/Wufangni/lab0-c/commit/f6ddd47f27dd0818c3b6d0549c494f838235f613>)。
### `q_reverse`
使用 `list_for_each_safe` 對每個節點互換 `*prev` 和 `*next` 指標。
``` c
struct list_head *nex, *s;
list_for_each_safe (nex, s, head) {
element_t *tmp_element = list_entry(nex->next, element_t, list);
nex->next = nex->prev;
nex->prev = &tmp_element->list;
}
struct list_head *tmp_head_next = head->next;
head->next = head->prev;
head->prev = tmp_head_next;
```
實作程式碼在 [commit_f6ddd47](<https://github.com/Wufangni/lab0-c/commit/b92088728cb41a80fdb31cd1bf64f5b59dc5baf8>)。
### `q_reverseK`
新增 `*h` 及 `*t` 兩指標分別指向每組要替換的頭跟尾節點，將此組的頭與尾節點與原先 list 斷開並使用 `q_reverse` 做反轉，連回原本的list後將 `*cur` 指向反傳後在此組節點中最尾端的 `*h`，跑 k 次迴圈後停止。
``` c
struct list_head *h, *t, *cur = head;
for (int i = 0; i < (q_size(head) / k); i++) {
h = cur->next;
t = h;
for (int j = 1; j < k; j++)
t = t->next;
cur->next = t->next;
(t->next)->prev = cur;
t->next = h;
h->prev = t;
q_reverse(h);
h->next = cur->next;
(h->next)->prev = h;
t->prev = cur;
cur->next = t;
cur = h;
}
```
實作程式碼在 [commit_ceb5070](<https://github.com/Wufangni/lab0-c/commit/ceb5070f50e8edf908e5ea17f7cf473e667b948a>)。
### `q_sort`
先建立一個可回傳 `list_head` 的 function `merge`，用 `*pos1` 及 `*pos2` 分別指向兩個 list 的第一個節點，若 `*pos1` 所指節點值比較小則往下跳一節點再做比較，比較大則刪除 `*pos2` 所指節點並將 `*pos2` 往下一節點移動，直到 `*pos1` 或 `*pos2` 跳至 head 。若此時 `*pos2` 指向的list中尚有節點則從第一個節點逐一加到 `*pos1` 所在 list 最後端。
``` c
struct list_head *merge(struct list_head *head1, struct list_head *head2)
{
struct list_head *pos1 = head1->next, *pos2 = head2->next, *insert;
while (pos1 != head1 && pos2 != head2) {
element_t *ele1 = list_entry(pos1, element_t, list);
element_t *ele2 = list_entry(pos2, element_t, list);
if (strcmp(ele1->value, ele2->value) > 0) {
insert = pos2;
pos2 = pos2->next;
list_del(&ele2->list);
(pos1->prev)->next = insert;
insert->next = pos1;
insert->prev = pos1->prev;
pos1->prev = insert;
} else {
pos1 = pos1->next;
}
}
while (pos2 != head2) {
insert = pos2;
pos2 = pos2->next;
list_del(&list_entry(insert, element_t, list)->list);
list_add_tail(&list_entry(insert, element_t, list)->list, head1);
}
return head1;
}
```
實作出 merge sort 的遞迴 function `merge_divide`，再利用剛創好的 `merge` 合併兩 list 。
``` c
struct list_head *merge_divide(struct list_head *head)
{
struct list_head *mid = head->next, *mid_prev, new_head;
if (q_size(head) <= 1)
return head;
for (int i = 0; i < q_size(head) / 2; i++)
mid = mid->next;
struct list_head *new_pos = &new_head;
new_pos->next = mid;
new_pos->prev = head->prev;
(head->prev)->next = new_pos;
mid_prev = mid->prev;
mid->prev = new_pos;
head->prev = mid_prev;
mid_prev->next = head;
return merge(merge_divide(head), merge_divide(new_pos));
}
```
實作程式碼在 [commit_aed93df](<https://github.com/Wufangni/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>)。
### `q_ascend` / `q_descend`
`q_ascend` 對每個節點皆往下逐一檢查，若此節點往下有比它的值還小的節點存在則刪除此節點，且換下一節點檢查。
`q_dscend` 與 `q_ascend` 大致一樣，唯一差別在於 `q_dscend` 尋找比它大的節點，找到才做刪除。
``` c
for (int i = 0; i < len; i++) {
bool delete = false;
if (cur->next == head)
break;
struct list_head *node_ = cur->next;
element_t *cur_element = list_entry(cur, element_t, list);
for (int j = i + 1; j < len; j++) {
element_t *nod_element = list_entry(node_, element_t, list);
if (strcmp(cur_element->value, nod_element->value) < 0) {
cur = cur->next;
list_del(&cur_element->list);
free(cur_element->value);
free(cur_element);
delete = true;
break;
}
node_ = node_->next;
}
if (delete == false)
cur = cur->next;
}
```
`q_ascend` 實作程式碼在 [commit_5008760](<https://github.com/Wufangni/lab0-c/commit/50087600b8952fd86a62a440ff0f4eb52a3d7cbb>)。
`q_dscend` 實作程式碼在 [commit_8e8a14a](<https://github.com/Wufangni/lab0-c/commit/8e8a14a91c317b9eacb58b9e7a19a2b3066d1a10>)。
### `q_merge`
> [commit_aed93df](<https://github.com/sysprog21/lab0-c/commit/aed93dfb1ad8df5bb85d20f23cacbd69a61de1e8>)
:::danger
對照 Dictionary.com 對 [implement](https://www.dictionary.com/browse/implement) 一詞的解釋:
* to fulfill; perform; carry out:
* to put into effect according to or by means of a definite plan or procedure.
* Computers. to realize or instantiate (an element in a program), often under certain conditions as specified by the software involved.
* to fill out or supplement
「實作」會是符合上述 "implement" 語意的譯詞，取「起」以「創作」的意思，而「製造」本質上是固定輸入並通常產生固定輸出的行為。
$\to$ [資訊科技詞彙翻譯](https://hackmd.io/@sysprog/it-vocabulary)
:::
實做 ```merge_two_list``` ，作法與上述提到的 ```merge``` 相似，差別在於沒有回傳值。
利用 ```head``` 指向每個 ```queue_contex_t``` 位置串列，將第一個 ```queue_contex_t``` 包含的 ```q``` 分別與每個 ```queue_contex_t->q``` 做 merge。
``` c
int q_merge(struct list_head *head, bool descend)
{
if (!head || list_empty(head))
return 0;
struct list_head *first_q = head->next, *next_q = first_q->next;
queue_contex_t *first_queue = list_entry(first_q, queue_contex_t, chain);
if (descend == true)
q_reverse(first_queue->q);
while (next_q != head) {
queue_contex_t *next_queue = list_entry(next_q, queue_contex_t, chain);
if (descend == true)
q_reverse(next_queue->q);
merge_two_list(first_queue->q, next_queue->q);
next_q = next_q->next;
}
return q_size(first_queue->q);
}
```
:::danger
你如何確認目前的測試程式已涵蓋排序演算法的最差狀況？
:::
---
## 研讀並引入 `lib/list_sort.c`
:::danger
command 的翻譯是「命令」，而非「指令」(instruction)，這裡其實不是「命令」，而是編譯器提供的選項 (option)，查閱 GCC 手冊。
> 好的，謝謝老師 。
:::
`__attribute__` 屬於 GCC 的一種編譯器命令，可用來指示編譯器進行一些高階處理和檢查工作，查閱 GCC 手冊得知 `nonnull(2,3,4)` 指示第 2 、 3 、 4 不能為空值。
``` c
__attribute__((nonnull(2,3,4)))
```
`*priv` 用來記錄傳入的 cmp function回傳的值，若 `cmp(priv, a, b) <= 0` 則表示 a < b ，將 a 加入尾端並把 `*a` 往後移一節，若 `*a` 為空串列則回 `*b` 做排序。
:::danger
段落中的程式碼標注，使用 1 個 [backtick](https://en.wikipedia.org/wiki/Backtick)，而非 3 個。
> 已更改
:::
``` c
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b)
{
struct list_head *head, **tail = &head;
for (;;) {
/* if equal, take 'a' -- important for sort stability */
if (cmp(priv, a, b) <= 0) {
*tail = a;
tail = &a->next;
a = a->next;
if (!a) {
*tail = b;
break;
}
} else {
*tail = b;
tail = &b->next;
b = b->next;
if (!b) {
*tail = a;
break;
}
}
}
return head;
}
```
先排除 list 為空值或只有一個節點的情況，再利用 `head->prev->next` 將 list 轉為單向鏈結串列。
``` c
struct list_head *list = head->next, *pending = NULL;
size_t count = 0; /* Count of pending */
if (list == head->prev) /* Zero or one elements */
return;
/* Convert to a null-terminated singly-linked list. */
head->prev->next = NULL;
```
將 list_sort.c 及 list_sort.h 引入 lab0-c ，在 qutest.c 中用 `extern` 外部宣告 `list_sort` 函式。
```diff=
+typedef int
+ __attribute__((nonnull(2, 3))) (*list_cmp_func_t)(void *,
+ const struct list_head *,
+ const struct list_head *);
+extern void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
```
定義 `cmp` 函式減少後續重複程式碼使用。
```diff=
+int cmp(void *priv, const struct list_head *a, const struct list_head *b)
+{
+ return strcmp(list_entry(a, element_t, list)->value,
+ list_entry(b, element_t, list)->value);
+}
```
新增 listsort 命令。
```diff=
ADD_COMMAND(reverse, "Reverse queue", "");
ADD_COMMAND(sort, "Sort queue in ascending/descening order", "");
+ ADD_COMMAND(listsort, "Sort queue in ascending/descening order", "");
ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]");
ADD_COMMAND(show, "Show queue contents", "");
ADD_COMMAND(dm, "Delete middle node in queue", "");
```
修改 Makefile。
```diff=
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
- linenoise.o web.o
+ linenoise.o web.o list_sort.o
deps := $(OBJS:%.o=.%.o.d)
```
詳細程式碼在 [commit_b8e0681](<https://github.com/Wufangni/lab0-c/commit/b8e0681edeac9fb56a32106fe5d7f0bfcc215a0f>)。
## 提供新的命令 `shuffle`
參考 [Fisher–Yates shuffle](<https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm>) 實做洗牌演算法，新增 `q_shuffle` 函式根據下面步驟進行：
1. 確認鏈節串列不為空值。
2. 使用 `q_size` 計算鍊結串列長度，並用 for 迴圈從最尾端依序向前做交換。
3. 從目前要交換的節點之前找出隨機節點，使用 `srand(time(NULL))` 更改 `seed` 避免每次找隨機值結果不變。
4. 利用 `swap` 交換兩節點，直到 `*last` 指向第二節點時停止迴圈。
``` c
void q_shuffle(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *last = head->prev;
for (int len = q_size(head); len > 1; len--) {
srand(time(NULL));
int random_idx = rand() % len;
struct list_head *random_node = head->next;
while (random_idx--)
random_node = random_node->next;
swap(last, random_node);
last = last->prev;
}
}
```
使用 `ADD_COMMAND` 新增 `shuffle` 命令。
```diff=
ADD_COMMAND(reverse, "Reverse queue", "");
ADD_COMMAND(sort, "Sort queue in ascending/descening order", "");
ADD_COMMAND(listsort, "Sort queue in ascending/descening order", "");
+ ADD_COMMAND(shuffle, "Shuffle the queue using Fisher-Yates Shuffle", "");
ADD_COMMAND(size, "Compute queue size n times (default: n == 1)", "[n]");
ADD_COMMAND(show, "Show queue contents", "");
ADD_COMMAND(dm, "Delete middle node in queue", "");
```
修改 Makefile。
```diff=
OBJS := qtest.o report.o console.o harness.o queue.o \
random.o dudect/constant.o dudect/fixture.o dudect/ttest.o \
shannon_entropy.o \
- linenoise.o web.o list_sort.o
+ linenoise.o web.o list_sort.o shuffle.o \
deps := $(OBJS:%.o=.%.o.d)
```
詳細程式碼在[commit_adfc198](<https://github.com/Wufangni/lab0-c/commit/adfc19869c4d31a0446df73415a9f7dbf0906b38>)。
## 研讀論文〈Dude, is my code constant time?〉
`Timing attacks` 是一種廣泛的 `side-channel attacks` ，不同於直接使用密碼學演算上的攻擊手段，他是利用系統執行時間的特性進行破解。舉例來說，在判斷一段密碼是否與原密碼相符時，若是從第一個字母逐一比對遇到不符合再回傳錯誤警告，就可利用回傳時間來判斷前面正確的字符有幾個，進而產生資安疑慮。
有多數研究和偵測執行可變時間的方法被開發出來，例如 `ctgrind` 、`Flow-tracker` 或 `ctverif` ，大多需要對硬體進行建模，但困難點在於較難取得 CPU 細節資訊，此論文提出 `dudect` 方法可利用統計分析的程式判定是否達成 constant-time ，不用依靠靜態分析可避免硬體上的限制。
### Step 1: Measure execution time
- 針對不同輸入資料重複對執行時間進行觀察，第一種資料通常為固定的值，第二種為隨機產生。
- 現在 CPU 提供週期計數器（Cycle counters）可準確獲取執行時間。
- 最小化環境差異造成的影響，每次測量都會對應隨機產生的輸入分類。
### Step 2: Apply post-processing
在進入統計分析之前會先對每個單獨的測量值進行一些後處理：
- Cropping:可能會因為 OS 或一些外部因素導致時間分佈呈現 positive skew ，這時候可透過裁減 (crop) 掉一些超過 threshold 的測量結果。
- Higher-order preprocessing:使用高階的預處理方式有益於測量，例如`scentered product` 、`mimicking higher-order DPA attack` 。
### Step 3: Apply statistical test
透過統計檢定來反駁兩執行時間相等的假設，有幾種檢測方式如 `t-test` 及 `Non-parametric tests` 等。
## `dudect`
從每個 trace 中追蹤第17筆測資會無法通過，觀察內部指令為進入 `simulation` 判斷時造成的問題，回到 `qtest.c` 中觀察程式做 constant time 判斷使用到的兩函式分別為 `is_insert_tail_const()` 及 `is_insert_head_const()`
``` c
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;
}
```
兩函式存放位置在 `fixture.h` 檔案中，裡面定義了 `DUT_FUNCS` 用來測試是否達到 constant time 。
``` c
#ifndef DUDECT_FIXTURE_H
#define DUDECT_FIXTURE_H
#include <stdbool.h>
#include "constant.h"
/* Interface to test if function is constant */
#define _(x) bool is_##x##_const(void);
DUT_FUNCS
#undef _
#endif
```
到 `fixture.c` 中找到關於 constant time 的實作程式，與 [dudect](<https://github.com/oreparaz/dudect/blob/master/src/dudect.h>) 原始程式碼做比對發現缺漏了部份內容。
``` c
static void prepare_percentiles(dudect_ctx_t *ctx) {
qsort(ctx->exec_times, ctx->config->number_measurements, sizeof(int64_t), (int (*)(const void *, const void *))cmp);
for (size_t i = 0; i < DUDECT_NUMBER_PERCENTILES; i++) {
ctx->percentiles[i] = percentile(
ctx->exec_times, 1 - (pow(0.5, 10 * (double)(i + 1) / DUDECT_NUMBER_PERCENTILES)),
ctx->config->number_measurements);
}
}
```
在 `fixture.c` 補上 `prepare_percentiles` 函式，且因 `prepare_percentiles` 使用了 `DUDECT_NUMBER_PERCENTILES` 定義及其餘函式所以需要一併補齊。
``` c
static int cmp(const int64_t *a, const int64_t *b) {
if (*a == *b)
return 0;
return (*a > *b) ? 1 : -1;
}
static int64_t percentile(int64_t *a_sorted, double which, size_t size) {
size_t array_position = (size_t)((double)size * (double)which);
assert(array_position < size);
return a_sorted[array_position];
}
```
在 `doit` 函式中新增剛補上的 `prepare_percentiles` ，且修改有使用到 `DUDECT_NUMBER_PERCENTILES` 定義的 `update_statistics` 參數。
``` diff=
@@ -123,6 +161,7 @@ static bool doit(int mode)
int64_t *exec_times = calloc(N_MEASURES, sizeof(int64_t));
uint8_t *classes = calloc(N_MEASURES, sizeof(uint8_t));
uint8_t *input_data = calloc(N_MEASURES * CHUNK_SIZE, sizeof(uint8_t));
+ int64_t *percentiles = calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
@@ -133,7 +172,8 @@ static bool doit(int mode)
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
- update_statistics(exec_times, classes);
+ prepare_percentiles(percentiles, exec_times);
+ update_statistics(exec_times, classes, percentiles);
ret &= report();
```
再使用 `make test` 測試所有 trace ，可發現所有測試項目都可通過。
```
fangni@fangni-G5-KF:~/linux2024/lab0-c$ make test
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
--- trace-02-ops 6/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
--- trace-03-ops 6/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
--- trace-04-ops 6/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
--- trace-05-ops 6/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
--- trace-06-ops 6/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
--- trace-07-string 6/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
--- trace-08-robust 6/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
--- trace-09-robust 6/6
+++ TESTING trace trace-10-robust:
# Test operations on NULL queue
--- trace-10-robust 6/6
+++ TESTING trace trace-11-malloc:
# Test of malloc failure on insert_head
--- trace-11-malloc 6/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
--- trace-12-malloc 6/6
+++ TESTING trace trace-13-malloc:
# Test of malloc failure on new
--- trace-13-malloc 6/6
+++ TESTING trace trace-14-perf:
# Test performance of insert_tail, reverse, and sort
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
```
詳細程式碼在 [commit_50da0ff](<https://github.com/Wufangni/lab0-c/commit/50da0ff96351d714fc74f095861b27ceba3c3340>)。
Sign in with Wallet
Connect another wallet