# 2020q3 Homework2 (quiz2)
###### tags: `sysprog2020` `homework`
contributed by < `JKChun` >
> [題目](https://hackmd.io/@sysprog/2020-quiz2)
## 測驗 `1`
```c=
#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
```c=
#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`
```c=
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`
```c=
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`
```cpp
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
### 程式原理
no idea
**TODO !!**
## 測驗 `5`
```c=
#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`
```c=
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 為:
```cpp
lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;
```
### 延伸問題
>1. 請撰寫不同上述的程式碼,並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
>2. 延伸題意,將重複 3 次改為改為重複 4 次或 5 次,並找出可容易推廣到多次的程式碼;
**TODO !!**