# 2020q3 Homework2 (quiz2)
contributed by < `Sisker1111` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz2)
>
## 1. 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;
}
```
從以上考慮單個字元，ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元(二進位的0~127)，若超過127，與 0x80 做 & 時必會得出一個非 0 的值.
以下只要把單個字元拓展到 8 個字元，答案很好理解的會選 `MMM`=`(d)` `0x8080808080808080`。
```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 & MMM)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
### Why use memcpy ?
>因為我們想要一次對 64 個 bits 做處理 ， 因此我們需要 memcpy 來將 8 個 8 bits 元轉為一個 64 bits 的 payload 來儲存，並拿來和 0x8080808080808080 做 & 運算，此外，memcpy 可以幫助我們做 memory aligned.
詳細說明可參考自以下網址 : (https://blog.csdn.net/yangbodong22011/article/details/53227560)
```c=
///// 擷取自 glibc memcpy()
if(len >= OP_T_THRES) //OP_T_THRES=16
{
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ; //OPSIZ=sizeof(unsigned long int)=8
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address manipulation,
as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known alignment of
DSTP. Number of bytes remaining is put in the third argument,
i.e. in LEN. This number may vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
```
`memcpy` 首先判斷需要 copy 的大小是否大於 OP_T_THRES (OP_T_THRES 是一個判斷 copy 大小的 Threshold ， 在不同的架構下有不同的值，通常為 8、16)，如果 len `<` OP_T_THRES ， 採用 `one byte one byte` copy ， 對於 `>=` OP_T_THRES 的 copy 才會需要 `memory aligned`，其中第 5 行就在做 aligned 的動作，下圖擷取自(https://blog.csdn.net/yangbodong22011/article/details/53227560)
`memory aligned`後按照`one page one page`的方式 copy .
## 2. 16進位字串轉換
開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作:
```cpp=
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` 一定隸屬於 '0', '1', '2', …, '9' 及 'a', 'b', 'c', …, 'f' (小寫) 及 'A', 'B', 'C', …, 'F' (大寫) 這些字元。預期 `hexchar2val('F')` 和 `hexchar2val('f')` 回傳 15，且 `hexchar2val('0')` 回傳 0，其他輸入都有對應的數值。
以下摘自 ASCII 表格
* `0`, `1`, `2`, ..., `9`對應到 `0x30`, `0x31`, `0x32`, ..., `039`
`a`, `b`, `c`, ..., `f`對應到 `0x61`, `0x62`, `0x63`, ..., `066`
`A`, `B`, `C`, ..., `F`對應到 `0x41`, `0x42`, `0x43`, ..., `046`
首先考慮到第 5 行的 return，因為最後會和`0xf`做 and 操作，因此我們只要考慮如何把最右邊 4 個 bits 變成我們想要的即可.
接著考慮數字部分，十六進位表示的字串轉為數值是一樣的，因此我們不會希望`return (in + shift) & 0xf`這部分改變到右邊 4 個 bits 的結果，也就是說，`shift`的內容應該要是`xxxx 0000`，從這裡我們推斷，選項中只要`letter = in & MASK`的結果不是全 0，就不是我們要找的答案，因此`(a)` `(b)`都不可能.
| Character | Hexadecimal | Binary |
| ---- | -------- | -------- |
| 1 | 0x30 | 0011 0000 |
| 9 | 0x39 | 0011 1001 |
| | 0xf | 0000 1111 |
再來看到 `return (in + shift) & 0xf` 於是知道 `F` 與 `f` 兩者輸入的 `in + shift` ==最低位的 4 個 bits== 必定為 `1111`，因此`letter`一定不是全 0，`(e)`就不可能了，最後考慮到第 4 行`shift = (letter >> AAA) | (letter >> BBB);`，一共會shift 2 次，可猜想到`letter`僅有一個 bits 為 1，因此先排除`(d)` `0x60`，最後驗證`(c)` `0x40`是否正確，發現`0x40`就是答案.
| Character | Binary |
| ---- | ---- |
| F | 0==1==00 0110|
| f | 0==1==10 0110|
| 0x40 | 0==1==00 0000|
原先我一直不明白為何要有第 3 行的 code，重新審視題目才發現到，`letter = in & MASK`這段其實就是在區別數字和英文字母.
## 3. 快速除法
```cpp=
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;
}
```
目前來講我只會以數學的角度來分析這題，Code 的原理還需要再多深入了解:
若要算出餘數，可以利用右邊這個關係 -> n mod D = n - Floor(n/D) * D.
看到 `return n - quotient * D;`可以發現`quotient`和上述的`Floor(n/D)`是等值的，因此只要第 6 行`((__uint128_t) M * n) >> 64`算出的結果能夠等同於`Floor(n/D)`即可.
假設`UINT64_C(XXX)`的值為 X,則 `M = X/D + 1`，因此第 6 行的式子可以更改成`{(X/D + 1)*n} / 2^64 `，將式子重新整理一下可以得出`{(n/D)*(X+D)} / 2^64 `，為了保持此式子與`Floor(n/D)`相等，`Floor( (X+D) / 2^64 )`，必須為 1，我們已知`D=3`且因為使用`uint128_t`轉型所以不考慮 overflow 的問題，滿足式子的選項只有
`(e).` `0xFFFFFFFFFFFFFFFF`.
## 4. 倍數判斷
延伸測驗 3，在 D 和 M 都沿用的狀況下，判斷某個數值能否被指定的除數所整除，這題可以用歸納法正出.
已知 `D = 3` `M = (0xFFFFFFFFFFFFFFFF / D) + 1 `
`M = (0xFFFFFFFFFFFFFFFF / D) + 1 = { ( 15 + 15*16^1 + 15*16^2 + ... + 15*16^7 ) / 3 } + 1 = 0x5555555555555555 + 1 = 0x5555555555555556`
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
令 `n=3k, 3k+1, 3k+2` (0 <= k <= n/3)
用 `k=1` 帶入，因為 `3M > 0xFFFFFFFFFFFFFFFF` (overflow) 所以 `3M = 0x0000000000000002`
1. 當`n=3k`時 n*M = 3kM = 2k.
2. 當`n=3k+1`時 n*M = 3kM + M = 2k + M.
3. 當`n=3k+2`時 n*M = 3kM + 2M = 2k + 2M.
帶入選項:
* ( a ). 當 k=0 時，n=3k+1=1，1 不能被 3 整除但 M <= M+1，矛盾.
* ( b ). 當 k=0 時，n=3k+1=1，1 不能被 3 整除但 M <= M，矛盾.
* ( c ). 任一情況代入皆成立.
* ( d ). n * M <= M>>1 可以理解成 n*M <= M/2,即 2n <= 1 , n <= 1/2 , n 只有 0 一種可能，與 n 為 32bits 的 unsigned int 的前提矛盾
* ( f ). 當 k=0 時，n=3k+2=2，2 不能被 3 整除但 2M <= M<<1，矛盾.
## 5. 字串大小寫轉換
```cpp=
#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);
}
```
` PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)`的用途是取出`b`的後 8 bits，unsigned的`0x0101010101010101`，會得到重複循環的 8bit 字節.
1. 第 13 行是在確認是否是有效的 ASCII code，因為 `PACKED_BYTE(0x80)`做完會變成`0x8080808080808080`.
2. 14、15行是在確認字元 c 是否在 'A'、'Z'之間，考慮以下情況:
* --- 對 'A' 而言 --- :
* 當 c 在 'A'~'Z' 之間或在 'Z' 之後，因為 `(C -'A') >= 0`，還要再加上 128 ，所以這 8 個 bits 最高位會是 1.
* 當 c 在 'A' 之前，因為 `(C -'A') < 0`，加上 128 後，這 8 個 bits 最高位會是 0.
* --- 對 'Z' 而言 --- :
* 當 c 在 'A'~'Z' 之間或在 'Z' 之前，因為 `(C -'Z') <= 0`，還要再加上 127 ，所以這 8 個 bits 最高位會是 0.
* 當 c 在 'Z' 之後，因為 `(C -'Z') > 0`，加上 127 後，這 8 個 bits 最高位會是 1.
總結: 若 c 在 'A'~'Z' 之間 `A ^ Z`的結果會是 `0b1xxxxxxx` 反之則是 `0b0xxxxxxx`，為了使得在 A ^ Z之間的數字從大小變成小寫，先將 `A ^ Z`的結果跟`0x80`做 and ，這個步驟了讓大寫英文字母變成小寫，其他字原則維持不變，接著運用`strlower`的技巧`s[j] ^= 1 << 5;`(其實就是跟 32 做 xor 操作)，在這裡，`0x80 >> 2 = 0b00100000 = 32`
### char str[] or char *str？
`char str[]`是建立一個名字為 str 的 char array的副本，其 str 指向的值是這個 array 開頭的 memory address，這個值是不可改變的，但 str 指向的 address 的 content 是可變的.
`char *str`則是建立一個指向 type char 的 pointer 叫做 str，str 所指到的 memory address 是可以改變的，但根據規格書 Undefined behavior 的部分提到，我們不可改寫指向的區域的內容.
亦即`char *s = "String1";`若接著寫`s[0]='H';`則會造成`Segment fault`
## 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;
higher ^= nums[i];
higher &= JJJ;
}
return lower;
}
```
以下是我實際用 Code 執行 [2,2,3,2] 這個例子的結果:
* 已知 ( A ^ B ) ^ B = A , ( A ^ B ) ^ A = B.
先說明一下問題:
Input 是一連串的數字，這群數字中只有一種數字是單獨存在的，其餘的數字都有 3 個，目的是要把單獨存在的那一種數據 Output 出來.
:::info
我們知道 A ^ A = 0，若要使的 A ^ A ^ A也等於 0 並且只使用 A 這個數字，可以對第 3 個 A 做兩種操作:
A ^ A, A & ~A
:::
看向 Code ，為何需要 `lower`和`higher`兩個變數?
我的理解是: `higher`是用來記錄出現過"兩次"的數字，並在該數字出現第三次時，將該數字與`~higher`做`&`，即可把該數字消除，說明如下:
1. 假設一數據 A 第一次出現時，`higher`會和`~lower`做`&`(如上圖中的第一個 higher 值)，此時對於 A 來說，`higher`會設為 0.
2. A 第二次出現時，因為`lower ^ lower`的關係，A 會被消除，因為剛剛`higher`是 0 ，對 A 來說，`A ^ 0`等於 A.
3. 當第三次 A 出現時，對 A 來說`higher = A`，此時坐`A & ~higher`會把 A 消除，如此一來，A 便不會影響要 return 的那個值
Sign in with Wallet
Connect another wallet