# 2025q1 Homework4 (quiz3+4)
contributed by < `tsaiiuo` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## Q3
### 測驗 1
#### 解釋上述程式碼運作原理
先研讀程式碼，回答答案。
`ceil_div` ： 可以透過 $\lceil \frac{n}{d} \rceil = \lfloor \frac{n+d-1}{d} \rfloor$ 的概念實作，因此`AAAA`：`(n + d - 1) / d`
`INTMAX` ： 這就比較直觀 `BBBB`：`0x7fffffff`
`mpi_mul_naive` ： 實現天真乘法（透過兩數逐位相乘，並累加各項乘積，同時處理進位。），第 `n` 位和第二個 `mpi_t` 的第 `m` 位而言，他們乘起來的數字要加到第 `n + m` 位，因此 `CCCC`：`n + m`
`mpi_fdiv_qr` ： 實現長除法，這邊須將餘數左移一位（跟實際的長除法一樣），因此 `DDDD`：`1`
`mpi_gcd`：用 `mpi_fdiv_qr` 做輾轉相除法用於計算計算兩個整數的最大公因數根據公式可以得知答案
例子：
gcd(46189,2310)
= gcd(2310, 46189 mod 2310)
= gcd(2310,2299) （因 46189 ÷ 2310 = 19，餘數 46189 – 19×2310 = 2299）
= gcd(2299,2310 mod 2299)
= gcd(2299,11) （2310 ÷ 2299 = 1，餘數 2310 – 1×2299 = 11）
= gcd(11,2299 mod 11)
= gcd(11,0) （2299 ÷ 11 = 209，餘數 2299 – 209×11 = 0）
= 11
因此`EEEE`：`mpi_gcd(rop, op2, r)`
#### 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
```cpp
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);
/* 當 b 不為 0 時，持續進行除法以取餘數 */
while (mpi_cmp_u32(b, 0) != 0) {
/* 計算 a / b，獲得餘數 r */
mpi_fdiv_qr(q, r, a, b);
/* 將 a, b 更新：令 a = b, b = r */
mpi_set(a, b);
mpi_set(b, r);
}
mpi_set(rop, a);
mpi_clear(a);
mpi_clear(b);
mpi_clear(q);
mpi_clear(r);
}
```
因為 `op1` 和 `op2` 皆為不可變更的，因此需要多定義 `a` 和 `b` 代替 `op1` 和 `op2` 去進行運算。
### 測驗 2
#### 解釋上述程式碼運作原理
先研讀程式碼，回答問題
```clike
#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)
```
用 X 與 mask 做 XOR 運算，產生一個新值，這樣在各個 byte 中若有 byte 等於 d（即 mask 中對應的 byte），則 XOR 後該 byte 會變為 0，再交由 DETECT_NULL 檢查是否存在 0 byte，因此 `AAAA` ： `(X) ^ (mask)`
```cpp
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;
```
這段程式碼目的是建立一個 word（unsigned long）大小的 mask，其中每個 byte 都填滿了目標字元 d 的值。這個 mask 之後會用來在一次讀入多個 byte 時，用意是透過 XOR 與位元運算來檢測該 word 中是否含有目標字元（d）。
而上面程式碼如何製作 mask 我用以下一個範例去 trace code 看看：
這邊假設 d = 'w' ， 即 0x77，且 LBLOCKSIZE = 8（64位元的系統）
初始計算：
d = 0x77
d<<8 = 0x7700
mask = 0x7700 | 0x77 = 0x7777
擴展到 32 位元：
mask<<16 = 0x7777 << 16 = 0x77770000
mask |= mask<<16 → 0x7777 | 0x77770000 = 0x77777777
擴展到 64 位元：
進入迴圈，初始 i = 32，
mask<<32（i） = 0x77777777 << 32 = 0x7777777700000000
mask |= mask<<32 → 0x77777777 | 0x7777777700000000 = 0x77777777_77777777
然後 i <<= 1 變成 64，迴圈結束。
因此 `BBBB` ： `mask << i`
```cpp
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(CCCC, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
```
這段程式碼就是以 word 為單位配合 `DETECT_CHAR` 檢查是否有符合的目標字元若有則中止，反之則檢查下一個 word（這邊的 ++ 會加上 sizeof(unsigned long) 也就是一個 word 的大小），因此 `CCCC` 應該為 `*asrc` (上面有一段 `unsigned long *asrc = (unsigned long *) src;` )
### userspace context 測試
此段用意在理解 `getcontext` ， `makecontext`，`setcontext`
```cpp
getcontext(&ctx_main);
```
可以取得目前程式的上下文並且存入參數的指標中
```cpp=
// 取得一個可修改的 context，再設定其執行函式為 func()
if (getcontext(&ctx_func) == -1) {
perror("getcontext");
exit(1);
}
ctx_func.uc_stack.ss_sp = malloc(8192);
if (ctx_func.uc_stack.ss_sp == NULL) {
perror("malloc");
exit(1);
}
ctx_func.uc_stack.ss_size = 8192;
ctx_func.uc_stack.ss_flags = 0;
// 當 ctx_func 執行完畢，會回到 ctx_main
ctx_func.uc_link = &ctx_main;
makecontext(&ctx_func, func, 0);
```
先呼叫 getcontext(&ctx_func)，以取得一個現有的上下文（用意在取得合法的 ucontext_t結構體），並分配堆疊空間。設定 uc_link 為 &ctx_main，表示當 func() 執行結束（或呼叫 setcontext() 跳轉）後，會返回主 context。呼叫 getcontext(&ctx_func) 初始化 ctx_func，再用 makecontext(&ctx_func, func, 0) 指定執行函式為 func()。
完整測試函式：
```cpp
#define _XOPEN_SOURCE 700
#include <stdio.h>
#include <ucontext.h>
#include <stdlib.h>
ucontext_t ctx_main, ctx_func;
void func() {
printf("In func(): start\n");
// 切換回主 context
if (setcontext(&ctx_main) == -1) {
perror("setcontext");
exit(1);
}
// 此處不會執行到，因為 setcontext 不返回
printf("In func(): end\n");
}
int main(void) {
// 取得主 context
if (getcontext(&ctx_main) == -1) {
perror("getcontext");
exit(1);
}
printf("Init\n");
// 初始化 ctx_func，並設定堆疊空間
ctx_func.uc_stack.ss_sp = malloc(8192);
if (ctx_func.uc_stack.ss_sp == NULL) {
perror("malloc");
exit(1);
}
ctx_func.uc_stack.ss_size = 8192;
ctx_func.uc_stack.ss_flags = 0;
// 當 ctx_func 執行完畢，會回到 ctx_main
// ctx_func.uc_link = &ctx_main;
// 取得一個可修改的 context，再設定其執行函式為 func()
if (getcontext(&ctx_func) == -1) {
perror("getcontext");
exit(1);
}
// 設定 ctx_func 執行 func()；此處沒有參數
makecontext(&ctx_func, func, 0);
printf("In main(): before setcontext to func\n");
// 切換到 ctx_func 執行 func()，切換後不會回到這行（除非從 ctx_func 的 uc_link 返回）
if (setcontext(&ctx_func) == -1) {
perror("setcontext");
exit(1);
}
printf("In main(): after setcontext\n");
free(ctx_func.uc_stack.ss_sp);
return 0;
}
```
### 測驗 3
#### 解釋上述程式碼運作原理
結構體
```cpp
typedef struct Env {
int status; /* Current status of the thread */
ucontext_t state; /* Context for saving and restoring thread execution */
int state_reentered; /* Indicate if the context has been reentered */
int ipc_sender; /* Identifier of the thread that sent an IPC message */
int ipc_value; /* Value received from an IPC message */
} Env;
```
程式碼本身是要實現可搶先 (preemptible) 的 user-level thread（使用者層執行緒）運作
```cpp
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 = AAAA;
/* 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 ，使找到 `ENV_UNUSED` 狀態的執行緒時，將他的狀態設置為可執行，因此 `AAAA` ：`ENV_RUNNABLE` 。
```cpp
static void coro_schedule(void)
{
int attempts = 0;
while (attempts < NENV) {
int candidate = (curenv + BBBB) % 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);
}
```
這段程式碼是要實現簡單的 round-robin 排程，應該為搜索下一個，`BBBB` ：`attempts + 1`。
```cpp
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.
*/
CCCC();
}
/* Upon re-entry, simply resume execution */
}
```
這段程式碼是要實現讓當前執行緒主動放棄 CPU，並進入排程。在呼叫 getcontext() 取得當前 context 後，根據 state_reentered 判斷是否是第一次保存該 context，如果是則呼叫排程，因此 `CCCC` ： `coro_shedule`。
```cpp
static void preempt(int signum UNUSED,
siginfo_t *si UNUSED,
void *context UNUSED)
{
DDDD();
}
```
這段程式碼當是要實現 preemption 信號傳來時，讓當前執行緒釋放。符合規範的函式名稱且以 coro_ 開頭，因此 `DDDD` ： `yield`
## Q4
### 測驗 1
#### 解釋上述程式碼運作原理
參見[Fast CRC32](https://create.stephan-brumme.com/crc32/) 提到的 "Half-Byte Algorithm"，我們可將 8-bit 表格查詢拆分為二次 4-bit 查詢，並且有提供產生器，則實際執行一次產生器即可得到所有答案。
```cpp
#include <stdint.h>
#include <stdio.h>
#define POLY 0x82F63B78
void generate_crc32c_table(void) {
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");
}
int main(void) {
generate_crc32c_table();
return 0;
}
```
```
static const uint32_t crc32c_table[16] = {
0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1,
0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d,
0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9,
0xc38d26c4, 0xd3d3e1ab, 0xe330a81a, 0xf36e6f75,
};
```
`AAAA`：`0xc38d26c4`
`BBBB`：`0xd3d3e1ab`
`CCCC`：`0xe330a81a`
`DDDD`：`0xf36e6f75`
#### 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
在 Linux 的 lib 中就有一個 [crc32.c](https://github.com/torvalds/linux/blob/master/lib/crc32.c#L40) 的檔案，其中
```cpp
u32 crc32_le_base(u32 crc, const u8 *p, size_t len)
{
while (len--)
crc = (crc >> 8) ^ crc32table_le[(crc & 255) ^ *p++];
return crc;
}
EXPORT_SYMBOL(crc32_le_base);
```
函式針對 little-endian 進行計算，結合查表（crc32table_le）快速查得校驗值。
```cpp
u32 crc32c_base(u32 crc, const u8 *p, size_t len)
{
while (len--)
crc = (crc >> 8) ^ crc32ctable_le[(crc & 255) ^ *p++];
return crc;
}
EXPORT_SYMBOL(crc32c_base);
```
與 crc32_le_base 類似，但此處計算 CRC32C 校驗值，CRC32C 使用不同的多項式（通常為 0x82F63B78），查表中用 crc32ctable_le 來計算。
[linux/blob/master/fs/jffs2/fs.c](https://github.com/torvalds/linux/blob/master/fs/jffs2/fs.c)
```cpp
....
ri->hdr_crc = cpu_to_je32(crc32(0, ri, sizeof(struct jffs2_unknown_node)-4));
...
```
在更新 inode 屬性時，JFFS2 需要保存或更新該 inode 的原始數據，這些數據包括 inode 的號碼、版本、擁有者、時間戳、檔案大小等資訊。為了防止這些資料在寫入 flash 或從 flash 中讀取時發生損壞，程式使用了 CRC32 校驗碼來計算和保存校驗值。
>Flash 存儲設備（如 NAND flash）在寫入或讀取過程中容易發生資料錯誤，使用 CRC32 可以快速檢查讀取到的資料是否正確
[linux/tools/pcmcia/crc32hash.c](https://github.com/torvalds/linux/blob/master/tools/pcmcia/crc32hash.c)
```cpp
// SPDX-License-Identifier: GPL-2.0-only
/* crc32hash.c - derived from linux/lib/crc32.c, GNU GPL v2 */
/* Usage example:
$ ./crc32hash "Dual Speed"
*/
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
static unsigned int crc32(unsigned char const *p, unsigned int len)
{
int i;
unsigned int crc = 0;
while (len--) {
crc ^= *p++;
for (i = 0; i < 8; i++)
crc = (crc >> 1) ^ ((crc & 1) ? 0xedb88320 : 0);
}
return crc;
}
int main(int argc, char **argv) {
unsigned int result;
if (argc != 2) {
printf("no string passed as argument\n");
return -1;
}
result = crc32((unsigned char const *)argv[1], strlen(argv[1]));
printf("0x%x\n", result);
return 0;
}
```
這段程式碼是計算該字串的 CRC32 校驗值，並以十六進位數形式印出來。使用 CRC32 作為一種雜湊或校驗演算法，將任意字串映射為一個 32 位元的校驗值，根據範例推測用途為快速驗證字串。
### 測驗 3
#### socket函式理解
```cpp
int socket(int domain, int type, int protocol);
//範例：建立一個 IPv4 的 TCP socket
int sockfd = socket(AF_INET, SOCK_STREAM, 0);
if (sockfd < 0) {
perror("socket");
exit(1);
}
```
```cpp
int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen);
```
將建立的 socket 與指定的本機位址（IP 與埠號）綁定。
```cpp
int listen(int sockfd, int backlog);
```
啟動監聽（ backlog 指定排隊等待連線的最大數）
```cpp
int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen);
```
透過監聽 socket 接受一個連線，建立一個新的 socket 對象用於與該客戶端通訊。
`read()/write()`
在建立連線之後，用來讀取或寫入資料。
先撰寫一個測試程式碼：
```cpp
#include <arpa/inet.h>
#include <netinet/in.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
int main(void) {
int server_fd = socket(AF_INET, SOCK_STREAM, 0);
if (server_fd < 0) {
perror("socket");
exit(1);
}
int on = 1;
if (setsockopt(server_fd, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on)) < 0) {
perror("setsockopt");
exit(1);
}
struct sockaddr_in addr;
addr.sin_family = AF_INET;
addr.sin_port = htons(8888);
addr.sin_addr.s_addr = htonl(INADDR_ANY);
if (bind(server_fd, (struct sockaddr *)&addr, sizeof(addr)) < 0) {
perror("bind");
exit(1);
}
if (listen(server_fd, 10) < 0) {
perror("listen");
exit(1);
}
printf("Server listening on port 8888\n");
while (1) {
struct sockaddr_in client_addr;
socklen_t client_len = sizeof(client_addr);
int client_fd = accept(server_fd, (struct sockaddr *)&client_addr, &client_len);
if (client_fd < 0) {
perror("accept");
continue;
}
printf("Client connected: %s:%d\n",
inet_ntoa(client_addr.sin_addr),
ntohs(client_addr.sin_port));
char buf[1024];
int n = read(client_fd, buf, sizeof(buf));
if (n > 0) {
buf[n] = '\0';
printf("Received: %s\n", buf);
n = write(client_fd, buf, n); // echo 給 client
}
close(client_fd);
}
close(server_fd);
return 0;
}
```
這段程式碼可以達成回聲的效果，伺服器持續可接受多個連線，並能與多個 client 反覆互動，但無法讓 client 間互相通訊。
#### select函式理解
```cpp
void FD_ZERO(fd_set *set);
void FD_SET(int fd, fd_set *set);
```
`FD_ZERO` 會將一個 fd_set 結構「清空」
`FD_SET` 會將指定的檔案描述符加入到 fd_set 集合中。這個檔案描述符會在後續的 select() 呼叫中被檢查，看是否有特定的 I/O 事件發生（例如可讀、可寫）。
```cpp
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
```
`nfds` ： 監控中最高檔案描述符 + 1。
`readfds` ： 指向要檢查「可讀」狀態的 fd_set。
`writefds` ： 要檢查「可寫」狀態的集合，若不需要檢查，所以傳入 NULL。
`exceptfds` ： 用來檢查例外或錯誤狀態，若不需要檢查，傳入 NULL。
`timeout` ： 指向等待時間的結構指標。
#### 解釋上述程式碼運作原理
根據 select 的理解可以得到以下的解答：
`IIII` ： 是目前監控的所有描述符中最大的數值加 1，因此答案為 `max_fd`。
`JJJJ` ： 則為指向要監控的可讀描述符集合的指標，因此答案為 `&rfds`.
#### 改進網路聊天室的文字呈現介面
目前是使用 ANSI 控制碼去控制使用者顏色辨識不同使用者
```cpp
#define MAX_BUF 1024 //將 MAX_BUF 事先定義好以便維護
const char *colors[] = {
"\033[1;31m", // red
"\033[1;32m", // green
"\033[1;33m", // yellow
"\033[1;34m", // blue
"\033[1;35m", // magenta
"\033[1;36m", // cyan
"\033[1;37m" // white
};
int client_color[FD_SETSIZE] = {0,1,2,3,4,5,6....};
```
並且在散播訊息時顯現出使用者的 file descriptor 當作使用者編號
```cpp
/* Format the message to improve presentation:
* use ANSI escape code */
char formatted[2 * MAX_BUF];
snprintf(formatted, sizeof(formatted), "%s[User %d]:\033[0m %s",
colors[client_color[fd]], fd, buf);
int f_len = strlen(formatted);
...
/* write to them */
if (write(dest_fd, formatted, f_len) < 0) {
...
```
並且有新連線時通知所有使用者
```cpp
/* create a buffer */
char buf[20] = "New connection \n";
/* Format the message to improve presentation:
* use ANSI escape code */
char formatted[50];
snprintf(formatted, sizeof(formatted), "\n%s[User %d]:\033[0m %s",
colors[client_color[new_fd]], new_fd, buf);
int f_len = strlen(formatted);
```
成效：
Sign in with Wallet
Connect another wallet