# 2025q1 Homework4 (quiz3+4)
contributed by <`Andrushika`>
## w3q1
本題使用 `mpi_t` 結構，作為包裝大數的基礎資料結構，結構定義如下：
```c
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data;
size_t capacity;
} mpi_t[1];
```
其中 `data` 會是儲存多個 32 bits (實際上是 31 bits) 整數的 array，`capacity` 則代表 array 的大小。注意到最終定義 `mpi_t[1]`，屬於一種小技巧，可以用來模擬物件導向風格的程式。
若要使用 `mpi_t`，在不使用上述技巧的情況下，會需要做以下操作進行初始化：
```c
mpi_t *number = malloc(sizeof(mpi_t));
mpi_init(number);
```
但使用上述技巧後，`mpi_t` 被定義為給定 `struct` 的陣列，所以記憶體空間已經分配好。使用 `mpi_t` 的方式就可以簡化：
```c
mpi_t number;
mpi_init(number);
```
可以發現 `number` 就像 OOP 中包裝好的 object 一樣，`mpi_t` 就像某個 class。
### AAAA
觀察 `ceil_div`，基本的除法向上取整操作：
```c
static size_t ceil_div(size_t n, size_t d)
{
return (n+d-1)/d; // AAAA
}
```
### BBBB
從先前定義的 `mpi_t` 可以發現 `data` 的基本單位應該為 32 bits signed int，但在題目的 context 下，mpi 只支援無號數運算，可以從以下 function 觀察出來：
```c
void mpi_set_u64(mpi_t rop, uint64_t op)
{
size_t capacity = ceil_div(64, 31);
mpi_enlarge(rop, capacity);
for (size_t n = 0; n < capacity; ++n) {
rop->data[n] = op & INTMAX;
op >>= 31;
}
for (size_t n = capacity; n < rop->capacity; ++n)
rop->data[n] = 0;
}
```
以上程式碼會以 31 bits 為單位儲存數值，因此，可以求得 `BBBB` 的答案：
```c
#define INTMAX 0x7fffffff // BBBB
```
### CCCC
`mpi_mul_naive` 使用類似直式乘法的概念來實作，每次相乘一位後持續往高位數進位。
```c
for (size_t n = 0; n < op1->capacity; ++n) {
for (size_t m = 0; m < op2->capacity; ++m) {
uint64_t r = (uint64_t) op1->data[n] * op2->data[m];
uint64_t c = 0;
for (size_t k = CCCC; c || r; ++k) {
if (k >= tmp->capacity)
mpi_enlarge(tmp, tmp->capacity + 1);
tmp->data[k] += (r & INTMAX) + c;
r >>= 31;
c = tmp->data[k] >> 31;
tmp->data[k] &= INTMAX;
}
}
}
```
`r` 代表剩餘需處理進位的數，`c` 表示 carry。
可以推得 `CCCC` 需填入 `n + m`，以對齊直式乘法操作時正確的位置。
### DDDD
`mpi_fdiv_qr` 的實作是使用二進位長除法的概念，維護一個 `r` 代表 remainder，從被除數的最高位做到最低位，每次將一位加入 remainder 中。當 `r > d` 代表有得除，將商的該位 bit 設為 1。
當初考試時一直卡在 `mpi_mul_2exp` 的作用。本函式的作用是將 mpi 乘上 2 的指數，實際上就是做左移操作。因為每次都要將被除數的一位加入 `r`，`r` 就需要事先左移空出一位。所以 `DDDD` 的答案：
```c
mpi_mul_2exp(r, r, 1); // DDDD
```
### EEEE
`mpi_gcd` 使用遞迴版本的[輾轉相除法](https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95)求最大公因數。每次求得 `op1 % op2` 的結果後，再用該結果進行下次的運算，因此可以填入 `EEEE`：
```c
mpi_gcd(rop, op2, r); // EEEE
```
### 將 `mpi_gcd` 的實作方式改為 iterative
```c
void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
// 額外增加 t1, t2 作為 tmp
mpi_t q, r, t1, t2;
mpi_init(q);
mpi_init(r);
mpi_init(t1);
mpi_init(t2);
mpi_set(t1, op1);
mpi_set(t2, op2);
while(mpi_cmp_u32(t2, 0) != 0){
mpi_fdiv_qr(q, r, t1, t2);
mpi_set(t1, t2);
mpi_set(t2, r);
}
mpi_set(rop, t1);
mpi_clear(q);
mpi_clear(r);
mpi_clear(t1);
mpi_clear(t2);
}
```
## w3q2
### `DETECT_NULL` 的巧思
本 macro 被用來確認 `X` 之中是否存在 NULL byte：
```c
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
```
為何這樣做有用？可以將每個 byte 分開、並拆成三種 case 來看。
因為最終會做 bitwise AND `0x80`，可以想成是對 MSB 進行檢測；接下來，關注 `MSB` 在不同 case 中是如何變化的。
#### case 1 `byte = 0x00`
在 `(X) - (0x0101010101010101)` 中：`0x00` - `0x01` = `0xFF`, `MSB = 1`
在 `~(X)` 中：`~0x00` = `0xFF`, `MSB = 1`
因為兩個 MSB 都被 set，最後檢測就會被判定為 NULL byte
#### case 2 `byte` 介於 `0x01` 到 `0x7F`
在 `(X) - (0x0101010101010101)` 中：`X` - `0x01`, `MSB = 0`
因此，無論後續做什麼操作，都不會被判定為 NULL byte
#### case 3 `byte` 介於 `0x80` 到 `0xFF`
在 `~(X)` 中：`MSB = 0`
因此，無論後續做什麼操作，都不會被判定為 NULL byte
根據 `memchr_opt` 的定義：
```c
void *memchr_opt(const void *str, int c, size_t len)
```
本函式會在長度為 `len` 的 `str` 中，尋找字元 `c` 是否存在。
### AAAA
`DETECT_CHAR` macro 透過前面提及的 `DETECT_NULL` 來幫助判斷給定的 `mask` 是否存在。只要先將 `mask` 對 `X` 做 XOR，就可以將 target byte 變成 NULL byte，進而能用 `DETECT_NULL` 判斷出來。
```c
#define DETECT_CHAR(X, mask) DETECT_NULL(X ^ mask)
```
### UNALIGNED 時的處理
若記憶體位置沒有和 `sizeof(long)` 對齊，則先一個一個字元讀取，並確定是否為目標字元，直到對齊為止。
```c
while (UNALIGNED(src)) {
if (!len--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
```
### BBBB, CCCC
當記憶體 `ALIGNED` 之後，就可以用題目所提及之 `SWAR` 方法快速求解。
首先需要將要尋找的目標 `d` 做成用來一次偵測多個 byte 的 `mask`，然後再使用 `DETECT_CHAR` 進行偵測：
```c
unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;+
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i; // BBBB
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask)) // CCCC
break;
asrc++;
len -= LBLOCKSIZE;
}
```
## w3q3
範例程式碼中實作了一個 `envs[NENV]` (`NENV = 1024`)，目的是保留不同 coroutine 的執行狀態。
### AAAA
在 `coro_create` 之中，會創建新的 `coroutine` 並進入等待被排程的狀態，所以可以填入：
```c
for (env = 0; env < NENV; env++) {
if (envs[env].status == ENV_UNUSED) /* Found a free environment */
break;
}
if (env == NENV) /* No free environments available */
return -1;
envs[env].status = ENV_RUNNABLE; // AAAA
```
注意到 `make_context` 的用法，其將用來設定 `context` 相關函式執行入口點及參數：
```c
makecontext(&envs[env].state, (void (*)(void)) entry, 1, args);
```
其中 `entry` 是在 `coro_create` 中傳入的函式指標。
### BBBB
根據題目敘述，排程採用 round-robin 策略，所以每次會找下一個 index 的 candidates，即：
```c
int candidate = (curenv + 1) % NENV; // BBBB
```
在選定 candidate 之後，就會設定一個 10 ms 的 timer，幫助後續進行 preempt，並使用 `setcontext` 跳回該 coroutine 先前執行到一半的狀態。
### CCCC
`coro_yield` 在讓出 CPU 之前，會先用保存 context，然後交由排程器決定下一個要執行的 coroutine，所以 `BBBB = coro_schedule`。
### DDDD
timer 將會觸發 `preempt()`，強制當前 coroutine 讓出 CPU，因此 `DDDD = coro_yield`
## w4q1
在 `crc32_naive` 做法中，會使用到「反向」二進位多項式除法的原理（即會從最低位開始運算，在二進位運算中，和從最高位開始會是等價的）。
### naive 版本的加速
參考 [Fast CRC32](https://create.stephan-brumme.com/crc32/)，一開始計算的迴圈部分如下：
```c
for (unsigned int j = 0; j < 8; j++)
if (crc & 1)
crc = (crc >> 1) ^ Polynomial;
else
crc = crc >> 1;
```
可以加速為 branch free 版本：
```c
for (unsigned int j = 0; j < 8; j++)
crc = (crc >> 1) ^ (crc & 1) * Polynomial;
```
然後再額外提升效能，由於 (crc & 1) 的結果始終只有 0 或 1，可以再簡化成以下版本：
```c
for (unsigned int j = 0; j < 8; j++)
crc = (crc >> 1) ^ (-(int)(crc & 1) & Polynomial);
```
### 作答
根據 [Fast CRC32](https://create.stephan-brumme.com/crc32/) 所提及的 "Half-Byte Algorithm"，可以用來產生剩餘的答案：
```c
for (unsigned int i = 0; i < 16; i++){
unsigned int crc = i;
for (unsigned int j = 0; j < 4; j++)
crc = (crc >> 1) ^ (-(int)(crc & 1) & 0x82f63b78);
printf("%x\n", crc);
}
```
<s>
`AAAA` = `0xC38D26C4`
`BBBB` = `0xD3D3E1AB`
`CCCC` = `0xE330A81A`
`DDDD` = `0xF36E6F75`
</s>
:::danger
不要列出參考題解，專注題目本身
:::
## w4q2
### Phase Increment
因為程式是使用離散取樣模擬 phase，要產生特定波的時候，可以想像成每次取樣都推進一點 phase。假設每秒取樣 $f_s$ 次，而我們想產生 $f_0$ Hz 的音的時候，可以透過下列算式計算每次 sample 時 phase 該增加多少：
$$\Delta \theta = \frac{f_0}{f_s} \cdot 2\pi$$
題目中使用 Q15 去表示 phase ($0 \sim 2\pi$)：
$$phase\_incr = \frac{f_0}{f_s} \cdot Q15\_MAX$$
對應的實作 code:
```c
#define SYNTH_HZ_TO_PHASE(frequency) ((frequency * Q15_MAX) / SAMPLE_RATE)
static const q15_t octave_phases[12] = {
// start at C8
SYNTH_HZ_TO_PHASE(4186.01), // C
SYNTH_HZ_TO_PHASE(4434.92), // C#
SYNTH_HZ_TO_PHASE(4698.63), // D
SYNTH_HZ_TO_PHASE(4978.03), // D#
SYNTH_HZ_TO_PHASE(5274.04), // E
SYNTH_HZ_TO_PHASE(5587.65), // F
SYNTH_HZ_TO_PHASE(5919.91), // F#
SYNTH_HZ_TO_PHASE(6271.93), // G
SYNTH_HZ_TO_PHASE(6644.88), // G#
SYNTH_HZ_TO_PHASE(7040.00), // A
SYNTH_HZ_TO_PHASE(7458.62), // A#
SYNTH_HZ_TO_PHASE(7902.13), // B
};
static q15_t midi_to_phase_incr(uint8_t note)
{
int octave = note / 12;
int note_index = note - (octave * 12);
q15_t phaseIncr = octave_phases[note_index];
// 每下降一個八度，頻率會是原來的一半
phaseIncr >>= (BASE_OCTAVE - octave + 1);
return phaseIncr;
}
```
### Envelope, ADSR
- Attack: 從沒聲音到最大聲，所花費的「時間」
- Decay: 從最大聲降到平穩音量，所花費的「時間」
- Sustain: 平穩音量的大小（唯一和時間無關的參數）
- Release: 聲音結束後，音量降到完全沒聲音的「時間」
### 低通濾波器 (Low-Pass Filter)
$$y[n] = y[n-1] + \alpha (x[n] - y[n-1])$$
- $y[n-1]$ 是上一次的輸出
- $x[n]$ 是當前的輸入
- $\alpha$ 控制平滑度，其範圍在 0 到 1 之間
### AAAA
接下來是根據 node type 更新 `state` 的部分，此處的 osc 因為要確保 state 始終可以用 Q15 來表示 phase，所以使用模除運算處理。
```c
case SYNTH_NODE_OSCILLATOR:
// 推進相位，加上 detune，並環繞
node->state += *node->osc.phase_incr;
if (node->osc.detune)
node->state += *node->osc.detune;
node->state &= Q15_MAX; /* AAAA, wrap around q15 */
break;
```
### BBBB ~ EEEE
這段集中在處理 envelope，先看先前取 state 值的方式：
```c
case SYNTH_NODE_ENVELOPE:
outputs[i] = (node->state & 0x7FFFFF) >> 4;
```
所以對於 `SYNTH_NODE_ENVELOPE`，低 23 位應該會用來存 value，然後才進行右移，目的是為了保留額外的 4 位精度。
同時註解中提到：
> The highest bit in the state indicates decay mode
所以 `BBBB` 應填入：
```c
int mode_bit = node->state & 0x00800000; // get bit 23
```
`CCCC` 則是 `0x7FFFFF`，如先前所示。
`DDDD` 需要在 attack 階段結束、value 達到最大值時，設置為 decay mode，所以應填入 `0x00800000`。
`EEEE` 的作用是在 gate 關閉時、release 作用時，把 decay bit 清除掉，這樣下一次 gate 打開時才可以直接進入 attack；應填入 `0xFF7FFFFF`。
### FFFF
`sine_wave` 的實作原理是，先使用 look up table 對比較大 scale 下的數值查表，查表後再用線性插值法提升精確度。
由於 input phase 是使用 `q15_t` 表示，且 index 讀取時先右移八位，代表最高七位會用來當 index。
先填入 `FFFF`：
```c
res += ((next - res) * (input & 0xFF) >> 8);
```
以上運算，可以想像是對 res 和 next 中間先計算「距離 table 的下一個點，目前走了多少百分比？」，然後用這個百分比來插值。
### GGGG, HHHH
`square_wave` 也是輸入 phase，輸出對應的波。
需要在前半個週期輸出 `+1`, 後半個週期輸出 `-1`，因此修改如下：
```c
q15_t square_wave(q15_t input)
{
return input < Q15_MAX/2
? Q15_MAX // GGGG
: Q15_MIN; // HHHH
}
```
## w4q3
### 實作原理
本題使用 `select` 實作了 TCP 連線工具，有幾個變數值得注意：
`server_fd`：負責處理新 socket 連線的 file descriptor。
`conns[FD_SETSIZE]`：在接收到 socket 連線請求後，會得到一個連線成功後傳輸資料用的 fd。`conns[fd] = 1` 時代表目前已建立連線，同時會將 fd 加入 `&rfds`，以便使用 `select()` 觀測。
### IIII, JJJJ
此處考的是 select 的用法，參照 linux manual page:
```c
int select(int nfds, fd_set *_Nullable restrict readfds,
fd_set *_Nullable restrict writefds,
fd_set *_Nullable restrict exceptfds,
struct timeval *_Nullable restrict timeout);
```
`IIII` 對應的是 `nfds`，說明如下：
> This argument should be set to the highest-numbered file descriptor in any of the three sets, plus 1. The indicated file descriptors in each set are checked, up to this limit (but see BUGS).
因為 rfds 只有監聽 `server_fd`，所以 `IIII` 應填入 `server_fd + 1`，也就是 `max_fd`。
`JJJJ` 對應的是 `readfds`，此處應填入 `&rfds`。值得注意的是，在 `select()` return 之後，`rfds` 會被改變，只剩下已經 ready 的 fds 被 set。
:::info
關於 select 運作的疑惑：
在我的理解中，`select` 應該是在偵測到任何一個 file descriptor ready 時，就會馬上 return。在微觀的角度下，kernel 應該無法「同時」偵測到多個 file descriptor ready，而在偵測到任一 fds ready 就要馬上 return 的狀況下，為何會出現 rfds 中可以找到多個 `FD_ISSET` 的狀況？
:::
### 關於 select 運作問題：ChatGPT 的回答
#### `do_select()` 的工作流程
以下是 `do_select()` 函數的簡化流程：
```c
int do_select(int n, fd_set_bits *fds, struct timespec64 *end_time) {
// 初始化等待佇列
poll_initwait(&table);
// 設定當前進程的狀態為可中斷的睡眠狀態
set_current_state(TASK_INTERRUPTIBLE);
// 檢查所有關心的檔案描述符是否就緒
for (i = 0; i < n; ++i) {
if (檔案描述符 i 就緒) {
// 如果有描述符就緒，則立即返回
return 就緒的描述符數量;
}
}
// 如果沒有描述符就緒，則進入等待狀態，直到有事件發生或超時
poll_schedule_timeout(&table, TASK_INTERRUPTIBLE, timeout, slack);
// 醒來後再次檢查描述符狀態
...
}
```
這段程式碼展示了 `do_select()` 如何初始化等待佇列，檢查描述符狀態，並在必要時進入等待狀態。
#### 為什麼 `select()` 可能返回多個就緒的描述符？
正如您之前提到的，從物理層面來看，兩個事件不可能在完全相同的時間發生。然而，對於 `select()` 而言，它關心的是在一次系統呼叫期間，哪些描述符在其返回之前變成了就緒狀態。這意味著：
如果在 `select()` 被呼叫後，`fd1` 和 `fd2` 都在其返回之前變成了就緒狀態，則 `select()` 會同時報告這兩個描述符為就緒。
這種行為是因為 `select()` 在返回時會檢查所有關心的描述符，並將所有已就緒的描述符標記在 `fd_set` 中。
Sign in with Wallet
Connect another wallet