---
# System prepended metadata

title: 2025q1 Homework4 (quiz3+4)
tags: [linux2025]

---

# 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`
