# 2025q1 Homework4 (quiz3+4)
contributed by < `liangchingyun` >
## 2025q1 第 3 週測驗題
### 測驗 [`1`](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-1)
實作一個多精度整數的運算框架，也就是支援比 64-bit 更大的整數計算
#### 延伸問題 1
> 解釋上方程式碼運作原理
##### 資料結構定義
```c
#include <inttypes.h>
#include <stdint.h>
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data; // 存放多精度整數每一部分的陣列，每個元素為 31-bit
size_t capacity; // 表示 data 陣列目前有多少個 element (即有多少「31-bit 位元段」)
} mpi_t[1];
typedef size_t mp_bitcnt_t;
```
##### 記憶體管理
```c
// 初始化
void mpi_init(mpi_t rop)
{
rop->capacity = 0;
rop->data = NULL;
}
// 釋放記憶體
void mpi_clear(mpi_t rop)
{
free(rop->data);
}
// 擴展 data 陣列的長度，並初始化新擴展的空間為 0
void mpi_enlarge(mpi_t rop, size_t capacity)
{
if (capacity > rop->capacity) { // 只有在新的 capacity 大於目前的容量時，才需要實際擴充
size_t min = rop->capacity;
rop->capacity = capacity;
rop->data = realloc(rop->data, capacity * 4);
// 新的空間大小是 capacity * 4 bytes
// 原因是data 裡面每個元素是 uint32_t，其大小就是 4 bytes
if (!rop->data && capacity != 0) {
fprintf(stderr, "Out of memory (%zu words requested)\n", capacity);
abort();
}
// 對新分配的區塊（從舊的大小 min 到現在的大小 capacity）進行初始化
for (size_t n = min; n < capacity; ++n)
rop->data[n] = 0;
}
}
// 去除尾端為 0 的位元段，減少記憶體使用
void mpi_compact(mpi_t rop)
{
size_t capacity = rop->capacity;
// 如果目前容量是 0，直接結束，無需處理
if (rop->capacity == 0)
return;
// 找出最右邊（高位）非零的那一個元素
for (size_t i = rop->capacity - 1; i != (size_t) -1; --i) {
if (rop->data[i])
break;
capacity--; // 若 rop->data[i] == 0，代表這一格可以被移除，因此縮減 capacity
}
// 保護性檢查
assert(capacity != (size_t) -1);
// 重新配置記憶體，只保留實際有用的部份
rop->data = realloc(rop->data, capacity * 4);
rop->capacity = capacity;
if (!rop->data && capacity != 0) {
fprintf(stderr, "Out of memory (%zu words requested)\n", capacity);
abort();
}
}
```
##### 輔助工具
```c
/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
return (n + d - 1) / d; // 計算 n ÷ d 的向上取整（ceiling）結果
}
#define INTMAX 0x7fffffff // 31-bit 的最大整數值
```
| n | d | n / d | ceil_div(n, d) |
|:---:|:---:|:-----:|:--------------:|
| 10 | 3 | 3.33 | 4 |
| 5 | 2 | 2.5 | 3 |
| 8 | 4 | 2 | 2 |
| 0 | 3 | 0 | 0 |
##### 基本設定與轉換
```c
// 將一個 64-bit 的整數，切成多個 31-bit 段，裝入 data 陣列
void mpi_set_u64(mpi_t rop, uint64_t op)
{
size_t capacity = ceil_div(64, 31); // 需要 3 個欄位
mpi_enlarge(rop, capacity); // 確保 rop 有足夠空間
// 拆解 uint64_t 成多個 31-bit 整數
for (size_t n = 0; n < capacity; ++n) {
rop->data[n] = op & INTMAX; // 取低 31-bit
op >>= 31; // 將剩下的往右移，準備下次寫入
}
// 清除多餘資料
for (size_t n = capacity; n < rop->capacity; ++n)
rop->data[n] = 0;
}
```
* `rop`: 多精度整數，作為輸出目標。
* `op`: 一個 64-bit 的無號數，要被轉換並儲存。
* 例子:
* `rop->data[0]` = 最低 31-bit
* `rop->data[1]` = 中間 31-bit
* `rop->data[2]` = 最高 2-bit（因為 31x3 = 93 > 64）
##### 乘法
```c
static void mpi_mul_naive(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
size_t capacity = op1->capacity + op2->capacity;
mpi_t tmp;
mpi_init(tmp);
mpi_enlarge(tmp, capacity);
for (size_t n = 0; n < tmp->capacity; ++n)
tmp->data[n] = 0;
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]; // r 是中間乘積（會超過 31 bit，所以用 uint64_t）
uint64_t c = 0;
for (size_t k = n+m; c || r; ++k) { // 從 k = n + m 開始累加（就是十進位乘法中對齊的位置）
if (k >= tmp->capacity)
mpi_enlarge(tmp, tmp->capacity + 1);
tmp->data[k] += (r & INTMAX) + c; // 加上本位結果與前一位的進位
r >>= 31; // 下一個 31 bit
c = tmp->data[k] >> 31; // 如果 overflow，產生進位
tmp->data[k] &= INTMAX; // 只保留 31 bit
}
}
}
mpi_set(rop, tmp);
mpi_compact(rop);
mpi_clear(tmp);
}
```
例子: 假設 `op1 = ABC`，`op2 = DE`
```
A B C
× D E
---------------------
AE BE CE ← 對齊加總
+ AD BD CD
---------------------
```
##### 除法與餘數
* 初始化商 `q = 0`，餘數 `r = 0`
* 從最高位開始，比對每一位是否能被除數 `d` 減去
* 如果可以，商的那一位設為 `1`，餘數更新為減掉後的值
```c
void mpi_fdiv_qr(mpi_t q, mpi_t r, const mpi_t n, const mpi_t d)
{
// 建立副本避免破壞原始數據
mpi_t n0, d0;
mpi_init(n0);
mpi_init(d0);
mpi_set(n0, n);
mpi_set(d0, d);
// 除以零檢查
if (mpi_cmp_u32(d0, 0) == 0) {
fprintf(stderr, "Division by zero\n");
abort();
}
// 初始化商與餘數
mpi_set_u32(q, 0);
mpi_set_u32(r, 0);
// 從最高位 bit 開始處理
size_t start = mpi_sizeinbase(n0, 2) - 1;
// Long Division 迴圈，每次處理一個 bit
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);
}
}
mpi_clear(n0);
mpi_clear(d0);
}
```
##### 最大公因數
* 遞迴呼叫 `mpi_fdiv_qr`，直到餘數為 `0`，得到 GCD
* 終止條件：`op2 == 0`，這時 `op1` 就是 GCD。
```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);
}
```
##### 測試程式碼
驗證 `549755813889 ÷ 1234 = 445507142...661` 是否正確。
```c
printf("mpi_fdiv_qr\n");
{
mpi_t n, d, q, r;
mpi_init(n);
mpi_init(d);
mpi_init(q);
mpi_init(r);
mpi_set_str(n, "549755813889", 10);
mpi_set_str(d, "1234", 10);
mpi_fdiv_qr(q, r, n, d);
assert(mpi_cmp_u32(q, 445507142) == 0);
assert(mpi_cmp_u32(r, 661) == 0);
mpi_clear(n);
mpi_clear(d);
mpi_clear(q);
mpi_clear(r);
}
```
驗證 `GCD(2310, 46189) = 11`
```c
printf("GCD test\n");
{
mpi_t a, b, r;
mpi_init(a);
mpi_init(b);
mpi_init(r);
mpi_set_str(a, "2310", 10);
mpi_set_str(b, "46189", 10);
mpi_gcd(r, a, b);
assert(mpi_cmp_u32(r, 11) == 0);
mpi_clear(a);
mpi_clear(b);
mpi_clear(r);
}
```
#### 延伸問題 2
> 這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
#### 延伸問題 3
> 改進最大公因數的運算效率
### 測驗 [`2`](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-2)
#### 延伸問題 1
> 解釋上述程式碼運作原理
##### 判斷一個整數是否為奇數
確認最低位元是否為 1
傳統寫法:
```c
#include <stdint.h>
bool both_odd(uint32_t x, uint32_t y)
{
return (x & 1) && (y & 1);
}
```
這樣需要兩次 `&` 運算與一次`&&` 邏輯運算。
SWAR 的核心思想是：把多個資料打包在同一個暫存器中，並一次性處理，這可以減少操作次數並提升效能。
bitmask 定義:
```c
static uint64_t SWAR_ODD_MASK = (1L << 32) + 1; // 第 0 位及第 32 位為 1
bool both_odd_swar(uint64_t xy) {
return (xy & SWAR_ODD_MASK) == SWAR_ODD_MASK;
}
```
測試程式:
```c
static inline uint64_t bit_compound(uint32_t x, uint32_t y) // 同時檢查兩個位置的最低位是否都是 1
{
return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}
int main()
{
int x = 12345678;
int y = 9012345;
uint64_t xy = bit_compound(x, y);
printf("%d, %d\n", both_odd(x, y), both_odd_swar(xy));
}
```
##### 加速 `memchr` 搜尋
步驟:
1. 對齊檢查：先用 byte-wise 判斷，直到指標對齊。
2. word 級搜尋：一次檢查 `sizeof(long)` bytes，判斷這個 word 內是否有目標字元。
3. 當剩下不足一整個 word 時，再回到 byte-wise 搜尋。
```c
#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
/* How many bytes are loaded each iteration of the word copy loop */
#define LBLOCKSIZE (sizeof(long))
/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
(((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(X^mask)
void *memchr_opt(const void *str, int c, size_t len)
{
const unsigned char *src = (const unsigned char *) str;
unsigned char d = c;
while (UNALIGNED(src)) {
if (!len--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
if (!TOO_SMALL(len)) {
/* If we get this far, len is large and src is word-aligned. */
/* The fast code reads the source one word at a time and only performs
* a bytewise search on word-sized segments if they contain the search
* character. This is detected by XORing the word-sized segment with a
* word-sized block of the search character, and then checking for the
* presence of NULL in the result.
*/
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;
while (len >= LBLOCKSIZE) {
if (DETECT_CHAR(*asrc, mask))
break;
asrc++;
len -= LBLOCKSIZE;
}
/* If there are fewer than LBLOCKSIZE characters left, then we resort to
* the bytewise loop.
*/
src = (unsigned char *) asrc;
}
while (len--) {
if (*src == d)
return (void *) src;
src++;
}
return NULL;
}
```
#### 延伸問題 2
> 比較 Linux 核心原本 (與平台無關) 的實作和 `memchr_opt`，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
>
#### 延伸問題 3
> 研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
> 下一步：貢獻程式碼到 Linux 核心
> [Phoronix 報導](https://www.phoronix.com/news/Linux-Kernel-Faster-memchr)
### 測驗 [`3`](https://hackmd.io/@sysprog/linux2025-quiz3#%E6%B8%AC%E9%A9%97-3)
## 2025q1 第 4 週測驗題
### 測驗 [`1`](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-1)
#### 延伸問題 1
> 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
#### 延伸問題 2
> 設計實驗來分析 [Fast CRC32](https://create.stephan-brumme.com/crc32/) 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
#### 延伸問題 3
> 以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令
### 測驗 [`2`](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-2)
#### 延伸問題 1
> 解釋上述程式碼運作原理，搭配「[信號與系統](https://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/103S207)」教材
#### 延伸問題 2
> 探討定點數的使用和其精確度
#### 延伸問題 3
> 改進 MIDI 一閃一閃亮晶晶的音效輸出
### 測驗 [`3`](https://hackmd.io/@sysprog/linux2025-quiz4#%E6%B8%AC%E9%A9%97-3)
#### 延伸問題 1
> 解釋上述程式碼運作原理
#### 延伸問題 2
> 學習 [jserv/ttt](https://github.com/jserv/ttt) 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
#### 延伸問題 3
> 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 [ping value](https://www.business.att.com/resources/knowledge-center/what-is-latency-impact-on-gaming-streaming.html) 的處理機制
Sign in with Wallet
Connect another wallet