# 2025q1 Homework4 (quiz3+4)
contributed by <`bevmmf`>
## 預期目標
- [ ] 檢驗學員對於 bitwise 操作及 rbtree 的熟悉程度
- [ ] 檢驗學員對於 CS:APP 第二章的掌握：別忘了課程指定的教科書
- [ ] 引導學員接觸 Linux 核心原始程式碼及解說應用案例
## quiz3
### 測驗一
補完程式碼
- `AAAA`：`(n + d - 1) / d`
- `BBBB`：`0x7fffffff`
- `CCCC`：`n + m`
- `DDDD`：`1`
- `EEEE`：`mpi_gcd(rop, op2, r)`
:::success
解釋上述程式碼運作原理
:::
```c
#include <inttypes.h> //support int32_t, uint64_t
#include <stdint.h> //support uint32_t, int64_t
/* mpi: Multi-Precision Integers */
typedef struct {
uint32_t *data;
size_t capacity;
} mpi_t[1];
typedef size_t mp_bitcnt_t;
```
- Essential Knowledge
- `size_t` : 一個專為表示「大小」或「數量」設計的unsignd int類型
- 根據系統為 32bits或64bits
- 必為非負
此為宣告本題MPI的結構，由 `capacity` 段 uint32_t 類型 `data` 組合成多精度的整數進而能描述規模大的int
- `mpi_t[1]` 表示單元素array，目的是傳遞pointer
`mpi_init` : 初始化一mpi_t使capacity為0，data指向NULL
`mpi_clear` : free 釋放一mpi_t之data
```c
void mpi_enlarge(mpi_t rop, size_t capacity)
{
if (capacity > rop->capacity) {
size_t min = rop->capacity;
rop->capacity = capacity;
rop->data = realloc(rop->data, capacity * 4);
if (!rop->data && capacity != 0) {
fprintf(stderr, "Out of memory (%zu words requested)\n", capacity);
abort();
}
for (size_t n = min; n < capacity; ++n)
rop->data[n] = 0;
}
}
```
`mpi_enlarge` : 擴充一mpi_t的data段數，若傳參capacity > 該mpi之capacity才運作。運作時由realloc重新分配(傳參capacity*4)bytes，然後將新擴充的段數data都設為0。若分配失敗則輸出錯誤資訊然後abort。
```c
void mpi_compact(mpi_t rop)
{
size_t capacity = rop->capacity;
if (rop->capacity == 0)
return;
for (size_t i = rop->capacity - 1; i != (size_t) -1; --i) {
if (rop->data[i])
break;
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();
}
}
```
`mpi_compact` : 壓縮一mpit的記憶體使用，去除末尾的零元素，調整capacity。從data array末尾倒序檢查是否為0，為0則使capcity-1，直到不為0退出。此時退出後之capacity即為皆非0值之data段數。最後利用realloc分配該capacity段數4 bytes的空間。分配失敗則終止。
:::info
- 為什麼需要 `(size_t) -1`？
- 此為將 -1 強制轉型為size_t值(0xFFFFFFFF或0xFFFFFFFFFFFFFFFF)
- 當 i = 0 - -i 時i會變成size_t最大值也就是(size_t)，確保迴圈不會無限執行
- `%zu` 專為用來輸出 size_t 的值
- 為什麼不用 %d 或 %u？
- %d 用於有符號整數（int），而 size_t 是無符號的，可能導致輸出錯誤（特別是當值很大時）。
- %u 用於無符號 int，但 size_t 的大小可能與 int 不同（例如在 64 位系統上，size_t 可能是 64 位，而 int 是 32 位）。使用 %u 可能導致截斷或未定義行為。
:::
```c
/* ceiling division without needing floating-point operations. */
static size_t ceil_div(size_t n, size_t d)
{
return (n + d - 1) / d;
}
#define INTMAX 0x7fffffff
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;
}
```
`ceil_div` : 取天花板數(向上取整)
`mpi_set_u64` : 將 uint64_t 轉成 mpi_t
- 操作
- 先用 ceil_div 對 64 與 31 取得分段數 capacity
- 再將傳參mpi擴充到該capacity
- 最後將 uint64_t 的data以31個1(0x7FFFFFFF,$2^{31}-1$)為一段作mask放進傳參mpi
- 若傳參mpi capcity過大則將高段數設為0
:::info
為啥用 31 bit 作為一段長度?
因為若用 32 bit 加法或乘法進位(carry)處理會變複雜
- 例如：兩個最大 32 位元數相加：0xFFFFFFFF + 0xFFFFFFFF = 0x1FFFFFFFE（33 位元）
- 兩個 31 位元數相加的最大結果是 0x7FFFFFFF + 0x7FFFFFFF = 0xFFFFFFFE（32 位元），正好能放入一個 uint32_t 而不溢位
:::
```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];
uint64_t c = 0;
for (size_t k = n + m; 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_set(rop, tmp);
mpi_compact(rop);
mpi_clear(tmp);
}
```
`mpi_mul_naive` : mpi乘法
- 運作
做直式乘法
- 外圈 : op1段數遍歷
- 中圈 : op2段數遍歷
- 內圈 : 處理carry加到data[k+1]
:::info
是否需要以下部分?
1.
```c
if (k >= tmp->capacity)
mpi_enlarge(tmp, tmp->capacity + 1);
```
不需要 => n段*m段不會大於n+m段
2.
```c
tmp->data[k] &= INTMAX;
```
不需要 => 因data大小即為INTMAX
:::
```c
//計算多精度整數 n 除以 d 的商 q 和餘數 r (即 n = d * q + r)
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);//copy
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);
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);
}
}
mpi_clear(n0);
mpi_clear(d0);
}
```
使用二進制長除法
- 以下為運作流程 :
### 初始化
- 被除數：n0 = 1101（十進位 13）
- 除數：d0 = 11（十進位 3）
- 商：q = 0
- 餘數：r = 0
- 起始索引：`start = mpi_sizeinbase(n0, 2)` - 1 = 4 - 1 = 3（最高位索引）
### 逐位處理
從最高位（i = 3）到最低位（i = 0）逐一處理被除數的每一位。
#### 步驟 1：i = 3（最高位，n0[3] = 1）
- 餘數左移：r = 0 左移 1 位 → r = 0
- 附加位元：n0[3] = 1，設 r[0] = 1 → r = 1
- 比較與減法：r = 1 < d0 = 3，不減，設 q[3] = 0
- 結果：r = 1, q = 0000
#### 步驟 2：i = 2（n0[2] = 1）
- 餘數左移：r = 1 左移 1 位 → r = 10（十進位 2）
- 附加位元：n0[2] = 1，設 r[0] = 1 → r = 11（十進位 3）
- 比較與減法：r = 3 >= d0 = 3，減去 d0：r = 3 - 3 = 0，設 q[2] = 1
- 結果：r = 0, q = 0100
#### 步驟 3：i = 1（n0[1] = 0）
- 餘數左移：r = 0 左移 1 位 → r = 0
- 附加位元：n0[1] = 0，r 不變 → r = 0
- 比較與減法：r = 0 < d0 = 3，不減，設 q[1] = 0
- 結果：r = 0, q = 0100
#### 步驟 4：i = 0（最低位，n0[0] = 1）
- 餘數左移：r = 0 左移 1 位 → r = 0
- 附加位元：n0[0] = 1，設 r[0] = 1 → r = 1
- 比較與減法：r = 1 < d0 = 3，不減，設 q[0] = 0
- 結果：r = 1, q = 0100
### 最終結果
- 商：q = 0100（十進位 4）
- 餘數：r = 1（十進位 1）
### 驗證
驗證結果：
13 = 3 × 4 + 1
```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);
}
```
使用輾轉相除法
當發生整除時(下一次r=0，guard clause發生return)，將輸出rop設為當時被除數op1
:::success
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
:::
我將原來遞迴修改成以迭代實作
```c
void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
if (mpi_cmp_u32(op1, 0) == 0 || mpi_cmp_u32(op2, 0) == 0) {
fprintf(stderr, "Both operands are zero, GCD undefined\n");
return;
}
mpi_t opa, opb, q, r;
mpi_init(opa); // Dividend
mpi_init(opb); // Divisor
mpi_init(q);
mpi_init(r);
mpi_set(opa,op1);
mpi_set(opb,op2);
while(mpi_cmp_u32(opb, 0) != 0){
mpi_fdiv_qr(q, r, opa, opb);
mpi_set(opa,opb);
mpi_set(opb,r);
}
mpi_set(rop,opa);
mpi_clear(q);
mpi_clear(r);
mpi_clear(opa);
mpi_clear(opb);
}
```
:::success
改進最大公因數的運算效率
:::
### 測驗二
- `AAAA`：`(x) ^ (mask)`
- `BBBB`：`mask << i`
- `CCCC`：`*asrc`
### 測驗三
- `AAAA`：`ENV_RUNNABLE`
- `BBBB`：`attempts + 1`
- `CCCC`：`coro_shedule`
- `DDDD`：`yield`
## quiz4
### 測驗一
- `AAAA`：`0xc38d26c4`
- `BBBB`：`0xd3d3e1ab`
- `CCCC`：`0xe330a81a`
- `DDDD`：`0xf36e6f75`
### 測驗二
- `AAAA`：`0x7FFF`
- `BBBB`：`0x80000000`
- `CCCC`：`0x7FFFFFFF`
- `DDDD`：`0x80000000`
- `EEEE`：`0x7FFFFFFF`
- `FFFF`：`input & 0xFF`
- `GGGG`：`Q15_MIN`
- `HHHH`：`Q15_MAX`
### 測驗三
- `IIII`：`max_fd`
- `JJJJ`：`&rfds`
## Reference
- [2025q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)
- [2025q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz4)
Sign in with Wallet
Connect another wallet