# 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 語言規格書的章節),以及==進行相關實驗==。
---
### `測驗一`
```cpp=
#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),程式碼改寫如下:
```cpp=
#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。
```cpp=
memcpy(&payload, str + i, 8);
```
* 是由 `str + i` 指向地址為起始地址的連續 8 個位元組的資料,再複製到以 `payload` 指向地址為起始地址的空間內。
---
### `測驗二`
開發解析器 (parser) 時,常會將十六進位表示的字串 (hexadecimal string) 轉為數值,例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:
```cpp=
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`
---
### `測驗三`
```cpp=
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`
---
### `測驗四`
```cpp=
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` 。
---
### `測驗五`
```cpp=
#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`
---
### `測驗六`
```cpp=
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`