# 2020q3 Homework2 (quiz2)
contributed by <`joe-U16`>
###### tags: `sysprog2020`

## 測驗 `1`

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

### Q1
:::info
解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
:::

* MMM=0x8080808080808080
* ASCII 定義了0-127 共128個字元，若 payload 這個字元的第 8個 bit 有值，則會讓 `(payload & MMM)` 為 1，進而 return false。
* 在 x86_64 中 unsigned long long 一次對齊是 8 bytes
* 使用memcpy 將 8 個 bytes 大小的字元 payload 這個變數內
### Q2
:::info
將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
:::
### Q3
:::info
承 (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)
:::

## 測驗 `2`

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

### Q1
:::info
解釋上述程式的運作原理;
:::

* `第5行` 跟 `0xf` 做 `&` ，因為要表達的值只有0-15
* 可以發現做 `第5行` 的話 `0-9` 不用處理，就可以得到答案了。
* `f` = 0110 0110
* `F` = 0100 0110
* `9` = 0011 1001
* `9` 不需要shift，所以MASK 是為了讓 `0-9` 跟 `a-f` 做出區別，
* MASK=0x40， `0-9` 不會有 letter ，`a-f` 有letter
* 如果只看 `8` `4` `2` `1` ，4個bit， `f` 為 `0110` 所以想要讓他變 `15` ，要再讓他加 9，所以 AAA=3 BBB=6 可以讓 shift=9
* 成功了
* Ans:
* MASK=0x40
* AAA=3
* BBB=6

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

## 測驗 `3`

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

### Q1
:::info
解釋上述程式的原理;
:::
* $M$ 即為 ${2^N \over d}$
* ${n \over d} = n * {{2^N \over d} \over 2^N}$
* `quodient` 為 ${n \over d}$ 的商數
* 最後n - `quodient` * d 即為餘數。
* Ans:
* `XXX=0xFFFFFFFFFFFFFFFF`

### Q2
:::info
由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
:::

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

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

$n * M$ 即為 $n * ({{2^N-1} \over d}+1)$

* `n * M = n * ((0xFFFFFFFFFFFFFFFF / d) + 1)` => `(n * (0xFFFFFFFFFFFFFFFF / d)) + (n * 1)`
* 如果 n 可被 d 整除，則 $n*M$ 會溢位得到很小的數
* 運用上述規則來判斷 n 是否可整除 d
* 考慮 `n=1` 且 `d=2` ，此條件下 不可整除 n ，函式該 return `0`
* 推導
* $n * ({{2^N-1} \over d}+1)\lt= YYY$
* 代入 n=1 d=2
* $1 * ({{2^N-1} \over 2}+1)\lt= YYY$
* $M <= YYY$ 需return `0`
* 可推知YYY為選項 M-1 或 (M >> 1)
* 找 M>>1的反例
* 如果 n 不可整除 d 則 YYY 需小於 M， (M >> 1) 可達成
* 如果 n 可整除 d 則 YYY 須大於等於 M
* 找不到反例
* M-1 和 (M>>1) 都對

## 測驗 `5`

#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=0x80  VV2=0  VV3=(-1)  VV4=0x80

### Q1
:::info
解釋上述程式的原理
:::
:::success
以下討論為不使用PACKED_BYTE()這個 macro ，使用一個字元8 bits 的情況，可較直觀的理解程式碼的目的。
:::
* VV1
* PACKED_BYTE() 這個 macro 功能是只取 input 前面 8 個 bits ，並將得到的資料重複擴展到 64 bits
* ASCII 定義了0-127 共128個字元 透過 ==#13==` (*chunk & 1000 0000(b)) == 0` 可判斷是否為 ASCII ，若是才繼續做，不是的話就做extended ASCII
* `VV1 = 0x80`
* ==#16== mask
* ==#17== 如果`(*chunk ^= ' ')` ，可讓\*chunk 這個字元大小寫互換，而`' '`即為`0b00100000`
* 若要讓mask 符合此值，==#16==`(A ^ Z)` 的第 8 bit 需為 1
* 再與`0x80`做`&`，可得`0b10000000`
* 再右移2格可得`0b00100000`，即為`' '`
* 可知 `VV4=0x80`
* `A ^ Z` 的第8 bit 為 1
* `A = (*chunk) + (128 - 65 + 0)`，若 \*chunk 大於等於65，則A可得大於128的值
* `B = (*chunk) + (128 - 90 + (-1))`，若 \*chunk 小於等於`90`，則B可得小於128的值
* 可知 `A^Z` 目的為判斷 \*chunk 是否為字元 A-Z ，若是，才需大小寫轉換。

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

* char str[] 更換為 char *str
* 會發生 segmentation fault(core dumped)
* 在[你所不知道的C語言：指標篇](https://hackmd.io/@sysprog/c-prog/%2Fs%2FHyBPr9WGl)中有提到：
* definition/statement, 如 char x[10] →不能變更為 pointer 的形式
* 請參閱 C 語言規格書，說明 string literal 的行為
* 是一種字串常值的型態

## 測驗 `6`

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=~higher  JJJ=~lower

### Q1
:::info
解釋前述程序的原理;
:::

* 取一個例子 [2, 2, 2, 3]
* 第一個迴圈做完後 `lower=2` `higher=0`
* 第二個 `lower=0` `higher=2`
* 第三個迴圈 `lower=0` `higher=0` 像是一切重新計算
* 第四個迴圈 `lower=3` `higher=0` higher = return lower
* 不管排列組合怎麼排，都可以讓數字做三次後就歸零

### Q2
:::info
請撰寫不同上述的程式碼，並確保在[LeetCode 137 Single Number](https://leetcode.com/problems/single-number-ii/) 可成功執行
:::

### Q3
:::info
延伸題意，將重複3次改為重複重複4次或5次，並發現可容易推廣到多次的程式碼;
:::

如果要重複次數為偶數次的話，使用 `Xor` ，利用相同數字 `Xor` 後會為0的特性，即可得解：

int singleNumber(int *nums, int numsSize)
{
    int tmp = 0;
    for (int i = 0; i < numsSize; i++) {
        tmp ^= nums[i];
    }
    return tmp;
}