# 2020q3 Homework2 (quiz2)
contributed by < [`OliveLake`](https://github.com/OliveLake/lab0-c.git) >

- ==[quiz2 題目](https://hackmd.io/@sysprog/2020-quiz2)==
### Q1:

if (str[i] & 0x80)

要判斷是否為有效的 ASCII 字元只需確認第 8 位元( MSB )是否有值。
16 進位的`0x80`= 1000 0000 ，透過 `&`可以判斷 MSB 是否為 1 ，若是則超過範圍( 8 bit )。
在 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;
}

`其中 __uint64_t 是 GCC extension，用以表示 64 位元的無號數值。`

memcpy(&payload, str + i, 8);

透過 memcpy() 抓取 str 字串的前八個 byte 做比對，每一個 byte 都和一組 `0x80` 做 `&` ，所以 MMM 應選 `0x8080808080808080` 。

MMM = ?

- [ ] `(a) 0x0080008000800080`
- [ ] `(b) 0x8000800080008000`
- [ ] `(c) 0x0808080808080808`
- [x] `(d) 0x8080808080808080`
- [ ] `(e) 0x8888888888888888`
- [ ] `(f) 0xFFFFFFFFFFFFFFFF`

### 延伸問題
::::info
1.為何特別用到 memcpy 呢？
::::
memcpy() 常見的實做是先檢查 memory address 是否 word aligned，如果不是，就先 copy 前幾 bytes 讓目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快。
所以，當資料來源和要寫入的目的記憶體區塊有部份重疊的時候，就不能使用。
例如 strcpy(str, str+1) 這種狀況，就只能每個 byte 逐一 copy 才是安全的。
::::info
2.將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
::::
TODO
::::info
3.承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
::::
TODO
### Q2:

 uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & MASK;
    const uint8_t shift = (letter >> AAA) | (letter >> BBB);
    return (in + shift) & 0xf;
}

| char | hex | binary |
| -------- | -------- | -------- |
| 0 | 0x30 | 0011 0000 |
| 9 | 0x39 | 0011 1001 |
| A | 0x41 | 0100 0001 |
| a | 0x61 | 0110 0001 |
| F | 0x46 | 0100 0110 |
| f | 0x66 | 0110 0110 |
| | 0xf | 0000 1111 |

由 `return (in + shift) & 0xf` 可以知道最後會 return 4 bits ，因此 `MASK` 應為 `0x40` ，由表格可以看到`'F'` 和 `'f'` 、`'A'` 和 `'a'` 的共同位數也是 4 bits ，因此確定 `MASK` 為 `0x40`。

MASK = ?
- [ ] `(a) 0x10`
- [ ] `(b) 0x20`
- [x] `(c) 0x40`
- [ ] `(d) 0x60`
- [ ] `(e) 0x80`

| char | hex | binary |
| -------- | -------- | -------- |
| MASK | 0x40 | 0100 0000 |
由`'F'` 和 `'f'` 的回傳值都是15(1111)可以知道 `shift` 為 `1001` ，回推 `letter` 需兩次右移3和6。

- [x] `(a) 3`
- [ ] `(b) 2`
- [ ] `(c) 1`
- [ ] `(d) 0`

BBB = ?

- [ ] `(a) 7`
- [x] `(b) 6`
- [ ] `(c) 5`
- [ ] `(d) 4`

### 延伸問題

::::info
1.將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
::::
TODO

### Q3:
* 快速除法運算

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 位元的無號數值。`
`return n - quotient * D` 符合除法公式： 餘數 = 被除數 - 除數 * 商 ，即
$$
R=n- [\dfrac{n}{3}] * D
$$
又
$$[\dfrac{n}{3}]=n \times \frac{\frac{2 ^ N}{D}}{2 ^ N}
$$
`M`應為 ${\frac{2 ^ N}{D}}$ ， N = 64 ，`XXX` 最接近${\frac{2 ^ {64}}{D}}$ 的值是 `0xFFFFFFFFFFFFFFF`。

#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)

需要再 `+1` 是為了再補回忽略的小數。
XXX = ?

- [ ] `(a) 0x00F000F000F00080`
- [ ] `(b) 0xF000F000F000F000`
- [ ] `(c) 0x0F0F0F0F0F0F0F0F`
- [ ] `(d) 0xF0F0F0F0F0F0F0F0`
- [ ] `(e) 0x8888888888888888`
- [x] `(f) 0xFFFFFFFFFFFFFFFF`

### 延伸問題

::::info
1.由 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) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
::::
TODO

### Q4:
承上題，判斷某個數值能否被指定的除數所整除， D 和 M 沿用

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

因為
$$
n*M = ( n\%D )\times 2^{64}
$$
且
$$M = {\frac{2 ^ {64}}{D}+1} ， M - 1 = {\frac{2 ^ {64}}{D}}
$$
若不整除則$( n\%D ) = 1$ 或 $2$
$$
n*M > M - 1
$$
反之整除則 $( n\%D ) = 0$，則
$$
n*M <= M - 1
$$

YYY = ?

- [ ] `(a) M + 1`
- [ ] `(b) M`
- [x] `(c) M-1`
- [ ] `(d) (M >> 1)`
- [ ] `(e) (M << 1)`

### Q5:
考慮 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]);
    }
}

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

VV1 = ?

- [ ] `(a) 0x10`
- [ ] `(b) 0x20`
- [ ] `(c) 0x40`
- [ ] `(d) 0x60`
- [x] `(e) 0x80`

VV2 = ?

- [ ] `(a) (-1)`
- [x] `(b) 0`
- [ ] `(c) 1`

VV3 = ?

- [x] `(a) (-1)`
- [ ] `(b) 0`
- [ ] `(c) 1`

VV4 = ?

- [ ] `(a) 0x10`
- [ ] `(b) 0x20`
- [ ] `(c) 0x40`
- [ ] `(d) 0x60`
- [x] `(e) 0x80`

::::info
1.將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
::::
TODO

### Q6:

考慮以下程式碼為 LeetCode [137. Single Number II](https://leetcode.com/problems/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 = ?

- [ ] `(a) higher`
- [ ] `(b) lower`
- [x] `(c) ~higher`
- [ ] `(d) ~lower`
- [ ] `(e) 0xFFFFFFFF`

JJJ = ?

- [ ] `(a) higher`
- [ ] `(b) lower`
- [ ] `(c) ~higher`
- [x] `(d) ~lower`
- [ ] `(e) 0xFFFFFFFF`

::::info
1.請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時
::::
TODO

::::info
2.延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼
::::
TODO