# 2020q3 Homework2 (quiz2)
contributed by < `Rsysz` >
###### tags: `sysprog`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz2)
## 1. ASCII 編碼判斷
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元
```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;
}
```
其中 `str` 是開頭的記憶體地址，`size` 則是要檢驗的範圍。逐一字元比對的效率低，在 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;
}
```
已知 7 位元編碼的字元隸屬於 ASCII，透過 `uint64_t` 也就是 `long int` `payload` 截取 `str` 字串陣列中前8位進行判斷，如下圖所示，與 `0x80` 進行 `&` 運算後必須等於==0==
而 `payload` 內有 8 個bytes對應8個字元，因此每個字元對應一組 `0x80`
MMM = `0x8080808080808080`
| Hexadecimal | Binary | Decimal |
| ---- | ---- |----|
| 0x80 | 1000 0000 | 128 |
| 0x7F | 0111 1111 | 127 |
:::info
`memcpy` 常見的實做是先檢查 memory address 是否 ==word aligned==，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。
因此同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。
:::
> 還要考慮 MIPS/Arm 架構中，如果硬體無法處理 misalignment，上述程式碼如果沒有 memcpy 這樣事先考慮到 alignment 的處理，會發生什麼事？
> :notes: jserv
ARM 架構中部分CPU“部分支援”非對齊訪問其“單指令”操作支援非對齊，但“群指令”操作(SIMD)則不支援，如 LDM、STM、LDRD、STRD。ARMv5 指令集的CPU(一般是arm9架構)預設不支援非對齊記憶體訪問，ARMv6及以上的CPU預設支援處理大部分的非對齊記憶體地址訪問。
MIPS 架構中硬體不支援對齊訪問，但通過軟體支援，通過核心中對 alignment fault 異常處理流程中進行處理，比如將非對齊的資料訪問，通過多次訪存操作和拼接操作來處理，也可以使用類似 memcpy的方式來處理，當然代價是更嚴重的效能損失。
通常，在出現 alignment fault 時，需要分析定位原因，而不能簡單的通過核心的 fixup 或者忽略，由於 alignment fault 帶來的效能損耗是非常大的因此在很多CPU中，會將此類問題當做一種異常上報，目的就是希望工程師能修正程式碼，提升效能。
而最常見的可能導致 alignment fault 的程式碼編寫方式如:
* 指標轉換：將低位寬型別的指標轉換為高位寬型別的指標
* 使用packed屬性或者編譯選項。這樣的操作會關閉編譯器的自動填充功能，從而使結構體中各個欄位緊湊排列，如果排列時未處理好對齊，則可能導致alignment fault
[參考資料](https://www.itread01.com/content/1544492598.html)
[檢測英文大小寫字母](https://github.com/Rsysz/quiz2/blob/master/test1.c)
## 2. 16進位字串轉換
```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，其他輸入都有對應的數值。
* 已知 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15
* `F` 對應`0x46`, `f` 對應 `0x66`
| Character | Hexadecimal | Binary |
| ---- | -------- | -------- |
| F | 0x46 | 0100 0110 |
| f | 0x66 | 0110 0110 |
| | 0xf | 0000 1111 |
再來看到 `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`
[擴充版本](https://github.com/Rsysz/quiz2/blob/master/test2.c)
## 3. 快速除法
> 不懂就說不懂，不要說「不是很懂」這樣不精準的話，而且你已經不懂，還「僅供參考」什麼？會不會誤導自己和他人呢？
> :notes: jserv
```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;
}
```
如標題所述，除法可以利用$2^N進行加速，透過將\dfrac{n}{d}=n\times\dfrac{\dfrac{2^N}{d}}{2^N}$將除法轉換為乘法和位移操作，進而減少運算成本。
已知 `quotient = ((__uint128_t) M * n) >> 64` 對應$\dfrac{1}{2^N}$ 所以 $N=64$
但對應的$M卻不等於\dfrac{2^N}{d}$而是$M=\dfrac{2^N-1}{d} + 1$
因此要證明兩者最終結果是相等的。
若以數學的角度考量$\dfrac{M \times n}{2 ^ {64}} = \dfrac{(\dfrac{2 ^ {64} - 1}{d} + 1) \times n}{2 ^ {64}} = \dfrac{n \times 2 ^ {64} - n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}}$
$= \dfrac{n}{d} - \dfrac{n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}} = \dfrac{n}{d} + (\dfrac{d \times n - n}{d \times 2 ^ {64}}) = \dfrac{n}{d} + (\dfrac{(d - 1) \times n}{d \times 2 ^ {64}}) < \dfrac{n}{d} + \dfrac{n}{2^{64}}$。
由於$n,d < 2^{32} - 1因此\dfrac{n}{2 ^ {64}} < \dfrac{1}{2^{32}} < \dfrac{1}{2^{32} - 1}且\dfrac{n}{d}的餘數部分最大值為\dfrac{2^{32}-2}{2^{32} - 1}$
所以$\dfrac{n}{d}的餘數部分加上\dfrac{n}{2^{64}}也不會進位$
---
但若以程式碼的角度考量
若$M=\dfrac{2^{64}}{d}為整數(設為K)，因\dfrac{2^{64} - 1}{d} < K所以M=\dfrac{2^{64} - 1}{d}+1=(K-1)+1 = K$
若$M=\dfrac{2^{64}}{d}為非整數，因\dfrac{2^{64} - 1}{d} > K所以M=\dfrac{2^{64} - 1}{d}+1=K+1$
兩種情況會讓 `quotient` 分別等於$\dfrac{n}{d}和\dfrac{n}{d}+\dfrac{n}{2^{64}}$但根據上述數學推論的結果，兩者得到的答案相等
因此 XXX = `(f) 0xFFFFFFFFFFFFFFFF`
**jemalloc 的除法原理**
$n$為**被除數**, $q$為**商**, $d$為**除數**
假設$n = q \times d，已知 n,d 求q = n / d$
$=\left \lfloor \left \lceil \dfrac{2^k}{d} \right \rceil \times \dfrac{n}{2^k} \right \rfloor = \left \lfloor \dfrac{2^k + r}{d} \times \dfrac{n}{2^k} \right \rfloor，k為任意整數，而r = (- 2)^k mod \space d$
$將\left \lfloor \dfrac{2^k + r}{d} \times \dfrac{n}{2^k} \right \rfloor展開為\left \lfloor \dfrac{2^k}{d} \times \dfrac{n}{2^k} + \dfrac{r}{d} \times \dfrac{n}{2^k}\right \rfloor = \left \lfloor \dfrac{n}{d} + \dfrac{r}{d} \times \dfrac{n}{2^k} \right \rfloor$
$因假設n /d為整除，所以n/d的小數部分為0，因此式子可以化簡為\dfrac{n}{d} + \left \lfloor \dfrac{r}{d} \times \dfrac{n}{2^k} \right \rfloor$
也就是當$\dfrac{r}{d} \times \dfrac{n}{2^k} < 1$，$n/d = \left \lfloor \left \lceil \dfrac{2^k}{d} \right \rceil \times \dfrac{n}{2^k} \right \rfloor$就會成立
因$r是\dfrac{2^k}{d}的餘數因此r<d且r/d<1$總是成立，所以只需滿足$\dfrac{n}{2^k} < 1$
又$n為32bits的數，最大值為2^{32}-1，因此可以令k = 32來確保\dfrac{n}{2^k} < 1$
## 4. 倍數判斷
已知 `D = 3` `M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556`
```cpp
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
令 `n=3k, 3k+1, 3k+2` (k為非負整數) `n * M` 等於
若 `k=1` 因為 `3M > 0xFFFFFFFFFFFFFFFF` (overflow) 所以 `3M = 0x0000000000000002`
求三者最小值:
* 3kM = 2k
* (3k+1)M = 3kM + M = 2k+M
* (3k+2)M = 3kM + 2M = 2k + 2M
因此只有 `(c) M - 1, (d) M >> 1` 符合要求
但答案的 YYY = `(c) M - 1`
:::danger
:warning: 注意共筆書寫要求：中英文之間用一個半形空白字元區隔，從小處做起！
:notes: jserv
:::
## 5. 字串大小寫轉換
```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
e.g. 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|
| |128 |1000 0000|
因此可得知當
`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`
延伸問題 將前述測試程式 main 函式的 char str[] 更換為 char *str，會導致
`Segmentation fault (core dumped)`的發生。
根據C語言規格書[ISO/IEC 9899:1999](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)p.130
> The contents of the arrays are modifiable. On the other hand, the declaration
**char \*p = "abc";**
defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal.
If an attempt is made to use **p** to modify the contents of the array, the behavior is undefined.
嘗試使用 p 去修改 arrary 內的值是屬於 undefined behavior
**6.4.5 String literals**
>The multibyte character sequence is then used to initialize an array of **static** storage duration and length just sufficient to contain the sequence.
又提到會將內容初始化為指定大小的**靜態**陣列，因此使用 **char \*str** 相當於 **const char \*str**
## 6. 單次數尋找
```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;
}
```
是有限狀態機的味道，而本題題解屬於Mealy機，輸出依賴於輸入和狀態
首先構建一個真值表如下圖所示
| 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 |
當出現第三次時代表此數並非我們所尋找的數，因此直接重置狀態為 00
$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`，得到題解程式碼如上圖。
[延伸問題 2](https://github.com/Rsysz/quiz2/blob/master/test6.c)
[延伸問題 3](https://github.com/Rsysz/quiz2/blob/master/test6_extend.c)
Sign in with Wallet
Connect another wallet