# 2020q3 Homework3 (quiz3)
contributed by < `joey3639570` >
###### tags: `進階電腦系統理論與實作`
## 測驗 `1`
針對有號整數的跨平台 ASR 實作如下:
```c
int asr_i(signed int m, unsigned int n)
{
const int logical = (((int) -1) OP1) > 0;
unsigned int fixu = -(logical & (OP2));
int fix = *(int *) &fixu;
return (m >> n) | (fix ^ (fix >> n));
}
```
#### 參考解答
- `OP1` : `>> 1`
- `OP2` : `m < 0`
### 延伸問題:
>1. 解釋上述程式運作原理，應提供數學證明和 Graphviz 製作的圖解;
先了解何謂題目提到的 **Implementation-defined behavior**
依據 [ISO/IEC 9899:TC2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) (即 C99) 標準的 3.4.1 章節 (第 3 頁):
> **unspecified behavior** where each implementation documents how the choice is made
因此，我們必須參考 [GCC documentation](https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html#Integers-implementation) 中 4.5 章節 (第 5 點) :
> The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5).
>
>Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. **Signed ‘>>’ acts on negative numbers by sign extension.**
那接下來則了解何謂 [Sign Extension](https://en.wikipedia.org/wiki/Sign_extension)
>If ten bits are used to represent the value "`11 1111 0001`" (decimal negative 15) using two's complement, and this is sign extended to 16 bits, the new representation is "`1111 1111 1111 0001`". Thus, by padding the left side with ones, the negative sign and the value of the original number are maintained.
再以 [位元左移運算 (<<), 位元右移運算 (>>)](http://www.86duino.com/?p=1413&lang=TW) 中舉的例子理解:
```cpp
int x = -16; // binary: 11111111111111111111111111110000
int y = x >> 3; // binary: 11111111111111111111111111111110
```
```cpp
int x = -16; // binary: 11111111111111111111111111110000
int y = (unsigned int)x >> 3; // binary: 00011111111111111111111111111110
```
`int -1` 透過 `%x` print 出來的是 `0xffffffff`，也就是 :
- 沒有 Sign Extension下，則應該會導致 right shift 後的到 most significant bit (MSB) 為`0` 的狀況，這會導致此數字被判斷為正值，因此 `logical` 為 1
- Sign Extension 下， right shift 後依然得到 `-1` (`0xffffffff`)，實測下 `>>` right shift 1 後，確實得到 `0xffffffff` ，因此 `logical` 為 0
由此可得知 `logical` 使用於判定是否使用 Sign Extension
再來看到 `unsigned int fixu = -(logical & (m < 0))` :
- 需要先注意的是，這裡將有號數指派給 unsigned int ，這樣會將原本用來當正負號判斷的 MSB 也納入數值使用。
- 當沒有 Sign Extension ， 也就是 `logical` 為 1 的狀況下，且 m 為負的狀況， 為 unsigned int 的 `fixu` 是 `0xffffffff` ， m 若為正， `logical` 為 0
- 在 `logical` 為 0 的狀況下， `fixu` 不管怎樣都是 0
- `fix` : 其實是跟 `fixu` 一樣的值
在 `RinHizakura` 的作業中參考到 `jserv` 老師說 :
>```cpp
>unsigned int fixu = -(logical & (OP2));
>int fix = *(int *) &fixu;
>```
>這段可避免編譯器進行過度 (aggressive) 最佳化
回歸參考[你所不知道的 C 語言：編譯器和最佳化原理篇](https://hackmd.io/@sysprog/c-compiler-optimization)
`int fix = *(int *) &fixu;` 其實便是 **Pointer aliasing** ，有了這個會讓最佳化無用武之地!
:::warning
這邊仍有問題未解決，編譯器若進行最佳化，此段 Code 會長怎樣呢?
> 請用 `gcc -S -O0` 和 `gcc -S -Os` 來觀察
> :notes: jserv
:::
透過老師說的用 `-S` 輸出組譯碼來看:
- `gcc -S -O0`
```assmbly
asr_i:
.LFB5:
.cfi_startproc
pushq %rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
movq %rsp, %rbp
.cfi_def_cfa_register 6
movl %edi, -20(%rbp)
movl %esi, -24(%rbp)
movl $0, -8(%rbp)
movl -20(%rbp), %eax
shrl $31, %eax
movzbl %al, %eax
andl -8(%rbp), %eax
negl %eax
movl %eax, -4(%rbp)
movl -24(%rbp), %eax
movl -20(%rbp), %edx
movl %eax, %ecx
sarl %cl, %edx
movl %edx, %eax
movl %eax, %esi
movl -24(%rbp), %eax
movl -4(%rbp), %edx
movl %eax, %ecx
shrl %cl, %edx
movl %edx, %eax
xorl -4(%rbp), %eax
orl %esi, %eax
popq %rbp
.cfi_def_cfa 7, 8
ret
```
- `gcc -S -Os
> -Os : Optimize for size. -Os enables all -O2 optimizations except those that often increase code size
> 不使用以下:
>```
>-falign-functions -falign-jumps
>-falign-labels -falign-loops
>-fprefetch-loop-arrays -freorder-blocks-algorithm=stc
>```
```
asr_i:
.LFB41:
.cfi_startproc
movl %edi, %eax
movl %esi, %ecx
sarl %cl, %eax
ret
.cfi_endproc
```
:::warning
補充 assembly 相關知識 :
- [StackOverflow : How could this assembly be possible?](https://stackoverflow.com/questions/40451274/how-could-this-assembly-be-possible/40451442)
回答中提到 `sarl %cl, %eax` 的作用
> SAR opcode only supports the %cl register as an input for a variable arithmetic shift (by %cl times).
- [x86 Assembly Guide](https://www.cs.virginia.edu/~evans/cs216/guides/x86.html)
x86 Assembly 指南， eax ebx ecx edx esi edi ebp esp 的功能參考於此
- [Compiler Explorer](https://godbolt.org)
提供即時 c 轉譯成 assembly code ，供觀察變化
:::
接下來看到 `(m >> n) | (fix ^ (fix >> n));`
先分為 `logical` 為 0 和 1 的狀況來看:
- `logical` 為 0
這種狀況下， `fix` 為 0 ，不管怎樣 `fix ^ (fix >> n)` 都會是 0 ，因此這邊不會對 `m >> n` 造成影響
- `logical` 為 1
在此還要考慮 m 的正負，若為正值則 `(fix ^ (fix >> n))` 跟 `logical` 為 0 的狀況是一樣的，不會對 `m >> n` 造成影響。而 m 若為負，我們分為 `m >> n` 及 `(fix ^ (fix >> n))` ，並且以 `-5 (0xFFFFFFFB) >> 1` 為例來看:
- `m >> n` : 在沒有 Sign Extension 的狀況下，經這步會變成 `0x7FFFFFFFD`
- `(fix ^ (fix >> n))` : 在沒有 Sign Extension 的狀況下，這裡會變成 `0xFFFFFFFF ^ 0x7FFFFFFF ` ，也就是 `0x80000000` ，只有 MSB 為 1
- 再經過 `|` 後， 這樣可以透過右邊的部分形成 Sign Extension，以例子而言，結果便成了 `0xFFFFFFFFD` ，也就是 `-3`
- 數學證明
待辦...
- Graphviz 製作的圖解
以 8 位元為例，沒有 Sign Extension<br>`m` 為 `-2` ， `n` 為 `1` :
`(int) -1 >> 1`
```graphviz
graph {
node [shape=none];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
t [label=">> 1" ]
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
由上圖可發現 Sign bit 被 right shift 掉，變成正的，因此 `logical` 為 1。
當此時 `m < 0` 也成立時:
`1 (logical) & 1 (m < 0 成立)`
`fixu = -1` ，但要注意 unsigned
`m >> n`
```graphviz
graph {
node [shape=none];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
t [label=">> 1 =" ]
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>0</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
`fix >> n`
```graphviz
graph {
node [shape=none];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
t [label=">> 1 =" ]
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
`fix ^ (fix >> n)`
```graphviz
graph {
node [shape=none];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
t [label="^" ]
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
```graphviz
graph {
node [shape=none];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
`(m >> n) | (fix ^ (fix >> n))`
```graphviz
graph {
node [shape=none];
a [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>0</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>0</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
t [label="|" ]
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
<TD>0</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
```graphviz
graph {
node [shape=none];
b [label=<
<TABLE BORDER="0" CELLBORDER="1" cellspacing="0">
<TR>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>1</TD>
<TD>0</TD>
<TD>1</TD>
</TR>
<TR><TD>Sign</TD></TR>
</TABLE>>]
}
```
由上圖可以得到最後結果 `-3 (11111101)`
>2.練習實作其他資料寬度的 ASR，可參照 [C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor) 撰寫通用的巨集以強化程式碼的共用程度;
## 測驗 `2`
```c
bool isPowerOfFour(int num)
{
return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);
}
```
### 延伸問題:
>解釋上述程式運作原理;
- 先藉 `num > 0` 檢測 `num` 是否為正值，若為負值可直接判斷為 `false`
- `(num & (num - 1))==0` 之前有學過，用於判斷是否為偶數，不是偶數保證不是 4 的 power ，故 return `false`
- `__builtin_ctz(num)` 用於找出右邊第一個 1 的右邊有幾個0，觀察 4 的power (4, 16, 64, 256)，32 位元下經此 function 所得到的值 :
- 4 (100) : 2 個 0
- 16 (10000) : 4 個 0
- 64 (1000000) : 6 個 0
- 256 (100000000) : 8 個 0
觀察此規律，出來的值要是**偶數**，故使用 `& 0x1` 可以判斷最後一個位元是否為 1 ，若 `& 0x1` 得到 0 ，加上 `!` 後便讓條件成立。
>改寫上述程式碼，提供等價功能的不同實作，儘量降低 branch 的數量;
- 判斷是否為正數: 利用 `& 0x80000000`
- 判斷是否為偶數: 利用 `(num & (num - 1))`
```cpp
bool isPowerofFour(int num)
{
return !((num & 0x80000000) | (num & (num - 1)) | (__builtin_ctz(num) & 0x1));
}
```
透過 Assembly 檢查看看有沒有 Branch ，如下:
```
isPowerof_Four:
pushq %rbp
movq %rsp, %rbp
movl %edi, -4(%rbp)
movl -4(%rbp), %eax
andl $-2147483648, %eax
movl %eax, %edx
movl -4(%rbp), %eax
subl $1, %eax
andl -4(%rbp), %eax
orl %eax, %edx
movl -4(%rbp), %eax
rep bsfl %eax, %eax
andl $1, %eax
orl %edx, %eax
testl %eax, %eax
sete %al
popq %rbp
ret
```
:::warning
:boom:此段 Code 的缺點是一定要全部的動作都跑一遍才會 return ，而不會因前面的正值或奇數判斷就先提前 return 0 。
:::
2. 練習 LeetCode [1009. Complement of Base 10 Integer](https://leetcode.com/problems/complement-of-base-10-integer/) 和 [41. First Missing Positive](https://leetcode.com/problems/first-missing-positive/)，應善用 clz;
3. 研讀 [2017 年修課學生報告](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/Bk-uxCYxz)，理解 `clz` 的實作方式，並舉出 [Exponential Golomb coding](https://en.wikipedia.org/wiki/Exponential-Golomb_coding) 的案例說明，需要有對應的 C 原始程式碼和測試報告;
> x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器，實作中也用到 clz/ctz 指令，可參見 Selecting the Golomb Parameter in Rice Coding。
---
## 測驗 `3`
```c
int numberOfSteps (int num)
{
return num ? AAA + 31 - BBB : 0;
}
```
### 延伸問題:
>解釋上述程式運作原理;
- `num` 為 0 的狀況下，直接 return 0
- `num` 不為 0 ，至少就會有一次 ( 0x1 )，故從 31 為基準點開始判斷
- `BBB` : 為 `__builtin_clz(num)` ，藉此可以判斷需要處理的位元數量，以 `0x00000008` 為例，前面的 28 個 0 便可不用考慮要處理，而會有 $31 - 28 = 3 $ 個 `/2` 的次數。
- `AAA` : 為 `__builtin_popcount(num)` ，在此代表著**有幾個 1 需要被減掉**，每次 `/2` ( Right Shift >> )會有 1 在 LSB 的狀況，要透過減 1 才會繼續進行 `/2`，換句話說，有幾個 1 ，就會有幾個減 1 的動作。
以 `num = 0x00000008` 為例:
- `__builtin_clz(num)` = 28 ，`__builtin_popcount(num)` = 1<br>$1 +31 - 28 = 4$
- 實際用算的步數如下:<br>$8 \div 2 = 4$<br>$4 \div 2 = 2$<br>$2 \div 2 = 1$<br>$1 - 1 = 0$<br>共 4 次
>改寫上述程式碼，提供等價功能的不同實作並解說;
>>提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用，如 bit inverse、abs 等等，是極好的參考材料。
>避免用到編譯器的擴充功能，只用 C99 特徵及 bitwise 運算改寫 LeetCode [1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，實作出 branchless 解法，儘量縮減程式碼行數和分支數量;
## 測驗 `4`
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
while (v) {
uint64_t t = v;
v = u % v;
u = t;
}
return u;
}
```
```c
#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
if (!u || !v) return u | v;
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
while (!(u & 1))
u /= 2;
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (XXX);
return YYY;
}
```
### 延伸問題:
>解釋上述程式運作原理;
- `if (!u || !v) return u | v;`:
此段用於判斷為 0 的 Case ，若其中一者為 0 則 return 非 0 者，都 0 就 return 0。
- 觀察此 for 迴圈:
```c
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
在此從 `!((u | v) & 1)` 發現，這是要濾出 u 和 v 的最低位元皆是 0 的狀況，這種狀況同時也代表 **u 和 v 都是偶數** ，每當此狀況發生，便把 u 和 v 各提出 2 (也可想為 >> 1)，只要當 u 或 v 其中一者變成奇數，迴圈就會結束。
- 下面這段 Code :
```c
while (!(u & 1))
u /= 2;
```
判斷如果 u 是偶數，就把他所有的質因數 2 去掉，原因如下:
- 若 u 是偶數，則 v 一定是奇數，（承襲前面的迴圈）
- 若一個是偶數一個是奇數，則 2 一定不會是公因數，把 2 除掉也不會影響最大公因數
:::warning
參考 `sammer1107` ，此段 Code 用到兩個性質:
- 若 u 為偶數，v為奇數，則 $gcd(u,v) = gcd(\frac{u}{2},v)$
- 當 $u > v$ ， $gcd(u,v) = gcd(u-v,v)$
:::
- 繼續看到下面這段 Code:
```cpp=
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (XXX);
```
每次迴圈開頭都會先對 v 進行**性質1**的處理，接著利用**性質2**將大的減去小的，特別需要注意的是 `sammer1107` 提到的:
> u,v 都是奇數，故大減小之後的結果會出現**偶數**，在此固定把偶數放在 v ，會把奇數放在 u ，下次進入迴圈時，又會利用到性質1了。
利用上面的敘述推斷， `XXX` 這個迴圈的終止條件是相減的結果為 0 的時候，也就是 $v = 0$ ， $gcd(u,v) = gcd(u,0) = u$，在此 `XXX` 應為 `v`，自然在最後是用 u 為 return 值，別忘了要補上最一開始紀錄起來的 shift ，故 `YYY` 為 `u << shift`
:::warning
參考 `sammer1107`:
必須要注意 `XXX` 不能用 `u - v` ，雖然當 $u - v = 0$ ，$gcd(u,v) = gcd(u, u) = u$ ，會得到正確結果，但要是 $v = 2u$ ，迴圈不會結束，但下次迴圈 v 會被除為 u ，所以迴圈結束時 `v=0` ， u 不變，但會發現 `u - v != 0` ，因此陷入無窮迴圈。
:::
>在 x86_64 上透過 `__builtin_ctz` 改寫 GCD，分析對效能的提升;
## 測驗 `5`
```c
#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
for (size_t k = 0; k < bitmapsize; ++k) {
uint64_t bitset = bitmap[k];
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
}
return pos;
}
```
```c
#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
size_t pos = 0;
uint64_t bitset;
for (size_t k = 0; k < bitmapsize; ++k) {
bitset = bitmap[k];
while (bitset != 0) {
uint64_t t = KKK;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
}
return pos;
}
```
### 延伸問題:
>解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
利用本題練習利用觀察推論，以利之後測驗的反應:
- 對照兩段 Code 不同的部分:
```c
size_t p = k * 64;
for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}
```
```c
while (bitset != 0) {
uint64_t t = KKK;
int r = __builtin_ctzll(bitset);
out[pos++] = k * 64 + r;
bitset ^= t;
}
```
- 第一段 for 迴圈掃視所有位元，檢測 `(bitset >> i) & 0x1` 這個條件，若成立便進行 `out[pos++] = k * 64 + r;`
- 比對上面的流程，並且了解 `__builtin_ctzll` 用於算出 trailing 0-bits ，藉此便可以快速找出下一個 1 的位置，而不是像 for 迴圈版本一一比對
- 一開始寫題目透過刪去法推論 `KKK` 為 `bitset & -bitset` ，其他選項只對最後一個位元做處理
- 試著透過例子理解流程，例子如下:
若 bitset 為 136
Binary : `00000000 00000000 00000000 00000000 00000000 00000000 00000000 10001000`<br>
`-bitset` = 18446744073709551480
Binary : `11111111 11111111 11111111 11111111 11111111 11111111 11111111 01111000`
`bitset & -bitset` (t) 得到 `1000`<br>
`bitset ^= t` ， `bitset` 變為:
`00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000`<br>
可以發現這樣的流程下，**去除掉了最低位元的 1** ，在下一次的迴圈透過 `__builtin_ctzll` 得到下一次位元的 1
>設計實驗，檢驗 clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
>思考進一步的改進空間;
:::danger
避免說「最快」，只有你徹底理解一件事物，才能事後評價「快」或「慢」
:notes: jserv
:::
用舉例來看<s>最快</s>
最後要結果會是2個0或是3個0
Sign in with Wallet
Connect another wallet