# 2024q1 Homework1 (lab0)
contributed by < [Terry7Wei7](https://github.com/Terry7Wei7) >
### Reviewed by `vax-r`
* 未完成任何指定事項
* github repository 未提交任何 commmit
### Reviewed by `vestata`
1. github repository 未提交 commit
2. Git 命令筆記與此開發紀錄無直接相關，故可省略。
3. 在開發紀錄中應使用 `diff` 標示修改過的程式碼。
## 問題
## 筆電安裝雙系統（windows/ubuntu_linux）
因後續檢視perf需求,故重新安裝ubuntu22.04
## 前置作業
```bash
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 45 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-6700HQ CPU @ 2.60GHz
CPU family: 6
Model: 94
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 2
Stepping: 3
BogoMIPS: 5183.99
```
### cppcheck version
```bash
terry@terry-virtual-machine:~$ cppcheck --version
Cppcheck 2.7
```
### 複製 `id_rsa` 到剪貼簿
```bash
$ cat ~/.ssh/id_rsa.pub | xclip -selection clipboard
```
### git 命令筆記
| 命令 | 作用 |
|---------------------|------------------------------------------------------------------------------------------------------|
| git init | 初始化一個新的 Git 儲存庫。 |
| git clone `<repository>` | 複製一個遠端儲存庫到本地。 |
| git add `<filename>` | 將檔案的變更添加到暫存區。 |
| git add . | 將所有檔案的變更添加到暫存區。 |
| git commit -m "Commit message" | 提交暫存區的變更到本地儲存庫。 |
| git status | 檢查儲存庫的狀態，顯示已修改、已追蹤、未追蹤等檔案的狀態。 |
| git log | 顯示提交的歷史記錄。 |
| git log -p | 顯示提交的歷史記錄，包括每次提交的詳細差異。 |
| git shortlog | 生成一個簡化的提交歷史報告，按照作者進行分組。 |
| git branch | 顯示本地分支列表。 |
| git branch <branch_name> | 建立新分支。 |
| git checkout <branch_name> | 切換到指定的分支。 |
| git merge <branch_name> | 合併指定分支到目前分支。 |
| git pull | 從遠端儲存庫拉取最新的變更。 |
| git push | 推送本地變更到遠端儲存庫。 |
| git diff | 顯示工作目錄與暫存區之間、暫存區與最後提交之間的差異。 |
| git reset HEAD `<filename>` | 取消對指定檔案的暫存。 |
| git rm `<filename>` | 從工作目錄和暫存區中刪除檔案。 |
| git mv `<old_filename>` `<new_filename>` | 更改檔案名稱。 |
| git blame `<filename>` | 逐行顯示指定檔案對應的最新修改是由誰進行及其提交資訊。 |
| git revert `<commit_sha>` | 建立一個新的提交，該提交會撤銷之前的一次或多次提交的變更。 |
| git rebase `<base_branch>` | 用於將一個分支的修改應用到另一個分支。 |
| git show `<commit_sha>` | 顯示一個特定提交的詳細信息，包括提交的作者、日期、變更的文件、差異等。 |
## 補齊指定的佇列操作
### `牛刀小試`
```bash
make test
scripts/driver.py -c
--- Trace Points
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-01-ops 0/5
+++ TESTING trace trace-02-ops:
# Test of insert_head, insert_tail, remove_head, remove_tail, and delete_mid
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-02-ops 0/6
+++ TESTING trace trace-03-ops:
# Test of insert_head, insert_tail, remove_head, reverse and merge
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-03-ops 0/6
+++ TESTING trace trace-04-ops:
# Test of insert_head, insert_tail, size, swap, and sort
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-04-ops 0/6
+++ TESTING trace trace-05-ops:
# Test of insert_head, insert_tail, remove_head, reverse, size, swap, and sort
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-05-ops 0/6
+++ TESTING trace trace-06-ops:
# Test of insert_head, insert_tail, delete duplicate, sort, descend and reverseK
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-06-ops 0/6
+++ TESTING trace trace-07-string:
# Test of truncated strings
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-07-string 0/6
+++ TESTING trace trace-08-robust:
# Test operations on empty queue
ERROR: Computed queue size as -1, but correct value is 0
--- trace-08-robust 0/6
+++ TESTING trace trace-09-robust:
# Test remove_head with NULL argument
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-09-robust 0/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
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-11-malloc 0/6
+++ TESTING trace trace-12-malloc:
# Test of malloc failure on insert_tail
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-12-malloc 0/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
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-14-perf 0/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
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-15-perf 0/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
Segmentation fault occurred. You dereferenced a NULL or invalid pointer--- trace-16-perf 0/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
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
ERROR: Probably not constant time or wrong implementation
--- trace-17-complexity 0/5
--- TOTAL 12/100
make: *** [Makefile:60: test] Error 1
```
### `q_new`, `q_free`
```c
/* Create an empty queue */
struct list_head *q_new()
{
- return NULL;
+ struct list_head *tmp = (struct list_head *) malloc(sizeof(*tmp));
+ if (!tmp) {
+ return NULL;
+ }
+ INIT_LIST_HEAD(tmp);
+ return tmp;
}
```
```c
/* Free all storage used by queue */
/* Free all storage used by queue */
-void q_free(struct list_head *head) {}
+void q_free(struct list_head *l)
+{
+ if (!l)
+ return;
+
+ element_t *curr, *safe;
+ list_for_each_entry_safe (curr, safe, l, list) {
+ if (curr->value)
+ free(curr->value);
+ free(curr);
+ }
+ free(l);
+}
```
### `q_insert_head`, `q_insert_tail`
```
/* Insert an element at head of queue */
bool q_insert_head(struct list_head *head, char *s)
{
+ if (!head)
+ return false;
+
+ element_t *new_node = (element_t *) malloc(sizeof(*new_node));
+ if (!new_node)
+ return false;
+
+ size_t len = strlen(s);
+ new_node->value = (char *) malloc(sizeof(char) * (len + 1));
+ if (!new_node->value) {
+ free(new_node);
+ return false;
+ }
+
+ strncpy(new_node->value, s, len + 1);
+
+ list_add(&new_node->list, head);
return true;
}
```
### `q_remove_head`, `q_remove_tail`
```
/* Remove an element from head of queue */
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
- return NULL;
+ if (!head || head == head->next)
+ return NULL;
+ element_t *removed = list_entry(head->next, element_t, list);
+ if (sp) {
+ strncpy(sp, removed->value, bufsize);
+ sp[bufsize - 1] = '\0';
+ }
+
+ list_del(&removed->list);
+ return removed;
}
```
:::warning
> [name=I-HSIN Cheng]
> 善用 `diff` 而非單純寫上 `-, +` 來表示程式碼更動，並且列出的更動應是優化的部分而非最初的實作。
:::
---
## 研讀論文〈Dude, is my code constant time?〉
<s>
### dudect 工具介紹：
用於評估代碼是否在給定平台上以恆定時間運行。
基於泄漏檢測技術，實現簡潔、易於使用和易於維護的工具。
### 計時攻擊和泄漏檢測：
計時攻擊是一種側信道攻擊，通過測量加密實現的執行時間來推斷密鑰或密碼等秘密信息。
泄漏檢測測試執行時間，檢查兩個不同輸入數據類別的執行時間分佈是否統計上不同。
### 泄漏檢測的步驟：
測量執行時間：重複測量加密函數的執行時間，使用兩個不同輸入數據類別。
後處理：對每個測量進行一些後處理，如裁剪或更高級別的預處理。
應用統計檢驗：使用統計檢驗檢查兩個定時分佈是否相等。
</s>
:::warning
使用台灣慣用科技詞彙書寫，且該切合論文內容。
:::
:::warning
> [name=I-HSIN Cheng]
> TODO : 完成指令論文的閱讀和實驗
:::
Sign in with Wallet
Connect another wallet