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

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

## 測驗 `1`

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101)

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 #(MMM) )
            return false;
        i += 8;
    }
    while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }
    return true;
}

### 程式原理
一個 char 是1個 byte，也就是8 bit，只要跟 `1000 0000 (0x80)` 做 `AND` 運算，就可以確定是不是有效的 ASCII 字元(因為128~255第8個 bit 一定是1)，在64位元的系統中，可以一次處理8個字元，所以 mask 是 `0x8080808080808080` ，而`while` 迴圈中的 `i` 一次加8個，由於字元的總數不一定是8的倍數，最後的 `while` 迴圈用原本的方法一個字元慢慢檢查

### 延伸問題
>1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性
>2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
>3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4
#### 為何用到 memcpy ?
#### 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
A~Z: 0x41~0x5A
a~z: 0x61~0x7A

#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;
        }
        uint64_t a = payload + PACKED_BYTE(128 - 'a' );  
        uint64_t z = payload + PACKED_BYTE(128 - 'z' - 1); 
        uint64_t A = payload + PACKED_BYTE(128 - 'A' );  
        uint64_t Z = payload + PACKED_BYTE(128 - 'Z' - 1); 

        uint64_t lower = (a ^ z) & PACKED_BYTE(0x80);
        uint64_t upper = (A ^ Z) & PACKED_BYTE(0x80);
        
        if ( ( lower || upper ) ){
            return true;
        }
        i += 8;
    }
    while (i < size) {
        uint64_t a = payload + (128 - 'a' );  
        uint64_t z = payload + (128 - 'z' - 1); 
        uint64_t A = payload + (128 - 'A' );  
        uint64_t Z = payload + (128 - 'Z' - 1); 

        uint64_t lower = (a ^ z) & 0x80;
        uint64_t upper = (A ^ Z) & 0x80;
        if (( lower || upper ))
            return true;
        i++;
    }
    return false;
}

#### 考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對

## 測驗 `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;
}

+ `'0'`, `'1'`, `'2'`, …, `'9'` 對應到 `0x30`, `0x31`, `0x32`, … `0x39`
+ `'a'`, `'b'`, `'c'`, …, `'f'` (小寫) 對應到 `0x61`, `0x62`, `0x63`, …, `0x66`
+ `'A'`, `'B'`, `'C'`, …, `'F'` 對應到 `0x41`, `0x42`, `0x43`, …, `0x46`
### 程式原理
第一行是在判斷輸入是字母還是數字，由於數字0~9的 ASCII 的前4bit 都是`0011`，而大寫和小寫的字母的 ASCII 的前4bit分別是`0100`和`0110`，所以把輸入 `in` 和`0x40`(**MASK**)做 AND 運算就能辨別輸入是字母還是數字：
| 輸入 | letter 的值 |
| -------- | -------- |
| 數字 | 0000 0000 |
| 字母 | 0100 0000 |

先看最後一行的 `return`，裡面有 `& 0xf`，這代表只取 `in + shift` 的後4bit，再看數字0~9的 ASCII 的後4bit 剛好就是對應的0~9，所以 `shift` 在輸入是字母的時候不是0，在輸入是數字的時候是某個數，接下來看大寫和小寫的字母的 ASCII 的後4bit，發現大寫和小寫的後4bit 都是一樣的，且只和對應的十進位數值差9，所以在輸入是字母時，shift的值為`0x09`，因此在第二行將 letter 向右位移3(**AAA**)和6(**BBB**)並做 OR 運算得到`0x09`

| 字母 | ASCII | 對應的十進位 |
| --- | ----- | -------- |
| a | 0110 0001 | 10 |
| A | 0100 0001 | 10 |
### 延伸問題
>將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值 [`Hexspeak`](https://en.wikipedia.org/wiki/Hexspeak)

**TODO !!**

## 測驗 `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;
}

### 程式原理
找餘數的想法：$n\ mod\ d\ =\ n\ -\lfloor(\frac{n}{d})\rfloor * d$
目標：找出 $\lfloor(\frac{n}{d})\rfloor$，$\frac{n}{d}$ 的**商**

數學式 $\frac{n}{d} = n * \frac{\frac{2^N}{d}}{2^N} = n * M * \frac{1}{2^N}$
為什麼程式中的 $M = \frac{2^{64}-1}{d}+1$ ?
現在還不知道 **TODO!!**
參考了 `sammer1107` 的推導以及他對 `jemalloc` 的講解
>**只要今天 n 是被 d 整除且我們選擇的 k 夠大**，我們就可以用 $\lceil\frac{2^k}{d}\rceil$ 當作 magic number $M$。**要做除法時就做 $n \cdot M \cdot \frac{1}{2^k}$ 即可**，對應到 c 語言中，即是乘法與位移兩個動作。

>According to division rule, we can say that $n = qd + r$ for some $q,r \in N$ and $r < d$. Then, we have
$\lfloor\lceil\frac{2^k}{d}\rceil * n * \frac{1}{2^k}\rfloor =\ q\ +\ \lfloor\frac{r}{d}+\frac{r'}{d} * \frac{n}{2^k}\rfloor.$
>The first and second equality comes from the same reasoning in the jemalloc case. The third equality comes from the fact that $\frac{n}{d} = q+\frac{r}{d}$. The final equality stands because $q$ is an integer.
The final line equals to $q$ only if $\frac{r}{d}+\frac{r'}{d} \cdot \frac{n}{2^k} < 1$.

因為在 $2^k$ 不整除於 d 的時候，M 會得到 $\lfloor\frac{2^k}{d}\rfloor$ ，為了讓程式在計算 M 時都可以得到 $\lceil\frac{2^k}{d}\rceil$ 這個結果，所以讓 $M = \frac{2^{64}-1}{d}+1$ 。
### 延伸問題
**TODO !!**

## 測驗 `4`

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

### 程式原理
no idea
**TODO !!**
## 測驗 `5`

#include <ctype.h>
#include <stddef.h>
#include <stdint.h>

#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101)

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

###
- 開頭的 `#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)` 是用來取 b 的後4 bit 並複製8次，如：0x23，則結果為 0x2323232323232323
- 第一個 if branch 要判斷8個字元裡有沒有不是 ASCII 的，所以 VV1 為 0x80
- 先看 `*chunk ^= mask` 可以得出如果字元在 A~Z 之間則 `mask` 一定是 0x20，不然就是 0x00，來轉小寫，所以 `((A ^ Z) & PACKED_BYTE(VV4))` 的值在 A~Z 之間要 0x80
- 又中間是做 `AND` 運算，所以 `VV4` 為 0x80
- 為了讓 `A 和 Z` 的第 8 bit 不一樣，所以選擇 VV2 = 0, VV3 = -1，讓在 A~Z 之間的字元經過加法後，變數 `A` 可以大於 128 而變數 `Z` 可以小於 128，不是在 A~Z 之間的字元經過加法後，變數 `A 和 Z` 不是都大於要不就都小於 128 。

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

**TODO !!**

## 測驗 `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;
} 

### 程式原理
- 很重要的一點是每個 bit 是獨立的，只要管 bit 的1跟0出現幾次就好，舉例：[1, 2, 1, 2, 3, 2, 1]，換成 binary 就是[01, 10, 01, 10, 11, 10, 01]，以題目的規則看，每個 bit 不是1出現 3n 次，0出現 3n + 1 次，就是0出現 3n 次，1出現 3n + 1 次，$n\in0,1,2,3,\ ......$。
- 所以題目用 `lower` 紀錄出現一次的 bit，`higher` 紀錄出現兩次的 bit，而且只有在`lower` 為0 `higher` 才能為1，只有在 `higher` 為0 `lower` 才能為1，假如已經出現過兩次了接著又出現了，代表出現第三次，那 `lower` 和 `higher` 的 bit 皆為0
- 舉例：參考 `joey3639570`

>以**5 (101)** 為例:
>
>**第一次**
000 ^ 101 = 101 (`lower ^=`)
101 & 111 = 101 (`lower &= ~higher`)
000 ^ 101 = 101 (`higher ^=`)
101 & 010 = 000 (`higher &= ~lower`)
結果而論 `lower` 為 101 ， `higher` 為 000
>
>**第二次**
101 ^ 101 = 000 (`lower ^=`)
000 & 111 = 000 (`lower &= ~higher`)
000 ^ 101 = 101 (`higher ^=`)
101 & 111 = 101 (`higher &= ~lower`)
結果而論 `lower` 為 000 ， `higher` 為 101
>
>**第三次**
000 ^ 101 = 101 (`lower ^=`)
101 & 010 = 000 (`lower &= ~higher`)
101 ^ 101 = 000 (`higher ^=`)
000 & 111 = 000 (`higher &= ~lower`)
結果而論 `lower` 為 000 ， `higher` 為 000
- 所以 code 為：

lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;

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

**TODO !!**