---
# System prepended metadata

title: 2020q3 Homework2 (quiz2)
tags: [sysprog2020]

---

# 2020q3 Homework2 (quiz2)
###### tags: `sysprog2020`
contributed by < `Msiciots` >

## 	:page_facing_up: 題目
- [2020q3 第 2 週測驗題](https://hackmd.io/@sysprog/2020-quiz2)
- [2020q3 Homework2 (作業區)](https://hackmd.io/@sysprog/2020-homework2)
:::info
目的: 檢驗學員對 [**數值系統**](https://hackmd.io/@sysprog/c-numerics) 及 [**bitwise**](https://hackmd.io/@sysprog/c-bitwise) 操作 的認知
:::
## 測驗 `1`
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元:
```c=
#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)，程式碼改寫如下:
```c=
#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)
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}
```
:::success
延伸問題:
1. 解釋上述程式的運作原理，特別是為何用到 `memcpy` 呢？提示: 與 data alignment 有關，詳閱 [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
    >提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: [Schema Validation with Intel® Streaming SIMD Extensions 4](https://software.intel.com/content/www/us/en/develop/articles/schema-validation-with-intel-streaming-simd-extensions-4-intel-sse4.html)
:::
###  延伸問題1.
程式目的為檢測 `str[]` 是否為有效 ASCII 字元。 
`0x80 = 1000 0000` ，只有第 1 ~ 7 bit 有效，若第 8 bit 存在則為 extended ASCII。
```c=
for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
```
Word size 為記憶體存取的最小單位，在 64 位元架構下可以一次比對 64 bits (8 bytes) 較有效率。讓每個 byte `& 0x80`，while 迴圈的索引 `i` 一次移動 8 bytes。　
參考 [glibc/string/memcpy.c](https://code.woboq.org/userspace/glibc/string/memcpy.c.html) 中 `memcpy()` 的實作，`memcpy()` 會事先檢查資料對齊，若原本沒對齊會先複製幾個 bytes 使得資料對齊後才以 word 為單位進行複製。
:::danger
使用 `memcpy()` 在特定情況會發生問題：
`void *memcpy(void *dest, const void *src, size_t n);`
當 `dest` 與 `src` 的記憶體區段重疊時會出錯，參考 [copying-overlapping-memory](https://riptutorial.com/c/example/2150/copying-overlapping-memory)，因此有了改良版的 `memmove()`。

:::
```c=
while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & 0x8080808080808080)
            return false;
        i += 8;
    }
```
考慮到剩餘字元的情況（不足 8 bytes），逐一檢查每個字元值。
```c=
while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
```
###  延伸問題2.
TODO
###  延伸問題3.
TODO
## 測驗 `2`
開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 `'0xF'` (大寫 `F` 字元) 和 `'0xf'` (小寫 `f` 字元) 都該轉換為 `15`。考慮以下不需要分支 (branchless) 的實作:
```c=
uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40; // MASK = 0x40 
    const uint8_t shift = (letter >> 3) | (letter >> 6); // AAA = 3 , BBB = 6
    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`
:::success
延伸問題:

1. 解釋上述程式的運作原理;
2. 將 `hexchar2val` 擴充為允許 `"0xFF"`, `"0xCAFEBABE"`, `"0x8BADF00D"` 等字串輸入，且輸出對應的十進位數值
    >[Hexspeak](https://en.wikipedia.org/wiki/Hexspeak)
:::
### 延伸問題1.
| in | hex | binary |
| -------- | -------- | -------- |
| `'0'`~`'9'`     |  `0x30` ~ `0x39`    | `0011 0000` ~ `0011 1001`     |
| `'A'`~`'F'`     |  `0x41` ~ `0x46`    | `0100 0001` ~ `0100 0110`     |
| `'a'`~`'f'`     |  `0x61` ~ `0x66`    | `0110 0001` ~ `0110 0110`   |
由上表觀察可得出
- 輸入`'0'`~`'9'` 保留低位 4 bits 即為回傳值，而`'A'`~`'F'` 與`'a'`~`'f'`則是需要把低位 4 bits 加上 9 。
- 若輸入為字母，第 7 bit 為 1
```c=
uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40; 
    const uint8_t shift = (letter >> 3) | (letter >> 6); 
    return (in + shift) & 0xf;
}
```
Line 3 : 判斷輸入是否為字母
Line 4 : 若輸入為字母，`shift = 0000 1001` 等於 `9` ，可改寫為`const uint8_t shift = letter? 9 : 0; `
Line 5 : `in` 加上 `shift` 後保留低位 4 bits 即為回傳值 
### 延伸問題2.
TODO
## 測驗 `3`
除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如 $\frac{n}{d}$ 在分子和分母分別乘上$\ 2^{N}$ 後，得到等價的$\ n\times \frac{\frac{2^{N}}{d}}{2^{N}}$，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當$\ d$ (除數) 的數值是已知的狀況下，$\frac{2^{N}}{d}$可預先計算，也就是說，$\frac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然 $\frac{2^{N}}{d}$ 無法總是用整數來表達 (僅在 $d$ 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。 
重新檢視 $\frac{n}{d} = \ n\times \frac{\frac{2^{N}}{d}}{2^{N}}$，當我們想將 $n$ 除以 $4$ 時，就相當於乘以 $0.25$，所以我們可將 $\frac{5}{4}$ 改為 $5\times0.25$，我們得到整數的部分 (即 $1$)，和小數部分 (即 $0.25$)，後者乘以 $4$ 就是 $1$，也就是餘數。下方程式碼展示這概念:
```c
const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1)) // XXX = 0xFFFFFFFFFFFFFFFF

/* 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 位元的無號數值。
> [GCC: C Extensions: 128-bit Integers](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) 

預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (`555` 是 3 的倍數)。
:::success
延伸問題:

1. 解釋上述程式的原理;
2. 由 Facebook 公司所維護的 [jemalloc](https://github.com/jemalloc/jemalloc) 是個高效能的記憶體配置器 (memory allocator，即 `malloc` 和 `free` 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 [include/jemalloc/internal/div.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/div.h) 和 [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
:::
###  延伸問題1.
透過數學式 $\frac{n}{d} = \ n\times \frac{\frac{2^{N}}{d}}{2^{N}}$ 可以快速的做取餘數運算，程式碼中 `N=64, d=3`，由於 64 位元只能表示 `0xFFFFFFFFFFFFFFFF = 2^64 - 1` ，所以在除與 `D` 之後做 `+1`  ，利用得到的 `quotient` 可以反推餘數
###  延伸問題2. 
todo

## 測驗 `4`
延伸測驗 `3`，我們想判斷某個數值能否被指定的除數所整除，在 `D` 和 `M` 都沿用的狀況下，程式碼如下:
```c
bool divisible(uint32_t n)
{
    return n * M <= M - 1; // YYY = M - 1
}
```
以 `D = 3` 來說，`divisible(7)` 要得到 `0` (即 7 無法被 3 整除)，`divisible(87)` 要得到 `1` (即白痴是三的倍數)

### 延伸問題1.
- 此題需要考慮 unsigned int overflow 的行為
- 將 `M = 0x5555555555555555 + 1` 帶入左式中，考慮 `n` 分別為 `3k`, `3k+1`, `3k+2` 的情況 
    - 3k * M = ( 0xffffffffffffffff + 3 ) * k = 2k
    - (3k+1) * M = 2k(套用上式結果) + M
    - (3k+2) * M = 2k + 2M
1. 2k <= M - 1
2. 2k + M <= M - 1
3. 2k + 2M <= M - 1

上述三式只在 1. (`n` 為 3 的倍數) 成立，符合預期結果
## 測驗 `5`
考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) 的實作如下:
```c=
#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](https://man7.org/linux/man-pages/man3/tolower.3.html)，需要留意到在不同的語系 (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`，程式碼列表如下:
```c=
#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(0x80)) == 0) { /* is ASCII? */ // VV1 = 0x80
            uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0); // VV2 = 0
            uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1)); // VV3 = -1           
            uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2; // VV4 = 0x80
            *chunk ^= mask;
        } else
            strlower(s, 8);
    }
    
    k = n % 8;
    if (k)
        strlower(s, k);
}
```
對應的測試程式碼如下:
```c=
#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

:::success
延伸問題:
1. 解釋上述程式的原理;
2. 將前述測試程式 `main` 函式的 `char str[]` 更換為 `char *str`，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
:::
### 延伸問題1.
- `PACKED_BYTE(b)` 的用意是將 b 的最小 byte 值填滿 8 bytes
    - e.g. PACKED_BYTE(0x80) = 0x8080808080808080
- `A`, `Z` 用來判斷輸入字元是否介於 ASCII A ~ Z 
    我們判斷字元 `c` 是否介於 ASCII A ~ Z 會使用以下判斷式
    ```c=
    if('A' <= c && c <= 'Z')
    ```
    `128 - 'A' + 0` 表示 `A` 到 128 的位移量，如果 `c + 128 - 'A' + 0` 的 MSB 為 1，代表 `'A' <= c`
    `128 - 'Z' + (-1)` 表示 `Ｚ` 到 127 的位移量，如果 `c + 128 - 'Z' + (-1)` 的 MSB 為 1，代表 `c > 'Z'`，MSB 為 0 代表 `c <= 'Z'`
    要達成 c 介於 ASCII A ~ Z 的條件為 `A ^ Z == 1` 即滿足 `A` 的 MSB 為 1，`Z` 的 MSB 為 0

| char | hex | binary |
| -------- | -------- | -------- |
| `'A'`~`'Z'`     |  `0x41` ~ `0x5A`    | `0100 0001` ~ `0101 1010`     |
| `'a'`~`'z'`     |  `0x61` ~ `0x7A`    | `0110 0001` ~ `0111 1010`     |
- 由上表可觀察出，大小寫 ASCII 字母的關鍵差異是 `0010 0000` 左邊數第 3 個位元
    若已知輸入字元 `c` 介於 ASCII A ~ Z ，執行 `c ^= 0010 0000b` 可將 `c` 轉為小寫字母，搭配前面判斷大寫的 `A ^ Z` 可完成大小寫轉換的 `mask`
    ```c=16
    uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2; // VV4 = 0x80
    *chunk ^= mask;
    ```
### 延伸問題2.

## 測驗 `6` 
LeetCode [137. Single Number II](https://leetcode.com/problems/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](https://leetcode.com/problems/single-number-ii/) 的題解:
```c=
int singleNumber(int *nums, int numsSize)
{
    int lower = 0, higher = 0;
    for (int i = 0; i < numsSize; i++) {
        lower ^= nums[i];
        lower &= ~higher; // KKK = ~higher
        higher ^= nums[i];
        higher &= ~lower;  // JJJ = ~lower
    }
    return lower;
} 
```
:::success
延伸問題:
1. 解釋上述程式的原理;
2. 請撰寫不同上述的程式碼，並確保在 LeetCode [137. Single Number II](https://leetcode.com/problems/single-number-ii/) 執行結果正確且不超時;
3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
:::
### 延伸問題 1.
我們可以將每個整數的位元獨立看待，當一個位元 Set 3 次必須用 2 個位元來紀錄狀態轉換
00 -> 該位元 Set 0 次
01 -> 該位元 Set 1 次
10 -> 該位元 Set 2 次
00 -> 該位元 Set 3 次
總共分為三個狀態轉換：00→01→10→00。針對這個變化規律，我們可以得到一個真值表：


| higher_bit | lower_bit | input |higher_bit_output | lower_bit_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    |
將真值表轉為邏輯表達式：

$lower_{out} = lower\cdot \neg higher\cdot \neg in + \neg lower\cdot \neg higher\cdot in \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ = \neg higher \cdot (lower\cdot\neg in+\neg lower\cdot in) \\ 
\ \ \ \ \ \ \ \ \ \ \ \ \ \ = \neg higher \cdot(lower \oplus in)$
$higher_{out} = higher \cdot \neg lower_{out} \cdot \neg in + \neg higher \cdot \neg lower_{out} \cdot in \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\neg lower_{out} \cdot (higher \cdot \neg in + \neg higher \cdot in) \\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = \neg in \cdot (higher \oplus in)$
對應到程式碼 5~8 行：
```cpp=5
        lower ^= nums[i];
        lower &= ~higher; // KKK = ~higher
        higher ^= nums[i];
        higher &= ~lower;  // JJJ = ~lower
```

### 延伸問題 2.
### 延伸問題 2.
### 延伸問題 3.

