# 2025q1 Homework4 (quiz3+4)
contributed by < `yy214123` >
## [2025 q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz3)
### 測驗 `1`
ceiling division：
任何的整數除法都能如下表示：
$n=dq+r$ $,where:0\leq r<d$
* case 1（$r=0$)：
$n = dq$
$n/d = q$
$\lceil n/d \rceil=\lceil q \rceil=q$
* case 2（$r\neq0$)：
$n = dq+r$
$n/d = q+r/d$
$\lceil n/d \rceil=\lceil q \rceil+\lceil r/d \rceil=q+1$
顯然可以用一個 if 判斷式去進行決策，但這以組合語言的角度會多一次分支指令，會是額外的成本。
可以透過加減乘除來達成 ceiling division：
即 $\lceil n/d \rceil＝\lfloor(n+d-1)/d \rfloor$
這東西以往都直接背起來了，但我們還是可以證明一下他們等價，這邊我使用矛盾證法：
假設存在 $n,d$ 使 $\lceil n/d \rceil \neq（n+d-1）/d$
設 $n$ 可被 $d$ 整除
> `左式`
則 $\lceil \dfrac{n}{d} \rceil = q$
`右式`
又 $\dfrac{n+d-1}{d} = \dfrac{dq+d-1}{d} = q + \dfrac{d-1}{d}$
由於 $\dfrac{d-1}{d} > 0$
則 $\lfloor \dfrac{n+d-1}{d} \rfloor = q$
**矛盾！**
設 $n$ 不可被 $d$ 整除
> `左式`
則 $\lceil \dfrac{n}{d} \rceil = q + 1$
`右式`
又 $\dfrac{n+d-1}{d} = \dfrac{dq+r+d-1}{d} = q + \dfrac{r+d-1}{d}$
由於 $1 \le r \le d - 1$
則 $r + d - 1 \ge 1 + d - 1 = d$
則 $r + d - 1 \le d - 1 + d - 1 = 2d - 2 < 2d$
所以 $1 \le \dfrac{r+d-1}{d} < 2$
所以 $\lfloor \dfrac{n+d-1}{d} \rfloor = q + 1$
矛盾！
均矛盾故原式成立。
### 測驗 `2`
### 測驗 `3`
## [2025 q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2025-quiz4)
### 測驗 `1`
在 CRC 中有兩個角色：
* 除數：對應不同長度，會有不同的定義，以這個測驗來說 CRC32C 使用的是 `0x1EDC6F41`。
* 被除數：欲驗證的資料。
兩者進行除法運算的餘數，就會是對應的校驗碼。
XOR 的真值表如下：
| 運算 | 結果 |
| -------- | -------- |
| 0 xor 0 | 0 |
| 0 xor 1 | 1 |
| 1 xor 0 | 1 |
| 1 xor 1 | 0 |
> 若奇數個 1 ，則結果為 1。反之。
使用這個特性，可以透過 xor 來達到多項式取餘數的運算，範例如下：
* 被除數：1101011011
* 除數：10011
```shell
1101011011
10011 (xor)
---------
0100111011
```
拿上次運算的結果再跟除數做一次 xor，除數要對齊 MSB set bit：
```shell
100111011
10011 (xor)
---------
000001011
```
此時剩下 `1011`，其位元數小於除數的 `10011` 所以這就是結果。
可以將被除數與除數轉為對應的多項式來驗證：
* 被除數：1101011011 ＝ $x^9 + x^8 + x^6 + x^4 + x^3 + x + 1$
* 除數：10011 ＝ $x^4 + x + 1$
商為：$x^5+x^4 −2x$
餘為：$x^3+2x^2+3x+1$
而 CRC 是基於 Gf(2) 這個有限域，直白一點來說，可以將各項次的係數 mod 2：
商為：$x^5+x^4 −x$
餘為：$x^3+1x+1$
在 xor 運算中，只會求算出餘數，先前提到的 1011 其相當於 $1*x^3+0*x^2+1*x+1*1$，即為 $x^3+1x+1$。
那也可以都將數字反轉來進行 xor 運算，以先前的例子來說：
```shell
1101011011
10011 (xor)
---------
0100111011
```
實際上要將 10011 後面再補 5 個 0：
```shell
1101011011
1001100000(xor)
---------
0100111011
```
這在運算上會有多餘的計算成本，因為每次要補幾個 0 是不固定的，若反轉運算：
```shell
1101101011
11001(xor)
---------
1101110010
```
本身 `11001` 前面的 0 電腦會為我們補上。剛剛下一步要運算時要去找 MSB set bit ，現在變成找 LSB set bit，我們可以將其與 1 進行 xor，來判斷說是否需要位移，例如 `1101110010`，其 LSB set bit 在由右往左第 `2` 個 bit，此時將其右移一次就能使其移動到第 `1` 個 bit，即可進行下一步操作。
上述的流程呼應了本測驗的此程式碼片段：
```c
for (int bit = 0; bit < 8; bit++)
crc = (crc & 1) ? ((crc >> 1) ^ UINT32_C(0x82f63b78)) : (crc >> 1);
```
將這個迴圈展開會像這樣：
```c
if (bit0 == 1) crc = (crc >> 1) ^ POLY
else crc = (crc >> 1)
if (bit1 == 1) crc = (crc >> 1) ^ (POLY >> 1)
else crc = (crc >> 1)
...
if (bit7 == 1) crc = (crc >> 1) ^ (POLY >> 7)
else crc = (crc >> 1)
```
可如下分析低位元 8 bits：
$b_7\,b_6\,b_5\,b_4\,b_3\,b_2\,b_1\,b_0$
檢查 $b_0$
> 若 $b_0 = 0$ 則 $crc=(crc>>1)\oplus (0x82f63b78)$
> 若 $b_0 = 1$ 則 $crc=crc>>1$
檢查 $b_1$
> 若 $b_1 = 0$ 則 $crc=(crc>>1)\oplus (0x82f63b78)$
> 若 $b_1 = 1$ 則 $crc=crc>>1$
> 其中 $crc$ 是檢查 $b_0$ 後移動過的 $crc$。
依此類推直到檢查到 $b_7$，所以可以發現其實這是一顆二元樹，從 root 開始代表檢查 $b_0$，將左子都當成是 0，右子是 1，第二層開始是檢查 $b_1$，直到最後會有 256 個樹葉。
這 256 個樹葉就分別對應 $b_7\,b_6\,b_5\,b_4\,b_3\,b_2\,b_1\,b_0$ 的所有可能，按照這個性質可以用查表的方式來避免多次迭代及分支的成本。
在看測驗提供的 [util/crc32c.c](https://github.com/qemu/qemu/blob/907209e3111dd62a553a19319b422ff8aba5b9c0/util/crc32c.c#L40)時，我發現其中第 4 行的註解有誤，應該要改成：
```diff
/*
* Castagnoli CRC32C Checksum Algorithm
*
- * Polynomial: 0x11EDC6F41
+ * Polynomial: 0x1EDC6F41
*
* Castagnoli93: Guy Castagnoli and Stefan Braeuer and Martin Herrman
* "Optimization of Cyclic Redundancy-Check Codes with 24
* and 32 Parity Bits",IEEE Transactions on Communication,
* Volume 41, Number 6, June 1993
*
* Copyright (c) 2013 Red Hat, Inc.,
*
* Authors:
* Jeff Cody <jcody@redhat.com>
*
* Based on the Linux kernel cryptographic crc32c module,
*
* Copyright (c) 2004 Cisco Systems, Inc.
* Copyright (c) 2008 Herbert Xu <herbert@gondor.apana.org.au>
*
* This program is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License as published by the Free
* Software Foundation; either version 2 of the License, or (at your option)
* any later version.
*
*/
```
如此才與下方 table 的註解一致：
```c
/*
* This is the CRC-32C table
* Generated with:
* width = 32 bits
* poly = 0x1EDC6F41
* reflect input bytes = true
* reflect output bytes = true
*/
```
### 測驗 `2`
### 測驗 `3`
Sign in with Wallet
Connect another wallet