# 2025q1 Homework4 (quiz3+4)
contributed by < `Brianpan` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## Quiz 3
### Q1
[完整程式碼](https://github.com/Brianpan/kernel-hw4/blob/master/q1.c)
#### 目標
- 理解高精度無號整數運算
- 以區塊為單位的四則運算和位元操作
#### 結構體定義
```cpp=
#include <inttypes.h>
#include <stdint.h>
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data;
size_t capacity;
} mpi_t[1];
typedef size_t mp_bitcnt_t;
```
mpi_t[1]的理由: 根據03/04[課堂筆記](https://hackmd.io/K4C5ofeqQg6LC8OEbdVcwg)將mpi_t定義為一個元素的陣列,在編譯時便可確保 `mpi_t` 始終會佔據一個 struct 的空間。而使用陣列的形式而非指標，即可不需要再額外分配記憶體
上取整數的商, 此計算方法是利用餘數定義
$0 \leq r < d$ 同時加上d-1
$d-1 \leq r' <(2d-1)$
(2d -1)/d的商數仍是1故這個方法成立
詳細步驟[參見](https://hackmd.io/@sysprog/linux-intdiv#%E6%95%B4%E6%95%B8%E9%99%A4%E6%B3%95%E7%9A%84%E5%90%91%E4%B8%8A%E5%8F%96%E6%95%B4)
```cpp=
/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
return (n + d - 1)/d;
}
```
此程式每個區塊我們最大利用的空間為31位元
因此我們的INTMAX會是0x7ffffff
mpi_set_u64的邏輯是
- 確立容量多少的mpi_t, uint64_t需要三
- 每個block最多存31位元資料,透過INTMAX & 操作去取得數值
- 下一輪即是右移31位元並繼續比較
```cpp=
#define INTMAX 0x7ffffff
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;
}
```
#### mul_naive
略過初始化和清理區域變數
乘法的主要邏輯是這個雙層迴圈
乘數和被乘數以區塊為單位相乘得到的結果再放置到相應的位置
舉個例子 n = 0, m = 1
先將對應區塊的乘積算出, 也就是變數r,使用uint64_t是因為兩個31位元大小乘法必須使用64位元存放
c變數為進位的數值
再來是填格子,把乘積放到對應的位置
k從m+n開始算起,因為至少會從m+n位開始填
可以想成指數乘法
繼續條件是考慮是否有進位或是仍有數值沒處理
```cpp=
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;
}
}
}
```
#### 除法與餘數運算
利用的函式：
mpi_sizeinbase: 計算需要多少個位元, 8 -> $2^3$ 結果為三
mpi_mul_2exp:取得 $r * 2^x$ ->這裡的x是1
mpi_testbit:比較某個索引的值是否是1
mpi_setbit:設置特定位元至某個索引
mpi_sub: mpi減法運算
主要程式邏輯可以想成直式除法
$mpi_mul_2exp(r, r, 1);$ 的用意是上一輪結束後要和新一輪位數合併
至於使用1的理由是我們是以二進位表示法的除法
接著判斷被除數的新加進來的最右位是否存在
存在就設置位元
第二個if是直式除法的核心邏輯
如果現在被除數的值比除數大,減掉被除數, 並設置商在該i位元為一
比起十進位簡化很多,因為二進位除法一個位數的商只有0或1兩種可能
```cpp=
size_t start = mpi_sizeinbase(n0, 2) - 1;
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);
}
}
```
#### 計算最大公因數
用的是輾轉相除法的定義解
```cpp=
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);
}
```
### Q2
[完整程式](https://github.com/Brianpan/kernel-hw4/blob/master/q2.c)
#### 目標
- 理解 SIMD within a register (SWAR) 技巧
- 實作以區塊為單位的快速字元搜尋
#### SWAR
透過利用硬體的word大小, 一次進行以word大小的區塊做操作
本題是一次比較sizeof(long)長度的字串是否包含要找尋的目標字元
#### memchr_opt
函數定義： void *memchr_opt(const void *str, int c, size_t len)
找到出現字元c的指標位置,如果沒有回傳NULL
改進的方法是利用SWAR技巧一次比較一個word大小
本題是比較sizeof(long)
#### 主要程式邏輯
- 迴圈判斷是否對齊並檢查沒對齊的字元是否符合條件
```cpp=
while (UNALIGNED(src)) {
if (!len--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
```
- 以一個sizeof(long)的大小去比較該字元是否存在這個區塊中, 這裡也是程式的精髓,
透過位元運算把一個字元大的字元變成sizeof(long)
```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 |= mask << i;
```
透過特殊設計的DETECT_CHAR巨集判斷字元是否在內
```cpp=
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
```
- 最後是去搜尋sizeof(long)長度的區塊是哪一個包含目標字元,當然如果len等於0代表沒有找到,回傳NULL
```cpp
while (len--) {
if (*src == d)
return (void *) src;
src++;
}
return NULL;
}
```
#### 解構DETECT_CHAR
```cpp=
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* 當 X（型態為 long）包含 NULL byte 時會是非 0 */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(X^mask)
```
DETECT_CHAR呼叫DETECLT_NULL(X^mask)判斷X和mask是否有位元組相符
用XOR比較的理由是如果位元組相同回傳0x00
接著解構DETECT_NULL巨集
$(X) - (0x0101010101010101)$: 如果某個位元組是0x00相減過後為0xFF
$~(X)$: 取一補數後0x00會變為0xFF
$(0x8080808080808080)$:如果該字元是0x00前面兩個操作結束後的最高位是1
```graphviz
digraph G {
rankdir=TB;
node [shape=record];
context1 [label="1|*|*|*|*|*|*|*"];
}
```
### Q3
#### 目標
- 了解linux當中的signal
- 了解搶佔式coroutine
詳見[整理筆記](https://hackmd.io/@brianpan21/coroutine)
建立coroutine後要更改狀態是可排程`ENV_RUNNABLE`
```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 = 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;
}
```
排程coroutine使用`attempts + 1` 避免重複在試同一個coroutine
```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);
}
```
coro_yield: 讓出資源給其他coroutine
```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.
*/
coro_schedule();
}
/* Upon re-entry, simply resume execution */
}
```
搶佔coroutine就是讓出現在的資源給其他coroutine
```cpp=
static void preempt(int signum UNUSED,
siginfo_t *si UNUSED,
void *context UNUSED)
{
coro_yield();
}
```
## Quiz 4
### Q1
#### 目標
- CRC (循環冗餘校驗，Cyclic Redundancy Check) 的運作方法
CRC 計算時，不是使用標準的數字除法，而是透過 XOR 運算來**模擬**二進位多項式的除法
在計算 CRC 時，使用資料的多項式去除以預先指定的 CRC 多項式，取餘數作為校驗碼。例如，給定資料 11010101（8-bit），若用 0x1EDC6F41 來除，就會得到一個 32-bit 餘數，這就是 CRC32 的值。
在編譯器最佳化的運作下(cmov)使用三元運算子會有更好的效率
```cpp=
for (int bit = 0; bit < 8; bit++)
crc = (crc & 1) ? ((crc >> 1) ^ UINT32_C(0x82f63b78)) ? (crc >> 1);
```
題目是要計算32位元組長度的CRC校驗碼產生
利用godbolt程式碼來改寫
最外層迴圈i是執行16組的預設資料
內迴圈j是每4個位元為一組
```cpp=
#include <stdint.h>
#include <stdio.h>
/* CRC32C polynomial */
#define POLY 0x82f63b78
void generate()
{
printf("static const uint32_t crc32_table[16] = {\n");
for (size_t i = 0; i < 16; i++) {
uint32_t crc = i;
for (uint32_t j = 0; j < 4; j++)
crc = (crc >> 1) ^ (-(int)(crc & 1) & POLY);
printf(" 0x%08X%s", crc, (i % 4 == 3) ? ",\n" : ", ");
}
printf("};\n");
}
int main()
{
generate();
}
```
#### XOR技巧
```cpp=
crc = (crc >> 1) ^ (-(int)(crc & 1) & POLY);
```
(crc & 1):檢查LSB是否為一
-(int)(crc & 1): 如果為一,取負數的32位元組表示是0xffffffff相當於所有的位元為一
- & POLY: 和預設的多項式值取AND運算
- (crc >> 1) ^ (上述結果)：(crc >> 1)就是等同於如果LSB是一就和POLY做XOR運算
#### 產生後的表格
```cpp=
static const uint32_t crc32_table[16] = {
0x00000000, 0x105EC76F, 0x20BD8EDE, 0x30E349B1,
0x417B1DBC, 0x5125DAD3, 0x61C69362, 0x7198540D,
0x82F63B78, 0x92A8FC17, 0xA24BB5A6, 0xB21572C9,
0xC38D26C4, 0xD3D3E1AB, 0xE330A81A, 0xF36E6F75,
};
```
AAA: 0xc38d26c4
BBB: 0xd3d3e1ab
CCC: 0xe330a81a
DDD: 0xf36e6f75
### Q2
沒有修過信號與系統 先跳過 @@
### Q3
#### 學習目標
- 精簡的聊天伺服器實作
- tcp socket建立流程
- select 系統呼叫
#### 聊天伺服器
主要程式碼邏輯透過下圖的描述建立一個TCP伺服器
socket() -> bind() -> listen() 在 event loop之前完成
accept()則是在event loop去取得新連接
中間有一段ioctl使得連結不是blocking
原因如註解所說斷開的連結仍可以讀取, 所以之後的read呼叫可能會卡住
```cpp=
int onoff = 1;
if (ioctl(new_fd, FIONBIO, &onoff) < 0) {
printf("fcntl(%d): %s\n", new_fd, strerror(errno));
close(new_fd);
continue;
}
```
#### 更改增加使用者
[commit](https://github.com/Brianpan/kernel-hw4/commit/01c64ecd07572d471d042bbfc7523e372c952f7d)
主要的改動是多一個結構體userinfo的陣列存取使用者名稱
```cpp=
struct userinfo {
int fd;
char name[32];
};
```
在每一次accept()之後給使用者發送訊息輸入使用者名稱
並且透過[set_userinfo](https://github.com/Brianpan/kernel-hw4/blob/01c64ecd07572d471d042bbfc7523e372c952f7d/chat.c#L19C5-L19C17)去判斷儲存使用者名稱
並在廣播訊息的時候把發訊息的使用者名稱透過snprintf再寫給建立連接的其他檔案描述子
```cpp=
int sz = snprintf(userbuf, sizeof(userbuf), "[%.*s]:", (int) sizeof(users[fd].name), users[fd].name);
```
#### 測驗答案
- IIII: max_fd
- JJJJ: &rfds
Sign in with Wallet
Connect another wallet