# 2025q1 Homework4 (quiz3+4) contributed by < [`charliechiou`](https://github.com/charliechiou?tab=repositories) > {%hackmd NrmQUGbRQWemgwPfhzXj6g %} ## 第三週測驗題 ### 測驗 `1` [測驗 1 課堂問答](https://hackmd.io/K4C5ofeqQg6LC8OEbdVcwg?view) #### 延伸問題 1 >解釋上述程式碼運作原理 程式碼使用 mpi_t 的結構來儲存大數，藉由組合多個 uint32_t 來完成。 mpi_t 預先分配為 1 個 struct 元素的陣列，在編譯時便可確保 mpi_t 始終會佔據一個 struct 的空間。而使用陣列的形式而非指標，即可不需要再額外分配記憶體。在結構體中，使用 data 來儲存該大數的其中一段，而 capacity 則表示這個大數用到的空間。 ```c typedef struct { uint32_t *data; size_t capacity; } mpi_t[1]; ``` 其餘使用 mpi_init 初始化，使用 mpi_clear 釋放資料，並使用 mpi_set_u32 及 mpi_set_u64 來設定數值。 ##### mpi_set_u64 & mpi_set_u32 由於要保留一位做進位,因此使用 mpi_t 中每個段落為 31 位元。藉由 ceil_div 來計算總共需要多少段落，並將其存入 capacity 中。 ```c size_t capacity = ceil_div(32, 31); & size_t capacity = ceil_div(64, 31); ``` 計算完 capacity 後使用 mpi_enlarge 將 mpi 擴充到所需的空間，其中 mpi_enlarge 使用 realloc 來重新分配空間，由於每個 data 會需要 32 位元，因此分配 `capacity * 4` 的大小。 接著將輸入使用位元遮罩 `0x7fffffff` 切分，取底下 31 位元並存入 data 後位移。 ```c for (size_t n = 0; n < capacity; ++n) { rop->data[n] = op & INTMAX; op >>= 31; } ``` 接著再把剩下的空間清 0 避免多餘的空間造成錯誤。 ```c for (size_t n = capacity; n < rop->capacity; ++n) rop->data[n] = 0; ``` ##### mpi_get_u32 & mpi_get_u64 函式用來把 MPI 格式轉換回 uint32 或 uint64，這部份計算 capacity 。以 32 位元為例，由於 32 位元存為 mpi_t 最多只需要兩個 limb 因此這邊僅提取 mpi_t 的最低兩個 limb 其餘則截斷，而 64 位元則僅提取最低三個 limb 。由於有留下最高位當作進位用，因此會移動 31 位元再加入到要儲存的結果中。 ```c for (size_t n = capacity - 1; n != (size_t)-1; --n) { r <<= 31; r |= op->data[n]; } ``` 這部份我也嘗試去修改讓 capacity 固定，修改 mpi_get_u32 中的 capacity 為 2 可以發現執行結果正確， 可見到 32 位元僅須兩個 limb 的數值便足夠。原先 ceil_dev 的寫法是為了可讀性，能夠更清楚的表示 capacity 的計算方式。 此外，我也嘗試將 capacity 設超過 2 並檢視會發生什麼錯誤，由於每次計算皆會把結果向左 shift 因此無論讀取了多少個 mpi_t 內部的數值都只會剩下最後的兩個 limb。然而，capacity 超過 2 時可能會讀取到錯誤的記憶體空間，但這樣的錯誤卻不會反應在結果上。 透過 valgrind 查看，可以發現 capacity 超過 2 時會顯示錯誤的讀取。 ```bash ==37738== mpi_init, mpi_clear mpi_set_u32, mpi_get_u32 ==37738== Invalid read of size 4 ``` ##### mpi_add, mpi_sub 相加或相減需要先確認 capacity，將其設為兩者中較大者，並擴展 rop 的容量。 ```c size_t capacity = op1->capacity > op2->capacity ? op1->capacity : op2->capacity; mpi_enlarge(rop, capacity); ``` 使用 for 迴圈遍歷每個 limb ，首先先使用各自的 capacity 確認該 limb 有數值 ```c uint32_t r1 = (n < op1->capacity) ? op1->data[n] : 0; uint32_t r2 = (n < op2->capacity) ? op2->data[n] : 0; ``` 接著把兩個 limb 相加並加上 carry （進位）存入 rop 對應的 limb 中。 ```c rop->data[n] = r1 + r2 + c; ``` 最後再把進位設定好並截斷多餘的位元。 ```c c = rop->data[n] >> 31; rop->data[n] &= INTMAX; ``` 最後若還有進位則擴充 capacity 並使用 compact 壓縮。 ```c if (c != 0) { mpi_enlarge(rop, capacity + 1); rop->data[capacity] = 0 + c; } mpi_compact(rop); ``` 而其餘 `mpi_add_u64`, `mpi_add_u32`, `mpi_sub_u32`, `mpi_mul_u32` 也是用類似的方式來完成。 ##### mpi_set_str, mpi_set #### 延伸問題 2 >這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷 #### 延伸問題 3 >改進最大公因數的運算效率 ### 測驗 `2` #### 延伸問題 1 >解釋上述程式碼運作原理 #### 延伸問題 2 >比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響 #### 延伸問題 3 >研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析 ## 第四週測驗題 ### 測驗 `1` #### 延伸問題 1 >在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼 #### 延伸問題 2 >設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。 #### 延伸問題 3 >以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令 ### 測驗 `2` #### 延伸問題 1 >解釋上述程式碼運作原理，搭配「信號與系統」教材 #### 延伸問題 2 >探討定點數的使用和其精確度 #### 延伸問題 3 >改進 MIDI 一閃一閃亮晶晶的音效輸出