# 2020q3 Homework2 (quiz2)
contributed by < `joey3639570` >
###### tags: `進階電腦系統理論與實作`
:::danger
:warning: 注意共筆書寫規範，中英文之間用一個半形空白區隔，從小處做起！
:notes: jserv
:::
經過測驗 2，發現自己對於 bitwise 操作相當不熟，參照老師給的下列連結給自己複習:
- [C Bitwise Operators Quiz](https://doc.callmematthi.eu/C_Bitwise_Operators.html)
- [線上測驗 (附上解答)](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/)
- [Bitwise Practice](https://web.stanford.edu/class/archive/cs/cs107/cs107.1202/lab1/practice.html)
### 實例：
**ASCII**
> A= 0x41, a= 0x61, ' '= 0x20, '_'=0x5f
- 將字元轉成小寫: 免除使用分支
```cpp
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
```
0110 0001 | 0010 0000 -> **0110 0001**
0100 0001 | 0010 0000 -> **0110 0001**
- 將字元轉為大寫: 免除使用分支
```cpp
('a' & '_') // 得到 'A'
('A' & '_') // 得到 'A'
```
0110 0001 & 0101 1111 -> **0100 0001**
0100 0001 & 0101 1111 -> **0100 0001**
- 大小寫互轉: 避免使用分支
```cpp
('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
```
0110 0001 ^ 0010 0000 -> **0100 0001**
0100 0001 ^ 0010 0000 -> **0110 0001**
:::warning
延伸思考：課堂多次提到「避免分支」，這在程式碼的效能 (提示: 複習計算機組織/結構提到的 superscalar) 和資訊安全有什麼特別考量呢？
:notes: jserv
:::
### 為何要避免分支?
- 參考 [Why is it good to avoid instruction branching where possible?](https://stackoverflow.com/questions/5662261/why-is-it-good-to-avoid-instruction-branching-where-possible)
:zap:於效能而言，可以先從 [Instruction Prefetch](https://en.wikipedia.org/wiki/Cache_prefetching) 來看，其為處理器增加 performance 的主要方法之一，能藉此有能夠**提前**執行 instruction 的可能性，但是需要確定**下一個指令**才能有效果。
此時可以再引入 [Instruction Pipeline](https://en.wikipedia.org/wiki/Instruction_pipelining) 的思考，更能了解為何 Branch 會影響 Performance，可參見 [Instruction Pipeline : Branches](https://en.wikipedia.org/wiki/Instruction_pipelining#Branches)
>Programs written for a pipelined processor deliberately **avoid branching to minimize possible loss of speed.**
#### 管線處理五個步驟 (Five stages, one step per stage)
- IF: Instruction Fetch (**擷取指令**) 從記憶體擷取指令<br> (Instruction fetch from memory)
- ID: Instruction Decode (**指令解碼**) 解碼指令並讀取暫存器<br> (Instruction decode & register read)
- EX: Execution (**執行指令**) 執行運算或計算位址<br> (Execute operation or calculate address)
- MEM: Memory Access (**記憶體存取**) 存取記憶體運算元<br> (Access memory operand)
- WB: Write Back (**寫回**) 將結果寫回至暫存器<br>(Write result back to register)
```graphviz
digraph foo {
rankdir=BT;
node_1 [shape=plaintext,label="Fetching next instruction depends on branch outcome in ID stage."]
{
node [shape=record];
rankdir=LR;
node_A [shape=record label="{Instruction Pipeline|{IF|<t>ID|EX|MEM|WB}}"];
node_1->node_A:t
}
}
```
:bomb:**影響效能的關鍵問題 - Control Hazard :**
>當 Branch 指令尚未決定是否分支，但後續指令已進入管線,故執行順序發生錯誤
:zap: **有 Branch ，便意指下一個 Instruction 有兩個或以上的可能** :zap:
然而， pre-fetching 便有了以下三種應對方法:
- 不 prefetch 分支後的 Instructions ，而讓 instruction pipeline 空下來，等待分支判斷後再去取要執行的 instruction (**worse performance**)
- Processor 可以先猜要走哪個 branch ( [branch prediction](https://en.wikipedia.org/wiki/Branch_predictor) ) ， prefetch 之後執行，但如果猜錯 branch ， 就必須把先做完的部分丟掉，然後 fetch 正確的 instruction
- Processor 同時 fetch 且執行兩個分支，分支後把沒有走的 branch 的部分丟掉 ( [eager execution](https://en.wikipedia.org/wiki/Speculative_execution#Eager_Execution) )
:::success
:boom: 但不管怎樣，減少 branch 的使用，也就是減少**猜測**行為，就更能確保 Performance！
:::
#### Superscalar?
> - A **superscalar processor** is a CPU that implements a form of parallelism called **instruction-level parallelism within a single processor**.
> - Superscalar processor can execute **more than one instruction during a clock cycle** by simultaneously dispatching multiple instructions to different execution units on the processor.
>
> 參見 [Wikipedia: Superscalar Processor](https://en.wikipedia.org/wiki/Superscalar_processor#Limitations)
:::warning
:boom: 不要把 Superscalar 跟 Pipelining 搞混！
- Pipelining: several instructions are simultaneously **at different stages** of their execution
- Superscalar: several instructions are simultaneously **at the same stages** of their execution
:::
於 Superscalar 架構下，**efficiency of speculation** 是一個 key issue ，若能每次都能精準的完成 Branch Prediction，將能使 Processor 的整體 Performance 上升。
#### Branch 和資訊安全有關?
相關資訊可閱讀: [Side-Channel Attacks](https://zh.wikipedia.org/wiki/旁路攻击)
參考[BranchScope: A New Side-Channel Attack on
Directional Branch Predictor](https://www.cs.ucr.edu/~nael/pubs/asplos18.pdf)
>Modern microprocessors rely on **branch prediction units(BPUs)** to sustain uninterrupted instruction delivery to the execution pipeline across conditional branches.
#### BPU, Branch Prediction Units
- 通常由兩個部分組成: **branch target buffer** (BTB) and the **irectional predictor**.
:::warning
**:BOOM:當多個 Processes 在同個 Physical Core 執行時**，他們會使用同一個 BPU ，此動作開了一個**能操控共享的 BPU 狀態的洞給攻擊者**，正是一個 **Side-Channel**，能導出受攻擊者的 Branch Instruction 的方向或目標，此 leakage 可能危及到較重要的 data
:::
Attack example:
>When a branch instruction is conditioned on a bit of a secret key, **the key bits are leaked directly**. This occurs in implementations of exponentiation algorithms and other key mathematical operations of modern cryptographic schemes. The attacker may also **change the predictor state**, changing its behavior in the victim.
>**Side-channel attack on the BTB that creates BTB collisions** between the victim and the attacker processes, thus allowing the attacker to discover the location of a particular victim’s branch instruction in the address space, bypassing address space layout randomization.
## Quiz
### 測驗`1`
```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)
return false;
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
#### `MMM` 為`0x8080808080808080`
原理可以參照：
>7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。
#### 推論重點:
- uint64_t payload，64 位元
- `0x8080808080808080` 共 16 個十六進位的位數，每一個數字代表 4 bits，參閱題目上原本用 `& 0x80` 判斷是否為 ASCII。
### 延伸問題
> 1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性
**程式運作原理**
1. 傳入 string 陣列及其 `size`
2. 如果 `size` 為 0，回傳 `false`，即不是 ASCII
3. 之所以使用 `while ((i + 8) <= size)` 是因為基本比較就以 `& 0x80` 起跳，以下為迴圈內
1. **透過 memcpy，告知 compiler 以 uint64_t 進行 data alignment，對於效能有影響(?，待實驗)**
2. **13~14行**藉`bitwise 操作`，得知是否為ASCII
3. 以兩碼( 8 bits )為單位往後移
4. 最後在以原始方法，把剩下的部分一個個確定真的不是 ASCII
5. 都通過後，回傳 True
[data alignment 參考](https://hackmd.io/@sysprog/c-memory)
> data alignment 的意思就是， data 的 address 可以公平的被 1, 2, 4, 8,這些數字整除，從這些數字可以發現他們都是 2 的 N 次方 (N為從 0 開始的整數)。換句話說，這些 data object 可以用 1, 2, 4, 8 byte 去 alignment
> 現代的處理器處理一般的讀取跟寫入資料，如果沒有效能考量，不用特別處理 data alignment 的議題，例如 **intel x86 系統 是允許 data unalignment** 的！（老師上課有提到）
[data alignment 問題參考](https://stackoverflow.com/questions/26381206/why-does-an-uint64-t-needs-more-memory-than-2-uint32-ts-when-used-in-a-class-a)
> The rule for alignment (on x86 and x86_64) is generally to align a variable on it's size.
In other words, **32-bit variables are aligned on 4 bytes, 64-bit variables on 8 bytes, etc.**
e.g. uint32_t v.s. uint64_t
> 2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
可以參考測驗 `5` 來取得 A~Z 的範圍!
參考 `RinHizakura`...
>如果字元是小寫的英文子母，則 `lower_mask` 對應的 8 bits 就會是 `0x80`，大寫的字母亦然，`upper_mask` 對應的 8 bits 會是 `0x80`，因此，如果 `str` 的內容僅由大小寫字母組成，則 `lower_mask | upper_mask` 會得到 `0x8080808080808080`，我們可以藉此來判斷一個已知長度的字串，是否包含有效的英文大小寫字母。
**英文大小寫字母 ASCII 範圍:**
A~Z: **0x41~0x5A**
a~z: **0x61~0x7A**
```cpp
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
bool is_char(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);
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_mask = (a ^ z) & PACKED_BYTE(0x80);
uint64_t upper_mask = (A ^ Z) & PACKED_BYTE(0x80);
if ((lower_mask | upper_mask ) ^ PACKED_BYTE(0x80)){
return false;
}
i += 8;
}
while (i < size) {
if (str[i] & 0x80)
return false;
i++;
}
return true;
}
```
> 3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對 提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4
(20200924 未撰寫)
---
### 測驗`2`
```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. 解釋上述程式的運作原理
**程式運作原理**
`MASK` = **0x40**，這個 mask 是有用來判斷是否為字母，字母範例如下:
F = 0**1**00 0110
f = 0**1**10 0110
故利用 `0x40(0100 0000)` 作為 mask
根據上述兩例帶入，`letter` 為**0100 0000**
若為數字，`letter` 則為**0000 0000**
**shift** 於數字的 case 用不到，於字母的 case，在此需要以**9**為起點，故`AAA` = 3，`BBB` = 6
帶入上兩例 (F,f)，可得到**0000 1001**，也就是**9**
在帶入底下
`(in + shift)` -> 0100 0110 + 0000 1001 = **0100 1111**
最後`& 0xf`的目的是用於清除掉前面4碼
上例便是得到**1111**，也就是**15**
>2. 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值
此題解題想來自 [convert-hex-string-char-to-int](https://stackoverflow.com/questions/10156409/convert-hex-string-char-to-int)。
```cpp
#include <stddef.h>
#include <stdint.h>
#include <string.h>
uint64_t haxcharstr2val(const char str[])
{
int len = strlen(str);
// Check length of string
assert(len <= 18);
// Check if start with '0x'
assert(str[0] == '0' && (str[1] == 'x' || str[1] == 'X'));
int i = 2;
uint64_t val;
while (i <= size) {
uint8_t byte = str[i];
byte = hexchar2val(byte);
// shift 4 to make space for new digit, and add the 4 bits of the new digit
val = (val << 4) | (byte & 0xF);
}
return val;
}
```
---
### 測驗`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;
}
```
預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (`555` 是 3 的倍數)。
### 延伸問題:
>1. 解釋上述程式的原理;
數學式 $\frac{n}{D} = n * \frac{\frac{2^N}{D}}{2^N}$ ，此段程式首要解決的便是 `M`，也就是$\frac{2^N}{D}$
值得注意的是**程式第6行**，`uint64_t quotient = ((__uint128_t) M * n) >> 64;`，在此**向右 Shift 了 64個位元**，意同於除以 $2^{64}$，藉此得知`M`應要代表 $2^{64}$
`XXX`便為`0xFFFFFFFFFFFFFFFF`
>2. 由 Facebook 公司所維護的 jemalloc 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 include/jemalloc/internal/div.h 和 src/div.c 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
(20200924 未撰寫)
---
### 測驗`4`
>延伸測驗 3，我們想判斷某個數值能否被指定的除數所整除，在 `D` 和 `M` 都沿用的狀況下，程式碼如下:
```cpp=
bool divisible(uint32_t n)
{
return n * M <= YYY;
}
```
>以 D = 3 來說，divisible(7) 要得到 0 (即 7 無法被 3 整除)，divisible(87) 要得到 1 (即白痴是三的倍數)
參考 `RinHizakura`...
>$n * M$ 可以想成是把數字位移到剩下 $\frac{n}{D}$ 的小數部份，而 M - 1 則是 $\frac{1}{D}$ 的小數部份，要判斷 n 是否可以整除 D，思路是判斷 $\frac{n}{D}$ 的小數部份是否小於 $\frac{1}{D}$ (因為小數部份只能是 0、$\frac{1}{D}$、$\frac{2}{D}$…$D-\frac{1}{D}$)
根據上述推斷，可以得知 `YYY` 為 `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);
}
```
### 延伸問題:
>1. 解釋上述程式的原理
- 先解釋`PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)`如下:
- `(uint64_t)(b) & (0xff)` 可以取出最後八個位元
- `* 0x0101010101010101u` 用於複製這八個位元八次
- `VV1` 就是在測驗 1 中有用到的技巧，故選 `(e) 0x80`
- 確認為 ASCII 後，便是要利用 bitwise 製作出 `if(c - 'A' >= 0 && c - 'Z' <= 0)` 的效果
- 變數 `A` 用於判斷是否大於 `A` (若最左邊的 bit 為 1 則為 1)
- 變數 `Z` 用於判斷是否小於 `Z` (若最左邊的 bit 為 1 則為 1)
- 參考 `RinHizakura`...
>- 因此如果 c 同時滿足 >= 'A' 且 <= 'Z'，c + 128 - 'A' XOR c + 128 - 'Z' + 1 的結果會是 0b10000000，否則就是 0b00000000。
>- 又如果 s 是 'A' ~ 'Z' 之間的字元，最終對 chunk 處理的 mask 是 0b00100000(對應 **strtolower 的 1 << 5**)，也就是前面的結果 0b10000000 >> 2 所得到的 mask，不然就是 0b00000000。
因此:
VV2 = `(b) 0`
VV3 = `(c) -1`
VV4 = `(e) 0x80`
>2. 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
參照:[你所不知道的 C 語言：指標篇](https://hackmd.io/@ofAlpaca/SyzamVp_Q?type=view)
>`char *s="Hello world"` 此為string literal，和 `char s[]="Hello world"` 不同，前者存於read-only data section ，後者則是 stack 的 local variable。
底下是測資:
```cpp
#include <stdio.h>
#include <string.h>
int main()
{
/* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */
char str[] =
"This eBook is for the use of anyone anywhere at no cost and with \
almost no restrictions whatsoever. You may copy it, give it away or \
re-use it under the terms of the Project Gutenberg License included \
with this eBook or online at www.gutenberg.net";
int n = strlen(str);
strlower_vector(str, n);
puts(str);
}
```
在這裡 `char str[]` 改成 `char *str` 的話， `strlen()` 不能接受 null pointer ，會造成未定義的行為 (**undefined behavior**)。
可藉底下這段解決:
```cpp
#define strlens(s) (s==NULL?0:strlen(s))
```
### 測驗`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;
}
```
### 延伸問題:
>1. 解釋上述程式的原理
- 由於一開始無法直接理解這題的解法，故決定直接帶答案進去理解，答案如下:
- 參考 `sammer1107` ，解了一個困惑許久的觀念：
>首先每個 bit 的動作是獨立的，不會互相影響。所以我們其實是在分別計算每個 bit 的出現次數。
- `xor` 這個動作可以當作是**兩者相加，但不進位**，這個觀念可以用於判斷出現兩次。
| a | b | output |
| --- | --- |:------:|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- 推廣到判斷三次，程式內的 `lower` 和 `higher` ，其實概念是兩個位元代表2進位的數字，出現第一次`01`,第二次`10`，第三次`00`來代表
以**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
綜合上述，其實可以看出來，第一次我們使用 `lower` 保留紀錄，第二次這個紀錄會被傳到 `higher` ，若遇到第三次，則兩者歸零，因此在遇到只有一次的case ， `lower` 會保留住只出現一次的數字，故在最後 return `lower`。
>2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時
(20200924 未撰寫)
>3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼
- 重複4次這種偶數，原本可能直覺要套用 `mod 4` 算法，其實套用 `mod 2` 的算法就可以了，因為最主要是要選擇一個 `m` 確保 `4k mod m == 0`
- 重複5次，會想到要套用 `mod 5` ，但這樣必須要用到3個位元來記錄次數了。
- 此時可以回想前面，主要目的是要找到 `mod m == 0` 的 `m` ， `m` 可以推想為 `n` (重複次數) 的最小質因數，舉例而言，重複9次可以套用 `mod 3` 的算法。
Sign in with Wallet
Connect another wallet