# 2020q3 Homework2 (quiz2)
contributed by < `chi-ming5566` >
> [測驗題](https://hackmd.io/@sysprog/2020-quiz2)
> ---

---
## 作業要求
* 重新回答[第 2 周測驗題](https://hackmd.io/@sysprog/2020-quiz2)，連同附帶的「延伸問題」。
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb)的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及==進行相關實驗==。

---

### `測驗一`

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

此函式是用來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元。

但逐一字元比對的效率低，在 64 位元的架構下，所以嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:

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

:::success
延伸問題:
1.解釋上述程式的運作原理，特別是為何用到 memcpy 呢？
2.將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對。
提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對。
:::

* `payload` 會去抓 `str` 字串陣列中前 8 位與 `0x80` 進行 & 運算後需等於 0，而 `payload` 內有 8 個 bytes 對應8個字元，因此每個字元對應一組`0x80`，故 MMM = 0x8080808080808080。

memcpy(&payload, str + i, 8);

* 是由 `str + i` 指向地址為起始地址的連續 8 個位元組的資料，再複製到以 `payload` 指向地址為起始地址的空間內。

---

### `測驗二`

開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

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

已知 `in` 一定隸屬於 ``'0'``, ``'1'``, ``'2'``, …, ``'9'`` 及 ``'a'``, ``'b'``, ``'c'``, …, ``'f'`` (小寫) 及 ``'A'``, ``'B'``, ``'C'``, …, ``'F'`` (大寫) 這些字元。預期 `hexchar2val('F') ` 和 `hexchar2val('f')` 回傳 15，且 `hexchar2val('0')` 回傳 0，其他輸入都有對應的數值。

以下摘自 ASCII 表格

* ``'0'``, ``'1'``, ``'2'``, …, ``'9'`` 對應到 `0x30`, `0x31`, `0x32`, … `0x39`
* ``'a'``, ``'b'``, ``'c'``, …, ``'f'`` (小寫) 對應到 `0x61`, `0x62`, `0x63`, …, `0x66`
* ``'A'``, ``'B'``, ``'C'``, …, ``'F'`` 對應到 `0x41`, `0x42`, `0x43`, …, `0x46`

:::success
延伸問題:
1.解釋上述程式的運作原理;
2.將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
:::

* 已知 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15。
* `F` 對應`0x46`, `f` 對應 `0x66` 。
* 所以 `0x46` 轉換成二進位就是 `0100 0110`，而 `0x66` 則是 `0110 0110`。

因為`return (in + shift) & 0xf` ，所以 `F` 與 `f` 輸入的 `in + shift` ==最低位的 4 個 bits== 必為 `1111`，轉換成十進位就是 15 。

| Character | Binary |
| --- | --- |
| F | 0==1==00 0110|
| f | 0==1==10 0110|
| 0x40 | 0==1==00 0000|

由此可知兩者在最高位 4 個 bits 只有 1 個 bit 相同，於是MASK = ? `0x40` 。

| Character | Binary |
| --- | --- |
| 0x40 | 0==1==00 0000|
| letter| 0==1==00 0000|
| F | 0==1==00 0110|
| f | 0==1==10 0110|
| in+shift| XXXX 1111|
根據 `MASK = 0x40` 的結果我們可以知道 `letter` 在兩種輸入情況下皆等於 `0100 0000`，又`in + shift` 最低位的 4 個 bits 等於 `1111`，於是讓 `letter` 分別做兩次右移補滿 `F` 和 `f` 的最低位 `0110` ， 於是
AAA = `3`
BBB = `6`

---

### `測驗三`

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;
}

其中 __uint128_t 是 GCC extension，用以表示 128 位元的無號數值。
預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。

請補完程式碼。

XXX = `(f) 0xFFFFFFFFFFFFFFFF`

---

### `測驗四`

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

以 `D = 3` 來說，`divisible(7)` 要得到 `0` (即 `7` 無法被 `3` 整除)，`divisible(87)` 要得到 `1` (即白痴是三的倍數)

請補完程式碼。

令 `n=3a, 3a+1, 3a+2` (a為非負整數)
若 `a=1` ， 因為 `3M > 0xFFFFFFFFFFFFFFFF` (overflow) 所以 `3M = 0x0000000000000002`
求三者最小值:
* 3aM = 2a
* (3a+1)M = 3aM + M = 2a+M
* (3a+2)M = 3aM + 2M = 2a + 2M
`(c) M - 1` 符合要求，所以YYY = `(c) M - 1` 。

---

### `測驗五`

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)

/* vectorized implementation for in-place strlower */
void strlower_vector(char *s, size_t n)
{
    size_t k = n / 8;
    for (size_t i = 0; i < k; i++, s += 8) {
        uint64_t *chunk = (uint64_t *) s;
        if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}

`PACKED_BYTE` 的作用是將輸入 LSB 的 8 bits 擷取後重複擴充至 64 個 bits，例如: `PACKED_BYTE(0xAB)` 會得到 0xABABABABABABABAB，如同第一題以`0x80`對 ASCII 範圍內的字元進行檢測，因此 VV1 = `(e) 0x80`

再來看到`uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2` ，而
* ('a' ^ ' ') // 得到 'A'
* ('A' ^ ' ') // 得到 'a'

此外`0x80` >> 2 = `' '`可以知道 `A ^ Z` 的數值可以決定這 8 個字元哪一個要做大小寫轉換
因此只有字元為大寫時，`A ^ Z`的 MSB 才能為 1
`(128 - 'A' + char + VV2) ^ (128 - 'Z' + char + VV3)`
| char | Decimal | Binary |
| ---- | ------- | ------ |
| A | 65 |0100 0001|
| Z | 90 |0101 1010|

由此可得知當
`char >= 'A'` 時 `uint64_t A` 的 MSB 為 1
`char >= 'Z'` 時 `uint64_t Z` 的 MSB 為 1
但當 `char = Z` 時為了使 `A ^ Z` 的 MSB 為 1 還需額外減 1
所以
VV2 = `(b) 0`
VV3 = `(a) (-1)`
VV4 = `(e) 0x80`

---

### `測驗六`

int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= KKK;
        higher ^= nums[i];
        higher &= JJJ;
    }
    return lower;
} 

首先建一個真值表:

| higher | lower | input | higher_output | lower_output |
| ------ | ----- | ----- | ------ | ------ |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |

$lower\_output =
\overline{input} \times \overline{higher} \times lower +
input \times \overline{higher} \times \overline{lower}
=\overline{higer} \times input \oplus lower$

$higher\_output =
\overline{input} \times higher \times \overline{lower} +
input \times \overline{higher} \times lower$

但題解中 `higer` 計算並未使用到前次 `lower` 的狀態，因此修改真值表，
而這次就嘗試使用 `lower_output` 計算 `higher_output`。

| higher | lower(lower_output) | input | higher_output |
| ------ | ----- | ----- | ------ |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 |

$higher\_output =
\overline{input} \times higher \times \overline{lower} +
input \times \overline{higher} \times \overline{lower}
=\overline{lower} \times input \oplus higher$

因此改用`lower`計算`higher`，得到
`KKK = ~higher`
`JJJ = ~lower`