# 2024q1 Homework1 (lab0)
contributed by < `slipet` >
:::danger
移除 `</details>`，開發紀錄的存在是讓他人更容易理解你所作所為，從而協同開發，但過多的 `</details>` 只是增加編輯的難度。
:::
## 開發環境
```
$ gcc --version
gcc (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
$lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 48 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 5600X 6-Core Processor
CPU family: 25
Model: 33
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 0
Frequency boost: enabled
CPU max MHz: 4650.2920
CPU min MHz: 2200.0000
BogoMIPS: 7399.64
```
## 改進 `queue.c`
### `q_new`
> commit: [629656](https://github.com/sysprog21/lab0-c/commit/6296564ce31abd17e69e83dd2ec55106d9a73699)
將記憶體<s>分配</s> 配置給指標 `q` 後檢查是否成功配置記憶體，並且使用`ININT_LIST_HEAD` 將 `q->next` 和 `q->prev` 指向自身。
:::warning
allocate 翻譯為「配置」，而非「分配」，是為了跟「分發」(dispatch) 區隔，二者都會在作業系統領域多次出現。
:::
### `q_insert_head` and `q_insert_tail`
```
$ sed -n '/bool q_insert_head/,/^\}/p' queue.c > q_insert_head.tmp
$ sed -n '/bool q_insert_tail/,/^\}/p' queue.c > q_insert_tail.tmp
$ diff q_insert_head.tmp q_insert_tail.tmp
... ...
13c13
< list_add(&new_element->list, head);
---
> list_add_tail(&new_element->list, head);
```
利用 `diff` 命令，我們能分辨出 [q_insert_head](https://github.com/sysprog21/lab0-c/commit/b3da17e944943f374e7f82444225008bd84c3dce) 和 [q_insert_tail](https://github.com/sysprog21/lab0-c/commit/d5e373d953bb66b8e1c8daa6d71f701cd25989a1) 分別使用了不同的插入函式。
:::warning
使用 `diff -u`
:::
當我們在 `head->prev` 位置利用 `list_add` 函式插入元素時，這一操作實際上與使用 `list_add_tail` 函式達到的插入效果相同。
因此，透過統一採用 [q_insert](https://github.com/sysprog21/lab0-c/commit/baf00e902cfaddb9c5fc0b85d736bcd8e0cd9b03) 函式來統一這兩種插入操作，從而減少程式碼的重複性。
### `q_remove_head` and `q_remove_tail`
原本想重用之前寫過的程式碼，但這次想嘗試讓程式碼更簡潔，因此參考 [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax) 定義了一個 [MIN](https://github.com/sysprog21/lab0-c/commit/309ee17a54964dff6ecf69fc1c3fe2afb9fe6d8a) 的巨集，被複製的字串長度最多不會超過 `bufsize - 1`，預留一個空間的用意是為了放置字串的結束字元 `\0`。
```diff
- size_t len = strlen(del->value);
- len = (len + 1 > bufsize) ? bufsize : len + 1;
- strncpy(sp, del->value, bufsize);
- sp[len - 1] = '\0';
+ /* Bufsize reserves space for a null terminator.*/
+ size_t len = MIN(strlen(del->value), bufsize - 1);
+ strncpy(sp, del->value, len);
+ sp[len + 1] = '\0';
```
但是上述的程式碼在第一個測試案例會出現錯誤。
```
+++ TESTING trace trace-01-ops:
# Test of insert_head and remove_head
ERROR: Removed value dolphinX != expected value dolphin
ERROR: Removed value bearX != expected value bear
...
```
被移除的字串並沒有正確的複製到 `sp` ，因為結尾都是 `X`，在 `qtest.c` 的 `queue_remove()` 可以發現測試程式會事先在 `removes` 填入 `X` ，透過檢查 `[string_length + 1, string_length + STRINGPAD)` 區間的字元判斷記憶體操作是否有越界。
```c
memset(removes + 1, 'X', string_length + STRINGPAD - 1);
```
我推測是 `sp[len + 1] = '\0';` 寫錯了， `strncpy` 複製長度 len 的字串填入 `\0` 的位置應該是 `sp[len]` 。
```diff
- sp[len + 1] = '\0';
+ sp[len] = '\0';
```
修改後可以通過第一個測試案例。
最後，與 `q_insert` 相同，採用 [q_remove](https://github.com/sysprog21/lab0-c/commit/085036867cd436c92bd93b4de5e329643e853032) 函式統一這兩種移除操作，減少重複的程式碼。
### `q_delete_mid`
[分析「快慢指標」](https://hackmd.io/@sysprog/ry8NwAMvT) 裡討論了兩種實作方式 (1) 單一節點走訪 (2) 快慢指標，兩者的時間複雜度皆為 $O(n)$，需要存取 $O(\frac3{2}n)$ 個節點的記憶體位置。
這裡我想嘗試"從頭尾兩端相向前進"的方式來刪除中間的節點，具體方法為從頭尾兩端相向走訪，最後會在中間相遇，時間複雜度為 $O(\frac{n}{2})$，走訪的節點數 $O(n)$，與上述兩者相比要少 $\frac{1}{3}$。
```c
bool q_delete_mid(struct list_head *head)
{
if (head == NULL || list_empty(head))
return false;
struct list_head **iter = &head;
struct list_head *tail = head->prev;
while ((*iter) != tail && (*iter)->next != tail) {
iter = &(*iter)->next;
tail = tail->prev;
}
struct list_head *del = (*iter)->next;
list_del(del);
q_release_element(container_of(del, element_t, list));
return true;
}
```
在 `Makefile` 中修改編譯選項 <s>旗標</s>，分別採用 `-O0` 和 `-O3` 兩種最佳化等級來編譯，得到的組合語言分別為 53 行和 41 行。可以觀察到，由於對 `list_empty` 函式的聲明中加入`inline` 關鍵字，在 `-O3` 最佳化等級下（第 4、5 行）可以直接將程式碼展開，而不需要像在 -O0 等級（第 11、12 行）那樣進行函式呼叫。此外，在 `-O0` 最佳化等級下發現了對 `list_del` 和 `q_release_element` 的呼叫，但在 `-O3` 下則未見這些呼叫，推測這與 `list_empty` 一樣，已經被編譯器進行了最佳化。
- [ ] `-O0`
```diff
45a: f3 0f 1e fa endbr64
45e: 55 push %rbp
45f: 48 89 e5 mov %rsp,%rbp
462: 48 83 ec 30 sub $0x30,%rsp
466: 48 89 7d d8 mov %rdi,-0x28(%rbp)
46a: 48 8b 45 d8 mov -0x28(%rbp),%rax
+ 46e: 48 85 c0 test %rax,%rax // head == NULL
+ 471: 74 10 je 483 <q_delete_mid+0x29> // 如果 head 為 NULL 跳到 483
473: 48 8b 45 d8 mov -0x28(%rbp),%rax
477: 48 89 c7 mov %rax,%rdi
+ 47a: e8 4c fc ff ff call cb <list_empty> 呼叫 list_empty
+ 47f: 85 c0 test %eax,%eax // 確認 list_empty 的回傳值
+ 481: 74 0a je 48d <q_delete_mid+0x33> // 如果 回傳值為 0 跳到 48d
+ 483: b8 00 00 00 00 mov $0x0,%eax //把 false 搬到 %eax
+ 488: e9 85 00 00 00 jmp 512 <q_delete_mid+0xb8> // 跳到 return => 512
48d: 48 8d 45 d8 lea -0x28(%rbp),%rax
491: 48 89 45 e0 mov %rax,-0x20(%rbp)
495: 48 8b 45 d8 mov -0x28(%rbp),%rax
499: 48 8b 00 mov (%rax),%rax
49c: 48 89 45 e8 mov %rax,-0x18(%rbp)
4a0: eb 1a jmp 4bc <q_delete_mid+0x62>
+ 4a2: 48 8b 45 e0 mov -0x20(%rbp),%rax // while-loop body start
4a6: 48 8b 00 mov (%rax),%rax
4a9: 48 83 c0 08 add $0x8,%rax
4ad: 48 89 45 e0 mov %rax,-0x20(%rbp)
4b1: 48 8b 45 e8 mov -0x18(%rbp),%rax
4b5: 48 8b 00 mov (%rax),%rax
4b8: 48 89 45 e8 mov %rax,-0x18(%rbp)
4bc: 48 8b 45 e0 mov -0x20(%rbp),%rax
4c0: 48 8b 00 mov (%rax),%rax
+ 4c3: 48 39 45 e8 cmp %rax,-0x18(%rbp) //(*iter) != tail
+ 4c7: 74 11 je 4da <q_delete_mid+0x80> // 如果等於成立跳到 4da
4c9: 48 8b 45 e0 mov -0x20(%rbp),%rax
4cd: 48 8b 00 mov (%rax),%rax
4d0: 48 8b 40 08 mov 0x8(%rax),%rax
+ 4d4: 48 39 45 e8 cmp %rax,-0x18(%rbp) // (*iter)->next != tail
+ 4d8: 75 c8 jne 4a2 <q_delete_mid+0x48> // 如果不等於成立 跳到 4a2
4da: 48 8b 45 e0 mov -0x20(%rbp),%rax
4de: 48 8b 00 mov (%rax),%rax
4e1: 48 8b 40 08 mov 0x8(%rax),%rax
4e5: 48 89 45 f0 mov %rax,-0x10(%rbp)
4e9: 48 8b 45 f0 mov -0x10(%rbp),%rax
4ed: 48 89 c7 mov %rax,%rdi
+ 4f0: e8 76 fb ff ff call 6b <list_del> // 呼叫 list_del
4f5: 48 8b 45 f0 mov -0x10(%rbp),%rax
4f9: 48 89 45 f8 mov %rax,-0x8(%rbp)
4fd: 48 8b 45 f8 mov -0x8(%rbp),%rax
501: 48 83 e8 08 sub $0x8,%rax
505: 48 89 c7 mov %rax,%rdi
+ 508: e8 da fb ff ff call e7 <q_release_element> // 呼叫 q_release_element
50d: b8 01 00 00 00 mov $0x1,%eax
512: c9 leave
+ 513: c3 ret
```
- [ ] `-O3`
```diff
380: f3 0f 1e fa endbr64
+ 384: 48 85 ff test %rdi,%rdi //檢查指標 head 是否為 0
+ 387: 74 57 je 3e0 <q_delete_mid+0x60> // 如果為 0 跳到 3e0
+ 389: 48 8b 47 08 mov 0x8(%rdi),%rax // head->next
+ 38d: 48 39 c7 cmp %rax,%rdi // head->next == head
+ 390: 74 4e je 3e0 <q_delete_mid+0x60> // 如果為 0 跳到 3e0
392: 53 push %rbx
393: 48 8b 1f mov (%rdi),%rbx
+ 396: 48 39 df cmp %rbx,%rdi //(*iter) != tail
+ 399: 75 11 jne 3ac <q_delete_mid+0x2c> //如果不等於跳到 3ac
39b: eb 51 jmp 3ee <q_delete_mid+0x6e>
39d: 0f 1f 00 nopl (%rax)
3a0: 48 8b 1b mov (%rbx),%rbx
3a3: 48 39 d8 cmp %rbx,%rax
3a6: 74 40 je 3e8 <q_delete_mid+0x68>
3a8: 48 8b 40 08 mov 0x8(%rax),%rax
+ 3ac: 48 39 d8 cmp %rbx,%rax //(*iter)->next != tail)
+ 3af: 75 ef jne 3a0 <q_delete_mid+0x20> // 如果不等於跳到 3a0
3b1: 48 8b 03 mov (%rbx),%rax
3b4: 48 8b 53 08 mov 0x8(%rbx),%rdx
3b8: 48 8b 7b f8 mov -0x8(%rbx),%rdi
3bc: 48 89 02 mov %rax,(%rdx)
3bf: 48 89 50 08 mov %rdx,0x8(%rax)
3c3: e8 00 00 00 00 call 3c8 <q_delete_mid+0x48>
3c8: 48 8d 7b f8 lea -0x8(%rbx),%rdi
3cc: e8 00 00 00 00 call 3d1 <q_delete_mid+0x51>
3d1: b8 01 00 00 00 mov $0x1,%eax
3d6: 5b pop %rbx
+ 3d7: c3 ret
3d8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
3df: 00
3e0: 31 c0 xor %eax,%eax
+ 3e2: c3 ret
3e3: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
3e8: 48 8b 5b 08 mov 0x8(%rbx),%rbx
3ec: eb c3 jmp 3b1 <q_delete_mid+0x31>
3ee: 48 89 c3 mov %rax,%rbx
3f1: eb be jmp 3b1 <q_delete_mid+0x31>
3f3: 66 66 2e 0f 1f 84 00 data16 cs nopw 0x0(%rax,%rax,1)
3fa: 00 00 00 00
3fe: 66 90 xchg %ax,%ax
```
:::danger
去閱讀 Intel 指令集手冊，而非毫無權威可言的 ChatGPT!
為何要捨近求遠呢？
:::
TODO:設計實驗比較文章裡的兩種方法跟我的方法，速度，快取錯失 (cache miss)，要注意實驗的資料量。
### `q_delete_dup`
使用 `list_for_each_entry_safe` 迭代檢查 `entry` 和 `safe` 是否相等，若是相等則進入 `while` 迴圈將重複的元素刪除。實作完成後測試程式碼時出現 `Segmentation fault` 。
```
Segmentation fault occurred. You dereferenced a NULL or invalid pointerAborted (core dumped)
```
```c
bool q_delete_dup(struct list_head *head)
{
if (head == NULL || list_empty(head) || list_is_singular(head))
return false;
element_t *entry = NULL, *safe = NULL;
list_for_each_entry_safe (entry, safe, head, list) {
if (strcmp(entry->value, safe->value) == 0) {
element_t *del;
while (&safe->list != head &&
strcmp(entry->value, safe->value) == 0) {
del = safe;
safe = list_entry(safe->list.next, element_t, list);
list_del_init(&(del->list));
q_release_element(del);
}
list_del_init(&entry->list);
q_release_element(entry);
}
}
return true;
}
```
使用 valgrind 觀察錯誤發生時的訊息:
```
$ valgrind ./qtest -f traces/trace-18-dedup.cmd
# Test of insert_head and remove_head
l = []
l = [a]
l = [aa a]
l = [z aa a]
==39771== Invalid read of size 1
==39771== at 0x484FBD7: strcmp (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39771== by 0x10FAF9: q_delete_dup (queue.c:138)
==39771== by 0x10C081: do_dedup (qtest.c:465)
==39771== by 0x10E02E: interpret_cmda (console.c:181)
==39771== by 0x10E5DF: interpret_cmd (console.c:201)
==39771== by 0x10E9E0: cmd_select (console.c:610)
==39771== by 0x10F2BE: run_console (console.c:705)
==39771== by 0x10D420: main (qtest.c:1258)
==39771== Address 0xdeadbeef is not stack'd, malloc'd or (recently) free'd
==39771==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer==39771== 2 bytes in 1 blocks are still reachable in loss record 1 of 48
==39771== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==39771== by 0x10BEF5: do_dedup (qtest.c:442)
==39771== by 0x10E02E: interpret_cmda (console.c:181)
==39771== by 0x10E5DF: interpret_cmd (console.c:201)
==39771== by 0x10E9E0: cmd_select (console.c:610)
==39771== by 0x10F2BE: run_console (console.c:705)
==39771== by 0x10D420: main (qtest.c:1258)
```
從前兩個區塊的開頭訊息可以分別得知 `Invalid read of size 1` 和 `Segmentation fault occurred. You dereferenced a NULL or invalid pointer`，並且從 `at 0x484FBD7: strcmp` 可以得知錯誤可能發生在上述實作的第 7 行 if 內的 `strcmp` 。
仔細觀察程式碼後，發現 `list_for_each_entry_safe` 有確保進入迴圈的 `entry` 不等於 `head`，但是 `safe` 則沒有。當迴圈走訪至鏈結串列最後一個元素時， safe 的 list 位置會在 head 上，因此這時如果 `safe->value` 則會存取一個未知的記憶體空間而產生 `Segmentation fault` 。
```diff
- if (strcmp(entry->value, safe->value) == 0) {
+ if (&safe->list != head && strcmp(entry->value, safe->value) == 0) {
```
多加一個條件檢查 `safe` 確保不是 `head` ，修改後可以正確的刪除重複的元素。
### `q_reverse`
走訪每一個節點，把節點移出並且加入開頭，如下圖所示:
```graphviz
digraph G {
rankdir = LR
node[shape=record];
{
rank = same
h [label="head", style=dashed, color=grey];
cur [label="iter", style=dashed, color=grey];
}
subgraph cluster0 {
1->2->"..."->6->7;
}
h -> 1 [style=dashed, color=grey];
cur -> 2:s [style=dashed, color=grey];
2:e -> 1:w [style=dashed, color=red];
}
```
走訪完成可以得到翻轉後的鏈結串列。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
{
rank = same
h [label="head", style=dashed, color=grey];
cur [label="iter", style=dashed, color=grey];
}
subgraph cluster0 {
6->5->"..."->1->7;
}
h -> 6 [style=dashed, color=grey];
cur -> 7:s [style=dashed, color=grey];
7:e -> 6:w [style=dashed, color=red];
}
```
### `q_reverseK`
維護一個計數器 `counter` 一旦走訪 k 個節點後利用 `list_cut_position` 將剛剛所經過的子串列截取出來，使用 `q_reverse` 將子串列翻轉並用 `list_splice_init` 插入原本的鏈結串列。要注意的是翻轉的是 `(start, end]` ，也就是 `q_reverse` 傳入的節點位置必須是子串列開頭的前一個位置。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
{
rank = same
start [label="start", style=dashed, color=grey];
h [label="head", style=dashed, color=grey];
cur [label="end", style=dashed, color=grey];
}
subgraph cluster0 {
"..."->3->4->5->6->"....";
}
start -> 3 [style=dashed, color=grey];
h -> "..." [style=dashed, color=grey];
cur -> 6:s [style=dashed, color=grey];
}
```
假設 k = 3，翻轉 `(3, 6]` 內的子串列。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
{
rank = same
start [label="start", style=dashed, color=grey];
h [label="head", style=dashed, color=grey];
tmp [label="tmp", style=dashed, color=grey];
}
subgraph cluster0 {
"..."->3->"....";
}
4->5->6;
start -> 3 [style=dashed, color=grey];
h -> "..." [style=dashed, color=grey];
tmp-> 4;
}
```
翻轉完後插入原本的串列，接著將 `start` 指到子串列的尾端 `safe->prev` ，要注意這裡 `end` 因為翻轉後變成子串列的開頭所以不能將 `start` 指向 `end` 。
```graphviz
digraph G {
rankdir = LR
node[shape=record];
{
rank = same
start [label="start", style=dashed, color=grey];
h [label="head", style=dashed, color=grey];
end [label="end", style=dashed, color=grey];
}
subgraph cluster0 {
"..."->3->6->5->4->"....";
}
start -> 4 [style=dashed, color=grey];
h -> "..." [style=dashed, color=grey];
end -> 6:s [style=dashed, color=grey];
safe -> "...." [style=dashed, color=grey];
}
```
[q_swap](https://github.com/sysprog21/lab0-c/commit/95aa11af5cc766150aa150bb7513eb46a136cb1b) 是 `q_reverseK` 在 k = 2 時的特例，因此選擇重用 `q_reverseK`。
### `q_ascend` and `q_descend`
[q_ascend](https://github.com/sysprog21/lab0-c/commit/2f1dd8fa93933dba53a3bda58d77ed82e1a82438) 從 `head` 沿著 `next` 的方向走訪至鏈結串列的尾端，在走訪的過程中不斷更新目前的最大值，移除比最大值還小的節點，以維持串列的單調性。 而 [q_descend](https://github.com/sysprog21/lab0-c/commit/e829aefe8c27aadd9e404aa763124091a1fe81c9) 也是相同的概念，但是走訪的方向則是從 `head` 沿著 `prev` 的方向走訪至鏈結串列的開頭。兩者的差別如下:
```diff
$ diff q_ascend.tmp q_descend.tmp
4,5c4,5
- < element_t *entry = list_entry(head->next, element_t, list);
- < element_t *safe = list_entry((entry->list).next, element_t, list);
---
+ > element_t *entry = list_entry(head->prev, element_t, list);
+ > element_t *safe = list_entry((entry->list).prev, element_t, list);
14c14
- < safe = list_entry((entry->list).next, element_t, list);
---
+ > safe = list_entry((entry->list).prev, element_t, list);
```
前四行為一開始初始化的宣告，可以觀察到兩個函式只差別在從 `next` 或是 `prev` 開始走訪。最後兩行則是走訪方向，分別為 `next` 和 `prev` 。
因為程式碼有大量重複的部份，所以想嘗試設計一個 `q_monotonic` 函式，利用傳入 `descend` 決定鏈結的單調性。
```c
static inline int q_monotonic(struct list_head *head, bool descend)
{
// 1 for descend
// 0 for ascend
if (head == NULL || list_empty(head) || list_is_singular(head))
return list_is_singular(head);
element_t *entry, *safe;
if (descend) {
entry = list_entry(head->prev, element_t, list);
safe = list_entry((entry->list).prev, element_t, list);
} else {
entry = list_entry(head->next, element_t, list);
safe = list_entry((entry->list).next, element_t, list);
}
char *mx = entry->value;
while (&entry->list != head) {
if (compare(mx, entry->value)) {
list_del_init(&entry->list);
q_release_element(entry);
} else
mx = entry->value;
entry = safe;
if (descend) {
safe = list_entry((entry->list).prev, element_t, list);
} else {
safe = list_entry((entry->list).next, element_t, list);
}
}
return q_size(head);
}
```
結果為了判斷遞增或遞減，加入額外的 if-else 並沒有使得程式碼更精簡。因此，考慮使用前處理器產生程式碼，一開始設計的時候不太確定前處理器是否可以使用巢狀的方式撰寫巨集，查詢 [C 語言規格書](https://www.dii.uchile.cl/~daespino/files/Iso_C_1999_definition.pdf) 可以發現 `6.10.3.4 Rescanning and further replacement` 就有關於前處理器關於取代規則的說明。
>1. After all parameters in the replacement list have been substituted and # and ## processing has taken place, all placemarker preprocessing tokens are removed. Then, the resulting preprocessing token sequence is rescanned, along with all subsequent preprocessing tokens of the source file, for more macro names to replace.
以我的理解，這段告訴我們可以使用巢狀巨集 (nested macro) 的技巧，因為前處理器會在取代後會再次掃描產生出來的 `preprocessing token sequence` ， 儘可能地尋找要取代的巨集。
我們可以從 `list.h` 裡的 `list_for_each_entry` 為例子，在展開的程式碼裡又有一個 `list_entry` 的巨集。
>2. If the name of the macro being replaced is found during this scan of the replacement list (not including the rest of the source file’s preprocessing tokens), it is not replaced. Furthermore, if any nested replacements encounter the name of the macro being replaced, it is not replaced. These nonreplaced macro name preprocessing tokens are no longer available for further replacement even if they are later (re)examined in contexts in which that macro name preprocessing token would otherwise have been replaced.
這段接著解釋，前處理器在哪些情況下不會進行展開。首先，在當前掃描的部份不會遞迴展開。此外，如果在當前的掃描中如果沒有符合的巨集可以取代的部份，那在後續的掃描即使這部份有符合的巨集名稱也無法進行取代。
```c
#define q_monotonic(head, direction) \
({ \
if (!head || list_empty(head) || list_is_singular(head)) \
return q_size(head); \
element_t *entry = list_entry(head->direction, element_t, list); \
element_t *safe = \
list_entry((entry->list).direction, element_t, list); \
char *mx = entry->value; \
while (&entry->list != head) { \
if (compare(mx, entry->value)) { \
list_del(&entry->list); \
q_release_element(entry); \
} else { \
mx = entry->value; \
} \
entry = safe; \
safe = list_entry((entry->list).direction, element_t, list); \
} \
q_size(head); \
})
int q_ascend(struct list_head *head)
{
return q_monotonic(head, next);
}
int q_descend(struct list_head *head)
{
return q_monotonic(head, prev);
}
```
[q_monotonic(head, direction)](https://github.com/sysprog21/lab0-c/commit/a470fbb5666acecd0023ae3c2f3015c0b4c6d8c1) 利用取代 `direction` 的方式決定鏈結為遞增或是遞減。使用前處理器的方式會有一個缺點，必須在編譯時期就決定為遞增或是遞減，若使用函數 `q_ascend` 和 `q_descend` 包裝起來可以在使用上更彈性。
### `q_sort`
使用 top-down 的方法:
1. 頭尾相向而行尋找中點。
2. 將鏈結串列從中點斷開成左右兩個子串列。
3. 對子串列進行遞迴排序，直到子串列為空或是剩下一個節點。
4. 呼叫 `q_merge_two` 將兩個排序完成的子鏈結串列結合成一個鏈結串列。
>commit [79b62e](https://github.com/sysprog21/lab0-c/commit/79b62e6b157099a1091ea940b12294d5d9f25ad8)
`q_merge_two` 比較左右子串列的節點大小，將被選擇的節點加入 `head`。因為需要支援升序和降序排列的功能，因此會有四種情況需要考慮。
#### 降序排列時:
使用 `compare(left, right) ＆ descend` 判斷將左或右的子鏈結的節點加入 `head` ，必須將較<font color="#f00">大</font>的節點加入 `head` 維持降序排列。
1. 當 `compare(left, right) == true` 時，表示左邊節點的字串"大於"右邊節點，因此選擇左鏈結的節點。
2. 當 `compare(left, right) == false` 時，表示左邊節點的字串"小於等於"右邊節點，因此選擇右鏈結的節點。
#### 升序排列時:
使用 `compare(right, left) ＆ ！descend` 判斷將左或右的子鏈結的節點加入 `head` ，必須將較<font color="#f00">小</font>的節點加入 `head` 維持升序排列。
1. 當 `compare(right, left) == true` 時，表示右邊節點的字串"大於"左邊節點，因此選擇左鏈結的節點。
2. 當 `compare(right, left) == false` 時，表示右邊節點的字串"小於等於"左邊節點，因此選擇右鏈結的節點。
```c
static inline bool compare(char *left, char *right)
{
return strcmp(left, right) > 0;
}
static inline void q_merge_two(struct list_head *head,
struct list_head *left,
struct list_head *right,
bool descend)
{
while (!list_empty(left) && !list_empty(right)) {
if ((compare(list_entry(left->next, element_t, list)->value,
list_entry(right->next, element_t, list)->value) &
descend) ||
(compare(list_entry(right->next, element_t, list)->value,
list_entry(left->next, element_t, list)->value) &
(!descend))) {
list_move_tail(left->next, head);
} else {
list_move_tail(right->next, head);
}
}
if (!list_empty(left)) {
list_splice_tail_init(left, head);
} else {
list_splice_tail_init(right, head);
}
}
```
### `q_merge`
跟 `q_sort` 一樣，走訪時會從頭尾兩端相向而行，將合併後的佇列放回原本的鏈結等待下輪合併，反覆的迭代直到整個鏈結串列只剩一個佇列。
>commit: [fb1594](https://github.com/sysprog21/lab0-c/commit/fb1594550c073cce579296c387aa8aea9dcb175d)
:::danger
HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」，不是用來「假裝自己有付出」
:::
---
## 整合網頁伺服器
從程式碼可以發現，網頁伺服器啟動後，因為`use_linenoise`被設為`false`導致`linenoise`不能使用，這時會執行`cmd_select`函式處理使用者從命令列和網頁輸入的命令。修改`run_console`中`while-loop`的判斷式使`linenoise`的功能可以在網頁伺服器啟動後仍然得以執行，如下所示:
```diff!
- while (use_linenoise && (cmdline = linenoise(prompt, web_proc))) {
+ while ((cmdline = linenoise(prompt, web_proc))) {
```
雖然修改後`linenoise`得以恢復執行，但`linenoise`會不斷讀取使用者的輸入導致網頁的輸入阻塞沒有回應。而原本能處理網頁輸入的`cmd_select`也因此無法執行。
這裡我參考原本`cmd_select`裡關於處理網頁輸入的方法，額外定義一個`web_proc`的函式處裡網頁的輸入，並且使用參數傳遞(`linenoise` -> `line_raw` -> `line_edit`)將`web_proc`以函式指標傳遞至`line_edit`內的`while-loop`處理網頁輸入。
>commit: [6d9771c](https://github.com/sysprog21/lab0-c/commit/6d9771c67e4cc50b266046e3a4b84695523068a2)
參考[vax-r](https://hackmd.io/@vax-r/linux2024-homework1#%E6%95%B4%E5%90%88%E7%B6%B2%E9%A0%81%E4%BC%BA%E6%9C%8D%E5%99%A8)後發現我目前的實作方式有一個缺點，使用函數指標傳遞會造成傳遞的路徑過長(`linenoise` -> `line_raw` -> `line_edit`)，會增加未來除錯與維護時的困難度，應該使用註冊函式的方式將處理網頁輸入的函式獨立於`linenoise`。
## 引入 lib/list_sort.c
參考 [chiangkd](https://hackmd.io/duPg38XOTL-XKa7_h0Ielw?view#2023q1-Homework1-lab0) 的方法引入 list_sort.c 和 list_sort.h
因為需要支援 descend 和 ascend 兩種功能，因此在 `cmp` 使用跟前面 `qsort` 裡的 `compare` 相似的技巧減少重複的程式碼。
```c
int cmp(void *priv, const struct list_head *a, const struct list_head *b)
{
element_t *itemA = list_entry(a, element_t, list);
element_t *itemB = list_entry(b, element_t, list);
int ascend_result = ((strcmp(itemB->value, itemA->value) > 0) & descend);
int descend_result = ((strcmp(itemA->value, itemB->value) > 0) & !descend);
return ascend_result || descend_result;
}
```
在 `qtest.c` 加入新的<s>指令</s>命令。
:::danger
command 的翻譯是「命令」，而非「指令」(instruction)
:::
```c
ADD_COMMAND(kernel_sort,"Sort queue in ascending/descening order with lib/list_sort.c","");
```
`kernel_sort` 的實作大部分都跟原本的 `sort` 相同，只有在實作時呼叫 `list_sort` 取代原本的 `qsort`。
```diff
...
- q_sort(current->q, descend);
+ list_sort(NULL, current->q, cmp);
...
```
定義實驗的腳本如下:
```
# Test qsort & list_sort
option fail 0
option malloc 0
new
ih RAND 1000000
time
sort/kernel_sort
time
```
分別執行五次紀錄所需時間
| | qsort | list_sort |
|----|-------|-----------|
|1st | 0.420 | 0.471 |
|2nd | 0.416 | 0.472 |
|3rd | 0.428 | 0.488 |
|4th | 0.435 | 0.459 |
|5th | 0.426 | 0.469 |
|avg | 0.425 | 0.472 |
實驗結果發現使用的執行時間 `list_sort` 並沒有優於 `qsort`。參考 [Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)，使用`perf` 觀察兩者的 instruction 、 cpu cycle 、 cache miss/references。
```
$perf stat --repeat 5 -e cache-misses,cache-references,instructions,cycles ./qtest -f ./traces/trace-sort.cmd
```
| | qsort | list_sort |
|-----------------|--------------|-------------|
|**cache-misses** |2,6957,4388 <br /> **58.089 %** of all cache refs |2,3196,1362 <br/>**60.275 %** of all cache refs |
|**cache-references** |7,7342,3443 |6,4220,6947 |
|**instructions** |270,7594,3722 |276,6568,6444|
|**cycles** |275,3986,7721 |285,9127,1880|
|**elapsed time(s)**|1.2012 +- 0.0107|1.23950 +- 0.00852|
可以發現雖然使用 `lib/list_sort` 的 cache-misses 較低，但是在 instructions 、 cycles 、 elapsed time 的表現都是都是比 `qsort` 要高一點的。
:::danger
注意測試案例是否反映出資料分布
:::
## shuffle
將隨機選到的 node 用 `list_move_tail` 插入 list 的尾端，並且用 size 的控制隨機取值的區間。
```c
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 *cur;
while(size--) {
int idx = rand()%(size);
cur = head->next;
while(idx--)cur = cur->next;
list_move_tail(cur,head);
}
}
```
在 `qtest` 執行 `shuffle` 後會出現錯誤:
```
Floating point exception (core dumped)
```
使用 valgrind 後可以發現是因為除以零出現 SIGFPE 這個 signal 而出錯。
```
==1288817==
==1288817== Process terminating with default action of signal 8 (SIGFPE)
==1288817== Integer divide by zero at address 0x1002DE3155
==1288817== at 0x1104BA: q_shuffle (queue.c:350)
==1288817== by 0x10C628: do_shuffle (qtest.c:526)
==1288817== by 0x10E306: interpret_cmda (console.c:181)
==1288817== by 0x10E8BB: interpret_cmd (console.c:201)
==1288817== by 0x10ECBC: cmd_select (console.c:610)
==1288817== by 0x10F5A8: run_console (console.c:705)
==1288817== by 0x10D6F8: main (qtest.c:1341)
...
```
最後修改成下面：
```diff
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 *cur;
- while(size--) {
+ while(size) {
int idx = rand()%(size);
cur = head->next;
while(idx--)cur = cur->next;
list_move_tail(cur,head);
+ size--;
}
}
```
接著使用 [1,2,3] shuffle 一百萬次，
設 $\alpha = 0.05$
```
Expectation: 166666
Observation: {'123': 166680, '132': 166887, '213': 166492, '231': 166606, '312': 166431, '321': 166904}
chi square sum: 1.1686966747866991
```
我們的 $X^2=1.1686966747866991$，自由度為 5，從[卡方分布表](https://en.wikipedia.org/wiki/Chi-squared_distribution)可以得知我們的 P value 會是介於0.95和0.90之間。
因此 P value(0.90~0.95)> $\alpha$(0.05)，統計檢定的結果不拒絕虛無假說（$H_0$）
分佈圖如下：
---
## 研讀論文〈Dude, is my code constant time?〉
* 論文的方法是計算兩組 input data(fix-vs-random) 的執行時間，進行 Student’s t-test 驗證是否能推翻虛無假說 $H_0$: the two timing distributions are equal。
* 本專案使用的是 [Welch’s t-test](https://en.wikipedia.org/wiki/Welch%27s_t-test) ， 與 Student’s t-test 相比會在兩組樣本有不同的變異數和樣本數時更可靠
* 從論文的 II-B 可以得知因為 process 可能會因為 OS 的中斷或其他因素導致 timing distributions 比較偏向分佈的右邊。
> Typical timing distributions are positively skewed towards larger execution times. This may be caused by measurement artifacts, the main process being interrupted by the OS or other extraneous activities.
* 由作業可以得知 lab0-c 並未實作 percentile 的處理。
>We discard measurements that are larger than the p percentile, for various^2 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.
### 嘗試引入 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的 percentile 處理
在 [dudect.h](https://github.com/oreparaz/dudect/blob/master/src/dudect.h) 的實作將 percentiles 定義在 `dudect_ctx_t` 這個資料結構中，但是 lab0 的實作則沒有，所以我也遵循 lab0 的方式將 percentiles 定義在 `do_it`。
```diff
static bool doit(int mode)
{
......
+ int64_t *percentiles =
+ (int64_t *) calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
if (!before_ticks || !after_ticks || !exec_times || !classes ||
!input_data) {
die();
}
prepare_inputs(input_data, classes);
bool ret = measure(before_ticks, after_ticks, input_data, mode);
differentiate(exec_times, before_ticks, after_ticks);
- update_statistics(exec_times, classes);
+ bool first_time = percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
+ if (first_time) {
+ prepare_percentiles(exec_times, percentiles);
+ }
update_statistics(exec_times, classes, percentiles);
ret &= report();
......
}
```
:::danger
工程人員說話要精準，看不懂就是看不懂，不要說「比較看不懂」
誠實面對自己！
:::
將 exec_times 利用 `qsort` 排序，計算每個百分點位置對應的值存入 percentiles。 `1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)` 這段程式碼的計算是 <s>比較看不懂</s> 的部份。 這裡我們把 DUDECT_NUMBER_PERCENTILES 設為 100 ，可以把前面寫成數學式 $1-2^{-\frac{10*(i+1)}{100}}$ 。我們可以發現：
| i-th | $1-2^{-\frac{10*(i+1)}{100}}$ |
|---- |-------------------------------|
|0 | 0.066967008 |
|1 | 0.129449437 |
|2 | 0.187747604 |
|3 | 0.242141717 |
|... |... ... |
|30 | 0.883370876 |
|31 | 0.891181180 |
|... |... ... |
|98 | 0.998878224 |
|98 | 0.998953346 |
|99 | 0.999023438 |
我們可以發現這段數學是主要是算出每個百分點位置，並且對分佈在右側的資料密集的取樣。
```c
static int cmp(const int64_t *a, const int64_t *b)
{
return (int) (*a - *b);
}
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 >= 0);
assert(array_position < size);
return a_sorted[array_position];
}
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 < DUDECT_NUMBER_PERCENTILES; i++) {
percentiles[i] = percentile(
exec_times,
1 - (pow(0.5, 10 * (double) (i + 1) / DUDECT_NUMBER_PERCENTILES)),
N_MEASURES);
}
}
```
接著在 `update_statistics` 中利用 percentiles 進行裁切。
```diff
static void update_statistics(const int64_t *exec_times,
uint8_t *classes,
int64_t *percentiles)
{
......
/*do cropping ...*/
+ for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES;
+ crop_index++) {
+ if (difference < percentiles[crop_index]) {
+ t_push(t, difference, classes[i]);
+ }
+ }
}
}
```
加入 percetiles 的部份後，測試程式可達到目標的 100/100 並且看到<s>皮卡丘</s>卡比。
:::danger
為什麼是皮卡丘？
你應該確認程式碼是在 2024 年 2 月 21 日 09:10AM 以後取得。
務必細讀 [2024 年 Linux 核心設計/實作課程作業 —— lab0](https://hackmd.io/@sysprog/linux2024-lab0)
使用 `git rebase`，而非 `git merge`
:::
:::info
先在 [540e9b](https://github.com/sysprog21/lab0-c/commit/5ee9d6093f605f7bc3b3ffb992d1d4d164b12823) 建立一個新的 branch `develop_2024`， 然後使用 `$git rebase -i develop_2024 540e9b` 。 並且將之前的 commit 移除。
:::
回顧現有的 git commits:
存在以下錯誤:
1. 未依據 Chris Beams 撰寫的 [How to Write a Git Commit Message](https://chris.beams.io/posts/git-commit/) 一文，撰寫明確的 git commit message。你可以想像 Apple 和 Google 的工程師隨便安置程式碼，然後不用管合作的議題嗎？
2. 在 git commit message 中，應該在內文解釋 what 以及 why vs. how
3. 單一 commit 混雜不相關的修改，例如 `q_size` 與 `q_insert` 無關
4. 使用的英語詞彙太困乏，無助於溝通
:::danger
重新 fork 再來，不要假裝自己有投入，我們追求的是「有強度」的資訊系統。
:::
## MCTS
由 [MCTS](https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Exploration_and_exploitation) 可以知道每個節點的權重會扮演著非常重要的角色，其計算公式如下:
$$\frac{w_i}{n_i}+c\sqrt{\frac{\ln{N_i}}{n_i}}$$
$w_i$ 代表選擇某節點後贏的次數;$n_i$ 代表選擇某節點的模擬次數;$N_i$ 代表總模擬次數;$c$ 為一個 `empirically` 參數，通常為 $\sqrt{2}$。可以把公式的左項當成 `exploitation` 項(利用過去經驗)，右項當成 `exploration` (當模擬次數越多，此節點被選次數越少，比重越大)。
上述公式會在 ttt 中的 `uct_score` 進行計算，為了避免使用浮點運算單元 (FPU)，可以以定點數來替代浮點數運算。定點數的加減乘除可以利用位移的方式確保正確計算，但是公式內自然對數 $\ln{(x)}$ 和開根號 $\sqrt{x}$ 的計算卻沒辦法，這裡為了研究如何計算定點數的對數和開根號，在 stackoverflow [[5]](https://stackoverflow.com/questions/32159300/compute-logarithmic-expression-without-floating-point-arithmetics-or-log) [[6]](https://stackoverflow.com/questions/76908525/how-do-i-compute-a-fixed-point-binary-logarithm)看到一段程式碼後無法理解其中的邏輯，因此開始研究 [Pseudo Division and Pseudo Multiplication Processes](https://archived.hpcalc.org/laporte/Meggitt_62.pdf) 這篇論文，關於論文的心得和其定點數對數以及開根號演算法的實作因為篇幅的關係放在 [Fixed Point Arithmetic](https://hackmd.io/@Slipet/fixed_point_arithmetic)。
論文作者 IBM 研究員 J.E. Meggitt 改良了一個中古世紀時人們計算對數的演算法 [Radix Method](https://archived.hpcalc.org/laporte/The%20Radix%20Method.htm)，模擬除法的運算期間將除數進行調整，可以幫助我們獲得 $\log{x}$, $\sqrt{x}$, $\tan^{-1}{x}$ 的近似值，由於其中的運算只需要加法和位移，不需要使用到浮點數運算，因此適合實作在計算機當中，世界上第一台手持式計算機 [HP-35](https://en.wikipedia.org/wiki/HP-35) 內就是實作這種演算法計算 $\ln{x}$。其核心概念源自於16、17世紀的數學家 [Henry Briggs](https://en.wikipedia.org/wiki/Henry_Briggs_(mathematician)) 的方法，他改良了原本對數，使用以10為底的方式建立後來人們常用的對數表。其概念其實很簡單:
$$\log{(a\times b)} = \log{(a)} + \log{(b)}$$
這個我們從高中就可以學到的對數性質，可以將 N 分解成若干個 $N_0(1 + q_1)(1 + q_2)...$ 的乘積，而 $\log{N} = \log{N_0} + \log{(1 + q_1)} + \log{(1 + q_2)} + ...。$
\begin{aligned}
1716 &= 1000 \times 1.1 \times 1.2 \times 1.3\\
\log{1716} &= 3 + \log{1.1} + \log{1.2} + \log{1.3}
\end{aligned}
由文章可以得知等式:
$$ y + x = x \prod_{j=0}(1 + 10^{-j})^{q_j}$$
我們可以將一個 10 進制的實數 $R$ 使用 $R = 10^{K}(1.r_1r_2r_3....) = y + 10^{K}$ 表示，這裡的 $10^K$ 就是上面的公式的 $x$ ，而 $10^K$ 的對數可以很輕易地透過定義得知 $\log{10^K} = K$ ，這個例子只是為了更容易理解上述的公式，實際上 $x$ 的數值可以透過事先定義的對數表替換成任意數值。
對兩邊取 $log$ 後:
$$\log{(1 + \frac{y}{x})} = \sum_{j}{q_j\log{(1+10^{-j})}}$$
[Fixed Point Arithmetic](https://hackmd.io/@Slipet/fixed_point_arithmetic) 內有詳細的公式推導說明，這裡的 $q_j$ 表示在第 $j$ 位元的表示，因此 $0\le q_j < 10$，所以如果可以知道 $q_j$ 的數值就可以透過事先計算好的對數表組合出目標的對數值，文章內的演算法就是在講述如何計算 $q_j$。
要注意的是這個公式是應用在10進制的計算。關於二進制部分接著介紹一篇由浮點數之父 [William Kahan](https://en.wikipedia.org/wiki/William_Kahan) 撰寫的一篇文章 [Pseudo-Division Algorithms for Floating-Point Logarithms and Exponentials](https://ieeemilestones.ethw.org/w/images/3/30/Wk_pseudo_division_log_exp_may01.pdf) ，主要的內容只有6頁，但是卻可以言簡意賅的闡述從推導到實際演算法的過程。
> What makes the pseudo-division algorithms so attractive is their close resemblance to the simplest binary multiplication and division algorithms
這段話可以得知為何人們一開始會選擇使用 pseudo-division 的原因，因為整個演算法只需要單純的加法和位移操作即可實作，因此文中也有提到像是 8087 數值協同處理器也有使用此演算法。
>Algorithms like these are used by the Intel 8087 family of numeric coprocessors.
雖然這篇文章的內容是應用在浮點數， 但是對於 pseudo division 的核心想法同樣適用在定點數上。由於計算 `uct_score` 時只會有正整數，所以這裡只考慮關於正整數的部份。
首先定義等式:
$$ y = \frac{1}{(1 + \frac{q_1}{2})(1 + \frac{q_2}{4})(1 + \frac{q_3}{8})(...)(1 + \frac{q_k}{2^k})(1 + ...)} \ , \ q_j \in \{0, 1\}$$
$y$ 的最小值為:
\begin{aligned}
\frac{1}{\eta(1)} &= 0.41942244\\
\frac{1}{\eta(t)} &=\frac{1}{(1 + \frac{t}{2})(1 + \frac{t}{4})(1 + \frac{t}{8})(...)(1 + \frac{t}{2^k})(1 + ...)}
\end{aligned}
這個無窮乘積需要使用 [Euler function](https://en.wikipedia.org/wiki/Euler_function) (不是 [Euler's totient function](https://en.wikipedia.org/wiki/Euler%27s_totient_function)) 才能計算[[註](https://math.stackexchange.com/questions/1924882/evaluating-prod-n-1-infty-left1-frac12n-right)]，可以得到 [link](https://www.wolframalpha.com/input?i=product+1%2F%281%2B2%5E%28-j%29%29%2C+j%3D1+to+infinity) 與論文中相同的答案。可以得到 $y$ 會介於 $\frac{1}{\eta{(1)}}$ 和 $1$ 之間。對於同一 $y$ 可以有不唯一的表式方式:
\begin{aligned}
\frac{2}{3} &= \frac{1}{1 + \frac{1}{2}}\\
&= \frac{1}{(1 + 2^{-2})(1 + 2^{-3})(1 + 2^{-4})(1 + 2^{-8})(1 + 2^{-16})(1 + ...)} \\
&= (0.666666666821...) \times (1 + ...) \ , \ \text{calculate by Win11 calculator} \\
&= \frac{1}{(1 + 2^{-2})(1 + 2^{-3})(1 + 2^{-4})(1 + 2^{-8})(1 + 2^{-16}) \prod_{k = -33}^{-51}(1 + 2^k)}\\
&= (0.666666666666666962750...) \ , \ \text{calculate by Win11 calculator}
\end{aligned}
對於單精度的浮點數至小數點後第7位即足夠($log_{10}{2^{24}}\approx 7.224719$)，雙精度則會是小數點後15位($log_{10}{2^{53}}\approx 15.954590$)，因為這個不唯一的性質使得我們可以利用 pseudo-division 演算法產生 y 的 pseudo-quotient bits $q_k$，對 y 取 $log$ 後可以得到:
$$\log{y} = -q_1\log{\frac{3}{2}} - q_2\log{\frac{5}{4}} - ... - q_k\log{(1 + 2^{-k})}-...$$
對於一個浮點數 Y，想計算其 $\log{(Y)}$，可以利用提取 $2^n$ 將其值域轉換至 $y$ 的區間:
$$\frac{1}{\eta{(1)}} < \frac{1}{2} \le y = \frac{Y}{2^n} \le 1$$
可以知道"正" [單精度的浮點數](https://en.wikipedia.org/wiki/Single-precision_floating-point_format) 表示為:
\begin{aligned}
\text{Normalized:} \ \ Y &= (2^0 + \sum_{i=-1}^{-23}q_i2^i) \times 2^{e-127} \ ,\ 2^{-126}\le Y\le (2 - 2^{-23})\times 2^{127}\\
\text{Denormalized:} \ \ Y &= (\sum_{i=-1}^{-23}q_i2^i) \times 2^{-126} \ , \ 2^{-149} \le Y \le (1 - 2^{-23})\times 2^{-126}\\
\end{aligned}
只考慮正數部分，對於 Normorlized 的部分可以將 $1$ 化為 $2^0$ ，可以得到:
$$\frac{1}{2} \le y = \frac{Y}{2^{n}} = \sum_{i=1}^{24}q_i2^{-i} \le 1\ ,\ \text{for} \ \ n\in[-126, 128]$$
對於 Denormorlized 的部分同樣可以得到:
$$\frac{1}{2} \le y = \frac{Y}{2^{n}} = \sum_{i=1}^{23}q_i2^{-i} \le 1\ ,\ \text{for} \ \ n\in[-149, -126]$$
可以發現不管是浮點數或是定點數，都可以透過提取出 $2^{n}$ 將目標 $y$ 轉換至 $(\frac{1}{\eta{(1)}}, 1]$ 的值域當中。除了前面提到的浮點數，若是定點數 $Z$ 使用 $M$ 個位元表示小數如下:
\begin{aligned}
Z &= \sum_{i = 0}^{31} q_i 2^{i-M} \ , \ q_i \in \{0, 1\} \\
\frac{1}{\eta{(1)}} &< \frac{1}{2} \le y = \frac{Z}{2^n} \le 1
\end{aligned}
仍然可以提取出 $2^n$ 使得 $y$ 落在 $[\frac{1}{\eta{(1)}}, \ 1]$。因此對於浮點數和定點數可得:
\begin{aligned}
y &= \frac{1}{(1 + \frac{q_1}{2})(1 + \frac{q_2}{4})(1 + \frac{q_3}{8})(...)(1 + \frac{q_k}{2^k})(1 + ...)} \ \\ \\
y_k&=y(1+\frac{q_1}{2})(1+\frac{q_2}{4})(1+\frac{q_3}{8})(1+...)(1+\frac{q_k}{2^k}) \\
&= \frac{1}{(1+\frac{q_{k+1}}{2^{k+1}})(1+\frac{q_{k+2}}{2^{k+2}})(1+\frac{q_{k+3}}{2^{k+3}})(1+...)} \ge \frac{1}{\eta(2^{-k})} \ \\
&, \ \text{for} \ k = 1,2,3,4...,L \ \ \text{in turn}
\end{aligned}
對於每個 pseudo-quotient bit $q_k \in \{0,1\}$ ，可以透過下面的不等式來決定:
\begin{aligned}
\frac{1}{(1+2^{-k})} < y_{k-1} \le 1 \ &\text{then} \ q_k = 0 \ \text{and} \ y_k = y_{k-1} \\
&\text{so} \ \frac{1}{\eta{(2^{-k})}} < \frac{1}{1+2^{-k}} < y_k \le 1; \\
\frac{1}{\eta{(2^{1-k})}} < y_{k-1} < \frac{1}{\eta{(2^{-k})}} \ &\text{then} \ q_k = 1 \ \text{and} \ y_k = y_{k-1}(1+2^{-k}) \\
&\text{so} \ \frac{1}{\eta{(2^{-k})}} < y_{k} < 1.
\end{aligned}
這個不等式可以理解為，為了找出符合所求 $y$ 的 $\frac{q_k}{1+2^{(-k)}}$ 乘積組合，對於 $k=1,2,3...,L$ 利用 $y_{k-1}(1+2^{(-k)}) \le 1$ 找出所求的乘積組合，所以當 $y_{k-1}(1+2^{(-k)}) > 1$ 時則超出我們所求的範圍，且 $y_{k-1}$ 同時也必須落在一開始所限制 $[\frac{1}{\eta{(t)}}, 1]$ 區間中，所以才有了第一個不等式 $\frac{1}{(1+2^{-k})} < y_{k-1} \le 1$。
從上面的不等式可以得到下面的遞迴式:
\begin{aligned}
y_{k - 1}(1+2^{-k}) > 1 \ &\text{then} \ q_k = 0 \ and \ y_k = y_{k-1} \\
&\text{else} \ q_k = 1 \ and \ y_k = y_{k-1}(1+2^{-k}).
\end{aligned}
### Implementation
由前一小節得到的遞迴式:
\begin{aligned}
y_{k - 1}(1+2^{-k}) > 1 \ &\text{then} \ q_k = 0 \ and \ y_k = y_{k-1} \\
&\text{else} \ q_k = 1 \ and \ y_k = y_{k-1}(1+2^{-k}). \ \ \ \ \ \ \ \ \ \text{(1)}
\end{aligned}
可以實作出32位元 `UQ16.16` 的定點數 $log_2$ 演算法，為了將定點數 $X = \sum_{i = 0}^{31} q_i 2^{i-16} \ , \ q_i \in \{0, 1\}$ 轉換至 $y$ 值域 $(\frac{1}{\eta{(1)}}, 1]$ 中，使用 `__builtin_clz` 得到最高項的係數 `expo = 32 - lz`，可以將前面的定點數表示為 $X =2^{expo} \times y$，第 14 行的計算是就是將得到的 $y$ 位移成 `UQ1.16`。第 17 ~ 35 行是上述遞迴式的實作，當等式成立時 pseudo-qoutient bit $q_k = 1$ 為:
\begin{aligned}
\log{(X)} &= \log{(2^{expo} \times y)} = lz + \log{(y)} \\
&=lz -q_1\log{1 + 2^{-1}} - q_2\log{1 + 2^{-2}} - ... - q_k\log{(1 + 2^{-k})}-...
\end{aligned}
下面的實作透過變數 `r` 儲存當 $q_k = 1$ 時對應的 $\log{(1 + 2^{-k})}$ 。以 $\log{(1 + 2^{-1})}$ 為例子:
\begin{aligned}
\log_2{1+2^{-1}} &= 0.584962500721 \\
0.584962500721 \times 2^{16} &= 38336.102447 \\
38336_{10} &= 95C0_{16}
\end{aligned}
必須把事先計算的對數值轉換成定點數的格式，所以此時必須乘 $2^{16}$ 可以得到 `0x95C0`。
由[[註](https://hackmd.io/ow1GlyhdRNCujAUcPD61Zg?both=#Binary-format)]可以知道如果要對小於 $\log{(1+2^{-L})}$ 的部分進行補償，可以在結果的最後加上 $\log{(y_L)} = \log{(\eta{(2^{-L})})}$ ， 若是以 $UQ16.16$ 為例子此時的 $L = 16$ ，使用 [link](https://www.wolframalpha.com/input?i=product+1%2F%281%2B2%5E%28-j-16%29%29%2C+j%3D1+to+infinity&lang=zh) 計算得到 $\eta{(2^{-L})} \sim 0.999984741366...$ ，由下面式子計算:
\begin{aligned}
\eta{(2^{-L})} &= 0.999984741366... \\
\log_2{(\eta{(2^{-L})})} &\simeq \log{(0.999984741366)}= -0.00002201372 \\
-0.00002201372 \times 2^{16} &= -1.44269115392
\end{aligned}
因此所得到的補償值會是 $-2 < \log{(y_L)} = \log{(\eta{(2^{-L})})} \simeq -1.44269115392 < -1$ ，對應下面實作最後將所得的 r 減去 2。
最終，將前面得到的 `expo` 轉換成 $UQ16.16$ 計算 `(expo << FSHIFT32) - r` 得到輸出的答案。下面是對應的實作:
```c=
#define FSHIFT32 16
#define FIXED32_1 (1 << FSHIFT32)
uint32_t log2(uint32_t x)
{
if (x == 1) return 0;
uint32_t z, t, one = FIXED32_1; // UQ1.16
uint32_t r = 0;
uint32_t lz, expo;
/* split: x = a * 2**expo, 0 < a < 1 */
lz = __builtin_clz(x);
expo = 32 - lz;
z = (x << lz) >> (32 - FSHIFT32); // UQ1.16
/* try factors (1+2**(-i)) with i = 1, ..., 16 */
if ((t = z + (z >> 1)) < one) { z = t; r += 0x095c0; }
if ((t = z + (z >> 2)) < one) { z = t; r += 0x0526a; }
if ((t = z + (z >> 3)) < one) { z = t; r += 0x02b80; }
if ((t = z + (z >> 4)) < one) { z = t; r += 0x01664; }
if ((t = z + (z >> 5)) < one) { z = t; r += 0x00b5d; }
if ((t = z + (z >> 6)) < one) { z = t; r += 0x005ba; }
if ((t = z + (z >> 7)) < one) { z = t; r += 0x002e0; }
if ((t = z + (z >> 8)) < one) { z = t; r += 0x00171; }
if ((t = z + (z >> 9)) < one) { z = t; r += 0x000b8; }
if ((t = z + (z >> 10)) < one) { z = t; r += 0x00052; }
if ((t = z + (z >> 11)) < one) { z = t; r += 0x0002e; }
if ((t = z + (z >> 12)) < one) { z = t; r += 0x00017; }
if ((t = z + (z >> 13)) < one) { z = t; r += 0x0000c; }
if ((t = z + (z >> 14)) < one) { z = t; r += 0x00006; }
if ((t = z + (z >> 15)) < one) { z = t; r += 0x00003; }
if ((z + (z >> 16)) < one) { /* z = t;*/ r += 0x00001; }
r-=2;
r = (expo << FSHIFT32) - r;
return r;
}
```
原本的遞迴式可以透過迭代加上查找表的方式實作，但是直接展開可以利用編譯器的最佳化選項改善，另外最後一個判斷式內的 `z = t` 其實是冗餘，展開後可以直接省略。這裡要注意的是這個函式輸入為32位元的無號整數，而輸出則是 $UQ16.16$ 的定點數。
#### Square Root
由 [從 √2 的存在談開平方根的快速運算](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method) 可以知道對於開根號有非常多種的方式可以實作，這裡會接著介紹如合從 Meggitt 的 10 進制 pseudo division 計算開根號並推廣至 2 進制的實作，核心想法與 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 類似。
首先定義等式:
\begin{aligned}
y &= x[\sum_{j=0}q_j10^{-j}]^2 \\
\sqrt{\frac{y}{x}} &= \sum_{j=0}q_j10^{-j}
\end{aligned}
假設對於 pseudo qoutient bit $q_0, ... q_{j-1}$ 都已經確定，如果要確定 $q_j$ 可以有下面的表達式:
\begin{aligned}
y_{a}^{(j)} &= y - x[\sum_{k=0}^{j-1}q_{k}10^{-k} + a10^{-j}]^2\ , \ \text{for } a=0,1,2,... \\
x_a^{(j)} &= 2x[\sum_{i=0}^{j-1}q_{i}10^{-i} + a10^{-j}]+x10^{-j}
\end{aligned}
此等式的目標是要盡可能的使 $y_a^{(j)}$ 靠近 0 並保持為正數。由此定義遞迴式:
\begin{aligned}
x_{a+1}^{(j)} &= x_{a}^{(j)} + 2x10^{-j} \\
y_{a+1}^{(j)} &= y_{a}^{(j)} - 10^{-j}x_a^{(j)}
\end{aligned}
跟之前一樣簡化遞迴式:
\begin{aligned}
z_a^{(j)} &= 10^jy_a^{(j)}\\
z_{a+1}^{(j)} &= z_{a}^{(j)} - x_a^{(j)} \\
x_{a+1}^{(j)} &= x_{a}^{(j)} + 2x10^{-j} \\
\end{aligned}
遞迴式會一直計算 $z_a^{(j)}$ 直到負數，得到係數 $q_j$ 有 $z_{q_j}^{(j)} \ge 0 > z_{q_j + 1}^{(j)}$ 。
對於初始條件可以知道，當從第 $j$ 個位元要計算第 $j + 1$ 位元時，必須將被除數進位也就是乘上 10:
$$z_0^{(j+1)} = 10z_{q_j}^{(j)}$$
另外可以知道，
$$x_0^{(j+1)} = x_{q_j}^{(j)} - x10^{-j} + x10^{-j-1}$$
由上面性質可以得到，當需要計算 $q_{j+1}$ 時，必須減去 $0.9 \times 10^{-j}x$ 。最後利用下面的初始值，
$$y_0^{(0)} = y \ , \ x_0^{(0)} = x$$
完成整個演算法。
#### Binary
接著將演算法推廣至2進制，假設定點數:
\begin{aligned}
y &= x[\sum_{j=0}q_j2^{-j}]^2 \ ,\ \text{for } q_j \in \{0,1\}\\
\sqrt{\frac{y}{x}} &= \sum_{j=0}q_j2^{-j}
\end{aligned}
$$x_a^{(j)} = 2x[\sum_{i=0}^{j-1}q_{i}2^{-i} + a2^{-j}]+x2^{-j}$$
定義遞迴式:
\begin{aligned}
x_{a+1}^{(j)} &= x_{a}^{(j)} + 2x2^{-j} \\
&= x_{a}^{(j)} + x2^{1-j} \\
y_{a+1}^{(j)} &= y_{a}^{(j)} - 2^{-j}x_a^{(j)}
\end{aligned}
簡化遞迴式:
\begin{aligned}
z_a^{(j)} &= 2^jy_a^{(j)}\\
z_{a+1}^{(j)} &= z_{a}^{(j)} - x_a^{(j)} \\
x_{a+1}^{(j)} &= x_{a}^{(j)} + x2^{1-j} \\
\end{aligned}
初始條件為，
$$y_0^{(0)} = y \ , \ x_0^{(0)} = x$$
對於初始條件可以知道，當從第 $j$ 個位元要計算第 $j + 1$ 位元時，必須將被除數進位也就是乘上 2:
$$z_0^{(j+1)} = 2z_{q_j}^{(j)}$$
由前面 10 進制的介紹對於 $x_{q_j}^{(j)}$ 可以得到，
\begin{aligned}
x_0^{(j+1)} &= x_{q_j}^{(j)} - x2^{-j} + x2^{-j-1} \\
&= x_{q_j}^{(j)} + x2^{-j}(-1 + 2^{-1}) \\
&= x_{q_j}^{(j)} - x2^{-j-1} \\
\end{aligned}
#### Implementation
為了將輸入改寫成下面的形式:
$$y = x[\sum_{j=0}q_j2^{-j}]^2 \ ,\ \text{for } q_j \in \{0,1\}$$
需要將 $2^K$ 提取出來使定點數 $Y$ 可以有:
\begin{aligned}
2^0 \le y = \frac{Y}{2^K} &= \frac{Y}{(2^k)^2} = \sum_{i=0}(q_i2^{-i})^2 < 2^2 \\
1 \le \sqrt{y} = \sqrt{\frac{Y}{2^K}} &= \frac{\sqrt{Y}}{2^k} = \sum_{i=0}(q_i2^{-i}) < 2
\end{aligned}
可以發現下面第 9 行就是為了將 $Y$ 轉換至 $[1,4)$ 的區間當中，第 10 行則是相當於提取出 $2^K$。
從前面的說明可以知道如果 $q_k = 1$，則關於更新 $x_{q_k}^{(j)}$ 的遞迴式如 (1)，當 $q_k = 0$ 仍然滿足 $x_{0}^{(j)} = x_{0}^{(j)}$; 而從第 $j$ 位計算 $j + 1$ 時
\begin{aligned}
x_{q_k}^{(j)} &= x_{0}^{(j)} + x2^{1-j}q_k \ \ \ \ \ \ \text{(1)}\\
x_0^{(j+1)} &= x_{q_j}^{(j)} - x2^{-j-1} \ \ \ \ \ \ \ \text{(2)}\\
y_0^{(j+1)} &= 2y_{q_k}^{(j)} = 2(y_{q_k}^{(j)} - 2^{-j}x_{q_k}^{(j)})\ \ \ \ \ \ \text{(3)}\\
\end{aligned}
\begin{aligned}
x_{q_k}^{(j+1)} &= x_{q_{j}}^{(j)} + x2^{-j-1}(-1 + 2q_k) \ \ \ \ \ \ \text{(1)}\\
\end{aligned}
由上面的說明可以知道初始條件為，
$$y_0^{(0)} = y = \frac{Y}{2^K} \ , \ x_1^{(0)} = 1$$
下面程式碼是對應的實作:
```c=
uint32_t UQ16P16_pseudo_division_sqrt(uint32_t n)
{
const int lz = __builtin_clz(n);
const uint32_t one = 1UL << 29;
uint32_t y = n;
uint32_t x = one, d = one << 2;
uint32_t r = 0, count = 0;
y = (y << lz >> 1) >> (lz & 1);
int expo = (FSHIFT - lz + (lz & 1)) / 2;
while (count < (FSHIFT) ) {
d >>= 1;
if (y >= x) {
y -= (x);
x = x + (d);
r += (one >> count >> 14);
}
y <<=1;
x-= (d >> 2);
count++;
}
return (expo >= 0) ? r << (expo) : r >> (-expo);
}
```
#### 客製化定點數
前面的實作為 $UQ16.16$ 的定點數實作，但是如果考量到計算 MCTS 權重的最大模擬次數 $N_i$ ，只用 16 位元表示正整數最多只能表示至 $2^{16} - 1 = 65535$，使得 MCTS 模擬的次數會受限於定點數本身設計。
#### Coroutine
參考 [coro](https://github.com/sysprog21/concurrent-programs/tree/master/coro) 設計我的 coroutine 實作，`coro` 使用 `setjmp` 和 `longjmp` 達到在不同任務間切換。
當使用者輸入指令 `ttt` 會呼叫 `schedule` 利用使用者輸入的參數初始化遊戲，將執行遊戲的 `task` 放入一個鏈結串列 `tasklist` 中提供 `task_switch` 挑選執行的任務，如同 `coro` 設計的一樣， `task` 反覆的呼叫 `gameplay` 函數進行遊玩，每個 `task` 的目標很簡單只需要在 `gameplay` 返回時跳轉至 `task_switch`，`task_switch` 會從 `tasklist` 中選出下一個要執行的任務進行跳轉。
整個過程如同下面這張圖:
```graphviz
digraph G {
rankdir = TB;
newrank=true;
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
do_ttt [shape=Mdiamond];
return [shape=Msquare];
subgraph cluster0 {
style=filled;
color=lightgrey;
node [style=filled,color=white];
schedule0 [label="schedule"];
schedule1 [label="schedule"];
task_switch0 [label="task switch"];
task_switch1 [label="task switch"];
task_switch2 [label="task switch"];
task_switch3 [label="task switch"];
task_switch4 [label="... ..."];
schedule0 -> schedule1;
schedule1 -> task_switch0;
task_switch0 -> task_switch1;
task_switch1 -> task_switch2;
task_switch2 -> task_switch3;
task_switch3 -> task_switch4;
label = "scheduler";
};
subgraph cluster1 {
node [style=filled];
task0_init [label="task init"];
gameplay0 [label="gameplay"];
gameplay2 [label="... ..."];
empty1 [style=invis];
task0_init -> gameplay0;
gameplay0 -> gameplay2;
gameplay2 -> empty1:s;
label = "game task 0";
color=blue
};
subgraph cluster2 {
node [style=filled];
empty[style = invis ];
empty2 [style=invis];
task1_init [label="task init"];
gameplay1 [label="gameplay"];
gameplay3 [label="... ..."];
task1_init -> gameplay1;
gameplay1 -> gameplay3;
gameplay3 -> empty2:s;
label = "game task 1";
color=blue
};
{ rank=same; schedule0; task0_init; empty;}
{ rank=same; schedule1; task1_init;}
{ rank=same; task_switch0; gameplay0;}
{ rank=same; task_switch1; gameplay1;}
{ rank=same; task_switch2; gameplay2;}
{ rank=same; task_switch3; gameplay3;}
{ rank=same; task_switch4; empty1; empty2;}
splines=ortho
do_ttt -> schedule0;
schedule0:en -> task0_init:wn
task0_init:ws -> schedule0:es
schedule1:en -> task1_init:wn
task1_init:ws -> schedule1:es
task_switch0:en -> gameplay0:wn
gameplay0:ws -> task_switch0:es
task_switch1:en -> gameplay1:wn
gameplay1:ws -> task_switch1:es
task_switch2:en -> gameplay2:wn
gameplay2:ws -> task_switch2:es
task_switch3:en -> gameplay3:wn
gameplay3:ws -> task_switch3:es
task_switch4:s -> return
}
```
將每場 ttt 遊戲的遊玩狀態劃分成 INIT, MOVE, DRAW, CMPLT, END，因此可以利用目前的狀態得知下一個階段該怎麼執行，INIT 為開始時初始化遊戲的部分，狀態 DRAW 會判斷當前棋盤是否有贏家產生並繪製棋盤，MOVE 可以利用目前玩家的參數使用 AI 或是 HUMAN 選擇落子，若是兩個玩家的參數都是 AI 則是 AI 與 AI 互相對弈，當遊戲進行中時會不斷地在 DRAW 和 MOVE 間切換，一旦其中一方勝利時會切換至 CMPLT 將遊戲收尾並將狀態設為 END 宣告這局遊戲真正的結束。狀態圖的變化如下:
```graphviz
digraph finite_state_machine {
fontname="Helvetica,Arial,sans-serif"
node [fontname="Helvetica,Arial,sans-serif"]
edge [fontname="Helvetica,Arial,sans-serif"]
rankdir=TB;
node [shape = doublecircle];
INIT;
END;
node [shape = circle];
MOVE;DRAW;CMPLT;
INIT -> DRAW;
MOVE -> DRAW;
DRAW -> MOVE;
DRAW -> CMPLT[label="check win"];
CMPLT -> END
}
```
由於每局遊戲的狀態都是各自分配空間儲存，儘管其中一局遊戲提前結束時，`task` 不會將結束的遊戲加入 `tasklist` 進行排程，所以不會影響未結束的遊戲，這個設計可以使我們同時觀看多局遊戲同時進行。
暫停當前畫面輸出的功能則是利用將 `stdout` 導入一個暫時的 buffer達到暫停的效果。
接著參考 [Build Your Own Text Editor](https://viewsourcecode.org/snaptoken/kilo/) 的方式建立一個 pthread 監聽目前的鍵盤事件，這裡選擇使用 pthread 的方式的原因為如果在原本的 `tasklist` 加入監聽任務，會因為其他的任務執行而沒辦法及時的對鍵盤事件進行回應。
目前的實作有一個缺點未來可以繼續改進的部分，一旦暫停畫面輸出時若是有某局遊戲已經結束了，仍然會留在 `tasklist` 中參與排程等待停止暫停輸出時繪製遊戲結果，造成占用執行資源的情況，隨著同時遊玩的局數增加時，大量的任務會在列隊裡等待輸出遊戲結果，這種情況勢必會影響到尚未結束的遊戲執行時間。目前的初步的改良想法為增加一個 `idlelist`，將遊玩結束後等待輸出結果的任務放入 `idlelist` 等待恢復輸出，當重新開始輸出時便加入一個任務將 `idlelist` 內等待的任務加回 `tasklist`。
## Reference
1. [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)
2. [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_remove_head)
3. [hongpei100](https://hackmd.io/@MrShark/S1Z73ZTTj#%E9%96%8B%E7%99%BC%E6%B5%81%E7%A8%8B%E7%B4%80%E9%8C%84)
4. [Linux 效能分析工具: Perf](https://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
5. [Compute logarithmic expression without floating point arithmetics or log](https://stackoverflow.com/questions/32159300/compute-logarithmic-expression-without-floating-point-arithmetics-or-log)
6. [https://stackoverflow.com/questions/76908525/how-do-i-compute-a-fixed-point-binary-logarithm](https://stackoverflow.com/questions/76908525/how-do-i-compute-a-fixed-point-binary-logarithm)
:::danger
本文標題用 `# ` (一個井字號)，子項目標題用 `## ` (二個井字號)。注意細節！
:::
Sign in with Wallet
Connect another wallet