# 2020 sysprog Homework2 (quiz2)
###### tags: `sysprog`
contributed by < `sciyen` >

[TOC]

## Q1 is_ascii()

題目：

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

已知 extended ASCII 的第8個 bit 為1，若以單一個 byte 來看，用以下方式可以判斷第8個 bit 是否為1

int b = byte & 0x80;

:::info
For example:
0b11000111
0b10000000 -> 0xf0
0b10000000
:::

利用相同方式，若有 8 byte，則 Mask 以一個 byte 為單位，用 8組。

0x8080808080808080

:::warning
**Memory alignment problem**

由於傳入的參數 `str` 可能是記憶體中的任意位置(不一定會 alignment )，因此若直接對該記憶體操作有可能因為 unalignment 必須讀兩個記憶體區段再合併導致效能變差，因此利用 `memcpy()` 強制將記憶體 alignment 後再進行後續操作。
:::

#### 延伸問題 - 給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母

## Q2 hexchar2val()

題目：將十六進位表示的字串 (hexadecimal string) 轉為數值

uint8_t hexchar2val(uint8_t in)
{
    const uint8_t letter = in & 0x40;
    const uint8_t shift = (letter >> 3) | (letter >> 6);
    return (in + shift) & 0xf;
}

:::info
注意 ASCII 中數字與英文字的表示方式
- 數字 0x30~0x39, 前4個 byte 皆為 0b0011
- 小寫英文 0x61~0x66, 前4個 byte 為0b0110
- 大寫英文 0x41~0x46, 前4個 byte 為0b0100
:::

1. 為了判斷是否為英文，利用第一個 MASK 判斷前 4 byte 中的 4 位置是否為1， 因此 MASK 為0x40。因此 `letter` 的意義為 `in` 是 `>=10` 的值。
2. 接下來，若 `in` 是 `>=10` 的值，則必須要創造出一個 `10` 加進去答案裡面，又若 `in>=10` ， `letter` = `0b01000000`，因此將 `letter` 右移3格得到 `0b00001000`，右移6格得到 `0b00000010`，做 or 運算後得到 `0b00001001` 也就是9。
:::warning
| |`0b01000000`|
|-|------------|
|3|`0b00001000`|
|6|`0b00000001`|
|OR|`0b00001001`|
:::
4. 最後將 `in` 與 `shift` 相加，若 `in` 為數字，則 `shift` 為0；若 `in` 為 A~Z 或 a~z ，則 `shift` 為9，由於 A~Z 及 a~z 的後4個 byte 皆對應到 A=1, B=2,...，因此 A 為9+1=10，以此類推...
5. 最後，與0x0f做 `AND 運算`將剩餘的前 4 byte 濾掉。

## Q3 quickmod(uint32_t n)

題目：該算法將除法變形為 乘法 與 shift 的組合。

const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (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;
}

#### 問題解析
由原式中
\begin{equation}
\frac{n}{d}=n \times \frac{\frac{2^N}{d}}{2^N}
\end{equation}
可以發現 `M` 應為式中 $\frac{2^N}{d}$ 的部分，而 `N` 為64，但由於 $2^{64}$ 恰好進一位，導致記憶體位置不夠，因此用 `0xFFFFFFFFFFFFFFFF` 代替，最後再加1。

#### 程式碼說明
1. 對於 `#define` 代表利用預處理器先行計算 `((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (D) + 1))` 並視為 constant 處理，因此可以大幅減少執行時期的計算。
2. 對於式中的 $\frac{1}{2^{64}}$ ，由於其為2的倍數，可以用 shift 快速處理。
:::info
**Proof**
$\frac{2^N}{d}$ 於程式中寫為 $\frac{2^N-1}{d}+1$
假設：商數為 `q` ，餘數為 `r` 且 $q, r \in \mathbb{N}$
依據情況可以分為下列兩種：
- $2^N$ 整除 `d`：
\begin{equation}
\left\{
\begin{array}{lr}
2^N=q\times d \\
2^N-1=(q-1)d+(d-1), \ if \ d>1 \ then \ d-1>0
\end{array}
\right.
\end{equation}
因此 `q` 必定比原式少1
- $2^N$ 不整除 `d`：
\begin{equation}
\left\{
\begin{array}{lr}
2^N=q\times d +r, \ where \ 1<r<d \\
2^N-1=(q-1)d+(r-1)
\end{array}
\right. \\
\because 1<r<d \\
\therefore 0<r-1<d-1
\end{equation}
`d-1`必定無法進位，因此 `q` 必定比原式少1

**結論：**
不管$\frac{2^N-1}{d}$中的 `N` 及 `d` 為多少，所得的 `q` 必定較 $\frac{2^N}{d}$ 少1，因此$\frac{2^N}{d}$ 於程式中寫為 $\frac{2^N-1}{d}+1$。
:::

#### 延伸問題

## Q4 divisible(uint32_t n)

## Q5 strlower

### 解析 `void strlower(char *s, size_t n)` 程式碼原理

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

觀察 ASCII code 可以發現，其大寫字母與小寫字母差在第 5 個 bit ，例如：
A: 0x41 0100 0001
B: 0x61 0110 0001

因此若要將大小寫互換，只要將第 5 個 bit 作 not 運算即可。

### 利用 64 bit 架構做運算
一次對 8 個 byte 做處理以加速計算：

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

- 12行：由於 char array 為連續的記憶體，透過 uint64_t 指標的方式取值可以獲得連續 8 byte 的記憶體。
- 5行：由於要做 64 bit 乘法運算，因此將 `b` 強制轉為 uint64_t ，同時，為確保只有第一個 byte

## 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 &= ~higher;
        higher ^= nums[i];
        higher &= ~lower;
    }
    return lower;
} 

### 首先看 `XOR` 的特性：

XOR 重複做兩次後會變回原本的數字

5: 00000101
5: 00000101
------------
A: 11111111
5: 00000101
------------
A: 00000101

如果從 0 開始，對 0 做 2 次一樣的 `XOR` 後會變回 0 。
**Note**：可以觀察到，對任意數做兩次一樣的 `XOR` 後都會變回原本的數，其原因也很明確，因為相同的數做 `XOR` 後必定全為 1 ，然後任意數對 1 做 `XOR` 後，其值不變。

0: 00000000
5: 00000101
------------
A: 11111010
5: 00000101
------------
A: 00000000

5: 00000101
3: 00000011
------------
A: 11111001
5: 00000101
------------
A: 00000011
5: 00000101
------------
A: 11111001
5: 00000101
------------
A: 00000001