# 2020q3 Homework3 (quiz3) contributed by < `blueskyson` > ###### tags: `linux2020` ## 測驗 `1` 依據 [ISO/IEC 9899:TC2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) (即 C99) 標準的 6.5.7 章節 (第 84 到第 85 頁): >“The result of E1 >> E2 is E1 right-shifted E2 bit positions. … If E1 has a signed type and a negative value, the resulting value is ==implementation-defined==.” 在 C 語言中，對有號型態的物件進行算術右移 (arithmetic right shift，以下簡稱 ASR 或 asr) 歸屬於 [unspecified behavior](https://hackmd.io/@sysprog/c-undefined-behavior)，包含 [Cppcheck](http://cppcheck.sourceforge.net/) 在內的靜態分析器會嘗試找出 C 程式中這項 [unspecified behavior](https://hackmd.io/@sysprog/c-undefined-behavior)。考慮到程式碼的相容性，我們想實作一套可跨越平台的 ASR，假設在[二補數](https://hackmd.io/@sysprog/binary-representation)系統，無論標的環境的 shift 究竟輸出為何，我們的 ASR 總可做到: $-5\gg^{arith}1=-3$ 上述$-3$正是$\dfrac{-5}{2}$的輸出, 並向$-\infty$進位(rounding)。 針對有號整數的跨平台 ASR 實作如下: ```cpp= 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)); } ``` ### 解題 由題目敘述得知: 對有號數做算數右移屬於 implementation-defined 。所以第 3 行的 `logical` 應該是用來判斷在此機器上的右移運算是執行 [Logical Shift](https://en.wikipedia.org/wiki/Logical_shift)，或是執行 [Arithmetic Shift](https://en.wikipedia.org/wiki/Arithmetic_shift) ，所以 ==OP1== = `>>1` 。當 sign-bit 會被右移補 0 時， `logical` 等於 1 ；否則 `logical` 等於 0 。 接下來，在第四行是用來判斷 `m` 是否為負數，所以 ==OP2== = `m < 0`。 若 `logical == 1` 且 `m < 0` 則會讓 `fixu` 等於 -1 ，也就是 0xff...ff ，然後將此值賦予有號整數 `fix` ，使用 `(fix ^ (fix >> n))` 讓原本 logical shift 補 0 的位元改為 1 其餘位元則填上 0 ，最後跟 `(m >> n)` 做 `|` 運算達成 Arithmetic Right Shift。 ## 測驗 `2` 在 [C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics) 中，我們介紹過 power of 2 (漢字可寫作「二的冪」)。 [GCC extension](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 其中兩個是 ctz 和 clz: >Built-in Function: `int __builtin_ctz (unsigned int x)` >- Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined. >Built-in Function: `int __builtin_clz (unsigned int x)` >- Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. 我們可用 `__builtin_ctz` 來實作 [LeetCode 342. Power of Four](https://leetcode.com/problems/power-of-four/) ，假設 int 為 32 位元寬度。實作程式碼如下: ```cpp= bool isPowerOfFour(int num) { return num > 0 && (num & (num - 1))==0 && !(__builtin_ctz(num) OPQ); } ``` ### 解題 首先第一個判斷條件是 `num > 0` 不用多作解釋。 因為 2 的冪次有以下特性: - 2 = `00010`, (2 - 1) = `00001`, 2 & (2 - 1) = `0` - 4 = `00100`, (4 - 1) = `00011`, 4 & (4 - 1) = `0` - 8 = `01000`, (8 - 1) = `00111`, 8 & (8 - 1) = `0` - 16 = `10000`, (16 - 1) = `01111`, 16 & (16 - 1) = `0` 所以 `(num & (num - 1))==0` 可用來判定 2 的冪次 最後，我們需要從所有 2 的冪次中挑出 4 的冪次。觀察上面 2 的冪次的規律，可以發現只要是 4 的冪次，其 trailing 0-bits 的個數都為偶數，如: 4 的 trailing 0-bits 有 2 個、 16 的 trailing 0-bits 有 4 個。 如果 `num` 的 trailing 0-bits 為偶數，則 `!(__builtin_ctz(num) OPQ)` 回傳 `TRUE` ，很明顯的 ==OPQ== 為 `& 0x1` 。 ## 測驗 `3` [population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight) 。 Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `POPCNT` 指令，`POPCNT` 可處理 16-bit, 32-bit, 64-bit 整數。 對應到 C 程式的實作: ```cpp= unsigned popcnt_naive(unsigned v) { unsigned n = 0; while (v) v &= (v - 1), n = -(~n); return n; } ``` 函式 `popcnt_naive()` 利用不斷清除 LSB 直到輸入的數值 `v` 為 0。 `v &= (v - 1)` 的作用是將 LSB 設為 0 (reset LSB) 舉例來說，假設輸入數值為 20: ```c 0001 0100 # 20 ; LSB in bit position 2 0001 0011 # 20 - 1 0001 0000 # 20 & (20 - 1) ``` > 類似的操作還有 `x & -x`，將 `x` 的 LSB 取出 **(isolate LSB)** `n = -(~n)` 等同 `n++`，因為在二補數系統中 $-n =\ \sim n+1$ $-( \sim n) = n+1$ 因此 `popcnt_naive()` 的執行時間取決於輸入數值中 1 (set bit) 的個數。可改寫為以下常數時間複雜度的實作: ```cpp= unsigned popcnt_branchless(unsigned v) { unsigned n; n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; v = (v + (v >> 4)) & 0x0F0F0F0F; v *= 0x01010101; return v >> 24; } ``` 對於一個 32 bit 的無號整數，popcount 可以寫成以下數學式: $popcnt(x) = x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - ... - \left \lfloor{{\dfrac{x}{2^{{31}}}}}\right \rfloor$ 假設 $x = b_{31}...b_3b_2b_1b_0$ ，先看看 $x[3:0]$ 4 個位元，用以上公式可以計算得: $(2^3b_3 + 2^2b_2 + 2^1b_1 + 2^0b_0) - (2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$ >$\left \lfloor{{\dfrac{x}{2}}}\right \rfloor$ 相當於 C 表達式中 `x >> 1` 稍微改寫可得到: $(2^3 - 2^2 - 2^1 - 2^0)b_3 + (2^2 - 2^1 - 2^0)b_2 + (2^1 - 2^0)b_1 + 2^0b_0$ 因此 popcnt 的一般式可改寫為: $popcnt(x) = \sum\limits_{n=0}^{31} (2^n - \sum\limits_{i=0}^{n-1} 2^{i})b_n = \sum\limits_{n=0}^{31}b_n$ 因為 $2^n - \sum\limits_{i=0}^{n-1} 2^{i} = 1$ 只要對應的 $b_n$ 為 1，這個 bit 就會在 popcnt 的總和中加一，剛好對應 `popcnt_naive()` ，因此映證上述數學式確實可計算出 population count。 且一個 32 位元無號整數最多有 32 個 1 (set bit)，剛好可用一個 byte 表示，所以可分成幾個區塊平行計算，最後再全部加總到一個 byte 中，進行避免檢查 32 次。 `popcnt_branchless` 實作一開始以每 **4 個位元 (nibble) 為一個單位**計算 1 的個數，利用最初的公式計算 $x - \left \lfloor{{\dfrac{x}{2}}}\right \rfloor - \left \lfloor{{\dfrac{x}{4}}}\right \rfloor - \left \lfloor{{\dfrac{x}{8}}}\right \rfloor$ 關鍵的程式碼，逐行解釋: ```cpp= n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; ``` 1. `n = (v >> 1) & 0x77777777` : 將輸入數值 `v` 除以 2，得到 $\left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ ``` b_31 b_30 b_29 b_28 ... b7 b6 b5 b4 b3 b2 b1 b0 // v 0 b_31 b_30 b_29 ... 0 b7 b6 b4 0 b3 b2 b1 // (v >> 1) & 0x77777777 ``` 2. `v -= n` : 計算結果相當於 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ 3. `n = (n >> 1) & 0x77777777` : 再對 `n` 除以 `2` ，得到 $\left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 4. `v -= n` : 計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor$ 5. 和 6. 重複同樣動作 最後這段結束後計算出 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor - \left \lfloor{{\dfrac{v}{4}}}\right \rfloor - \left \lfloor{{\dfrac{v}{8}}}\right \rfloor$ ，得到每 4 個位元為一個單位中 set bit 的個數 **`v = (v + (v >> 4)) & 0x0F0F0F0F`** : 將每 4 個位元中 set bit 的個數加到 byte 中: 1. 假設 $B_n$ 代表第 n 個 nibble (4 位元) 中的數值 ``` B7 B6 B5 B4 B3 B2 B1 B0 // v 0 B7 B6 B5 B4 B3 B2 B1 // (v >> 4) ``` 2. 加總可得到: ``` // (v + (v >> 4)) B7 (B7+B6) (B6+B5) (B5+B4) (B4+B3) (B3+B2) (B2+B1) (B1+B0) ``` 3. 最後使用 0x0F0F0F0F 做 mask 可得 ``` // (v + (v >> 4)) & 0x0F0F0F0F 0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0) ``` **`v *= 0x01010101`** : 在最後一道敘述中，將 v 乘上 0x01010101。寫成直式如下: ``` 0 A6 0 A4 0 A2 0 A0 x 0 1 0 1 0 1 0 1 --------------------------------------------------- 0 A6 0 A4 0 A2 0 A0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 0 A6 0 A4 0 A2 0 A0 0 --------------------------------------------------- ↑_______________________A6+A4+A2+A0 ``` 我們可發現期望輸出就在原本 $A_6$ 的位置 ($2^7$)，因此將 `v` 右移 24 bits 即為所求，剩下的位數會 overflow ，右移後不影響結果。 - 假設 $A = B_7 + B_6$, $B = B_5 + B_4$, $C = B_3 + B_2$, $D = B_1 + B_0$, 根據分配律可得: ``` v * 0x01010101 = (A + B + C + D) (B + C + D) (C + D) (D) |<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->|<-- 1 byte -->| ``` **`return v >> 24`** : 最後得到的結果會放在 Most significant byte 中，因此向右位移 24 位元，即為所求的 popcount 值。 GCC 提供對應的內建函式: >`__builtin_popcount(x)`: 計算 x 的二進位表示中，總共有幾個 `1` 使用示範： ```c int x = 5328; // 00000000000000000001010011010000 printf("%d\n", __builtin_popcount(x)); // 5 ``` 針對 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/) ，我們可運用 gcc 內建函式實作，假設 int 寬度為 32 位元，程式碼列表如下: ```c int numberOfSteps (int num) { return num ? AAA + 31 - BBB : 0; } ``` 請補完程式碼。 ### 解題 根據 LeetCode 的題目敘述，當數字為奇數時，將該數字減 1 ； 當數字為偶數時，將該數除以 2 ，重複動作直到該數字變成 0。 當我把除以 2 這個動作帶換成向右平移 1 就變得很好理解了，以 `18` 這個數字為例: ```c 0001 0010 // LSB 為 0 ，所以是偶數，向右平移 0000 1001 // LSB 為 1 ，所以是奇數，將其減 1 0000 1000 // 向右平移 0000 0100 // 向右平移 0000 0010 // 向右平移 0000 0001 // 將其減 1 0000 0000 // 結束 ``` 觀察發現，從左邊 (MSB) 數過來，所有 leading zero 都不需要額外判斷向右位移，所以用 31 減去 leading zero 的數量， ==BBB== = `__builtin_clz(num)` 。 再來，只要位元的值為 1 ，就一定會被移到 LSB 並且被減去 1 ，只要該數有 n 位元為 1 ，就會執行 n 次減 1，所以要加上 `num` 中，位元值等於 1 的數量， ==AAA== = `__builtin_popcount(num)` 。 這題本身不難，難的是理解 `popcnt_branchless` 的位元操作。 ## 測驗 `4` 考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式: ```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; } ``` 請補完程式碼。 ### 解題 1. `if (!u || !v) return u | v;` 判斷 `u`, `v` 是否是 0 ，若其中一個是 0 就回傳 0。 2. ```c for (shift = 0; !((u | v) & 1); shift++) { u /= 2, v /= 2; } ``` 若 `u`, `v` 同時可被 2 整除，就將 `u`, `v` 同除以 2 ，並且讓 `shift` 加 1 ，由此可知 `u`, `v` 同為 `(0x1 << shift)` 的倍數，也就是將 $2^{shift}$ 作為公因數提出來。 3. ```c while (!(u & 1)) u /= 2; ``` 已經將 $2^{shift}$ 提出來了，代表接下來 gcd 的過程不會再萃取出偶數公因數，但是 `u` 或 `v` 可能還是偶數，繼續將 `u` 除以 2 直到 `u` 不是偶數。 4. ```c while (!(v & 1)) v /= 2; ``` 同理，在 gcd 的過程中將 `v` 除以 2 直到 `v` 不是偶數， ```c if (u < v) { v -= u; } ``` 進行輾轉相除，如果 `v` 大於 `u` ，就讓 `v` 減去 `u` ，然後繼續執行迴圈。這個持續相減過程就是除法，減到最後 `v` 小於 `u` 時， `v` 即為還沒開始相減前，`v ÷ u` 的餘數；`v` 等於`u` 時，`v` 即為所求公因數。由此可以推斷 `do while` 的條件 ==XXX== =`v` 。 ```c else { uint64_t t = u - v; u = v; v = t; } ``` 讓 `u` 等於新的 `v` ，讓 `v` = `u` - `v` ，這個過程可以這樣表示: `gcd(u, v) = gcd(u - (v mod u), (v mod u))` 當 `v mod u` 等於 0 時，得到 `u` 即為最大公因數，但是要記得乘上先前被消去的 $2^{shift}$ ，所以 ==YYY== = `u << shift` 。 ## 測驗 `5` 在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼: ```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; } ``` 可用 clz 改寫為效率更高且等價的程式碼: ```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; } ``` 請補完程式碼。 ### 解題 因為 `improved` 是根據 trailing zero 的數量來判斷最靠近 LSB 的 `1` 的 bit ，所以每次紀錄完最靠近 LSB 的 `1` 的 bit ，都必須將該 bit 的值變為 `0` 且其他 bit 保持不變。根據本次**測驗三**的提示: >類似的操作還有 `x & -x`，將 `x` 的 LSB 取出 (isolate LSB) 得知 ==KKK== = `bitset & -bitset` 即可達成此目標，其原理為: $Mask = A \ \& \ (\bar{A} + 1), \ A \oplus Mask = (A \ without \ the \ last \ 1)$ - 若 $A$ 的 LSB 為 1: ``` A = xxxx xxxx1 & ~A + 1 = yyyy yyyy1 -------------------------- Mask = 0000 00001 ^ A = xxxx xxxx1 -------------------------- Result = xxxx xxxx0 (A without last 1) ``` - 若 $A$ 的後 n 位為 0: ``` A = xxxx 1000 & ~A + 1 = yyyy 1000 -------------------------- Mask = 0000 1000 ^ A = xxxx 1000 -------------------------- Result = xxxx 0000 (A without last 1) ```
Last changed by  
 
Lin Cheng-Chieh
https://github.com/blueskyson https://blueskyson.github.io/ https://www.linkedin.com/in/blueskyson/ https://dev.to/blueskyson
252

Read more

2022q1 Homework3 (fibdrv)

contributed by < blueskyson >

3/17/2024
學習 Ansible

Ansible 是一個容易上手的 IT 自動化引擎，可自動執行雲端配置、應用程式部署和許多其他 IT 需求。存放 yml 描述檔並執行 ansible-playbook 的機器稱為 Control Node，遠端的所有參與佈署的機器稱為 Managed Node。Ansible 這個詞起源於科幻小說 Ender’s Game 中的一種超光速通訊裝置，用來控制遠方的星際戰艦。

9/14/2023
分析 .NET MVC 官方教學 MvcMovie

官方教學網址: https://docs.microsoft.com/en-us/aspnet/core/tutorials/first-mvc-app/start-mvc

7/17/2023
SoK 相關調查（由 ChatGPT 統整）

SoK 論文 SoK: Decentralized Finance (DeFi) Attacks 最後更新時間：Tue, 20 Sep 2022 20:19:53 UTC (2,188 KB) 2023/03/09 與 Ron 哥討論的統整： Sok 做了很多統整、做了弱點掃描，但是沒有做到讓開發者在開發時期就避開可能產生漏洞的設計模式，目前就 sok 可以我們有機會做的主題： 1、看別人的survey 思考怎麼做 design pattern 才能讓 contract 安全 2、這篇論文是 2021 的，可以延伸思維、把2021之後的攻擊統整。（可能要花較多體力，而且新的 contract 可能把大多漏洞都避掉了） 這周先用以下方法快速累積閱讀論文量： 先利用 chat gpt 快速 survey reference paper 的摘要跟結論、看別人注重的方向、看別人做到甚麼程度，再看未來展望。除非確定那篇很重要，不然數學證明等細節可以先不用看。拿future work 來做。

6/4/2023
Read more from Lin Cheng-Chieh
Published on HackMD