# 2018q3 Homework3 (review)
`contributed by <0xff07>`
# Week 2 測驗 `8`
以下程式碼改寫自 Linux 核心原始程式碼，請對照註解 (預期功能)，指出實作上的問題，假設輸入 `value` 不會超過 32-bit。
```C
/*
* Convert a signed n-bit integer to signed 32-bit integer.
* Common cases are done through the compiler,
* the screwed things has to be done by hand.
*/
static int32_t snto32(uint32_t value, unsigned n) {
switch (n) {
case 8: return ((int8_t) value);
case 16: return ((int16_t) value);
case 32: return ((int32_t) value);
}
return value & (1 << (n - 1)) ? value | (-1 << n) : value;
}
```
該段程式位於 `linux/drivers/hid/hid-core.c` 當中
可以在 [git log](https://github.com/torvalds/linux/commit/08585e43d22802666a466af1ca5795085e74d60d) 中找到下列敘述：
> HID: core: don't use negative operands when shift
>
> The recent C standard in 6.5.7 paragraph 4 defines that operands for
bitwise shift operators should be non-negative, otherwise it's an
undefined behaviour.
引述該章節：
> The result of `E1 << E2` is `E1` left-shifted `E2` bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is $E_1 × 2^{E_2}$, reduced modulo one more than the maximum value representable in the result type. If `E1` has a signed type and nonnegative value, and $E_1 × 2^{E_2}$ is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
可以發現將負數進行左移是未定義行為。
觀察一下程式註解預期的功能，可以發現該程式本質上在進行 sign extension：若第 n 個位元是 1，則要把最高位(也就是第 n)以上的位元通通設為 1; 反之則設為 0。若輸出的是 32 位元整數，則將 `-1 << n` 改成 `0xFFFFFFFF << n`，或是 commit 中的 `~0U << n` 即可。
在 CVE 中[查到](https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2017-8326)一個類似的問題。修改該程式的 [commit](https://github.com/jsummers/imageworsener/commit/a00183107d4b84bc8a714290e824ca9c68dac738)也幾乎如出一徹。
:::success
延伸問題:
1. 參照 Linux 核心原始程式碼 (以及 git log，探討對應的修正;
2. 在 [Common Vulnerabilities and Exposure](https://cve.mitre.org/) (CVE) 找出類似的安全弱點，並且進行案例分析;
:::
---
# Week 3 測驗 `2`
考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:
```C
int main() {
union { int a; char b;
} c = { .a = K1 };
return c.b == K2;
}
```
補完上述程式碼。
==作答區==
K1 = ?
* `(a)` 0
* `(b)` 1
* `(c)` -1
* `(d)` 254
K2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 254
在研讀整數相關部分的規範時，第 6.2.6.2 第 2 段提到：
> For signed integer types, the bits of the object representation shall be divided into three groups: value bits, padding bits, and the sign bit. There need not be any padding bits; there shall be exactly one sign bit.
>
> Each bit that is a value bit shall have the same value as the same bit in the object representation of the corresponding unsigned type (if there are M value bits in the signed type and N in the unsigned type, then M ≤ N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, the value shall be modified in one of the following ways:
>
> — the corresponding value with sign bit 0 is negated (sign and magnitude);
>
> — the sign bit has the value −(2N ) (two’s complement);
>
> — the sign bit has the value −(2N − 1) (ones’ complement).
>
> Which of these applies is implementation-defined,
這表示 C99 沒有強制規定要用 2's complement 嗎？
:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::
---
# Week 3 測驗 `3`
以下程式碼計算 parity bit:
```C
#include <stdint.h>
int parity(uint32_t x)
x ^= x >> 1;
x ^= x >> 2;
x = (x & 0x11111111U) * 0x11111111U;
return (x >> P) & 1;
}
```
補完程式碼
==作答區==
P = ?
* `(a)` 32
* `(b)` 31
* `(c)` 30
* `(d)` 29
* `(e)` 28
* `(f)` 27
* `(g)` 26
* `(h)` 25
* `(i)` 24
答案為 (e)。
首先可以證明：把所有位元 XOR 起來，若位元中有奇數個 1，則結果將是 1; 反之若有偶數個 1，則結果將為 0。證明可以使用數學歸納法：
`base case`：只有一個位元 (0 或 1) 顯然對。
`induction`：由 XOR 的定義立刻得到成立。列表討論如下：
|第 n 位 |前 n - 1 位計算結果 1，且有奇數個 1|前 n - 1 位計算結果 0 ，且有偶數個 1|
|---|---|---|
|1|奇數 + 1 = 偶數，且 1 ^ 1 = 0|偶數 + 1 = 奇數，且 1 ^ 0 = 1|
|0|奇數 + 0 = 奇數，且 0 ^ 1 = 1|偶數 + 0 = 偶數，且 0 ^ 0 = 0|
因此，解決這個問題的其中一個方向，是找出所有位元的 XOR。而該程式正**計算了所有位元進行 XOR 的結果**。說明如下：
假定(用類似 verilog 的敘述方式)：
$$
x[31:0]
$$
是原先希望計算 parity bit 的數。首先經過：
```c
x ^= x >> 1;
```
假定這時候的結果令為 $x_2[31:0]$，則有：
$$
\begin{align}
x_1[0] &= x[0] \oplus x[1] \newline
x_1[1] &= x[1] \oplus x[2] \newline
x_1[2] &= x[2] \oplus x[3] \newline
x_1[3] &= x[3] \oplus x[4] \newline
\dots\newline
x_1[30] &= x[30] \oplus x[31] \newline
\end{align}
$$
類似地，進行到下一個敘述：
```c
x ^= x >> 2;
```
假定這時候的運算結果為 $x_3$，則類似地，有：
$$
\begin{align}
x_2[0] &= x_1[0] \oplus x_1[2] = x[0] \oplus x[1] \oplus x[2] \oplus x[3]\newline
x_2[4] &= x_1[4] \oplus x_1[6] = x[4] \oplus x[5] \oplus x[6] \oplus x[7]\newline
\dots\newline
x_2[28] &= x_1[28] \oplus x_1[30] = x[28] \oplus x[29] \oplus x[30] \oplus x[31]\newline
\end{align}
$$
也就是一般地說：
$$
x_2[4i] = x[4i]\oplus x[4i + 1] \oplus x[4i + 2] \oplus x[4i + 3]
$$
因此，只要再計算：
$$
\bigoplus_{i = 0}^{7} x_2[4i]
$$
即可。接下來觀察：
```c
x = (x & 0x11111111U) * 0x11111111U;
```
當中 `x = (x & 0x11111111U)` 把上述 $x_2[4i]$ 取出來，接著乘上 `0x0x11111111U`，轉成二進位觀察為 `0001...00010001`。這個步驟可以視為：
```c
(x) + (x << 4) + (x << 8) + (x << 12) + ... + (x << 28);
```
因為是加法，所以套用加法器的原理，第 28 個位元就是 $x_2[28]$, $x_2[24]$ ... $x_2[0]$ 進行 XOR 的結果。由前面對 $x_2[4i]$ 的觀察可知，這樣做之後，第 28 位元其實也就是將所有位元 XOR 起來的結果。因此將第 28 位元取出來即可。
另外一個思考方式是在取出 $x_2[4i]$ 之後，計算：
$$
\sum_{i = 1}^{7}x_2[i]
$$
再看結果是奇數或是偶數（取第一個位元）就可以了。
因此在進行：
```c
(x) + (x << 4) + (x << 8) + (x << 12) + ... + (x << 28);
```
之後，最左邊 [31:28] 形成的整數之奇偶，或說第 28 個位元是 1 或是 0，就是 parity bit。
:::success
延伸問題: 解釋原理，並且提出更快的實作機制 (提示: 透過 SIMD)
:::
Sign in with Wallet
Connect another wallet