2025q1 Homework4 (quiz3+4)

contributed by <Andrushika>

w3q1

本題使用 mpi_t 結構，作為包裝大數的基礎資料結構，結構定義如下：

/* 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，在不使用上述技巧的情況下，會需要做以下操作進行初始化：

mpi_t *number = malloc(sizeof(mpi_t));
mpi_init(number);

但使用上述技巧後，mpi_t 被定義為給定 struct 的陣列，所以記憶體空間已經分配好。使用 mpi_t 的方式就可以簡化：

mpi_t number;
mpi_init(number);

可以發現 number 就像 OOP 中包裝好的 object 一樣，mpi_t 就像某個 class。

AAAA

觀察 ceil_div，基本的除法向上取整操作：

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 觀察出來：

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 的答案：

#define INTMAX 0x7fffffff // BBBB

CCCC

mpi_mul_naive 使用類似直式乘法的概念來實作，每次相乘一位後持續往高位數進位。

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 的答案：

mpi_mul_2exp(r, r, 1); // DDDD

EEEE

mpi_gcd 使用遞迴版本的輾轉相除法求最大公因數。每次求得 op1 % op2 的結果後，再用該結果進行下次的運算，因此可以填入 EEEE：

mpi_gcd(rop, op2, r); // EEEE

將 mpi_gcd 的實作方式改為 iterative

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：

#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 的定義：

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 判斷出來。

#define DETECT_CHAR(X, mask) DETECT_NULL(X ^ mask)

UNALIGNED 時的處理

若記憶體位置沒有和 sizeof(long) 對齊，則先一個一個字元讀取，並確定是否為目標字元，直到對齊為止。

while (UNALIGNED(src)) {
    if (!len--)
        return NULL;
    if (*src == d)
        return (void *) src;
    src++;
}

BBBB, CCCC

當記憶體 ALIGNED 之後，就可以用題目所提及之 SWAR 方法快速求解。
首先需要將要尋找的目標 d 做成用來一次偵測多個 byte 的 mask，然後再使用 DETECT_CHAR 進行偵測：

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 並進入等待被排程的狀態，所以可以填入：

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 相關函式執行入口點及參數：

makecontext(&envs[env].state, (void (*)(void)) entry, 1, args);

其中 entry 是在 coro_create 中傳入的函式指標。

BBBB

根據題目敘述，排程採用 round-robin 策略，所以每次會找下一個 index 的 candidates，即：

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，一開始計算的迴圈部分如下：

for (unsigned int j = 0; j < 8; j++)
  if (crc & 1)
    crc = (crc >> 1) ^ Polynomial;
  else
    crc =  crc >> 1;

可以加速為 branch free 版本：

for (unsigned int j = 0; j < 8; j++)
  crc = (crc >> 1) ^ (crc & 1) * Polynomial;

然後再額外提升效能，由於 (crc & 1) 的結果始終只有 0 或 1，可以再簡化成以下版本：

for (unsigned int j = 0; j < 8; j++)
  crc = (crc >> 1) ^ (-(int)(crc & 1) & Polynomial);

作答

根據 Fast CRC32 所提及的 "Half-Byte Algorithm"，可以用來產生剩餘的答案：

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);
}

`AAAA` = `0xC38D26C4` `BBBB` = `0xD3D3E1AB` `CCCC` = `0xE330A81A` `DDDD` = `0xF36E6F75`

不要列出參考題解，專注題目本身

w4q2

Phase Increment

因為程式是使用離散取樣模擬 phase，要產生特定波的時候，可以想像成每次取樣都推進一點 phase。假設每秒取樣

$f_s$ 次，而我們想產生

$f_0$ Hz 的音的時候，可以透過下列算式計算每次 sample 時 phase 該增加多少：

$$\mathrm{\Delta }\theta =\frac{f_0}{f_s}\cdot 2\pi$$

題目中使用 Q15 去表示 phase (

$0\sim 2\pi$)：

$$phase\mathrm{\_}incr=\frac{f_0}{f_s}\cdot Q15\mathrm{\_}MAX$$

對應的實作 code:

#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，所以使用模除運算處理。

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 值的方式：

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 應填入：

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：

res += ((next - res) * (input & 0xFF) >> 8);

以上運算，可以想像是對 res 和 next 中間先計算「距離 table 的下一個點，目前走了多少百分比？」，然後用這個百分比來插值。

GGGG, HHHH

square_wave 也是輸入 phase，輸出對應的波。
需要在前半個週期輸出 +1, 後半個週期輸出 -1，因此修改如下：

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:

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。

關於 select 運作的疑惑：
在我的理解中，select 應該是在偵測到任何一個 file descriptor ready 時，就會馬上 return。在微觀的角度下，kernel 應該無法「同時」偵測到多個 file descriptor ready，而在偵測到任一 fds ready 就要馬上 return 的狀況下，為何會出現 rfds 中可以找到多個 FD_ISSET 的狀況？

關於 select 運作問題：ChatGPT 的回答

do_select() 的工作流程

以下是 do_select() 函數的簡化流程：

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