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÷4=3...1$$結果正確。

  4. mpi_gcd：

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

 

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

 

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

 

第三周測驗二

• 解釋上方程式碼運作原理

  程式上使用了 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。

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

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

  這邊使用 -1L ， 表示的是64位元全1，如圖所示：

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

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

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

  在函式中使用位元運算 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 的大小繼續左移，假設依據規格書， long 的資料型別大小是8，mask 擴充至64位，我們得到 mask 為
     $0x8787878787878787$

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

  TBD

 

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

 

• 研讀 2022 年學生報告，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析

 

第四周測驗一

• 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼

 

• 設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。

 

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

 

第四周測驗二

• 解釋上述程式碼運作原理，搭配「信號與系統」教材

 

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

 

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

 

第四周測驗三

• 解釋上述程式碼運作原理

 

• 學習 jserv/ttt 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面

 

• 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 ping value 的處理機制