# 2020q3 Homework2 (quiz2)
contributed by < `ZhuMon` >
###### tags: `sysprog2020` `quiz`
> [2020q3 第 2 週測驗題](https://hackmd.io/@sysprog/2020-quiz2)
## :memo: Table of Contents
[TOC]
---
## :page_facing_up: [測驗 `1`](https://hackmd.io/@sysprog/2020-quiz2#%E6%B8%AC%E9%A9%97-1)
### 題目
```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;
}
```
### 解答
* `MMM` = `(d)` `0x8080808080808080`
* 從原始程式碼可知，`is_ascii` 藉由將 byte 與 `0x80` 做 and，確認 byte 的第一個 bit 是否為 1，藉此確認是否為 ASCII 的有效字元
* 改寫後，為了達成一次比對 8 個 byte，一次將 8 個 byte 存到 `payload` (第 12 行)，因此 mask 也要擴展，從只能判斷 1 個 byte 的 `0x80` 擴展到可以比對 8 個 byte 的 `0x8080808080808080`
### 延伸問題
1. 為何使用 `memcpy`?
根據 glibc 2.33 的 [memcpy.c](https://sourceware.org/git/?p=glibc.git;a=blob;f=string/memcpy.c;h=2cb4c76515f476f36a9a8d5dd258ea98e36792b2;hb=4c56bcbceb05b44965d48e701711f850b83d7c69)，將註解去掉後，如下
```cpp=
#include <string.h>
#include <memcopy.h>
#ifndef MEMCPY
# define MEMCPY memcpy
#endif
void *
MEMCPY (void *dstpp, const void *srcpp, size_t len)
{
unsigned long int dstp = (long int) dstpp;
unsigned long int srcp = (long int) srcpp;
if (len >= OP_T_THRES)
{
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
WORD_COPY_FWD (dstp, srcp, len, len);
}
BYTE_COPY_FWD (dstp, srcp, len);
return dstpp;
}
libc_hidden_builtin_def (MEMCPY)
```
以下幾個 macro 會根據不同的架構而有所不同，在 glibc 的 generic [memcopy.h](https://github.com/lattera/glibc/blob/895ef79e04a953cac1493863bcae29ad85657ee1/sysdeps/generic/memcopy.h) 定義如下
```cpp
#define OP_T_THRES 16
#define OPSIZ (sizeof(op_t))
#define op_t unsigned long int
```
* `memcpy` 解釋
若是要複製長度大於 `OP_T_THRES` 的記憶體，先將沒有對齊的資料複製完成後 (line==17==)，便可以直接以 Page 作為單位快速的複製記憶體(`PAGE_COPY_FWD_MAYBE`)，接著以 word 作為單位複製剩下的記憶體，然後複製剩下的 byte
```mermaid
graph TD
memcpy[dstp = dstpp<br>srcp = srcpp]
if{len >= OP_T_THRES}
bcf[BYTE_COPY_FWD]
pcfm[PAGE_COPY_FWD_MAYBE]
wcf[WORD_COPY_FWD]
bcf2[BYTE_COPY_FWD]
memcpy --> if
if -- true --> bcf --> pcfm --> wcf --> bcf2
if -- false --> bcf2
```
* `memcopy.h` 對於 `BYTE_COPY_FWD(dst_bp, src_bp, nbytes) ` 的描述為
> Copy exactly NBYTES bytes from SRC_BP to DST_BP,
> without any assumptions about alignment of the pointers.
也就是說，`BYTE_COPY_FWD` 會從 `src_bp` 開頭逐一複製 `nbytes` 個 byte 到 `dst_bp` 的開頭 (另一個 macro `BYTE_COPY_BWD` 則是將來源位址和目標位址都視為結束位址來複製)
```c
#define BYTE_COPY_BWD(dst_ep, src_ep, nbytes) \
do \
{ \
size_t __nbytes = (nbytes); \
while (__nbytes > 0) \
{ \
byte __x; \
src_ep -= 1; \
__x = ((byte *) src_ep)[0]; \
dst_ep -= 1; \
__nbytes -= 1; \
((byte *) dst_ep)[0] = __x; \
} \
} while (0)
```
---
2. 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母
查看 ASCII Table，可以知道英文大小寫字母所對應的 ASCII code 為 `0x41~0x5A`, `0x61~0x7A`，以二進位表示如下
| Char | Bin | Hex |
| -------- | -------- | -------- |
| A | 0100 0001 | 0x41|
| Z | 0101 1010 | 0x5A|
| - | ---- | - |
| a | 0110 0001 | 0x61|
| z | 0111 1010 | 0x7A|
> 以 `*` 代表 don't care
觀察可知，英文字母的 ASCII code 前兩個 bit 必為 01，但是在 `01** ****`的範圍中，{`01000000`, `01011011 ~ 01100000`, `01111011 ~ 01111111`} 這三個區間內所對應的字元不是英文字母，總共有 12 個 ($2^6 - 26*2 = 12$)
繼續觀察，將上述 12 個字元以第三個 bit 分成兩類，可以再歸納出三組
1. `01*0 0000`
2. `01*1 1011`
3. `01*1 11**`
|hex|bin|hex|bin|
|-|-|-|-|
|0x40 | 0100 0000 | 0x60 | 0110 0000 |
|0x5b | 0101 1011 | 0x7b | 0111 1011 |
|0x5c | 0101 1100 | 0x7c | 0111 1100 |
|0x5d | 0101 1101 | 0x7d | 0111 1101 |
|0x5e | 0101 1110 | 0x7e | 0111 1110 |
|0x5f | 0101 1111 | 0x7f | 0111 1111 |
因此只要 ASCII code 同時符合以下四點，便為英文字母
1. `(char & 11000000) == 01000000`
2. `(char & 00011111) != 0`
3. `(char & 00011111) != 00011011`
4. `(char & 00011100) != 00011100`
但是要在單個 byte 實作很簡單，多個 byte 同時判斷就很困難
> TODO: 第五題似乎有較好的解決方法
---
## :page_facing_up: 測驗 `2`
### 題目
```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`，其他輸入都有對應的數值。
### 解答
`MASK` = `0x40`
`AAA` = `3`
`BBB` = `6`
1. 從結尾回推
從第 5 行的 return 值可以看到 `(in + shift)` 與 `0xf` 做 mask，因此 return 值只會在 `0~15` 之間。
* 數字部分
因為數字的 ASCII code 介於 `0x30~0x39`，因此 `shift` 只要不會影響 `in` 的後 4 bit，便可以使數字部分達成目的，預計 `shift` 為 `0x?0`
* 英文字母
要將 `0x61` (`a`) 和 `0x41` (`A`) 對應到 10 (`b'1010`)，因此最簡單的想法就是將 `shift` 設為 9 (`0x09`)
明顯兩個規則矛盾，因此 `shift` 應該符合下述條件
* `shift` = `0x?0`, if `in` $\in$ {`'0'`, `'1'`, ..., `'9'`}
* `shift` = `0x?9`, if `in` $\in$ {`'A'`, ..., `'F'`, `'a'`, ..., `'f'`}
2. 判斷 `letter` 為何
從字面意義大概猜出 `letter` 代表英文字母，從選項來看，可以知道要將 `in` 的前 4 bit 的某些 bit 取出來
* `(a)` `0x10`
* `(b)` `0x20`
* `(c)` `0x40`
* `(d)` `0x60`
* `(e)` `0x80`
而可以判斷英文字母與數字的 bit 為第 2 個 bit 和第 4 個 bit
* 數字: `0011 xxxx`
* 大寫: `0100 xxxx`
* 小寫: `0110 xxxx`
稍微瞄到下一行 (line 4)，`shift` 會以 `letter` 來決定值，而我們的 `shift` 在 `in` 為數字時，不需要有值，因此應該以第 2 個 bit 作為 mask，也就是
* `MASK` = `(c)` `0x40`
3. `AAA` & `BBB`
由於前面已經知道在 `in` 為英文字母時，`letter` 為 `b'0100 0000`，而要讓 `shift` 的後 4 bit 為 9 (`b'0000 1001`)，必須讓 `letter` 向左位移 3 位和向左位移 6 位，因此可以得到
* `AAA` = `3`
* `BBB` = `6`
---
## :page_facing_up: 測驗 `3`
### 題目
```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;
}
```
### 解答
為了得到餘數，function 必須返回
$\begin{split} n\ \%\ d &= n - x \times d \end{split}$
其中 $x$ 為 $n/d$ 的整數部分，也就是 `quotient`，將 $M = \dfrac{XXX}{d}+1$ 帶入下式
$\begin{split}x &= quotient \\
&= \dfrac{M \times n}{2^{64}} \\
&= \dfrac{(\dfrac{XXX}{d}+1) \times n}{2^{64}} \ \ \ \ \ 重新排列後 \\
&= n \times \dfrac{\dfrac{XXX}{d}+1}{2^{64}}
\end{split}$
對照題目可知 (XXX / d) + 1 便是 2^64^/d，~~而 XXX 最接近的選項便是 `0xFFFFFFFFFFFFFFFF`~~
~~> 關於為甚麼要先除以 d 再加 1，可以參考 [@cmwchw](https://hackmd.io/@cmwchw/2020q3-quiz2#Why--Mdfrac2N-1d1-) 的解說~~
也就是說
$n \times \dfrac{\dfrac{XXX}{d}+1}{2^{64}} = n \times \dfrac{\dfrac{2^{64}}{d}}{2^{64}}$
設 $Q = \dfrac{n}{d}$
$=> \dfrac{XXX}{2^{64}}Q+\dfrac{n}{2^{64}}=Q$
由於 $n << 2^{64}$
所以 $\dfrac{n}{2^{64}}$ 可以捨去
$=> \dfrac{XXX}{2^{64}}Q=Q$
$XXX = 2^{64}$
---
## :page_facing_up: 測驗 `4`
### 題目
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
判斷 n 是否被 d 整除
### 解答
將 M 帶入後可得
$n \times (\dfrac{2^{64}-1}{d}+1) \leq YYY$
...
將 n = 1 帶入，可以得到選項 (a) (b) (e) 都矛盾，因此只有可能是 $M-1$ 或 $M>>1$
試過所有值(0~2^32^-1)後發現兩者依舊可以達成目的，懷疑等號右方只要小於 $M$ 便可以達成目的
---
## :page_facing_up: 測驗 `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);
}
```
---
## :page_facing_up: 測驗 `6`
Sign in with Wallet
Connect another wallet