# 2023q1 Homework1 (lab0)
contributed by < `SPFishcool` >
## 開發環境
```shell
$ neofetch --stdout
OS: Ubuntu 22.04.1 LTS x86_64
Host: GL552VW 1.0
Kernel: 5.15.0-60-generic
Uptime: 13 hours, 20 mins
Packages: 1877 (dpkg), 9 (snap)
Shell: bash 5.1.16
Resolution: 1920x1080
DE: GNOME 42.5
WM: Mutter
WM Theme: Adwaita
Theme: Yaru [GTK2/3]
Icons: Yaru [GTK2/3]
Terminal: gnome-terminal
CPU: Intel i5-6300HQ (4) @ 3.200GHz
GPU: Intel HD Graphics 530
GPU: NVIDIA GeForce GTX 960M
Memory: 3626MiB / 11868MiB
$ gcc -v
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04)
```
## lab0 資料架構認識
### list_head
- list_head 負責作為鏈結串列將其 entry 串連在一起，其為 Circular Doubly-linked list 類型
:::warning
注意書寫: doubly-linked list，連字號的位置在 doubly 和 linked 之間。
:notes: jserv
:::
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
head [label="{<prev>prev|<next>next}"];
color=invis;
label=list_head
}
}
```
- list_head架構圖
:::warning
使用 Graphviz 製圖並嵌入到 HackMD 頁面。
:notes: jserv
收到！正在改進中！
:::
- list_head的struct為：
```c
struct list_head {
struct list_head *prev;
struct list_head *next;
};
```
### element_t
- `element_t` 為佇列儲存 value，內部有 `list_head` 架構的 list 能夠將所有 `element_t` 串接起來
```graphviz
digraph list {
rankdir=LR;
node[shape=record, style=bold];
subgraph cluster_0 {
value [label="{*value}"];
list [label="list", shape=plaintext]
head [label="{<prev>prev|<next>next}"];
label=element_t;
}
}
```
- element_t 架構圖
- element_t 的 struct 為：
```c
typedef struct {
char *value;
struct list_head list;
} element_t;
```
- 因此 lab0 實做的佇列結構會是
### queue_chain_t
- 在執行 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 時，會先 create 一個 `queue_chain_t` 結構的物件，其功用類似上述佇列結構的 **head**，目的是每當 `q_new` 一個新的佇列時會將新的佇列利用 list_add_tail 加入到 `queue_chain_t` 鏈結串列的最後面。
>
>queue_chain_t 架構圖，size 為佇列的數量
```c
typedef struct {
struct list_head head;
int size;
} queue_chain_t;
```
### queue_contex_t
- `queue_contex_t` 在紀錄每一條佇列的資訊，`*q` 為 pointer of queue head，`size` 是佇列裡面 element_t 的數量，`chain` 為與其他 `queue_contex_t` 串連的 `list_head`。
>
>queue_contex_t架構圖
```c
typedef struct {
struct list_head *q;
struct list_head chain;
int size;
int id;
} queue_contex_t;
```
- 再加入 `queue_chain_t` 其完整佇列架構就完成了！
>
>queue 為上圖的紅色虛線部份
## lab0 開發過程
### q_new
`q_new()` 會先配置 `list_head` 大小的記憶體位置，接下來判斷是否配置成功，最後 `INIT_LIST_HEAD(new)` 會將這個 node 接回自己（成為 Doubly-linked list 型態）。
```c
struct list_head *q_new()
{
struct list_head *new = malloc(sizeof(struct list_head));
// check if space allowed
if (!new)
return NULL;
INIT_LIST_HEAD(new);
return new;
}
```
### q_free
`q_free()` 從 `head->next` (第一個有entry的節點)開始釋放，直到回到 head 最後釋放 head 節點。
```c
void q_free(struct list_head *l)
{
if (!l)
return;
struct list_head *indirect = l->next;
struct list_head *tmp = NULL;
while (indirect != l) {
tmp = indirect;
indirect = indirect->next;
q_release_element(list_entry(tmp, element_t, list));
}
free(l);
}
```
### q_insert_head / q_insert_tail
兩者可以使用 [list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h) 中的 `list_add` 與 `list_add_tail` 將 `element_t` 內的list加入鏈結串列中。
```c
bool q_insert_head(struct list_head *head, char *s)
{
if (!(head && s))
return false;
element_t *new_ele = malloc(sizeof(element_t));
if (!new_ele)
return false;
new_ele->value = (char *) malloc(strlen(s) * sizeof(char) + 1);
if (!new_ele->value) {
free(new_ele);
return false;
}
strncpy(new_ele->value, s, strlen(s) + 1);
// struct list_head *new_node = (new_ele -> list);
list_add(&new_ele->list, head);
return true;
}
```
### q_remove_head/q_remove_tail
remove 只有將 element_t 的串列節點從佇列中移除並沒有釋放其空間，因此只需要將其 next 與 prev 連接起來即可移除。
```c
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
struct list_head *indirect = head->next; //or head->prev (q_remove_tail)
list_del(indirect);
element_t *ele = list_entry(indirect, element_t, list);
if (sp)
{
strncpy(sp, ele->value, bufsize-1);
*(sp+bufsize-1) = '\0';
}
return ele;
}
```
### q_size
`q_size` 則從 `head->next` 開始計算這條佇列的 `element_t` 數量，並且回傳 `i` (count 後的結果)
```c
int q_size(struct list_head *head)
{
if (!head)
return -1;
struct list_head *indirect = head->next;
int i = 0;
while (indirect != head) {
i++;
indirect = indirect->next;
}
return i;
}
```
### q_delete_mid
因為佇列是 doubly-linked list 結構，因此可以使用左右指標（最左和最右可以快速找到），其原理是每一迴圈 `left_node` 往右走一步，`right_node` 往左走一步，直到兩指標相遇（奇數 element）或相鄰（偶數 element）時 right_node 就是我們要找的節點。
優點：跟快慢指標相比，迴圈節省了一半的次數（僅限 Circular Doubly-linked list）。
```c
bool q_delete_mid(struct list_head *head)
{
while(!head || list_empty(head))
return false;
struct list_head *left_node = head->next;
struct list_head *right_node = head->prev;
while ((left_node->next != right_node) && (left_node != right_node)) {
left_node = left_node->next;
right_node = right_node->prev;
}
list_del(right_node);
q_release_element(list_entry(right_node, element_t, list));
return true;
}
```
### q_delete_dup
`q_delete_dup` 這個 question 我紀錄此次和前次的比較紀錄，而受到「判決」的節點為
`indirect->prev`(目前指到的節點的前一個節點)
- `cmp`：`indirect` 與 `indirect->prev` 的比較結果
- `prev_cmp`：`indirect->prev` 與 `indirect->prev->prev` 的比較結果
不管是 `cmp` 還是 `prev_cmp` 只要為 0 都代表著**中間這個節點的 value 與前後節點重複**，必刪除！
```c
bool q_delete_dup(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *indirect = (head->next)->next;
element_t *prev_ele = NULL;
element_t *current_ele = NULL;
int cmp = -1, prev_cmp = -1;
while (indirect != head) {
prev_ele = list_entry(indirect->prev, element_t, list);
current_ele = list_entry(indirect, element_t, list);
cmp = strcmp(prev_ele->value, current_ele->value);
if (cmp == 0 || prev_cmp == 0) {
list_del(indirect->prev);
q_release_element(prev_ele);
}
prev_cmp = cmp;
indirect = indirect->next;
}
if (cmp == 0) {
list_del(indirect->prev);
q_release_element(current_ele);
}
return true;
}
```
### q_swap
`q_swap` 只要將佇列內的 element 兩兩交換即可，因此只需要使用 [list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h) 中的 `list_move` 把自己搬到 `next` 後面即可
```c
void q_swap(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *indirect = head->next;
while (indirect != head && indirect->next != head) {
list_move(indirect, indirect->next);
indirect = indirect->next;
}
}
```
### q_reverse
這裡則是使用 pointer to pointer 紀錄第一個 element 節點內的 next 位址（`&head->next->next`），在每次迴圈中將 `next` 指到的節點利用 `list_move` 移到 `head` 前面直到 `next` 指向的位置為 `head` 為止。
```c
void q_reverse(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head **indirect = &((head->next)->next);
while (*indirect != head)
list_move(*indirect, head);
}
```
### q_reverseK
`q_reverseK` 其原理與 `q_reverse` 相似，但因為如果後面個數不足 k 個則不做 reverse，因此我的作法是先讓一個指標邊走邊數，數到第 k 個後，再將後面的節點一一搬到前面來，因此如果走完一圈沒有數到 k 個，剩下的節點就不會動到。
```c
void q_reverseK(struct list_head *head, int k)
{
if (!head || list_empty(head))
return;
struct list_head **indirect = &(head->next);
struct list_head *current = head->next;
struct list_head *tmp = NULL;
int i = 1;
while (current != head) {
if (i % k == 0) {
tmp = current;
while (*indirect != tmp) {
list_move(tmp->prev, current);
current = current->next;
}
indirect = &((current)->next);
}
current = current->next;
i++;
}
}
```
### q_sort
參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)merge_sort寫法。
原先想法是要維持 doubly-linked list 的結構去設計，但當我要 `malloc` 新的 head 來接分割後的子串列時遇到`ERROR:Calls to malloc disallowed`，因此決定將 circular 斷開將最後一個 node 的`prev`指向`NULL`才進行`mergesort`並且在排序後將排序過後的串列重新接上 head。
```c
void q_sort(struct list_head *head)
{
if (!head || list_empty(head))
return;
struct list_head *start = head->next;
struct list_head *tail = head->prev;
tail->next = NULL;
struct list_head *sorted_list = merge_sort(start);
head->next = sorted_list;
struct list_head *cur = head;
while (cur->next) {
cur->next->prev = cur;
cur = cur->next;
}
cur->next = head;
head->prev = cur;
}
```
```c
struct list_head *mergeList(struct list_head *l1, struct list_head *l2)
{
struct list_head *head = NULL;
struct list_head **current = &head;
while (l1 && l2) {
if (strcmp(list_entry(l1, element_t, list)->value,
list_entry(l2, element_t, list)->value) >= 0) {
*current = l2;
l2 = l2->next;
} else {
*current = l1;
l1 = l1->next;
}
current = &((*current)->next);
}
*current = (struct list_head *) ((__intptr_t) l1 | (__intptr_t) l2);
return head;
}
```
```c
struct list_head *merge_sort(struct list_head *head)
{
if (!head || head->next == NULL)
return head;
struct list_head *slow = head;
for (struct list_head *fast = head->next; fast && fast->next;
fast = fast->next->next) {
slow = slow->next;
}
struct list_head *list2 = slow->next;
slow->next = NULL;
return mergeList(merge_sort(head), merge_sort(list2));
}
```
### q_descend
`q_descend` 若是 `prev` 方向有比自己小的節點則這些小的節點都要 delete 掉，直到遇到下一個比自己大的節點，則移動到下一個節點(`prev`)
```c
int q_descend(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
struct list_head *current = head->prev;
struct list_head *cur_prev = current->prev;
while (cur_prev != head) {
if (strcmp(list_entry(current, element_t, list)->value,
list_entry(cur_prev, element_t, list)->value) > 0) {
list_del(cur_prev);
q_release_element(list_entry(cur_prev, element_t, list));
} else {
current = current->prev;
}
cur_prev = current->prev;
}
int len = q_size(head);
return len;
}
```
### q_merge
在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 裡執行`q_merge`其程式碼為
```c
len = q_merge(&chain.head);
```
這個 chain 其實就是 `queue_chain_t` 結構，所以得知輸入的資料為 `queue_chain_t` 內的 `head` 元素因此我們可以很簡單的拜訪所有佇列再使用[list.h](https://github.com/SPFishcool/lab0-c/blob/master/list.h)中的 `list_splice_init` 從第二個佇列到最後一個一一串在 ~~`id=0`~~ 目前第一個 `queue_contex_t->q` 的串列內。
```c
int q_merge(struct list_head *head)
{
if(!head || list_empty(head))
return 0;
else if(list_is_singular(head))
return list_entry(head->next, queue_contex_t, chain)->size;
queue_contex_t *target = list_entry(head->next, queue_contex_t, chain);
queue_contex_t *que = NULL;
list_for_each_entry (que, head, chain) {
if (que == target)
continue;
list_splice_init(que->q, target->q);
target->size = target->size + que->size;
que->size = 0;
}
q_sort(target->q);
return target->size;
}
```
## 目前 queue.c 靜態與動態評分
### make test
- score: 95/100
- problem: q_insert 系列程式時間複雜度非 constant time
### make valgrind
- score: 94/100
- problem: Test of malloc failure on new 測試未通過
- reason：在 `qtest` 執行結束未妥善釋放其程式所配置的記憶體所導致
- solved: 在研讀[Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b#%E4%BB%A5-Valgrind-%E5%88%86%E6%9E%90%E8%A8%98%E6%86%B6%E9%AB%94%E5%95%8F%E9%A1%8C)後發現大部分的test其實都在記憶體配置上出現問題，例如：
```bash
==104151== 128,000 bytes in 2,000 blocks are still reachable in loss record 4 of 6
==104151== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104151== by 0x10F110: test_malloc (harness.c:133)
==104151== by 0x10F645: q_insert_tail (queue.c:72)
==104151== by 0x10C62B: do_it (qtest.c:312)
==104151== by 0x10DDFA: interpret_cmda (console.c:181)
==104151== by 0x10E3AF: interpret_cmd (console.c:201)
==104151== by 0x10E7B0: cmd_select (console.c:610)
==104151== by 0x10F09C: run_console (console.c:705)
==104151== by 0x10D1EC: main (qtest.c:1223)
```
而上述 problem 的錯誤為：
```bash
==104070== 160 bytes in 5 blocks are possibly lost in loss record 3 of 3
==104070== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104070== by 0x10CBCE: do_new (qtest.c:145)
==104070== by 0x10DDFA: interpret_cmda (console.c:181)
==104070== by 0x10E3AF: interpret_cmd (console.c:201)
==104070== by 0x10E7B0: cmd_select (console.c:610)
==104070== by 0x10F09C: run_console (console.c:705)
==104070== by 0x10D1EC: main (qtest.c:1223)
```
在這情況下我決定先嘗試解決比較輕的問題，解決過程如下：
- 檢查 queue.c 是否有哪一個功能沒有完全 free 空間
- 檢查 script 資料夾內的 cmd 檔案，發現沒有此問題的腳本都有執行 free。
- 開始檢查 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 的退出程式發現：
```c
static bool q_quit(int argc, char *argv[])
{
return true;
report(3, "Freeing queue");
if (current && current->size > BIG_LIST_SIZE)
set_cautious_mode(false);
if (exception_setup(true)) {
struct list_head *cur = chain.head.next;
while (chain.size > 0) {
queue_contex_t *qctx, *tmp;
tmp = qctx = list_entry(cur, queue_contex_t, chain);
cur = cur->next;
q_free(qctx->q);
free(tmp);
chain.size--;
}
}
```
發現 `do_quit` 第一行程式碼即 `return true` 表示下方程式完全沒有走過，註解掉後重新 `make valgrind` 所有問題都解決了。
## 研讀 Linux 核心原始程式碼的 lib/list_sort.c
在 linux 核心原始程式碼內的 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 所作的 sort 為 **Merge Sort** ，但這裡面的 Merge Sort 跟我們以前認識的 Merge Sort 不同。
在 `list_sort` 內有 3 個 Function
- `merge`
- `merge_final`
- `list_sort`
而走訪 linked list 時會使用 count 會計算目前走訪到的節點數量，一旦走訪數量走到 $2^k$ 數量時不執行 `merge`，反之就會執行 merge。其流程如下
1. 一開始 `list` 從 `head->next` 開始，而 `pending` 起始為 `NULL`，`count` 起始為 `0`，linked list 最後指向 `NULL`。
2. 迴圈開始，宣告 `**tail`指向 `pending` 的位址。
3. 會先計算 `count` 是否為 $2^k-1$ ，如果是，跳到 "7."。
4. 準備 `merge` ，將 `a = *tail`、`b = a->prev`，執行 `merge(priv, cmp, b, a);`
5. `merge` 會有一個 `**tail` 紀錄前一次比較最小的節點的 `next` 位址，每一次比較會把 `*tail` 指向較小的節點，**其實就是一般的merge，這裡就把 `next` 拿來做 merge 的主要 link。**
6. merge return 為 merge 後的第一個節點（最小）存入 `a` ，將目前的 `a->prev` 重指成 `b->prev`，藉由 `*tail` 把 `pending` 指向 `a`（merge 起始節點）。
7. 將 `list->prev` 指向 `pending`，`list` 往前一步， `panding = list->prev`， 把 `pending->next` 指向 `NULL`。
8. 若 `list` 還沒走完，回到 "2."
9. merge 剩下還沒 merge 起來的 pending list。
10. 最後 `merge_final` 把 merge 完的 list 將其 `prev` 連接起來。
看完 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 發現他並沒有特別做 divide 而是走訪過程一一將 `next` 斷開並且把 `next` 當成執行 merge 動作時走訪的 link，比較「[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list#Merge-Sort-%E7%9A%84%E5%AF%A6%E4%BD%9C)」所提及的遞迴與非遞迴，此做法省去 divide 這一部份，也沒有使用 stack 有 Max Depth 的限制。
## 引入 lib/list_sort.c 到 lab0-c 專案
- 在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/queue.c) 新增 [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 三條 finction 和引入 [list_sort.h](https://github.com/torvalds/linux/blob/master/include/linux/list_sort.h) 內宣告設定
- 參考[lab 0:Valgrind + 自動測試程式](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-b)中的 qtest 直譯器實作，使用 `ADD_COMMAND` 新增剛才加入的 `list_sort`， 再依照檔案裡的 `do_sort` 新增 `do_list_sort`
```c
ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");
```
- 製作分析準備
### 利用 perf 分析 `list_sort` 與自己做的 `q_sort` 效能比較
參考 [linhoward0522 開發紀錄 (lab0)](https://hackmd.io/@linhoward/lab0-2023#2023q1-Homework1-lab0) 使用 perf 分析其效能，在 [traces/trace-15-perf.cmd](https://github.com/SPFishcool/lab0-c/blob/master/traces/trace-15-perf.cmd) 有三筆資料來測試排序，因此我們可以依照這個檔案自製用來測試的 cmd 檔。
```
.
├── RAND-1000000-list.cmd
├── RAND-1000000-q.cmd
├── RAND-100000-list.cmd
├── RAND-100000-q.cmd
├── RAND-10000-list.cmd
├── RAND-10000-q.cmd
├── RAND-1000-list.cmd
└── RAND-1000-q.cmd
```
`q` : `q_sort`
`list` : `list_sort`
接下來是試做 `shell scripts`
```bash
#!/bin/bash
# q_sort
for i in ./traces/perf_traces/RAND-*-q.cmd
do
perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done
#list_sort
for i in ./traces/perf_traces/RAND-*-list.cmd
do
perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done
```
- `q_sort`
| #node | cache-misses | branches | instructions | context-switch |
| ------- | ------------ | ----------- | ------------ | -------------- |
| 1000 | 3469 | 77,9884 | 516,0401 | 0 |
| 10000 | 3,3403 | 621,9374 | 4305,8950 | 0 |
| 100000 | 543,0532 | 6326,2119 | 4,3295,3471 | 0 |
| 1000000 | 7491,5547 | 4,6974,1917 | 31,6153,3055 | 10 |
- `list_sort`
| #node | cache-misses | branches | instructions | context-switch |
|-------|--------------|----------|--------------|-----------------|
|1000|2489|77,7798|519,9240|0|
|10000|4,1257|614,2028|4329,3845|0|
|100000|439,1922|6258,0696|4,3642,0292|3|
|1000000|5824,6891|4,6028,3507|31,6579,3448|9|
可以看到節點數增多，效能差異越大，雖然 RAND 會導致偶爾會讓 `list_sort` 效能看起來跟 `q_sort` 差不多甚至更差，但時間上還是 `list_sort` 略勝一籌。
## 在 [qtest.c](https://github.com/SPFishcool/lab0-c/blob/master/qtest.c) 新增 `shuffle` 命令
作業要求為使用「Fisher–Yates shuffle」完成 `shuffle`，其原理就是從最後一個節點開始，隨機選取前面的節點與其交換，交換完後再往前一格完成前面敘述的事情直到第二張牌為止。
```c
for (int i = len-1;i > 0;i--)
{
//random 1~i
int count = rand() % i;
struct list_head *node = head->next;
for (int j=1; j < count;j++)
node = node->next;
swap(tail, node);
tail = node->prev;
}
```
跟設定 `list_sort` 一樣，新增 `do_shuffle` 與 `ADD_COMMAND`
```c
ADD_COMMAND(shuffle, "shuffle queue.", "");
```
接下來統計剛設計出來的 `shuffle` 亂度
參考 [L01: lab0 亂數+論文閱讀](https://hackmd.io/@sysprog/linux2023-lab0/%2F%40sysprog%2Flinux2023-lab0-d) 中的測試程式並載入 [Makefile](https://github.com/SPFishcool/lab0-c/blob/master/Makefile) 執行指令
```makefile
shuffle_check: qtest scripts/shuffle_test.py
scripts/shuffle_test.py
```
執行結果：
依照 4 個數字的亂數來看，分佈差距大約在 $\pm1.2\%$ ，學生突然想到如果數字在多一點的話分佈會不會變化比較大，因此我將數字加到 6 個，而 6 個數字的排列組合比 4 個數字多出 30 倍，因此也將次數增加到 30000000 次。
執行結果：
在這張圖最少次為 41081，最多次為 42281，幅度有稍微增加，但沒有特別明顯。
## 使用 entropy 觀察亂數
在認識 entropy 之前，對 entropy 的唯一認知就是機器學習中計算 loss 值的方式 `cross entropy`，發現其中的含意與 entropy 也有一些關係，但知道了「entropy 與亂數產生的資訊量成反比」還是覺得對 entropy 有點抽象，因此我打算從 qtest.c 裡的指令 `option entropy 1` 與 `ih RAND 10` 找出關於 entropy 的蛛絲馬跡，最後發現 [shannon_entropy.c](https://github.com/SPFishcool/lab0-c/blob/master/shannon_entropy.c) 裡的 `shannon_entropy` 實作了以下 entropy 公式。
$-\sum^{n}_{i=1} p(x_i)\log_2{p(x_i)}$
```c
for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i]) {
uint64_t p = bucket[i];
p *= LOG2_ARG_SHIFT / count;
entropy_sum += -p * log2_lshift16(p);
}
}
entropy_sum /= LOG2_ARG_SHIFT;
return entropy_sum * 100.0 / entropy_max;
```
這裡除了使用 bucket 計算每一個字元的熵值，而且使用 `LOG_ARG_SHIFT` 預計算的常數來避免使用浮點數增加計算時間。
Sign in with Wallet
Connect another wallet