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

## 測驗一

#### 原始版本

* 藉由逐一與`0x80`做`&`檢查是否為 `ASCII` 字元

#include <stddef.h>
bool is_ascii(const char str[], size_t size)
{
    if (size == 0)
        return false;
    for (int i = 0; i < size; i++)
        if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */
            return false;
    return true;
}

#### 修改後， 一次可比8個 `char`

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

* MMM = ?
* (a) 0x0080008000800080
* (b) 0x8000800080008000
* (c\) 0x0808080808080808
* (d) 0x8080808080808080
* (e) 0x8888888888888888
* (f) 0xFFFFFFFFFFFFFFFF

* SOL:
* 由修改前的程式碼可知，要比對一個字元是否為 `ASCII` 字元，需要與`0x80`做`&`，故要比對8個字元便要與8個`0x80`做`&`，即`0x8080808080808080`

* 程式碼解釋:

    int i = 0;
    while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;
    }

* uint64_t為何?([參考](https://blog.csdn.net/Mary19920410/article/details/71518130))
* 這個型別是利用舊有的型別 `typedef` 出來的，具體定義在`/usr/include/stdint.h`，因為跨平台舊有型別可能會有不同字長的問題，用 `typedef` 型別比較好維護

#ifndef __int8_t_defined  
# define __int8_t_defined  
typedef signed char             int8_t;   
typedef short int               int16_t;  
typedef int                     int32_t;  
# if __WORDSIZE == 64  
typedef long int                int64_t;  
# else  
__extension__  
typedef long long int           int64_t;  
# endif  
#endif  
  
  
typedef unsigned char           uint8_t;  
typedef unsigned short int      uint16_t;  
#ifndef __uint32_t_defined  
typedef unsigned int            uint32_t;  
# define __uint32_t_defined  
#endif  
#if __WORDSIZE == 64  
typedef unsigned long int       uint64_t;  
#else  
__extension__  
typedef unsigned long long int  uint64_t;  
#endif

while ((i + 8) <= size) {
        uint64_t payload;
        memcpy(&payload, str + i, 8);
        if (payload & MMM)
            return false;
        i += 8;

* `i` 剛開始設為0，即 `str+i` 是字串陣列的開頭，`memcpy` 的 `size` 設為8，就會把8個字元填入 payload(剛好64-bit)
* 之後與先前提到`0x8080808080808080` 做`&`，不為 `ASCII` 字元的就 return `false` ，之後再將 `i+=8` 繼續比較之後8個 `char`

while (i < size) {
        if (str[i] & 0x80)
            return false;
        i++;
    }

* 這段程式碼跟修改之前的一樣，目的是若最後剩下沒比較的 `char` 數量少於8個，就讓這幾個 `char` 用原本的方法比較

:::success
延伸問題:

1.解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性

:::
* `memcpy()` 會先檢查 memory address 是否 word aligned，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方， ==然後以 word 而不是 byte 為單位做資料 copy。== 同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。[參考](https://www.facebook.com/pcman.im/posts/1623916640981340/)
:::success
2.將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
:::

* 大寫英文字母在 `ASCII` 編碼裡的號碼是65～90，小寫則是97～122，兩者各相差32
* 目前只知道如何判斷介於65～127之間，尚不知道如何只用`&`將其限制在上述兩個範圍之內

if ((payload & 0x4040404040404040) && !(payload & 0x8080808080808080))
            return true;

:::success
3.承 (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)
:::

todo

----
## 測驗二

開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:

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

* MASK = ?
* (a) 0x10
* (b) 0x20
* (c\) 0x40
* (d) 0x60
* (e) 0x80

* AAA = ?
* (a) 3
* (b) 2
* (c\) 1
* (d) 0

* BBB = ?
* (a) 7
* (b) 6
* (c\) 5
* (d) 4

| ASCII | Dec | Hex | Binary |
| --- | --- | --- | -------- |
| 0 | 48 | 0x30 | 0011 0000 |
| 9 | 57 | 0x39 | 0011 1001 |
| A | 65 | 0x41 | 0100 0001 |
| F | 70 | 0x46 | 0100 0110 |
| a | 97 | 0x61 | 0110 0001 |
| f | 102 | 0x66 | 0110 0110 |

:::success
延伸問題:
1.解釋上述程式的運作原理;
:::

* 從前面無法判斷答案，因此我先從最後一行開始看

return (in + shift) & 0xf;

* `0xf` 的二進位表示是`1111`，這行的意思就是 `in + shift` 只回傳後四碼，而 `a~f` 或 `A~F`，同樣字母無論大小寫，後四碼皆相同，範圍是0001\~0110，即1~6，若要讓其以10進位方式表達，則需加上 `shift` => 1001 才能表達10~15
* 由於需要 `shift` 的只有字母，由上表可以得知，字母有一個特徵，就是由左邊數來第二個 `bit`是1，故 `MASK` 為0100 0000，也就是0x40
* `shift` 值必須為1001，可由0100 0000右移3-bit ，及右移6-bit `OR` 起來得到，故 AAA 和 BBB 為3和6

const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);

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

#include <stdint.h>
#include <stdio.h>
#include <string.h>

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

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

uint64_t hexspeak2val(char str[]){

    int len = strlen(str);

    if (len == 1)
        return hexchar2val(str[0]);

    uint64_t total = 0;


    uint64_t i = 2;
    for (; (i + 8) <= len ; i += 8){
        uint64_t in;
        memcpy(&in, str + i, 8);
        
        const uint64_t letter = in & PACKED_BYTE(0x40); 
        const uint64_t shift = (letter >> 3) | (letter >> 6);
        const uint64_t value = (in + shift) & PACKED_BYTE(0x0f);

        for (size_t j = 0; j < 64 ; j += 8)
            total += (( value << j ) >> 56) << (j >> 1);
    }

    for (; i < len ; i++)
        total = total << 4 | hexchar2val(str[i]);

    return total;
}
int main(){
    
}

----
## 測驗三

除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如 $\dfrac{n}{d}$ 在分子和分母分別乘上 $2^N$ 後，得到等價的 $n×\frac{\frac{2^N}{d}}{2^N}$，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當 d (除數) 的數值是已知的狀況下，$\dfrac{2^N}{d}$ 可預先計算，也就是說，$\dfrac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然 $\dfrac{2^N}{d}$ 無法總是用整數來表達 (僅在 d 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。

重新檢視 $\dfrac{n}{d}=n\times\dfrac{\frac{2^N}{d}}{2^N}$，當我們想將 n 除以 4 時，就相當於乘以 0.25，所以我們可將 $\dfrac{5}{4}$ 改為 $5×0.25$，我們得到整數的部分 (即 1)，和小數部分 (即 0.25)，後者乘以 4 就是 1，也就是餘數。下方程式碼展示這概念:

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

其中 __uint128_t 是 GCC extension，用以表示 128 位元的無號數值。

GCC: C Extensions: 128-bit Integers

預期 quickmod(5) 會得到 2, quickmod(55) 得到 1, quickmod(555) 得到 0 (555 是 3 的倍數)。

請補完程式碼。

* XXX = ?
* (a) 0x00F000F000F00080
* (b) 0xF000F000F000F000
* (c\) 0x0F0F0F0F0F0F0F0F
* (d) 0xF0F0F0F0F0F0F0F0
* (e) 0x8888888888888888
* (f) 0xFFFFFFFFFFFFFFFF

:::success
1.解釋上述程式的原理;
:::
* $C99$新增了 ==<stdint.h>== ，其定義了 `UINT64_C(x)` 和 `UINT64_MAX`

#define UINT64_C(x)  ((x) + (UINT64_MAX - UINT64_MAX))
#define UINT64_MAX  0xffffffffffffffff [exact]

* 其功能是將無號整數 `x` 轉為 64-bit 無號整數，至於是 `unsigned long` 還是 `unsigned long long` 則是 `implementation-defined`

uint64_t quotient = ((__uint128_t) M * n) >> 64;

* 由此行程式碼可知，右移64-bit 即是除以$2^N$，即N=64，M為預先計算的$\dfrac{2^{64}} {d}$，但顯然 `XXX` 不能表示$2^{64}$，而且$2^{N}$未必能被d整除，除法會自動去掉小數部分只留下整數部分，也就是商

* 我們要計算$\dfrac{2^N}{d}$，由於整數除法的特性，我們會得到$\lfloor\dfrac{2^N}{d}\rfloor$，但此處按照先前所提的先估算，之後再將差值補回去，所以我們將他改寫成$\dfrac{2^N-1}{d}+1$，也就是$\lceil\dfrac{2^N}{d}\rceil$，實際上的意義就是不管有沒有整除，都無條件進位，得到的答案一樣，但只需要64-bit

#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))

* 故 `XXX` 為$2^{64}-1$ 也就是0xFFFFFFFFFFFFFFFF

uint64_t quotient = ((__uint128_t) M * n) >> 64;
return n - quotient * D;

* 先將 `n` 乘上 `M` (即$\lceil\dfrac{2^{64}}{3}\rceil$)，而且由於上面多乘了$2^{64}$ 所以第7行要右移64-bit 把它消掉(由於這裡使用了128-bit 的 `int` ，所以精準度較64-bit 高)
* 最後就是計算餘數了，由$n = q \times d + remainder$ 可知$remainder = n - q \times d$

#### 參考:
* [stdint.h](https://www.qnx.com/developers/docs/6.4.1/dinkum_en/c99/stdint.html)
* [Purpose of using UINT64_C?](https://github.com/boostorg/config/blob/master/include/boost/cstdint.hpp)

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

----
## 測驗四

延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 D 和 M 都沿用的狀況下，程式碼如下:

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

以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數)

請補完程式碼。

作答區

* YYY = ?
* (a) M + 1
* (b) M
* (c\) M - 1
* (d) (M >> 1)
* (e) (M << 1)

* 已知除數為 $d$ 若 $n$ 能被 $d$ 整除，設 $n = dk$，若不能被 $d$ 整除，則有 $n = dk +1$ ~ $n = dk +(d-1)$種情形
* 若 $n = dk$，則 $n \times M = dk \times (\dfrac{2^{64}-1}{d}+1) = k \times (2^{64}-1 + d) = k(d-1)$
:::info
$2^{64}-1 + d$ => overflow 得到 $d-1$
:::
* 若 $n = dk + 1$，則 $n \times M = (dk+1) \times (\dfrac{2^{64}-1}{d}+1) = k \times (2^{64}-1 + d) + (\dfrac{2^{64}-1}{d}+1) = k(d-1) + M$
* $...$
* 若 $n = dk + (d-1)$，則 $n \times M = (dk+(d-1)) \times (\dfrac{2^{64}-1}{d}+1) = k \times (2^{64}-1 + d) + (d-1)(\dfrac{2^{64}-1}{d}+1) = k(d-1) + (d-1)M$
* 觀察不能被 $d$ 整除的 $n$ 的 $n \times M$ 皆有額外加上常數 $M$ 的倍數，無論 $d$ $or$ $n$ 是多少，不能被整除的 $n$ 其與 $M$ 的乘積皆 $>=M$，而且程式碼給的運算符號是`<=`，故 `YYY` 的值為 $M-1$

:::warning
這樣能成立是建立在 $k(d-1)<M$ 的情況下，不知道是否能確定這個一定成立，感覺當 $d$ 跟 $n$ 大一點就不行了，不過在 $d = 3$的情況下還綽綽有餘
:::

----
## 測驗五

考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) 的實作如下:

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

針對 extended ASCII，我們呼叫 C 語言標準函式庫的 tolower，需要留意到在不同的語系 (locale)，字母順序和大小寫的定義可能異於我們認知的英文字母。以下摘自手冊:

>If c is a lowercase letter, toupper() returns its uppercase equivalent, if an uppercase representation exists in the current locale. Otherwise, it returns c.

語系對程式碼的影響不能輕忽，舉例來說，若語系設定為捷克語，以 “Ch” (屬於 digraph，二合拉丁字母，常見於西歐語言) 開頭的字串要排在 “H” 之後，但單看字母的話，“C” 要在 “B” 之後。不過，如果明確只處理英美語系 (American/British English)，上述程式碼列表的第 9 及第 10 行可略去。

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

對應的測試程式碼如下:

#include <stdio.h>
#include <string.h>
int main()
{
    /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
    char str[] =
        "This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever.  You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
    int n = strlen(str);
    strlower_vector(str, n);
    puts(str);
}

參考執行輸出:

>this ebook is for the use of anyone anywhere at no cost and with almost no restrictions whatsoever. you may copy it, give it away or re-use it under the terms of the project gutenberg license included with this ebook or online at www.gutenberg.net

請補完程式碼。

作答區

* VV1 = ?
* (a) 0x10
* (b) 0x20
* (c\) 0x40
* (d) 0x60
* (e) 0x80

* VV2 = ?
* (a) (-1)
* (b) 0
* (c\) 1

* VV3 = ?
* (a) (-1)
* (b) 0
* (c\) 1

* VV4 = ?
* (a) 0x10
* (b) 0x20
* (c\) 0x40
* (d) 0x60
* (e) 0x80

:::success
延伸問題:
1.解釋上述程式的原理;
:::

if (s[j] >= 'A' && s[j] <= 'Z')
    s[j] ^= 1 << 5;

* 此段程式碼是將大寫的英文字母+32以得到小寫字母(詳見測驗二所提的 `ASCII` 編碼)

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

由上述程式碼可知，PACKED_BYTE會將 b 其 `ASCII` 編碼(16進位)增加成八個，如 'a' 是 0x61 會變成 0x6161616161616161

if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */

這段程式碼是要判斷是否為 `ASCII` 所以 `VV1` 為 0x80

uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2;
    *chunk ^= mask;

由17行可以得出如果字元在 A~Z 之間則 mask 一定是要是0x20或0x00，來轉小寫，所以 ((A ^ Z) & PACKED_BYTE(VV4)) 的值在 A~Z 之間要 0x80

uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); 
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3);

令 VV2 = 0, VV3 = -1，以區別 A, Z 的最後1位，讓在 A~Z 之間的字元經過加法後，A 大於 128 或 Z 小於 128
:::success
將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
:::
會發生 segmentation fault
>C99 6.7.8 Example 8
>EXAMPLE 8 The declaration
char s[] = "abc", t[3] = "abc";
defines "plain" **char** array objects s and t whose elements are initialized with character string literals.
This declaration is identical to
char s[] = { 'a', 'b', 'c', '\0' },
t[] = { 'a', 'b', 'c' };
***The contents of the arrays are modifiable***. On the other hand, the declaration
char *p = "abc";
defines **p** with type "pointer to **char**" and initializes it to point to an object with type "array of char" with length 4 whose elements are initialized with a character string literal. ***If an attempt is made to use p to modify the contents of the array, the behavior is undefined.***

----
## 測驗六

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

lower 為出現過一次數的集合，higher 為出現過兩次數的集合，並於第三行清空

lower ^= nums[i];

若 `num[i]` 已在 lower 裡則清除

lower &= KKK;

若 `num[i]` 不在 lower 裡面，有可能是第一或第三次出現，所以須檢查上次的 higher
因此 KKK=~higher

higher ^= nums[i];

若 `num[i]` 已在 higher 裡則清除

higher &= JJJ;

若 `num[i]` 不在 higher 裡面，有可能是第一或第二次出現，所以須檢查 lower
因此 JJJ=~lower

:::success
請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
:::

int singleNumber(int* nums, int numsSize){
    int one = 0, two = 0, three = 0;
    for (int i = 0; i < numsSize; ++i) {
        two |= one & nums[i];
        one ^= nums[i];
        three = one & two;
        one &= ~three;
        two &= ~three;
    }
    return one;
}

:::success
延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
:::

int singleNumber(int* nums, int numsSize){
    int one = 0, two = 0, three = 0, four = 0, five = 0;
    for (int i = 0; i < numsSize; ++i){
        four |= one & two & three & nums[i];
        three ^= one & two & nums[i];
        two ^= one & nums[i];
        one ^= nums[i];
        five = one & two & three & four;
        one &= ~five;
        two &= ~five;
        three &= ~five;
        four &= ~five;
    }
    return one;
}

上面是重複五次的 code ，只是依照重複三次去的做延伸而已，要重複更多次只須將變數增多並按照這個規則寫下去即可