# 2021q1 Homework1 (quiz1)
contributed by < [`toastcheng`](https://github.com/toastcheng) >
###### tags: `linux2021`
## Q1. 運作原理
> 重新回答第 1 周測驗題，附帶的「延伸問題」也需要完成
解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
先看程式內容，主要分為三個部分：
1. 資料結構的定義
2. Quicksort 排序演算法
3. 便於測試的函式
以下逐一說明。
### 1. 資料結構的定義
資料結構 `__node` 定義了此連結串列 (linked list) 中的節點長相，由一個整數作為節點的值，以及一個 `__node` 的指標指向連結串列中的下一個節點。
```c=
typedef struct __node {
int value;
struct __node *next;
} node_t;
```
### 2. Quicksort 排序演算法
#### `list_add_node_t`: 將`node`接在`*list`的開頭。
```c=
static inline void list_add_node_t(node_t **list, node_t *node) {
node_t->next = *list;
*list = node;
}
```
其中由兩個動作完成，考慮最初的情況，`list` 型別為 `node_t` 的指標的指標，對其取值可以得到某個節點的位址，在此用 `node0`、`node1`、...代表以節點 `*list` 為首的連結串列。
1. 執行函式前
```graphviz
digraph G {
rankdir=LR;
more [label="..." shape=plaintext]
null [label="null" shape=plaintext]
pp [label="list" shape=plaintext]
p [label="&node0" shape=plaintext width=0.1]
node [shape=record]
n [label = "{<addr> node |<next>}"]
n0 [label="{<addr> node0|<next>}"]
n1 [label="{<addr> node1|<next>}"]
n2 [label="{<addr> node2|<next>}"]
pp -> p;
p -> n0;
n -> null;
n0 -> n1 -> n2 -> more;
}
```
2. `node->next = *list;`
將 `node` 的指向的下一個節點位址設定成 `list` 的取值，即 `node0` 的位址。
```graphviz
digraph G {
rankdir=LR;
more [label="..." shape=plaintext]
pp [label="list" shape=plaintext]
p [label="&node0" shape=plaintext width=0.1]
node [shape=record]
n [label = "{<addr> node |<next>}"]
n0 [label="{<addr> node0|<next>}"]
n1 [label="{<addr> node1|<next>}"]
n2 [label="{<addr> node2|<next>}"]
n:next -> n0:addr [color=red];
pp -> p;
p -> n0;
n0 -> n1 -> n2 -> more;
}
```
3. `*list = node;`
```graphviz
digraph G {
rankdir=LR;
more [label="..." shape=plaintext]
pp [label="list" shape=plaintext]
p [label="&node" fontcolor=red shape=plaintext]
node [shape=record]
n [label = "{<addr> node |<next>}"]
n0 [label="{<addr> node0|<next>}"]
n1 [label="{<addr> node1|<next>}"]
n2 [label="{<addr> node2|<next>}"]
n:next -> n0:addr [color=red];
pp -> p;
p -> n0 [color=gray];
p -> n [color=red];
n0 -> n1 -> n2 -> more;
}
```
#### `list_concat`: 將`*left`的最後一個節點接上`*right`的第一個節點。
```c=
static inline void list_concat(node_t **left, node_t *right) {
while (*left)
/* LLL */ left = &((*left)->next);
*left = right;
}
```
1. 執行函式前
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left0" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> l -> l0;
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
}
```
2. `while (*left)
left = &((*left)->next);`
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left0" shape=plaintext]
l1_p [label="&((*left1)->next)" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> l1_p [color=red];
ll -> l [color=gray];
l1_p -> l1:next;
l -> l0;
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
more_l -> ln;
}
```
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
null [label="null" shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left0" shape=plaintext]
ln_p [label="&((*leftN)->next)" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
ln [label = "{<addr> leftN |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> ln_p [color=red];
ln_p -> ln:next;
l -> l0;
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
more_l -> ln;
ln -> null;
}
```
3. `*left = right;`
將左右接上。
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left0" shape=plaintext]
ln_p [label="&((*leftN)->next)" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
ln [label = "{<addr> leftN |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> ln_p [color=red];
ln_p -> ln:next;
l -> l0;
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
more_l -> ln;
ln -> r0;
}
```
LLL 的部分一開始沒有想通 (c\) 及 (d) 的差異，故以下花一點篇幅紀錄思考的過程：
- (a) left = left->next
錯誤。`left` 為 `node_t` 的指標的指標， dereference 後不應該有 `next` 這個屬性。
- (b) left = (*left)->next
錯誤。`left` 為 `node_t` 的指標的指標，而 `node_t.next` 為 `node_t` 的指標，不應該指派 `node_t*` 型別的值給 `left`。
- (c\) left = &((*left)->next)
正確。如函式說明，
- (d) *left = (*left)->next
錯誤。這和 (c\) 的差別非常的微妙，兩者看似行為相同，但如果作圖出來其實能發現差異：
以執行 while 迴圈第一次迭代為例，(c\) 的行為:
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left0" shape=plaintext]
l1_p [label="&((*left1)->next)" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> l1_p [color=red];
l1_p -> l1:next;
l -> l0;
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
more_l -> ln;
}
```
而 (d) 的行為：
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&left1" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> l;
l -> l0 [color=gray];
l -> l1 [color=red];
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
}
```
差別在於 (c\) 不會改動到 `left` 指向的位址，只改動 `left` 本身的值，因為 `left` 是以 copy 的形式傳進函式，所以執行完後，外層的 `*left` 依然是第一個節點。
相對的 (d) 不改 `left` 本身的值，而是修改 `left` 指向的位址，雖然看似執行 while 迴圈時，有正確的走訪各個節點，但函式執行完後 `*left` 指向的節點會是 `right` ，而不是第一個節點。
```graphviz
digraph G {
rankdir=LR;
node [shape=record]
more_l [label="..." shape=plaintext]
more_r [label="..." shape=plaintext]
ll [label="left" shape=plaintext]
l [label="&right0" shape=plaintext]
rr [label="right" shape=plaintext]
l0 [label = "{<addr> left0 |<next>}"]
l1 [label = "{<addr> left1 |<next>}"]
l2 [label = "{<addr> left2 |<next>}"]
ln [label = "{<addr> leftN |<next>}"]
r0 [label = "{<addr> right0 |<next>}"]
r1 [label = "{<addr> right1 |<next>}"]
r2 [label = "{<addr> right2 |<next>}"]
ll -> l;
l -> r0 [color=red];
l -> l0 [color=gray];
rr -> r0;
r0:next -> r1:addr;
r1:next -> r2:addr;
r2:next -> more_r;
l0:next -> l1:addr;
l1:next -> l2:addr;
l2:next -> more_l;
more_l -> ln;
ln -> r0;
}
```
#### `quicksort`: 執行 quick sort 主要邏輯的函式。
```cpp
void quicksort(node_t **list)
{
if (!*list)
return;
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? /* AAA */ &right : /* BBB */ &left, n);
}
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
/* CCC */ list_concat(&result, pivot); list_concat(&result, right);
*list = result;
}
```
以下是對應程式碼解說。
首先處理空值的狀況，函式直接回傳。
```cpp
if (!*list)
return;
```
接著指定連結串列的第一個節點為 `pivot`。
以 `pivot` 的值為分界，將連結串列從頭到尾走訪過一遍，將值大於 `pivot` 的節點附加在 `right` ，否則附加在 `left`。
```cpp
node_t *pivot = *list;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? /* AAA */ &right : /* BBB */ &left, n);
}
```
根據這樣的邏輯 `AAA` 及 `BBB` 應分別是代表 `right` 和 `left` 的兩個連結串列，又 `list_add_node_t()` 預期的資料型別是指標的指標，因此應該分別填入 `&right` 及 `&left`。
最後遞迴地對 `left`、`right` 執行 quicksort 。
宣告一個新的連結串列 `result`，將兩個遞迴的執行結果 `left` 和 `right` 依序串接。
```cpp
quicksort(&left);
quicksort(&right);
node_t *result = NULL;
list_concat(&result, left);
/* CCC */ list_concat(&result, pivot); list_concat(&result, right);
*list = result;
```
依據 quicksort 的需求，排序好的連結串列其值要由小到大，因此將 `left`、`pivot`、`right` 串接的順序應該是：`left -> pivot -> right`，因此 `CCC` 應為 `list_concat(&result, pivot); list_concat(&result, right)`。
### 3. 便於測試的函式
```cpp
static bool list_is_ordered(node_t *list) {
bool first = true;
int value;
while (list) {
if (first) {
value = list->value;
first = false;
} else {
if (list->value < value)
return false;
value = list->value;
}
list = list->next;
}
return true;
}
```
```cpp
static void list_display(node_t *list) {
printf("%s IN ORDER : ", list_is_ordered(list) ? " " : "NOT");
while (list) {
printf("%d ", list->value);
list = list->next;
}
printf("\n");
}
```
其中還有兩個在 `main()` 呼叫但沒有實作的函式：
```cpp
void list_free(node_t **list) {
while (*list) {
node_t* tmp = *list;
*list = (*list)->next;
free(tmp);
}
}
```
```cpp
static inline node_t* list_make_node_t(node_t *list, int val) {
node_t* n;
n = malloc(sizeof(node_t));
n->value = val;
node_t **ll = &list;
while (*ll) {
ll = &((*ll)->next);
}
*ll = n;
return list;
```
---
### 改善 random 的部分，並使用不同的 psuedorandom number generator (PRNG)
連續執行 quicksort ，可以發現 `random()` 函式所產生的數值其實都是相同的序列，可以被輕易預測且重現。
```shell
root@988da3fcde51:/data/week1/quiz1# ./quicksort
NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
root@988da3fcde51:/data/week1/quiz1# ./quicksort
NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
root@988da3fcde51:/data/week1/quiz1# ./quicksort
NOT IN ORDER : 359 966 105 115 81 255 74 236 809 205 186 939 498 763 483 326 124 706 84 1016
IN ORDER : 74 81 84 105 115 124 186 205 236 255 326 359 483 498 706 763 809 939 966 1016
```
這個現象直接和 PRNG 的機制有關，閱讀 [Wikikpedia: PRNG](https://en.wikipedia.org/wiki/Pseudorandom_number_generator)上的資料可以了解到， PRNG 本質上就是一個函數，給 PRNG 輸入，他就回應一個數，但他不只是函數，他是有狀態 (state) 的，他會將過去產生的隨機數保存下來（依照函數的行為，需要保存下來的數量也會不一樣），並用過去的隨機數來計算出下一個。這也是為什麼呼叫 `random()` 時不用帶參數，因為 `random()` 把已產生的隨機數存下來了。
參考 glibc 專案中的 `random.c`，可以看到 `random()` 計算用到的隨機表：
```cpp
static int32_t randtbl[DEG_3 + 1] =
{
TYPE_3,
-1726662223, 379960547, 1735697613, 1040273694, 1313901226,
1627687941, -179304937, -2073333483, 1780058412, -1989503057,
-615974602, 344556628, 939512070, -1249116260, 1507946756,
-812545463, 154635395, 1388815473, -1926676823, 525320961,
-1009028674, 968117788, -123449607, 1284210865, 435012392,
-2017506339, -911064859, -370259173, 1132637927, 1398500161,
-205601318,
};
```
再用圖示表示其中的運作：
```graphviz
digraph G {
rankdir=LR
node [shape=box]
seed [label="seed" shape=plaintext];
output [label="output" shape=plaintext];
seed -> r0:w;
r1 -> output;
subgraph cluster {
id="prng"
label="PRNG"
subgraph cluster2 {
label="random table"
r0->r1->r2->more->rn [style=invis];
r0 [label="r0"];
r1 [label="r1"];
r2 [label="r2"];
more [label="..." shape=plaintext];
rn [label="rN"];
}
fn [label="function"];
r0 ->fn -> r1;
}
}
```
```graphviz
digraph G {
rankdir=LR
node [shape=box]
output [label="output" shape=plaintext];
r2 -> output;
subgraph cluster {
id="prng"
label="PRNG"
subgraph cluster2 {
label="random table"
r0->r1->r2->more->rn [style=invis];
r0 [label="r0"];
r1 [label="r1"];
r2 [label="r2"];
more [label="..." shape=plaintext];
rn [label="rN"];
}
fn [label="function"];
r1 ->fn -> r2;
}
}
```
粗略地表示： $rand_i = function(rand_{i-1})$
PRNG 本質上的組成就是：
1. 一個數學函數
2. 一個變數存放上一個（或多個）產生的隨機數，如果是第一次呼叫，則用 seed 當作輸入。
照 man page 所述 `random()` 的 seed 預設是 1，所以很自然地每一次產生出來的隨機數會是相同的。
讓程式能夠每一次執行都有隨機的輸出就必須設置 seed 。最常見的做法是用目前的時間來當作 seed，如此就能達到每次執行都從不同的 seed 開始產生隨機數：
```cpp
char state[32];
initstate(time(NULL), state, sizeof(state));
setstate(state);
```
但看到 [linD026](https://hackmd.io/NCWueseZTYufmR65Zyb9fw?view) 同學提到，若有兩支 process 在相同的時間點執行該程式，確實會有兩支 process 產生相同隨機數序列的問題，依照同學的解法是用`*argv` 的地址來計算 seed，利用每次程式都會在不同的記憶體位址這個特性來區分不同的 process。
而我在此嘗試另一個方式，回憶起 `/dev/random` 和 `/dev/urandom` 可以得到透過蒐集硬體雜訊來生成真正意義上隨機數，若是先用其作為 seed，就能保證總是從隨機的 seed 開始生成隨機數。
[Wikipedia: /dev/random](https://en.wikipedia.org/wiki//dev/random)
最赤裸的方式是直接來讀 `/dev/random` ！
```cpp
int *seed = malloc(sizeof(int));
int randomData = open("/dev/urandom", O_RDONLY);
read(randomData, seed, sizeof(int));
char state[32];
initstate(*seed, state, sizeof(state));
setstate(state);
```
從 Linux 3.17 開始，加入 [getrandom](https://man7.org/linux/man-pages/man2/getrandom.2.html) 系統呼叫，因此可以將上面讀檔的行為簡化：
```cpp
int *seed = malloc(sizeof(int));
syscall(SYS_getrandom, seed, 4, 1);
char state[32];
initstate(*seed, state, sizeof(state));
setstate(state);
```
閱讀 man page 後了解到 `random()` 是一種 psuedorandom number generator，而更詳細地說，是一種nonlinear additive feedback random number generator，[The GLIBC random number generator](https://www.mathstat.dal.ca/~selinger/random/) 這篇文章針對 glibc 中 `random()` 的機制做了說明，雖然這篇文章是 2007 年撰寫的，對照現在的 glibc 原始碼並沒有落差。使用的演算法經過對照其設置 state 、產生隨機數的方式以及所使用的常數（例: 16807），是 [Lehmer random number generator](https://en.wikipedia.org/wiki/Lehmer_random_number_generator)，為一種 linear congruential generator (LCG) 演算法。但這一類的演算法被證實有著隨機數品質不佳的缺陷：
> - Shorter-than-expected periods for some seed states (such seed states may be called "weak" in this context);
> - Lack of uniformity of distribution for large quantities of generated numbers;
> - Correlation of successive values;
> - Poor dimensional distribution of the output sequence;
> - Distances between where certain values occur are distributed differently from those in a random sequence distribution.
簡單來說就是產生出來的隨機序列不符合我們對「隨機」的期待，像是：找得到規律、數字出現的頻率有高低之分等等。有趣的是儘管 LCG 被批評產生出來的隨機序列品質不佳，但仍被廣泛使用，Java 也不例外，因為產生隨機數的需求非常大。
> As an illustration, consider the widely used programming language Java. As of 2017, Java still relies on a linear congruential generator (LCG) for its PRNG, which are of low quality
做為改進，我參考了 [List of random number generators](https://en.wikipedia.org/wiki/List_of_random_number_generators) 列出的一大票 PRNG ，這其中我發現了一類特性十分有趣的演算法 [CBRNG](https://en.wikipedia.org/wiki/Counter-based_random_number_generator_(CBRNG)#Squares_RNG)，這也帶出了另外一個我沒想到的議題，前述如 LCG 類演算法都是一個一個地生成隨機數，而且理論上以好的 PRNG 來說前後兩個隨機數的關係應該要很難預測，也就是說要生成一組隨機序列免不了要序列地 (sequentially) 地執行。以至於這些 PRNG 「先天上」不太好受惠於現代多處理器、顯示卡等架構的平行運算加速。
例如我想要取得從 $rand_0$ 開始的 N 個隨機數，那我就必須從 N 開始計算 N 次，即便我有多個核心能夠平行計算，我還是得一個一個計算來。
但 CBRNG 這類的演算法並不一樣，CBRNG 在產生第 i 個隨機數 $r_i$ 時不必依賴於第 i - 1 個隨機數 $r_{i-1}$。這個特性讓 CBRNG 特別適合平行化運算。
我起初覺得 counter-based 這個形容詞不是很直觀，畢竟他的特色感覺比較像 hash function，不太懂為何會選擇 counter 這個字。但再進一步理解其運作原理後就能理解 CBRNG 的「上下文」了。CBRNG 並不是完全嶄新的概念，他其實參考了密碼學中的區塊加密 ([block cipher](https://en.wikipedia.org/wiki/Block_cipher)) 中的 counter mode。
區塊加密是指將明文以相等大小切割，一個區塊一個區塊加密的方式。而 counter mode 是將每個區塊的會有一個遞增 counter，先對這個 counter 用鑰匙加密，再對每個區塊的明文XOR。
而如果將 seed 當作鑰匙，省略與明文做 XOR 的步驟，每個區塊的輸出不也有不可預測性嗎？這是 CBRNG 的基本邏輯，非常巧妙，隨機數之間也沒有前後相依。
${\displaystyle \mathrm {PRNG} (i)=E(i,\mathrm {seed} )}$
詳細的資訊可以一覽 Udacity 上一系列[密碼學課程](https://www.youtube.com/playlist?list=PLAwxTw4SYaPnCeih6BPvJ5GdqqThGcWlX)。影片其中之一 [Prng Implementation - Applied Cryptography](https://youtu.be/3gNR7hEIlsY) 提及的 PRNG 實作方式就是一種 CBRNG。
這樣可以生產出非常密碼學上安全的隨機數，但是問題是比較耗時且許多應用並不要求這樣的安全性。因此 CBRNG 的發展方向就是追求更快的隨機數生成，放棄一定的安全性。
因此就照著這個方向找到了 Philox 和 Squares 這兩個 CBRNG，前者被近年許多軟體如 nVidia 的 curand 、Tensorflow 等使用，後者則是列表中最新的一個演算法，並沒有太多軟體實作，但其聲稱快過 Philox 而吸引了我的注意，其發表的論文中提到：
> It is significantly faster than Philox and produces data of equivalent or better quality.
以下列出兩篇論文分別介紹了 Philox 及 Squares：
1. [Parallel Random Numbers: As Easy as 1, 2, 3](http://www.thesalmons.org/john/random123/papers/random123sc11.pdf) 這篇論文，文內提及 Philox 演算法。
這篇論文非常詳細地討論一個好的 CBRNG 要有怎麼樣的取捨，由此說明 Philox 演算法的設計理由。
考量：週期為 $2^{64}$ 也不夠大，好的 PRNG 的重複週期應該要大到能讓人安心。
> One million cores, generating 10 billion random numbers per second, will take about half an hour to generate $2^{64}$ random numbers, which raises doubts
about the long-term viability of a single, unpararameterized PRNG with a periods of “only” $2^{64}$.
考量：現代的區塊加密都有很多次的 round，來模糊同一個 block 的明文和密文之間的關係，但太多次 round 對於 PRNG 來說並不必要。
> Most modern block ciphers consist of multiple iterations of simpler bijections, called “rounds.” Each round introduces some diffusion
>
> For example, 128-bit AES has 10 rounds, DES has 16
rounds, and 256-bit Threefish has 72 rounds.
以 PRNG 來說區塊加密的運算效率太低，也不用像 TLS 等其他應用那麼要求安全性，因此其改善方向：減少 round 的數量、限縮 data path、簡化 key schedule（用來藏 key的步驟）。
這裡參雜著許多資安領域的概念：[Feistel functions](https://www.youtube.com/watch?v=FGhj3CGxl8I&ab_channel=Computerphile) 以及 [SP network (Substitution–permutation network)](https://www.youtube.com/watch?v=DLjzI5dX8jc&ab_channel=Computerphile)，花了不少時間釐清他們之間的關係。
[Feistel functions](https://www.youtube.com/watch?v=FGhj3CGxl8I&ab_channel=Computerphile):
他有非常巧妙的性質，詳情可見 Computerphile 的說明，但簡單來說它透過 `B` 和 `F` 兩個函數的計算，可以把 `LR` 轉換成 `L'R'`，並且一一對應。
[SP network (Substitution–permutation network)](https://www.youtube.com/watch?v=DLjzI5dX8jc&ab_channel=Computerphile):
是更大的一個概念，由 S-box 和 P-box 組成，S-box 提供將輸入映射成不同值 (substitution) 的功能，而 P-box 則如圖所示，將每個輸入置換 (permutation)。
事實上 Fiestel function 其實就是一種 S-box。
作者利用兩個 instruction 來進行 Philox：
- $mulhi(a, b) = (a \times b) / 2^W$
- $mullo(a,b) = \lfloor (a \times b) \rfloor \space mod \space 2^W$
他們有以下性質：
- 給定奇數 M：mullo(a, M) 是 bijection 操作（一一映射）
例如：M = 3，W = 2，則 $mullo(a, M)$ 操作為 $\lfloor (a \times 3) \rfloor \space mod \space 4$ 。在$[0,4]$區間有：
0 -> 0
1 -> 3
2 -> 2
3 -> 1
這樣的一一映射。
- 給定常數 M：改動 a 的其中一個位元便會造成 $mulhi(a, b)$ 多個位元的改變（文中以雪崩 acalanche 形容）。
- Integer multiplication takes between 2 and 10 cycles on common high-performance architectures, but can generally be overlapped with other operations like addition, subtraction, and xor. （這不太懂）
- 在某些架構下如 x86、x86-64 ， mulhi 和 mullo 如果有相同的參數，將可以同時在一個指令下完成。
而這兩個指令的特性可以很巧妙的組成 Fiestel function，需要的 round 不多速度也快：
- $L' = B_k(R) = mullo(R,M)$
- $R' = F_k(R) \oplus L= mullo(R,M) \oplus k \oplus L$
其中$\oplus$為 XOR 運算。而 Philox 則是以 `mulhi` 和 `mullo` 組成的 Fiestel function 組成的 SP-network。
`// TODO: 加原始碼分析`
2. [Squares: A Fast Counter-Based RNG](https://arxiv.org/abs/2004.06278v3) 這篇論文是在 Philox 之後提出的演算法 Squares ，在此來嘗試用其代替原本的 PRNG。
```cpp
inline static uint32_t squares(uint64_t ctr, uint64_t key) {
uint64_t x, y, z;
y = x = ctr * key; z = y + key;
x = x*x + y; x = (x>>32) | (x<<32); /* round 1 */
x = x*x + z; x = (x>>32) | (x<<32); /* round 2 */
x = x*x + y; x = (x>>32) | (x<<32); /* round 3 */
return (x*x + z) >> 32; /* round 4 */
}
int main(int argc, char **argv) {
uint64_t *seed = malloc(sizeof(uint64_t));
syscall(SYS_getrandom, seed, 8, 0);
size_t count = 20;
node_t *list = NULL;
while (count--) {
list = list_make_node_t(list, squares((*seed)++,k) % 1024);
}
...
}
```
`// TODO: 加說明`
---
## Q2. 避免使用遞迴呼叫
> 參考 [Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/) 並重寫上述 quick sort 程式碼，避免使用遞迴呼叫
避免使用遞迴呼叫的方式
文章中提到使用遞迴呼叫雖然在程式碼上能夠更加簡潔以及更好實作，但也有些隱性地成本：
1. 函式呼叫與回傳需要時間。
2. 遞迴使用 call stack 來儲存每一個子問題的狀態，但其實 call stack 做的事也是用它自己管理的陣列來實作 stack 的功能，直接使用陣列的話會更有效率。
3. 再者使用 stack 會有 stack overflow 的問題，這樣的邏輯並不好在程式端處理，使用自己管理的陣列的話便能彈性地限制 stack 的最大深度。
```cpp
void quicksort(node_t **list)
{
#define MAX_LEVELS 1000
node_t* stk[MAX_LEVELS];
node_t *pivot;
node_t *dmy = malloc(sizeof(node_t));
node_t *r = dmy;
stk[0] = *list;
int i = 0;
while (i>=0) {
node_t* top = stk[i--];
if (top->next) {
pivot = top;
int value = pivot->value;
node_t *p = pivot->next;
pivot->next = NULL;
node_t *left = NULL, *right = NULL;
while (p) {
node_t *n = p;
p = p->next;
list_add_node_t(n->value > value ? &right : &left, n);
}
if (right) stk[++i] = right;
stk[++i] = pivot;
if (left) stk[++i] = left;
}
else {
r->next = top;
r = r->next;
}
}
*list = dmy->next;
}
```
用變數 `i` 紀錄現在的 `stack` 在什麼位置，每次迴圈的開始都進行 pop 的操作：
```cpp
node_t *top = stk[i--];
```
依照相對於 `pivot` 大小整理節點的步驟沒有不同。而分類完 `left` 和 `right` 之後，本來應該各自遞迴計算的部分換成「放進 stack 中」。
這裡的順序至關重要：
```cpp
if (right) stk[++i] = right;
stk[++i] = pivot;
if (left) stk[++i] = left;
```
因為希望能先處理小的節點，所以必須先放 `right`，接著 `pivot`，最後 `left`，而 `left` 會最先被 pop 出來計算。每當從 stack 拿出單獨的節點，因為放入 stack 的順序一定會先處理值小的節點，所以可以保證單獨的節點都會是目前最小的，因此可以加入排序好的連結串列 `r` 中。
但有趣的是，文章作者在發佈的三年後補充提到其實作並不一定比常見的遞迴版本要好，建議讀者還是自行比較。
`// TODO`
---
## Q3. Linux-list
> Linux 核心內部也有 linked list 實作，但是 circular doubly-linked list，[linux-list](https://github.com/sysprog21/linux-list) 仿效 Linux 核心的實作並予以簡化，在 `examples/` 目錄提供 quick sort 實作，請探討 Linux 的 linked list 和上述程式碼的落差，並改寫 [linux-list](https://github.com/sysprog21/linux-list) 的 quicksort 範例，避免使用遞迴呼叫
參考資料: [The Linux Kernel API - List Management Functions](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html)
在 `linux-list` 中 quicksort 演算法實作在 `list_qsort` 這個函式之中，查看可以發現跟 quiz1 最初的 quicksort 十分雷同：
1. 選用連結串列的第一個節點為 pivot。
2. 宣告 `list_less` 及 `list_greater` 分別存放比 pivot 小及大的節點，同 quiz1 中的 `left` 和 `right`。
3. 遞迴地對 `list_less` 及 `list_greater` 執行。
4. 將結果連接起來。
```cpp
static void list_qsort(struct list_head *head)
{
struct list_head list_less, list_greater;
struct listitem *pivot;
struct listitem *item = NULL, *is = NULL;
if (list_empty(head) || list_is_singular(head))
return;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);
pivot = list_first_entry(head, struct listitem, list);
list_del(&pivot->list);
list_for_each_entry_safe (item, is, head, list) {
if (cmpint(&item->i, &pivot->i) < 0)
list_move_tail(&item->list, &list_less);
else
list_move(&item->list, &list_greater);
}
list_qsort(&list_less);
list_qsort(&list_greater);
list_add(&pivot->list, head);
list_splice(&list_less, head);
list_splice_tail(&list_greater, head);
}
```
相較於 quiz1 不同之處在於連結串列的資料結構有所不同，`linux-list` 中的 `listitem` 定義如下：
```cpp
struct listitem {
uint16_t i;
struct list_head list;
};
```
```cpp
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
除了 `next` 之外，還多了 `prev` 指標來指向連結串列的前一個節點，實作成 doubly-linked list。而再觀察 `list.h` 中幾個用於操作連結串列的函式可以發現：
```cpp
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
```
他還是一個環狀 (circular) 的連結串列，如果都透過 `list_` 開頭的函式對其操作，將可以確保第一個節點的 `prev` 會指向最後一個節點；最後一個節點的 `next` 會指向第一個節點。
既然他是環狀連結串列，那照一般的方式走訪每個節點將不斷的循環，而讓 quicksort 在比對每個節點跟 pivot 值的大小時不重複走訪同一個節點的是 `list_for_each_entry_safe` 這個 macro，這是一個將 for 迴圈的初始條件、終止條件、更新值的部分封裝起來的 macro 。
```cpp
#define list_for_each_entry_safe(entry, safe, head, member) \
for (entry = list_entry((head)->next, __typeof__(*entry), member), \
safe = list_entry(entry->member.next, __typeof__(*entry), member); \
&entry->member != (head); entry = safe, \
safe = list_entry(safe->member.next, __typeof__(*entry), member)
```
防止重複走訪節點的邏輯在 `&entry->member != (head)`，當發現回到 `head` 時終止 for 迴圈。
將 `linux-list` 避免使用遞迴呼叫的方式：
`// TODO`
---
## Q4. 高效率linked list排序演算法
> 研讀 Ching-Kuang Shene (冼鏡光) 教授撰寫的 [A Comparative Study of Linked List Sorting Algorithms](https://pages.mtu.edu/~shene/PUBLICATIONS/1996/3Conline.pdf)，思考高效率的 linked list 排序演算法，並落實於上述 (3) 的程式碼中
`// TODO`
## 參考資料
* [Graphviz](https://graphviz.org/pdf/dotguide.pdf)
* [用隱形的 edge 讓 nodes 對齊](https://stackoverflow.com/questions/33959969/order-cluster-nodes-in-graphviz)
Sign in with Wallet
Connect another wallet