# W3 ## Q1 ## Q2 #### 解釋程式碼運作原理 這段程式碼運用 [SWAR ](https://en.wikipedia.org/wiki/SWAR) 達到 [memchr](https://man7.org/linux/man-pages/man3/memchr.3.html) 的優化，memchr_opt 分成三個部分 * 先逐個 byte 檢查未對齊記憶體位置的部分 * 接著透過 mask 一次檢查一個 word 長度 * 最後檢查剩餘部分 重點在於第二部分要如何一次檢查一個 word 長度，首先先定義 `DETECT_NULL` ```c #if LONG_MAX == 2147483647L #define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080)) #else #if LONG_MAX == 9223372036854775807L /* Nonzero if X (a long int) contains a NULL byte. */ #define DETECT_NULL(X) \ (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080)) #else #error long int is not a 32bit or 64bit type. #endif #endif ``` 在不同設備上 long 的大小可能為 4 bytes 或 8 bytes，在 Linux 中，long 通常為 8 bytes，後續討論皆將 long 的大小視為 8 bytes。`DETECT_NULL` 用來檢查 `X` 裡有沒有 NULL byte 也就是 `0x00`。 接著定義 `DETECT_CHAR` ```c /* @return nonzero if (long)X contains the byte used to fill MASK. */ #define DETECT_CHAR(X, mask) DETECT_NULL(AAAA) ``` 檢查 `X` 中 有沒有包含 `mask` ，其中 `mask` 實作如下 ```c unsigned long mask = d << 8 | d; mask |= mask << 16; for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1) mask |= BBBB ``` `mask` 的用意是產生一段 word 大小的目標字元，如果想要找 `'A'` 這個字元，對應到的 byte 為 `0x41`，產生的 `mask` 即為 `0x4141414141414141`，所以 `BBBB` 為 `mask << i`。 接著討論 `DETECT_CHAR` ，想法是要運算使得 X 中目標字元的 byte 變為 NULL byte，XOR 的真值表如下 | A | B | output | | -------- | -------- | -------- | | 0 | 0 | 0 | | 1 | 0 | 1 | | 0 | 1 | 1 | | 1 | 1 | 0 | 於是 `AAAA` 為 `X^mask`。 接著看到 ```c while (len >= LBLOCKSIZE) { if (DETECT_CHAR(CCCC, mask)) break; asrc++; len -= LBLOCKSIZE; } ``` 這段程式碼會使用 `DETECT_CHAR` 一次檢查一個 word 的長度，看字串中有沒有目標字元，直到找到或者是剩下字串的長度不足一個 word 的長度。`CCCC` 即為指向字串目前檢查的起始點的值 `*asrc`。