# 2020q3 Homework2 (quiz2)
contributed by < `Veternal1226` >

###### tags: `sysprog2020`

---
### 測驗 `1`
題目:
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:

#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)，程式碼改寫如下:

#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`
#### 解題想法:
將原本只比對1個字元改寫成一次比對8個字元
因此直接將 0x80 擴展成 0x8080808080808080
故答案選 ==(d) 0x8080808080808080==

:::success
延伸問題:
1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性
:::
程式流程:
第 7 行: 判斷長度是否為 0 ，若為 0 則直接 return false
第 9~21 行: 判斷輸入的字元串是否皆為 ASCII 字元
10~16 行: 一次比對 8 個字元
17~21 行: 比對剩下的字元

使用 memcpy 而不使用 type casting原因:
需要做 memory alignment

參考[GNU C Library/memcpy.c](https://elixir.bootlin.com/linux/v4.6/source/arch/nios2/lib/memcpy.c#L160)
程式碼如下:

/* Type to use for aligned memory operations.
   This should normally be the biggest type supported by a single load
   and store.  */
#define	op_t	unsigned long int
#define OPSIZ	(sizeof(op_t))

/* Copy exactly NBYTES bytes from SRC_BP to DST_BP,
   without any assumptions about alignment of the pointers.  */
#define BYTE_COPY_FWD(dst_bp, src_bp, nbytes)				\
do {									\
	size_t __nbytes = (nbytes);					\
	while (__nbytes > 0) {						\
		unsigned char __x = ((unsigned char *) src_bp)[0];	\
		src_bp += 1;						\
		__nbytes -= 1;						\
		((unsigned char *) dst_bp)[0] = __x;			\
		dst_bp += 1;						\
	}								\
} while (0)

/* Copy *up to* NBYTES bytes from SRC_BP to DST_BP, with
   the assumption that DST_BP is aligned on an OPSIZ multiple.  If
   not all bytes could be easily copied, store remaining number of bytes
   in NBYTES_LEFT, otherwise store 0.  */
/* extern void _wordcopy_fwd_aligned __P ((long int, long int, size_t)); */
/* extern void _wordcopy_fwd_dest_aligned __P ((long int, long int, size_t)); */
#define WORD_COPY_FWD(dst_bp, src_bp, nbytes_left, nbytes)		\
do {									\
	if (src_bp % OPSIZ == 0)					\
		_wordcopy_fwd_aligned(dst_bp, src_bp, (nbytes) / OPSIZ);\
	else								\
		_wordcopy_fwd_dest_aligned(dst_bp, src_bp, (nbytes) / OPSIZ);\
	src_bp += (nbytes) & -OPSIZ;					\
	dst_bp += (nbytes) & -OPSIZ;					\
	(nbytes_left) = (nbytes) % OPSIZ;				\
} while (0)

/* Threshold value for when to enter the unrolled loops.  */
#define	OP_T_THRES	16

void *memcpy(void *dstpp, const void *srcpp, size_t len)
{
	unsigned long int dstp = (long int) dstpp;
	unsigned long int srcp = (long int) srcpp;

	/* 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;
}

分析 160~190 行的 memcpy
若長度不足 OP_T_THRES 則直接進行 BYTE_COPY_FWD (189行)
若長度超過 OP_T_THRES :
　　先計算`(-dstp) % OPSIZ`，代表除以 OPSIZ 剩下來的長度
　　先複製此長度的資料到 dstp 使dstp 位置對齊
　　再對每個 word 做 WORD_COPY_FWD (183行)

因此若複製的內容不為word整除依然能符合對齊的行為。

:::success
延伸問題:
2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
>提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4
:::

//TODO

---
### 測驗 `2`
開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

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
請補完程式碼。

作答區

MASK = `(c) 0x40`
AAA = `(a) 3`
BBB = `(b) 6`

#### 解題想法:
先分析 ASCII 字元的二進制

| Dec | Hex | Binary | Output(Dec) | Output(Bin) |
| --- | --- | -------- | ------ | -|
| 0 | 0x30 | 0011 0000 | 0 | 0000 |
| 9 | 0x39 | 0011 1001 | 9 | 1001 |
| A | 0x41 | 0100 0001 | 10 | 1010 |
| F | 0x46 | 0100 0110 | 15 | 1111 |
| a | 0x61 | 0110 0001 | 10 | 1010 |
| f | 0x66 | 0110 0110 | 15 | 1111 |

從第 5 行 `(in + shift) & 0xf` 得知結果只 return 後 4 bit 的值。
in + shift 表示把輸入的 uint8_t 加上一個偏移值 shift 後輸出。
>以`A`為例，若只看後 4 位元，1010 - 0001 = 1001 = shift
>以`f`為例，若只看後 4 位元，1111 - 0110 = 1001 = shift

因此得知若輸入為字母則加上偏移值1001 (二進制表示)，若輸入為數字則偏移值為 0000。

從第 4 行`shift = (letter >> AAA) | (letter >> BBB)`可得知 shift 是由 letter right shift 不同 bits 後做 OR 運算的結果，因此先猜測 letter 應該是位在某個位置的 1 。
例如:
　　1001 = 10000000 >> 4 | 10000000 >> 7
　　1001 = 01000000 >> 3 | 01000000 >> 6
　　1001 = 00100000 >> 2 | 00100000 >> 5

觀察大小寫字母均有的特徵
| Dec | Hex | Binary | Output(Dec) | Output(Bin) |
| --- | --- | -------- | ------ | -|
| A | 0x41 | 0==1==00 0001 | 10 | 1010 |
| F | 0x46 | 0==1==00 0110 | 15 | 1111 |
| a | 0x61 | 0==1==10 0001 | 10 | 1010 |
| f | 0x66 | 0==1==10 0110 | 15 | 1111 |

因次推測字母均有的特徵為 01000000 = 0x40, ==MASK = 0x40==。
又因 MASK=0x40, AAA 與 BBB 為 3 與 6，從選項得知 ==AAA = 3, BBB = 6==

:::success
延伸問題:
1. 解釋上述程式的運作原理
:::
第 3 行為分辨是不是字母，若是則 letter = 0x40 ；若不是則 letter = 0x0
第 4 行使用剛剛得到的 letter，將其轉為正確的偏移值。若輸入為字母則 shift = 1001 ；若輸入為數字則 shift = 0
第 5 行將輸入的值加上偏移值後，利用AND運算做MASK，只取後 4 bits 並回傳

:::success
延伸問題:
2. 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
>Hexspeak
:::

//TODO

---
### 測驗 `3`
除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如 $\tfrac{n}{d}$ 在分子和分母分別乘 $2^N$ 後，得到等價的 $n×\tfrac{\tfrac{2^N}{d}}{2^N}$ ，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當 $d$ (除數) 的數值是已知的狀況下，$\tfrac{2^N}{d}$ 可預先計算，也就是說，$\tfrac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然 $\tfrac{2^N}{d}$ 無法總是用整數來表達 (僅在 $d$ 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。

重新檢視 $\tfrac{n}{d} =n ×\tfrac{\tfrac{2^N}{d}}{2^N}$ ，當我們想將 $n$ 除以 $4$ 時，就相當於乘以 $0.25$ ，所以我們可將 $\tfrac{5}{4}$ 改為 $5×0.25$ ，我們得到整數的部分 (即 $1$ )，和小數部分 (即 $0.25$ )，後者乘以 $4$ 就是 $1$ ，也就是餘數。下方程式碼展示這概念:

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`

#### 解題想法:
:::success
延伸問題:
1.解釋上述程式的原理;
:::
已知 $n \mod d = n-\lfloor\tfrac{n}{d}\rfloor×d$ ，也就是第 7 行的回傳值。由此可得知 quotient = $\lfloor\tfrac{n}{d}\rfloor$。
從題目的提示可以得知 $\tfrac{n}{d} =n ×\tfrac{\tfrac{2^N}{d}}{2^N}$ 、$\tfrac{1}{2^N}$ 等同於右移 (shift) N 個位元，
從第 6 行可推出 N = 64，從第 2 行得知預定義的M為 $\tfrac{XXX}{d}+1$ ，

M = $\tfrac{2^N}{d} = \tfrac{2^{64}}{d}$ ，
$\tfrac{XXX}{d}+1 = \tfrac{2^{64}}{d}$ ，
$XXX = 2^{64}-d$
因為題目定義 uint32_t D;
因此 $2^{64}-(2^{32}-1) \le XXX \le 2^{64}-0$
0xFFFFFFFF00000001 < XXX < 0x10000000000000000 (17位)
選項中符合的只有 ==(f) 0xFFFFFFFFFFFFFFFF==
:::success
延伸問題:
2. 由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
:::

//TODO

---
### 測驗 `4`
延伸測驗 `3`，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

bool divisible(uint32_t n)
{
    return n * M <= YYY;
}

以 `D = 3` 來說，`divisible(7)` 要得到 `0` (即 7 無法被 3 整除)，`divisible(87)` 要得到 `1` (即白痴是三的倍數)

請補完程式碼。

作答區

YYY = `(c) M - 1`

#### 解題想法:

//TODO

---
### 測驗 `5`
考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 in-place 的實作如下:

#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]);
    }
}

針對 extended ASCII，我們呼叫 C 語言標準函式庫的 tolower，需要留意到在不同的語系 (locale)，字母順序和大小寫的定義可能異於我們認知的英文字母。以下摘自手冊:

>If c is a lowercase letter, toupper() returns its uppercase equivalent, if an uppercase representation exists in the current locale. Otherwise, it returns c.

語系對程式碼的影響不能輕忽，舉例來說，若語系設定為捷克語，以 “Ch” (屬於 digraph，二合拉丁字母，常見於西歐語言) 開頭的字串要排在 “H” 之後，但單看字母的話，“C” 要在 “B” 之後。不過，如果明確只處理英美語系 (American/British English)，上述程式碼列表的第 9 及第 10 行可略去。

>捷克字母 (依序)
>A a Á á B b C c Č č D d Ď ď E e É é Ě ě F f G g H h Ch ch I i
>Í í J j K k L l M m N n Ň ň O o Ó ó P p Q q R r Ř ř S s Š š
>T t Ť ť U u Ú ú Ů ů V v W w X x Y y Ý ý Z z Ž ž

在 64 位元處理器架構 (以下針對 `x86_64`, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 `x86_64` 來說，就是 64 bits，或 8 個位元組)。沿用上述的 `strlower` 函式，我們用這樣的思路實作向量化的 `strlower`，程式碼列表如下:

#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);
}

對應的測試程式碼如下:

#include <stdio.h>
#include <string.h>
int main()
{
    /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
    char str[] =
        "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
    int n = strlen(str);
    strlower_vector(str, n);
    puts(str);
}

參考執行輸出:

>this ebook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. you may copy it, give it away or re-use it under the terms of the project gutenberg license included with this ebook or online at www.gutenberg.net

請補完程式碼。

作答區

VV1 = `(e) 0x80`

VV2 = `(b) 0`

VV3 = `(a) (-1)`

VV4 = `(e) 0x80`

#### 解題想法:

//TODO

:::success
延伸問題:
1. 解釋上述程式的原理;
2. 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
:::

//TODO

---
### 測驗 `6`

LeetCode 137. Single Number II:

>Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: `[2,2,3,2]`
Output: 3

Example 2:
Input: `[0,1,0,1,0,1,99]`
Output: 99

考慮以下程式碼為 LeetCode 137. Single Number II 的題解:

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;
} 

請補完程式碼。

作答區

KKK = `(c) ~higher`

JJJ = `(d) ~lower`

#### 解題想法:

//TODO

:::success
延伸問題:
1. 解釋上述程式的原理;
2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
:::

//TODO