--- tags: Linux2020 --- # 2020q3 Homework2 (quiz2) contributed by < `YLowy` > ## 測驗 `1` ### 題目 : 目前電腦中用得最廣泛的字元集及其編碼，是美國國家標準局 (ANSI) 制定的 ASCII 碼，被國際標準化組織 (ISO) 採納為 ISO 646 標準。7 位碼 ASCII 是以 7 位元二進位數字進行編碼，可表示 128 個字元，第 128～255 號為擴展字元 (extended ASCII)。如果我們明確界定 7 位元編碼的字元隸屬於 ASCII，可透過以下函式來判斷指定的記憶體範圍內是否全是有效的 ASCII 字元: ```c= #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)，程式碼改寫如下: ```c= #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 = 0x8080808080808080 方便起見可以看看 ASCII Table ![](https://i.imgur.com/3Bdbevw.png) 單個 byte 若屬於 ASCII 類型必定為 0x1*** **** 所以對任此 byte 做 & 0x80 0x0*** **** 結果必定為 0 64 位元 CPU 可以一次判斷 8 組 bytes 可得到 0x 80 80 80 80 80 80 80 80 ### 延伸問題 1. 解釋上述程式的運作原理，特別是為何用到 memcpy 呢？提示: 與 data alignment 有關，詳閱 C 語言：記憶體管理、對齊及硬體特性 memcpy() 會先進行檢查memory address 是否 word aligned 當我們想對 8 個 bytes (8*8 bits) 做處理 使用 memcpy 可以針對某些 unaligned 硬體做處理 2. 將上述技巧應用於「給予一個已知長度的字串，檢測裡頭是否包含有效的英文大小寫字母」 3. 承 (2)，考慮常見的英文標點符號，判斷輸入字串是否為有效的字元集，避免逐一字元比對 ( 提示: Intel SSE 4.2 加入 STTNI (String and Text New Instructions) 指令，可加速字串比對，詳見: Schema Validation with Intel® Streaming SIMD Extensions 4 ) ## 測驗 `2` 開發解析器 (parser) 時，常會將十六進位表示的字串 (hexadecimal string) 轉為數值，例如 '0xF' (大寫 F 字元) 和 '0xf' (小寫 f 字元) 都該轉換為 15。考慮以下不需要分支 (branchless) 的實作: ```c= uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & MASK; const uint8_t shift = (letter >> AAA) | (letter >> BBB); return (in + shift) & 0xf; } ``` '1' -> 0011 0000 'a' -> 0110 0001 'A' -> 0100 0001 如果說要判斷 in 是英文還是數字可以直接 (in & 0100 0000) 輸出結果為 0 代表數字 輸出結果為 1 代表英文 MASK 可以判斷為 0100 0000 -> 0x40 10 = 9 + 1 1010=1001 + 0001 可知道 AAA = 3 BBB = 6 ### 延伸問題 將 hexchar2val 擴充為允許 "0xFF", "0xCAFEBABE", "0x8BADF00D" 等字串輸入，且輸出對應的十進位數值 ```c= /* This is for hexchar2val and allow "0XFF" "0xCAFEBABE" "0x8BADF00D" */ #include <stdio.h> #include <stdint.h> #include <string.h> #include <assert.h> uint8_t hexchar2val(uint8_t in) { const uint8_t letter = in & 0x40; const uint8_t shift = (letter >> 3) | (letter >> 6); return (in + shift) & 0xf; } int Hexspeak(char input[]){ size_t len = strlen(input); assert(len <= 18); //printf("len : %d \n",len); assert(input[0]=='0' && (input[1]=='x'||input[1]=='X')); // make sure 0x ________ unsigned int answer = 0; for(int i=2;i<=len-1;i++){ answer <<= 4; answer |= hexchar2val(input[i]); } return answer; } int main(){ char input[] = "0xFFFF"; printf("Input :%s \t Output :%d \n",input, Hexspeak(input)); return 0; } ``` 不過以上會根據輸入字元大小影響執行速度，可以思考能不能改進這點 ## 測驗 `3` 快速除法 ```c= const uint32_t D = 3; #define M ((uint64_t)(UINT64_C(0xFFFFFFFFFFFFFFFF) / (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; } ``` 按照題目一開始所想的應該是要讓一個 $2^n$/D 找出 M，然後就卡住了 沒有任何選項是符合的 後來想一下可以想到不如用 $2^{32}$-1 這個值也就是 0xFFFFFFFFFFFFFFFF ($2^{32}$-1)/D =$2^{32}$/D - 1/D 最後補上 +1 確保 M 值是 "正確值無條件進整數位" 微微略大於原本計算數值 也就是 M = $\dfrac{0xFFFFFFFFFFFFFFFF}{D}$ + $\dfrac{D-1}{D}$ quickmod() 的部分挺容易理解的 quotient 就是 $\dfrac{n * M}{2^{32}}$ 也就是商數 餘數就是 n - 商數 * D ## 測驗 `4` 檢查是否能被整除 ```c= bool divisible(uint32_t n) { return n * M <= (M - 1); } ``` 這邊還蠻難想到的 我認為n * M 這個值相乘會導致overflow (<<32) 但是先前提到M 是一個"微微略大於原計算的值" `return n * M <= (M - 1);` n * M = n * ${0xFFFFFFFFFFFFFFFF/D}$ <= (M - 1) = 0xFFFFFFFFFFFFFFFF 簡化 n/D <=1 如果整除 n/D = 0 <=1 -> true ## 測驗 `5` ```c= #include <ctype.h> #include <stddef.h> #include <stdint.h> #include<string.h> #define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u) 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]); } } /* 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(0x40)) == 0) { /* is ASCII? */ uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + 1); uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x40)) >> 2; *chunk ^= mask; } else strlower(s, 8); } k = n % 8; if (k) strlower(s, k); } 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); } ``` `#define PACKED_BYTE(b) (((uint64_t)(b) & (0xff)) * 0x0101010101010101u)` 這個假設input b = 0xAB 那 PACKED_BYTE(b) = 0xABABABABABABABAB 和第一題很像透過 0x40 mask 判斷這個 bytes 是否屬於 ASCII 再來我們目標: 如果該字元介於 65 ~ 90 之間 讓該值 + 32 ```c= uint64_t A = *chunk + PACKED_BYTE(128 - 'A' + 0); uint64_t Z = *chunk + PACKED_BYTE(128 - 'Z' + 1); ``` 這裡要先從 128 -> A(65) 128->Z (90) 這兩段距離開始想 如果我有任意一個字元介於 A~Z 假設為B (66) B(66) + 128 -> A(65) 距離 or B(66) + 128->Z (90) 距離 會有其中一個 > 128 也就會造成該 byte 最高 bit 變成 1 (0x1XXXXXXX) ```c= uint64_t mask = ((A ^ Z) & PACKED_BYTE(0x80)) >> 2; ``` 0x1XXX XXXX & 0x1000 0000 在 right shift 2 bits 成為對 ASCII 大寫轉小寫的 mask 再來透過 bit 操作讓原本值 +32 就能轉成最小寫字元了 ### 延伸問題 將前述測試程式 main 函式的 char str[] 更換為 char *str，會發生什麼事？請參閱 C 語言規格書，說明 string literal 的行為 ``` char str[] = "This eBook ...; ``` 改寫成 ``` char *str = "This eBook ...; ``` Output: ``` $ ./quiz2Q5 Segmentation fault (core dumped) ``` C11 規格書: 6.4.5 String literals Semantics: 4. In translation phase 6, the multibyte character sequences specified by any sequence of adjacent character and wide string literal tokens are concatenated into a single multibyte character sequence. If any of the tokens are wide string literal tokens, the resulting multibyte character sequence is treated as a wide string literal; otherwise, it is treated as a character string literal. 6. It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined. 6.7.8 Initialization: 14. An array of character type may be initialized by a character string literal, optionally enclosed in braces. char 陣列 initialized 成先前提到的 character string literal 而根據上述對於更動 character string literal 的值是 undefined behavior 32. The declaration **char s[] = "abc", t[3] = "abc";** defines ‘‘plain’’ char array objects s and t whose elements are initialized with character string literals. This declaration is identical to *char s[] = { 'a', 'b', 'c', '\0' }, t[] = { 'a', 'b', 'c' };* The contents of the arrays are modifiable. On the other hand, the declaration *char p = "abc";* defines p with type ‘‘pointer to char’’ and initializes it to point to an object with type ‘‘array of char’’ with length 4 whose elements are initialized with a character string literal. If an attempt is made to use p to modify the contents of the array, the behavior is undefined. char a[1] <- 這是可以修改的，沒問題 char a* <- 修改這個是 undefined behavior ** *當我使用* char *a 會在 read only memory 裡面建立該字串，回傳當記憶體位址 而使用 char a[] 時候同樣的也會在 read only memory 建立字串並且回傳位址，不同的是會在當下 stack 中建立相對應副本 故可以修改 character array 內的內容。** ## 測驗 `6` ```c= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0; for (int i = 0; i < numsSize; i++) { lower ^= nums[i]; lower &= ~higher; higher ^= nums[i]; higher &= ~lower; } return lower; } ``` #### 以下解釋: 一直想不太通這個機制，直接用帶入數字試試看 ``` lower ^= nums[i]; lower &= ~higher; higher ^= nums[i]; higher &= ~lower; ``` Input = [2, 1, 2, 2] 1. num[0] = 2: lower = 0010 lower = 0010 <- 該次輸出 lower higher = 0010 higher = 0000 <- 該次輸出 h 2. num[0] = 1: lower = 0011 lower = 0011 <- 該次輸出 lower higher = 0001 higher = 0000 <- 該次輸出 h 3. num[0] = 2: lower = 0001 lower = 0001 <- 該次輸出 lower higher = 0010 higher = 0010 <- 該次輸出 h 4. num[0] = 2: lower = 0011 lower = 0001 <- 該次輸出 lower higher = 0000 higher = 0000 <- 該次輸出 h l = 0001 為解 做到這裏有點感覺就是他是透過狀態圖機制 : 剛好三次回到 00 做延伸 一開始想法卡住因為直覺應該要記住當下輸入資料，但是其實可以透過 XOR 這個運算元以記錄得到數字，經過上述狀態機描述可以得到一開始推得結果。 我覺得跟之前上課提到 bitwise swap 有以曲同工之妙 在一有限狀態機下，分別有**0**(00) , **1**(01) , **2**(10) 個別的 state state 為 2 個 bits 組成分別為 low bit / higher bit ```graphviz digraph { rankdir = LR 0 1 2 0->1 1->2 2->0 0->0 1->1 2->2 } ``` 想一下current state -> + input -> next state 的狀態圖 ```graphviz digraph D { node_A [shape=record label="{current state|00|00|01|01|11(X)|11(X)|10|10}|{input |0|1|0|1|0|1|0|1}|{next state|00|01|01|10|X|X|10|00}"]; } ``` higher bit 的邏輯圖 ```graphviz digraph D { node_A [shape=record label="{in\\state|0|1}|{00|0|0}|{01|0|1}|{11|X|X}|{10|1|0}"]; } ``` lower bit 的邏輯圖 ```graphviz digraph D { node_A [shape=record label="{in\\state|0|1}|{00|0|1}|{01|1|0}|{11|X|X}|{10|0|0}"]; } ``` lower = in & (~higher) & (~lower) + (~in) & (~higher) & lower = (~higher) & (in & (~lower) + (~in) & lower ) = (~higher) & (in & (~lower) + (~in) & lower ) = (~higher) & (in ⊕ lower) C 可以寫成 `lower = lower ^ input; lower = lower & ~higher;` 在精簡些就寫成題目所寫的方式 再來 higher 比較特別 如果是讓我寫的話應該就只能寫出 higher = (~in) & higher + (in) & lower 這種 " 正確 " 的邏輯判斷式 由於一開始先計算 Lower 新的 Lower 可以取代舊的 Lower 並且加入原先計算 higher 的狀態圖 新的 state 的狀態圖 : ```graphviz digraph D { node_A [shape=record label="{current state|00|01|01|00|11(X)|11(X)|10|10}|{input |0|1|0|1|0|1|0|1}|{next state(higer)|0|0|0|1|X|X|1|0}"]; } ``` higher = (~higher) & (~newl) & input + higher & (~newl) & (~input) =(~newlower) & (higher ⊕ in) 濃縮成`higher ^= nums[i]; higher &= ~lower;` 也就是題目附上的對稱 " 優雅 " 的程式碼 想不到短短 4 行我會花那麼多時間zzz #### 延伸問題 ***1. 請撰寫不同上述的程式碼，並確保在 LeetCode 137. Single Number II 執行結果正確且不超時;*** https://leetcode.com/problems/single-number-ii/ 上述題目所寫的程式中可以看到 higher 會使用到前一次所計算的 new lower 對於效能而言若是想要計算 higher 必須先等 lower 計算完成 而若是使用我先前所說的 " 正確 " 程式碼: higher = (~in) & higher + (in) & lower ` higher &= ~nums[i] ; higher += nums[i] & lower; ` 可以再多核系統上做平行運算，省下等待時間 但是會多使用一組 tmp 存放上個 lower ```c= int singleNumber(int *nums, int numsSize) { int lower = 0, higher = 0, tmp = 0; for (int i = 0; i < numsSize; i++) { tmp = lower; lower ^= nums[i]; lower &= ~higher; higher &= ~nums[i]; higher += (nums[i] & tmp); } return lower; } ``` ![](https://i.imgur.com/s9kziV1.png) ***2. 延伸題意，將重複 3 次改為改為重複 4 次或 5 次，並找出可容易推廣到多次的程式碼*** 偶數次都可以透過 1 個 state 完成， 最後落在 " State 1 " 為 Output 而奇數次得透過新增狀態機以擴充，也就是原先 higher lower 所組成的狀態需要更多位元表示
Last changed by  
 
YLowy
455

Read more

eBPF

Debug always make developer sad, especially in a big system. How to debug in Linux Kernel? Tracing In early kernel patch, we have some tracing tools, e.g. strace, gdb. They are all based on the old tracing system call: ptrace. GDB gdb -q test.o strace

7/8/2022
How io_uring and eBPF Will Revolutionize Programming in Linux

refer: https://thenewstack.io/how-io_uring-and-ebpf-will-revolutionize-programming-in-linux/ io_uring Classic IO system call For UDP's receive system call, it can be divided into two stages, wait for data and copy data to user space. Kernel offered the following blocking system calls to deal with file descriptors, be they storage files or sockets: size_t read(int fd, void *buf, size_t count); size_t write(int fd, const void *buf, size_t count);

6/15/2022
Optimed Strlen (cont.)

1. uclib vs glib uclib ->https://git.uclibc-ng.org/git/uclibc-ng.git uClibc-ng is a small C library for developing embedded Linux systems. It is much smaller than the GNU C Library, but nearly all applications supported by glibc also work perfectly with uClibc-ng. In strlen() function, the "finding zero in long size string" is different between glib and uclib. See Here //uclib

6/6/2022
Optimed Strlen

We often use the strlen(str) function to get the length of the string. This is broad-use, and simply implemented. In C, we cannot consider a string as an object. We need to find the '\0'(NULL) character to determine the end of the string. C11 6.4.5 6. a byte or code of value zero is appended to each multibyte character sequence that results from a string literal or literals. C11 7.1.1 A string is a contiguous sequence of characters terminated by and including the first null character. The term multibyte string is sometimes used instead to emphasize special processing given to multibyte characters contained in the string or to avoid confusion with a wide string. A pointer to a string is a pointer to its initial (lowest addressed)

5/22/2022
Read more from YLowy
Published on HackMD