# 2025q1 Homework4 (quiz3+4)
contributed by < `rota1001` >
## Q3
### 測驗 1
:::danger
不要列出參考題解，專注題目本身
:::
- `AAAA`：
這個函式是要計算向上取整，於是使用 $\lceil \frac{n}{d} \rceil = \lfloor \frac{n+d-1}{d} \rfloor$ 的概念去實作：
```cpp
static size_t ceil_div(size_t n, size_t d)
{
return (n + d - 1) / d;
}
```
- `BBBB`：
接下來這個部份，`int` 中最大的正數是除了最高位以外，其他都是 1：
```cpp
#define INTMAX 0x7fffffff
```
- `CCCC`：
這是一個乘法操作，兩層迴圈分別代表兩個數在 $2^{31}$ 進位制下的位數。於是，一個 `n` 次一個 `m` 次的數乘起來會放在 `n + m` 次的位置。然後之所以它會繼續往高處去做是因為進位的關係，如果兩者的乘積 `r` 在這個位數還沒有用完的話，那就會往更高次的地方去進位。
```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 = n + m; c || r; ++k) {
...
}
}
}
```
- `DDDD`：
這個部份在做逐位的除法，`mpi_mul_2exp(r, r, 1)` 做的事情是一直把 `r` 乘上 2，這個函式的原理在[下面](https://hackmd.io/QItcw2JIRta8OcN69eyyyg?both=&stext=1463%3A11%3A0%3A1746798190%3A9w41aW)有做解釋。
- `EEEE`：
這是再做輾轉相除法 `mpi_fdiv_qr(q, r, op1, op2);` 會計算出 `op1` 除以 `op2` 的商和餘數，於是除數會變成被除數、餘數會變成除數，繼續遞迴呼叫 `mpi_gcd` 直到中止條件成立（也就是 `op2` 變成 0），呼叫的是 `mpi_gcd(rop, op2, r)`
:::success
解釋上述程式碼運作原理
:::
上述程式碼實現了一個大整數的各種運算，結構體是用一個 32 位元無號整數的陣列與容量組成，每個數字存一個範圍是有號整數的數字，第 `i` 格代表 $2^{31}$ 進位制的第 `i` 位。提供了一些函式，這裡瑣碎的不講，只敘述一些實作想法：
- `ceil_div`：
利用 $\lceil \frac{n}{d} \rceil = \lfloor \frac{n+d-1}{d} \rfloor$ 的概念實作
- `mpi_mul_naive`：
對於第一個 `mpi_t` 的第 `n` 位和第二個 `mpi_t` 的第 `m` 位而言，他們乘起來的數字要加到第 `n + m` 位，並且依照 $2^{31}$ 進位制往高位進位，直到無法進位。
- `mpi_fdiv_qr`：
先用一個數字 `r` 代表餘數，如果我們只看 `mpi_setbit` 和 `mpi_mul_2exp` 的操作的話，那 `r` 最後會變成 `n0`。然後如果中途在 $i=k$ 的時候被減掉 $d_0$ 的話，結果上來說他是被減掉了 $d_0\times 2^k$，同時，`q` 被加上了 $2^k$，所以 $d_0q+r$ 會維持一個定值，可以發現它是在做逐位元的除法（對 `q` 來說逐位元）。
```cpp
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);
}
}
```
- `mpi_gcd`：
使用 `mpi_fdiv_qr` 做輾轉相除法。
:::success
這項實作依賴遞迴呼叫，請避免使用並降低記憶體開銷
:::
將 `mpi_gcd` 改為迭代的輾轉相除法，因為 `mpi_fdiv_qr` 是傳入指標，所以還是會需要 `q` 和 `r` 兩個變數去紀錄結果，再把結果複製進去。然後使用一個兩格的陣列，利用 bitwise 操作將兩個元素交替使用。另外，因為 `op1` 和 `op2` 不能改，所以這兩格的陣列也是必要的記憶體開銷。
```cpp
void mpi_gcd(mpi_t rop, const mpi_t op1, const mpi_t op2)
{
unsigned int i = 1;
mpi_t op[2], q, r;
mpi_init(op[0]);
mpi_init(op[1]);
mpi_init(q);
mpi_init(r);
mpi_set(op[0], op1);
mpi_set(op[1], op2);
while (mpi_cmp_u32(op[i], 0)) {
mpi_fdiv_qr(q, r, op[i ^ 1], op[i]);
mpi_set(op[i ^ 1], r);
i ^= 1;
}
mpi_set(rop, op[i ^ 1]);
mpi_clear(op[0]);
mpi_clear(op[1]);
}
```
:::success
改進最大公因數的運算效率
:::
試著去分析這個問題後，想到一個改良方式。在 [最大公因數特性和實作考量](https://hackmd.io/@sysprog/gcd-impl) 中看到對最大公因數的改進有其中一種是在兩者差小於某個倍數時使用減法代替除法和模運算。去分析一下，現在有兩個數字 $a$ 和 $b$，$2(a\% b)$ 比 $b$ 小的機率大約是 $\frac{1}{2}$，甚至考慮到 `mpi_fdiv_qr` 的除法的複雜度大約是被除數的位元數，所以可以讓相差 32 倍以下的都使用減法，這樣的話會有 $\frac{31}{32}$ 是符合這種情況的（當然第一次很大機率還是用除法，不過接下來大部分都會用減法）。
這部份要實作一個 `mpi_cmp_shift_5` 函式，代表第一個 `mpi_t` 和左移 5 之後的第二個 `mpi_t` 的比較。這個函式的複雜度大約是 31 位元一組之後的長度，所以比除法快 31 倍左右。
這部份實作比較複雜，剩下的部份都是處理細節，等之後有空再回來做（然後我也會偏好把 `mpi_t` 的結構定義改成每個數字是 32 位元的，這樣在位元運算上比較方便，也沒有找到什麼一定要 31 位元的理由）。
### 測驗 2
- `AAAA`：`(x) ^ (mask)`
- `BBBB`：`mask << i`
- `CCCC`：`*asrc`
:::success
解釋上述程式碼運作原理
:::
`asrc` 是一個指向 `unsigned long` 的指標，並且初始值是 `src`。它目的是要每次進行 64 位元的檢查，看有沒有 `c` 這個字元在裡面。將 8 個 `c` 並在一起變成一個 mask，然後將一個 `unsigned long` 去和它做 bitwise xor，並且使用 `DETECT_NULL` 去檢查是否有 0。如果找到某個 `unsigned long` 裡面有這個字元的話，那麼就在這裡面去找到那個字元的位置。
:::success
比較 Linux 核心原本 (與平台無關) 的實作和 `memchr_opt`，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
:::
我設計了一個實驗，長度為 1 到 10000 ，在長度的一半的地方放目標的字元（目的是希望每次都是在中間被找到）。
```cpp
void test()
{
memset(str, 1, sizeof(str));
for (int i = 0; i < 10000; i++) {
str[i / 2] = 2;
for (int j = 0; j < 100; j++) {
result[0][i] += PERFTEST(memchr, str, 2, i + 1);
}
for (int j = 0; j < 100; j++){
result[1][i] += PERFTEST(memchr_opt, str, 2, i + 1);
}
str[i / 2] = 1;
}
FILE *file[2];
file[0] = fopen("file0.txt", "w");
file[1] = fopen("file1.txt", "w");
for (int i = 0; i < 10000; i++) {
fprintf(file[0], "%ld\n", result[0][i]);
fprintf(file[1], "%ld\n", result[1][i]);
}
fclose(file[0]);
fclose(file[1]);
}
```
但是第一次測的時候發現 `memchr` 的時間異常的短，於是使用 gdb 去看呼叫 `memchr` 的時候發生了什麼事。
對於 `memchr_opt` 的呼叫很正常：
```asm
► 0x55555555547f <test+239> call memchr_opt <memchr_opt>
rdi: 0x555555558040 (str) ◂— 0x101010101010102
rsi: 2
rdx: 1
```
但是 `memchr` 的部份會發現怎麼什麼都沒有阿：
```asm
0x5555555553f2 <test+98> call cpucycles <cpucycles>
0x5555555553f7 <test+103> mov qword ptr [rbp - 0x30], rax
0x5555555553fb <test+107> call cpucycles <cpucycles>
```
然後如果我們把 `memchr` 改個名字，變成 `memchr_original` 的話，那又正常了：
```asm
► 0x555555555415 <test+133> call memchr_orginal <memchr_orginal>
rdi: 0x555555558040 (str) ◂— 0x101010101010102
rsi: 2
rdx: 1
```
以下去進行實驗：
首先，我在這個程式碼中不宣告 `memchr`，會發現我還是可以呼叫 `memchr`，因為 libc 中有提供 `memchr`。
於是我們單獨去呼叫 `memchr` 看看：
```cpp
memset(str, 1, sizeof(str));
str[1000] = 0;
str[5] = 2;
memchr(str, 2, 1000);
```
會發現，它同樣被編譯器最佳化去掉了：
```asm
0x555555555639 <main+28> call memset@plt <memset@plt>
0x55555555563e <main+33> mov byte ptr [rip + 0x2de3], 0 [str+1000] <= 0
0x555555555645 <main+40> mov byte ptr [rip + 0x29f9], 2 [str+5] <= 2
0x55555555564c <main+47> mov eax, 0 EAX => 0
0x555555555651 <main+52> pop rbp
0x555555555652 <main+53> ret
```
接下來我們試著去使用 `memchr` 的回傳值：
```cpp
memset(str, 1, sizeof(str));
str[1000] = 0;
str[5] = 2;
char *a = memchr(str, 2, 1000);
```
會發現，它去呼叫 libc 中的 `memchr` 了：
```cpp
► 0x555555555684 <main+71> call memchr@plt <memchr@plt>
s: 0x555555558040 (str) ◂— 0x101020101010101
c: 2
n: 0x3e8
```
接下來去試一下有差不多性質的函式，`strcmp`，宣告一個自己實作的 `strcmp`：
```cpp
int strcmp(const char *__s1, const char *__s2)
{
return 0;
}
int main()
{
strcmp(str, "yee");
}
```
會發現它也被編譯器最佳化去掉了：
```asm
0x555555555634 <main>: endbr64
0x555555555638 <main+4>: push rbp
0x555555555639 <main+5>: mov rbp,rsp
0x55555555563c <main+8>: mov eax,0x0
=> 0x555555555641 <main+13>: pop rbp
0x555555555642 <main+14>: ret
```
然後去引用一下這個值：
```cpp
int a = strcmp(str, "yee");
```
發現它去呼叫 libc 中的 `strcmp` 了：
```asm
► 0x555555555654 <main+32> call strcmp <strcmp>
s1: 0x555555558040 (str) ◂— 0
s2: 0x55555555601f ◂— 0x31b010000656579 /* 'yee' */
```
所以，在這裡我們可以歸納一個結論（算是猜測，因為我沒有試過所有的函式，不過這在編譯器實作考量上是個合理的決定），對於在 libc 中存在的函式，如果這個函式只會經由回傳值影響到外部的狀態的話，當我沒有使用這個函式的回傳值，這個函式呼叫會被忽略。然後如果是名稱和這個函式一樣的同樣會被忽略（我想這是因為它被規定必須要提供這樣的界面和達成特定的功能，所以就算去進行重載也還是要符合這樣的規範）。
然後，我把函數名稱改成 `memchr_original` 之後，終於能進行實驗了，會發現 `memchr_opt` 確實比較快，以下是字串中特定字元出現的位置和 CPU cycle 的圖：
### 測驗 3
- `AAAA`：`ENV_RUNNABLE`
- `BBBB`：`attempts + 1`
- `CCCC`：`coro_shedule`
- `DDDD`：`yield`
接下來解釋一下他的運作原理：
:::info
這下面有些呼叫不是真正的函式呼叫，只是他的 context 中紀錄的它所要執行的地址被設定為某個函式的開頭，然後利用 `setcontext` 將 context 設為目標 context。只是這裡為了簡潔語言表達，而同樣使用呼叫這個詞彙。
:::
首先在 `main` 裡面呼叫了 `enable_preemption` 和 `init_threads`。
`enable_preemption` 就是設定一個 `timer`，會定時的發出一個訊號，接收到這個訊號的時候會呼叫 `preempt`，這個 `preempt` 會呼叫 `coro_yield`，並且在裡面會把現在的 context 存到 `envs[curenv].state` 裡面，並且進入 `coro_schedule` 進行排程。
`init_threads` 會輸入 `coro_main`，代表將它作為起始的函式（在使用這個排程器的程式碼中會實作它）。在裡面做的事情首先是設定 `exiter` 這個 `ucontext_t`，讓它成為一個正要呼叫 `coro_exit` 的 context（`coro_exit` 裡面會把這個進程的狀態設為 `ENV_UNUSED` 並進入 `coro_schedule`）。接下來是呼叫 `coro_create` 來創建一個正要呼叫 `entry` 的 context。並且設定讓他在退出的時候，會把 context 設為 `exiter`，也就是去呼叫 `coro_exit`。最後，它會把 context 設為第 0 個進程的 context，也就是去呼叫 `coro_main`。
接下來，去分類討論一下各個元件：
- `coro_schedule`：
它會環狀的找到下一個狀態是 `ENV_RUNNABLE` 的進程，並且進行 `setcontext`。
- `coro_send` 和 `coro_recv`：
引入了一個 `ENV_WAITING` 的狀態，代表正在等待別人傳送東西，在 `coro_recv` 中會將狀態設定為這個，並且呼叫 `coro_yeild`，直到有人對它進行 `coro_send`。然後 `coro_send` 會一直 `coro_yield` 直到目標進程的狀態變成 `ENV_WAITING`，然後設定數值完後將對方變為 `ENV_RUNNABLE`，對方就會醒來接收訊息（它之後會被排程器叫到）。
## Q4
### 測驗 1
```cpp
uint32_t crc32_naive(uint32_t crc, uint8_t v)
{
crc ^= v;
for (int bit = 0; bit < 8; bit++) {
if (crc & 1)
crc = (crc >> 1) ^ UINT32_C(0x82f63b78);
else
crc = (crc >> 1);
}
return crc;
}
```
這個程式會檢查每個位元是不是 1，如果是的話就會進行 `^ UINT32_C(0x82f63b78)`，然後一直向右移。注意到 `0x82f63b78` 是 8 的倍數，所以如果以 4 個為一單位去看的話最低的 4 個位元是不會被污染的（最低未一開使用掉了，第一次的 `^` 會與右移一次的去做操作，而最低的 3 位不會被碰到）。這樣的話，一個 4 位元的數字對應到去進行 `^` 的數字是固定的，所以可以建一個長度為 16 的表，這一題就是在做這件事情：
```cpp
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;
}
```
根據前面的敘述，因為最低的 4 位不會被改變，所以一個原始值會一一對應出一個需要去進行 `^` 操作的數字。既然證明唯一了，那只要進行窮舉就好了。
這裡稍做修改，讓這個函式以 4 個為單位去做操作，窮舉出要進行 `^` 的值是多少：
```cpp
#include <stdio.h>
#include <stdint.h>
uint32_t f(uint32_t crc, uint8_t v)
{
crc ^= v;
for (int bit = 0; bit < 4; bit++) {
if (crc & 1)
crc = (crc >> 1) ^ UINT32_C(0x82f63b78);
else
crc = (crc >> 1);
}
return crc;
}
int main()
{
for (int i = 0; i < 16; i++) {
printf("0x%x, ", f(i, 0) ^ i);
}
}
```
輸出的就是我們要的陣列：
```
0x0, 0x105ec76e, 0x20bd8edc, 0x30e349b2, 0x417b1db8, 0x5125dad6, 0x61c69364, 0x7198540a, 0x82f63b70, 0x92a8fc1e, 0xa24bb5ac, 0xb21572c2, 0xc38d26c8, 0xd3d3e1a6, 0xe330a814, 0xf36e6f7a,
```
:::danger
不要列出參考題解，專注題目本身
:::
Sign in with Wallet
Connect another wallet