# 2020q3 Homework2 (quiz2) contributed by < `unknowntpo` > ## 測驗 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 & 0x8080808080808080) // MMM return false; i += 8; } while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } ``` >Answer: MMM = (d) 0x8080808080808080 :::success 自我問答 * payload 的作用是？ 把要比對的數值 (大小為 8 bytes) copy 到 payload 上，在對 payload 做位元操作 * :question: 可以直接對 `str[]` 做 check 而不用額外 copy 到 payload 上嗎？ * 沒辦法，以 `str[1]` 這個 object 為例，它的大小是 1 個 byte，而如果要做一次 8 個 byte 的比對的話就需要另一個大小為 8 bytes 的 object，這也是 payload 的作用 ::: * :question: 第一個 while 判斷式為 `while ((i + 8) <= size)`, * 假設 size == 8, 在 str[] 後的第一個 byte 藏有 non-ascii code 的話，這樣會不會出現明明 `str[]` 內都是 ascii, 但是判斷結果卻是 non-ascii 呢？ * 我的解答: * 事實上 str[size] 永遠都會是 null character , 所以並不會發生 copy 到不屬於 `str[]` 的東西 * 第一次與第二次的 while loop 對於 i 的邊界不一樣，或許能改成 * `while((i + 8) < size)` * `while (i < size)`? * 答案是不行 * 第一個 while 是確認是否有足夠的 8-byte chunck 來複製到 payload * 第二個 while 是確認一次檢查一個 byte 的時候不會超出邊界 * 在第二個 while 如果使用 i <= size 的話，就會檢查到 null character 了！ * 這不符合我們的預期 :::success TODO: 做實驗來驗證自己的假設 ::: ```cpp assume str[] = "a" size == 8 i + 8 i size idx 0 1 2 3 4 5 6 7 8 str 0 1 1 0 0 0 0 1 x | ____________| 'a' ``` is ### 完整 test code :::spoiler ```cpp=1 /* * isascii: Check if all the elements at an array is ascii character or not * Ref: * 2020q3 Homework2 (quiz2) Question 1: https://hackmd.io/@sysprog/2020-quiz2 * My note: https://hackmd.io/@unknowntpo/quiz2 */ /* Change to 1 if we want to test non ascii character */ #define TEST_NON_ASCII 1 /* (a) 0x0080008000800080 (b) 0x8000800080008000 (c) 0x0808080808080808 (d) 0x8080808080808080 <-- right answer (e) 0x8888888888888888 (f) 0xFFFFFFFFFFFFFFFF */ /* Define MMM */ #define MMM 0x8080808080808080 #include <stdio.h> #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; /* Check the character 8 bytes (1 word in 64-bit cpu) at a time */ while ((i + 8) <= size) { uint64_t payload; memcpy(&payload, str + i, 8); if (payload & MMM) // MMM return false; i += 8; } /* * Not enough words, * so check the character 1 byte at a time */ while (i < size) { if (str[i] & 0x80) return false; i++; } return true; } int main() { char c[] = "12345678"; /* Insert non ascii character */ #if TEST_NON_ASCII c[1] = 128; #endif printf("is %s ascii ? %s\n", c, is_ascii(c, strlen(c)) ? "true" : "false"); return 0; } ``` ::: ## 測驗 2 開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 `'0xF'` (大寫 `F` 字元) 和 `'0xf'` (小寫 `f` 字元) 都該轉換為 `15`。考慮以下不需要分支 (branchless) 的實作: ```cpp=1 uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` AAA = ? 首先觀察字元的==規律==(用==黃色螢光筆==標示) | char | ascii code | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | number to transfer: | |------|------------|----|----|----|----|----|----|----|----|---------------------| | `'0'` | 0x30 | 0 | 0 | 1 | 1 | ==0== | ==0== | ==0== | ==0== | ==0000== | | `'1'` | 0x31 | 0 | 0 | 0 | 0 | ==0== | ==0== | ==0== | ==1== | ==0001== | | `'2'` | 0x32 | 0 | 0 | 0 | 0 | ==0== | ==0== | ==1== | ==0== | ==0010== | | `'9'` | 0x39 | 0 | 0 | 1 | 1 | ==1== | ==0== | ==0== | ==1== | ==1001== | | `'A'` | 0x41 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1010 | | `'a'` | 0x61 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1010 | | `'F'` | 0x46 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1111 | | `'f'` | 0x66 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1111 | 可以發現: 要轉換的值其實就是那個 character 的 lower 4 bits e.g. `'0'` = 0x30 = [001100000]~2~ 我們要擷取的就是後 4 bits `0000` :::success 設計 ascii table 的人真的太有智慧了，處處是玄機呢！ ::: 由解答回推運算流程 MASK = `(c) 0x40` [0100 0000]~2~ AAA = `(a) 3` [0000 0011]~2~ BBB = `BBB = (a) 6` [0000 0110]~2~ ```cpp=1 uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` assume `in` 為 `'f'`[0110 0110]~2~ * line 3: * 經由上面的表格，我們可以觀察到，只有當某個數字是英文字母而不是數字時，`b6` 才是 1 * 所以可以透過這個特性檢查我們的 `in` 是否為英文字母 * 如果 `in` 是英文字母，`letter == 0x40` * 如果 `in` 是數字，`letter == 0x0` ```shell letter := 'f' & 0x40 = [0100 0001] & [0100 0000] = [0100 0000] ``` * line 4,5: ```shell shift := (letter >> 3) | (letter >> 6) = [0000 1000] | [0000 0001] = [0000 1001] ``` * 發現 shift 的作用是如果 in 是 letter 的話，就讓 in + 9 * 因為 a 在 16 進位理面代表 10, | char | ascii code | b3 | b2 | b1 | b0 | lower 4 bits 代表的數值 | |------|------------|----|----|----|----|-------------------------| | 'a' | 0x41 | 0 | 0 | 0 | 1 | 1 | | 'b' | 0x42 | 0 | 0 | 1 | 0 | 2 | | 'c' | 0x43 | 0 | 0 | 1 | 1 | 3 | | 'd' | 0x44 | 0 | 1 | 0 | 0 | 4 | | 'e' | 0x45 | 0 | 1 | 0 | 1 | 5 | | 'f' | 0x46 | 0 | 1 | 1 | 0 | 6 | 可以發現只要把每個 letter 的數值 + 9，再 Mask 掉不必要的 higher 4 bits, 就會等於最終我們要轉換的數字了！ * `+9` 這個動作 就對應到 `(letter >> 3) | (letter >> 6)` * 因為如果 in 是英文字母的話， letter == 0x40 * 0x40 >> 3 == 0x08 * 0x40 >> 6 == 0x01 * 兩者做完 `|` 運算剛好是 `9` ! * line 5: ```shell return value := (in + shift) & 0xf = ([0110 0110] + [0000 1001]) & [0000 1111] = [0110 1111] & [0000 1111] = [0000 1111] = 15 ``` :::success * 其實 shift 這個變數改成 offset 更為恰當！ * 因為他就是把字母從 lower bits == 1 (a), 2 (b) 3, (c)，給他們一個 offset, 讓他們對應到 10 (a), 11 (b), 12 (c) ,13 (d) ... ::: ------ :::success TODO: 修飾說明語句 >[name=Chang Chen Chien][time=Fri, Sep 25, 2020 8:10 AM] ::: :::success 延伸問題: 1. 解釋上述程式的運作原理; 2. 將 hexchar2val 擴充為允許 `"0xFF"`, `"0xCAFEBABE"`, `"0x8BADF00D"` 等字串輸入，且輸出對應的十進位數值 >[Hexspeak](https://en.wikipedia.org/wiki/Hexspeak) ::: ## 測驗 3 除法運算的成本往往高於加法和乘法，於是改進的策略被引入。其中一種策略是將除法改為乘法運算，例如 $\frac{n}{d}$ 在分子和分母分別乘上 $2^N$ 後，得到等價的 $n\times\frac{\frac{2^N}{d}}{2^N}$，其中對 2 的 N 次方 (power of 2) 進行除法，在無號整數的操作就等同於右移 (shift) N 個位元，又當 $d$ (除數) 的數值是已知的狀況下，$\frac{2^N}{d}$可預先計算，也就是說，$\frac{n}{d}$ 可轉換為乘法和位移操作，進而減少運算成本。不過，顯然 $\frac{2^N}{d}$ 無法總是用整數來表達 (僅在 $d$ 是 power of 2 的時候才可)，因此，我們可先估算，並將差值補償回去。 重新檢視 $\frac{n}{d}=n\times\frac{\frac{2^N}{d}}{2^N}$，當我們想將 $n$ 除以 $4$ 時，就相當於乘以 $0.25$，所以我們可將 $\frac{5}{4}$ 改為 $5 \times 0.25$，我們得到整數的部分 (即$1$)，和小數部分 (即$0.25$)，後者乘以 $4$ 就是 $1$，也就是餘數。下方程式碼展示這概念: ```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; } ``` 其中 __uint128_t 是 GCC extension，用以表示 128 位元的無號數值。 >[GCC: C Extensions: 128-bit Integers](https://gcc.gnu.org/onlinedocs/gcc/_005f_005fint128.html) 預期 `quickmod(5)` 會得到 `2`, `quickmod(55)` 得到 `1`, `quickmod(555)` 得到 `0` (`555` 是 `3` 的倍數)。 請補完程式碼。 作答區 XXX = ? * `(a)` `0x00F000F000F00080` * `(b)` `0xF000F000F000F000` * `(c)` `0x0F0F0F0F0F0F0F0F` * `(d)` `0xF0F0F0F0F0F0F0F0` * `(e)` `0x8888888888888888` :::success 完全看不懂 ... 先從 整數除法開始下手！ [LeetCode 29: Divide Two Integers 解析](/ubTTbJcnRrq8r0ybHqfOZQ) ::: ### 數學推導 >摘自 < [WeiCheng14159](https://hackmd.io/5EJdbAmHTFWHfdqbqx2lwQ?view)> 同學的數學推導 \begin{align} n \% 3 &= n - \left \lfloor {\frac{n}{3}} \right\rfloor \times 3 \\ &= n - \left \lfloor n \times \frac{ \frac{2^{64}}{3} }{2^{64}} \right\rfloor \times 3\\ &= n - \left \lfloor \left( n \times \frac{2^{64}}{3} \right) \times \frac{1}{2^{64}} \right \rfloor \times 3\\ &= n - ((n \times M) >> 64) \times 3 \\ \end{align} :::success > ## Macro M 的解析 > `#define M ((uint64_t)(UINT64_C(XXX) / (D) + 1))` * 第二行同乘 $2^{64}$ 答案是否與之前一樣呢？ * $\frac{2^{64}}{D}$ 何時為整數？ * 如何用 integer 計算 $\frac{n}{d}$ * 如何確保精確度，不論 $\frac{2^{64}}{D}$ 是否為整數 * `UINT64_C` 是什麼？ * integer lieral * ref: [gnu.org](https://www.gnu.org/software/libcdio/doxygen/types_8h.html#a26a7bac63d90ef61175acb9f6fc4f2ca) * UINT64_C 功用是在輸入的東西後面利用 `##` 接上 `ULL` * `ULL` 作用是？ * specify 這個 literal 的 data type `unsigned long long` * 確保運算結果不會 overflow * [stackoverflow 解答](https://stackoverflow.com/questions/13134956/what-is-the-reason-for-explicitly-declaring-l-or-ul-for-long-values) * [示範](https://difyel.com/c/literal/integer-literals-in-c/) ::: :::success TODO: run `fastdiv` to profile the behavior of macro `M` 回答 如何確保精確度，不論 $\frac{2^{64}}{D}$ 是否為整數 ::: :::info 不懂: 整數除法上下乘以 $2^{64}$ 後結果是否一樣 ::: ### jemalloc 的 `div.c` 假設我們有 $n = q \times d$, 其中 $n$, $q$, $d$ 都是正整數，$n$ 和 $d$ 已知 我們的目標是不使用除法運算來求出 q = n / d 對於任何 k, 我們可以得到 q = $$ \left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor $$ 我們要找出他在何種條件下等於 $\frac{n}{d}$ 上式又可寫成 $$ \left\lfloor\frac{2^k+r}{d} \times \frac{n}{2^{k}} \right\rfloor $$ 其中 * :question: How do we get r? $\left\lceil\frac{2^k}{d}\right\rceil$ 如何變成$\frac{2^k+r}{d}$ ? $$ \quad r = (-2^{k})\mod d $$ 代入 r, 展開式子可得 $$ =\left\lfloor \frac{2^k}{d} \times \frac{n}{2^{k}} + \frac{r}{d} \times \frac{n}{2^k} \right\rfloor $$ $$ =\left\lfloor \frac{n}{d} + \frac{r}{d} \times \frac{n}{2^k} \right\rfloor $$ 因為前提是 $\frac{n}{d}$ 為整數，所以上式也可以寫成 $$ \frac{n}{d} + \left\lfloor \frac{r}{d} \times \frac{n}{2^k} \right\rfloor $$ 如果可以滿足 $$ \frac{r}{d} \times \frac{n}{2^k} < 1 $$ 則 $\frac{n}{d}$ (除法運算) 就可以簡化成 $\left\lfloor{\left\lceil\frac{2^k}{d}\right\rceil \times \frac{n}{2^k}} \right\rfloor$ (乘法與 bitwise shift) 因為 r < d 且 r / d < 1 總是滿足，為使 $\frac{n}{2^k}$ ，對於不會超出 $2^{32}$ 的 n，可以令 k = 32 來滿足此條件 * :question: How do we get r? * 參考解釋 * [nelsonlai1 同學](https://hackmd.io/@nelsonlai1/2020q3_quiz2#%E6%B8%AC%E9%A9%97-3) * [eechang 同學合理推導](https://hackmd.io/@eecheng/HJgpR7RNw#%E6%B8%AC%E9%A9%97-3) * [oOcarShiang 同學對 quickmod 解釋較為清楚](https://hackmd.io/@oscarshiang/sysprog_quiz2#%E6%B8%AC%E9%A9%97%E4%B8%89) * [justapig9020 同學對於誤差補償的說明](https://hackmd.io/@justapig9020/SJGJAARVw#%E6%B8%AC%E9%A9%97-3) * [ChongMingWei 同學對於各項說明與實驗都很完整！！明天先參考他的](https://hackmd.io/@cmwchw/2020q3-quiz2#2020q3-Homework2-quiz2) * [WeiCheng14159 同學對 n % 3 的數學推導很棒 還有 jemalloc 講得很完整](https://hackmd.io/@WeiCheng14159/HkesfMvBP#Test3) :::success TODO: 解釋 magic number ::: <br><br><br><br><br><br> <br><br><br><br><br><br> <br><br><br><br><br><br> <br><br><br><br><br><br> ## 測驗 4 ## 測驗 5 ## 測驗 6 # Reference [2020q3 第 2 週測驗題](/@sysprog/2020-quiz2) [作業區](https://hackmd.io/@sysprog/2020-homework2) [`RinHizakura` 同學共筆](https://hackmd.io/@RinHizakura/SJ5NuIANP)