2022-04-04 yyyyuwen

contributed by < yuwen >

作業要求

測驗1 memchr_opt

透過 memchr_opt 傳入的參數分別為

• const void *src_void ：memort area
• int c ：the byte to search for
• size_t length ：the size of its area

在 64–bit Size 底下， long 代表 8 byte。
可以得知程式碼中一開始先去檢查是否小於 8 byte

/* Nonzero if either X or Y is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

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

TOO_SMALL 是在檢查長度是否超出 8 byte

/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)

d 是要搜尋的字元，先將d擴展為 8 byte 來做後續的搜尋

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;

例如
d = 2e
第二行 mask = 2e2e
第三行 mask = 2e2e2e2e
第五行 mask = 2e2e2e2e2e2e2e2e

當要搜尋的句子長度 >= LBLOCKSIZE 時，一次 8 byte 遞迴下去找直到找到為止，若找不到則跳出 while 並回傳NULL。

while (length >= LBLOCKSIZE) {
    /* XXXXX: Your implementation should appear here */
    // 如果有找到
    if (DETECT_CHAR(*asrc, mask)) {
        // 取得該位址的字串
        src = (unsigned char *) asrc;
        while (length-- != 0) {
            // find the target char 
            if (*src++ == d)
                return (void *) (src - 1);
        }
    }
    else {
        // 一次減少 8 byte
        length -= LBLOCKSIZE;
        // 這邊宣告的是double的型態，當指標+1 等於一次前進8 byte
        asrc += 1;
    }
}

測試

int main()
{
    const char str[] = "http://wiki.csie.ncku.edu.tw";
    const char ch = 'n';
    const char ch1 = '/';
    const char ch2 = '.';


    char *ret = memchr_opt(str, ch, strlen(str));
    printf("String after |%c| is - |%s|\n", ch, ret);

    char *ret1 = memchr_opt(str, ch1, strlen(str));
    printf("String after |%c| is - |%s|\n", ch1, ret1);

    char *ret2 = memchr_opt(str, ch2, strlen(str));
    printf("String after |%c| is - |%s|\n", ch2, ret2);
    return 0;
}

結果

String after |n| is - |ncku.edu.tw|
String after |/| is - |//wiki.csie.ncku.edu.tw|
String after |.| is - |.csie.ncku.edu.tw|

測驗2

測驗3