---
# System prepended metadata

title: 2025q1 Homework4 (quiz3+4)
tags: [linux2025]

---

# 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 一閃一閃亮晶晶的音效輸出