---
tags: linux2022
---
# 2022-04-04 quiz8
contributed by < `blueskyson` >
[題目連結](https://hackmd.io/@sysprog/linux2022-quiz8)
## 測驗 1
首先看 `memchr_opt` 的前 12 行：
```c=
void *memchr_opt(const void *src_void, int c, size_t length)
{
const unsigned char *src = (const unsigned char *) src_void;
unsigned char d = c;
while (UNALIGNED(src)) {
if (!length--)
return NULL;
if (*src == d)
return (void *) src;
src++;
}
```
其中 `UNALIGNED` 巨集定義如下：
```c
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))
```
當 `UNALIGNED` 的 `X` 是對齊 `long` 的位址時，`UNALIGNED(X)` 的值為 `0`，因此在第 6 到 12 行的迴圈中，如果 `*src` 為字元 `d`，就直接回傳其所在的位址，否則 while 迴圈會於 `src` 指向對齊 `long` 的位址時跳出。
在 64 位元的系統上對齊 `long` 的位址為 8 的倍數，例如 `0x01000`、`0x10000` 等。
```c=13
if (!TOO_SMALL(length)) {
/* The fast code reads the source one word at a time and only performs
* the bytewise search on word-sized segments if they contain the search
* character, which is detected by XORing the word-sized segment with a
* word-sized block of the search character and then detecting for the
* presence of NULL in the result.
*/
unsigned long *asrc = (unsigned long *) src;
unsigned long mask = d << 8 | d;
mask = mask << 16 | mask;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask = (mask << i) | mask;
while (length >= LBLOCKSIZE) {
/* XXXXX: Your implementation should appear here */
}
/* If there are fewer than LBLOCKSIZE characters left, then we resort to
* the bytewise loop.
*/
src = (unsigned char *) asrc;
}
```
其中 `LBLOCKSIZE` 與 `TOO_SMALL` 巨集定義如下：
```c
#define LBLOCKSIZE (sizeof(long))
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)
```
當剩餘字串長度大於等於 `long` 的大小（4 byte 或 8 byte）時就進入第 13 行 if 條件。
第 21 到 24 行的作用是將 1 byte 的 `d` 擴展成 4 byte 或 8 byte 的 `mask`。舉例來說，如果 `d` 的值為 `0x2e`，則 `mask` 為 `0x2e2e2e2e2e2e2e2e`。
接下來就是實作第 26 行 while 迴圈，這裡老師提供了 `DETECT_CHAR` 巨集來偵測哪個位置的值為 `d` 的值：
```c
#define DETECT_NULL(X) (((X) -0x0101010101010101) & ~(X) & 0x8080808080808080)
#define DETECT_CHAR(X, MASK) (DETECT_NULL(X ^ MASK))
```
為了釐清 `DETECT_CHAR` 的作用，我將每一步運算印出，舉 `"//wiki.c"` 為例，從中偵測字元 `'.'`：
```c
int main() {
const char *src = "http://wiki.csie.ncku.edu.tw";
char d = '.';
while (UNALIGNED(src))
src++;
unsigned long mask = d << 8 | d;
mask = mask << 16 | mask;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
mask = (mask << i) | mask;
unsigned long *asrc = (unsigned long *) src;
unsigned long xor = *asrc ^ mask;
printf("\"%.8s\"\n", src);
printf("%016lx\n", *asrc);
printf("%016lx\n", xor);
printf("%016lx\n", xor - 0x0101010101010101);
printf("%016lx\n", (xor - 0x0101010101010101) & ~xor);
printf("%016lx\n", (xor - 0x0101010101010101) & ~xor & 0x8080808080808080);
return 0;
}
```
輸出如下：
```bash
"://wiki." # src
2e696b69772f2f3a # asrc
0047454759010114 # xor = asrc ^ mask
ff46444658000013 # xor - 0x0101010101010101
ff00000000000003 # (xor - 0x0101010101010101) & ~xor
8000000000000000 # DETECT_CHAR(asrc, mask)
```
1. 首先可以發現將 `"://wiki."` 以 `unsigned long` 讀取時，位元組的順序會倒過來，即 `2e696b69772f2f3a` 對應到 `".ikiw//:"`。
2. 接下來 `asrc ^ mask` 會得到 `0047454759010114` 可以發現 `00` 即對應到 `'.'` 的位置，我將 `asrc ^ mask` 的結果存到變數 `xor`。
3. `xor - 0x0101010101010101` 會將 `xor` 中的 `00` 轉變為 `fe` 或 `ff`。
4. 在上面的例子中，跳過 `& ~xor` 這一步驟是 ok 的，我推論這個步驟是為了防止超過 ASCII 範圍（大於 127）的字元影響到下一步的判斷。經過這一步驟可以強制將
5. 最後一步將前面運算的結果 `& 0x8080808080808080` 就能將所有 `fe` 與 `ff` 提取出來變成 `80`，並且其他 byte 變為 `00`。
### 解題
分析完前述程式碼的用途，開始補完上程式碼
```c
while (length >= LBLOCKSIZE) {
/* XXXXX: Your implementation should appear here */
unsigned long bits = DETECT_CHAR(*asrc, mask);
if (bits)
return (char*)asrc + (__builtin_ctzl(bits) >> 3);
asrc = asrc + 1;
length = length - 8;
}
```
首先用變數 `bit` 儲存 `DETECT_CHAR` 的結果，接下來先判斷 `bits` 是否大於 `0`。若是則代表找到所求字元，透過 `__builtin_ctzl(bits) >> 3` 得到該字元與 `asrc` 的距離，最後回傳 `asrc` 轉型為 `char*` 加上該字元與 `asrc` 的距離。
### 後續程式碼
```c=35
while (length--) {
if (*src == d)
return (void *) src;
src++;
}
return NULL;
}
```
最後若剩餘的字串長度不足 `long` 的長度，則透過第 35 行的 while 迴圈找尋所求字元。若還是找不到就回傳 `NULL`。
## 測驗 2
## 測驗 3
Sign in with Wallet
Connect another wallet