# 2025q1 Homework4 (quiz3+4)
contributed by: <``Beethovenjoker``> (章元豪) [Github](https://github.com/Beethovenjoker/lab0-c)
## 2025q1 第 3 週測驗題
### 測驗 `1`
```c
/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
return (n+d-1)/d;
}
```
取上界的除法，可以將情況歸納成:
- 有餘數 (1~d-1)。
- 當 n 除以 d 有餘數時，餘數的範圍是 1 到 d - 1，這時候我們希望商要進位，也就是要加一。
- 沒有餘數 (0)。
- 而當沒有餘數時，餘數為 0，商本來就是正確的，不需要改變。
為了讓這兩種情況可以統一處理，我們可以在除法之前先對被除數加上 d - 1。這樣做的好處是如果原本沒有餘數，像是 n = 93、d = 31，加上 d - 1 = 30 之後變成 123，除以 31 仍然是 3，不會改變原本的商。但如果原本有餘數，像是 n = 94、d = 31，加上 30 變成 124，這時候除以 31 就會從 3 變成 4，達到進位的效果。
```c
#define INTMAX 0x7fffffff
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;
}
```
這個函數是將一個 64 位元的無號整數轉換成多精度整數 mpi_t。由於 mpi_t 中的 data 陣列每個元素只使用 31 個位元儲存有效資料，因此會先用 `ceil_div(64, 31)` 計算將 64 位元整數分割成幾個 31 位元區段所需的容量，這裡會得到 3，表示最多需要 3 個 31 位元的欄位。
接著使用 `& 0x7fffffff` 取出最低的 31 位元並存入 `rop->data[n]`，再將 op 向右位移 31 位元，準備處理下一段資料。這樣每次迴圈就會處理一個 31 位元區段，直到整個 64 位元數字被分解完。若 `rop->capacity` 比實際需要的容量更大，就將剩下未使用的欄位填為 0，確保沒有殘留舊資料。
```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 = m+n; 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;
}
}
}
```
類似直式乘法的運算，被乘數第 n 位與乘數第 m 位相乘時，其結果從第 n + m 位開始儲存。
```c
for (size_t i = start; i != (size_t) -1; --i) {
mpi_mul_2exp(r, r, 1);
if (mpi_testbit(n0, i) != 0)
mpi_setbit(r, 0);
if (mpi_cmp(r, d0) >= 0) {
mpi_sub(r, r, d0);
mpi_setbit(q, i);
}
}
```
也是類似直式除法，從被除數的最高位元開始逐位處理。每次迴圈會先將目前的餘數乘以 2，也就是左移一位元。接著從被除數中取出當前位元補到餘數的最低位，再判斷是否能夠減去除數，若可以就執行減法並在商中對應的位置設為 1，否則進入下一輪處理。
```c
void mpi_gcd(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;
mpi_init(q);
mpi_init(r);
mpi_fdiv_qr(q, r, op1, op2);
mpi_gcd(rop,op2,r);
mpi_clear(q);
mpi_clear(r);
}
```
輾轉相除法，把餘數和 op2 代入 `mpi_gcd()`。
### 測驗 `2`
```c
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
```
這個巨集透過 SWAR 技巧，如果 X 中包含 NULL byte（0x00）時回傳 `非 0`。
```c
#define DETECT_CHAR(X, mask) DETECT_NULL(X^mask)
```
這個巨集的用途是快速判斷 X 中是否出現過指定字元。它會先將 X 中的每個 byte 與 mask 進行 XOR 運算，若其中有 byte 和目標字元相同，該位元組會變為 0x00，接著透過 `DETECT_NULL` 偵測是否存在 NULL byte，以此達成匹配檢查。
```c
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= mask<<i;
```
```c
mask = 0xdddddddddddddddd
```
這段使用了典型的 SWAR 技巧，用來把單一字元 d 複製到整個 32 位或 64 位元的 mask 裡，每個 byte 都會變成 d。
```c
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
```
在字串長度足夠，且指標已對齊至 long 邊界的情況下，這段程式會使用 SWAR 技巧，一次處理一個 word（也就是一個 block）大小的資料，加速搜尋目標字元。此時 asrc 是指向當前區塊的指標，而 *asrc 才是實際要拿來比對的資料內容，因此傳入 DETECT_CHAR 的應該是 *asrc，用來檢查該區塊中是否包含目標字元。
```c
while (len--) {
if (*src == d)
return (void *) src;
src++;
}
```
這段是標準的fallback 搜尋階段，當 SWAR 無法處理的資料（例如剩下不足一整個 word 的尾端）或在未對齊的初始區段中，就使用這段程式碼逐 byte 比對目標字元，直到找到或資料結束為止。
### 測驗 `3`
```c
int coro_create(coro_entry entry, void *args)
{
/* Search for an available environment slot */
int env;
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;
/* Initialize the context for the new user-level thread */
getcontext(&envs[env].state);
make_stack(&envs[env].state);
envs[env].state.uc_link = &exiter;
makecontext(&envs[env].state, (void (*)(void)) entry, 1, args);
/* Return the identifier of the newly created user-level thread */
return env;
}
```
建立一個新的使用者層級執行緒（user-level thread / coroutine），設定其執行狀態與context，並回傳其 ID（index）。
```c
int env;
for (env = 0; env < NENV; env++) {
if (envs[env].status == ENV_UNUSED)
break;
}
if (env == NENV)
return -1;
```
這段會從 envs[] 陣列中尋找一個狀態為 `ENV_UNUSED` 的空槽，如果全部都在使用中，就回傳 -1 代表失敗。
```c
envs[env].status = ENV_RUNNABLE;
```
找到空槽後，把這個槽位標記為 `RUNNABLE`，表示這個 coroutine 可以被排程執行。
```c
static void coro_schedule(void)
{
int attempts = 0;
while (attempts < NENV) {
int candidate = (curenv + attempts + 1) % NENV;
if (envs[candidate].status == ENV_RUNNABLE) {
curenv = candidate;
/* Request delivery of TIMERSIG after 10 ms */
timer_settime(timer, 0, &ts, NULL);
setcontext(&envs[curenv].state);
}
attempts++;
}
exit(0);
}
```
這段程式碼是 coroutine scheduler 的實作，負責選出下一個應該執行的 task（user-level thread，即 coroutine），並將執行控制權轉移給它。排程策略採用round-robin 方法，從目前執行中的 curenv 的下一個位置開始，依序搜尋狀態為 `ENV_RUNNABLE` 的 coroutine。一旦找到，就設定定時器並切換至該 coroutine 執行 context；若沒有任何 coroutine 可執行，則結束程式。
```c
int candidate = (curenv + attempts + 1) % NENV;
```
`+1` 是為了讓排程從目前 coroutine 的「下一個」位置開始尋找 `ENV_RUNNABLE` 的 coroutine，避免排程器重新選到當前正在執行的 coroutine 本身，這樣才能實現真正的 round-robin排程效果。
```c
void coro_yield(void)
{
envs[curenv].state_reentered = 0;
getcontext(&envs[curenv].state);
if (envs[curenv].state_reentered++ == 0) {
/* Context successfully saved; schedule the next user-level thread to
* run.
*/
coro_schedule();
}
/* Upon re-entry, simply resume execution */
}
```
這段程式碼的功能是讓目前正在執行的 coroutine 主動讓出 CPU，暫停自己，並交由排程器選擇下一個 coroutine 來執行。
```c
static void preempt(int signum UNUSED,
siginfo_t *si UNUSED,
void *context UNUSED)
{
coro_yield();
}
```
這段程式碼是 coroutine 系統中用來模擬 preemption 的 signal handler。當定時器送出 signal（例如 SIGRTMIN）時，系統就會進入 preempt() 函數。其目的在於中斷目前正在執行的 coroutine，並觸發排程器進行 coroutine 切換。因此，應呼叫的是主動讓出控制權的函式 `coro_yield()`。
## 2025q1 第 4 週測驗題
### 測驗 `1`
## Reference
- [2025q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)
- [2025q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz4)
Sign in with Wallet
Connect another wallet