# 2020q3 第 2 週測驗題
## 測驗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;
}

因為逐一比對字元的效率比較低，所以本題題目使用```memcpy()```把8個字元存到同一個變數中，並使用```& MMM```去判斷是否為ASCII code，而ASCII code的正常範圍在```0x00```~```0x7F```之間，若要判斷是否為ASCII code，只要判斷其數值小於```0x80```即可，所以每個字元去```& 0x80```若答案大於 0 則代表該字元的MSB等於 1 ，也代表其數值大於等於```0x80```即可回傳```false```。
- ### 判斷輸入是否為有效英文字元

bool is_ch(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);
        payload |= 0x2020202020202020;  //turn to lower case
        if(!(payload) & 0x4040404040404040){
            return false;
        }else{
            payload &= 0x1F1F1F1F1F1F1F1F; //only final 5 bits
            bool smaller_than_a = (payload - 0x0101010101010101) & ~(payload) & 0x8080808080808080;
            bool bigger_than_z = ~(payload - 0x1B1B1B1B1B1B1B1B) & 0x8080808080808080;
            if(smaller_than_a || bigger_than_z){
                return false;
            }
        }
        i += 8;
    }
    while(i < size){
        uint8_t payload;
        memcpy(&payload, str + i, 1);
        payload |= 0x20;
        if(!(payload & 0x40)){
            return false;
        }else{
            payload &= 0x1F;
            bool smaller_than_a = (payload - 0x01) & ~(payload) & 0x80;
            bool bigger_than_z = ~(payload - 0x1B) & 0x80;
            if(smaller_than_a || bigger_than_z){
                return false;
            }
        }
        i++;
    }
    return true;
}

1.把由左數來第三個bit改成1（若該字元為大寫英文轉成小寫英文）。
2.檢查由左數來第二個bit是否為1（此為英文字母ASCII code的特徵）。
3.smaller_than_a參考[bitwise操作](https://hackmd.io/@sysprog/c-bitwise)去判斷比```'a'```還要小（只剩```0x00```這個值)的狀況。
4.bigger_than_z去判斷扣掉```0x1B```(比```'z'```多1)後，是否有overflow，如果有則比```z```還要小。
## 測驗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;
}

第3行希望把英文跟數字分開，觀察下來，發現英文跟數字的差別如下：

graph G{
    rankdir=TB
    node[shape=record]
    A[label = "數字|0011 xxxx"]
    B[label = "英文|01x0 xxxx"]
}

所以只要判斷左邊數來第二個或第四個bit就可以了，所以若```letter = 0```時為數字時```mask = 0x 40```，若```letter = 0```時為英文時```mask = 0x10```。
但看最後一行的```return (in + shift ) & 0xf```可以看出，如果```in```為數字，且令```shift = 0```，```return```為```in```，所以可以猜測```mask = 0x40```。
如果要把英文轉為數字，觀察規律可以發現只要+9就可以了，所以這第四行這邊只是在湊數字，讓```shift = 9```就可以了。

結論：如果是數字，直接輸出就好，如果是英文，要+9再輸出。

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

$M = \dfrac{XXX}{D} + 1$
$quotient = M * n * \dfrac{1}{2^{64}}$
$return = n - quotient * D$
先計算 $M$：

$M = \dfrac{XXX}{D} + 1$

由題目指示與第6行後面的```>>64```可以推測$XXX$與 $2^{64}$ 接近，但因為$XXX$為 64bits，如果直接存 $2^{64}$ 會overflow，所以

$XXX = 0xFFFFFFFFFFFFFFFF$

下一行

$quotient = M * n * \dfrac{1}{2^{64}}$

代入$M$

$quotient = (\dfrac{2^{64}-1}{D} + 1) * n * \dfrac{1}{2^{64}}$

化簡

$quotient = \dfrac{n}{D} + \dfrac{n(D-1)}{2^{64}*D}$

此時如果要獲得餘數，只要$n - \dfrac{n}{D}$即可，而如果$quotient$後面那項只要$< 1$，即不能被```unsigned integer```儲存，所以證明$\dfrac{n(D-1)}{2^{64}*D}<1$
化簡：

$n - \dfrac{n}{D} < 2^{64}$

又 $n < 2^{32}$ ， $D>=1$

所以 $n - \dfrac{n}{D} < 2^{64}$ 成立。

## 測驗4
- ### 運作原理

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

代入$M*n$

$M * n = \dfrac{n}{D} (2^{64} - 1) + n$

令 $T = (2^{64}-1)$，$M * n = n(\dfrac{1}{D} * T + 1)$

先看前面部份$\dfrac{n}{D}(2^{64} - 1)$，如果整除，因為變數的type為```uint64_t```所以 $2^{64}$ 不論乘哪個整數，都會因為overflow而直接變成 $0$ ，減去商一次overflow相等於 $2^{64} - \dfrac{n}{D}$，在加上後面部份的 $n$ ，且 $n >= \dfrac{n}{D}$，所以又會在overflow一次，在整除狀況下 $M * n = n - \dfrac{n}{D} = n(1 - \dfrac{1}{D})$ ，而在variable type的限制下，$M *n$ 的最小值發生在 $n = 0$ ，此時 $M * n = 0$；最大值發生在 $n = 2^{32} - 1$ ，此時 $M * n = \dfrac{(2^{32}-1)(D-1)}{D}$，得在整除時：

$0 <= M *n <= \dfrac{(2^{32}-1)(D-1)}{D}$

而在非整除的狀況下，$M * n$ 的最小值發生在 $n = 1$， 此時 $M * n = \dfrac{2^{64}-1}{D}+1$；最大值發生在 $n = 2^{32} - 2$ ， $D = 2^{32} - 1$ ，此時 $M * n = 2^{64} - 4$ ，得在非整除時：

$2^{32} + 2 <= M * n <= 2^{64} - 4$

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