# 2022q1 Homework5 (quiz8)

contributed by < [tommy2234](https://github.com/tommy2234) >

題目連結 [quiz8](https://hackmd.io/@sysprog/linux2022-quiz8)

## 測驗 1
### Overview
當我們想尋找一個字串中第一次出現某字元的位置，最 naive 的方法便是從頭開始一個個 character 逐一檢查，但是此方法一次只能檢查一個 byte。

在本題中我們運用 SIMD 的概念，一次抓取一個 long 長度的 block ，在此 block 之中套用 bitwise 的操作偵測該字元的存在。

/* 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.
 */

### DETECT_CHAR
`DETECT_CHAR` 的概念是利用目標字元去對一個 block 之中每一個 byte 做 `XOR` ，當字元在 block 中存在 ，其所在的 byte 就會變成 0，如此就能達到辨別該字元的效果。

### memchr_opt() 函式

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++;
    }

    if (!TOO_SMALL(length)) {
        /* If we get this far, we know that length is large and
         * src is word-aligned.
         */

        /* 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.
         */

        // create a mask of length (8 * sizeof(long)) bits
        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))
                break;
            asrc++;
            length -= LBLOCKSIZE;
        }
        
        /* If there are fewer than LBLOCKSIZE characters left, then we resort to
         * the bytewise loop.
         */
        src = (unsigned char *) asrc;
    }

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

    return NULL;
}

- 首先我們將指向字串位置的指標 src 轉型為（unsigned Long \*) 之後 assign 給 asrc ，此時 asrc 就是我們當前抓取的 block 。
一個 block 的長度為 sizeof(long) bytes ，定義在 LBLOCKSIZE 。

        unsigned long *asrc = (unsigned long *) src;

- 接著我們創造一個 LBLOCKSIZE 個目標字元排列而成的 bit mask 。

        unsigned long mask = d << 8 | d;
        mask = mask << 16 | mask;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask = (mask << i) | mask;

- 在迴圈中不斷抓取下一個 block 並偵測目標字元的存在，直到字元被偵測到，或者剩下的字串長度少於一個 block 的大小。

        while (length >= LBLOCKSIZE) {
            /* XXXXX: Your implementation should appear here */
            if(DETECT_CHAR(*asrc, mask))
                break;
            asrc++;
            length -= LBLOCKSIZE;
        }

- 當字元在 block 中出現，我們跳出迴圈，然後逐個 byte 尋找其確切位置並回傳。