# 2022q1 Homework5 (quiz8)
contributed by < `hankluo6` >

> [第 8 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz8)

## 測驗 `1`

### 程式原理

void *memchr_opt(const void *src_void, int c, size_t length)
{
    ...
        
    if (!TOO_SMALL(length)) {
        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 (!DETECT_CHAR(*asrc, mask)) { 
                /* if not find within sizeof(long) bytes */
                length -= LBLOCKSIZE;
                asrc += 1;
            } else {
                /* the character is within sizeof(long) bytes */
                break;
            }
            src = (unsigned char *) asrc;
        }
    }

    while (length--) {
        if (*src == d)
            return (void *) src;
        src++;
    }
}

`mask` 將一個 byte 的字元，擴充成 `sizeof(long)` 個 bytes，其中每個 byte 都是這個字元。檢查時便能利用 `DETECT_CHAR` 一次檢查字串中。

當超過 `sizeof(long)` 時，便能一次檢查字串中的 `sizeof(long)` 個 byte，利用 `DETECT_CHAR` 判斷是否有該字元，如果沒有則直接將長度 `length -= LBLOCKSIZE`，且 `asrc += 1` 表示檢查完 `sizeof(long)` 內的字元，繼續往剩餘字串中尋找。而當找到該字元在 `sizeof(long)` 內後直接跳出迴圈，會在最後的 `while` 迴圈中逐個字元檢查，故最後的迴圈不會跑超過 `sizeof(long)` 次。

### Linux 核心實作與 `memchr_opt` 比較


x 軸表示要找的字元在字串中的位置， y 軸為對應的時間。

可以發現 `memchr_opt` 所需時間皆比 Linux 版本還小，且成長幅度也比 Linux 版本還少。

###### tags: `linux2022`