# 2020q3 Homework1 (lab0)
contributed by < [huang-me](https://github.com/huang-me) >
###### tags:`embedded_master`

# Outline
[TOC]

# Environment

$ uname -a
Linux muen-B550-GAMING-X 5.4.0-40-generic #44-Ubuntu SMP Tue Jun 23 00:01:04 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux

$ gcc --version
gcc (Ubuntu 9.3.0-10ubuntu2) 9.3.0
Copyright (C) 2019 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.

# Implementation

## quene.h

/* Queue structure */
typedef struct {
    list_ele_t *head, *tail; /* Linked list */
    int size;                /* Size of the queue*/
} queue_t;

- 在 Queue structure 中加入 linked list tail 以及 size 以便之後實作 q_size 及 q_insert_tail ，不過也意味之後必須要多加注意 head, tail 的指向

void merge_sort(list_ele_t **head_);

- 在 header file 裡先宣告 merge_sort

## queue.c

### q_insert_head()

    /* return false if the q is NULL */
    if (!q)
        return false;

- 測試傳入的 queue 是否為空的 queue，若為空則直接回傳 false

    /* free the space if malloc returns NULL */
    if (!newh->value) {
        free(newh);
        return false;
    }

- 測試新建立的 linked list 的 value 欄位是否有成功 allocate 空間，如果 allocate失敗的話就直接將整個 linked list 的記憶體歸還

    /* copy the string to the allocated space */
    memset(newh->value, '\0', strlen(s) + 1);
    strcpy(newh->value, s);

- 將創建的空間先用 memset 進行初始化放入"\0"，再用 strcpy 複製所要存取的字串內容
:::warning
在編譯時提示應該儘量避免使用 strcpy 以避免 vulnerability，所以將 strcpy 置換為 stncpy
strcpy 不會判斷 buffer 的 size，因此有機會將一個尺寸超過 buffer size 的資料放入記憶體內，因此改動到不合法的記憶體
:::

     new = malloc(sizeof(list_ele_t));
     if(!new) {
         free(new);
         return false;
     }

- make test 時發生錯誤提示沒有辨識到 malloc 失敗的情況，於是加上上方程式碼在 malloc 失敗之後歸還記憶體以及回傳 false

### q_insert_tail()

    new->next = NULL;
    if (!q->tail) {
        q->tail = q->head = new;
    } else {
        q->tail->next = new;
        q->tail = new;
    }

- 若還沒有 q->tail 代表目前的 queue 是空的，就直接將 head 以及 tail 都指向新的記憶體位置
- else 之後則是將 tail->next 指向新的記憶體之後再更新 tail 的指向
:::warning
make test 測試 O(1) 的時候不一定每次都通過，還需要思考一下原因
:::

### q_free()

    list_ele_t *tmp;
    tmp = q->head;
    while (tmp) {
        tmp = tmp->next;
        q->head->next = NULL;
        free(q->head->value);
        free(q->head);
        q->head = tmp;
    }

    free(q);

- 藉助 tmp 的幫助可以從 queue 的 head 開始走到 NULL 就可以依序將記憶體還給系統
:::warning
一開始忘記 free value 因此有 error 提示 n blocks still allocated
:::

### q_reverse()

    if (!q || q->size < 2)
        return;

    list_ele_t *tmp = q->head->next;
    q->tail->next = q->head;
    while (tmp != q->tail) {
        tmp = tmp->next;
        q->head->next->next = q->tail->next;
        q->tail->next = q->head->next;
        q->head->next = tmp;
    }
    q->tail = q->head;
    q->head = q->head->next;
    q->tail->next = NULL;

- 一開始我建立一個 tmp queue 並且依序將舊的資料指向新的 queue，不過因為這次作業的結構不是 doubly linked list ，所以這個方法要不停的從舊的 queue head 走到結束以找到最後一個 element ，所以如果 queue 內的資料比較多就容易超過時間
- 最後在參考上學期的同學([ZhuMon](https://hackmd.io/4tutrI2kSd6BGROf2KSy6g?both#queuec))作業中找到更加簡潔的做法,利用 tail->next 指向 head->next，以記得下一個要指向的 element
- 流程圖大致上如下
* **STEP 1**

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"];    
        2 [label = "{<data>2 |<ref>}"];
        3 [label = "{<data>3 |<ref>}"];
        4 [label = "{<data>4 |<ref>}"];
        1:ref -> 2:data [color=orange];
        2:ref -> 3:data [color=orange];
        3:ref -> 4:data [color=orange];
        head->1;
        tail->4;
        tmp->2;
        4:ref -> 2 [color=yellow]
    }

* **STEP 2**

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"];    
        2 [label = "{<data>2 |<ref>}"];
        3 [label = "{<data>3 |<ref>}"];
        4 [label = "{<data>4 |<ref>}"];
        1:ref -> 3:data [color=orange];
        2:ref -> 1:data [color=orange];
        3:ref -> 4:data [color=orange];
        head->1;
        tail->4;
        tmp->3;
        4:ref -> 2 [color=yellow]
    }

* **STEP 3**

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"];    
        2 [label = "{<data>2 |<ref>}"];
        3 [label = "{<data>3 |<ref>}"];
        4 [label = "{<data>4 |<ref>}"];
        1:ref -> 4:data [color=orange];
        2:ref -> 1:data [color=orange];
        3:ref -> 2:data [color=orange];
        head->1;
        tail->4;
        tmp->4;
        4:ref -> 3 [color=yellow]
    }

:::warning
make test 時發現在 sort 之後進行 reverse 就會產生錯誤甚至出現 segmentation fault 以為 reverse 的演算法有錯誤於是將 reverse 方法改變成以下方法
:::

list_ele_t *tmp = q->head->next, *store_head = q->head;
while (tmp != q->tail) {
    q->tail->next = tmp;
    tmp = tmp->next;
    q->tail->next->next = q->head;
    q->head = q->tail->next;
}
q->head = q->tail;
q->tail = store_head;
q->tail->next = NULL;

- 先利用 tail->next 存取暫時的 list tail，從 head->next 開始進行處理，將每個 element 的 next 指標指向 tail->next，並且把 tail->next 指向此 element
- 以下是新的 reverse 步驟
- **STEP 1** ==Inititialize==

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"]; 
        2 [label = "{<data>2 |<ref>}"]; 
        3 [label = "{<data>3 |<ref>}"]; 
        4 [label = "{<data>4 |<ref>}"]; 
        1:ref -> 2:data [color=orange];
        2:ref -> 3:data [color=orange];
        3:ref -> 4:data [color=orange];
        //4:ref -> 2:data;
        tail -> 4:data;
        store_head -> 1:data [color=red];
        tmp -> 2:data [color=yellow];
        head -> 1:data;
    }

- **STEP 2** ==Start reverse==

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"]; 
        2 [label = "{<data>2 |<ref>}"]; 
        3 [label = "{<data>3 |<ref>}"]; 
        4 [label = "{<data>4 |<ref>}"]; 
        1:ref -> 2:data;
        2:ref -> 1:data [color=orange];
        3:ref -> 4:data [color=orange];
        4:ref -> 2:data;
        tail -> 4:data;
        store_head -> 1:data [color=red];
        tmp -> 3:data [color=yellow];
        head -> 2;
    }

- **STEP 3**

    digraph linked_list{
        rankdir=LR;
        node [shape=record];
        1 [label = "{<data>1 |<ref>}"]; 
        2 [label = "{<data>2 |<ref>}"]; 
        3 [label = "{<data>3 |<ref>}"]; 
        4 [label = "{<data>4 |<ref>}"]; 
        1:ref -> 2:data;
        2:ref -> 1:data [color=orange];
        3:ref -> 2:data [color=orange];
        4:ref -> 3:data;
        tail -> 4:data;
        store_head -> 1:data [color=red];
        tmp -> 4:data [color=yellow];
        head -> 3;
    }

### q_size()

    return (!q) ? 0 : q->size;

- 利用 queue 的結構裡面的 size 可以在O(1)的時間複雜度得到目前的 queue size
:::warning
make test 測試 O(1) 的時候不一定每次都通過，還需要思考一下原因
:::

### q_remove_head()

   if (sp) {
        size_t size = (bufsize - 1 > strlen(q->head->value))
                          ? strlen(q->head->value) + 1
                          : bufsize;

        memset(sp, '\0', size);
        strncpy(sp, q->head->value, size - 1);
    }  

- 第一次判斷 size 用以記憶丟掉的 value 時計算錯誤所以 make test 時出現 "ERROR: copying of string in remove_head overflowed destination buffer."
- 因為無論是 bufsize 或者 string 都需要有一個字的空間留給 '\0'，因此比較時應該拿 bufsize - 1 與 strlen 作比較

### q_sort()
- 因為想要滿足 O($n\log{n}$) 所以選用 merge sort 就算在 worst case 還是可以保持一樣的效率

if (!(*head) || !((*head)->next))
    return;

- 因為 merge sort 用到 recursive 來達成，當傳入的 linked list 為空或者只有一個 element 的話便直接 return 不需要再作處理

    list_ele_t *tmp1, *tmp2;
    tmp1 = (*head)->next;
    tmp2 = *head;
    while (tmp1 && tmp1->next) {
        tmp1 = tmp1->next->next;
        tmp2 = tmp2->next;
    }
    tmp1 = tmp2->next;
    tmp2->next = NULL;
    tmp2 = *head;

    merge_sort(&tmp1);
    merge_sort(&tmp2);

- 使用從頭開始探索整個 linked list 的方式找尋 list 的中間點，並且在將 tmp1、tmp2 分別指向 list 的頭以及中間點後分開成兩個各別的 list，再呼叫 merge_sort

    *head = NULL;
    list_ele_t **tmp = head;
    while (tmp1 && tmp2) {
        if (strcmp(tmp1->value, tmp2->value) < 0) {
            *tmp = tmp1;
            tmp1 = tmp1->next;
        } else {
            *tmp = tmp2;
            tmp2 = tmp2->next;
        }
        tmp = &((*tmp)->next);
    }

    *tmp = tmp1 ? tmp1 : tmp2;

- 在將兩個 list 都排序完之後，分別比較兩個 list 的頭，將比較小的先放入新的 list 中，重複執行數次之後就排序完成了
:::warning

    while (q->tail->next)
        q->tail = q->tail->next;

在 sort 完之後一定要記得更新整個 list 的 tail 否則 sort 完成之後做的操作都會發生錯誤，前面提及的 reverse 修改原因就是因為這裡忘記更新 tail 的位置
:::

# 論文〈[Dude, is my code constant time?](https://eprint.iacr.org/2016/1123.pdf)〉探討
- 因為在執行 make test 時，不管是 insert_head 或者 q_size 都有幾率被分析為 probably not constant time，所以我開始研究此論文使用的方法有沒有什麼地方是值得思考，並且用來精進我的實作
:::warning
最後沒有思考出任何比較明確的解決方法QQ
:::

# Bonus
## .vimrc 修改
- 因為本次作業有要求要用一致的格式，不過一直執行```clang-format -i *.[ch]``` 實在有些麻煩，所以我便著手開始改寫 .vimrc 試圖使其自動修改檔案到符合的格式，使用 [rhysd]("https://github.com/rhysd") 開發的 [vim-clang-format]({"https://github.com/rhysd/vim-clang-format"}) 便可以達成自動將 c 語言檔案套用到規定的格式

let g:clang_format#style_options = {
  \ "BasedOnStyle": "Chromium",
  \ "Language": "Cpp",
  \ "MaxEmptyLinesToKeep": 3,
  \ "IndentCaseLabels": "false",
  \ "AllowShortIfStatementsOnASingleLine": "false",
  \ "AllowShortCaseLabelsOnASingleLine": "false",
  \ "AllowShortLoopsOnASingleLine": "false",
  \ "DerivePointerAlignment": "false",
  \ "PointerAlignment": "Right",
  \ "SpaceAfterCStyleCast": "true",
  \ "TabWidth": 4,
  \ "UseTab": "Never",
  \ "IndentWidth": 4,
  \ "BreakBeforeBraces": "Linux",
  \ "AccessModifierOffset": -4}
  
autocmd FileType c ClangFormatAutoEnable

- 將老師給的 .clang-format 檔案改寫成 dataset， 再設定當檔案語言為 c 時自動套用 format
:::warning
之後發現這樣的方法目前不適用於 header 以及其他語言，也在 ```README.md``` 中發現有其他的方式可以利用安裝好的 ```clang-format.py``` 自動套用格式

function! Formatonsave()
  let l:formatdiff = 1
  py3f /usr/share/vim/addons/syntax/clang-format.py
endfunction
autocmd BufWritePre *.h,*.hpp,*.c,*.cc,*.cpp call Formatonsave()

:::
## 嘗試新增上下鍵功能(console.c)
### TRY 1
#### interpret_cmda()

/* use an 2D-array to store the cmd history */
char tmpstring[1024];
memset(tmpstring, '\0', 1024);
for (int tmp = 0; tmp < argc; tmp++) {
    strncat(tmpstring, argv[tmp], strlen(argv[tmp]));
    strncat(tmpstring, " ", 1);
}

for (int tmp = 0; tmp < 4; tmp++) {
    strncpy(cmd_history[tmp], cmd_history[tmp + 1], 1024);
}

- 在實作上下鍵之前必須先記住前幾次的 command，這邊寫了一個 2D-array 記憶前5次的指令內容
:::warning
程式收到上下按鍵的資料分別為（上：```"\033[A"```下：```"\033[B"```）
目前如果在 qtest.c 檔案直接加入新的 add_cmd 可以順利執行 function，不過如果想要達成可以自動變換為之前執行的指令可能還有一些困難
:::
### TRY 2
#### cmd_select()

/* initialize the cmd_his */
for (int tmp = 0; tmp < 5; tmp++) {
    cmd_his[tmp] = malloc(1024);
    memset(cmd_his[tmp], '\0', 1024);
}

- 初始化 cmd_his 之後用來存取前面的 command
#### readline()

for (int tmp = 0; tmp < 4; tmp++) {
    memset(cmd_his[tmp], '\0', 1024);
    strncpy(cmd_his[tmp], cmd_his[tmp + 1], 1024);
}
strncpy(cmd_his[4], linebuf, 1024);

- 在 readline 時直接存取更新新的 commad
:::warning
在將存取之前的 command 的程式提前執行之後還是失敗，因為 strcmp 無法比較 up arrow 以及 ```"\033[A"```
:::