# 2020q3 Homework2 (quiz2)
contributed by < `ccs100203` >
###### tags: `linux2020`
- [2020q3 第 2 週測驗題](/@sysprog/2020-quiz2)
:::info
TODO 一些延伸問題
:::
## 測驗 1
從題目敘述得知，7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
而 0x80 為 1000 0000，所以當以下成立時，代表 `str` 已經超過 ASCII 的範圍了。
```cpp
if (str[i] & 0x80)
return false;
```
題目要我們在 64 位元的架構下，嘗試一次比對 64 位元的資料 (即 word size)，從上面的例子可以推斷出每個 byte 都要與 0x80 做比較，所以在第 4 行填入 0x8080808080808080
```cpp=
while ((i + 8) <= size) {
uint64_t payload;
memcpy(&payload, str + i, 8);
if (payload & 0x8080808080808080)
return false;
i += 8;
}
```
### 延伸問題
#### 1. 解釋上述程式的運作原理
題目敘述說一次要比對 64 bits
```cpp
while ((i + 8) <= size)
```
藉由 `i+8` 去移動，會一次比對 8 bytes，如果 if 為 true 則代表有找到不符合的，就會直接 return false
```cpp
while (i < size)
```
如果剩餘的無法一次比對 64 bits，那麼就會回歸為比較一個 byte
- 參考[記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory#data-alignment)
`memcpy` 的用途為 data alignment，e.g. 至少抓 1 byte，如果不對齊資料，會導致 cpu 的存取因 address 不是在 4 的倍數上而變慢。而現代 x86 處理器允許 data unalignment
#### 2.給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母
TODO
## 測驗 2
這題的 function 為一個 parser，給定的條件為
```cpp
hexchar2val(a~f) return 10~15
hexchar2val(A~F) return 10~15
hexchar2val(0~9) return 0~9
```
當我們從二進位的時候可以簡單地看出答案，所以先用二進位表示
| Example | 0</br>MSB | 1 | 2 | 3 | 4 | 5 | 6 | 7</br>LSB |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| <span style="color:green">**F**</span> | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
| <span style="color:green">**f**</span> | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| <span style="color:green">**8**</span> | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
```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;
}
```
1. 觀察以上程式碼，會發現 `shift` 是遇到英文字母的時候才會使用到的，因為第 5 行做 `(in + shift) & 0xf` 後只會保留右邊的 4 個 bits，而 0~9 在一開始的右邊 4 個 bits 就已經是答案了，所以沒有必要多做操作
2. 這樣就可以知道 `MASK` 是要分辨出==字母==與==數字==，從 column 1 就可以分辨出兩者，所以 `MASK` 為 0x40
3. 如果是字母，做完第 3 行後會得到 0x40 ( 0100 0000 )，因為最後是 `(in + shift)` ，推敲出字母都與所需的數字差 9， e.g. f 為 0110，但是答案需要輸出 15。這樣我們只要把 `shift` 變成 9 就好了
4. 因為 9 等於 1001，所以 `letter >> 3 | (letter >> 6)` 就是我們要的答案，下面是完整的程式碼
```cpp
uint8_t hexchar2val(uint8_t in)
{
const uint8_t letter = in & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
return (in + shift) & 0xf;
}
```
### 延伸問題:
很直接的先把 input 改為 pointer 來處理多個 char，再修改下面的第 14 行，把每個數值轉換過後再乘上對應的 $16^n$，這邊用 shift 去代替乘法。
```cpp=
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
uint64_t hexchar2val(uint8_t* in)
{
int len = strlen(in);
uint32_t ans = 0;
for (int i = 0; i < len; i++)
{
const uint8_t letter = in[i] & 0x40;
const uint8_t shift = (letter >> 3) | (letter >> 6);
ans |= ((in[i] + shift) & 0xf) << (4 * (len - i - 1));
}
return ans;
}
int main(){
u_int8_t* c1 = "0FF1CE";
u_int8_t* c2 = "FEE1DEAD";
u_int8_t* c3 = "FFBADD11";
u_int32_t a = hexchar2val(c3);
printf("%u\n", a);
return 0;
}
```
## 測驗 3
- 將除法改為乘法運算
為了將除法轉換為
1. 預先計算的 $\frac{2^N}{d}$
2. 乘法
3. shift
使用
$\frac{n}{D} = n * \frac{\frac{2^N}{D}}{2^N}$
```cpp=
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;
}
```
第 2 行的 M，就是為了預先計算 $\frac{2^N}{D}$，這時我們不知道應該要填多少。所以繼續往下，看到第 6 行，這邊就是要算 $n * \frac{\frac{2^N}{D}}{2^N}$，我們把他轉換為 $M * n / 2^{64}$，這時候就很容易看出 $2^N$ 即為 $2^{64}$，那麼為什麼是選擇 0xFFFFFFFFFFFFFFFF 呢，因為已經 overflow 了，所以索性 -1，再從後面的 +1 做無條件進位補回來，第 6 行的 shift 是無條件捨去，也能補回誤差。這樣我們就得到 `quotient` 了，於是就能在第 7 行得到餘數。
### 延伸問題:
TODO
## 測驗 4
```cpp
bool divisible(uint32_t n)
{
return n * M <= M - 1;
}
```
因為沿用 D 跟 M，D = 3, M = 0x55...56，所以
左邊會是 n * (0x5555555555555555 + 1)
右邊會是 0x5555555555555555
我把 n 轉換為 3k、3k+1、3k+2 這三種情況
1. 3k * (0x5555555555555555 + 1) = (0xff...ff + 3) * k = (0 + 2) * k = 2k
2. (3k + 1) * (0x5555555555555555 + 1) = 2k + 0x55...56 = 2k + M
3. (3k + 2) * (0x5555555555555555 + 1) = 2k + 0x55...56 * 2 = 2k + 2M
由於 n 是 unsigned 32 bits，所以 n >= M 不可能發生，只有 2k 會 <= M - 1，可以得知 n 在拆成 3k 的時候才能符合判斷式 n * M <= M - 1，故可判斷是否為 3 的倍數
## 測驗 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(0x80)) == 0) { /* is ASCII? */
uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0);
uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + (-1));
uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2;
*chunk ^= mask;
} else
strlower(s, 8);
}
k = n % 8;
if (k)
strlower(s, k);
}
```
`PACKED_BYTE` 的用處是把最小的兩個 bytes 補滿 64 bits，
e.g. PACKED_BYTE(0x80) 會得到 0x8080808080808080
- 因為單純看程式碼實在推敲不出答案，所以我直接執行程式，來推敲原因
`PACKED_BYTE(128 - 'A' + 0)` = 0x3f...3f
`PACKED_BYTE(128 - 'Z' + (-1))` = 0x25...25
```cpp
printf("%ld, %lx, %lx, %lx\n", i, A, Z, mask);
```
input "This eBo"
output: 0, ae81a45fb2a8a793, 94678a45988e8d79, 20000000000020
- 藍色是程式第 14~15 行的 `A` 跟 `Z`，綠色是 ASCII 內的字母
| | 0</br>MSB | 1 | 2 | 3 | 4 | 5 | 6 | 7</br>LSB |
| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |
| <span style="color:blue">**A**</span> | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
| <span style="color:blue">**Z**</span> | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
| <span style="color:green">**a**</span> | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| <span style="color:green">**z**</span> | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 |
| <span style="color:green">**A**</span> | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
| <span style="color:green">**Z**</span> | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
1. 可以看出大寫的時候會出現 2，從上面的表看出 0x20 在 ASCII 上剛好可以把大寫轉換為小寫，所以這個 `mask` 的用處很明顯就是要找出需要轉換為小寫的 char，並且在第 17 行 `*chunk ^= mask` 把他轉換為小寫，而小寫字母就保留原樣。 (與 1 做 xor 是 toggle)
2. 而會是 2 的原因是因為往右 shift 2，所以原本是 8，而這個 8 很明顯是從第 16 行 `((A ^ Z) & PACKED_BYTE(0x80))` 來的，從第 1 點我們知道大寫的時候應該要產生 0x80，小寫會是 0x00，所以接下來要推斷 `A^Z` 如何在 MSB 產生 1 或 0。
3. 大寫字母需要在 `A^Z` 的 MSB 產生 1，所以需要各一個 0 跟 1，而小寫字母則是需要兩個 0 或 1，程式內的 `(128 - 'A' + 0)` 跟 `(128 - 'Z' + (-1))` 相減得到 26，剛好可以容納下所有英文字母，嘗試 0x25 與 A~Z 相加可以發現最大是 0x7F 剛好會保持 MSB 為 0，而從 0x3F 加的話，就會從 0X80 開始，MSB 肯定是 1，於是 `(A ^ Z)` 過後的 MSB 就會得到 1。
4. 如果是小寫字母，無論如何我們都會得到大於 0x80 的數字，所以 `A` 跟 `Z` 的 MSB 都會是 1，`(A ^ Z)` 過後的 MSB 就會得到 0，在 `mask` 的地方就會產生 0。
6. 這樣就釐清為什麼程式會是這樣設計了，`VV1` 選 0x80 是為了驗證是否屬於 ASCII，`VV2` 選 0 是為了讓大寫的字母相加後的 MSB 一定是 1，`VV3` 選 -1 是因為需要多 -1 才能夠容納 26 個英文字母 (原本只相差 25)，`VV4` 選 0x80 是為了讓 `mask` 只保留需要轉換為小寫的 MSB，並將他 shift 到 0x20 的位置。
### 延伸問題
`char str[]` 就如同一般的 array 一樣，可以對他做任何的操作。但 `char *str` 是 string literal，屬於 read-only part of memory，任何想要對他們的修改都會變成 undefined behavior。由於題目的程式是 in-place 的演算法，所以不能夠用 `char*`
## 測驗 6
這題為 LeetCode 137. [Single Number II](https://leetcode.com/problems/single-number-ii/)，要找出只出現過一次的 value，而其他的 value 都會出現 3 次
```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;
}
```
- 在解這題前我想要先解釋如果其他 value 是出現 2 次的情況
由於 xor 的特性可以簡單的寫出下面的 code，當相同的 bit 出現兩次時，就會被清空成 0，最後就只會留下出現一次的 value 的 bits
```cpp
int singleNumber_even(int* nums, int numsSize){
int a = 0;
for(int i=0; i<numsSize; ++i)
a ^= nums[i];
return a;
}
```
- 回到這題，由於其他 value 會出現三次，所以使用兩個變數去紀錄，第一次出現時會存到 `lower` 裡，第二次會把他放到 `higher`，第三次就會把他從 `higher` 移除，這樣全部做完時就會在 `lower` 得到想要的 number，看下面的 code:
1. 第 5 行 會將 num 放進去 `lower` 裡面，但是如果 num 已經在裡面，就會把他移除，代表他已經出現第二次
2. 第 6 行 我們只會將第一次出現的 num 放進去 `lower`，所以如果在 `higher` 裡就會被移除，這樣可以檢測他是否為第三次出現
3. 第 7~8 行 `higher` 紀錄的是第二次出現的 num，所以當這個 num 是第一次出現時，會因為 num 在 `lower` 裡面也有，而藉由第 8 行把 `higher` 內的 num 清除。第二次遇到時就會直接放入 `higher`，第三次遇到時就會因為已經存在 `higher` 內而藉由第 7 行清除掉，換句話說，`higher` 最後會是 0
```cpp=
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;
}
```
### 延伸問題
其實就是一直增加變數去紀錄
- 將程式推廣成 3、4、5.... 次
1. 如果是偶數次的話，直接使用上面的如果是 2 次的情況就好，因為 xor 的特性每兩次就會清空一次，所以只要是偶數次都可以使用
2. 奇數次就需要增加變數去紀錄 //todo
Sign in with Wallet
Connect another wallet