2024q1 Homework1 (lab0)

contributed by < chloe0919 >

Reviewed by `david965154`

自 q_insert_head 函式後就開始貼上完整程式碼，可以嘗試用實作想法或只貼上實作的關鍵程式碼。

在 strcpy strncpy 之間選擇 strncpy 是因為 strcpy 會有緩衝區溢位的問題，而 strncpy 可以解決這問題，但是 strncpy 不會自動補上'\0'，所以需要自己手動增加。

事實上， strncpy 沒辦法避免溢位，以下實驗

#include <stdio.h>
#include <string.h>
#define MAX 9
int main() {
    char source[MAX] = "123456789";
    char source1[MAX] = "123456789";
    char destination[MAX] = "abcdefg";
    char destination1[MAX] = "abcdefg";
    int i = 5;

    /* This is how strcpy works */
    printf("destination is originally = '%s'\n", destination);
    strcpy(destination, source);
    printf("after strcpy, dest becomes '%s'\n\n", destination);

    /* This is how strncpy works */
    printf( "destination1 is originally = '%s'\n", destination1);
    strncpy(destination1, source1, 9);
    printf( "After strncpy, destination1 becomes '%s'\n", destination1 );

    return 0;
}

而輸出為

destination is originally = 'abcdefg'
after strcpy, dest becomes '123456789123456789abcdefg'

destination1 is originally = '123456789abcdefg'
After strncpy, destination1 becomes '123456789abcdefg'
*** stack smashing detected ***: terminated

我既使用了 strncpy ，也提供了要複製過去的大小，但多輸出了 9abcdefg ，若將問題歸咎至未將 destination1 最後補上 '\0' ，那麼 strcpy 也能達到避免緩衝區溢位的問題。
只要字串的複製來源一超出指定大小，便要做出避免溢位的處理，那麼 strncpy 本身便不是用來避免緩衝區溢位的問題。

The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.

C 語言規格書也完全沒有提到他用來避免緩衝區溢位的問題。

參考 Why should you use strncpy instead of strcpy?
雖然為 stack overflow，但也可以看到 C 中字串處理方法和問題。

Chloexyw 感謝提醒，我會修正以下的說明。
後來我去檢查以上提供的程式碼，發現最主要的問題是在宣告 char 時配置的空間就不足了，若能使用以下命令對程式進行檢查

$gcc -fsanitize=address -g filename.c

之後會輸出以下的檢查過程，就能先在宣告變數 source 的時候就發現記憶體位址溢位的問題

  This frame has 4 object(s):
    [32, 41) 'source' (line 5) <== Memory access at offset 41 overflows this variable
    [64, 73) 'source1' (line 6)
    [96, 105) 'destination' (line 7)
    [128, 137) 'destination1' (line 8)
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow ../../../../src/libsanitizer/asan/asan_interceptors.cpp:439 in __interceptor_strcpy
Shadow bytes around the buggy address:
  0x10001ee195a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee195b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee195c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee195d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee195e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10001ee195f0: 00 00 00 00 f1 f1 f1 f1 00[01]f2 f2 00 01 f2 f2
  0x10001ee19600: 00 01 f2 f2 00 01 f3 f3 00 00 00 00 00 00 00 00
  0x10001ee19610: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee19620: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee19630: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10001ee19640: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

是的，我在一開始就沒對 source 提供足夠大的空間 ( 因為需要添加 '\0' 於最後， MAX 應為 10 )，因為編譯器不會對此進行警告，而我想讓 strncpy 發生記憶體位址溢位的問題，因此我刻意選擇不對 source 提供足夠大的空間，只要 q_remove_head 一提供錯誤的 bufsize 且實作時沒有檢查就會出現錯誤。

你的洞見呢？

開發環境

$ 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:         43 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  12
  On-line CPU(s) list:   0-11
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 5 3600 6-Core Processor
    CPU family:          23
    Model:               113
    Thread(s) per core:  2
    Core(s) per socket:  6
    Socket(s):           1
    Stepping:            0
    BogoMIPS:            7200.10

佇列實作與改進

`q_new`

首先宣告一個 list_head 的指標 head ，並且使用 list.h 中的INIT_LIST_HEAD 建立並初始化一個 list head 分配給 head 記憶體位置。

HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」

q_free

詳閱資訊科技詞彙翻譯，理解詞彙背後的考量因素和使用精準詞彙。

Chloexyw 好的，謝謝老師

利用 list_for_each_entry_safe 的兩個指標 node 和 n 去逐一走訪 head 的所有節點，並且將它刪除掉，這裡不使用 list_for_each_entry 的是因為若使用 q_release_element 後會破壞掉原本的鏈結關係，導致無法找到當前節點連接的下一個節點

q_free 的程式碼：

void q_free(struct list_head *l)
{
    // Release all elements first, and then release the head.
    if (!l)
        return;
    element_t *n;
    element_t *node = list_first_entry(l, element_t, list);
    list_for_each_entry_safe (node, n, l, list)
        q_release_element(node);
    free(l);
}

使用作業指定的程式碼縮排風格。

Chloexyw 好的，已更改

q_insert_head

剛開始實作時是使用 memcpy ，而且計算 s 的字元數量時使用的是 sizeof(s) ，因為 sizeof 計算的是變量或類型所占用的字元數量，所以在 make test 的截斷字串的測試中就會產生錯誤，應該使用 strlen 來計算出字串的個數才對。

string 是「字串」，character 是「字元」
memory 是「(主) 記憶體」
byte 是「位元組」

考慮到科技文化延續議題，我們尊重台灣資訊科技前輩的篳路藍縷、理解詞彙背後的考量因素，和使用精準詞彙，其實後者也是工程素養的一環。

Chloexyw 好的，已更改

另外在配置記憶體的部份也要設置條件來判斷是否有配置成功，如果失敗需要釋放出配置的記憶體。

改進你的漢語描述。

台大電機系李宏毅教授對於 ChatGPT 的看法是，要善用人工智慧的成果，一旦人們得以善用，人類的書寫不該比 GPT 一類的語言模型差。

\to

2023 年 Linux 核心設計/實作課程第一次作業檢討

q_insert_head 的程式碼：

bool q_insert_head(struct list_head *head, char *s){
    if(!head || !s)
        return false;
    element_t *new = malloc(sizeof(element_t));   
    if(!new)                              
        return false;
    INIT_LIST_HEAD(&new->list);
    char *value = malloc(sizeof(char)*(strlen(s) + 1));
    if(!value){                                             
        free(new);
        return false;
    }
    //memcpy(value,s ,strlen(s) + 1);
    strncpy(value, s, strlen(s));
    value[strlen(s)] = 0;
    new->value = value;
    list_add(&new->list, head);
    return true;
}

剛開始是使用 memcpy 去複製字串到 value ，但是發現這樣會比較慢，所以後來改成使用 strncpy ，另外還需要在後面補上'\0'。

q_insert_tail

實作方法和 q_insert_head 類似，只有將 list_add 改成 list_add_tail 。

q_remove_head

想法是利用 list_first_entry 先找到head的記憶體位置，再來根據 list.h 的說明，如果 sp 為非空而且有一個 element 被移除掉，需要複製被移除的字串到 sp ，最後將 tmp 指向的 node 利用 list_del_init 移除並且初始化。

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 *tmp = list_first_entry(head, element_t,list);  // list_first_entry : find the address of first element
    if (sp){
        strncpy(sp, tmp->value, bufsize - 1);
        sp[bufsize - 1] = 0;
    }
    list_del_init(&tmp->list);
    return tmp;
}

根據 C 語言規則書

The strncpy function copies not more than n characters (characters that follow a null character are not copied) from the array pointed to by s2 to the array pointed to by s1. If copying takes place between objects that overlap, the behavior is undefined.

strncpy 可以將不超過 n 個字元從 s2 複製到 s1 ，不過並不會自動複製 \0 所以需要自己手動增加。

查詢第一手材料，例如 C 語言規格書和 Linux man-pages

另外在 list_del 和 list_del_init 的選擇上，根據下面提供的圖表，需要選擇 list_del_init 才能將需要 remove 的節點原始的鏈結狀態初始化，因為 list_del 並不會破壞掉即將被移除的節點本身的鏈結關係。

list_del :

list_del_init :

使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記內文。

Chloexyw 好的，已更改

q_remove_tail

實作方法和 q_remove_head 類似，只有將 list_first_entry 改成 list_last_entry 找出最後節點的位置即可。

q_size

參考〈2024 年 Linux 核心設計/實作課程作業 —— lab0 (A)〉，利用 list_for_each 逐一走訪所有節點並且每次都將 len+=1 。

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)

Chloexyw 好的，已更改

q_delete_mid

首先，透過 left 和 right 分別從左右兩邊開始尋找中點，再來利用 list_entry 找出目前指到的中點的 entry 並且使用 q_release_element 釋放掉此　element 。

q_delete_mid的程式碼：

bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;
    struct list_head *left = head->next;
    struct list_head *right = head->prev;
    while ((left != right) && (left->next != right)) {
        left = left->next;
        right = right->prev;
    }
    list_del(right);
    element_t *del = list_entry(right, element_t, list);
    q_release_element(del);
    return true;
}

q_delete_dup

注意標點符號的使用，這裡該用 〈 和 〉

Chloexyw 好的，已更改

參考〈Linux 核心專題: 改進 lab0〉，利用 list_for_each_entry_safe 的兩個指標 curr 和 nex ，判斷 curr 是否等於 nex ，如果相等就將目前 curr 指到的節點使用 list_del 改變鏈結關係，再用 q_release_element 將此節點的　element　釋放掉，另外，使用布林值　flag　用來判斷上一次是否有刪除過，如果有且這次沒有出現重複的節點，則需要再移除一次目前節點，因為要達到的目標是需要移除到全部有連續重複的節點。ihe

q_delete_dup 的程式碼

bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return false;
    bool flag = false;
    element_t *curr, *nex;
    list_for_each_entry_safe(curr, nex, head, list) {
        if (&nex->list != head && strcmp(curr->value, nex->value) == 0) {
            flag = true;
            list_del(&curr->list);
            q_release_element(curr);
        } else if (flag) {
            flag = false;
            list_del(&curr->list);
            q_release_element(curr);
        }
    }
    return true;
}

q_swap

宣告一個整數　count　來紀錄目前到達佇列的第幾個索引的節點，因為需要完成每兩個節點就進行交換的動作，所以當 count%2 == 1 的時候就要交換。
另外用 list_for_each_safe 來紀錄目前目前節點跟下一個節點，這裡不使用 list_for_each 的原因是：
在 list.h 中有說明 list_for_each_safe 的流程是每次迭代都會將 curr = n，n = curr->next ，而當我們在使用 list_move 時會改變掉 curr 指向的節點的相對位置，此時就要利用 n 指標來將 curr 指回正確的位置，程式才不會產生錯誤。

q_swap 的程式碼

void q_swap(struct list_head *head)
{
    if (!head || list_is_singular(head))
        return;
    struct list_head *curr, *n;
    struct list_head *tmp = head;
    int count = 0;
    list_for_each_safe(curr, n, head) {
        if (count % 2 == 1) {
            list_move(curr, tmp);
            tmp = curr->next;
        }
        count++;
    }
}

q_reverse

剛實作時使用 list_for_each ，導致一直無法正確　reverse　，經過幾次　trace　後發現因為 list_move 會將改變鏈結關係，將 curr 指到的位置移到 head 之後，所以需要使用 list_for_each_safe ，在每次迭代後都將 curr 只指回到原始位置的下一個節點，才能成功　reverse 。

q_reverse的程式碼：

void q_reverse(struct list_head *head) 
{
    if(!head || list_is_singular(head))
        return;
    struct list_head *curr,*n;
    list_for_each_safe(curr, n, head){
        list_move(curr, head);
    }
}

用以下圖表說明　reverse　實作想法：

經過第一次的迭代後，會形成：

再來使用 list_move 會將　B　插入到 tmp 所指到的　head　後面

再經過一次迭代 curr = n，n = curr->next 後：

這時候將　C　插入　head　之後

使用 Graphviz 重新製圖，並嵌入到 HackMD 筆記內文。

Chloexyw 好的，已更改

最後，經過最後一次迭代 curr = n，n = curr->next 後，形成　reverse　結果

q_reverseK

採用和 q_reverse 和 q_swap 的作法，一樣是有使用整數 countK 去紀錄位置，另外還有定義整數 n 為 n = q_size(head) / k 來當作臨界點，當滿足 k 個一組的時候才可以 reverse ，而 tmp 用來紀錄往後 list_move 時要插入的位置，所以只有在 countK % k == 0 時才會改變其位置。

list_for_each_safe (curr, safe, head) {
    if (countK % k == 0) {
        tmp = curr->prev;
    }
    if ((countK / k) < n)
        list_move(curr, tmp);
    countK++;
}

q_sort

注意標點符號的使用，這裡該用 〈 和 〉

Chloexyw 好的，已更改

參考〈你所不知道的 C 語言: linked list 和非連續記憶體〉以及〈Linux 核心專題: 改進 lab0〉，採用　Divide and Conquer　的想法先將佇列拆成子佇列，再透過 mergeTwoLists 將佇列排序並合併。

mergeTwoLists 的原始程式碼：

void mergeTwoLists(struct list_head *L1, struct list_head *L2){
    if (!L1 || !L2)
        return;
    struct list_head *Lnode = L1->next, *Rnode = L2->next;
    while(Lnode != L1 && Rnode != L2){
        if(strcmp(list_entry(Lnode, element_t, list)->value,list_entry(Rnode, element_t, list)->value) < 0){
            Lnode = Lnode->next;
        } else{
            list_move(Rnode, Lnode->prev);
            Rnode = Rnode->next;
        }
    }
    if (q_size(L2) != 0) {
        list_splice_tail(L2, L1);
    }
}

其中，如果先執行 list_move(Rnode, Lnode->prev) 則會將 Rnode 插入到 L1 中，這樣下一次執行 Rnode = Rnode->next 時， Rnode 會變成指向 Lnode 的資料，這時會發生錯誤。
因此，將原始程式碼的這兩行指令改成以下才會成功

Rnode = Rnode->next;
list_move(Rnode->prev, Lnode->prev);

在 q_sort 實現 Divide and Conquer 的想法，先利用 fast 和 slow 找出佇列的中點，接著宣告一個 list right 並初始化，再利用 list_cut_position 將中點左邊和右邊切開並且遞迴將左右切的更小，最後使用 mergeTwoLists 將兩個 list 排序並合併。

q_sort的程式碼：

void q_sort(struct list_head *head, bool descend)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    struct list_head *slow = head->next;
    for (struct list_head *fast = head->next;
         fast != head && (fast->next) != head; fast = fast->next->next)
        slow = slow->next;
    struct list_head *mid = slow;
    LIST_HEAD(right);
    list_cut_position(&right, head, mid->prev);

    q_sort(head, 1);
    q_sort(&right, 1);
    mergeTwoLists(head, &right);
}

q_ascend

參考〈Linux 核心專題: 改進 lab0〉的想法，先從佇列的最右邊開始逐步去看在 curr 右邊的 nex 指向的值是否有小於 curr ，如果小於則需要使用 list_del 和 q_release_element 將指向 curr 的節點刪除掉，每次都只需要看在 curr 右邊的值就好了，因為更右邊的值已經確定了是不需要被刪掉的節點了，代表他們一定是呈現升序。
另外在參考資料中是從 head->prev 開始看，但是實際上最右邊的點一定不會被移除掉，因為它的右邊並沒有值，所以可以從 head->prev->prev 開始執行。

q_ascend的程式碼：

int q_ascend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    if (list_is_singular(head))
        return 1;
    struct list_head *curr = head->prev->prev;
    while (curr != head) {
        struct list_head *nex = curr->next;
        element_t *f = list_entry(curr, element_t, list);
        element_t *s = list_entry(nex, element_t, list);
        if (strcmp(f->value, s->value) > 0) {
            struct list_head *del = curr;
            list_del(del);
            curr = curr->prev;
            q_release_element(list_entry(del, element_t, list));
        } else
            curr = curr->prev;
    }
    return q_size(head);
}

q_descend

實作概念和 q_ascend 類似，只有比較時需要改成 strcmp(f->value, s->value) > 0

q_merge

先透過 list_entry 算出 queue_contex_t *queue_head 的記憶體位置，也就是第一個節點的位置，然後逐一走訪佇列並透過 mergeTwoLists() 將第二個以後的佇列合併進第一個佇列中，然後再使用 INIT_LIST_HEAD 將已經合併過的佇列初始化，而且長度被設為0 。

無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景。
在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","

Chloexyw 好的，我會再改進

q_merge的程式碼：

int q_merge(struct list_head *head, bool descend)
{
    if (!head)
        return 0;
    queue_contex_t *queue_head = list_entry(head->next, queue_contex_t, chain);
    for (struct list_head *curr = head->next->next; curr != head;
         curr = curr->next) {
        queue_contex_t *queue = list_entry(curr, queue_contex_t, chain);
        mergeTwoLists(queue_head->q, queue->q);
        INIT_LIST_HEAD(queue->q);
        queue->size = 0;
    }
    return queue_head->size;
}

研讀 Linux 核心原始程式碼的 list_sort

__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
	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;

根據 attribute((nonnull)) function attribute 定義：

This function attribute specifies function parameters that are not supposed to be null pointers. This enables the compiler to generate a warning on encountering such a parameter.

表示 __attribute__ 屬於 function attribute，當第二、第三位置的 pointer 是 NULL 時發出警告。

首先利用head->prev->next = NULL;將 head 的最後節點指向 NULL

/* This mergesort is as eager as possible while always performing at least
 * 2:1 balanced merges.  Given two pending sublists of size 2^k， they are
 * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
 *
 * Thus, it will avoid cache thrashing as long as 3*2^k elements can
 * fit into the cache.  Not quite as good as a fully-eager bottom-up
 * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
 * the common case that everything fits into L1.

在 list_sort.c 的註解中提到這裡 merge sort 的實作重點。方法為以下的特點：

兩個要被合併的 list 至少是
$2^{k + 1}$ ：
$2^{k}$ = 2 : 1的平衡狀態
list_sort 和 fully-eager bottom-up mergesort 不同的是，前者是出現兩個
$2^{k}$ 的 list 時不會立刻合併，而後者是只要出現兩個
$2^{k}$ 就會合併

實作的方法是利用整數 count 紀錄有多少數量的 element 在 pending list 中，而且根據你所不知道的 C 語言: linked list 和非連續記憶體之中 list_sort 的介紹還有上述的規則，我們可以歸納出以下的規律：
如果要產生

2^{k + 1}

的鏈結佇列的話，需要兩個長度為

2^{k}

的 list，還要確定後面的元素個數達到

2^{k}

，這時可以確保差距不會超過

2^{k + 1}

：

2^{k}

= 2 : 1

$⟹$ : 表示合併

$2^{0}$
$2^{0}$ +
$2^{0}$ ( no merge )
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{0}$
$2^{1}$ +
$2^{0}$ +
$2^{0}$ ( no merge )
$2^{1}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{1}$ +
$2^{0}$
$2^{1}$ +
$2^{1}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{0}$ +
$2^{0}$
$2^{2}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{1}$ +
$2^{0}$

整理出以上合併原則試著帶入 count 進行歸納：

$2^{0}$
$\to$
count = 1 =
$1_{2}$
$\to$
$2^{0}$ +
$2^{0}$ ( no merge )
count = 2 =
$10_{2}$
$\to$
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{0}$ ( 需要 merge 出
$2^{1}$ )
count = 3 =
$11_{2}$
$\to$
$2^{1}$ +
$2^{0}$ +
$2^{0}$ ( no merge )
count = 4 =
$100_{2}$
$\to$
$2^{1}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{1}$ +
$2^{1}$ +
$2^{0}$ ( 需要 merge 出
$2^{1}$ )
count = 5 =
$101_{2}$
$\to$
$2^{1}$ +
$2^{1}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{0}$ +
$2^{0}$ ( 需要 merge 出
$2^{2}$ )
count = 6 =
$110_{2}$
$\to$
$2^{2}$ +
$2^{0}$ +
$2^{0}$ +
$2^{0}$
$⟹$
$2^{2}$ +
$2^{1}$ +
$2^{0}$ ( 需要 merge 出
$2^{1}$ )

for (bits = count; bits & 1; bits >>= 1)
tail = &(*tail)->prev;

可以觀察到需要 merge 出的大小可利用 count 的二進位數字的最小位元的位置計算出，透過以上程式碼中的 for 迴圈可以計算出 count 的最低位元，並且找到此輪要 merge 的兩個 list，並且利用 *tail 往 prev 走 k 步找到

2^{k}

大小的 list a

if (likely(bits)) {
    struct list_head *a = *tail, *b = a->prev;

    a = merge(priv, cmp, b, a);
    /* Install the merged result in place of the inputs */
    a->prev = b->prev;
    *tail = a;
}

而 *b = a->prev 可以找到另一個大小也為

2^{k}

的 list b ，並且將兩者合併。
另外，也可以發現到只有在 count 為

2^{k} - 1

的時候，不會有 merge 的動作。

    /* End of input; merge together all the pending lists. */
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;

        if (!next)
            break;
        list = merge(priv, cmp, pending, list);
        pending = next;
    }

接著輸入下一個元素：

/* Move one element from input list to pending */
list->prev = pending;
pending = list;
list = list->next;
pending->next = NULL;
count++;

沒有待輸入的元素的時候，將剩下的字串使用 merge 由大到小合併：

/* End of input; merge together all the pending lists. */
list = pending;
pending = pending->prev;
for (;;) {
    struct list_head *next = pending->prev;

    if (!next)
        break;
    list = merge(priv, cmp, pending, list);
    pending = next;
}

最後執行 merge_final 合併兩條子串列：

/* The final merge, rebuilding prev links */
merge_final(priv, cmp, head, pending, list);

留意各式細節，唯有重視小處並步步為營，方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心。及早更正上方的議題。

將 list_sort 引入到 lab0-c 專案

參考至 WangHanChi

將 list_sor.c 和 list_sort.h 加入至與 queue.c 相同層級的目錄中
修改 Makefile 中 OBJS，新增一個 list_sort.o

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

修改 qtest.c

加入 #include "list_sort.h"
設定變數決定是否使用 list_sort

static int use_list_sort = 0;

加入一個用來執行比較的函式

static int cmp(void* priv,
               const struct list_head *l1, 
               const struct list_head *l2)
{
    return strcmp(list_entry(l1, element_t, list)->value,
                  list_entry(l2, element_t, list)->value);
}

修改 do_sort中執行 sort 的部份，決定是否使用 list_sort

     if (current && exception_setup(true))
-        q_sort(current->q, descend);
+        use_list_sort ? list_sort(NULL, current->q, cmp)
+                      : q_sort(current->q, descend);
exception_cancel();

最後使用 add_param 將 listsort 指令加入到 help 選單中

add_param("listsort", &use_list_sort, 
          "Use the sort which is made by linux kernel developers", NULL);

安裝 perf

根據老師的安裝教學 perf 原理和實務即可順利安裝成功，特別要注意的是如果不是切換到 root 的情況下輸入

$ perf top

會出現以下錯誤畫面：

可以透過

$ cat /proc/sys/kernel/perf_event_paranoid

來獲取權限值。如果要將權限全開，用以下指令完成

$ sudo sh -c "echo -1 > /proc/sys/kernel/perf_event_paranoid"

用 perf 進行效能比較

開始比較 q_sort 與 list_sort 這兩個排序的效能差別，分別測試資料比數從 10 萬筆資料到 100 萬筆資料

資料數	q_sort	list_sort
100,000	0.034	0.031
200,000	0.111	0.108
300,000	0.187	0.179
400,000	0.268	0.267
500,000	0.366	0.354
600,000	0.434	0.428
700,000	0.526	0.522
800,000	0.643	0.609
900,000	0.706	0.694
1,000,000	0.810	0.783

項目	q_sort	list_sort
cache-misses	3,5196	3,4884
cache-references	13,6690	13,6938
% of all caches refs	25.75%	25.47%
instructions	160,8820	160,8588
cycles	197,2961	202,2427
insn per cycle	0.82	0.80

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

Timing Leakage Detection

執行 leakage detection test 測試兩筆不同資料的執行時間來檢查兩者的時間分佈是否具有顯著性的差異。

Step 1 : Measure execution time
針對屬於兩個不同資料類別的輸入，重複測量在加密函數 (cryptographic function) 的執行時間

a) Classes definition
採用 fix-vs-random tests，給定兩個不同的輸入資料
- 固定資料：經常選擇某些固定值來觸發 corner-case 的情形
- 隨機資料
b) Cycle counters
現在 CPU 提供 Cycle counters，可以準確的取得執行時間測量值。

c) Environmental conditions
為了減少環境變化對結果的影響，每次測量都對應於一個隨機選擇的類別
另外，類別分配和輸入準備任務在測量階段之前完成
Step 2 : Apply post-processing
可以對每個單獨的測量值進行一些後處理 (post-processing)

a) Cropping
典型的時序分佈在較長的執行時間中會呈現 positive skewness

這可能是由於測量誤差或主要的程序被 OS 或其他外部的無關活動中斷所引起的，在這種情況下可以裁剪掉測量值來避免誤差

b) Higher-order preprocessing
根據所應用的統計測試，應用一些高階預處理，例如 centered product、mimicking higher-order DPA attacks
Step 3 : Apply statistical test
利用統計測試來反駁虛無假說『兩個時間分佈相等』

a) Cropping
一個簡單的實作為 Welch’s t-test ，適用於且兩群體都為常態分布且變異數未知但不相同時。
當 t-test 與 Cropping preprocessing 結合時，不只是測試均值相等性，而且還測試更高階統計情境，因為 Cropping 是一種非線性轉換

b) Non-parametric tests
這些測試的優點是對於基本分佈的假設較少，缺點是他們可能收斂速度較慢並且需要更多樣本，例如 Kolmogorov-Smirnov

解釋 simulation 模式

首先在 qtest.c 可以看到 simulation 的三種模式

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;
    }

不需要 arguments
Probably not constant time
Probably constant time

Student's t-distribution 及程式實作原理

t = \frac{\bar{x_{1}} - \bar{x_{2}}}{\sqrt{\frac{s_{1}^{2}}{n_{1}} + \frac{s_{2}^{2}}{n_{2}}}}

假設 t 值越大則代表兩組資料的分佈差異越大，在 dudect/ttest.c 中由以下程式碼進行計算

double num = (ctx->mean[0] - ctx->mean[1]);
double den = sqrt(var[0] / ctx->n[0] + var[1] / ctx->n[1]);
double t_value = num / den;

fixture.c 中的 report 函式計算出 t 值

double max_t = fabs(t_compute(t));

最後量測是否為 constant time

/* Definitely not constant time */
if (max_t > t_threshold_bananas)
    return false;

/* Probably not constant time. */
if (max_t > t_threshold_moderate)
    return false;

/* For the moment, maybe constant time. */
return true;

修改程式以達成 constant time

commit

參考 chiangkd

根據 dudect.h 在 lab0-c 也加入 percentile 的處理，但是在 dudect.h 中有定義 dudect_ctx_t 結構體將所有資訊定義在一起，包括執行時間、輸入資料、類別等，而 lab0-c 中沒有

typedef struct {
  int64_t *ticks;
  int64_t *exec_times;
  uint8_t *input_data;
  uint8_t *classes;
  dudect_config_t *config;
  ttest_ctx_t *ttest_ctxs[DUDECT_TESTS];
  int64_t *percentiles;
} dudect_ctx_t;

所以另外要在 t_context_t 中定義 int64_t *percentiles

typedef struct {
    double mean[2];
    double m2[2];
    double n[2];
    int64_t *percentiles;
} t_context_t;

觀察論文和實際操作的程式碼

在 Dude, is my code constant time?〉提到以下：

Pre-processing: We pre-process measurements prior to
statistical processing. We discard measurements that are larger than the p percentile, for various values of p. The rationale here is to test a restricted distribution range, especially the lower cycle count tail. The upper tail may be more influenced by data-independent noise. This (heuristic) process gives good
empirical results (makes detection faster); nevertheless we also process measurements without pre-processing.

這邊的操作主要是為了把極端值去除，其中在 dudect.h 實際計算的公式為：

f (i) = 1 - {0.5}^{10 \cdot \frac{i + 1}{N}}

接下來將這個公式使用 python 畫出來，其中 x 軸代表的是

i

分別為 0-99 的值，而 y 軸則為對應

i

值使用上述公式計算出來的

f (i)

可以看到這個公式收斂到 1 的速度很快，當 i 為 33 時

f (33) = 1 - {0.5}^{10 \cdot \frac{33 + 1}{N}} \approx 0.905

代表 i 為 33 以後所取的都是剩下的大於 0.9 的

指出程式碼和論文描述的出入之處。

在 `qtest` 提供新的命令 `shuffle`

commit 69db7e5

使用你 fork 之後得到的 git repository 對應的超連結。

Fisher–Yates shuffle

舉例 1~5 的 shuffle 過程
每次都從原始數據中選出一個隨機數放到尾端，直到所有的數字都被取出

隨機數取值 index 範圍	隨機數	原始數據	結果
		12345
0~4	4 (index = 3)	1235	4
0~3	2 (index = 1)	135	24
0~2	1 (index = 0)	35	124
0~1	5 (index = 1)	3	5124

實作方法是利用 rand_idx 每次都在指定的範圍內取出隨機數在佇列中的索引，再來透過 for 迴圈去找出該索引所指到的節點，最後利用 list_del 改變鏈結關係後再用 list_add_tail 加入到原始數據的尾端

void q_shuffle(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head))
        return;
    int size = q_size(head);
    struct list_head *tmp = head;
    for (int i = size; i > 1; i--) {
        int rand_idx = rand() % i;
        struct list_head *rand_num = head;
        for (int j = 0; j <= rand_idx; j++)
            rand_num = rand_num->next;
        list_del(rand_num);
        list_add_tail(rand_num, tmp);
        tmp = tmp->prev;
    }
    return;
}

另外，也需要在 qtest.c 中定義 shuffle 的命令，其中在撰寫 do_shuffle 時參考 do_swap 的寫法，而且因為無法更改 list.h 的內容，所以將 void q_shuffle(struct list_head *head); 定義在 do_shuffle 之前。

使用 Valgrind 排除記憶體錯誤

根據以 Valgrind 分析記憶體問題執行命令 make valgrind ，檢查是否存在記憶體錯誤。
檢查出來的結果如下，看起來都是相同問題，所以只擷取部份內容

==6123== 72,800 bytes in 91 blocks are definitely lost in loss record 4 of 4
==6123==    at 0x484DA83: calloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==6123==    by 0x110BE0: doit (fixture.c:163)
==6123==    by 0x110BE0: test_const (fixture.c:209)
==6123==    by 0x110DA1: is_remove_tail_const (fixture.c:225)
==6123==    by 0x10C55A: queue_remove (qtest.c:313)
==6123==    by 0x10C9D1: do_rt (qtest.c:426)
==6123==    by 0x10E13E: interpret_cmda (console.c:181)
==6123==    by 0x10E6F3: interpret_cmd (console.c:201)
==6123==    by 0x10EAF4: cmd_select (console.c:610)
==6123==    by 0x10F3E0: run_console (console.c:705)
==6123==    by 0x10D530: main (qtest.c:1301)

根據教材可看到 memory lost 分成幾種類型：

definitely lost : 真的 memory leak
indirectly lost : 間接的 memory leak，structure 本身發生 memory leak，而內部的 member 如果是 allocate 的出來的，一樣會 memory leak
possibly lost : allocate 一塊記憶體，並且放到指標 ptr，但事後又改變 ptr 指到這塊記憶體的中間
still reachable: 程式結束時有未釋放的記憶體，不過卻還有指標指著，通常會發生在 global 變數，即便是在所用的函式庫裡頭配置的記憶體，也可偵測到，這也是動態分析手法的優勢。

後來去檢查 doit 才發現之前在定義 t->percentiles 時使用 calloc 動態分配記憶體時忘記釋放，因此修改下列程式。

free(before_ticks);
free(after_ticks);
free(exec_times);
free(classes);
free(input_data);
+free(t->percentiles);

return ret;

再執行一次 make valgrind 後問題就解決了。

+++ 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

透過 Massif 分析記憶體使用量

在 valgrind 使用的參數列表中加入 --tool=massif

$ valgrind --tool=massif ./qtest -f traces/trace-17-complexity.cmd

之後可以在檔案中找到一張 massif.out.XXXXX，接著輸入

$ massif-visualizer massif.out.XXXXX

就可以獲得 Massif 所分析在執行 traces/trace-17-complexity.cmd 的記憶體使用量圖表了

接下來分析執行以下測試項目時的記憶體使用量

option simulation 1
it
option simulation 0

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

參考 WangHanChi
相較於 valgrind ，Address Sanitizer 適用對於記憶體錯誤進行更快速的檢測，在 Makefile 可以看到以下規則：

# Enable sanitizer(s) or not
ifeq ("$(SANITIZER)","1")
    # https://github.com/google/sanitizers/wiki/AddressSanitizerFlags
    CFLAGS += -fsanitize=address -fno-omit-frame-pointer -fno-common
    LDFLAGS += -fsanitize=address
endif

所以只需要輸入 make SANITIZER=1 就可以直接使用，不過要特別注意的是，Anitizer 與 Valgrind 是不可以同時使用的，所以在執行前要先 make clean 清除之前編譯的內容。

改進授課教師要求更正的地方。

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

本筆記的標題不符合規範。

分析 List_sort 和 Timsort

參考筆記：vax-r

commit 41c3f48

使用 Timsort 提供的 main.c 檔，測試看看資料數 10-100000 筆時，timesort 和 list_sort 各自的 CPU Clock Elapsed 以及 Comparisons 的表現

首先是在資料呈現隨機分佈的時候，使用 rand() 建立隨機資料

Creating sample
==== Testing timesort for SAMPLES = 10 ====
  CPU Clock Elapsed : 0.000000 seconds
  Comparisons:    26
  List is sorted
==== Testing list_sort for SAMPLES = 10 ====
  CPU Clock Elapsed : 0.000000 seconds
  Comparisons:    21
  List is sorted
Creating sample
==== Testing timesort for SAMPLES = 100 ====
  CPU Clock Elapsed : 0.000003 seconds
  Comparisons:    586
  List is sorted
==== Testing list_sort for SAMPLES = 100 ====
  CPU Clock Elapsed : 0.000002 seconds
  Comparisons:    543
  List is sorted
Creating sample
==== Testing timesort for SAMPLES = 1000 ====
  CPU Clock Elapsed : 0.000048 seconds
  Comparisons:    10072
  List is sorted
==== Testing list_sort for SAMPLES = 1000 ====
  CPU Clock Elapsed : 0.000046 seconds
  Comparisons:    8693
  List is sorted
Creating sample
==== Testing timesort for SAMPLES = 10000 ====
  CPU Clock Elapsed : 0.000704 seconds
  Comparisons:    135965
  List is sorted
==== Testing list_sort for SAMPLES = 10000 ====
  CPU Clock Elapsed : 0.000679 seconds
  Comparisons:    121006
  List is sorted
Creating sample
==== Testing timesort for SAMPLES = 100000 ====
  CPU Clock Elapsed : 0.010123 seconds
  Comparisons:    1681266
  List is sorted
==== Testing list_sort for SAMPLES = 100000 ====
  CPU Clock Elapsed : 0.009377 seconds
  Comparisons:    1542859
  List is sorted
Creating sample
==== Testing timesort for SAMPLES = 1000000 ====
  CPU Clock Elapsed : 0.180587 seconds
  Comparisons:    20362814
  List is sorted
==== Testing list_sort for SAMPLES = 1000000 ====
  CPU Clock Elapsed : 0.149971 seconds
  Comparisons:    18687079
  List is sorted

根據以上實驗結果可以發現 list_sort 和 timsort 皆不會在任一個特定的資料量大小表現特別優秀，因此以下實驗皆以資料量 10000 進行比較實驗

再來比較看看資料分佈皆為升序的結果，這邊不比較降序的原因是，在 timsort 操作 findrun() 時，會將找到的 run 進行反轉

Creating sample
==== Testing timesort ====
  CPU Clock Elapsed : 0.000028 seconds
  Comparisons:    9999
  List is sorted
==== Testing list_sort ====
  CPU Clock Elapsed : 0.000169 seconds
  Comparisons:    65344
  List is sorted

3.最後比較資料分佈為 worse case 的情況，以 timsort 來看，worse case 則是在資料升序降序反覆的時候 ，例如 [ 1，4，3，5，2，6 ] 因為此時 timsort 所計算出來的 run 數最多，而當 run 數變多時，就需要更多的比較和合併的時間

Creating sample
==== Testing timesort ====
  CPU Clock Elapsed : 0.000654 seconds
  Comparisons:    128818
  List is sorted
==== Testing list_sort ====
  CPU Clock Elapsed : 0.000636 seconds
  Comparisons:    121133
  List is sorted

探討不同的資料分布對於排序演算法的影響。

結論：

根據實驗結果我們可以發現在資料分佈為 rand() 和 worse case 的時候 list sort 的表現都是優於 timsort 的，而在資料為排序好的情況時，timsort 就會明顯比 list sort 還要來的好，這個實驗結果的原因我覺得是因為 list sort 在決定合併與否不會受到資料的實際大小的影響，而 timsort 則是會在 findrun() 時就會因為資料的實際分佈而影響到 run 的數量，例如在 worse case 就會因為 run 數很多而需要逐一比對數量再進行合併

tic-tac-toe

jserv/ttt 專案提供可跟電腦對弈的互動環境，並且提供多種對弈時的演算法，因為不理解遊戲進行的流程，在理解演算法之前，先對程式碼進行初步的理解之後才能順利將遊戲整合至 lab0-c 中

文字訊息不要用圖片展現

check_win ：判斷棋盤上贏家，若是平手則會回傳 D
draw_board ：畫出棋盤
record_move ：紀錄每一步選擇的位置到 static int move_record[N_GRIDS] 中
get_input ：獲取使用者的移動位置
print_moves ：印出所有使用者和 AI 移動的位置

使用以上函式完成操作，並且定義一個 char table[N_GRIDS] 紀錄目前棋盤上的遊戲畫面，並且每次都使用 draw_board(table) 顯示畫面

if (turn == ai) {
        int move = mcts(table, ai);
        if (move != -1) {
            table[move] = ai;
            record_move(move);
        }
    }

如果此時為 ai 的輪次，會使用演算法(這邊使用 Monte Carlo Tree Search )去計算出 ai 下一個要移動的位置，接下來將 move 存到 table 和 move_record 中
反之如果是使用者輪次，則用 get_input 紀錄下一步位置並且一樣存到 table 和 move_record 中

turn = turn == 'X' ? 'O' : 'X';

最後使用此判斷式更換輪次

支援 MCTS AI 的 tic-tac-toe 程式碼：efc314f

Monte Carlo Tree Search

參考 Monte Carlo Tree Search 解說

模擬進行幾次遊戲，將遊戲的結果紀錄在一個 tree 裡，再根據最後模擬的結果來選擇最好的動作
步驟：

Selection ：選擇要對 tree 上的那一個 node 進行更新，在 Select 時只會選擇 leaf node (沒有 chlidren 的 node)
Expand or Rollout
(目前節點為全新的就進行 Rollout，若已經更新過則進行 Expand )

Expansion : 對某一個節點往下產生新的子節點
Simulation ：以目前的狀態開始完成一次對局的模擬

Backpropagation ：將節點沿著原路一直往上傳直到達到 root 為止，並且更新此路線上節點的權重

在 Selection 的步驟中，會使用 UCB (Upper Confidence Bound) 給於節點權重，並且以 UCB 的值決定要選擇的節點

\frac{w_{i}}{n_{i}} + c \sqrt{\frac{l n (N_{i})}{n_{i}}}

$w_{i}$ 代表目前該節點贏的次數
$n_{i}$ 代表目前該節點總共進行的模擬次數
$N_{i}$ 代表該節點的父節點總共進行的模擬次數
$c$ 可自行調整的常數，通常定為
$\sqrt{2}$

公式的前一項代表 exploitation ，可以使公式獲得目前已知最好策略的資訊，而公式的後一項代表的則是 exploration ，也就是探索其他策略，exploitation 和 exploration 需要達到良好的平衡，才能在選擇的時候不是只有選擇目前最好的策略而不去探索別的路線，或是只探索勝率很低的路線而導致效率太差

定點數

先觀察 Monte Carlo Tree Search 的實作中需要由浮點數轉換成定點數的地方有哪些

score 的宣告
原始宣告為 double，這邊改為 uint64_t
simulate 函式中若為平手會 return 0.5
浮點數 0.5 的定點數相當於將 1ULL 往左移縮放位元 - 1 個位置
calculate_win_value 函式中的 return 值

double calculate_win_value(char win, char player)
{
    if (win == player)
-       return 1.0;
+       return 1ULL << FIXED_SCALING_BITS;
    if (win == (player ^ 'O' ^ 'X'))
-       return 0.0;
+       return 0ULL;
-   return 0.5;
+   return 1ULL << (FIXED_SCALING_BITS - 1);
}

uct_score 的計算

score / n_visits +
           EXPLORATION_FACTOR * sqrt(log(n_total) / n_visits);

sqrt 改為定點數計算

參考 SuNsHiNe-75

此函示採用二分法，假設我們的目標要計算出

x \approx \sqrt{n}

中的

x

，將兩邊分別平方後會得到

x^{2} \approx n

，也就是需要找出

x

使得

x^{2}

逼近

n

實作流程:

先將左右兩邊區間 ( left，right ) 設為 0ULL 和 n (其中 n 為定點數)
以 fixed_power_int(mid,2) 計算出
$m i d^{2}$ 並且判斷是否大於
$n$
- 大於 : 改變區間 ( left，right ) 為 ( left，mid )
- 小於 : 改變區間 ( left，right ) 為 ( mid，right )
計算 left 和 right 的中心點為 mid
以 abs(mid-last) > eps 判斷上次的 mid 和這次算出來的 mid 差距是否小於 eps，若小於則結束逼近，大於則回到步驟 2 繼續進行判斷，其中 eps 設定為 1ULL，而 mid 和 last 都是以定點數進行表示
最後 return mid

實驗時會用以下巨集將定點數轉回浮點數，其中 LOAD_INT 是算出整數部分，而 LOAD_FRAC 是算出小數部份

#define FIXED_1 (1<<FIXED_SCALING_BITS)
#define LOAD_INT(x) ((x) >> FIXED_SCALING_BITS)
#define LOAD_FRAC(x)                                                           \
  ((double)((x) & (FIXED_1 - 1))) / ((double)(1 << FIXED_SCALING_BITS))

以下為使用二分法找出近似於

\sqrt{n}

的實驗結果

另外，剛開始的實驗的時候因為初始化的區間設定在 ( left，right ) = ( 1ULL，n )，而

x

介於 0 到 1 之間時，

\sqrt{n}

的數值會大於

n

，所以假設不調整初始化的區間，在介於 0 到 1 區間時，

\sqrt{n}

的結果最多只能為 n，如下圖

所以需要在程式碼中預先判斷是否介於 0 到 1 之間，如果是就需要調整初始化的區間到 ( left，right ) = (n，1ULL << FIXED_SCALING_BITS)，經過調整後誤差值降低了很多

sqrt 以定點數計算程式碼：

uint64_t fixed_sqrt(uint64_t n) 
{
  uint64_t eps = 1ULL;
  uint64_t left = 0ULL;
  uint64_t right = n;
  uint64_t mid = 0;
  uint64_t last; 
  if (n < 0)
    return 0;
  if (n < (1 << FIXED_SCALING_BITS)) {
    left = n;
    right = 1ULL << FIXED_SCALING_BITS;
    mid = n;
  }
  do {
    if (fixed_power_int(mid, 2) > n) 
      right = mid;
    else
      left = mid;

    last = mid;

    mid = left + ((right - left) / 2);

  } while (abs(mid - last) > eps); 
  return mid;
}

log 改為定點數計算

此函式的作法一樣採用二分法逼近，但是現在我們的目標是要計算出

\ln n = x

，也就是

e^{x} = n

，所以一樣逐步逼近，找出對應的

x

數學方法：

用區間

e^{s}

和

e^{d}

逐步逼近 n
每次迭代都去計算出

\sqrt{e^{s + d}} = e^{\frac{s + d}{2}}

並判斷 n 落在 (

e^{\frac{s + d}{2}}

，right ) 還是 ( left，

e^{\frac{s + d}{2}}

）以改變下次區間

實作流程：

在定義初始化區間( left，right )之前先定義出次方的值，其中 d 利用 (31 - __builtin_clz(n | 1) + 1 找出 n 最高位元 bit 的位置 + 1，之後扣掉設定好的縮放位元是因為 n 為定點數，最後需要再 << FIXED_SCALING_BITS 轉成定點數儲存
例如
$n$ 為
$23$ 的定點數，先算出最高位元 + 1 為
$16 + 1 = 17$ ，扣掉縮放位元 12 後為 5 ，最後再轉成定點數儲存，原因是
$n = 23$ 的最高區間不會超過
$e^{5}$

uint64_t s = 1 << FIXED_SCALING_BITS;
uint64_t d = ((31 - __builtin_clz(n | 1)) + 1 - FIXED_SCALING_BITS )
                    << FIXED_SCALING_BITS;

設定初始化區間( left，right )為
$e^{s}$ 和
$e^{d}$ 的定點數，因為初始化時
$s$ 和
$d$ 都是用定點數表示的整數，所以可以使用 fixed_power_int 進行計算

uint64_t left = fixed_power_int(e, s >> FIXED_SCALING_BITS);
uint64_t right = fixed_power_int(e, d >> FIXED_SCALING_BITS);

判斷新區間為( left，mid )還是( mid，right )
計算 mid 為
$\sqrt{e^{s + d}}$ ，並且儲存
$\frac{s + d}{2}$ 到 expp 中
以 abs(mid-last) > eps 判斷上次的 mid 和這次算出來的 mid 差距是否小於 eps，若小於則結束逼近，大於則回到步驟 3
最後 return expp，也就是
$e^{x} \approx n$ 中的近似值
$x$

log 以定點數計算程式碼：

uint64_t fixed_log(uint64_t n)
{
  uint64_t eps = 1ULL;
  uint64_t e = (uint64_t)(2.71828 * (1 << FIXED_SCALING_BITS)); // e = 11134
  uint64_t s = 1 << FIXED_SCALING_BITS;
  uint64_t d = ((31 - __builtin_clz(n | 1)) - FIXED_SCALING_BITS + 1)
                        << FIXED_SCALING_BITS;
  uint64_t left = fixed_power_int(e, s >> FIXED_SCALING_BITS);
  uint64_t right = fixed_power_int(e, d >> FIXED_SCALING_BITS);
  uint64_t mid = left;
  uint64_t last;
  uint64_t expp = s;

  if (n < 1)
    return 0;
  do {
    if (mid > n) {
      right = mid;
      d = expp;
    } else {
      left = mid;
      s = expp;
    }

    last = mid;
    mid = mysqrt_2((left * right) >> FIXED_SCALING_BITS);
    expp = (s + d) / 2;

  } while (abs(mid - last) > eps);
  return expp;
}

實驗結果：

測試

\ln x

的

x

大於 1000 時的結果：

2024q1 Homework1 (lab0)

Reviewed by david965154

開發環境

佇列實作與改進

q_new

q_free

q_free 的程式碼：

q_insert_head

q_insert_head 的程式碼：

q_insert_tail

q_remove_head

q_remove_head 的程式碼

q_remove_tail

q_size

q_delete_mid

q_delete_mid的程式碼：

q_delete_dup

q_delete_dup 的程式碼

q_swap

q_swap 的程式碼

q_reverse

q_reverse的程式碼：

q_reverseK

q_sort

mergeTwoLists 的原始程式碼：

q_sort的程式碼：

q_ascend

q_ascend的程式碼：

q_descend

q_merge

q_merge的程式碼：

研讀 Linux 核心原始程式碼的 list_sort

將 list_sort 引入到 lab0-c 專案

參考至 WangHanChi

安裝 perf

用 perf 進行效能比較

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

Timing Leakage Detection

解釋 simulation 模式

Student's t-distribution 及程式實作原理

修改程式以達成 constant time

觀察論文和實際操作的程式碼

在 qtest 提供新的命令 shuffle

使用 Valgrind 排除記憶體錯誤

透過 Massif 分析記憶體使用量

開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤

分析 List_sort 和 Timsort

結論：

tic-tac-toe

Monte Carlo Tree Search

定點數

sqrt 改為定點數計算

實作流程:

sqrt 以定點數計算程式碼：

log 改為定點數計算

數學方法：

實作流程：

log 以定點數計算程式碼：

實驗結果：

Read more

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

2024q1 Homework2 (quiz1+2)

Reviewed by `david965154`

`q_new`

在 `qtest` 提供新的命令 `shuffle`