# 2020q3 Homework2 (quiz2)
contributed by < `Tim096` >
> [測驗題](https://hackmd.io/@sysprog/2020-quiz2)
[TOC]
## 1. ASCII 編碼判斷
目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元
```cpp
#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;
}
```
其中 `str` 是開頭的記憶體地址，`size` 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下:
```cpp=
#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) //payload : 處理的資料區段
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
<font color="#f00">Q : 第12行為何要`str+i`?</font>
A : 這一行有更動到i值
<font color="#f00">Q : 第17~21行為何還需要 ? (是不是怕說不一定是8的倍數)</font>
A : ok
:::info
`memcpy` 常見的實做是先檢查 memory address 是否 ==word aligned==，如果不是會先 copy 前幾 bytes 使目前位址到 word aligned 的地方，然後以 word 而不是 byte 為單位做資料 copy。
因此同樣一個 instruction 可以搬多個 bytes，會比用迴圈每個 byte 逐一 copy 要快，有時候甚至可以用 Intel cpu 特殊的專用指令做一次 copy 整個區塊。
:::
已知 7 位元編碼的字元隸屬於 ASCII，透過 `uint64_t` 也就是 `long int` `payload` 截取 `str` 字串陣列中前8位進行判斷，如下圖所示，與 `0x80` 進行 `&` 運算後必須等於==0==
而 `payload` 內有 8 個bytes對應8個字元，因此每個字元對應一組 `0x80`
MMM = `0x8080808080808080`
白話版本 : 因為ASCII的合法字元為0~127，轉換成 Binary 會發現和 128 做 &`(And)`運算都會等於 ==0==
然後j會發現了這一件事情`Payload`這一件事情，其實就只是藉由64位元架構，一次比8個變成 `0x80` 有8個就變成 MMM 了~
| Hexadecimal | Binary | Decimal |
| ----------- | --------- |---- |
| 0x80 | 1000 0000 | 128 |
| 0x7F | 0111 1111 | 127 |
---
### 檢測英文大小寫字母(進階題)
**給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母**
只要檢測到英文字母，便可`return true`
[檢測英文大小寫字母](https://github.com/Rsysz/quiz2/blob/master/test1.c)
---
## 2. 16進位字串轉換
```cpp=
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & MASK;
const uint8_t shift = (letter >> AAA) | (letter >> BBB);
return (in + shift) & 0x0f;
}
```
MASK = `0x40`
AAA = `3`
BBB = `6`
第三行 : 判斷是否為字母可以藉由以下表格發現規律
第四行 : 這邊其實很特別，建議自己帶一個字母和一個數字就會知道其實很酷的，以下我用 pseudo code 來解釋
```cpp=
第四行程式解釋
if "字母" shift = 0000 1001 (9)
else "0~9" shift = 0000 0000 (0)
```
第五行 : 這邊數字的部分很好理解，但是字母的大小寫的部分之所以可以這樣玩就要追究的到 ASCII ，當初神奇地設計了仔細觀察一下英文字母對應的大小寫都是剛好差距 32(0010 0000)這一個數字就在第三行的時候把利用 `0x40` 剛好的解決掉了這一差異。
> 已知 `in` 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15，且 `hexchar2val('0')` 回傳 0，其他輸入都有對應的數值。 [`Aa(10)` `Bb(11)` ... ]。
* 已知 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15
* `F` 對應`0x46`, `f` 對應 `0x66`
| Character| Hexadecimal | Binary |
| ---- | -------- | -------- |
| F | 0x46 | 0==1==00 0110 |
| E | 0x45 | 0==1==00 0101 |
| D | 0x44 | 0==1==00 0100 |
| C | 0x43 | 0==1==00 0011 |
| B | 0x42 | 0==1==00 0010 |
| A | 0x41 | 0==1==00 0001 |
| f | 0x66 | 0==1==10 0110 |
| e | 0x65 | 0==1==10 0101 |
| d | 0x64 | 0==1==10 0100 |
| c | 0x63 | 0==1==10 0011 |
| b | 0x62 | 0==1==10 0010 |
| a | 0x61 | 0==1==10 0001 |
| | 0x40 | 0==1==00 0000 |
| | 0x0f | 0000 1111 |
再來看到 `return (in + shift) & 0xf` 於是知道 `F` 與 `f` 兩者輸入的 `in + shift` ==最低位的 4 個 bits== 必定為 `1111`，轉為十進位也就是 15
----
[擴充版本](https://github.com/Rsysz/quiz2/blob/master/test2.c)
---
## 3. 快速除法
```cpp=
const uint32_t D = 3; //M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556
#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1)) //D需要小括號，可能是1+2
/* compute (n mod d) given precomputed M */
uint32_t quickmod(uint32_t n)
{ uint64_t quotient = ((__uint128_t) M * n) >> 64; //為何要用128 ? 可是暫存器只有64
return n - quotient * D;
}
```
查一下無號 * 有號? 有號 * 無號?
要怎麼讀資料是開發人員的責任! (c89 ， c99)
到底是除法還是上面這樣會比較快 ? marco articature 有可能在不同的處理器會有不同的結果
何謂叫做快 ? latency ， throughput(已經很不好) 之後會講!! 為甚麼
XXX = `(f) 0xFFFFFFFFFFFFFFFF`
`UINT64_C` = marco
第二行 :
<font color="#f00">Q : 看不懂 ? </font>
A : ok
如標題所述，除法可以利用$2^N$進行加速，透過將$\dfrac{n}{d}=n\times\dfrac{\dfrac{2^N}{d}}{2^N}$將除法轉換為乘法和位移操作，進而減少運算成本。
已知 `quotient = ((__uint128_t) M * n) >> 64` 對應$\dfrac{1}{2^N}$ 所以 $N=64$
但對應的$M卻不等於\dfrac{2^N}{d}$而是$M=\dfrac{2^N-1}{d} + 1$
因此要證明兩者最終結果是相等的。
- 若以數學的角度考量$\dfrac{M \times n}{2 ^ {64}} = \dfrac{(\dfrac{2 ^ {64} - 1}{d} + 1) \times n}{2 ^ {64}} = \dfrac{n \times 2 ^ {64} - n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}}$
$= \dfrac{n}{d} - \dfrac{n}{d \times 2 ^ {64}} + \dfrac{n}{2 ^ {64}} = \dfrac{n}{d} + (\dfrac{d \times n - n}{d \times 2 ^ {64}}) = \dfrac{n}{d} + (\dfrac{(d - 1) \times n}{d \times 2 ^ {64}}) < \dfrac{n}{d} + \dfrac{n}{2^{64}}$。
由於$n,d < 2^{32} - 1因此\dfrac{n}{2 ^ {64}} < \dfrac{1}{2^{32}} < \dfrac{1}{2^{32} - 1}且\dfrac{n}{d}的餘數部分最大值為\dfrac{2^{32}-2}{2^{32} - 1}$
所以$\dfrac{n}{d}的餘數部分加上\dfrac{n}{2^{64}}也不會進位$
- 但若以程式碼的角度考量
若$M=\dfrac{2^{64}}{d}為整數(設為K)，因\dfrac{2^{64} - 1}{d} < K所以M=\dfrac{2^{64} - 1}{d}+1=(K-1)+1 = K$
若$M=\dfrac{2^{64}}{d}為非整數，因\dfrac{2^{64} - 1}{d} > K所以M=\dfrac{2^{64} - 1}{d}+1=K+1$
兩種情況會讓 `quotient` 分別等於$\dfrac{n}{d}和\dfrac{n}{d}+\dfrac{n}{2^{64}}$但根據上述數學推論的結果，兩者得到的答案相等
因此最後 XXX = `(f) 0xFFFFFFFFFFFFFFFF`
## 4. 倍數判斷
已知 `D = 3` `M = (0xFFFFFFFFFFFFFFFF / D) + 1 = 0x5555555555555556`
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
YYY = `(c) M - 1`
令 `n=3k, 3k+1, 3k+2` (k為非負整數) `n * M` 等於
若 `k=1` 因為 `3M > 0xFFFFFFFFFFFFFFFF` (overflow) 所以 `3M = 0x0000000000000002`
求三者最小值:
* 3kM = 2k
* (3k+1)M = 3kM + M = 2k+M
* (3k+2)M = 3kM + 2M = 2k + 2M
因此只有 `(c) M - 1, (d) M >> 1` 符合要求
但答案的 YYY = `(c) M - 1`
## 5. 字串大小寫轉換
**考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 in-place 的實作**
//測驗寫程式能力
為了美觀和排版也可以說是摩斯密碼全部都是大寫
```cpp=
#include <ctype.h>
#include <stddef.h>
#include <stdint.h>
#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)
// mask generator 需要過濾特定的範圍 且 必須要在編譯期間建立
/* 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);
}
```
VV1 = `(e) 0x80`
VV2 = `(b) 0`
VV3 = `(a) (-1)`
VV4 = `(e) 0x80`
首先看到`PACKED_BYTE`的效果是將輸入LSB的8bits擷取後重複擴充至64個bits
e.g. PACKED_BYTE(0xAB) 會得到 0xABABABABABABABAB
**第5行** : <font color="#f00">Q :我知道是上面那個作用且我也知道如何操作，但是不懂`(uint64_t)(b)` 這一個部分 ? </font>
A : 確保型態的正確性 ， cast作用是拿來大轉小 或是 小轉大
問一下老師為何要+
**第10~11行** : 檢查傳進來的size多大`第10行`會除8以便讓`第11行`知道說需要跑幾次的迴圈
**第12行** : <font color="#f00">Q : 不太懂在幹嘛?</font>
A : cast 而已 把傳進來的文章切8 8 8 進行以便讓下面的運算。
**第13行** : 如同第一題一般以0x80對ASCII範圍內的字元進行檢測
因此 VV1 = `(e) 0x80`
**第14行** : <font color="blue">藍色線條的部分</font>
**第15行** : <font color="blue">藍色線條的部分</font>
**第16行** : <font color="green">綠色線條的部分</font>
<font color="pink"> 粉色線條的部分</font>
**第14~16行** : 可以參考 [RusselCK](https://hackmd.io/@RusselCK/syprog2020_quiz2#Q5-%E5%B0%87%E6%8C%87%E5%AE%9A%E7%9A%84%E5%AD%97%E4%B8%B2-%E6%88%96%E9%83%A8%E5%88%86%E5%AD%97%E4%B8%B2-%E7%9A%84%E8%8B%B1%E6%96%87%E5%AD%97%E6%AF%8D%E5%85%A8%E6%94%B9%E7%82%BA%E5%B0%8F%E5%AF%AB)搭配上面這張圖可以幫助理解。
再來看到`uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2`而上課時學到
> ('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
此外`0x80` >> 2 = `' '`可以知道`A ^ Z`的數值可以決定這8個字元哪一位要做大小寫轉換
也就是說只有字元為大寫時，`A ^ Z`的MSB才能為1
`(128 - 'A' + char + VV2) ^ (128 - 'Z' + char + VV3)`
ASCII
| char | Decimal | Binary |
| ---- | ------- |------- |
| A | 65 |0100 0001|
| Z | 90 |0101 1010|
| |128 |1000 0000|
|sapce |32 |0010 0000|
因此可得知當
`char >= 'A'` 時 `uint64_t A` 的MSB 為1
`char >= 'Z'` 時 `uint64_t Z` 的MSB 為1
但當 `char = Z` 時為了使 `A ^ Z` 的MSB為1 還需額外減1
VV2 = `(b) 0`
VV3 = `(a) (-1)`
VV4 = `(e) 0x80`
## 6. 單次數尋找
```cpp=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
lower ^= nums[i];
lower &= KKK; //KKK = (c) ~higher
higher ^= nums[i];
higher &= JJJ; //JJJ = (d) ~lower
}
return lower;
}
```
`KKK` = `(c) ~higher`
`JJJ` = `(d) ~lower`
- 強烈建議測驗6參考 [Hkoajm0Vw](https://hackmd.io/@joey3639570/Hkoajm0Vw#%E6%B8%AC%E9%A9%976)，我個人覺得寫的超級淺顯易懂。
題目前導知識 : `Melay狀態機` `~代表補數` `各個運算元`
題目須注意事項 : <font color="#f00">Q : 問一下第一點為何會這樣 ? 是不是這一邊所謂 bit 其實有一點瑕疵呢 ? 準確一點來說是不要說每一個不同的 data </font>
A : 的確就是每一個bit就是一個狀態機
1. 首先每個 bit 的動作是獨立的，不會互相影響。所以我們其實是在分別計算每個 bit 的出現次數。
2. 推廣到判斷三次，程式內的 lower 和 higher ，其實概念是兩個位元代表2進位的數字，出現第一次`01`,第二次`10`，第三次`00`來代表
### 開始講解題目
lower 代表的意義是 只出現第一次的
higher 代表的意義是 出現第二次的
e.g. : **nums{2,3,2,2}**
| For | i = 0 | i = 1 | i = 2 | i = 3 |
| ---- | ------- | ------- | ------- | ------- |
| Input | 2(0010) | 3(0011) | 2(0010) | 2(0010) |
| lower | 0010 | 0001 | 0001 |**0011** |
| higher | 0000 | 0010 | 0000 | 0000 |
綜合上述，其實可以看出來，第一次我們使用 `lower` 保留紀錄，第二次這個紀錄會被傳到 `higher` ，若遇到第三次，則兩者歸零，因此在遇到只有一次的 case ， `lower` 會保留住只出現一次的數字，故在最後 return `lower`
題目限制的關係她只會出現3次或是1次，所以若此 Data 只有出現過那麼一次你就會直接回傳那一個的`lower` 那就會是答案了~
<font color="#f00">Q : 確實很神奇但是為何這樣做可以這樣會對? </font>
A : 狀態機可用布林代數去證明
```cpp=
lower ^= nums[i]; //確保傳進來是啥
lower &= ~higher; // 去和higher確認他是否有傳進來過了
higher ^= nums[i]; //如果他是傳進來第二次的等一下可以用
higher &= ~lower; // 去和lower確認他是否有傳進來過 (是不是第二次)
```
:::info
* 狀態圖：( 圓圈中的值代表 H~i~L~i~ )
```graphviz
digraph {
rankdir = LR
00 -> 01 [label = "input = 1"]
01 -> 10 [label = "input = 1"]
10 -> 00 [label = "input = 1"]
00 -> 00 [label = "input = 0"]
01 -> 01 [label = "input = 0"]
10 -> 10 [label = "input = 0"]
}
```
* Truth table
| A | B | C | D | E |
|:---- | ---- | ------ | -------- |:-------- |
| H~i~ | L~i~ | num~i~ | new H~i~ | new L~i~ |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
* $E = 001 + 010$
$= A'B'C + A'BC'$
$= A'(B'C + BC')$
$= A'(B \oplus C)$
* 因此，**new L~i~ = ~ H~i~ & ( L~i~ $\oplus$ num~i~ )**
:::
---
[延伸問題2](https://github.com/Rsysz/quiz2/blob/master/test6.c)
[延伸問題3](https://github.com/Rsysz/quiz2/blob/master/test6_extend.c)
----
###### tags: `進階電腦系統應用2020` `quiz2`
Sign in with Wallet
Connect another wallet