---
# System prepended metadata

title: 2022-04-04 quiz8
tags: [linux2022]

---

---
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

