c++ - 是否有与 `memchr` 具有相似性能的函数可以将每个字符与位掩码匹配而不是完全相等？

Question

我试图解决的实际问题是搜索出现的位模式(110xxxxx、1110xxxx、11110xxx)表示UTF-8中多字节字符的开始。

我希望找到速度与 memchr() 类似的东西，但没有找到任何东西。我不能自己编写程序集，因为它必须是可移植的。

Answer 1

您正在尝试定位第一个 UTF-8 序列起始字节。测试是:

(c >= 0xC0 && c <= 0xF7)

这可以通过对每个字节进行一次测试来非常有效地完成:

void *memfind_start_byte(const void *p, size_t len) {
    unsigned char *s = (unsigned char *)p;
    while (len-- > 0) {
        if ((unsigned char)(*s++ - 0xC0) <= 0xF7 - 0xC0)
            return (void *)(s - 1);
    }
    return NULL;
}

这个循环可以通过优化编译器或多或少地自动展开。

您可以使用按位技巧一次检查多个字节，如 strlen():对齐源指针后，您可以一次检查 8 个字节:

if (*(uint64_t*)p & 0x8080808080808080) {
    /* one byte might match: write 8 tests */
}

这是一个未经测试的尝试:

void *memfind_start_byte(const void *p, size_t len) {
    unsigned char *s = (unsigned char *)p;
    while (((uintptr_t)s & 7) && len-- > 0) {
        if ((unsigned char)(*s++ - 0xC0) <= 0xF7 - 0xC0)
            return (void *)(s - 1);
    }
    for (; len >= 8; len -= 8, s += 8) {
        if (*(uint64_t *)s & 0x8080808080808080) {
            if ((unsigned char)(s[0] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 0);
            if ((unsigned char)(s[1] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 1);
            if ((unsigned char)(s[2] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 2);
            if ((unsigned char)(s[3] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 3);
            if ((unsigned char)(s[4] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 4);
            if ((unsigned char)(s[5] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 5);
            if ((unsigned char)(s[6] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 6);
            if ((unsigned char)(s[7] - 0xC0) <= 0xF7 - 0xC0) return (void *)(s + 7);
        }
    }
    while (len-- > 0) {
        if ((unsigned char)(*s++ - 0xC0) <= 0xF7 - 0xC0)
            return (void *)(s - 1);
    }
    return NULL;
}