# 2025q1 Homework4 (quiz3+4)
contributed by < `HeatCrab` >

## 第三周測驗一
* ### 解釋上方程式碼運作原理

首先定義 mpi 的資料型別 `mpi_t` ，接著定義以下四個記憶體操作函式：
1. `mpi_init`：初始化 `mpi_t`，將 data 設為 NULL，容量設為 0。
2. `mpi_clear`：釋放 data 的內存。
3. `mpi_enlarge`：擴展 data 數組到指定容量，並填充新分配的區域為 0。
4. `mpi_compact`：去除高位為 0 的冗餘空間，縮減容量並重新分配記憶體空間。

接下來是4個基本操作的函式：
1. `mpi_set_u64`：

首先呼叫 `ceil_div` 函式，作向上取整除法，原理如下：
在整數除法中，$n/d$ 是向下取整。例如：$5/2=2$（實際是 $2.5$）。
要向上取整，必須補償餘數部分。公式是 $(n+d-1)/d$ ，原因是
- 如果 $n$ 能被 $d$ 整除，則 $n+d-1$ 還是會落在 $n/d$ 的範圍中。
- 如果有 $n$ 除以 $d$ 有餘數，則 $n+d-1$ 會被推到下一個整數。

接著回傳 `n = 64` 與 `d = 31` 。 選擇 `d = 31` 的理由是 `uint32_t` 是32位元，為了防止未來在實作乘法時有溢位的情況發生，所以減少一位元，以方便計算。
再來進入第一個 for 迴圈，透過定義好的 `INT_MAX` ，對 `op` 實作 mask 的動作，位數同樣是31位。將 mask 好的資料儲存至 data 後，再把 `op` 右移 31 位元，重複此動作，直到沒有容量（`capacity`）。
最後再使用第二個 for 迴圈將 `rop` 剩下 capacity 中的 data 賦值為 $0$。

2. `mpi_mul_naive`：

這個函式使用的是樸素乘法，也就是我們最一開始學的乘法。
首先定義 capacity 變數為被乘數（`op1`）與乘數（`op2`）兩個數的 capacity 總和。這樣定義由樸素乘法可以知道，舉例二位數最大 $99$ $\times$ 三位數最大的 $999$：

           99
        × 999
        ------
          891  (99 × 9)
         891   (99 × 9, 左移一位)
        891    (99 × 9, 左移兩位)
        ------
        98901

可以得到最大值 $98901$ ，共五位數。那在我們 `mpi_mul_naive` 函式實作中的差別在於，我們一個 capacity 中存放的有31位元，但這不影響兩者乘積的位數最多就是兩者 capacity 相加的值。
在初始化 `tmp` 之後，進入雙重 for 迴圈，首先使用被乘數的第1位，有就是 data[0]，依序乘上乘數的每一位，並將結果存到變數 `r` 中。接著再使用一個 for 迴圈來將 r 切分成每31位元儲存。若是有進位的情況發生，就將進位值存放到 `c` 變數裡。重複此動作，直到乘法完成。過程就如同我們小學學的，以及上圖的 $99 \times 999$ 一樣。
最後使用 `mpi_set` 將 tmp 的值複製給 rop 完成乘法操作，並使用函式將記憶體釋放。

3. `mpi_fdiv_qr`：

實作上類比長除法。首先將被除數 `n` 與除數 `d` 使用函式複製為 `n0` 與 `d0` 防止更改到原本的變數。定義商數 `q` 與餘數 `r` 。
透過 `mpi_sizeinbase` 函式找到被除數 `n0` 的最高位數，因為要如同我們學的長除法一樣，從最左邊，也就是最高位數開始做。接著進入 for 迴圈，透過定義餘數 `r` 的值，與判斷 `r` 跟除數 `d` 的關係來決定商數，過程上使用位元計算來模擬實作長除法時，判斷要重哪一位開始除的過程。
為了更具體的說明，以下舉例 `n = 0b1101` 與 `d = 0b11` 為例子：
>嘗試過使用 graphviz 說明，但是做的圖片不是很理想，所以最後還是決定使用文字說明。

因為 `start = 3` ，所以迴圈從 `i = 3` 開始。
1. `i = 3`：
一開始 `r` 為 $0b0$，所以在移項（乘二）後，仍舊為零。
因為 `n` 的第三位不為零，所以將 `r` 的第0位設為1，變成 $0b1$。
比較餘數與除數的大小，因為餘數沒有大於除數，所以不做任何動作，繼續迴圈。
2. `i = 2`：
此時 `r` 為 $0b1$，在移項（乘二）後，變成 $0b10$。
因為 `n` 的第二位依舊不為零，所以將 `r` 的第0位設為1，此時 `r` 是 $0b11$。
比較餘數與除數的大小，因為餘數大於等於除數，所以將餘數 `r` 扣去除數，並將 `q` 的第二位設為1。
此時 `r` 為 $0b00$ ， `q` 為 $0b0100$ 。
3. `i = 1`：
`r` 現在又為 $0b0$，所以在移項（乘二）後，仍舊為零。
因為 `n` 的第三位為零，所以無動作。
再比較餘數與除數的大小，餘數沒有大於除數，不做任何動作，繼續迴圈。
4. `i = 0`：
`r` 依舊為 $0b0$，所以移項（乘二）後，仍舊為零。
因為 `n` 的第零位不為零，所以將 `r` 的第0位設為1，此時 `r` 為 $0b1$。
比較餘數與除數的大小，因為餘數沒有大於除數，所以不做任何動作，繼續迴圈。
5. 迴圈結束，得到以下結果：
`r` = $0b1$
`q` = $0b100$

用十進位除法驗證一下結果：$$
13 \div 4 = 3 \ ... 1
$$結果正確。

4. `mpi_gcd`：

透過遞迴呼叫的方式實作輾轉相除法來找最大公因數。
在程式碼的一開始確認 `op2` 是否為零，若是 `op2` 為零，則表示輾轉相除法完成，此時的 `op1` 即為所求，將 `op1` 賦值給 `rop` 結束函式。
除法的部分是透過 `mpi_fdiv_qr` 來計算。

&nbsp;

* ### 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷

&nbsp;

* ### 改進最大公因數的運算效率

&nbsp;

## 第三周測驗二
* ### 解釋上方程式碼運作原理
程式上使用了 SWAR 的手法，來實現 `memchr` 函式要做的事情。`memchr` 的原理十分簡單，就是透過 while 迴圈來找到目標 `c` 。那 SWAR 簡單來說，就是透過並行處理的方式，來減少運算上的成本。先使用測驗題說明中提供的程式碼來理解。
原先的 `both_odd` 函式就是跟將 `x` 與 `y` 兩個要比較的變數，先跟1作位元運算 and ，透過判斷最小位數是否為1，來決定是否為奇數。再使用邏輯運算 and 來判斷是否都是奇數。
使用 SWAR 方法則是透過 `bit_compound` 函式，使用以下的位元運算式，將 `x` 跟 `y` 這兩個32位元的變數結合在一起。

        return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));

以下是 0L 的示意圖，L 表示的是 long 數據型別。圖片中將4個 bits 劃分為一位元。總共有64個0。

    digraph step1_0L {
        rankdir=TB; 
        node [shape=record];
        n0 [label="0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0"];
    }

先加上變數 `x` ，接著左移32位元，得到上32位元等於 `x` 變數，下32位元為0的64位元數。

    digraph step2_0L_plus_x {
        rankdir=TB; 
        node [shape=record];

        n0 [label="0|0|0|0|0|0|0|0|x0|x1|x2|x3|x4|x5|x6|x7"];
        
        n1 [label="x0|x1|x2|x3|x4|x5|x6|x7|0|0|0|0|0|0|0|0"];

        n0 -> n1 [label="  shift"];    
    }

接著是先以同樣的動作操作 `y` 變數，得到如下圖：

    digraph step_1y {
        rankdir=TB; 
        node [shape=record];

        n0 [label="0|0|0|0|0|0|0|0|y0|y1|y2|y3|y4|y5|y6|y7"];
    }

這邊使用 [-1L](https://stackoverflow.com/questions/4115566/what-is-1l-1l-in-c) ， 表示的是64位元全1，如圖所示：

    digraph step1_minus_oneL {
        rankdir=TB; 
        node [shape=record];
        n0 [label="1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1"];
    }

透過右移32位元，並且與 `y` 變數做位元運算 and ，就可以得到一個上32位元為零，下32位元為 `y` 的64位元數。

    digraph step_y_result {
        rankdir=TB; 
        node [shape=record];

        n0 [label="0|0|0|0|0|0|0|0|y0|y1|y2|y3|y4|y5|y6|y7"];
    }

最後將新的 `x` 與 `y` 變數做位元運算 or ，實現加法的動作，就得到一個上32位元為 `x` ，下32位元為 `y` 的64位元數 `xy` 。
在使用 `both_odd_swar` 函式前，先定義 `SWAR_ODD_MASK` 變數。首先使用 1L ，表示的是前63位元為0，最低位，也就是第0位為1。

    digraph step1_1L {
        rankdir=TB; 
        node [shape=record];
        n0 [label="0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0001"];
    }

透過左移32位元，將1的位置移到 `xy` 中上32位元 `x` 的第0位，來判斷 `x` 是否為奇數，接著加上1，來判斷 `xy` 中下32位元 `y` 是否為奇數。

    digraph step_SWAR_ODD_MASK {
        rankdir=TB; 
        node [shape=record];
        n0 [label="0|0|0|0|0|0|0|0001|0|0|0|0|0|0|0|0001"];
    }

在函式中使用位元運算 and ，如果是奇數，那經過運算後的 `xy` 會跟 `SWAR_ODD_MASK` 一致，此時回傳1，表示 true ，否則回傳0表示 false。

回到函式 `memchr_opt` ， 首先先轉換 `str` 的型別變成 unsigned char （一位元組），並將其記憶體位置定義為變數 `src`。同樣將 `c` 轉換成 unsigned char 資料型別的 `d` 。
透過 while 迴圈與 `UNALIGNED` 函式判斷 `src` 變數是否有對齊 long 這個資料型別。透過位元運算 and 判斷傳入的變數 `X` 是否是 (sizeof(long) - 1) 的倍數，若是有對齊則位元運算結果會是0，否則回傳1，繼續 while 迴圈，直到 `src` 對齊。
接下來即是我們實作 SWAR 的部分。先判斷字串長度是否有足夠的必要使用 SWAR 來實作。確認字串長度夠大後，定義一個 unsigned long 的變數 `asrc` 來加快尋找與判斷的字串位元數。然後將 `d` 變數依據 `LBLOCKSIZE` 大小的不同擴充，舉例 `d` 為 $0x87$，根據程式碼步驟：
1. `d` 先左移8位，`d` = $0x8700$
2. 跟 `d` 作位元運算 or ， 得到 `mask` = $0x0000000000008787$
3. `mask` 再左移32位，接著與自己做位元運算 or ，得 $0x0000000087878787$
4. 依據 `LBLOCKSIZE` 的大小繼續左移，假設依據[規格書](https://refspecs.linuxbase.org/elf/x86_64-abi-0.99.pdf)， long 的資料型別大小是8，`mask` 擴充至64位，我們得到 `mask` 為 $0x8787878787878787$

如果字串長度比 `LBLOCKSIZE` 大，那麼呼叫 `DETECT_CHAR` 函式。
`DETECT_CHAR` 函式會先將傳入的變數 `X` 與 `mask` 作 XOR，如果 `X` 字串包含要尋找的 `d` 字串的話，那 XOR 的結果就會有0位元組。接著將這個包含0位元組的結果傳入 `DETECT_NULL` 函式中判斷是否有零位元組。
:::info
TBD
:::

&nbsp;

* ### 比較 Linux 核心原本 (與平台無關) 的實作和 `memchr_opt`，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響

&nbsp;

* ### 研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析

&nbsp;

## 第四周測驗一
* ### 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼

&nbsp;

* ### 設計實驗來分析 [Fast CRC32](https://create.stephan-brumme.com/crc32/) 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。

&nbsp;

* ### 以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令

&nbsp;

## 第四周測驗二
* ### 解釋上述程式碼運作原理，搭配[「信號與系統」](https://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/103S207)教材

&nbsp;

* ### 探討定點數的使用和其精確度

&nbsp;

* ### 改進 MIDI 一閃一閃亮晶晶的音效輸出

&nbsp;

## 第四周測驗三
* ### 解釋上述程式碼運作原理

&nbsp;

* ### 學習 [jserv/ttt](https://github.com/jserv/ttt) 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面

&nbsp;

* ### 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 [ping value](https://www.business.att.com/resources/knowledge-center/what-is-latency-impact-on-gaming-streaming.html) 的處理機制

&nbsp;