# 2020q3 Homework2 (quiz2)
contributed by < `jonec76` >
###### tags: `sysprog-2020`
> [作業說明](https://hackmd.io/@sysprog/B1zAbkAEP)
> [題目](https://hackmd.io/@sysprog/2020-quiz2)
## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```
## 參考解答
MMM = 0x8080808080808080
MASK = 0x40
AAA = 3
BBB = 6
XXX = 0xFFFFFFFFFFFFFFFF
YYY = M - 1
VV2 = 0
VV3 = -1
VV4 = 0x80
## 作業
- 重新回答 [第 2 周測驗題](https://hackmd.io/@sysprog/2020-quiz2)，連同附帶的「延伸問題」。
- 將你的共筆加到 [2020q3 Homework2 (作業區)](https://hackmd.io/@sysprog/2020-homework2)
### Q1
- 分析提示程式碼
先從提示程式碼去思考加入 `if (str[i] & 0x80)` 的用意。此段程式碼 `is_ascii` 是為了判斷字串裡是否全都是 ascii code，判斷方法是檢測每個 char 對應到的 ascii 值是否小於 128。1 個 char 佔了 1byte，也就是說最大值只能存到 255，超過就是 overflow。
當 str[i] 是介於 128~255 時，就是 extended ascii。跟 `0x80` 做完 `&` 之後如果為 1，表示超過 127，此時則要回傳 `false` 表示該記憶體空間包含了非 ascii 的值。
- 解題想法
接著，看到題目需要改成一次比對 64bit (8 bytes)的資料，但提示程式碼只能比對 1 byte。這時其實只要改變比對的 bitmask 即可。也就是說，對於 `0x80` 做 8 次的比對，相當於將目前指向的後 8 個字元依序排列後，對 `0x8080808080808080` 做比對。
以表格來講，假如一個字串 "sysq3nice" 執行 `memcpy(&payload, str + i, 8);` 後，因為電腦是 little endian 的讀法，所以會像下面的表格
|index: |7|6|5|4|3|2|1|0|
|-----|-----|----|----|----|----|----|----|----|
|char:|c|i|n|3|q|s|y|s|
接著再和新的 bitmask 做 `&` 運算
|index: |7|6|5|4|3|2|1|0|
|-----|-----|----|----|----|----|----|----|----|
|char:|c|i|n|3|q|s|y|s|
|& op:|127|127|127|127|127|127|127|127|
當運算完之後，若這 8 個 bytes 有其中任何一個值大於 0，就表示這塊記憶體空間有 non-ascii 的值存在。
#### 補充筆記
- 如何得知自己的電腦是 little/big endian 呢？參考了 [how-can-i-find-endian-ness](https://stackoverflow.com/questions/8571089/how-can-i-find-endian-ness-of-my-pc-programmatically-using-c) 中看到以下的程式碼
```c=1
int num = 1;
if (*(char *)&num == 1)
printf("Little-Endian\n");
else
printf("Big-Endian\n");
```
先看 `(char *)&num`，每個 `int` 是 4 bytes，而當 `num` 為 1 時，little endian 會將這個 1 存在最低位的 byte，也就是 `(char *)&num`。如果是 big endian 的話會將 1 存在最高 byte 的位置，也就是 `(char *)&num+3` 的位置。
所以當取出最低位 byte `*(char *)&num` 時，如果是 1 就表示是 little endian。
另外，根據上述的方法嘗試做了下方的測驗
```c=1
int num = 1, b=2;
*((char *)&num+4) = 5;
printf("%d\n", b); // 5
```
更改 `num` 往後算第 5 個 byte 時，能夠更改到宣告在 `num` 之後的變數。
### Q2
```c=1
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0xf;
}
```
- 思考方向
1. 第一個是 'A' 和 'a' 的輸出要相同
- 第 1 個想法可以觀察 `A` 跟 `a` 有何差別，`A` 是 `0x41 => 0100 0001`，`a` 是 `0x61 => 0110 0001`，也就是要想辦法忽略第 6 個 bit。
2. `in` 不是英文，就是數字。
- 第 2 個想法是要分辨出英文跟數字，從變數名稱 letter 來看就可知道 MASK 應該要做到這件事，只要知道第 7 個 bit 是 0 或者 1 就可分辨，所以 MASK 應該填入 `0100 0000 => 0x40`。
- 解題想法
AAA 跟 BBB 當時寫的時候湊很久，只能透過下面的二進位數來觀察
|hex: |0011 0001|0110 0001|0100 0001|
|---|---|---|---|
|to val:|0000 0001|0000 1010|0000 1010|
英文的輸出值都是 10 以上，透過觀察可以知道第 4 個 bit 一定為 1，數字的輸出都是 10 以下，可知道第 4 個 bit 為 0。那分辨英文跟數字的 bit 如前面第 (2) 點推敲是第 7 個 bit。於是在 `AAA` 可以填入 3，表示將第 7 個 bit 直接挪到第 4 個 bit。
另外，第 (1) 點的想法是忽略第 6 個 bit，但是沒有類似的選項。於是當時先試著右移 6 bits，發現剛好能夠將答案湊出來，既符合轉換數字的結果，也剛好能算出轉換英文。
### Q3
- jemalloc 裡頭的快速乘法原理
在 [div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 裡頭說到以下數學式
$\dfrac{n}{d}$ ＝ $\lfloor{(
{\dfrac{2^k+r}{d}}\cdot{\dfrac{n}{2^k}}
)}\rfloor$ , $where~~r=(-2^k)~mod~d$
展開後可以得到 $\dfrac{n}{d}$＝$\lfloor{\dfrac{n}{d}}+
(\dfrac{r}{d})\cdot
(\dfrac{n}{2^k})
\rfloor$。
由於此式子左右兩邊需要成立
所以 $(\dfrac{r}{d})\cdot
(\dfrac{n}{2^k})< 1$ 必須成立才行，
又知道 $r=(-2^k)~mod~d$，表示 $\dfrac{r}{d} < 1$ 成立。
接著，如何保證 $(\dfrac{n}{2^k}) < 1$ 呢？
在 div.c 裡頭可以看到 `two_to_k = ((uint64_t)1 << 32)`，這裡的 `1<<32` 就是為的產生出一個比任何 `uint32_t` 還要大的值。
如此一來， $(\dfrac{n}{2^k}) < 1$ 就成立了。
- 題目問題
```c=1
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))
```
看到 `XXX` 時，直觀認為應該是 `1<<64`，但這個 1 是用在哪呢？此題的數學式推倒應為
$\dfrac{n}{d} = \dfrac{n}{2^{64}}
\cdot
(\dfrac{2^{64}-1}{d} + 1), where~d=3$
展開後可以得到下面式子
$\dfrac{n}{d} = \lfloor\dfrac{n}{2^{64}}
\cdot
(\dfrac{2^{64}}{d} + \dfrac{2}{3})\rfloor$
這邊可以觀察出跟前面的推倒過程是一樣的，可以知道 $(\dfrac{n}{2^{64}}\cdot\dfrac{2}{3}) < 1$ 一定成立。此時看到這個 $\dfrac{2}{3}$ 的分子 $2$，才知道一開始題目的 $+1$ 目的（應該是湊出來的?），是能夠使此項小於 $1$。
### Q4
```c=1
bool divisible(uint32_t n)
{
return n * M <= M - 1/*YYY*/;
}
```
- 題目分析
從 `Q3` 可得到 `M` = $\
(\dfrac{2^{64}-1}{d} + 1)=(\dfrac{2^{64}+2}{3} )$，
接著，從答案回推數學式子
$n$ 的可能性有 $3n', 3n'+1, 3n'+2, where ~n=1,2,...$，
1. $n=3n':$
$3n' * (\dfrac{2^{64}+2}{3} )=n' * (2^{64}+2)$
2. $n=3n'+1:$
($3n'+1) * (\dfrac{2^{64}+2}{3} )=n' * (2^{64}+2) + (\dfrac{2^{64}+2}{3} )$
3. $n=3n'+2:$
($3n'+2) * (\dfrac{2^{64}+2}{3} )=n' * (2^{64}+2) + 2*(\dfrac{2^{64}+2}{3} )$
分析到這會覺得蠻神奇的，明明這些出來的值 "看似" 都比 `M-1` 大，怎麼會有小於的時候呢？
但這邊仔細觀察時，可以先從 UINT64_C($2^{64}-1$) 來看。在 `uint64_t` 的變數中，最大值應為 $2^{64}-1$，那超過會怎麼辦呢？也就是 overflow，$2^{64}$ 其實會得到 0 這個數值。
回到上述的數學推導過程，可以發現當 $n=3n'+1, n=3n'+2$，也就是沒辦法被 3 整除時，所得結果都會多出一項 $r*M, where~r=n\%3, M=(\dfrac{2^{64}+2}{3})$。
這項是此題的關鍵，因為 overflow 的關係，前項的 $n' * (2^{64}+2)$ 可以化減成 $n'*2$。所以無法整除 3 時，都會多出後面那項 $r*M$，換句話說，要整除 3 時都必須小於 $r*M, where~r=1,2$，才可得出此題答案是 $M-1$
### Q5
- 題目分析
```c=1
if (s[j] >= 'A' && s[j] <= 'Z')
s[j] ^= 1 << 5;
```
如果 char 大於 `A` 或小於 `Z`，就表示是個大寫的英文。參考 ascii code 表可以發現，`A` 跟 `a` 差別於第 6 個 bit（可參考上面的 `Q2`）
- 思考方向
```c=1
uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80/*VV4*/)) >> 2;
```
若從這行倒著推測的話，`PACKED_BYTE(0x80)` 就是 `0x8080808080808080` ，`>>2` 剛好會是 `0x2020202020202020`，對應到每個 char 剛好是第 6 個 bit。
`(A ^ Z)` 的功用在哪呢？其實要能夠讓 `PACKED_BYTE(0x80) >> 2` 的關鍵在於，`(A ^ Z) = 0x8080808080808080` 才成立。
```c=1
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' - 1);
```
下圖是以每個 `*chunk` 的 byte 來看，列出所有可能
|range|*chunk[i] < A|A < *chunk[i] < Z|z < *chunk[i] |
|-|-|-|-|
|A 第 8 bit|0|1|1|
|Z 第 8 bit|0|0|1|
可以明顯看到，當 `A < *chunk[i] < Z` 時，做完 `A ^ Z` 後就會得到 `0x8080808080808080`
### Q6
- 思考方向
看完解法後覺得這題蠻神奇的，老師上課時有提示 "兩個相同的數做 XOR 會等於 0"，那三個數呢？
思考方向是使用真值表，將所有可能的狀態都列出來後，可以思考成出現 0,1,2 次，當出現 3 次時可以當作出現 0 次，真值表如下
|high|low|input|output (high bit)|output (low bit)
|-|-|-|-|-|
|0|0|0|0|0|
|0|0|1|0|1|
|0|1|0|0|1|
|0|1|1|1|0|
|1|0|0|1|0|
|1|0|1|0|0|
high/low 記錄著該數值過去出現過幾次，input 記錄著該數值是否是這次讀到的數字。有趣的是，整個 array 中的數值都是共用 lower, higher 變數，對變數做 XOR，難道不會互相影響嗎？
仔細思考後發現，並不會影響，因為要看的是所有的數字。以 1,1,1,2,3,3,3 來看，第 0 個 bit 總共有 6 個 1 ，第 1 個 bit 總共有 7 個 1，依據上述狀態執行後的確能得到 2。
狀態希望是 `0` -> `1` -> `2` 的形式，所以當值為 `3` 時，則要變成 `0`，從真值表能推出下列式子：
\begin{aligned}
lower&=lower\cdot\bar{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\\
&=\bar{higher} \cdot(lower\cdot\bar{input}+\bar{lower}\cdot{input})\\
&=\bar{higher}\cdot(lower\oplus{input})
\end{aligned}
\begin{aligned} higher&=\bar{lower}\cdot{higher}\cdot\bar{input}+\bar{lower}\cdot\bar{higher}\cdot{input}\\
&=\bar{lower} \cdot(higher\cdot\bar{input}+\bar{higher}\cdot{input})\\
&=\bar{lower}\cdot(higher\oplus{input})
\end{aligned}
$
Sign in with Wallet
Connect another wallet