# 2020q3 Homework2 (quiz2)
contributed by < `StevenChen8759` >
###### tags: `linux2020`
> 相關連結：
> [2020秋季進階電腦系統理論與實作 quiz2](https://hackmd.io/@sysprog/2020-quiz2)
> [2020秋季進階電腦系統理論與實作 quiz2 作業說明](https://hackmd.io/@sysprog/B1zAbkAEP)
> [2020秋季進階電腦系統理論與實作 quiz2 作業繳交區](https://hackmd.io/@sysprog/2020-homework2)
> [color=green]
---
# :hammer_and_wrench: 測驗一
```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 & 0x8080808080808080)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
## :building_construction: 程式碼分析
* 函式透過第一個 `while` 迴圈，可一次比對字串中的八個字元是否為 `ASCII charcater` ，其原理是透過位元運算達成。
* 標準的 `ASCII charcater` 之範圍如下
```verilog
Dec: 8'd0 to 8'd127
Bin: 8'b00000000 to 8'b01111111
```
* 因此，我們可透過 `bitwise and` 位元運算過濾非標準的 `ASCII character`
* 不大於 $127$ 的 `char` 值輸出全零。
* 反之，則輸出非零。
* 因 $127$ 恰等於 $2^{(8 - 1)} - 1$，故大於 $127$ 的數，其 `最高位元 (MSB)` 之值必為 $1$ (以 `char` 型別而言)。
* 因此我們將任意 `char` 與 `0x80` 做 `bitwise and` 運算，再檢查其值是否非零，即可確認該字元是否為標準 `ASCII character`
* 上述的運作原理只針對一個 `char`，在此處我們將其擴充成一次針對 8 個 `char` 操作，因此 `uint64_t` 的 `bitwise and` 操作，常數部分即替換成 `0x8080_8080_8080_8080_8080_8080_8080_8080` 進行操作，並透過 `memcpy()` 呼叫將字串中的 8 個字元內容複製至區域變數內。
* 第二個 while 迴圈則是針對長度非恰為 8 的倍數之字串檢查，其執行次數為 `char length` mod $8$。
## :pencil: 改寫: 應用於檢知已知長度字串是否包含英文大小寫字母
* TODO
---
# :hammer_and_wrench: 測驗二
```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;
}
```
## :building_construction: 程式碼分析
* `letter` 變數的主要目的在於指出引數 `in` 是否為字母，考量 return 的值加上了一個 `and mask`，其值為 `0x0F`，根據 ASCII 數字表示法的特性，我們不須再將回傳值加上 `shift` 偏移值，即可代表 數字 `0` ~ `9`。
* 根據以上分析，此 case 中的 `shift` 值應為 0
* 因此，變數 `in` 的 `and mask` 應選擇 `0x40`，在輸入非字母的情況下，使 `shift` 值為 0。
* 根據上述的分析，在 `in` 值輸入字母(不分大小寫)時，`letter` 的值為 `0x40`
* 而 `shift` 變數的主要作用在於 `in` 為字母輸入時加上一個 `offset`，使 return `(in + shfit)` 的最低四個位元對應到`0x00` ~ `0x0F`，並透過 `and mask` 值 `0x0F` 令最高四位元的值為 0。
* 因此，`in` 輸入為字母時，`shift` 值應為 9。
* 因為 `A` / `a` 對應 `0x41` / `0x61`，故 `in + 9` 後即為 `0x4A` / `0x6A`，加上 `and mask` 值 `0x0F`，即得正確回傳值 `10 (decimal)`
* 其餘 `B` / `b` 至 `F` / `f` 之對應亦同。
* 參考下列的數值對應，可理解 `shift` 初值指派的右移值原理。
```
8'b01000000 <= letter
------------------------------
8'b00001000 <= letter >> 3
| 8'b00000001 <= letter >> 6
------------------------------
8'b00001001 <= shift
```
## :pencil: 擴充: 十六進制字串輸入與轉換
* TODO
---
# :hammer_and_wrench: 測驗三、四
### :penguin: 測驗三程式碼與分析
```cpp=
const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFF_FFFF_FFFF_FFFF) / (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 位元的整數，並結合定點數的概念，將低 64 位元視為小數，高 64 位元視為整數。
* 除法原理公式: $n = q \cdot d + m$
* 移項除法原理公式: $\frac{n}{d} = q + \frac{m}{d}$
* 根據公式 $\frac{n}{d}=n\cdot\frac{2^{64}}{d}\cdot\frac{1}{2^{64}} = q + \frac{m}{d}$
* 移項得 $q = n\cdot\frac{2^{64}}{d}\cdot\frac{1}{2^{64}} - \frac{m}{d}$
* 因 $m < d$，且在，故上述公式在二進位計算下可簡化成 $q = n\cdot\frac{2^{64}}{d}\cdot\frac{1}{2^{64}}$
* 我們接著計算 $\frac{2^{64}}{d}$ ，也就是 Macro `M` 的部份。
* 因數值 $2 ^ {64}$ 需要 65 位元才能表示，且因 $2 ^ {64}$ 與 $2 ^ {64} - 1$ 除以 3 皆有**精確度不足**的狀況，因此我們使用 $\frac{2 ^ {64} - 1}{d}$ 代替。
* 也因為精確度不足的問題，不論是使用 $2 ^ {64}$ 與 $2 ^ {64} - 1$ ，在輸入數字恰好整除時，`((__uint128_t) M * n) >> 64` 所計算的 `quotient` 將會與實際值恰好差 1。(參考下述分析)
* 因此，我們在 Macro `M` 中的 $\frac{2 ^ {64} - 1}{d}$ 項後面再加上 1 補償誤差，即可解決。(參考下述分析)
* 變數 `quotient` 已重現了上述 $\frac{n}{d}=n\cdot\frac{2^{64}}{d}\cdot\frac{1}{2^{64}}$ 的較快版本，$n$ 乘上 Macro `M` 所計算的常數後，右移 64 位元，即可得到商數。
* 最後，透過除法原理公式的移項，回傳 n 的餘數。
* 即 $m = n - q \cdot d$
:::info
這方面的描述不太確定數值會恰好差 1 的原因，希望老師可以在指點方向修改成正確且精準的描述，謝謝老師~
:::
:::warning
考慮到 underflow 了嗎？
:notes: jserv
:::
>謝謝老師指點，經過一番思考後終於找出原因，但在研讀 [IEEE 754 Standard](https://people.eecs.berkeley.edu/~wkahan/ieee754status/IEEE754.PDF) 的 `underflow` 描述後，個人認為使用 `定點數精確度不足` 描述此一狀況較為精準，再麻煩老師分析，謝謝老師~
### :game_die: 分析：定點數精確度不足與補償
* 我們在上述使用 $\frac{2 ^ {64} - 1}{d}$ 時，與原式表示值會有誤差，這是因為定點數可能會遇到無法精確表示小數的狀況 (像是$\dfrac{1}{3}$)，考量下列的算式：
* 理想：$\dfrac{1}{3} = \dfrac{1}{4} + \dfrac{1}{16} + \dfrac{1}{256} + ...= \sum_{i = 1}^{\infty}\dfrac{1}{4^i}$
* 實際：$\dfrac{1}{3} \approx \sum_{i = 1}^{N/2}\dfrac{1}{4^i}$，其中 $N$ 為定點數中小數部份的表示位元數
* 上述實際狀況的算式在左右兩邊乘以三之後，使用二進位表示之值明顯會小於 1，在只保留定點數中整數部份的情況下，即造成了 `quotient` 與實際值相差 1 之情形。
* 我們假設使用 16 位元表示一個定點數，整數與小數部份各佔用 8 個位元，參考下列 $\frac{1}{3}\cdot3$ 的操作：
```verilog
origin: 16'h0055 => 16'h00FF
```
* 因此，我們在小數點末位 +1 補償，即可得到正確的結果, 且不影響不可被 3 整除的數字輸出之商。
```verilog
add_1: 16'h0056 => 16'h0100
```
### :penguin: 測驗四程式碼與分析
```cpp=
const uint32_t D = 3;
#define M ((uint64_t)(UINT64_C(0xFFFF_FFFF_FFFF_FFFF) / (D) + 1))
bool divisible(uint32_t n)
{
return n * M <= M - 1;
}
```
* 根據上述精度的分析, 我們代入數個 `n` 值解析輸出結果：
```verilog
"1 * M" : 64'h5555_5555_5555_5556
"2 * M" : 64'hAAAA_AAAA_AAAA_AAAC
"3 * M" : 64'h0000_0000_0000_0002
_
"M" : 64'h5555_5555_5555_5556
"M - 1" : 64'h5555_5555_5555_5555
_
"4 * M" : 64'h5555_5555_5555_5558
"4 * M" : 64'hAAAA_AAAA_AAAA_AAAE
"6 * M" : 64'h0000_0000_0000_0004
```
* 根據上述的演示，當輸入的 n 可整除時，因定點數的整數部份須 128 位元才能表示，因此此處 64 位元即為定點數的小數部份，且因 n 整除時其定點數的小數部份趨近於 0 (此處僅考慮以二進位表示)，其值必定小於 `M`, 故可以此作為判斷是否整除的依據。
* 再考量輸入值為 1 的狀況，此時因比較運算子為 `<=` ，故代入 `M` 會造成錯誤的輸出，故我們須採用 `M - 1` 表示，才能正確判斷是否整除。
---
# :hammer_and_wrench: 測驗五
```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);
}
```
## :building_construction: 程式碼分析
* 大寫轉成小寫的位元運算方法為：`char ^ 0x40`，因此當輸入值須轉換成小寫時，`mask` 之值應為 `0x40` ；否則為 `0x00` ，即保留原始字元之值。
* `mask` 初始值指派時，前面的運算結果右移了兩個位元，綜合上述的想法，`VV4` 之值應為 `0x80`。
* 根據原題目已給定的程式碼，`(A ^ Z)` 為判斷輸入字元是否在 `A` 到 `Z` 的範圍內。
* `XOR` 運算的特性為 `同0異1`， 即兩輸入位元相同則輸出0，兩輸入位元相異則輸出1。
* 根據這樣的特性, 我們期望透過 `XOR` 運算，在輸入為大寫英文字母時輸出 1，否則輸出 0 ；以符合上述的轉換規則。
* 再接著看到變數 `A` 與 `Z` 的初始值指派，我們透過下列表格搭配位元運算特性，推論 `VV2` 與 `VV3` 之值:
| 輸入字元 | 變數 `A` 之值 | 變數 `Z` 之值 | `mask` 之 MSB |
| -------- | ------------- | ------------- | --- |
| (0x40) | 127 + `VV2` | 102 + `VV3` | 0 |
| A(0x41) | 128 + `VV2` | 103 + `VV3` | 1 |
| Z(0x5A) | 153 + `VV2` | 128 + `VV3` | 1 |
| (0x5B) | 154 + `VV2` | 129 + `VV3` | 0 |
| a(0x61) | 160 + `VV2` | 135 + `VV3` | 0 |
| z(0x7A) | 185 + `VV2` | 160 + `VV3` | 0 |
* 參考 `0x40` 的輸入，其 `mask` 之 MSB 值應為 0，故 *`VV2` 必非正值*。
* 參考 `A` 的輸入，其 `mask` 之 MSB 值應為 1，因此 *`VV2` 必不可能為負值*，**故 `VV2` 必為 0**。
* 參考 `Z` 的輸入，其 `mask` 之 MSB 值應為 1，此時僅有令 `VV3` -1，才能同時令輸入 `Z` 時為 1，且輸入 `0x5B` 時輸出為 0；**故 `VV3` 必為 -1**。
* 參考測驗一中 `Standard ASCII` 之位元運算判定方法，`VV1` 之值應為 `0x80`。
## :dagger_knife: String Literal 議題探討
* `char *str = "xxxx"` 的宣告方式會將字串視為 `String Literal` 並儲存在 code section，對此 `String Literal` 進行寫入操作是 `未定義行為 (Undefined Behavior)`，進而造成 `Segmentation Fault`。
* 因此在宣告的時候須使用陣列配置或是動態記憶體配置的方法，才能順利將字串中的大寫字元轉換成小寫。
* Ref: [你所不知道的C語言：指標篇 - 重新探討「字串」](https://hackmd.io/@sysprog/c-pointer?type=view#%E9%87%8D%E6%96%B0%E6%8E%A2%E8%A8%8E%E3%80%8C%E5%AD%97%E4%B8%B2%E3%80%8D)
---
# :hammer_and_wrench: 測驗六
```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;
}
```
## :building_construction: 程式碼分析
* TODO
Sign in with Wallet
Connect another wallet