# 2025q1 Homework4 (quiz3+4)
contributed by < [Mike1117](https://github.com/Mike1117/) >
## 進度記錄
:::spoiler 進度記錄
## quiz 3
### 測驗一
- [x] 填空
- [ ] 延伸問題：
- [ ] 解釋上方程式碼運作原理
- [x] 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
- [ ] 改進最大公因數的運算效率
### 測驗二
- [x] 填空
- [ ] 延伸問題：
- [x] 解釋上方程式碼運作的原理
- [x] 比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt
- [x] 設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
- [ ] 研讀 2022 年學生報告
- [ ] 在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
### 測驗三
- [x] 填空
---
## quiz 4
### 測驗一
- [x] 填空
- [ ] 延伸問題：
- [ ] 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
- [ ] 設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
- [ ] 以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令
### 測驗二
- [ ] 填空
- [ ] 延伸問題：
- [ ] 解釋上述程式碼運作原理，搭配「信號與系統」教材
- [ ] 探討定點數的使用和其精確度
- [ ] 改進 MIDI 一閃一閃亮晶晶的音效輸出
### 測驗三
- [ ] 填空
- [ ] 延伸問題：
- [ ] 解釋上述程式碼運作原理
- [ ] 提供測試程式碼
- [ ] 學習 jserv/ttt 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
- [ ] 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 ping value 的處理機制
:::
## 第 3 周測驗題
### [測驗一](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-1)
#### 填空部分
```
AAAA = (n+d-1)/d
BBBB = 0x7fffffff
CCCC = n+m
DDDD = 1
EEEE = mpi_gcd(rop,op2,r)
```
#### 延伸問題
:::success
解釋上述程式碼運作原理
:::
##### void mpi_init(mpi_t rop)
初始化 mpi 。
##### void mpi_clear(mpi_t rop)
釋放 mpi 的記憶體空間。
##### void mpi_enlarge(mpi_t rop, size_t capacity)
當目前的 capacity 不夠大時，重新分配記憶體，使其可以放下更大的數。
##### void mpi_compact(mpi_t rop)
當目前數值不需要這麼大的 capacity 時，重新分配記憶體縮小 capacity ，減少記憶體佔用。
##### static size_t ceil_div(size_t n, size_t d)
向上整除。
##### void mpi_set_u64(mpi_t rop, uint64_t op)
將一個 uint64_t 轉換為 mpi 並存入 rop 中。
##### void mpi_set_u32(mpi_t rop, uint32_t op)
將一個 uint32_t 轉換為 mpi 並存入 rop 中。
##### uint64_t mpi_get_u64(const mpi_t op)
將 mpi 轉換為 uint64_t 並回傳。
##### uint32_t mpi_get_u32(const mpi_t op)
將 mpi 轉換為 uint32_t 並回傳。
##### void mpi_add(mpi_t rop, const mpi_t op1, const mpi_t op2)
將兩個 mpi op1 及 op2 相加並存入 rop 。
##### void mpi_sub(mpi_t rop, const mpi_t op1, const mpi_t op2)
將兩個 mpi op1 及 op2 相減並存入 rop 。
##### void mpi_add_u64(mpi_t rop, const mpi_t op1, uint64_t op2)
將 mpi op1 及 uint64_t op2 相加並存入 rop 。
##### void mpi_add_u32(mpi_t rop, const mpi_t op1, uint32_t op2)
將 mpi op1 及 uint32_t op2 相加並存入 rop 。
##### void mpi_sub_u32(mpi_t rop, const mpi_t op1, uint32_t op2)
將 mpi op1 及 uint32_t op2 相減並存入 rop 。
##### void mpi_mul_u32(mpi_t rop, const mpi_t op1, uint32_t op2)
將 mpi op1 及 uint32_t op2 相乘並存入 rop 。
##### int mpi_set_str(mpi_t rop, const char *str, int base)
將字串轉換為 mpi 並存入 op 。
##### void mpi_set(mpi_t rop, const mpi_t op)
將 op 存入 rop 。
##### static void mpi_mul_naive(mpi_t rop, const mpi_t op1, const mpi_t op2)
將兩個 mpi op1 及 op2 相乘存入 rop 。
##### void mpi_fdiv_r_2exp(mpi_t r, const mpi_t n, mp_bitcnt_t b);
##### void mpi_fdiv_q_2exp(mpi_t q, const mpi_t n, mp_bitcnt_t b);
##### void mpi_mul_2exp(mpi_t rop, const mpi_t op1, mp_bitcnt_t op2);
##### static void mpi_mul_karatsuba(mpi_t rop, const mpi_t op1, const mpi_t op2)
##### void mpi_mul(mpi_t rop, const mpi_t op1, const mpi_t op2)
##### int mpi_cmp(const mpi_t op1, const mpi_t op2)
##### int mpi_cmp_u32(const mpi_t op1, uint32_t op2)
##### uint64_t mpi_get_word_u64(const mpi_t op, size_t n)
##### uint32_t mpi_get_word_lshift_u32(const mpi_t op, size_t n, size_t lshift)
##### void mpi_mul_2exp(mpi_t rop, const mpi_t op1, mp_bitcnt_t op2)
##### int mpi_testbit(const mpi_t op, mp_bitcnt_t bit_index)
##### void mpi_setbit(mpi_t rop, mp_bitcnt_t bit_index)
##### size_t mpi_sizeinbase(const mpi_t op, int base)
##### void mpi_fdiv_qr(mpi_t q, mpi_t r, const mpi_t n, const mpi_t d)
##### void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
:::success
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
:::
```c
void mpi_gcd2(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
if (mpi_cmp_u32(op2, 0) == 0) {
mpi_set(rop, op1);
return;
}
mpi_t q,r,a,b;
mpi_init(q);
mpi_init(r);
mpi_init(a);
mpi_init(b);
mpi_set(a,op1);
mpi_set(b,op2);
do{
mpi_fdiv_qr(q, r, a, b);
mpi_set(a,b);
mpi_set(b,r);
}while(mpi_cmp_u32(r, 0) != 0);
mpi_set(rop,a);
mpi_clear(q);
mpi_clear(r);
mpi_clear(a);
mpi_clear(b);
}
```
:::success
改進最大公因數的運算效率
:::
### [測驗二](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-2)
#### 填空部分
```
AAAA = X^mask
BBBB = mask<<i
CCCC = *asrc
```
#### 延伸問題
:::success
解釋上方程式碼運作的原理
:::
##### #define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
定義一個巨集，用以檢查 X 是否有對齊 long
##### #define LBLOCKSIZE (sizeof(long))
定義 LBLOCKSIZE 的大小為 long 的 size
##### #define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
檢查目前的剩餘的 len 是否有小於 LBLOCKSIZE
##### #if LONG_MAX == 2147483647L...
```
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
檢查 long 是 32-bit 還是 64-bit ，定義一個對應 bit 數的 `DETECT_NULL` ，用以檢查 X 中是否存在一個為 `00` 的 char。
##### #define DETECT_CHAR(X, mask) DETECT_NULL(X ^ mask)
檢查 X 中是否存在某特定的 char ，會先用 char 構造一個特殊的 mask，與 X 作 XOR 之後用 `DETECT_NULL` 判斷。
##### void *memchr_opt(const void *str, int c, size_t len)
主函式部分，首先以一個迴圈來處理 `UNALIGNED` 的部分，若在該迴圈中檢查完 len 個 byte 都未找到 c ，則回傳 `NULL` ，若找到則回傳 c 的位置；
若在第一個迴圈中成功對齊 long ，則會進入到 SWAR 的實作部分。
首先通過 `if (!TOO_SMALL(len))` 判斷目前的剩餘長度是否需要進入最佳化的實作，若過短則直接處理，否則會先製作一個 `mask` ，看到如下程式碼：
```c
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
```
假設欲尋找之 byte d 為 0xAB ，該段程式碼會將 mask 變為 `0xABABABAB` （若為 64-bit 之環境則會再擴充為 `0xABABABABABABABAB` ）,再利用 `DETECT_CHAR` 一次比對一個 `LBLOCKSIZE` ，找到則回傳位置。
:::success
比較 Linux 核心原本 (與平台無關) 的實作和 `memchr_opt`，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
:::
觀察 [Linux 核心原本的實作](https://github.com/torvalds/linux/blob/master/lib/string.c#L788-L809) 實作，可以看出其為簡單的逐字元比對。再將其與 `memchr_opt` 對比，可以看出可能會影響兩者效能的變數主要有以下幾點
· `size_t len` ，即欲搜尋記憶體區塊的大小
· 欲搜尋之字元 c 的位置
· 是否有對齊
故針對此三個變數設計測試程式，測試不同記憶體區塊大小、不同 c 之位置、不同 Alignment offset 情況下兩者效能之差異。
Memory Block Size: 8 KB
| Align Offset | Position | Std (ns) | Opt (ns) | Speedup |
|--------:|:-----------|-----------:|-----------:|----------:|
| 0 | begin | 110 | 50 | 2.2 |
| 0 | middle | 5100 | 431 | 11.83 |
| 0 | end | 10050 | 922 | 10.9 |
| 0 | none | 10310 | 962 | 10.72 |
| 7 | begin | 20 | 20 | 1 |
| 7 | middle | 3337 | 391 | 8.53 |
| 7 | end | 6352 | 632 | 10.05 |
| 7 | none | 6422 | 742 | 8.65 |
Memory Block Size: 10 MB
| Align Offset | Position | Std (μs) | Opt (μs) | Speedup |
|---------------:|:-----------|-----------:|-----------:|----------:|
| 0 | begin | 0.06 | 0.03 | 2 |
| 0 | middle | 2057.79 | 257.907 | 7.98 |
| 0 | end | 4114.8 | 520.233 | 7.91 |
| 0 | none | 4118.57 | 546.023 | 7.54 |
| 7 | begin | 0.01 | 0.02 | 0.5 |
| 7 | middle | 2068.46 | 262.777 | 7.87 |
| 7 | end | 4139.78 | 521.426 | 7.94 |
| 7 | none | 4137.62 | 516.426 | 8.01 |
Memory Block Size: 1 GB
| Align Offset | Position | Std (ms) | Opt (ms) | Speedup |
|---------------:|:-----------|-----------:|-----------:|----------:|
| 0 | begin | 0 | 0 | 0.61 |
| 0 | middle | 212.304 | 27.068 | 7.84 |
| 0 | end | 425.045 | 54.116 | 7.85 |
| 0 | none | 425.356 | 54.125 | 7.86 |
| 7 | begin | 0 | 0 | 0.57 |
| 7 | middle | 213.175 | 26.99 | 7.9 |
| 7 | end | 426.024 | 53.972 | 7.89 |
| 7 | none | 426.055 | 53.984 | 7.89 |
以上列出了三組在不同 Memory Block Size 的情況下，針對不同欲尋找字元之位置及不同 Alignment Offset ，兩個函式的運行時間對比。
可以看出當欲尋找字元位於 Memory Block 開頭時，兩函式的運行效率幾乎一致；但當其位於 Memory Block 的中後段時， `memchr_opt` 則比 Linux 核心原本的實作要快接近八倍。這個結果也非常接近理論值，因為原實作一次只能檢查一個字元，而 `memchr_opt` 則一次可以檢查一個 `long` 的長度，即八個字元。
:::success
研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
:::
### [測驗三](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-3)
#### 填空部分
```
AAAA = ENV_RUNNABLE
BBBB = attempts + 1
CCCC = coro_schedule
DDDD = coro_yield
```
#### 延伸問題
:::success
解釋上述程式碼運作原理
:::
:::success
:::
## 第 4 周測驗題
### [測驗一](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-1)
#### 填空部分
```
AAAA = 0xc38d26c4
BBBB = 0xd3d3e1ab
CCCC = 0xe330a81a
DDDD = 0xf36e6f75
```
#### 延伸問題
此處讓我們求出 AAAA - DDDD 的十六進制數其實是讓我們求出該 `crc32_table` 的原始多項式是什麼。而根據計算 table 的程式碼不難發現當 4-bit 為 1000 時，所求出之值即為其本身。
而此處第 9 個值為 `0x82f63b78` ，將此值填入老師所提供的 godbolt 中，即可獲得完整的表格。
:::success
在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
:::
##### [linux/drivers/md/raid5-ppl.c](https://github.com/torvalds/linux/blob/5723cc3450bccf7f98f227b9723b5c9f6b3af1c5/drivers/md/raid5-ppl.c)
---
##### [fs/gfs2/log.c](https://github.com/torvalds/linux/blob/5723cc3450bccf7f98f227b9723b5c9f6b3af1c5/fs/gfs2/log.c)
---
##### [linux/fs/btrfs/disk-io.c](https://github.com/torvalds/linux/blob/5723cc3450bccf7f98f227b9723b5c9f6b3af1c5/fs/btrfs/disk-io.c)
---
:::success
設計實驗來分析 [Fast CRC32](https://create.stephan-brumme.com/crc32/) 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
:::
:::success
以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令
:::
### [測驗二](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-2)
#### 填空部分
```
AAAA = 0x7FFF
BBBB = 0x80000000
CCCC = 0x7FFFFFFF
DDDD = 0x80000000
EEEE = 0x7FFFFFFF
FFFF = input & 0xFF
GGGG = Q15_MAX
HHHH = Q15_MIN
```
#### 延伸問題
:::success
解釋上述程式碼運作原理，搭配「信號與系統」教材
:::
##### static q15_t midi_to_phase_incr(uint8_t note)
`octave` 意為音階，而一個音階為八度，即 12 個音，此處先透過 `note / 12` 計算出 note 所處的音階，再算出此 note 在音階中的相對位置 `note_index` (即具體是哪個音名)。
再透過儲存了 C8 - B8 頻率對應相位的 `octave_phases[12]` ，先計算出 note 低 `BASE_OCTAVE` 幾個八度。因同音名時，低一個八度頻率減半，所以只需透過右移操作即可計算出 note 的相位。
##### static void synth_voice_note_on(synth_voice_t *voice, uint8_t note)
##### static void synth_voice_note_off(synth_voice_t *voice)
關閉 `gate` ，進入 release 階段。
##### void synth_init_osc_node
初始化一個振蕩器節點，設定他的對應參數。
##### void synth_init_envelope_node
初始化一個 envelope 節點，設定他的對應參數。
##### void synth_init_filter_lp_node
初始化一個 low pass filter 節點，設定他的對應參數。
##### q15_t synth_process()
處理每個聲部的每個節點在一個 frame 中的 output 。
外層迴圈 traverse 每個聲部，內層迴圈 traverse 每個節點，並透過 switch 處理不同節點類型。
##### q15_t sawtooth_wave(q15_t input)
##### q15_t sine_wave(q15_t input)
##### q15_t square_wave(q15_t input)
此三個函式為生成不同的波形。
##### static int write_wav(const char *filename, const int16_t *audio_buffer, uint32_t sample_count)
將生成的音頻寫入到檔案中。
##### main()
初始化各個節點，，定義一閃一閃亮晶晶每個 note 的音高以及持續時間，以一迴圈生成每個 frame 的音頻，存入到 buffer 中，最後寫入檔案。
:::success
探討定點數的使用和其精確度
:::
根據[維基百科](https://zh.wikipedia.org/zh-tw/%E5%AE%9A%E9%BB%9E%E6%95%B8%E9%81%8B%E7%AE%97)，定點數的定義為 `用固定整數位數表達分數的格式`。使用定點數的好處為可以在一些不支援浮點數的硬體上模擬浮點數的運算，節省資源的調用。
下面借由本程式中出現的 `q15` 以及 `q7` 分析其精確度。
參考 [CMSIS-DSP](https://github.com/ARM-software/CMSIS-DSP/blob/main/Include/arm_math_types.h) 中對於`q15` 以及 `q7`之定義：
```c
/**
* @brief 8-bit fractional data type in 1.7 format.
*/
typedef int8_t q7_t;
/**
* @brief 16-bit fractional data type in 1.15 format.
*/
typedef int16_t q15_t;
```
可以看出 `q15` 為以 16-bit 整數表示小數，`q7` 則以 8-bit 整數表示小數。
其中，`q15` 的格式為 `1 位整數位 + 15 位小數位`，`q7` 則為 `1 位整數位 + 7 位小數位`。
據此，我們可以推斷出他們所能表示的最大值與最小值為：
```c
Q15_MAX 0x7FFF → 32767
Q15_MIN 0x8000 → -32768
Q7_MAX 0x7F → 127
Q7_MIN 0x80 → -128
```
而具體表示的小數，需要將目前的值除以 16-bit 的最大值 32768 ( q7 為 128)，才可以得出。
所以 `q15` 可以表示的小數具體介於 `[32767/32768 , -32768/32768]`，為`[0.999969482421875 , -1]` 。
而`q15` 可以表示的小數則具體介於 `[127/128 , -128/128]`，為`[0.9921875 , -1]` 。
此處不難看出，最大誤差值即為其最大值的倒數，故`q15` 的誤差最大為 `1/32768 = 0.000030517578125`，而 `q7` 的誤差最大為 `1/128 = 0.0078125`
:::success
改進 MIDI 一閃一閃亮晶晶的音效輸出
:::
首先要思考的便是何為 `改進音效輸出`，我認為可以從兩個方面進行改進：
1. 音色
目前輸出的 wav 僅能說音準符合旋律，音色則不太符合我們日常所聽的音樂，需要對音色進行調整，使其符合我們認知中好聽的音色。
2. 旋律
目前旋律僅為單音所構成，缺少和弦編配，可以多加入一個聲部用以播放和弦。
這邊我先透過加入兩個額外的聲部，為旋律編入根音，以下為編入的根音
```c
const uint8_t twinkleTwinkleChord[] = {
48, 55, 53, 48, 0,
53, 48, 55, 48, 0,
48, 53, 48, 55, 0,
48, 53, 48, 55, 0,
48, 55, 53, 48, 0,
53, 48, 55, 48, 0,
};
const uint8_t twinkleTwinkleChordBeats[] = {
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
2, 2, 2, 2, 2,
};
```
此時生成的 wav 檔如下，旋律已聽上去比原來豐富：
[一閃一閃亮晶晶 with 根音](https://raw.githubusercontent.com/Mike1117/File/main/origin_with_simple_chord.wav)
後續將根音改進為分解和弦，音檔如下：
[一閃一閃亮晶晶 with 分解和弦](https://raw.githubusercontent.com/Mike1117/File/main/TTL_with_broken_chord.wav)
而針對音色的改進，我其實沒有什麼頭緒，所以先從顯而易見的問題先開始解決。
聆聽原始音檔以及加入和弦的兩個音檔，會覺得音色整體還是有一點點刺耳，此處可以簡單地透過調低 LP 的 factor 使其過濾更多的高頻雜音，結果如下：
[一閃一閃亮晶晶 with 更低的 LP 參數](https://raw.githubusercontent.com/Mike1117/File/main/TTL_with_low_factor_LP.wav)
但這樣做的結果就是整體音量會變低。
### [測驗三](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-3)
#### 填空部分
```
IIII = max_fd
JJJJ = &rfds
```
#### 延伸問題
:::success
解釋上述程式碼運作原理
:::
:::success
學習 [jserv/ttt](https://github.com/jserv/ttt) 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
:::
:::success
在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 [ping value](https://www.business.att.com/resources/knowledge-center/what-is-latency-impact-on-gaming-streaming.html) 的處理機制
:::
Sign in with Wallet
Connect another wallet