# 2020q3 Homework2 (quiz2)
contributed by < `carlhutant` >

[TOC]
## 測驗 1

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

char size 為 1 byte
若只使用 7 位元編碼 則須確保 MSB 為 0
因此跟 10000000(0x80) 做 and 即可
一次比對 64 位元時，將 8 個 char 合起來
因此將 8 個 0x80 合起來即可
`MMM = (d) 0x8080808080808080`

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

第三行判斷 in 是否為字母
因為字母皆有 0x01X0 XXXX 的特徵
所以與 0x0100 0000 and 可得到 0x0100 0000
`MASK = (c) 0x40`

第五行的 & 將所有輸入高位的 byte 去除
從觀察可發現 0~1 剛好變成 0~1
a~f 與 A~F 都變成 1~6 全都加 9 就達到目標
因此 shift 為 0x0000 1001

可知第四行原本 letter 為 0x0100 0000
應該右移 3 與 6
`AAA = (a) 3`
`BBB = (b) 6`

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

目標是要達到 $\dfrac{n}{D} = \dfrac{X}{D} \times \dfrac{n}{X}$
$\dfrac{X}{D}$ 可事先算好並重複使用， $\dfrac{n}{X}$ 可透過 shift 就達到
因此只須做乘法計算
從第六行可知 X 應該為 $2^{64}$
但選項中沒有，而且第二行最後還做了加一的行為
那我們就先設 XXX 為 $2^{64}-x$
第六行會變成 :

uint64_t quotient = ((__uint128_t) ((uint64_t)(UINT64_C(XXX) / (D) + 1)) * n) >> 64;

(UINT64_C(XXX) / (D) + 1)) 先計算，結果為 $\left\lfloor{\dfrac{2^{64}-x}{D}} \right\rfloor+1$ ，為整數，因為是 int 運算，小數捨去
也可表示成 $\dfrac{2^{64}-x-r}{D}+1$ ，也為整數， 其中 $r$ 為 $2^{64}-x$ 除以 D 的餘數

接著乘 n ，結果為 $\dfrac{n\times2^{64}-nx-nr}{D}+n$ ，為整數

接著向右 shift 64 bits 可視為除以 $2^{64}$ 後捨去小數

結果為 $\left\lfloor\dfrac{n}{D}-\dfrac{nx}{D\times2^{64}}-\dfrac{nr}{D\times2^{64}}+\dfrac{n}{2^{64}}\right\rfloor=\left\lfloor\dfrac{n}{D}+\dfrac{\dfrac{-nx-nr+nD}{2^{64}}}{D}\right\rfloor$

因為我們希望最終結果等於$\left\lfloor\dfrac{n}{D}\right\rfloor$

所以必須確保 $-R<=\dfrac{n(-x-r+D)}{2^{64}}<D-R$ ，其中 $R$ 為 $n$ 除以 $D$ 的餘數

由題目可知 :
1. $n$ 為 32 bits uint
2. $x$ 由選項 A~F 決定，可為 0x0~0xFFFFFFFFFFFFFFFF 的 64 bits uint
3. $r$ 為 $2^{64}-x$ 除以 D 的餘數，範圍在 0~D-1 的 32 bits uint
4. $D$ 為 32 bits uint

發現可透過 $x$ 將 $(-x-r+D)$ 限制在 $2^{32}$ 以內的正數
兩個 32 bits uint 相乘不會超過 64bits

達到 $-R<=0<=\dfrac{n(-x-r+D)}{2^{64}}<1<=D-R$

$D-r$ 的範圍在 $2^{32}$~$1$ ( $2^{32}$ 不確定，但最小是 1 )，所以 $x$ 就只能是 0 或 1 了
`XXX = (f) 0xFFFFFFFFFFFFFFFF`
推測使用 0xFFFFFFFFFFFFFFFF 而非 0xFFFFFFFFFFFFFFFF + 1 是為了記憶體操作方便
## 測驗 4

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

此設計的核心建立在 uint64_t 乘法發生的 overflow 上

$D \times (\left\lfloor{\dfrac{2^{64}-1}{D}} \right\rfloor+1)$ 可能為 $2^{64}-1+D$ 或是 $2^{64}-1-r+D$ 其中 $r$ 為 $2^{64}-1$ 除以 D 的餘數

以上兩者皆大於 0xFFFFFFFFFFFFFFFF 因此會 overflow ，在 uint64_t 表示下會是 $D$ 或是 $D-r$

接著 $n$ 可以拆解為 $t \times D + s$ ，其中 $t$ 與 $s$ 皆為非負整數， $s$ 小於 $D$

$t \times D \times M$ 會 overflow ，在 uint64_t 下是 $t \times D$ 或是 $t \times (D-r)$

$s$ 最大為 $D-1$ 乘上 $M$ 可能為以下兩者 :

1. $\dfrac{2^{64}-1}{D}$ 為整數 -> $2^{64}-1+D-(\dfrac{2^{64}-1}{D}+1)$

2. $\dfrac{2^{64}-1}{D}$ 不為整數 -> $2^{64}-1-r+D-(\dfrac{2^{64}-1-r}{D}+1)$

因為 $D$ 為 32 bits uint ， 0xFFFFFFFFFFFFFFFF 除以任何 32 bits uint 的商皆會大於除數，也就是分數部分大於 $D$ ，第二種雖然有 $-r$ 但只會使其整除不會改變整數部分

因此兩者都必小於 $2^{64}$ 也就是不會 overflow ，所以只要 $s>0$ 結果必定大於 $M$
此設計就是 $n$ 拆解為 $t \times D + s$ ，只要 $s>0$， $n \times M$ 就至少為 $M$ ，只要 $s=0$， $n \times M$ 就因為 overflow 小於 $M$ ( 或是 $t=0$ )

但如何確保 $s>0$ 時，$s \times M$ 不會因為加上 $t \times D \times M$ 的結果而 overflow 變成小於 $M$ ?
首先 $t \times D \times M$ 在 uint64_t 下為 $t \times D$ 或是 $t \times (D-r)$ 皆小於 $2^{32}$
$$
\begin{align}
s \times M &\leq (D-1)\times M\\
&=(D-1)(\dfrac{2^{64}-1-r}{D}+1)\\
&\leq\frac{(D-1)2^{64}}{D}\\
&=2^{64}(1-\dfrac{1}{D})\\
&<2^{64}(1-\dfrac{1}{2^{32}})\\
&=2^{64}-2^{32}
\end{align}
$$
則 $(t \times D) + (s \times M) < (2^{32})+(2^{64}-2^{32})$
不會 overflow ，也就是會大於等於 $M$
`YYY = (c) M - 1`
## 測驗 5

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

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

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

程式要做的就只有 1.找出 A~Z 的字元 2.將該字元第 6 個 bit 設為 1
但為了要加速，避免使用 if else 判斷式，並且一次處理 8 個 char
真正改變 bits 的位置在第 16 行，而且從使用 exclusive or 可知道 mask 一定會根據對應的 char 不同而變化，若對應 A~Z 為 0x20 否則為 0x00
在往上看到 `mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2`
可知 `(A ^ Z) & PACKED_BYTE(VV4)` 會是由 0x80 或 0x00 共八個組成
那`PACKED_BYTE(VV4)` 就可能是 0x8080808080808080 並且由 `(A ^ Z)` 對應的 bits 來決定要保留還是改成 0x00

`VV4 = (e) 0x80`

可知當 char 位於 A~Z 時，A 與 Z 該位置的 MSB 彼此會不同
看到 13 14 行， `128 - 'A'` 與 `128 - 'Z'` 為字元到 0x80 的差，此字元以上的 char 加此值 MSB 都會為 1 ，但我們要的是一個 1 一個 0 ，因為選項只有 1 0 -1 所以選擇 "大於等於 A 的 MSB 為 1" 與 "小於 Z+1 的 MSB 為 0"

`VV2 = (b) 0`
`VV3 = (a) (-1)`

但是要避免加上 A 與 Z 後超出 0xff 影響其他 char ，必須將每個 char 的值限制在 0x7f 以下，也就是 MSB 為 0 ，因此在第 12 行將有大於 0x7f 的資料 8 筆一起交由 strlower 處理
`VV1 = (e) 0x80`

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

當ㄧ個數與其他 xor 在一起後可再次 xor 相同的其他數還原出此數
可想成第一次 xor 會將數字的 information 加入，第二次則會移除
本設計為第一次出現的資訊會出現在 lower 第二次會從 lower 中移除但加入 higher 中 第三次會從 higher 中移除
`KKK = ~higher`
`JJJ = ~lower`