# 2025q1 Homework1 (lab0)
contributed by <`allen741`>
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
#### Reviewed by `kk908676`
部份 commit message 可以描述的更加詳細
#### Reviewed by `MikazukiHikari`
對於 queue.[ch] 實作的部分，若能在共筆中補充你實作的核心邏輯程式碼，將有助於他人更快理解你的思路。
## 開發環境
```shell
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
$ lscpu
Architecture: x86_64
CPU Operating Modes: 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz
CPU Family: 6
Model: 140
Threads per core: 2
Cores per socket: 4
Socket(s): 1
Process: 1
CPU(s) scaling MHz: 23%
CPU max MHz: 4200.0000
CPU min MHz: 400.0000
BogoMIPS: 4838.40
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 192 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 5 MiB (4 instances)
L3: 8 MiB (1 instance)
NUMA:
NUMA nodes: 1
NUMA node0 CPU(s): 0-7
```
## 實作 queue.c
### `q_new`
```
struct list_head *queue = malloc(sizeof(struct list_head));
if (!queue) {
return NULL;
}
INIT_LIST_HEAD(queue);
```
利用` malloc() `分配記憶體並使用` list.h `中的` INIT_LIST_HEAD() `初始化 head 中的指標 next 和 prev
### `q_free`
> [commit a0f1662](https://github.com/allen741/lab0-c/commit/a0f16620711b913e8732d8130456c8d7eb0f8b43)
>
利用` list.h `的巨集` list_for_each_safe `遍歷雙向鏈結串列並釋放元素，因為 element_t 中的成員 value 為字元指標，所以需要另外釋放它所指向的字元
### `q_insert_head`
```
element_t *new_element = malloc(sizeof(element_t));
if (!new_element) {
return false;
}
new_element->value = strdup(s);
if (!new_element->value) {
free(new_element);
return false;
}
list_add(&(new_element->list), head);
/* cppcheck-suppress memleak */
```
利用` malloc() `分配記憶體後使用 C 語言內建函式` strdup() `將字元複製到所分配的記憶體空間，使用` list.h `的函式` list_add() `加入元素並使用註解` cppcheck-suppress memleak `使程式通過靜態分析
### `q_insert_tail`
```
return q_insert_head(head->prev, s);
```
利用` q_insert_head `實作函式
### `q_remove_head`
>[Commit db4538e](https://github.com/allen741/lab0-c/commit/db4538eac9cdd1699f852783df66c19da85d9c6b)
>
利用` list.h `的函式` list_del() `刪除雙向鏈結串列的第一個元素使其無法透過雙向鏈結串列存取，並使用 C 語言內建函式` strncpy() `複製 bufsize-1 個字元到` sp `並在最後加入空字元`\0`代表字元結尾
### `q_size`
>[Commit 9a4588b](https://github.com/allen741/lab0-c/commit/9a4588b2c95a9b47c2accc866ad7d26139080e1d)
>
利用` list.h `的巨集` list_for_each `計算雙向鏈結串列的元素數量
### `q_delete_mid`
>[Commit 9d86eea
](https://github.com/allen741/lab0-c/commit/9d86eeac01eaa371aa7c7b03a956b80ea9a84ec0)
>
利用快慢指標找到串列的中間元素並釋放其記憶體
### `q_delete_dup`
>[Commit 6c1b975](https://github.com/allen741/lab0-c/commit/6c1b975002a02bc83a49751d3e81a147fb4ec8f3)
>
原先沒有仔細思考函式需要實作的功能，以為是刪除鄰近元素中含有相同字元的元素，經過` make test `測試後才發現問題所在並改成利用兩層迴圈檢查是否有重複的字元，其中使用 C 語言內建函式` strcmp() `比較字元指標所指到的字元是否相同，若相同則會回傳 0。針對回傳 0 的情況將串列中較後面的元素刪除。
之後由於` make test `的第六項測試` trace-06-ops `顯示 ERROR: Duplicate strings are in queue or distinct strings are not in queue，回去重新看[題目](https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/description/)發現有相同字元的元素並非留下一個，而是一個也不留全部刪除因此新增[ commit ](https://github.com/allen741/lab0-c/commit/0d5671032450d67573a8fa37d6a384ebb3bdddfc)刪除第一個重複的元素
### `q_swap`
```
struct list_head *first, *second;
for (first = head->next, second = first->next;
first != head && second != head;
first = first->next, second = first->next) {
list_move(first, second);
}
```
利用兩個指標 first 和 second 指向要交換的元素，並使用` list.h `的函式` list_move() `讓 first 所指向的元素插入到 second 所指向的元素後面達成元素兩兩互相交換，直到 first 或 second 指向 head 才停止繼續交換
### `q_reverse`
>[Commit 0314fac](https://github.com/allen741/lab0-c/commit/0314fac330b60be1ef66e9da1a091d90874c4598)
>
從串列的第二個元素開始將元素利用` list.h `的函式` list_move() `依序插入到 head 的後面完成串列反轉
### `q_reverseK`
```
for (struct list_head *group_first = head;;) {
struct list_head *group_last = group_first;
int check = 0;
for (int i = 0; i < k; i++) {
group_last = group_last->next;
if (group_last == head) {
check = 1;
break;
}
}
if (check == 1) {
break;
}
struct list_head *tmp_next = group_last->next;
struct list_head *tmp_prev = group_first->prev;
group_last->next = group_first;
group_first->prev = group_last;
q_reverse(group_first);
tmp_next->prev = group_first->prev;
group_first->prev->next = tmp_next;
struct list_head *tmp = group_first->prev;
group_first->prev = tmp_prev;
group_first = tmp;
}
```
利用迴圈找到要反轉的串列開頭` group_first `(作為串列開頭因此之後不會被反轉)和結尾` group_last `，透過之前實做的函式` q_reverse `進行反轉，之後將` group_first `更新為反轉串列的最後一個元素用來作為下次反轉的開頭
### `q_sort`
>[Commit f0226e0](https://github.com/allen741/lab0-c/commit/f0226e0f834842028c18182c6b9d8f03e92f29c1)
>
仔細閱讀 linux 中的 [ list_sort.c ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)和[ Linux 核心的鏈結串列排序 ](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-e) 按照 Linus Torvalds 的方法實作雙向鏈結串列排序，將[ list_sort.c ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)的函式` merge() `利用巨集` merge_two_list() `代替，並將[ list_sort.c ](https://github.com/torvalds/linux/blob/master/lib/list_sort.c)的函式` merge_final() `的功能直接寫在` q_sort() `中以減少參數傳遞
### `q_ascend`
>[Commit 12d47ed](https://github.com/allen741/lab0-c/commit/12d47edcb58f22cde11131e05ee0d9eec3c3cfe6)
>
原先以為是將較前面元素小的元素刪除以確保之後的元素所儲存的字元大小會大於或等於前面的元素，但經過` make test `測試無法通過後重新閱讀[Remove Nodes From Linked List](https://leetcode.com/problems/remove-nodes-from-linked-list/description/)才了解是若遇到後面元素小於前面的元素時要刪除前面的元素而非刪除後面的元素，因此我利用兩層迴圈檢查前面的元素所儲存的字元是否皆小於或等於後面的元素所儲存的字元，一旦發現有大於前面元素的元素則刪除前面的元素，並結束第二層迴圈
### `q_merge`
```
struct list_head *first_queue =
list_entry(head->next, queue_contex_t, chain)->q;
struct list_head *queue_ptr = head->next->next;
while (queue_ptr != head) {
struct list_head *queue =
list_entry(queue_ptr, queue_contex_t, chain)->q;
list_splice_init(queue, first_queue);
list_entry(queue_ptr, queue_contex_t, chain)->size = 0;
queue_ptr = queue_ptr->next;
}
q_sort(first_queue, descend);
list_entry(first_queue, queue_contex_t, chain)->size = q_size(first_queue);
return list_entry(first_queue, queue_contex_t, chain)->size;
```
將第一個串列之後的所有串列利用` list.h `的函式` list_splice_init() `依序插入到第一個串列的開頭之後，並將欲插入串列的` size `設為 0，最後利用上述實做的函式` q_sort()`一次排序所有元素
## 閱讀 [Dudect](https://eprint.iacr.org/2016/1123.pdf)
Dudect 的主要目標是檢測函式是否能在常數時間執行完成，分成以下三個步驟檢測
### 1. 測量執行時間
#### a. 定義輸入數據類別
固定輸入: 測試資料設定為常數
隨機輸入: 每次測試時隨機產生測試資料
#### b. 測量執行時間
使用 CPU 週期計數器或外部計時設備
#### c. 減少測試環境影響
減少作業系統干擾
隨機分配測試時的輸入數據類別以減少測試偏差
### 2. 處理測量數據
#### 計算百分位數
針對測試到的執行時間進行排序後，計算百分位數並將執行時間小於百分位數的數據納入統計分析
#### 高階處理
使用 Centered Product 技術來強化統計檢測
### 3. 統計分析
#### Welch’s t-test
測試固定輸入和隨機輸入的執行時間的平均值是否相同，如果差異很大代表函式可能無法在常數時間執行完成
#### Kolmogorov-Smirnov Test
## 實作 Dudect percentile
### 觀察[ Dudect 原始碼](https://github.com/oreparaz/dudect/blob/master/src/dudect.h)
#### 主函式
```
dudect_state_t dudect_main(dudect_ctx_t *ctx) {
prepare_inputs(ctx->config, ctx->input_data, ctx->classes);
measure(ctx);
bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
dudect_state_t ret = DUDECT_NO_LEAKAGE_EVIDENCE_YET;
if (first_time) {
// throw away the first batch of measurements.
// this helps warming things up.
prepare_percentiles(ctx);
} else {
update_statistics(ctx);
ret = report(ctx);
}
return ret;
}
```
對比老師實作的主函式可以發現在測量完執行時間後` Dudect `會透過`prepare_percentiles(ctx) `進行快速排序並計算0~100的百分位數，之後透過` update_statistics(ctx) `針對不同數據結果進行統計分析，但在作業的` fixture.c `測量完執行時間後直接進行統計分析導致執行時間過長的數據大幅地影響結果，因此需實作`prepare_percentiles(ctx) `使執行時間較短的數據能突顯在 t-test 的結果上
### 實作 prepare_percentiles
```
static void prepare_percentiles(int64_t *exec_times, int64_t *percentiles)
{
qsort(exec_times, N_MEASURES, sizeof(int64_t),
(int (*)(const void *, const void *)) cmp);
for (size_t i = 0; i < 100; i++) {
percentiles[i] =
percentile(exec_times, 1 - (pow(0.5, 10 * (double) (i + 1) / 100)),
N_MEASURES);
}
}
```
### 改善 update_statistics
```diff
- for (size_t i = 0; i < N_MEASURES; i++) {
+ for (size_t i = 5; i < N_MEASURES; i++) {
```
因為執行時間受硬體和作業系統影響，因此` Dudect `在函式` update_statistics(ctx) `刻意丟棄前10次所計算的執行時間減少影響，因此我也將作業的` update_statistics() `函式丟棄前五次測試數據
```diff
+ // t-test on the execution time
+ for (size_t crop_index = 0; crop_index < 100; crop_index++) {
+ if (difference < percentiles[crop_index]) {
+ t_push(t, difference, classes[i]);
+ }
+ }
```
加入 percentiles 的計算結果使執行時間較短的數據能突顯在 t-test 的結果上
## 實作 q_shuffle 並探究亂度
利用 Fisher–Yates shuffle 演算法實作 q_shuffle 函式並利用 [lab0](https://hackmd.io/@sysprog/linux2025-lab0/%2F%40sysprog%2Flinux2025-lab0-d) 提供的 python 測試檔對鏈結串列1-2-3-4進行1百萬次的 shuffle，經過大約十五分鐘的執行後得到以下統計結果
||觀察到的頻率|期待的頻率| |觀察到的頻率|期待的頻率
| -------- | -------- | -------- |---|---|-|
1 2 3 4|41666 |41666| 3 1 2 4| 41958|41666
1 2 4 3|41822 |41666| 3 1 4 2 |41727|41666
1 3 2 4|41676 |41666| 3 2 1 4 |42091|41666
1 3 4 2|41814 |41666| 3 2 4 1 |41691|41666
1 4 2 3|41723 |41666| 3 4 1 2 |41964|41666
1 4 3 2|41540 |41666| 3 4 2 1 |41534|41666
2 1 3 4|41472 |41666| 4 1 2 3 |41320|41666
2 1 4 3|41868 |41666| 4 1 3 2 |41377|41666
2 3 1 4|41557 |41666| 4 2 1 3 |41563|41666
2 3 4 1|41387 |41666| 4 2 3 1 |41812|41666
2 4 1 3|41468 |41666 | 4 3 1 2| 41692|41666
2 4 3 1|41672 |41666 | 4 3 2 1| 41606|41666
```
chi square sum: 21.330773292372676
```
對照[卡方圖](https://people.richland.edu/james/lecture/m170/tbl-chi.html)在自由度為23的清況下，得到 P value 在 0.1 ~ 0.9之間，大於預設常見的 P value = 0.05，因此我們可以說統計結果不拒絕虛無假說（$H_0$），代表目前的測試樣本不足以證明 shuffle 的結果不是均勻分布的，可能是測試次數不夠所以無法證明 shuffle 函式不是均勻分佈，或是 shuffle 函式真的為均勻分佈。從上方長條圖可以看出24項數據彼此差異不大，的確接近常態分佈
## 亂數
執行 option entropy 1 並搭配 ih RAND 10 得到以下結果
```
l = [txrinv(29.69%) nxcgyxn(26.56%) elgohm(29.69%) quxfbv(29.69%) zrsfhgzew(35.94%) plxctcly(29.69%) ecwqnxqp(32.81%) fxdyxd(21.88%) qetpub(29.69%) ppttjvdt(25.00%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%) rand(23.44%)]
```
利用以下公式可以計算亂度
$$
S=- \sum^{n}_{i=1} P(x_i) log_b P(x_i)
$$
以第一個字串` txrinv `計算亂度
||$P(x_i)$|$log_2 P(x_i)$| $-P(x_i)log_2 P(x_i)$
| -------- | -------- | -------- |---|
t|0.167 |-2.585| 0.432|
x|0.167 |-2.585| 0.432 |
r|0.167 |-2.585| 0.432|
i|0.167 |-2.585| 0.432 |
n|0.167 |-2.585| 0.432 |
v|0.167 |-2.585| 0.432 |
將得到的$-P(x_i)log_2 P(x_i)$全部相加後得到 S 約為2.59017，按照 shannon_entropy.c 最後所進行的正規化得到以下結果
$$
S = \frac{2.59017}{8} \times 100\%=32.377\%
$$
Sign in with Wallet
Connect another wallet