2025q1 Homework4 (quiz3+4)

contributed by < charliechiou >

作業書寫規範:

• 無論標題和內文中，中文和英文字元之間要有空白字元 (對排版和文字搜尋有利)
• 文字訊息 (尤其是程式執行結果) 請避免用圖片來表示，否則不好搜尋和分類
• 共筆書寫請考慮到日後協作，避免過多的個人色彩，用詞儘量中性
• 不要在筆記內加入 [TOC] : 筆記左上方已有 Table of Contents (TOC) 功能，不需要畫蛇添足
• 不要變更預設的 CSS 也不要加入任何佈景主題: 這是「開發紀錄」，用於評分和接受同儕的檢閱
• 當在筆記中貼入程式碼時，避免非必要的行號，也就是該手動將 c= 或 cpp= 變更為 c 或 cpp。行號只在後續討論明確需要行號時，才要出現，否則維持精簡的展現。可留意「你所不知道的 C 語言: linked list 和非連續記憶體」裡頭程式碼展現的方式
• HackMD 不是讓你張貼完整程式碼的地方，GitHub 才是！因此你在開發紀錄只該列出關鍵程式碼 (善用 diff 標示)，可附上對應 GitHub commit 的超連結，列出程式碼是為了「檢討」和「便於他人參與討論」
• 留意科技詞彙的使用，請參見「資訊科技詞彙翻譯」及「詞彙對照表」
• 不要濫用 :::info, :::success, :::warning 等標示，儘量用清晰的文字書寫。:::danger 則僅限授課教師作為批注使用
• 避免過多的中英文混用，已有明確翻譯詞彙者，例如「鏈結串列」(linked list) 和「佇列」(queue)，就使用該中文詞彙，英文則留給變數名稱、人名，或者缺乏通用翻譯詞彙的場景
• 在中文敘述中，使用全形標點符號，例如該用「，」，而非 ","。注意書名號的使用，即 〈 和 〉，非「小於」和「大於」符號
• 避免使用不必要的 emoji 字元

第三週測驗題

測驗 1

測驗 1 課堂問答

延伸問題 1

解釋上述程式碼運作原理

程式碼使用 mpi_t 的結構來儲存大數，藉由組合多個 uint32_t 來完成。 mpi_t 預先分配為 1 個 struct 元素的陣列，在編譯時便可確保 mpi_t 始終會佔據一個 struct 的空間。而使用陣列的形式而非指標，即可不需要再額外分配記憶體。在結構體中，使用 data 來儲存該大數的其中一段，而 capacity 則表示這個大數用到的空間。

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 中。

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 後位移。

for (size_t n = 0; n < capacity; ++n)
{
    rop->data[n] = op & INTMAX;
    op >>= 31;
}

接著再把剩下的空間清 0 避免多餘的空間造成錯誤。

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 位元再加入到要儲存的結果中。

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 時會顯示錯誤的讀取。

==37738== 
mpi_init, mpi_clear
mpi_set_u32, mpi_get_u32
==37738== Invalid read of size 4

mpi_add, mpi_sub

相加或相減需要先確認 capacity，將其設為兩者中較大者，並擴展 rop 的容量。

size_t capacity =
    op1->capacity > op2->capacity ? op1->capacity : op2->capacity;

mpi_enlarge(rop, capacity);

使用 for 迴圈遍歷每個 limb ，首先先使用各自的 capacity 確認該 limb 有數值

uint32_t r1 = (n < op1->capacity) ? op1->data[n] : 0;
uint32_t r2 = (n < op2->capacity) ? op2->data[n] : 0;

接著把兩個 limb 相加並加上 carry （進位）存入 rop 對應的 limb 中。

rop->data[n] = r1 + r2 + c;

最後再把進位設定好並截斷多餘的位元。

c = rop->data[n] >> 31;
rop->data[n] &= INTMAX;

最後若還有進位則擴充 capacity 並使用 compact 壓縮。

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 年學生報告，在 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 一閃一閃亮晶晶的音效輸出