# 2020q3 Homework2 (quiz2)
contributed by < `fennecJ` >

> [2020q3 第 2 週測驗題](https://hackmd.io/@sysprog/2020-quiz2)

## 索引
[TOC]

## 測驗1

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

MMM = ?
* `(a)` `0x0080008000800080`
* `(b)` `0x8000800080008000`
* `(c)` `0x0808080808080808`
* `(d)` `0x8080808080808080`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`

此題答案應選 `(d)` ，這段程式碼的作用為一次驗證 8 個 byte 存的是否皆為 ascii ，因此只要把 0x80 推廣為 0x8080808080808080 即可。
## 測驗2

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

MASK = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`

觀察字母與數字的 ascii code :
最後 return 的數值會 & 0xf ，因此只要看最後 4 位就好 :
| | ascii in binary 的後四位 |
| ----- | ----------- |
| a | 0001 |
| ... | ... |
| f | 0110 |
| A | 0001 |
| ... | ... |
| F | 0110 |
| 0 | 0000 |
| ... | ... |
| 9 | 1001 |
可以發現，數字本身的後四位的值就是我們要輸出的結果，而字母後四位的值則和我們要輸出的結果相差 9 ，因此推測 MASK 的作用在於判斷 in 是數字還是字母，若是字母則要 +9 ，而若是數字則不須加任何數字直接回傳後四位的結果就好。
觀察字母與數字的 ascii code :
| | ascii in binary |
| ----- | ----------- |
| a | 0110 0001 |
| ... | ... |
| f | 0110 0110 |
| A | 0100 0001 |
| ... | ... |
| F | 0100 0110 |
| 0 | 0011 0000 |
| ... | ... |
| 9 | 0011 1001 |
可以發現字母和數字的差別在於第 2 個 bit 是否為 1 ，因此本題應選 `(c)` 。
AAA = ?
* `(a)` `3`
* `(b)` `2`
* `(c)` `1`
* `(d)` `0`
BBB = ?
* `(a)` `7`
* `(b)` `6`
* `(c)` `5`
* `(d)` `4`
考慮兩種情形：
若輸入值為數字，則 letter = 0 ，因此 shift = 0 ，不影響結果，無法判斷 AAA BBB 為何。
若輸入值為字母，則 letter = 0100 0000 ，最後會回傳 (in+shift) & 0xf ，而正如前面提到的，若為字母最後要 +9 才會是我們要的結果，因此shift 應 = 0000 1001 ，要以 letter (0100 0000) 湊出 0000 1001 ， (AAA,BBB) 應為 (3,6) 或 (6,3) ，因此
AAA 的答案為 `(a)` `3` ； BBB的答案為 `(b)` `6`
## 測驗3

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))
/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{   uint64_t quotient = ((__uint128_t) M * n) >> 64;
    return n - quotient * D;
}

XXX = ?
* `(a)` `0x00F000F000F00080`
* `(b)` `0xF000F000F000F000`
* `(c)` `0x0F0F0F0F0F0F0F0F`
* `(d)` `0xF0F0F0F0F0F0F0F0`
* `(e)` `0x8888888888888888`
* `(f)` `0xFFFFFFFFFFFFFFFF`
我們要求的是 $\dfrac{n}{d}$ 的整數部分 ( 也就是 quotient ) ，而題目一開始提示 $\dfrac{n}{d} =n \times \dfrac{\dfrac{2^N}{d}}{2^N}$ ，並說我們可以先估算 $\dfrac{2^N}{d}$ 之後再補上差值。而後看到 `quotient = ((__uint128_t) M * n) >> 64` 我們可以推測 $N = 64$ ，因此此題答案為 `(f)` `0xFFFFFFFFFFFFFFFF` ， $M = \dfrac{2^N-1}{d}+1$ 。
證明 $M = \dfrac{2^N-1}{d}+1$ 為何結果會和 $M = \dfrac{2^N}{d}$ 相同：
以下參考 [Rsysz](https://hackmd.io/@Rsysz/quiz2#3-%E5%BF%AB%E9%80%9F%E9%99%A4%E6%B3%95) ：

$\frac{M \times n}{2 ^ {64}}=\dfrac{(\dfrac{2^{64}-1}{d}+1)\times n}{2^{64}}=\dfrac{n \times 2^{64}}{d \times 2^{64}}-\dfrac{n}{d \times 2^{64}}+\dfrac{n}{2^{64}}\\=\dfrac{n}{d}+\dfrac{n}{2^{64}}(1-\dfrac{1}{d})<\dfrac{n}{d}+\dfrac{n}{2^{64}}$
又$\dfrac{n}{d}$ 的小數部分最大值為$\dfrac{2^{32}-2}{2^{32}-1}$ ，且 $n,d<2^{32}-1$，所以 $\dfrac{n}{2^{64}}<\dfrac{n}{2^{32}}<\dfrac{1}{2^{32}-1}$， $\dfrac{n}{d}$ 的小數部分加上 $\dfrac{n}{2^{64}}$ 也不會進位。因此當 $M = \dfrac{2^N-1}{d}+1$ 時， $quotient$ 的結果會是 $\dfrac{n}{d}$ 的整數部分，而當 $M = \dfrac{2^N}{d}$ 時， $quotient$ 的結果也是 $\dfrac{n}{d}$ 的整數部分，兩者相同。
## 測驗4
判斷是否可整除

bool divisible(uint32_t n)
{
    return n * M <= YYY;
}

YYY = ?
* `(a)` `M+1`
* `(b)` `M`
* `(c)` `M-1`
* `(d)` `(M >> 1)`
* `(e)` `(M << 1)`

若 $n$ 為 $d$ 的倍數，則 $n \times M$ 的結果會進位到需要第 65 個 bit 才能表達因此溢位，最後的結果遠小於 $M$ 。

而若 $n$ 不是 $d$ 的倍數，則我們能令 $n=a+r$ ，其中 $r=n\mod d$ ，則 $n \times M=(a+r)\times M=a\times M+r\times M$ ，其中，由於 $a$ 是 $d$ 的倍數 $a\times M$ 會進位到需要第 65 個 bit 才能表達因此溢位，而由於 $r<d$ 所以 $r\times M$ 不會進位並且幾乎每次都會大於 $M$ ，除了當 $r=1$ 的時候，這時 $r$ 可能會和 $M$ 相等 ( 依 $n,d$ 而定)，因此為了確保 $r\times M$ 總是大於 $M$ ，我們可以在比較大小的時候讓 $M$ 減 1
因此此題選 `(c)` `M-1`
:::info
問題：為何要有等號 ?

return n * M <= M-1;

若 $n*M=M-1$ ，則 $n=\dfrac{M-1}{M}$ ，此時 $n=0$ 仍小於 $M-1$ (因為 $M$ 為 (0xFFFFFFFFFFFFFFFF) 除以 uint32_t 再加 1 的結果，因此 $M$ 恆大於 1 ，既然如此，為何要有等號呢？
:::
## 測驗5
VV1 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
PACKED_BYTE 的作用為將輸入的 b 的最後 8 位複製 8 次之後並回傳。
本題原理和第一題一樣，因此選 `(e)` `0x80`
:::info
問題 : 為何 PACKED_BYTE 的 macro 中要用 0x0101010101010101u 而非 0x0101010101010101 ，有特別的理由嗎?
:::

VV2 = ?
* `(a)` `-1`
* `(b)` `0`
* `(c)` `1`

VV3 = ?
* `(a)` `-1`
* `(b)` `0`
* `(c)` `1`

VV4 = ?
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
這三題只有 VV4 我看得懂：
由於要轉換大小寫，我們可以推測 mask 應為 0010 0000( 重複八次 ) ，而 mask 是 (A^Z)&VV4 右移 2 位的結果，判斷最高位必需為 1 (1000 0000) ，因此本題選 `(e)` `0x80`
而關於 VV2 和 VV3 ，參考 [RinHizakura](https://hackmd.io/@RinHizakura/SJ5NuIANP#%E6%B8%AC%E9%A9%97-5) 的解釋後我才明白， VV2 和 VV3 的用途在於判斷輸入的值是否介於 A~Z 之間，若判斷值介於 A~Z 之間。
其中
* 若 `c + 128 - 'A'` 的第一個 bit 為 1 ，表示 `c + 128 - 'A' >= 128` ，即 `c >= 'A'`
* 若 `c + 128 - 'Z' - 1` 的第一個 bit 為 1 ，表示 `c + 128 - 'Z' - 1 >= 128` 則 `c - 'Z' >= 1` 即 `c > 'Z'` ，反之，若第一個 bit 為 0 ，則表示 `c <= 'Z'`
* 因此若 `'A' <= c <= 'Z'` ，此時 A 和 Z 的最高位恰分別為 (1,0) ，進行 XOR 運算後第一個 bit 會是 1 ，之後 & `0x80` 這個 1 才會被留下並用來進行大小寫轉換。
所以
VV2 應選 `(b)` `0`
VV3 應選 `(a)` `-1`
## 測驗6
看不懂，看了幾個同學的共筆都說可以把它當狀態機，但暫時還不能理解為何可以用 XOR 的效果把他記錄下來。