# 2020q3 Homework2 (quiz2)
contributed by < `KairC` >
[Github](https://github.com/KairC/)
## 測驗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
### 延伸問題
:::success
1. 解釋上述程式的運作原理，特別是為何用到 `memcpy` 呢？提示: 與 data alignment 有關，詳閱 [C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)
:::
* 運作原理：利用 `memcpy()` 複製字串 `str` 中 8 個 bytes 的資料 (8 個字元) 到 `payload`，並且對 `payload` 中每 1 byte 與 `0x80` 做 `&` 運算。而`payload` 總共有 8 bytes ，因此 `line 13` 將 `payload` 與 8 個 `0x80` 做 `&` 運算，也就是 `payload & 0x8080808080808080`。
為何要與 `0x80` 做 `&` 運算？因為要確保字元的數值 < 128 ，而 128 的 16 進位就是 `0x80` ，2 進位表示是 `1000 0000` ，代表若數值的第 8 個 bit 為 1 ，數值就會 >= 128。因此將字元的數值與 `1000 0000` 做 `&` 運算，意思就是確認每個字元的第 8 個 bit 是否為 1 ，若字元數值 < 128 則 `&` 運算後結果為 `0` ，若 8 個字元中的其中一個字元數值超過了 127 ，則 `&` 運算後的結果就不會是 `0` ，因此 if 判斷為 `true` ，執行 `return false` 。
`line 10` 的 while-loop 用來每一次複製 8 bytes 資料並做檢查，做完後往下一組 8 bytes 資料做檢查。`i` 為字串 `str` 的記憶體位址的偏移量，進入迴圈的判斷條件為，從當前的記憶體位址的偏移量加上 8 bytes 的位移會不會超過字串長度，意思是我將要從字串中取 8 bytes 資料，要先確認是否在容許的範圍內。在每一次迴圈結束前會做 `i += 8` ，代表已檢查完該次從字串中取得的 8 bytes 資料，將偏移量往後 8 bytes 移動。
`line 17` 的 while-loop 用來確保剩下的字元能被檢查到，因為字串長度不會每次都剛好是 8 的倍數，若剩下的最後一段字串不足 8 bytes ，就會需要在這裡進行處理。每一次檢查一個字元，直到偏移量 `i` 超過字串的最大長度，代表已檢查完整個字串。
* `memcpy()` 的意義在於搬動資料時，可以避免 load of misaligned address 或者是 store of misaligned address。以下用 [q1_ext.c](https://github.com/KairC/sysprog_quiz2/blob/master/q1_ext.c) 測試三種不同的複製資料方式做為範例︰
```cpp=
...
/*** use memcpy to copy 8 bytes string at one time.***/
memcpy(payload_, s, 8);
/*** not use memcpy to copy 8 bytes string at one time.***/
*payload_ = *((uint64_t *) s);
/*** not use memcpy to copy 8 bytes string one by one.***/
for (int i = 0; i < 8; i++) {
*((char *) payload_ + i) = *(s + i);
}
...
```
以下為不使用 `memcpy()` 而是用第二種方式進行複製資料，也就是從字串 `s` 中抓取 8 bytes 資料 assign 給 `payload_` 指向的記憶體位置。
編譯時開啟 `-fsanitize=alignment` ，`$gcc -fsanitize=alignment -o q1_ext_alignment q1_ext.c` 執行後出現以下錯誤訊息︰
```
q1_ext.c:15:5: runtime error: load of misaligned address 0x7ffe93a989ff for type 'uint64_t', which requires 8 byte alignment
0x7ffe93a989ff: note: pointer points here
60 5c 55 00 49 27 6d 20 61 20 64 6f 67 2e 00 53 68 65 20 69 73 20 61 20 70 69 67 2e 00 00 03 9d
^
q1_ext.c:25:17: runtime error: load of misaligned address 0x7ffe93a98a0a for type 'uint64_t', which requires 8 byte alignment
0x7ffe93a98a0a: note: pointer points here
6f 67 2e 00 53 68 65 20 69 73 20 61 20 70 69 67 2e 00 00 03 9d 9a ce e1 0d bf 20 8b a9 93 fe 7f
^
q1_ext.c:25:15: runtime error: store to misaligned address 0x7ffe93a989ff for type 'uint64_t', which requires 8 byte alignment
0x7ffe93a989ff: note: pointer points here
60 5c 55 00 49 27 6d 20 61 20 64 6f 67 2e 00 53 68 65 20 69 73 20 61 20 70 69 67 2e 00 00 03 9d
^
q1_ext.c:34:5: runtime error: load of misaligned address 0x7ffe93a989ff for type 'uint64_t', which requires 8 byte alignment
0x7ffe93a989ff: note: pointer points here
60 5c 55 00 53 68 65 20 69 73 20 61 67 2e 00 53 68 65 20 69 73 20 61 20 70 69 67 2e 00 00 03 9d
^
```
`line:15` 與 `line:34` 是以 unsigned long int (8 bytes) 讀取 `payload_` 指向的記憶體位置並列印出其中的資料，因此以 8 bytes 讀取未對齊的資料必定會有 error。
重點在 `line:25` 此行是用第二種複製方式才會產生的 error，右手邊的 `*((uint64_t *) s)` 是以 uint64_t (8 bytes) 讀取字串 `s`，而字串 `s` 的記憶體位置對於 8 bytes 讀取的方式而言是未對齊的，因此會產生 load of misaligned address。接著程式看了一下欲搬運到的目的地 `*payload_` 時，`*payload_` 明明應該是個 uint64_t (8 bytes) 的位置，但是 `payload_` 指向的記憶體位置對於 8 bytes 而言卻是未對齊的，因此將資料搬到未對齊的位置產生 store to misaligned address。
雖然在 intel 架構下上述程式不使用 `memcpy()` 也能成功執行，但是並非所有處理器架構都能處理 `misaligned data` ，例如 ARM 架構下若存取未對齊的記憶體位址，處理器會產生 Alignment fault。
* 例如：[ARM Architecture Reference Manual ARMv7-A and ARMv7-R edition](https://developer.arm.com/documentation/ddi0406/c/Application-Level-Architecture/Application-Level-Memory-Model/Memory-types-and-attributes-and-the-memory-order-model/Atomicity-in-the-ARM-architecture) (Table A3-1 on page A3-106)
* 不同的指令會做不同的 Alignment check ，大部分指令在發生 check fail 後則會產生 Alignment fault。
為何 `memcpy()` 能避免避免 load of misaligned address 或者是 store of misaligned address 呢？根據原始碼，如下
[glibc/string/memcpy.c](https://github.com/lattera/glibc/blob/master/string/memcpy.c)
[glibc/sysdeps/i386/memcopy.h](https://github.com/lattera/glibc/blob/master/sysdeps/i386/memcopy.h)
[glibc/sysdeps/generic/memcopy.h](https://github.com/lattera/glibc/blob/master/sysdeps/generic/memcopy.h)
在欲搬動的資料長度足夠長 `len >= OP_T_THRES` 的情況下
若 dst 所在的位置不是 OPSIZ 的倍數，代表 dst 有一小段 bytes 會是未對齊的
`memcpy()` 先把未對齊的部分 `(-dstp) % OPSIZ` 一個 byte 一個 byte 的複製
dst 剩餘的部分為 `len -= (-dstp) % OPSIZ;` 就會是對齊的，可以一個一個 page 或者是一個一個 word 去複製。
上面 dst 做完處理後可以確定是對齊的，然而 src 有可能是未對齊的，因此在 `WORD_COPY_FWD()` 中會對 src 是否對齊做處理。
如果長度太小，直接一個 byte 一個 byte 的複製過去就行
:::success
2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」
:::
TODO
模仿測驗 5 在字串中找出大寫英文字母的方法
就能夠找出小寫英文字母
:::success
3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對
> 提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: [Schema Validation with Intel® Streaming SIMD Extensions 4](https://software.intel.com/content/www/us/en/develop/articles/schema-validation-with-intel-streaming-simd-extensions-4-intel-sse4.html)
:::
TODO
[SIMD Processing (Vector Processors)](https://hackmd.io/xuG-FTj3RRea4x0PiMc0bw)
[Intel® Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#)
[x86 Assembly/X86 Architecture](https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture)
[CPUID](https://en.wikipedia.org/wiki/CPUID)
以下為本次作業使用的 CPU 資訊
```
$sudo lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 36 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 42
Model name: Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz
Stepping: 7
CPU MHz: 1292.842
CPU max MHz: 3100.0000
CPU min MHz: 800.0000
BogoMIPS: 4988.67
Virtualization: VT-x
L1d cache: 64 KiB
L1i cache: 64 KiB
L2 cache: 512 KiB
L3 cache: 3 MiB
NUMA node0 CPU(s): 0-3
Vulnerability Itlb multihit: KVM: Mitigation: VMX disabled
Vulnerability L1tf: Mitigation; PTE Inversion; VMX conditional cache flushes, SMT vulnerable
Vulnerability Mds: Mitigation; Clear CPU buffers; SMT vulnerable
Vulnerability Meltdown: Mitigation; PTI
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl and seccomp
Vulnerability Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer sanitization
Vulnerability Spectre v2: Mitigation; Full generic retpoline, IBPB conditional, IBRS_FW, STIBP conditional, RSB filling
Vulnerability Srbds: Not affected
Vulnerability Tsx async abort: Not affected
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ht tm pbe syscall nx rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic popcnt tsc_deadline_timer aes xsave avx lahf_lm epb pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid xsaveopt dtherm ida arat pln pts md_clear flush_l1d
```
可參照上方的 CPU 資訊確認哪些 Flags 有開啟
可以看到其中有 sse sse2 ssse3 sse4_1 sse4_2 因此應能用 CPU 完成此次作業
原本想測試 `__m128i _mm_loadu_si32 (void const* mem_addr)` 卻沒辦法用
gcc-9.3.0 編譯時出現以下訊息
```
q1_ext3.c: In function ‘is_ascii’:
q1_ext3.c:13:18: warning: implicit declaration of function ‘_mm_loadu_si32’; did you mean ‘_mm_loadu_si64’? [-Wimplicit-function-declaration]
13 | _payload = _mm_loadu_si32((__m128i *)str + i);
| ^~~~~~~~~~~~~~
| _mm_loadu_si64
q1_ext3.c:13:18: error: incompatible types when assigning to type ‘__m128i’ {aka ‘__vector(2) long long int’} from type ‘int’
```
原因是 : [Bug 95483 - [i386] Missing SIMD functions](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95483)
用 gcc-11.1.0 即可正常編譯
:::warning
* 還有一些 intrinsics 例如在 SVML library 裡面的，只能用 intel compilers 才能編譯，用 gcc 開發就沒辦法用，要特別注意。不然就要自己額外加 library 來用。
* 在使用上，要注意使用的 intrinsics 中，取最新的那個版本所在的標頭檔，裡頭會自動包含前幾個版本的標頭檔，這樣就不必 include 一堆東西。
[C++ error: ‘_mm_sin_ps’ was not declared in this scope](https://stackoverflow.com/questions/31978592/c-error-mm-sin-ps-was-not-declared-in-this-scope)
[Header files for x86 SIMD intrinsics](https://stackoverflow.com/questions/11228855/header-files-for-x86-simd-intrinsics)
[gcc: x86 Options](https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html)
[gcc/gcc/config/i386/nmmintrin.h](https://github.com/gcc-mirror/gcc/blob/master/gcc/config/i386/nmmintrin.h)
(雖然 SSE4.2 在 [Intel® Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#) 中是說要 `#include <nmmintrin.h>` ，但是我去看了一下 gcc 的程式碼，SSE4.2 是實作在 SSE4.1 的標頭檔 `smmintrin.h` 裡，`nmmintrin.h` 裡頭只有 `#include <smmintrin.h>`)
:::
From : [Intel® Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#ig_expand=6130,6073,4195,4278,4278,4305,4278,6102,4338,4369,4369,4373,4421,4371,2309,4326,317,4371,4368,2307,2307,6553,6553,2307,6791,960,1090&techs=SSE4_2)
當選用 `_SIDD_CMP_RANGES` 做為比較的模式，會進行以下流程
```
1: // ranges
IntRes1 := 0
FOR i := 0 to UpperBound
FOR j := 0 to UpperBound
IntRes1[i] := IntRes1[i] OR (BoolRes.word[i].bit[j] AND BoolRes.word[i].bit[j+1])
j += 2
ENDFOR
ENDFOR
```
BoolRes 用來記錄字串 a 與字串 b 比較是否相等後得到的 boolean value
e.g. BoolRes.word[i].bit[j] 記錄字元 a[i] 與 字元 b[j] 比較後得到的 boolean value
`i` 代表目標字串的 index
`j` 代表要用來限制 range 的字串的 index
意思是會確認 b[0] <= a[0] <= b[1] , b[2] <= a[1] <= b[3] , ...
( b[0] <= a[0] AND a[0] <= b[1] ) OR ( b[2] <= a[1] AND a[1] <= b[3] ) OR ...
看字串 a 的字元是否有落在字串 b 中任一對設置好的範圍內
:::warning
我個人在閱讀 [Intel® Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#ig_expand=6130,6073,4195,4278,4278,4305,4278,6102,4338,4369,4369,4373,4421,4371,2309,4326,317,4371,4368,2307,2307,6553,6553,2307,6791,960,1090&techs=SSE4_2) 中 intrinsics operation 的 pseudo code 時，有在一個小地方感到困惑。不論選擇的比較模式 (Mode) 為何，兩字串中字元的互相比較一律用 `==` (equal) ，這點讓我有些疑惑。在翻閱 [Intel® 64 and IA-32 architectures software developer’s manual](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) 中 Volume 2B 的 4.1.3 節 Table 4-2 之後，可以明確看到當 Mode 選擇 Ranges 會用 "greater than or equal" & "less than or equal" 做比較。
:::
下圖為實際使用 intrinsics 的結果
程式碼 : [q1_ext3.c](https://github.com/KairC/sysprog_quiz2/blob/master/q1_ext3.c)
編譯方式 : `$gcc -msse4.2 q1_ext3.c -O0 -o q1_ext3 `
( [GCC Online Document 3.19.59 x86 Options](https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html) )
:::warning
由於不清楚題目中 "常見的" 英文標點符號到底範圍是什麼，因此憑個人喜好選擇了一部份標點符號做為標準。
:::
## 測驗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;
}
```
MASK = 0x40
AAA = 3
BBB = 6
### 延伸問題
:::success
1. 解釋上述程式的運作原理;
:::
* 每一個字元 8 bits 轉換後只佔用了低位的 4 bits 儲存數值
* `'0'`、...、`'9'` 的 2 進位表示法 : `0011 0000` ~ `0011 1001`
* 轉換後 : `0000 0000` ~ `0000 1001`
* `'a'`、...、`'f'` 的 2 進位表示法 : `0110 0001` ~ `0110 0110`
* 轉換後 : `0000 1010` ~ `0000 1111`
* `'A'`、...、`'F'` 的 2 進位表示法 : `0100 0001` ~ `0100 0110`
* 轉換後 : `0000 1010` ~ `0000 1111`
* 可以觀察到，數字字元的轉換後會與原先的第 1 位到第 4 位 bit 一樣，而字母字元的轉換後會與原先的第 1 位到第 4 位 bit 再加上 `1001` 的結果相同。
* 可進一步看成：
* 數字字元 : 原先的 `in = 0011 xxxx` 加上 `shift = 0000 0000`
* 字母字元 : 原先的 `in = 0110 xxxx or 0100 0001` 加上 `shift = 0000 1001`
* 因此 `line 3` 與 `line 4` 目的就是做出符合預期的 shift 。
* 接著為了留下第 1 位到第 4 位 bit 並消除高位的 4 bits 數值，將 ( i +shift ) 後的值與 `0xf (0000 1111)` 做 `&` 運算。
:::success
2. 將 `hexchar2val` 擴充為允許 ``"0xFF"``, ``"0xCAFEBABE"``, ``"0x8BADF00D"`` 等字串輸入，且輸出對應的十進位數值
> [Hexspeak](https://en.wikipedia.org/wiki/Hexspeak)
:::
* 最後要得到的結果最長是 32 位元整數，因此 `val` 用來儲存轉換後的數值。
* `range` 代表預計要轉換的字元個數，例如 `0xCAFEBABE` 要轉換的字元有 8 個，分別是 `'C'`、`'A'`、`'F'`、`'E'`、`'B'`、`'A'`、`'B'`、`'E'`。
* `payload` 用來儲存單一字元轉換後的數值，從字串中最後一個字元開始做轉換，並根據字元的順序做位移後，加入 `val` 。例如 `'F'` 是由右往左數第五個字元，因此轉換後的 4 bits 數值，需向左移 4*(range - 1 - 2) 個 bit 。
* 從最後一個字元開始轉換的話，for-loop 的終止條件不能用 `i >= 0` ，因為 `i` 是 `unsigned` ，做 `i--` 會有 integer overflow 的問題，永遠不會終止。
```cpp=
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
uint32_t hexchar2val(const char in[]) {
uint32_t val = 0;
uint32_t range = strlen(in) - 2; // delete "0x"
for (uint32_t i = range - 1; i != (unsigned int) -1; i--) {
uint32_t payload = (uint32_t) * (in + i + 2);
const uint32_t letter = payload & 0x00000040;
const uint32_t shift = (letter >> 3) | (letter >> 6);
payload = (payload + shift) & 0x0000000f;
payload <<= 4 * (range - 1 - i);
printf("%x\n", payload);
val += payload;
}
printf("%x\n", val);
return val;
}
int main()
{
printf("%u\n", hexchar2val("0xFF"));
return 0;
}
```
## 測驗3
參考自 [@guaneec](https://hackmd.io/@guaneec/sp2020q3-h2#Q3---Fast-mod) 同學的共筆
```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;
}
```
XXX = 0xFFFFFFFFFFFFFFFF
### 延伸問題
:::success
1. 解釋上述程式的原理;
:::
根據 [Division by Invariant Integers using Multiplication (1991)](https://gmplib.org/~tege/divcnst-pldi94.pdf) 這篇論文所述
在 Ch.4 Unsigned division
對 $\dfrac{1}{d}$ 先找出合理的近似值 $\dfrac{m}{2^{N+L}}$ 使 (4.1) 成立
在 Theorem 4.2 經由 $\dfrac{m}{2^{N+L}}-q < 1$ 證明剛剛找到的近似值是可行的
$2^{N+\ell}\ \leq\ m\ *\ d\ \leq\ 2^{N+\ell}+2^{\ell}\ ,\ m、d、\ell\ \ are\ \ nonnegative\ \ ...\ (a)$
$\left\lfloor{\dfrac{n}{d}}\right\rfloor\ =\ \left\lfloor{\dfrac{m*n}{2^{N+\ell}}}\right\rfloor\ whenever\ \ 0\leq n\leq 2^{N}-1\ \ ...\ (b)$
當 $(a)$ 成立時，**除以 $d$** 可以用 **乘以 $\dfrac{m}{2^{N+\ell}}$** 替換。
在 `line 6` ，依據 Theorem 4.2 可以知道 $quotient = \left\lfloor\dfrac{m*n}{2^{N+\ell}}\right\rfloor = \left\lfloor\dfrac{M*n}{2^{64}}\right\rfloor$，$2^{N+\ell}=2^{64}$，$N=32\ ,\ \ell=32$
由 $(a)$ 可推得 $M$ 至少得是 $\left\lceil \dfrac{2^{64}}{D} \right\rceil$，在 `line 2` 寫成 $M = \dfrac{XXX}{D} + 1\ \ ...\ (1)$
將 $(1)$ 左右各乘上 $D$ ，可得到 $2^{64}\ \leq \ M*D = XXX + D\ \leq\ 2^{64}+2^{32}\ \ ...\ (2)$
由於 $D \geq 1$，得知 $XXX \geq 0xFFFFFFFFFFFFFFFF$，$XXX$ 至少得是 $0xFFFFFFFFFFFFFFFF$ 才能使不等式 $(2)$ 成立。
不過程式碼中限制了 $M$ 為 64-bit 無號整數，若 $D=1$ 會導致超過 64-bit 的部分被丟棄而得到錯誤的 $M$，因此需要 $D > 1$。
:::success
2. 由 Facebook 公司所維護的 [jemalloc](https://github.com/jemalloc/jemalloc) 是個高效能的記憶體配置器 (memory allocator，即 malloc 和 free 函式對應的實作)，特別在多核多執行緒的環境有優異表現，在其原始程式碼 [include/jemalloc/internal/div.h](https://github.com/jemalloc/jemalloc/blob/dev/include/jemalloc/internal/div.h) 和 [src/div.c](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距;
:::
[測試程式: q3_ext.c](https:// "title")
假設一等式為 $n=q*d$ ，$n$、$q$、$d$ 皆為 integer，已知 $n$、$d$ ，求 $q = n\ /\ d$
$All\ \ division\ \ is\ \ exact\ \ ,\ \ not\ \ C-style\ \ rounding.$
$\begin{split} \Bigl\lfloor {\Bigl\lceil{\dfrac{2^{k}}{d}} \Bigr\rceil * \dfrac{n}{2^{k}}} \Bigr\rfloor
&= \Bigl\lfloor \dfrac{\left( 2^{k} + r \right)}{d} * \dfrac{n}{2^{k}} \Bigr\rfloor \ \ ,\ \ r\ =\ -2^{k}\ \%\ d\ \ ,\ \ 0\ \leq\ r\ \lt\ \left| \ d\ \right|\ \ \\
&= \Bigl\lfloor {\dfrac{2^{k}}{d} * \dfrac{n}{2^{k}}}\ +\ {\dfrac{r}{d} * \dfrac{n}{2^{k}}} \Bigr\rfloor \\
&= \Bigl\lfloor {\dfrac{n}{d} + \left(\dfrac{r}{d}\right)*\left(\dfrac{n}{2^{k}}\right)} \Bigr\rfloor\ \ ,\ \ d\ \ divides\ \ n\ \ exactly. \\
&= \dfrac{n}{d}\ +\ \Bigl\lfloor\left(\dfrac{r}{d}\right)*\left(\dfrac{n}{2^{k}}\right)\Bigr\rfloor \ \ ,\ \ \dfrac{r}{d}*\dfrac{n}{2^{k}}\ \ \lt\ \ 1 \\
&= \dfrac{n}{d}\\
\end{split}$
根據以上推導可知，$n\ /\ d$ 可以寫成 $\Bigl\lfloor {\Bigl\lceil{\dfrac{2^{k}}{d}} \Bigr\rceil * \dfrac{n}{2^{k}}} \Bigr\rfloor$ 的形式。
但是在 C 語言中，在做整數除法的時候會做 floor 而非期望的 ceiling，因此 $\Bigl\lceil{\dfrac{2^{k}}{d}}\Bigr\rceil$ 以下方程式碼實作 ceiling，對應 [jemalloc/src/div.c 的第40行至第50行](https://github.com/jemalloc/jemalloc/blob/dev/src/div.c)
```cpp=
...
uint64_t two_to_k = ((uint64_t)1 << 32); // 2^k , k=32
uint32_t magic = (uint32_t)(two_to_k / d); // (2^k)/d
if (two_to_k % d != 0) { // 做 ceiling 判斷，有餘數則取整數部份+1
magic++;
}
...
```
得到 magic 後，在 `div_compute()` 計算出快速除法的結果。
下圖為利用 gcc 編譯並關閉最佳化後整數除法指令及快速除法的效能差距。
編譯指令為 `$gcc q3_ext.c -O0 -o q3_ext`
(參考資料 : [gnuplot 語法解說和示範](https://hackmd.io/@sysprog/gnu-linux-dev/https%3A%2F%2Fhackmd.io%2Fs%2FSkwp-alOg))
## 測驗4
( c )
在測驗 3 中需要先算出 quotient 才能得到 r
而測驗 4 的目的是學習如何不算出 quotient 就能判別 n/d 是否整除
[Faster Remainder by Direct Computation
Applications to Compilers and Software Libraries](https://arxiv.org/pdf/1902.01961.pdf)
(備用連結 : [點我](https://drive.google.com/file/d/1Y9XdRa4ZySLw7_Nc3IoaVjGW7zMVbAVh/view?usp=sharing) )
運作原理 : [Faster Remainder by Direct Computation Applications to Compilers and Software Libraries 讀後筆記](https://hackmd.io/akKsVGYqSCaVtBe3ZqYy6Q?view#41-SOFTWARE-IMPLEMENTATION)
## 測驗5
VV1 = 0x80
VV2 = 0
VV3 = (-1)
VV4 = 0x80
### 延伸問題
:::success
1. 解釋上述程式的原理;
:::
A : *chunck 中的字元做 shift (128 - 'A' + 0) 後的結果，讓 < 'A' 的字元在 128 以下，而 >= 'A' 的字元至少會是 128 以上 (1xxx xxxx)
Z : *chunck 中的字元做 shift (128 - 'Z' - 1)後的結果，讓 < 'Z' 的字元在 128 以下，而 > 'Z' 的字元至少會是 128 以上 (1xxx xxxx)
A ^ Z : 將 A 跟 Z 做 XOR，由於兩者中 > 'Z' 的部分都至少是 128 (1xxx xxx)，因此做完 XOR 後會導致 > 'Z' 的字元的最高位 bit 變成 0。而介於 'A' 跟 'Z' 的字元則會在做 XOR 後最高位 bit 為 1。
e.g.
*chunck = "AbCd"
= 0100 0001 | 0110 0010 | 0100 0011 | 0110 0100
A
= 1000 0000 | 1010 0001 | 1000 0010 | 1010 0011
Z
= 0110 0110 | 1000 0111 | 0110 1000 | 1000 1001
A ^ Z
= 1110 0110 | 0010 0110 | 1110 1010 | 0010 1010
(A ^ Z) & PACKED_BYTE(VV4)
= 1000 0000 | 0000 0000 | 1000 0000 | 0000 0000
mask = (A ^ Z) & PACKED_BYTE(VV4) >> 2
= 0010 0000 | 0000 0000 | 0010 0000 | 0000 0000
*chunck ^ mask
= 0100 0001 | 0110 0010 | 0100 0011 | 0110 0100
^ 0010 0000 | 0000 0000 | 0010 0000 | 0000 0000
= 0110 0001 | 0110 0010 | 0110 0011 | 0110 0100
= "abcd"
:::success
2. 將前述測試程式 `main` 函式的 `char str[]` 更換為 `char *str`，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為
:::
`char str[]` 更換為 `char *str` 後，gdb 執行結果為
```
Starting program: /home/kai/Desktop/q5
Program received signal SIGSEGV, Segmentation fault.
0x00005555555552ee in strlower_vector (
s=0x555555556008 "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 include"..., n=248) at q5.c:31
31 *chunk ^= mask;
Program terminated with signal SIGSEGV, Segmentation fault.
The program no longer exists.
```
在 [ISO/IEC 9899 中 6.7.8](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf#%5B%7B%22num%22%3A272%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C-27%2C816%2Cnull%5D) 有提到
>32 EXAMPLE 8 The declaration
>
>**char s[] = "abc", t[3] = "abc";**
>
>defines ‘‘plain’’ **char** array objects **s** and **t** whose elements are initialized with character string literals.
>This declaration is identical to
>
>**char s[] = { 'a', 'b', 'c', '\0' },
> t[] = { 'a', 'b', 'c' };**
>
>The contents of the arrays are modifiable. On the other hand, the declaration
>
>**char** ***p** **=** **"abc";**
>
>defines **p** with type ‘‘pointer to **char**’’ and initializes it to point to an object with type ‘‘array of **char**’’ with length 4 whose elements are initialized with a character string literal. If an attempt is made to use **p** to modify the contents of the array, the behavior is undefined.
經由 gdb 可得知 `uint64_t *chunk in fuction strlower_vector()` 指向的記憶體位址與 `char *str in main()` 相同，因此當執行 `*chunk ^= mask;` 時代表要對 `char *str` 指向的 object 做更動，這樣的行為是 ==undefined behavior==.
## 測驗6
KKK = ~higher
JJJ = ~lower
[LeetCode 137. Single Number II - Discuss - Detailed explanation and generalization of the bitwise operation method for single numbers](https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers)
題目 : array 中的每個數字會出現 k 次，k > 1，只有一個特別的數字會出現 p 次， p >= 1 ， p % k != 0 .
array 中的 elements 皆為 32-bit integer
一個 element 的每一個 bit 各自有一個 counter 計算 1 出現的次數
因此有 32 個 m-bit counter , $2^m >= k\ ,\ m >= \log{k}$ , m 取符合條件的最小正整數
每讀進一個 32-bit integer
每一個 counter 會各自計數並套上 mask
單一個 counter 的 binary form 為 $c_m\ ,\ ...,\ c_2\ ,\ c_1$
counter 如何計算次數 ?
每計數一次，第一位 bit 只會有 0 跟 1 兩種結果
但是其他位 bit 須要看前幾位 bit 的情形來決定是否改變值
例如當前 counter 為 1011 ，scan bit 為 1 ，計數一次後為 1100
i 為 scan bit，為 0 | 1
c4 ^= c3 & c2 & c1 & i
c3 ^= c2 & c1 & i
c2 ^= c1 & i
c1 ^= i
( 注意執行順序 )
mask 的目的是為了讓 counter 在數到 k 個 1 時，會自動歸零
如此一來當每個 element 計數完後，出現 k 次的 element 皆不會留下記錄
counters 裡只會留下 p 次
mask 的原理，單獨拿一個 counter 來看
為了使 counter 在數到非 k 次時維持不變，數到 k 次時歸零
首先思考如何從 ( counter = k ) &= mask 得到 0000 ... 0000 ?
mask 一定是 0000 ... 0000
將 k 的 binary form，$k_m\ ,\ ...,\ k_2\ ,\ k_1$
其中為 1 的 bit 保持不變，為 0 的 bit 做 ~ 運算
接著把每個 bit 做 & 運算可得到 1
把 1 做 ~ 運算即可得到 0
將這個結果做為 mask 跟 counter = k 做 & 運算可得到 0000 ... 0000
依照以上模式，當 ( counter = x )， 其 binary form 為 $x_m\ ,\ ...,\ x_2\ ,\ x_1$
mask = ~ ( y1 & y2 & y3 & ... & ym )
* 當 $k_j = 1$ ， $y_j = x_j$ ， $j\ \ for\ \ 1\ \ to\ \ m$
* 當 $k_j = 0$ ， $y_j =\ \sim x_j$ ， $j\ \ for\ \ 1\ \ to\ \ m$
當 x != k 時，肯定至少有一個 bit 與 k 不同，假設是第 $i$ 個位置的 bit $x_i$ ，則 $x_i\ !=\ k_i$
若 $k_i=1$ ，則 $x_i$ = 0 ， $y_i = x_i = 0$
若 $k_i=0$ ，則 $x_i$ = 1 ， $y_i =\ \sim x_i\ = 0$
mask = ~ (0) ，得到 mask = 1
(counter = x ) &= mask 可維持原來的值不變
接著將 counter 推廣成 32 個 counters
反正每個 counter 都會同時計數，也都要數到第 k 次時歸 0
可以將 $x_j$ 做為 32 個 counters 的第 j 個 bit 組合起來的 32-bit integer
明顯的這些 $x_j$ 做 bitwise operation 時每個 bit 各自獨立，意即每個 counter 各自獨立
因此也能利用上述單一 counter 的情況來找到 mask ，只是 $x_j$ 從 1-bit 變成 32-bit
最後用此 32-bit mask 同時套用在 32 個 counters 上
最後想要輸出的結果是特別出現 p 次的那個數，那該怎麼得到呢 ?
p' = p % k , 因為 p 有可能 > k
在 p' 的 binary form 中出現 1 的 bit 位置 $p^{'}_j$ ，對應到的 $x_j$ 都能做為結果輸出。
假設出現 p 次的那個 32-bit integer 為 $S$
當 scan 完所有 elements 後，s 有出現 1 的 bit 位置，假設是 $s_i$
counter $c_i$ 此時的值會等於 p' ，因為其他在 bit i 出現 1 的 elements 都出現 k 次了，也就是那些計數都歸零，只留下 p' .
將所有 32 個 counters 擺在一起看，就是 $S$ 數了 p' 次
$\begin{split} p^{'} * S\
&=\ p^{'}_1*2^{0}*S\ +\ p^{'}_2*2^{1}*S\ +\ p^{'}_3*2^{2}*S\ +\ ...\ +\ p^{'}_m*2^{m-1}*S \\
&=\ 2^0*(p^{'}_1*S)\ +\ 2^1*(p^{'}_2*S)\ +\ 2^2*(p^{'}_3*S)\ +\ ...\ +\ 2^{m-1}*(p^{'}_m*S) \\
&=\ 2^0*(x_1)\ +\ 2^1*(x_2)\ +\ 2^2*(x_3)\ +\ ...\ +\ 2^{m-1}*(x_m) \\
\end{split}$
p' 出現 1 的 bit 位置 $p^{'}_i$ 對應到的 $x_i$ 都會等於 $S$
p' 出現 0 的 bit 位置 $p^{'}_j$ 對應到的 $x_j$ 都會等於 $0000\ ...\ 0000$
### 延伸問題
:::success
1. 解釋上述程式的原理;
:::
lower 為 32 個 counters 的第 1 個 bit 組合起來 i.e. $x_1$
higher 為 32 個 counters 的第 2 個 bit 組合起來 i.e. $x_2$
出現三次， k = 3
單一個 counter 期望會出現 b'00' , b'01' , b'10'
當 counter 經過 XOR 後未數到 3 , 經過 mask 後應該維持不變
當 counter 經過 XOR 後已數到 3 , i.e. b'11' , 經過 mask 後應該回歸到 b'00'
但是題目中為何是 lower 先計數完才換 higher ?
而且連 mask 都沒看到 ?
照[上方連結](https://leetcode.com/problems/single-number-ii/discuss/43295/Detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers)的寫法應該如下
```cpp=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
higher ^= lower & nums[i];
lower ^= nums[i];
mask = ~(lower & higher);
higher &= mask;
lower &= mask;
}
return lower;
}
```
總之先畫真值表
| bit _ 2 | bit _ 1 | input _ bit | new_bit _ 2 | new_bit _ 1 |
| ------- | ------- | --------- | ----------- | ----------- |
| **H** | **L** | **I** | **NH** | **NL** |
| 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 |
| 1 | 1 | 0 | x | x |
| 1 | 1 | 1 | x | x |
(為求式子表達簡便，H、L、I、NH、NL 為代號)
將真值表轉為布林表示式 :
* **NL** = ( ~**H** ) * ( ~**L** ) * **I** + ( ~**H** ) * **L** * ( ~**I** )
= ( ~**H** ) * (( ~**L** ) * **I** + **L** * ( ~**I** ))
This could be written as ( ~**H** ) & ( **L** ^ **I** )
* **NH** = ( ~**H** ) * **L** * **I** + **H** * ( ~**L** ) * ( ~**I** )
This could be written as ( ( ~**H** ) & **L** & **I** ) | ( **H** & ( ~**L** ) & ( ~**I** ) )
寫成程式碼 :
```cpp=
int singleNumber(int *nums, int numsSize)
{
int lower = 0, higher = 0;
for (int i = 0; i < numsSize; i++) {
int lower_old = lower;
lower ^= nums[i];
lower &= ~higher;
higher = ((~higher) & lower_old & nums[i]) | (higher & (~lower_old) & (~nums[i]));
}
return lower;
}
```
長得雖然跟題目很像，但還是不一樣，因為需要多一個變數去存舊的 lower 值。
有辦法用新的 lower 值來計算新的 higher 值嗎 ?
再畫一張真值表
| bit _ 2 | new_bit _ 1 | input _ bit | new_bit _ 2 |
| ------- | ------- | --------- | ----------- |
| **H** | **NL** | **I** | **NH** | |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | x | 0 | x |
| 1 | x | 1 | x |
* **NH** = ( ~**H** ) * ( ~**NL** ) * **I** + **H** * ( ~**NL** ) * ( ~**I** )
= ( ~**NL** ) * (( ~**H** ) * **I** + **H** * ( ~**I** ))
This could be written as ( ~**NL** ) & ( **H** ^ **I** )
寫成程式碼 :
```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;
}
```
即可得到與題目一樣的程式碼
**原理 :**
當某個值(狀態) XOR 0 ，意思是值(狀態)維持不變
當某個值(狀態) XOR 1 ，則會改變值(狀態)
把 lower 看成是用來表示 "出現一次" 的狀態
把 higher 看成是用來表示 "出現兩次" 的狀態
該題目中會出現的狀態為 : b'00' -> b'01' -> b'10' -> b'00'
當 input 為 1
* 1. 有可能只會改變 lower 的狀態
* 2. 也有可能 lower 和 higher 兩者的狀態皆改變
既然無法確定現在的狀態 XOR 1 後是狀況 1. 還是狀況 2.
那就 lower 和 higher 皆做 XOR 1 ，再根據另一方的狀態做條件判斷
```cpp=
lower ^= nums[i]
if higher = 1 then lower = 0
else not changed
higher ^= num[i]
if lower = 1 then higher = 0
eles not changed
```
這樣的條件判斷能同時滿足 input 為 1 | 0
接下來再進一步用 bitwise operation 消除 branch
即可得到
```cpp=
lower ^= nums[i];
lower &= ~higher;
higher ^= nums[i];
higher &= ~lower;
```
:::warning
詳情請見 :
* [De Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws)
* [Canonical normal form](https://en.wikipedia.org/wiki/Canonical_normal_form)
:::
:::success
2. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;
:::
如開頭所寫的方法
counters 都計數完後再套用 mask 運算
:::success
3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼;
:::
用開頭的方法? 不過隨著次數增加，程式碼會拉長
如果要減少程式碼長度
重複次數為 k ，特別出現的為 p 次，各自用 unsigned 變數儲存
用 linked liist 建立 x1,x2,...,xm ?
* m 可由 $log_2{k}$ 獲得
* [Count Leading Zero](https://hackmd.io/@sysprog/c-numerics)
mask 用 bitwise shift operators 算出來 ?
* val = k & 0000...0001 可以得到 first bit
* if val == 0 then ~$x_i$ else $x_i$
* 然後 k >>= 1
重複做就能知道 $x_i$ 哪些要做 NOT 、哪些不用做 NOT
全部相互 & 之後再做 ~ 就能得到 mask 了
結果輸出 ?
用類似的方法得到 p' = p % k 的 binary form 中為 1 的 bit 位置 i，然後輸出對應的 $x_i$
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet