---
# System prepended metadata

title: 2020q3 Homework2 (quiz2)
tags: [sysprog-2020]

---

# 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}
$