# 2025q1 Homework4 (quiz3+4)
contributed by < `wurrrrrrrrrr` >
## 測驗 1
### 程式碼運作原理
首先看到 `ceil_div` 是無條件進位除法：
```c
static size_t ceil_div(size_t n, size_t d)
{
return AAAA;
}
```
他的作用為計算 n 除以 d，其中 n 可以表示為 `q × d + r`，其中 r 是餘數，範圍為 0 到 d-1。若 `r == 0`，表示整除，則結果為 q；若 `r > 0`，則需向上取整，結果為 `q + 1`，為了達成這個向上取整的效果，關鍵是觀察當 n 沒有整除時，餘數 r 的範圍會落在 1 到 d - 1。因此，而如果餘數為 1 時想進位 n 就要加 d-1 ，而如果餘數為 `d - 1` 時想進位 n 只要加 1，為了涵蓋所有可能的餘數，我們選擇固定補上 d - 1，也就是使用公式 `(n + d - 1) / d`。`d - 1` 這個數值雖然在某些情況下可能超過進位所需要的，但它不會導致進位超過一位，而且又能保證所有餘數大於 0 的情況下都能正確進位。
`AAAA` = `(n+d-1)/d`
第二個 ` mpi_set_u64()` 這個函式的作用是把 `uint64_t` 拆解成多個 `31` bit 並儲存在 `mpi_t` 結構中。一開始計算要幾個 `31` bit來表示 `64` bit 的數值，而第二段是確保 rop 有足夠空間來放這些 `31` bit，如果記憶體不夠，會擴展它，再來執行了一段迴圈把 `64` bit 的整數 op 拆成 `31` bit 的小塊儲存到 rop->data[] 中，從低位到高位依序填入，而要如何拿出 31 bit？此時就需要一個 mask 只取後 31 位，因此 `INTMAX = 0x7fffffff`。
若記憶體不夠，會分配或擴展。
```c
#define INTMAX BBBB
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;
}
```
`BBBB` = `0x7fffffff`
mpi_mul_naive 函式的作用是計算兩個 op1 × op2 的乘積，並將結果儲存到 rop 中。
```c
static void mpi_mul_naive(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
...
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;
}
}
}
...
}
```
其中的這段模仿我們手動筆算乘法的方式：
1. 對每一位做乘法
1. 加總
1. 處理進位
而其中 `op1[n] × op2[m]` 的結果會放在第 `n + m` 位開始，就像十進位乘法的位移，因此 `CCCC` = `n + m`
`mpi_fdiv_qr` 的作用是執行整數的整除與餘數運算，也就是計算 `q = n / d` 和 `r = n % d`，並將結果分別儲存在 q 和 r 中:
```c
void mpi_fdiv_qr(mpi_t q, mpi_t r, const mpi_t n, const mpi_t d)
{
...
size_t start = mpi_sizeinbase(n0, 2) - 1;
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);
}
}
...
}
```
例子：當 n 為 1101 時
一開始：
* 商 q = 0
* 餘數 r = 0
n 是 1101 ，最高位是第 3 位
每個步驟：
* 第 1 步：i = 3
* r <<= 1 ➔ r = 0
* 把 n 第 3 位(1)加進 r ➔ r = 1
* 比較 r = 1 跟 d = 3 ➔ 1 < 3，所以不用減。
* 商 q 第 3 位寫0。
第 2 步：i = 2
* r <<= 1 ➔ r = 2
* 把 n 第 2 位(1)加進 r ➔ r = 3
* 比較 r = 3 跟 d = 3 ➔ 3 == 3，可以減
* 減完 r = 0
* 商 q 第 2 位寫 1。
第3步：i=1
* r <<= 1 ➔ r = 0
* 把 n 第 1 位(0)加進 r ➔ r還是0
* 比較 r = 0 跟 d = 3 ➔ 0 < 3，不用減。
* 商 q 第 1 位寫 0。
第4步：i = 0
* r <<= 1 ➔ r = 0
* 把 n 第 0 位(1)加進 r ➔ r = 1
* 比較 r = 1 跟 d = 3 ➔ 1 < 3，不用減。
* 商 q 第 0 位寫 0。
最後結果：
* 商 q = 0100 (十進位就是4)
* 餘數 r = 1
* 所以 13 ÷ 3 = 4 餘 1
mpi_mul_2exp(r, r, DDDD)這行的作用是將餘數 r 左移 1 位，因此`DDDD` = `1`。
mpi_gcd 這個函式實作的是輾轉相除法來計算兩個整數 op1 和 op2 的最大公因數。依照輾轉相除法的原理：
若 b ≠ 0，則 GCD(a, b) = GCD(b, a mod b)
所以，在遞迴的情況下，只要 op2 不為 0，就持續以 op1 % op2 的餘數作為新的下一輪的參數，直到餘數等於 0 為止。
`EEEE` = `mpi_gcd(rop, op2, r)`
### 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
下列這段程式為 mpi_gcd 的非遞迴實作版本：
```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);
}
```
:::success
延伸問題:
解釋上述程式碼運作原理
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
改進最大公因數的運算效率
:::
## 測驗 2
### 解釋上述程式碼運作原理
```c
static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
```
在測驗 2 中可以發現，這個函式中的` ((y + 0L) & (-1L >> 32)) `是多餘的。
原因是，我傳入的 y 是` uint32_t `類型（無號整數），
在進行 (y + 0L) 時，C 語言會將 y 進行無號升型（promotion），
轉換成 long 型別，並且高位自動補 0，不會產生符號擴展或高位污染的問題。
為了確認這段我做了測試：
```c
int32_t si = -1;
uint32_t ui = 0xFFFFFFFF;
long sl = si + 0L;
long ul = ui + 0L;
printf："Signed int32_t si = %d\n", si);
printf("After (si + 0L): 0x%016lx\n", (unsigned long)sl);
printf("\n");
printf("Unsigned int32_t ui = %u\n", ui);
printf("After (ui + 0L): 0x%016lx\n", (unsigned long)ul);
```
而印出來的結果為
```
Signed int32_t si = -1
After (si + 0L): 0xffffffffffffffff
Unsigned int32_t ui = 4294967295
After (ui + 0L): 0x00000000ffffffff
```
後面的 & (-1L >> 32) 遮罩操作實際上並沒有任何作用，可以直接省略。
另外，如果真的需要截取後32位元，為了保證正確性與跨平台行為，
應該明確使用 unsigned long 型別進行操作，例如遮罩 0xFFFFFFFFUL，
而不是使用 (-1L >> 32) 這種有號數右移行為的寫法。
為了驗證上述這段我做了以下測試：
```c
unsigned long ul = (unsigned long)-1L;
printf("Test shifting -1L (signed long)\n");
printf("-1L >> 32 = 0x%016lx\n", (-1L >> 32));
printf("\nTest shifting (unsigned long)-1L\n");
printf("(unsigned long)-1L >> 32 = 0x%016lx\n", ul >> 32);
return 0;
```
此為輸出結果：
```
Test shifting -1L (signed long)
-1L >> 32 = 0xffffffffffffffff
Test shifting (unsigned long)-1L
(unsigned long)-1L >> 32 = 0x00000000ffffffff
```
而 memchr_opt 分為三個階段，其中要填入的為第二段
第一段：逐字元搜尋 c 直到記憶體位置對齊
第二段：快速以 long 單位搜尋是否包含目標字元 c
第三段：逐字元搜尋剩餘字元是否包含目標字元 c
首先看到這段：
```
#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)
```
從題目的敘述可以知道 DETECT_NULL(X) 會檢查 X 中是否有 byte 是 0x00。
我們想判斷某個 long 變數是否包含特定字元 c，做法是：
將該 long 變數 X 與一個由目標字元重複填滿的 mask 做 XOR，若 X 中有任何 byte 等於目標字元，則 XOR 結果對應 byte 就會是 0，等同 DETECT_NULL 可檢測到，因此 `AAAA = X^mask`
由上述可得知，mask 是由目標字元 d 重複填滿，而下列這段是想產生一個 unsigned long mask，裡面所有的 byte 都填滿字元 d。
初始時先用 16 bits 來填滿（d << 8 | d），接著利用位移與 OR 操作將其擴展到 32 bits。
如果 unsigned long 是 64 位元，會執行下面的迴圈，持續將目前的 mask 左移並 OR 到自己，直到整個 64-bit mask 都被填滿：
```c
unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask |= BBBB;
```
因此可以得知 `BBBB = mask<<i` 而 CCCC 則是指向資料區塊的 unsigned long 變數，因此 `CCCC = *asrc`，用來進行目標字元的檢測
:::success
延伸問題:
解釋上述程式碼運作原理
比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
研讀 2022 年學生報告，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
下一步：貢獻程式碼到 Linux 核心
Phoronix 報導
:::
## 測驗 3
AAAA = ENV_RUNNABLE
BBBB = attempts+1
CCCC = coro_schedule
DDDD = coro_yield
## 測驗 1
```c
uint32_t crc32_u8(uint32_t crc, uint8_t v)
{
crc ^= v;
static const uint32_t crc32_table[] = {
0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1,
0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d,
0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9,
AAAA, BBBB, CCCC, DDDD,
};
crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
return crc;
}
```
```
給一個 0到 15 的初始值
↓
做 4 次 CRC 模擬（每次根據最低 bit 決定要不要 XOR）
↓
得到最終 CRC 表格值
↓
填到你的查表陣列
```
用 0xC 當例子
初始： crc = 0x0000000C //(binary 1100)
0x0000000C 這樣的初始值，**其高位元可以假設為 0**，原因是後續的運算中，每次都會進行 crc >> 4 的位移操作，把高位資料不斷移除掉，因此原本高位的內容不會影響最終的結果。
**第一次位移 (bit 0)**
* crc & 1 == 0（最低位是0）
只右移 >>
crc = 0x00000006
**第二次位移 (bit 1)**
* crc & 1 == 0
再右移 >>
* crc = 0x00000003
**第三次位移 (bit 2)**
* crc & 1 == 1
先右移，再 XOR 0x82F63B78
crc = 0x82F63B79
**第四次位移 (bit 3)**
crc & 1 == 1
再次先右移再 XOR 0x82F63B78：
**crc = 0xC38D26C4**
以此類推
`AAAA`：`0xc38d26c4`
`BBBB`：`0xd3d3e1ab`
`CCCC`：`0xe330a81a`
`DDDD`：`0xf36e6f75`
:::success
延伸問題:
在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令
:::
## 測驗 2
`AAAA`：0x7FFF
`BBBB`：0x80000000
`CCCC`：0x7FFFFFFF
`DDDD`：0x80000000
`EEEE`：0x7FFFFFFF
`FFFF`：input & 0xFF
`GGGG`：Q15_MAX
`HHHH`：Q15_MIN
:::success
延伸問題:
解釋上述程式碼運作原理，搭配「信號與系統」教材
探討定點數的使用和其精確度
改進 MIDI 一閃一閃亮晶晶的音效輸出
:::
## 測驗 3
`IIII`： max_fd
`JJJJ`： &rfds
這支 server 程式是一個多人聊天室伺服器，支援同時多個 client 連線進來聊天，每當有一個 client 發訊息給 server，server 會自動把這個訊息轉發給其他所有連線中的 client，而且如果有 client 離開，server 也會自動偵測並清除連線。
執行這支程式，server 在本機的你輸入的 port 上開始監聽，等待 client 連進來。
**client 可以用像是 telnet 或 netcat 來連線到 server** ，例如:
```
telnet 127.0.0.1 5000
```
**每成功一個連線，server 端會：**
1. 執行 accept() 接受這個新連線
1. 打印出來一行訊息，顯示 new_fd 和 client 的 IP/port
1. 把這個新 client 的 fd 記錄到 conns[] 陣列中（活躍的 client 列表）
1. 把這個 fd 加到 select() 監控的集合裡（下一輪重建 fd_set 時加進去）
1. 把這個 socket 設成 non-blocking 模式（避免 read() 卡住）
```
listening on port 5000
[4] connect from 127.0.0.1:59490
```
**client 發送可以訊息給 server**
client 任意打字，例如： Hello everyone!
server 端在下一輪 select() 中偵測到這個 client fd 有資料可以讀。
```
listening on port 5000
[4] connect from 127.0.0.1:59490
[4] activity
[4] read: Hello everyone!
```
**server 處理收到的訊息**
當 server 偵測到某個 client 有資料：
呼叫 read(fd, buf, sizeof(buf)) 讀取資料。
如果 read() 回傳 > 0，代表真的有資料收到。
接著 server 會：
1. 把剛收到的這段文字存在 buf 中。
1. 迴圈遍歷所有活著的 client_fd。
1. 把這份資料（buf）寫給除了自己以外的所有 client (dest_fd != fd)。
1. 用 write(dest_fd, buf, nread) 把訊息廣播出去。
**client 斷線時的處理**
如果某個 client：
自己正常關閉連線或是網路問題中斷 server 端在 read(fd, buf, sizeof(buf)) 時會遇到： read() 回傳 0
這時 server：
1. 印出 [fd] closed
1. close(fd) 把這個 client 的連線關掉
1. conns[fd] = 0 從活躍連線列表清掉
```
[4] activity
[4] closed
```
:::success
延伸問題:
解釋上述程式碼運作原理
學習 jserv/ttt 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 ping value 的處理機制
:::
Sign in with Wallet
Connect another wallet