2020q3 第 2 週測驗題

# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 2 週測驗題 ###### tags: `sysprog2020` :::info 目的: 檢驗學員對 **[數值系統](https://hackmd.io/@sysprog/c-numerics)** 及 [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise) 的認知 ::: ==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSfbEUV0RVt9cC3dwILBdjbOEfJvkUDe8EIfii3p8dztbWa8aA/viewform)== ### 測驗 `1` 目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元: ```cpp #include <stddef.h> bool is_ascii(const char str[], size_t size) { if (size == 0) return false; for (int i = 0; i < size; i++) if (str[i] & 0x80) /* i.e. (unsigned) str[i] >= 128 */ return false; return true; } ``` 其中 `str` 是開頭的記憶體地址，`size` 則是要檢驗的範圍。逐一字元比對的效率低，在 64 位元的架構下，我們嘗試一次比對 64 位元的資料 (即 word size)，程式碼改寫如下: ```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 = ? * `(a)` `0x0080008000800080` * `(b)` `0x8000800080008000` * `(c)` `0x0808080808080808` * `(d)` `0x8080808080808080` * `(e)` `0x8888888888888888` * `(f)` `0xFFFFFFFFFFFFFFFF` :::success 延伸問題: 1. 解釋上述程式的運作原理，特別是為何用到 `memcpy` 呢？提示: 與 data alignment 有關，詳閱 [ C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory) 2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」 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) ::: --- ### 測驗 `2` 開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 `'0xF'` (大寫 `F` 字元) 和 `'0xf'` (小寫 `f` 字元) 都該轉換為 `15`。考慮以下不需要分支 (branchless) 的實作: ```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; } ``` 已知 `in` 一定隸屬於 `'0'`, `'1'`, `'2'`, ..., `'9'` 及 `'a'`, `'b'`, `'c'`, ..., `'f'` (小寫) 及 `'A'`, `'B'`, `'C'`, .., `'F'` (大寫) 這些字元。預期 `hexchar2val('F')` 和 `hexchar2val('f'`) 回傳 `15`，且 `hexchar2val('0')` 回傳 `0`，其他輸入都有對應的數值。以下摘自 ASCII 表格 * `'0'`, `'1'`, `'2'`, ..., `'9'` 對應到 `0x30`, `0x31`, `0x32`, .. `0x39` * `'a'`, `'b'`, `'c'`, ..., `'f'` (小寫) 對應到 `0x61`, `0x62`, `0x63`, ..., `0x66` * `'A'`, `'B'`, `'C'`, .., `'F'` 對應到 `0x41`, `0x42`, `0x43`, ..., `0x46` 請補完程式碼。 ==作答區== MASK = ? * `(a)` `0x10` * `(b)` `0x20` * `(c)` `0x40` * `(d)` `0x60` * `(e)` `0x80` AAA = ? * `(a)` 3 * `(b)` 2 * `(c)` 1 * `(d)` 0 BBB = ? * `(a)` 7 * `(b)` 6 * `(c)` 5 * `(d)` 4 :::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` * `(f)` `0xFFFFFFFFFFFFFFFF` :::success 延伸問題: 1. 解釋上述程式的原理; 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) 也運用類似的技巧，請閱讀原始程式碼，並抽離快速除法實作為獨立的程式碼，說明運作原理，也該撰寫測試程式，比較透過處理器的整數除法指令及本技巧的效能差距; ::: --- ### 測驗 `4` 延伸測驗 `3`，我們想判斷某個數值能否被指定的除數所整除，在 `D` 和 `M` 都沿用的狀況下，程式碼如下: ```cpp bool divisible(uint32_t n) { return n * M <= YYY; } ``` 以 `D = 3` 來說，`divisible(7)` 要得到 `0` (即 7 無法被 3 整除)，`divisible(87)` 要得到 `1` (即白痴是三的倍數) 請補完程式碼。 ==作答區== YYY = ? * `(a)` `M + 1` * `(b)` `M` * `(c)` `M - 1` * `(d)` `(M >> 1)` * `(e)` `(M << 1)` --- ### 測驗 `5` 考慮 `strlower` 函式的作用是將指定的字串 (或部分字串) 的英文字母全改為小寫，其 [in-place](https://en.wikipedia.org/wiki/In-place_algorithm) 的實作如下: ```cpp= #include <ctype.h> #include <stddef.h> /* in-place implementation for converting all characters into lowercase. */ void strlower(char *s, size_t n) { for (size_t j = 0; j < n; j++) { if (s[j] >= 'A' && s[j] <= 'Z') s[j] ^= 1 << 5; else if ((unsigned) s[j] >= '\x7f') /* extended ASCII */ s[j] = tolower(s[j]); } } ``` 針對 extended ASCII，我們呼叫 C 語言標準函式庫的 [tolower](https://man7.org/linux/man-pages/man3/tolower.3.html)，需要留意到在不同的語系 (locale)，字母順序和大小寫的定義可能異於我們認知的英文字母。以下摘自手冊: > If c is a lowercase letter, toupper() returns its uppercase equivalent, if an uppercase representation exists in the current locale. Otherwise, it returns c. 語系對程式碼的影響不能輕忽，舉例來說，若語系設定為捷克語，以 "Ch" (屬於 digraph，二合拉丁字母，常見於西歐語言) 開頭的字串要排在 "H" 之後，但單看字母的話，"C" 要在 "B" 之後。不過，如果明確只處理英美語系 (American/British English)，上述程式碼列表的第 9 及第 10 行可略去。 > 捷克字母 (依序) > A a Á á B b C c Č č D d Ď ď E e É é Ě ě F f G g ==H== h ==Ch== ch I i > Í í J j K k L l M m N n Ň ň O o Ó ó P p Q q R r Ř ř S s Š š > T t Ť ť U u Ú ú Ů ů V v W w X x Y y Ý ý Z z Ž ž 在 64 位元處理器架構 (以下針對 `x86_64`, little endian)，我們可引入向量化 (vectorized) 的手段，避免一次比對一個字元，而是直接操作一整個 word (對 `x86_64` 來說，就是 64 bits，或 8 個位元組)。沿用上述的 `strlower` 函式，我們用這樣的思路實作向量化的 `strlower`，程式碼列表如下: ```cpp #include <ctype.h> #include <stddef.h> #include <stdint.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) /* vectorized implementation for in-place strlower */ void strlower_vector(char *s, size_t n) { size_t k = n / 8; for (size_t i = 0; i < k; i++, s += 8) { uint64_t *chunk = (uint64_t *) s; if ((*chunk & PACKED_BYTE(VV1)) == 0) { /* is ASCII? */ uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + VV2); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + VV3); uint64_t mask = ((A ^ Z) & PACKED_BYTE(VV4)) >> 2; *chunk ^= mask; } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); } ``` 對應的測試程式碼如下: ```cpp #include <stdio.h> #include <string.h> int main() { /* quote from https://www.gutenberg.org/files/74/74-h/74-h.htm */ char str[] = "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 included \ with this eBook or online at www.gutenberg.net"; int n = strlen(str); strlower_vector(str, n); puts(str); } ``` 參考執行輸出: > 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 included with this ebook or online at `www.gutenberg.net` 請補完程式碼。 ==作答區== VV1 = ? * `(a)` `0x10` * `(b)` `0x20` * `(c)` `0x40` * `(d)` `0x60` * `(e)` `0x80` VV2 = ? * `(a)` `(-1)` * `(b)` `0` * `(c)` `1` VV3 = ? * `(a)` `(-1)` * `(b)` `0` * `(c)` `1` VV4 = ? * `(a)` `0x10` * `(b)` `0x20` * `(c)` `0x40` * `(d)` `0x60` * `(e)` `0x80` :::success 延伸問題: 1. 解釋上述程式的原理; 2. 將前述測試程式 `main` 函式的 `char str[]` 更換為 `char *str`，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為 ::: --- ### 測驗 `6` LeetCode [137. Single Number II](https://leetcode.com/problems/single-number-ii/): > Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. > > Note: > Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? > > Example 1: > Input: `[2,2,3,2]` > Output: 3 > > Example 2: > Input: `[0,1,0,1,0,1,99]` > Output: 99 考慮以下程式碼為 LeetCode [137. Single Number II](https://leetcode.com/problems/single-number-ii/) 的題解: ```cpp int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= KKK; higher ^= nums[i]; higher &= JJJ; } return lower; } ``` 請補完程式碼。 ==作答區== KKK = ? * `(a)` `higher` * `(b)` `lower` * `(c)` `~higher` * `(d)` `~lower` * `(e)` `0xFFFFFFFF` JJJ = ? * `(a)` `higher` * `(b)` `lower` * `(c)` `~higher` * `(d)` `~lower` * `(e)` `0xFFFFFFFF` :::success 延伸問題: 1. 解釋上述程式的原理; 2. 請撰寫不同上述的程式碼，並確保在 LeetCode [137. Single Number II](https://leetcode.com/problems/single-number-ii/) 執行結果正確且不超時; 3. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼; :::