# 2020q3 Homework2 (quiz2)
contributed by < `grb72t3yde` >
###### tags: `sysprog2020`
---
## 測驗題目
> [第二週測驗題](https://hackmd.io/@sysprog/B1zAbkAEP)
## 測驗`一`
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (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)，程式碼改寫如下:
```clike=
#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;
}
```
---
### 個人解題思路
#### 1. MMM = ?
1. 首先觀察改寫後之 `is_ascii`, 我從 `line 10` 的 `while loop condition` 以及 `payload` 的 `data type` 得知, 這個 while loop 是以 `word width` 來做是否為 `ascii` 的判斷。
2. 考慮對於任一 7位元編碼的 ASCII 字元, 其 `MSB` 必為 0 (其範圍在0~127); 因此, `MMM` = `0x8080808080808080`。
3. 對於不滿一個 `word` 的 `bytes` 組, 會在第二個 `while loop` 對 `byte` 逐一檢查。
### 延伸問題
#### 1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？
* 參考提示 [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)後得知, "編譯器會自動幫我們以 data 的大小做 alignment"; 因此在 `is_ascii` 函式中之 argument `const char str[]` 接受的引數以 `const char` 之寬度對齊
* 如今, 我們想要以 `word` 的寬度進行 bit-wise operation, 因此使用 `memcpy`, 將 8個 byte 的資料複製到已宣告且以 `uint64_t` type 來對齊的變數 `payload` 中
* 以此達到 "alignment 寬度" 之轉換
> 思考 : 如果不使用 `memcpy`?
考慮下列修改 :
```diff=
#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;
+ uint64_t *payload = (uint64_t)str;
while ((i + 8) <= size) {
- uint64_t payload;
- memcpy(&payload, str + i, 8);
if (*payload & MMM)
return false;
+ payload++;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
使用 `gdb` 觀察, 仍能達到類似效果; 但是參考 [Should I worry about the alignment during pointer casting?](https://stackoverflow.com/questions/13881487/should-i-worry-about-the-alignment-during-pointer-casting) 後得知, 這是相較於使用 memcpy() 較危險且不具效率的方法 -> 待研究細節。
#### 2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
* 查詢 `ASCII` 表
```shell=
$ man ascii
```
得知：`A` 至 `Z` 的範圍在 `0x41 ~ 0x5a` ; `a` 至 `z` 的範圍在 `0x61 ~ 0x7a` 。
* 想法 : 將所有輸入字串轉為大寫 (或是小寫), 再判斷其是否在對應的區間
* 實驗 : TODO
#### 3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
* TODO
## 測驗`二`
開發解析器 (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;
}
```
### 個人解題思路
#### 1. MASK = ?
1. 我首先觀察到的是 return value 的部分, 使用 mask 遮去了高位的4個位元; 因此, 我判斷此作法利用 shift 將原 input 的低位4個位元修正成我們想要的結果 (0~15的任一個值)
2. 乘上, 我觀察大小寫英文字母與數字字元在 `ASCII` 編碼中的低位4個 byte, 發現 : 數字字元不需要修正, 而英文字母需要 `+ 0x09` (e.g. 0x41 ('A') + 0x09 = 0x4a, mask 掉高位的4個 bit 後得到 0x0a = 10)
3. 考慮到數字與字母需要用到不同的 `shift` 修正值, 我思考要用 MASK 留下 in 中**得以區別字母與數字的部分**
4. 觀察大寫, 小寫字母與數字的高位4個bit, 如下 :
> 大寫字母字元 : 0==1==00
小寫字母字元 : 0==1==10
數字字元 : 0==0==11
發現可以用 `0100` 來 mask 出字母與數字! 因此初步判定 `MASK` = `0x40`
#### 2. AAA = ?, BBB = ?
1. 基於`MASK` = `0x40` 以及 `in` 只會是對應到 `ASCII` 中大小寫字母與數字假設, 我們得到
> letter = 0x40, if `in` 對應到的 `ASCII` 為大小寫字母
> letter = 0x00, else
2. 基於前述觀察 (字母需要 `+0x09` 的修正, 而數字不用), 可以判斷 AAA 和 BBB 其一為3, 另一個則為6
### 延伸問題
* 將 `hexchar2val` 擴充為允許 `"0xFF"`, `"0xCAFEBABE"`, `"0x8BADF00D"` 等字串輸入，且輸出對應的十進位數值
想法 : 首先考慮輸入字元的個數, 如果我們想要以 `word` 來處理資料, 需要考慮到補 `0`
實驗 : TODO
## 測驗`三`
* 快速除法概念 : 將除法運算轉換成 `shift operation` 以及 `乘法` 的組合
```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 位元的無號數值。
### 個人解題思路
#### 1. XXX = ?
1. 觀察 line6, 將此行對應至題目給訂的公式 $n * ((2^N/d) / 2^N)$, 可初步判斷這裡的 N 取的是64
2. 觀察到 `D = 3` 不為一個 `power of 2` 的數值, 因此思考題目敘述 : "我們可先估算，並將差值補償回去" 後, 判斷 line2 的 macro 應該在做此 "估算並補償的動作"
3. 有了這個初步的想法卻卡住了, 不知道為何聚集是如此定義, 因此決定直接先去 trace [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c)
4. 程式碼的註解中解釋並證明了藉由使用 `ceil(2^k / d)` 作為 `magic`, 並且設定 $k = 32$ (能使得 n / 2^k 恆小於 1) 的情況下 :
能使得 `floor(ceil(2^k / d) * n / 2^k)` 得到 $n/d$ 在數學上正確的 quotient
5. 此時回頭檢視我們定義的 macro `M`, 並根據 `ISO/IEC 9899:201x`, `UINT64_C(XXX)` 將 `XXX` expand 至 `unsigned long long int`, 這個 data type 沒辦法正確地表示出 $2^{64}$
6. 已知 `C` 使用 `floor` 處理商數的小數點, 於是我們使用 `+1` 來達到 `ceiling`
7. 我們要證明 $\ floor(2^{64}/3) + 1 = floor((2^{64}-1)/3) + 1$; 事實上, 因為 $2^{64} \mod 3 \neq0$, 我們定義的 macro M 在 `d = 3` 時永遠可以得到對的結果;
### 延伸問題
TODO
## 測驗`四`
延伸測驗 `3`，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
### 個人解題思路
#### 1. YYY = ?
1. 先思考 $\forall n, n = 3k \lor 3k + 1 \lor 3k + 2, n <= 0xffffffff$
2. 考慮 $n*M$ 在這三種情況下分別可**表示**成以下三種形式
* if $n = 3k, 此時k<=0x55555555$
* 此時$n*M = 3k * ((2^{64} - 1)/3+1)$
* 則$n*M = k*(0xffffffffffffffff + 3) = k*2 = 2k$, 因為此時$(0xffffffffffffffff + 3)$ 溢位回 `+2`
* if $n = 3k + 1, n*M = 2k + M$
* if $n = 3k + 2, n*M = 2k + 2M$
可以看出在 n 這三種情況下, n*M 的值會因為數值溢位會有對應且固定的表示公式, 再來我們從答案選出一個定值, 能夠分界出 `n = 3k` 與 `n = 3k + 1 和 n = 3k + 2` 的 case
## 測驗`五`
考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 in-place 的實作如下:
```cpp=
#include <ctype.h>
#include <stddef.h>
/* in-place implementation for converting all characters into lowercase. */
void strlower(char *s, size_t n)
{
for (size_t j = 0; j < n; j++) {
if (s[j] >= 'A' && s[j] <= 'Z')
s[j] ^= 1 << 5;
else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */
s[j] = tolower(s[j]);
}
}
```
在 64 位元處理器架構 (以下針對 x86_64, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 x86_64 來說，就是 64 bits，或 8 個位元組)。沿用上述的 strlower 函式，我們用這樣的思路實作向量化的 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);
}
```
### 個人解題思路
#### 1. VV1 = ?
1.
## 測驗`六`
Sign in with Wallet
Connect another wallet