# 2025q1 Homework4 (quiz3+4)
contributed by < `BrotherHong` >
## [第 3 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)
### 測驗 1
#### 參考答案
* AAAA = `(n+d-1)/d`
* BBBB = `0x7fffffff`
* CCCC = `n+m`
* DDDD = `1`
* EEEE = `mpi_gcd(rop,op2,r)`
#### 思路
==/* AAAA */==
題目要求不用到浮點數運算達到「整數除法並向上取整」的功能。
最直接的想法就是判斷餘數來決定是否要將結果 +1
```c
return (n / d) + (n % d != 0);
```
但還可以再更精簡
假設我們要對 n / d 向上取整，我們可以先觀察 n / d 的結果會長怎樣
```
n: | 0 1 ... d-1 | d d+1 ... 2d-1 | ... | qd qd+1 ... n-1 n |
q: | 0 | 1 | ... | q |
```
我們期望他的結果應該長這樣
```
n: | 0 | 1 2 ... d | d+1 d+2 ... 2d | ... | qd+1 qd+2 ... n-1 n |
q: | 0 | 1 | 2 | ... | q+1 |
```
觀察兩者的差異可以發現，下方的結果會是將上方的 n 向右移 d-1 個的結果，因此可以得到 (n+d-1) / d 這個結果。
```c
return (n+d-1)/d;
```
==/* BBBB */==
從定義的名字可推測這邊是要放 int 的最大值
```c
#define INTMAX BBBB
```
再根據底下的部份程式碼
* `mpi_set_u64` 片段
```c
for (size_t n = 0; n < capacity; ++n) {
rop->data[n] = op & INTMAX;
op >>= 31;
}
```
這個函式的操作是要將一個 64-bit 的 unsigned integer 方入 mpi 裡面，並且從這個 for 迴圈可以從 `op >>= 31` 推斷他是每 31 個 bits 放入 mpi 的一格 data，而 INTMAX 在這裡的作用就相當於一個 mask 用來取最低 31 bits，因此 BBBB = `0x7fffffff`
==/* CCCC */==
* `mpi_mul_naive` 片段
```c
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;
}
```
此部份程式碼被包在 `n = 0 ~ op1->capacity-1` 和 `m = 0 ~ op2->capacity-1` 的巢狀迴圈中，從名字可以知道這個函式是在做 mpi 乘法，並且使用最直接的方法。
由此資訊配上上方程式碼片段可以知道它是使用我們平常算乘法用的直式乘法來實做，其中 r 就是我們兩數乘完的結果，c 是上個運算的進位 (carry)，用 `(r & INTMAX) + c` 把結果 fit 到一個單位能表達的範圍。
最後會將當前運算結果放在第 k 個位置，從直式乘法的角度去想：第 0 個數和第 2 個數相乘結果要放在 0+2=2 的位置；或是從根本的運算方法去想：在第 0 個位置的數 (x) 代表 `x << (31*0)`，第 2 個位置的數 (y) 代表 `y << (31*2)`，因此的兩個數相乘的結果應該要放在 `1 << (32*(0+2))` 的位置，用一般式來表達可以說：第 n 個數和第 m 個數的結果就要被放在 k=n+m 的地方，因此 CCCC = `n+m`。
==/* DDDD */==
* `mpi_fdiv_qr` 片段
```c
for (size_t i = start; i != (size_t) -1; --i) {
mpi_mul_2exp(r, r, DDDD);
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);
}
}
```
從函式名字加上一些變數宣告可以推斷這邊是在做整數除法並且會計算他的商 `q` 和餘數 `r`。
假設我們將陣列的 0~len-1 元素由右往左看，也就是比較高位的放在左邊，這個 for 迴圈會由高位往低位依照順序做以下這些事：
* `r = r * 2^(DDDD)`
* 若 n0 的第 i 個 bit 為 1
* `r = r | 1`： 設 r 的第 0 bit 為 1
* 若 `r >= d0`
* `r = r - d0`
* `q = q | (1 << i)`： 設 q 的第 i bit 為 1
其中 n0 和 d0 分別是被除數和除數
我們可以發現這邊在做的事情有點像我們平常在算直式除法的樣子：由高往低做、當餘數大於除數時把餘數減掉除數並把商加一、...，只不過是以二進位的方式來做。
因此每進一位，餘數也就要從最低位新增一個 bit，DDDD 那邊的操作就是再做這件事的前置作業，因此 DDDD = `1`。
==/* EEEE */==
這部份是位在 `mpi_gcd` 裡面，這個函式是用來計算兩數的最大公因數，常見的算法就是用輾轉相除法：
**遞迴版**
```c
int gcd(int a, int b)
{
if (b == 0)
return a;
int r = a % b;
return gcd(b, r);
}
```
**迴圈版**
```c
int gcd(int a, int b)
{
int r;
while (b) {
r = a % b;
a = b;
b = r;
}
return a;
}
```
在填入部份可以看到做完除法後只有一行，因此可推斷他是使用遞迴的方式，參數的部份 `op1` 會傳入 `op2` ，而 `op2` 會傳入餘數 `r`，因此 EEEE = `mpi_gcd(rop,op2,r)`。
### 測驗 2
#### 參考答案
* AAAA = `X^mask`
* BBBB = `mask<<i`
* CCCC = `*asrc`
#### 思路
```c
/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)
```
* `memchr_opt` 片段
```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 |= BBBB;
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(CCCC, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
```
==/* AAAA */==
`DETECT_NULL` 會去判斷一個 `long` 中的每一個 byte 是否存在 NULL (0x00)，若有找到它的結果為非 0，沒找到則為 0。
這邊的 `DETECT_CHAR` 目的是要在 `(long) X` 中尋找是否存在目標的字元，不過它被定義成一個 `DETECT_NULL` 的形式，傳入的參數只有 `X` 和 `mask`，由此可知，`mask` 是用來把 `X` 中我們要找的目標字元變為 0，這樣就能在 `DETECT_NULL` 被找到。
在 `memchr_opt` 片段可以看到 `mask` 的值的每個 byte 都是我們要找的目標字元，所以我們要找到一個操作讓 `X` 和 `mask` 相同的 byte 變為 0，而這個相等位元變為 0 的操作就只有 exclusive or 可以達成，因此 AAAA = `X^mask`。
==/* BBBB */==
從填入部份的上方幾行可以知道，這個迴圈是在讓 `mask` 的每個 byte 都設為目標字元 d ，因此 BBBB = `mask<<i`。
```
char d -> 1 byte // assume d = 0x12
long mask -> 64 byte // assume long is 32 bytes
mask = d << 8 | d; // mask = 0x0000000000001212
mask = mask << 16 | mask; // mask = 0x0000000012121212
mask = mask << 32 | mask; // mask = 0x1212121212121212
```
==/* CCCC */==
從整體程式碼觀察，可以知道 `(unsigned long *) asrc` 是當作一個用來讀取輸入 `src` 的一個指標，每次讀取一個 `long` 的長度，然後再放進 `DETECT_CHAR` 尋找是否存在目標字元，`asrc` 是一個指標，所以在傳入 `DETECT_CHAR` 時要對它取值，所以 CCCC = `*asrc`。
### 測驗 3
#### 參考答案
* AAAA = `ENV_RUNNABLE`
* BBBB = `attempts+1`
* CCCC = `coro_schedule`
* DDDD = `coro_yield`
#### 思路
==/* AAAA */==
由 header file `coro.h` 對 `coro_create` 的定義註解可以知道，剛新增的 thread 的 status 會設定為 runnable，因此 AAAA = `ENV_RUNNABLE`。
```ㄏ
/* Create a new user-level thread that is marked as runnable.
* The thread's entry point is @entry with the given @args.
* The thread will not start executing until the next call to coro_yield().
* Returns a unique thread identifier on success, or -1 on failure.
*/
int coro_create(coro_entry entry, void *args);
```
==/* BBBB */==
從測驗題目的說明可以知道這邊 scheduler 的排程策略適用 round-robin，所以要找下一個可以執行的 thread 就是從目前的位置往後找，其中 `attempts` 變數從名稱可以推測他是用來紀錄我目前嘗試到後面第幾位，類似 offset 的功能，`attempts` 初始值為 0，一開始要是從下一個 thread 開始嘗試，因此 BBBB = `attempts+1`。
```c
int candidate = (curenv + BBBB) % NENV;
```
==/* CCCC */==
從 header file 註解，可以知道這個函式是要讓出目前的執行給其他 thread 用，讓出的方式就是讓 scheduler 選擇下一個要執行的 thread，因此呼叫 `coro_scheduler`。
```c
/* Yield execution to the next available user-level thread.
* The scheduler may choose to run a different thread or resume the current one.
*/
void coro_yield(void);
```
==/* DDDD */==
從函式的名字 preempt 可以知道目前執行的 thread 要被動地讓出 CPU (被搶佔) ，所以呼叫 `coro_yield` 讓出 CPU 的使用權給其他 thread 。
## [第 4 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz4)
### 測驗 1
### 測驗 2
### 測驗 3
Sign in with Wallet
Connect another wallet