# 2024q1 Homework1 (lab0)
contributed by < [jouae](https://github.com/jouae) >
## 開發環境
```shell!
$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu 22.04.4 LTS
Release: 22.04
Codename: jammy
$ 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.
```
CPU (Central Processing Unit) 資訊
在 Linux 作業系統行程 (process) ，是以檔案系統 (file system) 的方式存在於 `/proc` ([Linux 核心設計: 作業系統術語及概念：藉由星之卡比解讀 Linux 核心發展](https://hackmd.io/@sysprog/linux-concepts#%E8%97%89%E7%94%B1%E6%98%9F%E4%B9%8B%E5%8D%A1%E6%AF%94%E8%A7%A3%E8%AE%80-Linux-%E6%A0%B8%E5%BF%83%E7%99%BC%E5%B1%95))，其中包含 CPU 的詳細資訊。使用 `man proc` 查看手冊說明：
> `/proc/cpuinfo`
This is a collection of CPU and system architecture dependent items, for each supported architecture a different list. Two common entries are processor which gives CPU number and bogomips; a system constant that is calculated during kernel initialization. SMP machines have information for each CPU. The lscpu(1) command gathers its information from this file.
由於是檔案，可以 `cat` 連結檔案內容 `cat /proc/cpuinfo` 便得到相關 CPU 資料，但使用這個方式的話，會列舉所有處理器(processor)的資訊。使用 `lscpu` 可以得到 `Virtualization features` 如快取(caches)大小等額外資訊。
```shell!
$ 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): 6
On-line CPU(s) list: 0-5
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 4500U with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 1
Core(s) per socket: 6
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2375.0000
CPU min MHz: 1400.0000
BogoMIPS: 4741.04
Flags: ...
```
關於 flags ： [What do the flags in /proc/cpuinfo mean?](https://unix.stackexchange.com/questions/43539/what-do-the-flags-in-proc-cpuinfo-mean)
## Linux 中的鏈結串列
> [linux/include/linux/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
```c
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
```
[C macro expansion in Linux Kernel code](https://stackoverflow.com/questions/2673728/c-macro-expansion-in-linux-kernel-code) 解釋中給出
WRITE_ONCE() [你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Linux-%E6%A0%B8%E5%BF%83%E5%8E%9F%E5%A7%8B%E7%A8%8B%E5%BC%8F%E7%A2%BC)
建議搭配 [statment expression](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 與 [Linux 核心原始程式碼巨集: `max`, `min`](https://hackmd.io/@sysprog/linux-macro-minmax) 理解實作原理
## 基本工具
### `container_of`
[Linux 核心原始程式碼巨集: `container_of`](https://hackmd.io/@sysprog/linux-macro-containerof)
## 不安全的函式
[CERN Common vulnerabilities guide for C programmers](https://security.web.cern.ch/recommendations/en/codetools/c.shtml) 給出一些不安全的內建函式。
### strcpy()
相較於 `strncpy(char *s1, const char *s2, size_t n)` ， `strcpy(char *s1, const char *s2)` 少了 `size_t n` 參數。
C99 7.21.2.3 The strcpy function：
> The strcpy function copies the string pointed to by s2 (including the terminating null character) into the array pointed to by s1.
C99 7.21.2.4 The strncpy function：
> 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 the array pointed to by s2 is a string that is shorter than n characters, null characters are appended to the copy in the array pointed to by s1, until n characters in all have been written.
當 `s2` 的長度小於 `n` 時候，會將 null characters 寫入 `s1` 直到 `n` 個大小，例如：
```c
size_t n = 5;
char *s2;
s2 = "a";
strncpy(s1, s2, n);
for(int i = 0; i < n; i++)
printf("%d ", s1[i]);
```
會輸出 ACII 碼，結果會為：
```
97 0 0 0 0
```
CERN 給出 `strcpy` 不安全的例子：
```c
char str1[10];
char str2[]="abcdefghijklmn";
strcpy(str1,str2);
```
使用 valgrind 來檢查記憶體的狀況：
```shell
==42629== Memcheck, a memory error detector
...
==42629== Command: ./strcpy
==42629==
==42629== Source and destination overlap in strcpy(0x1ffefffdaf, 0x1ffefffdb9)
==42629== at 0x484EF00: strcpy (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==42629== by 0x1091B5: main (in /home/yanjie/playground/strcpy)
```
[valgrind User Manual 4.2.6. Overlapping source and destination blocks](https://valgrind.org/docs/manual/mc-manual.html)
問題：使用 GDB 要怎麼看 buffer overflow 的行為？記憶體 stack 要怎麼看？
## 佇列實作
### `q_new`
:::warning
allocate 翻譯為「配置」，以區格 dispatch (分發/分配) 的翻譯詞彙，二者在作業系統領域都是常見詞彙。
:::
參考 [YSRossi](https://hackmd.io/@YSRossi/lab0-2023) 和 [chiangkd](https://hackmd.io/@chiangkd/2023spring-lab0-c#q_new)，配置記憶體空間的時候採用更簡潔的方式表示
```c
// malloc(sizeof(struct list_head))
struct list_head *q = malloc(sizeof(*q));
```
[chiangkd](https://hackmd.io/@chiangkd/r1qCyPkzq#q_new) 引用 [C99 7.20.3 Memory management function]
> If the space cannot be allocated, a null pointer is returned. If the size of the space requested is zero, the behavior is implementation-defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.
使用 `malloc` 有可能無法配置足夠的記憶體而返回空指標（ null pointer ），空指標在某些場合會導致未定義行為（ undefined behavior）。因此直接回傳 `q` 是不安全的，為了處理這種情況，在回傳前加入一個 if 判斷句，檢查是否成功配置了記憶體。
```c
if(!q) // If the allocation is failed
return NULL;
```
:::danger
改進你的漢語表達。
:::
### q_free
由於釋放記憶體的過程會對原本的串列內容做改動，所以需要在遍歷整個串列並改動的同時紀錄原始串列的資訊，才能保證在改動記憶體過程時，指標不會指向未知的地址，這部分可以用 `list.h` 中定義的 `list_for_each_entry_safe` 來實踐。
這個巨集中相比 `list_for_each_entry` 多定義了一個 `safe` 指標，用於紀錄當前指標指向的下個節點的資訊。但這個巨集的使用僅限於**移開（ remove ）** 不包含修改串列本身。除了移開節點，任何對串列的修改，都可能會造成未定義行為。
安全的釋放記憶體：
1. 移開節點
`list_del()`
2. 釋放該節點記憶體
`q_release_element()`
### q_insert_head, q_insert_tail
對於字串（ string ）於 C99 7.1.1 Defitions of Terms 定義為
> A *string* is a contiguous sequence of characters terminated by and including the first null character. The term multibyte string is sometimes used instead to emphasize special processing given to multibyte characters contained in the string or to avoid confusion
with a wide string. A pointer to a string is a pointer to its initial (lowest addressed) character. The length of a string is the number of bytes preceding the null character and the value of a string is the sequence of the values of the contained characters, in order.
參考 [chun61205](https://hackmd.io/@roger61205/lab0-2023#q_insert_head-%E5%92%8C-q_insert_tail), [kdnvt](https://hackmd.io/@kdnvt/linux2022_lab0#q_insert_head) 等的實作方式，當中有使用 `strlen()` 來取得字串的長度，但在[你所不知道的 C 語言：指標——重新探討字串](https://hackmd.io/@sysprog/c-pointer#%E9%87%8D%E6%96%B0%E6%8E%A2%E8%A8%8E%E3%80%8C%E5%AD%97%E4%B8%B2%E3%80%8D)中引用 C99 7.21.1 String function conventions
>Various methods are used for determining the lengths of the arrays, but in all cases
a `char *` or `void *` argument points to the initial (lowest addressed) character of the
array. If an array is accessed beyond the end of an object, the behavior is undefined.
null pointer `*p` 使用 `strlen(p)` 是未定義行為。由於無法預期使用者的行為，所以在此直接使用 `strlen()` 並非是最好的選擇。所以我想先判斷 `s` 是否為 null pointer 再執行 `strlen()`
```c
if (!s)
return false
```
使用上述的程式碼會有一個危險，空字元（ null-chararter ） 也會回傳 `false`
C99 5.2.1 Characters Set
> A byte with all bits set to 0, called the null character, shall exist in the basic execution character set; it is used to terminate a character string
C99 6.4.4 Character constants
> The construction '\0' is commonly used to represent the null character.
所以我用邏輯運算子 <s>`&&`</s> `||` 修正上述判斷的過程
```diff
- if ((!s) && (s!="")) // If s is null pointer but not null-terminator
+ if (!s || !*s)
return false
```
:::info
[FB 2024 年系統軟體系列課程討論區 2024/02/28](https://www.facebook.com/groups/system.software2024/permalink/1556863905091502/?mibextid=uJjRxr) 中提問，邱冠維跟黃老師給予指點更正
:::
### q_swap
實作 swap 有兩個動作：
1. 選擇要交換的位置
2. 將要交換位置的節點與相鄰的節點兩者互換
```c
void swap (int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = *temp;
}
for each node of list do
swap(list[index], list[index+1])
```
但這是 bad taste 的作法，參考 [2020leon](https://hackmd.io/@6649/linux2022-lab0)，善用環狀鏈結串列的特性以及 API 巧妙的使用
以下是原作者將 swap 兩個動作實作的方式：
假設有一個指標的指標（indirect pointer） `*i` 指向要交換的 `list_head` 指標。以及實作交換的最小單位，有著兩個 `list_head` 結構體 `a` 和 `b` 節點的串列。
```graphviz
digraph structs {
node[shape=record]
rankdir=LR
head [label="{<data> head|{<next> next|<prev> prev}}"];
struct1 [label="{<data> a|{<next> next|<prev> prev}}"];
struct2 [label="{<data> b|{<next> next|<prev> prev}}"];
head:prev -> struct2:data[arrowhead=vee, tailclip=true, arrowsize=1];
head:next -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:prev -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> struct2:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:prev -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:next -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
1. **交換的動作**
當 `*i` 指向 `a` 時，需要將 `a->next=b` 和 `a->prev=b` 改為 `a->prev=b` 和 `a->next=b` 。同時 `b->prev=a` 和 `b->next=a`，改為 `b->next=a` 和 `b->prev=a` 。
其實在 `list.h` 中有定義這操作，那就是 `list_move` ，由 `list_del` 和 `list_add` 組成。 `list_del` 先將 `*i` 指向的指標，移開原本屬於的串列：
```graphviz
digraph structs {
node[shape=record]
rankdir=LR
head [label="{<data> head|{<next> next|<prev> prev}}"];
struct1 [label="{<data> b|{<next> next|<prev> prev}}"];
struct2 [label="{<data> a|{<next> next|<prev> prev}}"];
memory1 [label="0x00100100"];
memory2 [label="0x00200200"];
head:prev -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
head:next -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:prev -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:prev -> memory1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:next -> memory2:data[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
`list_add` 最後再將 `a` 新增到 `b` 的之後：
```graphviz
digraph structs {
node[shape=record]
rankdir=LR
head [label="{<data> head|{<next> next|<prev> prev}}"];
struct1 [label="{<data> b|{<next> next|<prev> prev}}"];
struct2 [label="{<data> a|{<next> next|<prev> prev}}"];
head:prev -> struct2:data[arrowhead=vee, tailclip=true, arrowsize=1];
head:next -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:prev -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct1:next -> struct2:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:prev -> struct1:data[arrowhead=vee, tailclip=true, arrowsize=1];
struct2:next -> head:data[arrowhead=vee, tailclip=true, arrowsize=1];
}
```
:::info
`list_del` 的行為，是 remove 這個動作，其註解中也有解釋：
> Remove a list node from the list
兩者的差異可見 [Difference between "delete" and "remove"](https://english.stackexchange.com/questions/52508/difference-between-delete-and-remove)。
:::
2. **選取欲交換位置的過程**
由於串列的長度會是奇數或是偶數，將分成兩個情況討論其終止條件
* **串列長度為偶數**
偶數長度串列，可以將整個串列視為成對節點構成的子串列鏈結在一起。所以討論最小可交換串列後，剩下的部分可以用歸納法的方式做結論。最小串列即兩個節點組成的串列，在上述交換動作時，指標 `*i` 做完交換動作指向 b，根據環狀鏈結串列的特性此時再將 `*i` 指向下一個位置即為 `head` ，至此便不用再做交換。每個子串列在內部進行交換後便會指向的相鄰的下個子串列做內部交換，根據歸納法最後可以得到每個已交換子串列組成的串列。因此當串列長度為偶數時，終止條件為 `i` 指向 `head`。
* **串列長度為奇數**
奇數長度串列，為成對節點構成的子串列鏈結一起後額外加一個沒有配對的節點組成。可以將整個串列視為前面偶數長度部分跟最後單一節點部分，偶數部分根據上偶數長度的討論，最後 `i` 指向最後的單一節點時， `i->next` 指向 `head` 時便停止交換。
根據上述兩個情況，終止條件為 `i->next` 為 `head` 或是 `i` 為 `head` 。以邏輯運算子表示的話：
```c
i->next == head || i == head
```
其否命題
```c
i->next != head && i != head
```
便是迴圈中的控制表達式（ controlling expression ）。
### q_reverse
逐一走訪所有節點的同時，將節點從串列移開（ remove ）然後加入至串列的開始。
### q_reverseK
這邊對有做一些 `K` 討論，`qtest.c` 中 `do_reverseK` 在判斷 `K` 的資料型態時，僅只使用 `get_int()` 判斷型態是否整數。
想到兩個解法：
1. 修改 `qtest.c` 內容
修改測試程式的內容時，只要將以下控制表達是增加一個邏輯運算子，確認 `K` 是否小於 $0$：
```diff
- if(!get_int(argv[1], &k))
+ if(!get_int(argv[1], &k) || k <= 0)
```
並在 `console_init` 中修改 `do_reverseK` 中的增加以下說明：
```
K must be positive integer.
```
2. 直接在 `reverseK` 中做判斷
這邊就要定義當 `K` 為負數含零時的行為，我這邊是採用甚麼都不做。如下：
```c
if (!head || list_is_singular(head) || k <= 0)
return;
```
我這邊採用後者的作法，由於目前不確認測資的實際行為如何，修改 `qtest.c` 可能會有無法預期的行為。
### q_delete_dup
參考 [yanjiew1](https://hackmd.io/@yanjiew/linux2023q1-lab0#q_delete_dup) 另外儲存重複出現的字串，最後再一次全部釋放。
想將最後釋放節點的方式改用成 `q_free` ：
```diff
- list_for_each_entry_safe (current, safe, &dup_head, list)
- q_release_element(current);
+ q_free(&dup_head)
```
過程中有出現一些錯誤提示，這邊使用 `valgrind` 查看
`valgrind ./qtest -v 3`
```
cmd> new
l = []
cmd> it a 4
l = [a a a a]
cmd> dedup
ERROR: Attempted to free unallocated block. Address = 0x1ffefff910
ERROR: Attempted to free unallocated or corrupted block. Address = 0x1ffefff910
==17064== Invalid read of size 8
==17064== at 0x10F44F: test_free (harness.c:183)
==17064== by 0x10F75D: q_free (queue.c:44)
==17064== by 0x10F9FA: q_delete_dup (queue.c:219)
==17064== by 0x10C053: do_dedup (qtest.c:465)
==17064== by 0x10DFD1: interpret_cmda (console.c:181)
==17064== by 0x10E586: interpret_cmd (console.c:201)
==17064== by 0x10F1F0: run_console (console.c:691)
==17064== by 0x10D3C3: main (qtest.c:1258)
==17064== Address 0x2003b80ac8 is not stack'd, malloc'd or (recently) free'd
==17064==
Segmentation fault occurred. You dereferenced a NULL or invalid pointer
```
這邊告訴我該去查看 `harness.c` 的 `test_free` 實際是如何運作的。因為 `q_free` 中使用到 `q_release_element` ，而 `q_release_element` 中使用 `test_free` 來釋放配置的記憶體。
但照原作者的方式釋放記憶體，是沒有問題的。具體來說的動作是一樣的藉由 `list_for_each_entry_safe` 和 `q_release_element` ，差別在於有沒有函式呼叫。細節部份在 [你所不知道的 C 語言：函式呼叫篇](/FXPLwKmxQdCuz0zC-XZXOQ) 跟 [你所不知道的 C 語言：指標篇](/hqJBzualRcOrb2wMhheKCQ) 中應該會有明確的解答。這部份的差異待釐清。
---
### q_remove_head, q_remove_tail
先觀察函式參數的作用，從 `queue.h` 中註解給定參數的定義為：
```
@head: header of queue
@sp: string would be inserted
@bufsize: size of the string
```
查看 `qtest.c` 中 `q_remove_tail` 的位置在 351 至 353 行出現。此時指標 `*sp` 為 `remove` 這個變數：
```c
re = pos == POS_TAIL
? q_remove_tail(current->q, removes, string_length + 1)
: q_remove_head(current->q, removes, string_length + 1);
```
追蹤 `remove` 指標在 `qtest` 的作用後， `*sp` 的正確敘述應該是 `string would be removed` 才對。理由是直接執行 `./qtest` 執行以下命令：
```
cmd> new
l = []
cmd> ih RAND 5
l = [arjqhbb caqgpt efwbhiiu fyzuwbhn dcewkbi]
cmd> rh 1
Removed arjqhbb from queue
ERROR: Removed value arjqhbb != expected value 1
l = [caqgpt efwbhiiu fyzuwbhn dcewkbi]
```
看到 `Removed value arjqhbb != expected value 1` ，從 `qtest.c` 找出位於 395 至 399 行中的 if 條件句中。
```c
if (ok && check && strcmp(removes, checks)) {
report(1, "ERROR: Removed value %s != expected value %s", removes,
checks);
ok = false;
}
```
#### 藉由前處理器重構
參考 [Shiritai](https://hackmd.io/@Eroiko/lab0-impl#q_insert_head-%E5%92%8C-q_insert_tail-%E7%9A%84%E5%AF%A6%E4%BD%9C%E8%88%87%E9%87%8D%E6%A7%8B), [paulpeng-popo](https://hackmd.io/@normal/SyAQbn26j#q_remove_headtail) 可以採用前置處理器的方式來簡化程式碼。
[你所不知道的C語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FS1maxCXMl) 中有提及使用 `##` 運算子的例子。[GNU onlinedoc 3.5 Concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html) 詳述：
> The ‘##’ preprocessing operator performs token pasting. When a macro is expanded, the two tokens on either side of each ‘##’ operator are combined into a single token, which then replaces the ‘##’ and the two original tokens in the macro expansion.
將 `##` 前後的兩邊的 tokens 合併成一個 token ，最後用這個 token 替換 `##` 與 `##` 前後兩邊的 tokens。
其中出現 `##` 這個運算子， C99 6.10.3.1 Argument substitution 給出以下敘述：
> After the arguments for the invocation of a function-like macro have been identified, argument substitution takes place. A parameter in the replacement list, unless preceded by a # or ## preprocessing token or followed by a ## preprocessing token (see below), is replaced by the corresponding argument after all macros contained therein have been expanded.
與 6.10.3.3 The ## operator：
> If, in the replacement list of a function-like macro, a parameter is immediately preceded or followed by a ## preprocessing token, the parameter is replaced by the corresponding argument’s preprocessing token sequence
回頭看程式碼的部份：
```c
#define q_remove(suffix, list_api) \
element_t *q_remove_##suffix(struct list_head *head, char *sp, \
size_t bufsize)
```
使用這種方式可以藉由 `suffix` 參數，來生成出不同的函式，例如： `q_remove(head, list_first_entry)` 便得到 `q_remove_head()` 的函式。所以藉由前置處理器對 `q_remove_head()` 、 `q_remove_tail()` 採用一致的界面 `q_remove(suffix, list_api)` 來宣告。
## 隨機
### fill_rand_string 生成的隨機字串不均勻
> [PR #173: Improve string randomness](https://github.com/sysprog21/lab0-c/pull/173)
在 [lab0-c](https://github.com/sysprog21/lab0-c) 的 `qtest.c` 中有對於隨機字串插入佇列的功能，藉由 `RAND` 關鍵字啟用偽隨機字串生成器。使用方式如 `ih RAND 5` ，執行 `q_insert_head` 對佇列開端插入隨機 $5$ 個字串。
在 `qtest` 中隨機字串生成的函式為 `fill_rand_string` ，對全域變數 `charset` 由 26 個小寫英文字母的組成陣列，隨機挑選介於 `MIN_RANDSTR_LEN` 和 `MAX_RANDSTR_LEN` 個字元，最後組成字串。
```c
static void fill_rand_string(char *buf, size_t buf_size)
{
size_t len = 0;
while (len < MIN_RANDSTR_LEN)
len = rand() % buf_size;
randombytes((uint8_t *) buf, len);
for (size_t n = 0; n < len; n++)
buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
buf[len] = '\0';
}
```
其中偽隨機數的生成藉由 [randombytes](https://github.com/dsprenkels/randombytes) 實踐。
而 `wuyihung` 發現在此採用 `uint8_t` 會有一個問題：
>However, since the number of variations is 256, which is not exact division of 26
`uint8_t` 在 [stdint.h(0p) — Linux manual page](https://man7.org/linux/man-pages/man0/stdint.h.0p.html) 中的敘述如下：
>The typedef name intN_t designates a signed integer type with width N, no padding bits, and a two's-complement representation.
藉由此敘述得知非符號整數，以十進位表示法範圍為： $[0,255]$ 。`buf[n] % (sizeof(charset) - 1)` 從數學角度解釋，此處是對於 $x\equiv i \pmod{26}$ 選定索引的過程。
藉由[除法原理](https://en.wikipedia.org/wiki/Euclidean_division)可以得到 $$
255 = 26 \times 9 + 21.$$
換句話說 0 到 25 數字的倍數在 0 至 255 中，除了 22, 23, 24, 25 倍數之外皆出現 10 次。
**假設 `randombytes` 給定的隨機數是均勻且彼此獨立的**，在此之下 0 到 21 數字倍數出現的頻率為 10， 22, 23, 24, 25 倍數為 9 。假設 0 到 25 對應到小寫英文 a 到 z ，其離散機率分佈表示為 $$
P(X=i) =
\begin{cases}
\dfrac{10}{256}, \text{ for } i=0,1,\dots,21 ,\\
\dfrac{9}{256}, \text{ for } i=22,23,24,25.
\end{cases} $$ 得知隨機生成的字元頻率不均勻。
`wuyihung` 使用 Python 設計一個[測試腳本](https://github.com/wuyihung/lab0-c/blob/master/scripts/test_prng.py)驗證上述理論上的情況。
他藉由重複執行 `ih RAND 30` $150,000/30$ 次後，將串列內所有的字串連接（ concatenate ）成一個字串，並使用 [`ent`](https://www.fourmilab.ch/random/)分析字串的 entropy 。發現理論跟實際有些許誤差（約 $0.0009$ ）。
```diff
- randombytes((uint8_t *) buf, len);
+ uint64_t *randstr_buf_64 = malloc(len * sizeof(uint64_t));
+ randombytes((uint8_t *) randstr_buf_64, len * sizeof(uint64_t));
for (size_t n = 0; n < len; n++)
- buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+ buf[n] = charset[randstr_buf_64[n] % (sizeof(charset) - 1)];
+ free(randstr_buf_64);
```
他改用 `uint64_t` 來改善隨機字串的生成過程。其想法很簡單，就是藉由把上述 8 bits 改成用 64 bits 表示，在上述分佈的分母由 $2^8$ 改為 $2^{64}$ 從除法原理得知：
$$2^{64} = 709490156681136600 \times 26 + 16$$ 其離散機率分佈表示為
$$
P(X=i) =
\begin{cases}
\dfrac{709490156681136601}{2^{64}}, \text{ for } i=0,1,\dots,16 ,\\
\dfrac{709490156681136600}{2^{64}}, \text{ for } i=17,18,\dots,24,25.
\end{cases} $$
參照他的實驗方式，此處將使用 `uint8_t` 和 `uint64_t` 的結果用 Python 套件 matplotlib 將數據以長條圖（ bar plot ）呈現。
採用 `uint8_t`：
總共 1050988 個字元。從 a 到 z 的頻率：
`[41080, 41161, 40861, 41197, 41150, 40723, 40969, 41191, 41006, 41099, 41278, 41312, 41146, 40890, 41113, 40846, 36915, 36894, 41141, 41231, 41035, 41269, 40993, 40905, 36696, 36887]`
採用 `uint64_t`：
總共 1049822 個字元。從 a 到 z 的頻率：
`[40629, 40651, 40560, 40750, 40237, 40244, 39793, 40428, 40261, 40372, 40540, 40571, 40310, 40795, 40222, 39952, 40452, 40058, 40700, 40048, 40713, 40398, 40332, 40431, 40047, 40328]`
`sizeof()` 在 C99 6.5.3.4 The sizeof operator 描述中也是回傳 `unsigned integer type`
> The value of the result is implementation-defined, and its type (an unsigned integer type) is size_t, defined in <stddef.h> (and other headers).
由於 `charset` 占用的記憶體大小固定，以 `26U` 取代 `sizeof(charset) - 1`
採用 `uint8_t` 並且使用 `26U` 取代 `sizeof(charset) - 1`取模：
```diff
- buf[n] = charset[buf[n] % (sizeof(charset) - 1)];
+ buf[n] = charset[buf[n] % 26U];
```
總共 1050391 個字元。從 a 到 z 的頻率：
`[40987, 41617, 40995, 41252, 41100, 40988, 40903, 41212, 40949, 40610, 40903, 41089, 41100, 40931, 41208, 40949, 40958, 40686, 41270, 41415, 40921, 40946, 37085, 36880, 36761, 36676]`
## 排序論文
### Bottom-up Mergesort
[閱讀筆記： Bottom-up Mergesort](https://hackmd.io/8Bf8P0OqTxmdSG22aPB3qw)
合併排序法的三種比較情況可以概括成：$$C(N)=N\log_2N+NP(\log_2N)+\text{low order terms}$$ 其中 $P(x)$ 為週期為 $1$ 的週期函數， Panny 和 Prodinger 以 Flajolet 和 Golin 在 1993 年使用梅林轉換（ Mellin Transforms ） 對 top-down 合併排序遞迴過程做漸進分析。
## 定點數與逼近
<!-- 多項式逼近法待更新
設 $f$ 在一個包含 $a$ 的區間中，在點 $a$ 有 $n+1$ 次可導，則對區間中任意 $x$ 有 $n$ 階泰勒展開式： $$P_n(x)=f(a)+\sum_{k=1}^n \frac{f^{(n)}}{n!}(x-a)^n + R_n(x).$$ 剩餘項 $R_n(x)$ 有多種表示形式，以微分均值定理推得的拉格朗日餘項表示式： $$R_n(x) = \dfrac{f^{(n+1)}(\xi)}{(n+1)!}(x-a)^{(n+1)},\quad \text{ $\xi$ is between $x$ and $a$}$$
從上述剩餘項可以看到，只要當 $f$ 是一個夠好的函數（在點 $a$ 可導的次數越高越好，如三角函數、指數函數這種定義域中任意點可以無窮可導的函數就是很好的函數，同時無窮可導的函數又叫光滑函數（ smooth function ）），泰勒多項式 $P_n(x)$ 與原函數 $f(x)$ 在點 $a$ 附近就會十分接近。
舉例來說，代 $n=3$ 、 $x=a+0.1$，上述剩餘項也就是誤差項為：$$R_3(a+0.1)=\dfrac{f^{(4)}(\xi)}{4!}(0.1)^4$$ 此處 $\xi \in(a, a+0.1)$ 此處再分析 $f^{(4)}(\xi)$ 在區間 $(a,a+0.1)$ 的行為，就可以得知 $R_3(a+0.1)$ 的上下界。
同時一般微積分教課書，在微分當中常見到的一個例子：給定可微分函數 $f$ 求在點 $x_0$ 切線的切線方程。而早在高中教科書中，我們就學習過這個數學式子——點斜式 $$f(x)-f(x_0)=f'(x_0)(x-x_0)$$ 仔細看，這就是一階泰勒多項式。為什麼很多教課書在微分求切線方程的章節會放入近似估計的例題，就是因為這裡以切線作為一階泰勒多項式逼近原函數在點 $x_0$ 附近的值。
在數值分析中，對原連續函數逼近產生的誤差也被稱作**截斷誤差（ truncation error ）**。
考慮以二為底的對數函數 $$f(x)=\log_2 x,\quad x>0.$$ 其 $n$ 次微分為 $$f^{(n)}(x)=\dfrac{(-1)^{(n+1)}(n-1)!}{x^n\ln(2)},\quad x>0.$$
則以二為底的對數函數在點 $a$ 其 $n$ 階泰勒展開為： $$P_n(x)=f(a)+\sum_{k=1}^n \dfrac{(-1)^{(k+1)}(n-1)!}{a^k\ln(2)}(x-a)^k + R_n(x)$$ -->
### 定點數
定點數(fixed-point)與數學中提到的固定點定理不同，為一種分數表示方法，例如，新台幣以整數 $1$ 為基本單位，與新台幣不同，美元以一美分為基本單位，通常表示下會以 $0.01$ 美元表示，其中，$\frac{1}{100}=1\times \frac{1}{100}$，定點數為 $1$ 乘以一係數 $1/100$。以此概念建構美元整數表示法，五美分則為 $5$，二十五美分為 $25$，一美元為 $100$ 以此類推。
總的來說定點數就是一分數表示法，以整數型態儲存，計算實際值時會乘上一係數。
在 C99 擴展規範之一 ISO/IEC TR 18037:2008 — 針對嵌入式裝置的定點數規範，內容涵蓋定點數型態定義方式、命名名稱建議、定點數運算子規範等等。
在 4.2 Detailed changes to ISO/IEC 9899:1999 小節中，兩個 C99 擴展條文描述定點數形式
* Clause 5.2.4.2.3 - Characteristics of fixed-point types
一定點數 $x$ 定義為：
$$
x= s\times n \times b^f
$$
其中，$s$ 為正負號(-1 或 1)；
$p$ 為精度；
$n$ 為一非負整數且小於 $b^p$；
$b$ 為一基數，在二進位系統中通常為 $2$；
$f$ 為一係數，用於表示小數部分的位數。
舉例來說，以 16 位元的有號整數來表示一定點數 $x$，其中 4 個位元用於表示分數部分，11 個位元用於表示整數部分，1 個位元用於表示正負號。$f=-4$、$p=11+4=15$、$0\leq n <2^{15}$。假如有一定點數為 $549$ 其二進位表示為 `0000 0010 0010 0101` 則此定點數 $x$ 實際數值為
$$
x = 549 \times 2^{-4} = 34.3125 = 2^5 + 2^1 + 2^{-2}+2^{-1}
$$
* Clause 6.2.6.3 - Fixed-point types
* 對有號定點數，可以將位元分成三個部分：
1. 正負號位元(sign bit)
2. 數值位元(value bits)
3. 填充位元(padding bits)
對於數值位元又可以分成：
1. 整數位元(integral bits)
2. 分數位元(fractional bits)
其中，假如數值位元為 $N$ 個且整數位元為 $L$ 個，則分數位元部分為 $N-L$ 個。對於用於表示純分數的定點數，該整數位元為 $L=0$ 個，則每一數值位元用於表示在 $2^{-1}$ 到 $2^{-N}$ 之間不同 $2$ 的冪，所以該定點數的實際數值範圍為 $-1$ 至 $1-2^N$；
對於用於表示帶分數的定點數，則每一數值位元用於表示在 $2^{L-1}$ 到 $2^{N-L}$ 之間不同 $2$ 的冪，所以該定點數的實際數值範圍為 $-2^L$ 至 $2^L-2^{N-L}$。
* 對無號定點數，可以將位元分成兩個部分：
1. 數值位元(value bits)
2. 填充位元(padding bits)
對於數值位元又可以分成：
1. 整數位元(integral bits)
2. 分數位元(fractional bits)
其中，假如數值位元為 $N$ 個且整數位元為 $L$ 個，則分數位元部分為 $N-L$ 個。對於用於表示純分數的定點數，該整數位元為 $L=0$ 個，則每一數值位元用於表示在 $2^{-1}$ 到 $2^{-N}$ 之間不同 $2$ 的冪，所以該定點數的實際數值範圍為 $0$ 至 $1-2^{-N}$；
對於用於表示帶分數的定點數，則每一數值位元用於表示在 $2^{L-1}$ 到 $2^{N-L}$ 之間不同 $2$ 的冪，所以該定點數的實際數值範圍為 $0$ 至 $2^L-2^{N-L}$。
常用的定點數表示法為 Q-format，以 Qm.f 表示，其中 m 為整數位元個數及 f 為分數位元個數。例如，以二補數系統中的有號 16 位元整數，定點數表示有 11 個整數位元、 4 個分數位元，及 1 個正負號位元，則 Q-format 表示為 Q11.4。
### 對數逼近
有了定點數表示法後，就可以明確寫出函數的**定義域與對應域範圍**。
$$
\tilde{f}(x) \approx \log_2(x)
$$
假設使用的定點數系統為 Qm.f，也就是使用 m 個整數位元、 f 個分數位元，及 1 個正負號位元。
其中 $\tilde{f}(x)$ 為一逼近函數， $x$ 為有號整數，在定點數表示下定義域為 $[0, 2^{m}-2^{f}]$，對應域為 $[-2^m,2^m-2^{f}]$。
可能有些人會有疑問是，為何定義域包含 $0$？為何對應域設定下界為 $-2^m$ 及上界為 $2^f$？這是因為逼近函數邊界映射為 $\tilde{f}(0)=-2^m$ 和 $\tilde{f}(2^m-2^{f})=2^m-2^{f}$。
以下算法參考 [`log2fix`](https://github.com/dmoulding/log2fix) 實作方式，依據 [A Fast Binary Logarithm Algorithm](http://www.claysturner.com/dsp/BinaryLogarithm.pdf) 中提及的算法實作，該算法與計算平方根中的十分逼近法相似，皆是計算一位元接一位元計算出近似值。
$x$ 為輸入，由對數表示輸出 $y$：
$$
y = \tilde{f}(x) \approx \log_2(x)
$$
則
$$
x = 2^y
$$
假設輸出 $y$ 的位元向量表示式寫為 $[b_{m+f+1},b_{m+f},b_{m-1+f},\dots,b_{f},b_{f-1},\dots,b_{1}]$ 其中 $b_i$ 的對應關係為
$$
(-1)^{b_{m+f+1}}\times\sum^{m+f}_{i=1} b_{m+f+1-i}\times 2^{m-i}
$$
**在此求解對數逼近的問題變成找出所有 $b_i$，其中 $i$ 從 $1$ 至 $m+f+1$。**
先討論正負號位元以外的情況。
將 $y$ 以十進位表示可以寫成
$$
\begin{align}
y
&= b_{m+f}\times 2^{m-1} + b_{m-1+f}\times 2^{m-2} + \dots +b_{f+1}\times2^0 \\
&\quad + b_{f}\times 2^{-1} + b_{f-1} \times 2^{-2} +\dots +b_{1} \times 2^{-f} \\
&=
\end{align}
$$
為了以迭代方式計算，改寫成巢狀結構來表示則為
$$
y = 2^{-1}(b_1+b_22^{-1}+\dots+b_n\times 2^{-(n-1)})
$$
將其代入 $x=2^{y}$ 則得到
$$
x= 2^{2^{-1}(b_1+b_22^{-1}+\dots+b_n\times 2^{-(n-1)})}
$$
兩側平方後得到
$$
\begin{align}
x^2
&= 2^{(b_1+b_22^{-1}+\dots+b_n\times 2^{-(n-1)})} \\
&= 2^{b_1}\times 2^{(b_22^{-1}+\dots+b_n\times 2^{-(n-1)})}
\end{align}
$$
在此會有兩個情況
1. $b_1=0$
$$
x^2 = 2^{(b_22^{-1}+\dots+b_n\times 2^{-(n-1)})}
$$
2. $b_1=1$
$$
x^2 = 2\times2^{(b_22^{-1}+\dots+b_n\times 2^{-(n-1)})}
$$
## 參考資料
* [GNU make](https://www.gnu.org/software/make/manual/make.html)
* [lab0 說明](https://hackmd.io/@sysprog/linux2024-lab0/%2F%40sysprog%2Flinux2024-lab0-a)
* [C99 規格書](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* [GCC online documentation](https://gcc.gnu.org/onlinedocs/)
* [graphviz 範例](https://hackmd.io/@sysprog/linked-list-quiz)
* [The On-Line Encyclopedia of Integer Sequences® (OEIS®)](https://oeis.org/)
Sign in with Wallet
Connect another wallet