2020q3 Homework3 (quiz3)

# 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-deﬁned behavior** 依據 [ISO/IEC 9899:TC2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) (即 C99) 標準的 3.4.1 章節 (第 3 頁): > **unspeciﬁed 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

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.