# 2025q1 Homework4 (quiz3+4)
contributed by <`MikazukiHikari`>
## quiz3
### 測驗`1`
```c
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data;
size_t capacity;
} mpi_t[1];
```
宣告了一個名為 `mpi_t` 的型別別名，實際上是含有一個元素的 `struct` 陣列；`data` 用來儲存這個多精度整數的「每一段資料」；`capacity` 是這個 `mpi_t` 能容納多少個 `uint32_t` 整數段。
其記憶體管理相關的操作如下:
* `mpi_init`：初始化一個 mpi_t 結構，使其處於「空值」狀態。
* `mpi_clear`：釋放 `data` 所指向的記憶體空間。
* `mpi_enlarge`：將 `rop` 的容量擴充至指定大小，如果目前容量不足。`realloc` 嘗試重新配置記憶體，讓它有 `capacity * 4` bytes 空間（`uint32_t` 為 4 bytes）。如果擴充記憶體成功，會把新擴空間的元素設成 0（清除舊資料以外的空間）。
* `mpi_compact`：將多餘的 0 結尾裁掉，也就是將數字尾端無意義的 0 移除，節省記憶體。for 迴圈從`rop->data`的尾端找，直到找到非零的數值才停下，這時候 `capacity` 就是新的有效長度。
接著準備基本操作:
* `ceil_div`：整數版的向上取整除法，每當 `n` 不是剛好能整除 `d`，就需要「多一格」來裝剩下的部分。`(n + d - 1)` 就是在模擬「多一格的情況」，強迫向上取整，`AAAA`為`(n + d - 1) / d` $(n + d - 1)/d = (n +(d-1))/d$，會衍生兩種情形：
1. n 可以被 d 整除： $(d-1)/d=0$ ，答案一樣。
2. n 不可被 d 整除： 即使 $n/d$ 的餘數只有1，結果依然是$((x*d+1)+d-1)/d=x+1$，依然有達成向上取整的效果。
* `BBBB`是 `0x7FFFFFFF`：由於這裡是把 64-bit 值「每 31 bits」切一段裝進 `uint32_t` 陣列中，所以需要一個遮罩也就是` 0x7FFFFFFF`。
* `mpi_set_u64`：把一個 `uint64_t` 的數字，存進一個多精度整數陣列中，每段用 31 位元表示。
基本的乘法運算：
* `mpi_mul_naive`：雙層迴圈對 `op1` 和 `op2` 每一位做乘法。`r` 是乘積，最多有 62 bits，因為每段用 31 bits 表示，以 31 位數為單位去做一次乘積。第三層迴圈負責處理進位與展開的多位加總。`CCCC`為`n+m`，代表此乘積的結果是從直式乘法的哪一位開始填，例如第 2 位 × 第 3 位 → 放在第 5 位。並且`r & INTMAX`會取出最低 31 bit 加上上一輪進位 `c`，加總結果後判斷有無進位，最後保留 31-bit 結果，其餘變成新的進位。
除法和餘數運算:
* `mpi_fdiv_qr`：先複製一份 `n` 和 `d` 到新的變數`n0` 和 `d0`中，接著檢查除以 0 要報錯，初始化商`q`與餘數`r`，計算起始位元位置（最高位）。接著 `for` 迴圈從高位往低位掃描，每次將餘數左移一位(乘2)，因此`DDDD`為`1`，再把 `n0` 的第 `i` 個 bit 接到 `r` 最低位，就像被除數再拉下一位數字來比對，接著嘗試減去除數，若`mpi_cmp(r, d0) >= 0`代表可以減掉一次除數（也就是商這一位是 1），並更新商的第 `i` 個 bit為`1`，然後新的一輪。最後得出商和餘數，並清掉暫存用的多精度整數，避免 memory leak。
最大公因數運算:
* `mpi_gcd`：用輾轉相除法，遞迴方式計算最大公因數，將每次`mpi_fdiv_qr`得出的餘數作為新的`op2`，原先的`op2`作為新的`op1`，不斷遞迴直到哪次`op2=0`，就將`rop=op1`，一路 `return` 回上一層，最終 `rop` 就會變成 GCD。因此 `EEEE：mpi_gcd(rop, op2, r)`。
:::success
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
:::
把原來遞迴的 `mpi_gcd` 改為迴圈版並減少重複配置變數，避免每次都要 `mpi_init` 或`clear` 。
```c
void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
mpi_t a, b, q, r;
mpi_init(a);
mpi_init(b);
mpi_init(q);
mpi_init(r);
mpi_set(a, op1);
mpi_set(b, op2);
while (mpi_cmp_u32(b, 0) != 0) {
mpi_fdiv_qr(q, r, a, b);
mpi_set(a, b);
mpi_set(b, r);
}
mpi_set(rop, a);
mpi_clear(a);
mpi_clear(b);
mpi_clear(q);
mpi_clear(r);
}
```
### 測驗`2`
尋找某個位元組是否出現在某段記憶體中，並儘可能使用 64-bit 比對以提升效能。
```c
#define DETECT_CHAR(X, mask) DETECT_NULL((X) ^ (mask))
```
`AAAA`為`(X) ^ (mask)`，透過 `XOR` 運算檢查`X` 裡是否有任一 byte 等於目標字元。
```c
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
```
`BBBB`為`mask << i`，這段迴圈會用位移和 `OR`，把 `mask` 複製成一整個 `long`，例如本來是 `0x0000000000000063`（64-bit）轉成 `0x6363636363636363`（64-bit），但這段程式應該可以化簡成：
```c
unsigned long mask = d ;
for (unsigned int i = 8; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask << i;
```
```c
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
```
`CCCC`為`*asrc`，`asrc` 是一個指向 `unsigned long` 的指標，並且初始值是 `src`。將整段字串照 `long` 讀進來，`DETECT_CHAR` 用 `XOR` 和 `mask` 比對，若結果某 byte 會變 `0x00` ，接著將包含有某變成`0x00`的byte進行`DETECT_NULL` ：
1. `(X - 0x01010101...)` → 該 byte 會變成 `0xFF`
2. `~X` → 該 byte 會變成 `0xFF`
3. `&`：兩者`AND`，該 byte 仍是 `0xFF`
4. `& 0x80808080`...：只留下最高位元的判斷標記位（bit 7）
如果結果是非 0，代表至少有一個 byte 是 `0x00`。接著，在這裡面去找那個字元的位置。
### 測驗`3`
首先在`main`呼叫 `enable_preemption` 和 `init_threads` 。
* `enable_preemption` ：`struct sigaction` 設定一個 signal handler，當 signal 到來時，呼叫 `preempt`；`sigevent` 結構定義了 timer 到期時該怎麼通知，設定為「用 signal 通知」並指定哪一個 signal（`SIGRTMIN`）；`sigemptyset`：確保進入 handler 時不封鎖其他訊號。之後正式註冊 signal 處理函式，並透過timer，定時的發出一個signal。
* `init_threads`：主要是建立第一個協程，設定好在結束時要跳去的結尾處，然後就把控制權交給協程並開始跑起來。首先設定目前正在執行的協程編號為 0；接著，建立`exiter` 這個` ucontext_t` 儲存目前狀態，並給`exiter` 分配一塊新的堆疊，再設定`exiter` 在執行時會呼叫 `coro_exit`；接下來是呼叫 `coro_create`，幫 `user_main` 包成一個 coroutine 放入 `envs[0]` 中，並設定 stack、context、初始狀態等；最後直接跳入第 0 個協程（就是 `user_main`）開始執行，也就是去呼叫 `coro_main`。
接下來分別討論一下其他函式：
* `coro_create`：掃描 `envs` 陣列（上限 1024 個）找一個沒被使用的 slot。如果都滿了就回傳 `-1` 表示失敗。標記這個 slot 是可執行的狀態，`AAAA`是`ENV_RUNNABLE`。接著，初始化它的 context，設定 `stack`，之後：
```c
envs[env].state.uc_link = &exiter;
```
這代表當某個協程主體函式跑完，會自動跳到 `exiter`，進而呼叫 `coro_exit`。而 `exiter` 的內容是在 `init_threads()` 裡設定的，最後一旦協程函式跑完，就會自動呼叫 `coro_exit` 做清理和排程。
* `coro_schedule`：環狀的找到下一個狀態是 `ENV_RUNNABLE` 的進程，若找到了則執行 `setcontext`，因此`BBBB`是`attempts + 1`；如果沒有任何 RUNNABLE coroutine，就結束整個程式。
* `coro_yield`：使用`envs[curenv].state_reentered`分辨現在是第一次儲存 `context`還是從 `setcontext` 回來之後，前者會進入 `coro_schedule`，所以`CCCC`是`coro_schedule`；後者不會再進 `coro_schedule` 會自動接著執行「當初 `yield` 時停下的地方」
* `coro_recv`：當 coroutine 呼叫 `coro_recv` 代表將狀態標為 `ENV_WAITING`；呼叫 `coro_yield` ，保存自己的 context，交給 scheduler；之後就等其他 coroutine 透過 `coro_send` 喚醒這個context，也就是將其設為 `ENV_RUNNABLE`，它就會醒來接收訊息（它之後會被排程器叫到）。
* `coro_send`：檢查對方是否已經進入 `ENV_WAITING`，若還沒，就持續呼叫 `coro_yield`，讓其他 coroutine 有機會執行；一旦對方狀態為 `ENV_WAITING`，則設定對方的 sender ID、value，並把對方設為 `ENV_RUNNABLE`，讓排程器之後可以排程它執行。
* `preempt`：`DDDD`為`coro_yield`，這樣才能在固定的時間觸發 coroutine 切換。
## quiz4
### 測驗`1`
我們實作程式碼，讓其手動產生表格，並且其具備與 `crc32_naive` 完全等效的行為
```c
#include <stdint.h>
#include <stdio.h>
#define POLY 0x82F63B78
void generate_crc32c_table() {
printf("static const uint32_t crc32c_table[16] = {\n");
for (uint32_t i = 0; i < 16; ++i) {
uint32_t crc = i;
for (int j = 0; j < 4; ++j) {
if (crc & 1)
crc = (crc >> 1) ^ POLY;
else
crc = (crc >> 1);
}
printf(" 0x%08x%s", crc, (i % 4 == 3) ? ",\n" : ", ");
}
printf("};\n");
}
```
輸出如下：
```
static const uint32_t crc32c_table[16] = {
0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1,
0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d,
0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9,
0xc38d26c4, 0xd3d3e1ab, 0xe330a81a, 0xf36e6f75,
};
```
舉例: index 12：i = 12 = `0b1100`
```
初始值：0x0C
Step 1: 0x0C & 1 = 0 → crc = 0x06
Step 2: 0x06 & 1 = 0 → crc = 0x03
Step 3: 0x03 & 1 = 1 → crc = (0x01 ^ POLY) = 0x82F63B79
Step 4: 0x82F63B79 & 1 = 1 → crc = ((0x82F63B79 >> 1) ^ POLY) = 0xC38D26C4
```
因此`crc32c_table[12]` = `0xc38d26c4`
其他的以此類推。
:::success
在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
:::
1. 在 [lib/crc32.c](https://github.com/torvalds/linux/blob/master/lib/crc32.c) 中提供了基本的 CRC32 計算函式，使用查表法來加速計算：
```c
// little-endian CRC32 計算 (常用於網路協議)
u32 crc32_le_base(u32 crc, const u8 *p, size_t len) {
while (len--)
crc = (crc >> 8) ^ crc32table_le[(crc & 0xff) ^ *p++];
return crc;
}
// big-endian CRC32 計算 (常用於儲存系統)
u32 crc32_be_base(u32 crc, const u8 *p, size_t len)
{
while (len--)
crc = (crc << 8) ^ crc32table_be[(crc >> 24) ^ *p++];
return crc;
}
```
函式針對 little-endian / big-endian 進行計算，透過查找預先生成的 `crc32table_le` / `crc32table_be` 表來快速計算每個位元組的 CRC 值。
2. 在 [crypto/crc32c_generic.c](https://github.com/torvalds/linux/blob/master/crypto/crc32c_generic.c)
此程式碼是 Linux 核心中 CRC32C 算法的標準實現樞紐，透過加密框架提供統一的校驗接口，同時整合軟硬體加速，廣泛應用於儲存、網路等關鍵子系統的數據完整性保護。
```c
//通用軟體實現核心計算函數
static int chksum_update(struct shash_desc *desc, const u8 *data,
unsigned int length)
{
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
ctx->crc = crc32c_base(ctx->crc, data, length);
return 0;
}
//硬體加速實現核心計算函數
static int chksum_update_arch(struct shash_desc *desc, const u8 *data,
unsigned int length)
{
struct chksum_desc_ctx *ctx = shash_desc_ctx(desc);
ctx->crc = crc32c(ctx->crc, data, length);
return 0;
}
```
這邊也是透過預先計算的查詢表加速計算。
```c
static struct shash_alg algs[] = {{
.digestsize = CHKSUM_DIGEST_SIZE,
.setkey = chksum_setkey,
.init = chksum_init,
.update = chksum_update,
.final = chksum_final,
.finup = chksum_finup,
.digest = chksum_digest,
.descsize = sizeof(struct chksum_desc_ctx),
.base.cra_name = "crc32c",
.base.cra_driver_name = "crc32c-generic",
.base.cra_priority = 100,
.base.cra_flags = CRYPTO_ALG_OPTIONAL_KEY,
.base.cra_blocksize = CHKSUM_BLOCK_SIZE,
.base.cra_ctxsize = sizeof(struct chksum_ctx),
.base.cra_module = THIS_MODULE,
.base.cra_init = crc32c_cra_init,
}, {
.digestsize = CHKSUM_DIGEST_SIZE,
.setkey = chksum_setkey,
.init = chksum_init,
.update = chksum_update_arch,
.final = chksum_final,
.finup = chksum_finup_arch,
.digest = chksum_digest_arch,
.descsize = sizeof(struct chksum_desc_ctx),
.base.cra_name = "crc32c",
.base.cra_driver_name = "crc32c-" __stringify(ARCH),
.base.cra_priority = 150,
.base.cra_flags = CRYPTO_ALG_OPTIONAL_KEY,
.base.cra_blocksize = CHKSUM_BLOCK_SIZE,
.base.cra_ctxsize = sizeof(struct chksum_ctx),
.base.cra_module = THIS_MODULE,
.base.cra_init = crc32c_cra_init,
}};
```
透過 `crypto_register_shashes` 註冊到 Linux 加密子系統，使其他模組可透過 `crypto_alloc_shash("crc32c", 0, 0)` 調用此算法。
3. 在 [fs/f2fs/checkpoint.c](https://github.com/torvalds/linux/blob/master/fs/f2fs/checkpoint.c)
F2FS 文件系統檢查點的校驗和計算核心，主要功能是確保檢查點數據的完整性。
```c
static __u32 f2fs_checkpoint_chksum(struct f2fs_sb_info *sbi,
struct f2fs_checkpoint *ckpt)
{ // 從檢查點結構 f2fs_checkpoint 中提取校驗和字段的偏移位置
unsigned int chksum_ofs = le32_to_cpu(ckpt->checksum_offset);
__u32 chksum;
chksum = f2fs_crc32(sbi, ckpt, chksum_ofs); // 計算從檢查點結構起始地址到校驗和字段偏移位置前的數據 CRC32 值
// 當校驗和字段位置小於標準偏移量時,跳過校驗和字段並補算剩餘數據
if (chksum_ofs < CP_CHKSUM_OFFSET) {
chksum_ofs += sizeof(chksum);
chksum = f2fs_chksum(sbi, chksum, (__u8 *)ckpt + chksum_ofs,
F2FS_BLKSIZE - chksum_ofs);
}
return chksum;
}
```
### 測驗`2`
* `AAAA`：`0x7FFF`
* `BBBB`：`0x80000000`
* `CCCC`：`0x7FFFFFFF`
* `DDDD`：`0x80000000`
* `EEEE`：`0x7FFFFFFF`
* `FFFF`：`input & 0xFF`
* `GGGG`：`Q15_MAX`
* `HHHH`：`Q15_MIN`
使用 `synth_node_t` 統一所有模組的結構。每個聲音模組都被抽象成一個「節點」，每個節點會：
* 根據輸入計算輸出
* 可以串接其他節點（聲音來源）
* 支援不同類型：振盪器、包絡、濾波器、等等
```c
typedef enum {
SYNTH_NODE_NONE = 0,
SYNTH_NODE_OSCILLATOR,
SYNTH_NODE_ENVELOPE,
SYNTH_NODE_FILTER_LP,
SYNTH_NODE_FILTER_HP,
SYNTH_NODE_MIXER,
SYNTH_NODE_END
} synth_node_type_t;
```
定義了一個 `synth_voice_t` 結構，每個聲部包含最多 `SYNTH_MAX_NODE` 個節點（模組）：
```c
typedef struct {
synth_node_t nodes[SYNTH_MAX_NODE];
int note;
q15_t phase_incr;
} synth_voice_t;
```
目前支援 2 個聲部：
```c
synth_voice_t synth_voices[SYNTH_MAX_VOICE];
```
將物理頻率轉換為 Q15 格式的相位增量，使用定點數乘法避免浮點運算
「頻率」轉換為「相位增量」公式：$Δphase=\frac{f_{Hz}×2^{15}}{fs}$
```c
#define BASE_OCTAVE 8
#define SYNTH_HZ_TO_PHASE(f) ((f * Q15_MAX) / SAMPLE_RATE)
```
八度相位表：每個元素對應一個半音
```c
static const q15_t octave_phases[12] = {
/* C8~B8 phase increment */
};
```
#### 音頻節點初始化
振盪器節點：`synth_init_osc_node`
包絡節點：`synth_init_envelope_node`
低通濾波器：`synth_init_filter_lp_node`
#### 音符觸發機制
`synth_voice_note_on`：重置振盪器相位、包絡狀態、濾波器累積值的節點狀態，設定 `gate=1` 啟動包絡的攻擊階段。
`synth_voice_note_off`：設定 `gate=0`。
#### 聲音處理流程`synth_process`
```c
int32_t outputs[SYNTH_NODES];
for (int i = 0; i < SYNTH_NODES; i++) {
// 根據節點類型計算輸出
switch (node->type) {
case SYNTH_NODE_OSCILLATOR:
tmp = node->state & 0x7FFF; // 相位截斷
outputs[i] = wavegen(tmp); // 波形生成
break;
case SYNTH_NODE_ENVELOPE:
value = (node->state & 0x7FFFFF) >> 4; // 提取數值
outputs[i] = (value * value) >> 15; // 平方強化動態
break;
}
// 應用增益
outputs[i] = (outputs[i] * *node->gain) >> 15;
}
```
使用臨時陣列 `outputs[]` 暫存計算結果，避免狀態更新影響同幀計算。
##### 振盪器狀態更新
```c
node->state += *phase_incr + *detune; // 相位累加
node->state &= 0x7FFF; // Q15 相位環繞
```
振盪器相位用 15 位元無號數表示 (0 ~ 32767)，因此`AAAA = 0x7FFF`。
##### 包絡狀態機詳解
狀態壓縮格式：
| 第 31 位 | 第 30 ~ 0 位 |
|-------|---------------|
| 模式 | 數值 |
模式位 (`BBBB = 0x80000000`)：最高位為 `1` 表示衰減模式；`0` 表示攻擊模式。
數值位 (`CCCC = 0x7FFFFFFF`)
衰減階段：
```c
value -= node->env.decay;
if (value < sustainAbs << 4)
value = sustainAbs << 4; // 維持到門控關閉
```
持續機制：保持電平直到 `gate=0`，避免持續衰減至零。
攻擊階段：
```c
value += attack; // 線性增加
if (value > Q15_MAX << 4) { // 達到峰值
value = Q15_MAX << 4;
mode_bit = 0x80000000; // 切換模式
}
```
當`value`達到峰值，從攻擊模式切換至衰減模式，因此 `DDDD = 0x80000000`。
釋放階段：
```c
node->state &= 0x7FFFFFFF; // 清除模式位
node->state -= release; // 線性釋放
if (node->state < 0) node->state = 0;
```
到了釋放階段必須重置狀態並清除模式位，確保下次觸發從攻擊階段(`mode_bit=0`)開始，因此`EEEE=0x7FFFFFFF`。
##### 濾波器實作
低通濾波器：
```c
outputs[i] = (node->filter.accum * node->filter.factor) >> 15; // IIR 濾波
node->filter.accum += (*node->filter.input - node->output); // 狀態更新
```
高通濾波器：
```c
outputs[i] = (node->filter.accum * node->filter.factor) >> 15;
outputs[i] = *node->filter.input - outputs[i];
```
從原始信號減去低通成分，保留高頻。
##### 混音與輸出級
```c
main_output += voice->nodes[0].output; // 各聲道主輸出
return (main_output * gain) >> 15; // 總增益調整
```
#### 波形生成函式
`sawtooth_wave`：
```c
q15_t sawtooth_wave(q15_t input) {
return input * 2 - Q15_MAX; // 轉換為 [-32767, 32767]
}
```
輸出公式為$y=2x−1$，將無號相位值轉換為對稱鋸齒波。
`sine_wave`：
```c
q15_t sine_wave(q15_t input) {
int index = (input >> 8) & 0x7F; // 取高 7 位元作為 LUT 索引
q15_t res = sine_lut[index] * 258; // 擴展到 Q15 範圍
q15_t next = sine_lut[index + 1] * 258;
res += ((next - res) * (input & 0xFF) >> 8); // 線性插值
return res;
}
```
使用相位值的低 8 位元 `(input & 0xFF)`=`FFFF` 作為插值權重，數學公式為:
$y = y_n + (y_n+1 −y_n )× \frac{input最低 8 位}{256}$
`square_wave`：
```c
q15_t square_wave(q15_t input) {
return input < Q15_MAX / 2 ? Q15_MIN : Q15_MAX; // GGGG=Q15_MIN, HHHH=Q15_MAX
}
```
利用比較輸入與 0.5的結果直接返回極值，小於則返回 Q15最小值，大於等於則返回 Q15最大值，以此建構方波。
#### 《小星星》旋律生成機制
MIDI 音符對照表
```c
const uint8_t twinkleTwinkle[] = {
60,60,67,67,69,69,67,0, // C4 C4 G4 G4 A4 A4 G4 (休止)
65,65,64,64,62,62,60,0, // F4 F4 E4 E4 D4 D4 C4 (休止)
// ... 重複段落
};
```
* 音高轉換：使用 `midi_to_phase_incr` 將 MIDI 音符號碼轉換為相位增量
* 節奏控制：`twinkleTwinkleBeats` 數組定義每音符的拍數，透過 `SYNTH_MS(2000/beat)` 轉換為樣本數
音符觸發時序圖
```
樣本數 0 500 1000 1500
Voice 0 [C4]-------------[G4]--------------
Voice 1 [C2]-------------[G2]--------------
| 攻擊 | 衰減 | 持續 | 釋放
```
在音符結束前 500 樣本(約45ms)觸發釋放階段，避免音尾截斷。
:::success
探討定點數的使用和其精確度
:::
以下探討聚焦於本題程式碼中的定點數格式在音頻合成中的關鍵設計及精確度
#### Q15 定點數格式規範
* 位元分配：16 位元有號數，1 位元符號 + 15 位元小數。
* 數值範圍：−1.0 ∼ +0.999969482 (即 `0x8000` 至 `0x7FFF`)。
* 在這裡的意義：1.0 對應 `0x7FFF`，-1.0 對應 `0x8000`。
#### 關鍵模組精度分析
1. 振盪器相位累加
```
node->state += *node->osc.phase_incr;
node->state &= 0x7FFF;
```
* 精度損失：相位累加誤差每週期 $Δ= \frac{1}{32768}$ ≈ 0.003%
* 頻率解析度：$f_{res} = \frac{f_s}{2^{15}} = \frac{11025}{32768}$ ≈ 0.336 Hz (`SAMPLE_RATE`=`11025`)
2. 包絡狀態機
```
value += node->env.attack;
if (value > (int32_t) Q15_MAX << 4) {
value = (int32_t) Q15_MAX << 4;
mode_bit = 0x80000000;
}
```
* 精度擴展：`Q15_MAX << 4`表明包絡值被放大了 $2^4 =16$ 倍，這相當於將原本的 Q15 格式擴展為 ==Q27== 格式（15 位小數增加到 5 位整數 + 27 位小數）。並且在輸出階段，包絡值被右移 4 位回 Q15 格式。
* 時間解析度：$t_{step} = \frac{1}{f_s ×2^{27}}$ ≈ $6.76×10^{−13}$ 秒 (`SAMPLE_RATE`=`11025`)
### 測驗`3`
這段程式的重點在於使用 `select` 函式來監控多個 socket file descriptor 的 可讀事件，實作出一個簡單的多用戶聊天室伺服器。
`select()` 系統調用允許程式同時監控多個文件描述符的狀態變化。應用場景包括：
* 檢測文件描述符是否可讀（讀操作不會阻塞）
* 檢測文件描述符是否可寫（寫操作不會阻塞）
* 檢測異常條件（如 out-of-band data）
```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);
```
各個參數的功能如下：
* `nfds`：整數值，指集合中所有檔案描述符的範圍，其值應為所有檔案描述符的最大值加1，不能錯！在Windows中這個參數的值無所謂，可以設定不正確。
* `readfds`：指向`fd_set`結構的指標，這個集合中應該包括檔案描述符，我們是要監視這些檔案描述符的==可讀==變化的，即我們關心是否可以從這些檔案中讀取資料了，如果這個集合中有一個檔案可讀，`select`就會返回一個大於0的值，表示有檔案可讀，如果沒有可讀的檔案，則根據`timeout`參數再判斷是否逾時，若超出`timeout`的時間，`select`返回0，若發生錯誤返回負值。可以傳入`NULL`值，表示不關心任何檔案的讀變化。
* `writefds`：指向`fd_set`結構的指標，這個集合中應該包括檔案描述符，我們是要監視這些檔案描述符的==可寫==變化的，即我們關心是否可以向這些檔案中寫入資料了，如果這個集合中有一個檔案可寫，`select`就會返回一個大於0的值，表示有檔案可寫，如果沒有可寫的檔案，則根據`timeout`參數再判斷是否逾時，若超出`timeout`的時間，`select`返回0，若發生錯誤返回負值。可以傳入`NULL`值，表示不關心任何檔案的寫變化。
* `exceptfds`：指向 `fd_set` 結構，用來監控==異常情況==。
* `timeout`：是`select`的逾時時間，這個參數至關重要，它可以使`select`處於三種狀態：
* 若將`NULL`以形參傳入，即不傳入時間結構，就是將`select`置於阻塞狀態，一定等到監視檔案描述符集合中某個檔案描述符發生變化為止
* 若將時間值設為0秒0毫秒，就變成一個純粹的非阻塞函數，不管檔案描述符是否有變化，都立刻返回繼續執行，檔案無變化返回0，有變化返回一個正值
* `timeout`的值大於0，這就是等待的逾時時間，即 `select`在`timeout`時間內阻塞，逾時時間之內有事件到來就返回了，否則在逾時後不管怎樣一定返回，傳回值同上述。
返回值：
* 成功時返回已準備好的文件描述符數量（大於 0 的整數）。
* 若無文件描述符準備就緒且超時，返回 0。
* 發生錯誤時返回 -1，並設置 errno（錯誤代碼）。
`nfds`要比最高監聽數字還要多1，也就是 `server_fd + 1` ，剛好程式碼已經幫我們計算 `max_fd = server_fd + 1`，因此，`IIII`是`max_fd`。
```c
int max_fd = server_fd + 1;
max_fd = fd + 1;
```
接著，`JJJJ` 是 `&rfds`，是待監聽「可讀事件」的 `fd_set`。
每一輪迴圈邏輯：
```c
while (select(max_fd, &rfds, NULL, NULL, NULL) >= 0) {
}
```
`select `會一直阻塞直到：
* 有 client 連進來（`server_fd` 變成可讀）
```c
int new_fd = accept(server_fd, ...);
conns[new_fd] = 1; // 記錄這個 fd 有 client
FD_SET(new_fd, &rfds); // 下輪要監控它
max_fd = new_fd + 1; // 更新最大 fd
```
* 有 client 傳資料進來（對應的 `client_fd` 變成可讀）
```c
int nread = read(fd, buf, sizeof(buf));
```
每輪要重建 `rfds`
```c
FD_ZERO(&rfds);
FD_SET(server_fd, &rfds);
for (int fd = 0; fd < FD_SETSIZE; fd++) {
if (conns[fd]) {
FD_SET(fd, &rfds);
max_fd = fd + 1;
}
}
```
因為`select` 會修改傳進去的 `rfds`，所以每次 `select` 完都要重新建立要監控的 `fd` 清單。
Sign in with Wallet
Connect another wallet