# 2020q3 Homework2 (quiz2)
contributed by < `tsengsam` >
[第二週測驗題](https://hackmd.io/@sysprog/2020-quiz2)
---
## 【測驗 `1`】
#### 如何計算輸入的字串是否全為有效的 ASCII 字元，這邊有效定義為 ASCII 10 進位表示的數值介於 1\~127，128~255 則屬無效。
* 第一種寫法為單一字元逐個確認，因無效字元的最高位元為 **1**，而 `0x80` 的二進位正好只有最高位元是 1，故第 13 行的運算可判斷是否有效。
```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;
}
```
* 第二種是從記憶體的角度來計算而非單一字元，因此可以一次檢查數個字元，本題在 64 位元架構下比對 64 位元的資料，相當於 8 個字元，從前種寫法可知比對一個字元用的是 0x80，而兩個字元是 0x8080，以此類推到 8 個字元就是用 `0x8080808080808080`。
但字串長度不一定剛好是 64 位元長度，不滿 8 個字元的部分仍逐一比對。
```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 & 0x8080808080808080) /*MMM*/
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
### 延伸問題1-1: 為何 `memcpy`
* `memcpy` 會從來源指標複製 n bytes 到目的指標，若兩者記憶體位址重疊則為 undefined behavior。
```cpp=
#include <string.h>
void *memcpy (void *dest, const void *src)
```
* 除了複製 64 位元長度字串做比較，該函式在 GNU Library C 的 [實作](https://github.com/lattera/glibc/blob/master/string/memcpy.c) 還有關於 data alignment 的設計:
```cpp=
void *memcpy (void *dstpp, const void *srcpp, size_t len)
{
...
/* Copy from the beginning to the end. */
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES) {
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of DSTP. Number of bytes remaining is put in the third argument, i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
```
1. 首先確認複製的長度是否超過閾值 `OP_T_THRES`，若是就做 data alignment，否則直接複製。
2. 計算所需的 bytes 並且對齊目的指標 (`BYTE_COPY_FWD`)
3. 盡可能地複製到目的位址 (`PAGE_COPY_FWD_MAYBE`, `WORD_COPY_FWD`) 直到目的記憶體區段填滿
4. 剩下的內容直接複製 (`BYTE_COPY_FWD`)
* 因此 memcpy 用記憶體長度直接比較之外，還有顧對齊的處理。
* 如果不用 memcpy 而是使用 explicitly casting 會是如何
> 從[:tada:RinHizakura:tada:](https://hackmd.io/@RinHizakura/SJ5NuIANP#Why-memcpy%EF%BC%9F)的筆記看到有趣的實驗，於是自己也做一次避免以後忘記><
若將 memcpy 那行改成 casting:
```cpp=
uint64_t *payload = (uint64_t *) str
```
且在編譯時 輸入參數 `-fsanitize=alignment` 使其檢查指標 dereference 時是否對齊，或 reference 未對齊的物件，又或是建構未對齊的物件諸如此類的行為。
因此當我執行 casting 版本會顯示:
```script=
$ gcc -fsanitize=alignment 1.c -o 1
$ ./1
1.c:18:13: runtime error: load of misaligned address 0x7ffe1341bbae for type 'uint64_t', which requires 8 byte alignment
0x7ffe1341bbae: note: pointer points here
00 00 00 00 71 71 71 71 71 61 73 64 31 32 33 00 66 69 67 69 6c 40 67 62 6a 68 64 75 62 00 00 1a
^
```
第 3 行的 run time error 表示程式碼中第 18 行對未對齊的指標做了 load 的指令，而最後一行的數字表示儲存的數值，並且可以看到未對齊的情況。
### 延伸問題1-2: 改寫為判斷字串是否僅包含大小寫英文字母
```cpp=
bool is_alphabet(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);
uint64_t A = payload + PACKED_BYTE(128 - 'A');
uint64_t Z = payload + PACKED_BYTE(127 - 'Z');
uint64_t upper_mask =
(A ^ Z) & PACKED_BYTE(0x80); /*Should be PACKED_BYTE(0x80) */
uint64_t a = payload + PACKED_BYTE(128 - 'a');
uint64_t z = payload + PACKED_BYTE(127 - 'z');
uint64_t lower_mask =
(a ^ z) & PACKED_BYTE(0x80); /*Should be PACKED_BYTE(0x80), too*/
if ((upper_mask | lower_mask) ^ PACKED_BYTE(0x80))
return false;
i += 8;
}
while (i < size) {
if (str[i] < 65 || str[i] > 122 || (str[i] > 90 && str[i] < 97))
return false;
i++;
}
return true;
}
```
* 本題是看了其他同學才知道怎麼寫的，可結合測驗 5 的 `PACKED_BYTE` 以及求 mask 的設計
1. 第 11 行的 `upper_mask` 若有其中一個 byte 是 0x80，表示對應的字元為大寫英文，否則為 0x00
2. 第 15 行的 `lower_mask` 同上，若有其中一個 byte 是 0x80，表示對應字元為小寫，否則為 0x00
4. 因此 17 行的 `upper_mask | lower_mask` 是將大寫或小寫的 mask 合起來並
`^ PACKED_BYTE(0x80)`，若為 0 表示 mask 的所有 bytes 皆為 0x80，即英文大寫或小寫。
5. 反之表示至少有一 byte 不為英文大小寫。
---
## 【測驗 `2`】
#### 將 16 進位表示的字串轉為 10 進位的數值，且程式碼不含分支
* 因 `in` 僅限於 1~9, a~f, A~F，於是可以搜尋一下這些字元的 [Binary ASCII](https://en.wikipedia.org/wiki/ASCII#Printable_characters)
```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;
}
```
1. 從第 5 行的回傳來看是 `in` 加上一個 `shift` 然後取前4個低的位元，也就是**如何把 `in` 前四個低位元湊成答案**。
2. 觀察 shift 應該要為多少使其加上 `in` 後成為答案，可發現恰好差了兩個位元，與第 4 行兩個位移相對應。
3. 用來位移的 letter 是從第三行 `in & MASK` 得到的，`MASK` 過濾多的 1 bit，留下一個可用也就是第七個位元，故 `MASK = 0x40`。
4. 求出 letter 後可確定 `AAA = 3`, `BBB = 6`。
---
## 【測驗 `3`】
#### 這題運用預處理 + 乘法 + 位移運算 來代替運算成本較高的除法運算，核心概念是將原始的除法: $\dfrac{n}{d}$ 等價代換為: $n*\dfrac{\dfrac{2^N}{d}}{2^N}$，其中 $\dfrac{2^N}{d}$ 的部分預處理、$\dfrac{1}{2^N}$ 可使用位移運算。
```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;
}
```
1. 首先第二行的 M 是預處理，可知和 $\dfrac{2^N}{d}$ 有關
2. 欲找出 $\dfrac{2^N}{d}$ 則可從第六行找到答案，這行是計算出除式的商，而 `>>` 對應到了 $\dfrac{1}{2^N}$，因此 `N = 64`，不過題目不同的是最後加一且型態是 uint64_t，因此 `XXX` 應小於 $2^{64}$，故猜測為 `0xFFFFFFFFFFFFFFFF`，然後再驗證結果與 $\dfrac{2^N}{d}$ 一致:
欲證 $\dfrac{n}{d}$ 與 $\dfrac{(\dfrac{2^N - 1}{d} + 1) * n}{2^N}$ 等效
$右式 = \dfrac{(\dfrac{n * 2^N - n}{d} + n)}{2^N} = \dfrac{n * 2^N - n}{d * 2^N} + \dfrac{n}{2^N} = \dfrac{n}{d} - \dfrac{n}{d * 2^N} + \dfrac{n}{2^N} = \dfrac{n}{d} - \dfrac{n + d * n}{d * 2^N} = \dfrac{n}{d} + \dfrac{n * (d - 1)}{d * 2^N}$
由於 $n < 2^{32} < 2^{64} = 2^{N}, (d-1) < d$, 故 $(\dfrac{n * (d - 1)}{d * 2^N}) < 1$
使得 $\dfrac{n}{d} + \dfrac{n * (d - 1)}{d * 2^N}$ 經計算機整數運算後等於 $\dfrac{n}{n} + 0 = \dfrac{n}{d} = 左式$
---
## 【測驗 `4`】
#### 判斷是否可以整除，回傳 1 表可整除，反之不可整除。
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
* 求 `YYY` 使得所有可以整除的數必定小於等於它
* `M = 0x5555555555555556`
* 為了找到可整除與不可整除的差異，將 n 分成 {3k, 3k+1, 3k+2} 分別代表整除、餘一、餘二的數:
當 n = 3k: $n * M = 3k * M = 3k * (\overbrace{0x55...5}^{64 bits} + 1) = k * (\overbrace{0xff...f}^{64 bits} + 3) = k * 2 = 2k$
當 n = 3k+1: $n * M = (3k + 1) * M = 3k * M + M = 2k + M$
當 n = 3k+2: $n * M = (3k + 2) * M = 3k * M + 2M = 2k+ 2M$
* 可整除與不可整除的差異就為常數 M，因此當 `n * M <= (M - 1)` 回傳 1 時必定為可整除，反之不可整除。
## 【測驗 `5`】
#### 本題是大寫轉換成小寫，且會判斷是否為英文語系，若非則會使用 `strlower` 函式
```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);
}
int main()
{
char str[] = "@AYZ~~<>";
printf("%s\n", str);
int size = strlen(str);
strlower_vector(str, size);
printf("%s\n", str);
return 0;
}
```
:::warning
TODO: 為何不都用tolower
:::
* 我解這題的方式是任選一個想要轉換的字母 ('A'->'a')，然後從後往前回推每一行的行為:
1. 首先知道 `PACKED_BYTE(b)` 是將輸入擴展為 64 位元長度，且每 8 位元都和輸入長一樣。目的一樣是一次對多個字元做處理。
2. 撇除處理其他語系，看到第 17 行的 `*chunk ^= mask` 可知經過 `mask` 之後我的大寫會被轉換成小寫，從 Binary ASCII 觀察大小寫差在第 6 個位元，故 mask 可推知為 (0010_0000)~2~。
3. 第 16 行可看出來 mask 是右移 2 位元過的值，可知 `((A ^ Z) & PACKED_BYTE(VV4))` 為 (1000_0000)~2~，由 AND operation 判斷左右兩邊第8個倍數的位元必須為 1 才能變成 mask，如此可推測出 `VVV4` 為 0x80，且A, Z 的最高位元不相同。
4. 需檢查輸入 'Y' 或 'Z' 時都要滿足 mask = (1000_0000)~2~，故只會剩下一種組合就是 `(VVV2, VVV3) = (0, -1)`。
5. 最後第 13 行的 `VV1` 用來判斷是否為英文語系，方式為判斷是否為 extended ASCII，與測驗一相同。
### 延伸問題5-1: String literal
* 若將 `main` 中 str 的宣告改為 `char *str` 會產生下列訊息:
```cpp=
$ ./5
@AYZ~~<>
Segmentation fault (core dumped)
```
* 翻閱 C:99 規格書第 6.4.5 提到嘗試更改 string literal 是 undefined behavior:
> It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.
string literal 是指 double-quotes (") 圍起來的序列，當用 string literal 定義了 `str[]` 物件後的內容是 `modifiable`；然而 `*str` 物件內容的更改則是 `undefined behavior`。
## 【測驗 `6`】
#### 給定一數列，其中只有一個數字僅出現一次，其他都出現三次
* 這題是出現兩次的進階版，其程式碼僅需 `nums[i] ^= nums[i]` 便可透過 XOR 紀錄出現過一次的數字，出現兩次的則會消失。
* 在紀錄出現三次的程式碼則是用兩個變數，`lower` 為記錄出現過一次的數字，`higher` 為記錄出現過兩個的數字，和基本版的 XOR 核心算法一樣，只是多了一個從出現一次跳到出現兩次，及從出現兩次跳到出現三次(即零次)的運算 `lower &= ~higher`。
* 將數字換成 4 bits 二進位表示，從原本輸入一個數字變成輸入四個數字 (位元)，亦即變成對每個位元來做計算。若該位元出現過一次 1 則會放在 lower，或出現兩次會在 higher，三次則都沒有:
| | 2 | 2 | 3 | 2 |
| ---------- | -------- | -------- | -------- |:-------- |
| **binary** | **0010** | **0010** | **0011** | **0010** |
| lower | 0010 | 0000 | 0001 | 0011 |
| higher | 0000 | 0010 | 0000 | 0000 |
```cpp=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;
}
return lower;
}
```
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet