c - 使用按位运算快速查找长整数中的 ascii 字符的方法？

Question

我正在制作一个 strchr 实现并尝试优化我的代码以使用我机器的 64 位属性。因此，我将我的字符串转换为长整数，从而一次比较 8 个字符。

目前，我有:

int    has_char(unsigned long word, unsigned long c)
{
    if((word & 0xFF00000000000000) == (c << 56) ) return (1);
    if((word & 0x00FF000000000000) == (c << 48))  return (1);
    if((word & 0x0000FF0000000000) == (c << 40))  return (1);
    if((word & 0x000000FF00000000) == (c << 32))  return (1);
    if((word & 0x00000000FF000000) == (c << 24))  return (1);
    if((word & 0x0000000000FF0000) == (c << 16))  return (1);
    if((word & 0x000000000000FF00) == (c << 8))   return (1);
    if((word & 0x00000000000000FF) == c)          return (1);
    return (0); /* Not found, returning 0 */
}

char    strchr(const char *s, int c)
{
    const char      *curr;
    const long      *str;
    unsigned long    wd;

    str = (long *)s;
    while (1) {
        wd = *str;
        if (has_char(wd, (unsigned long)c)) {
            curr = (char *)str;
                while (*curr) {
                    if (*curr == (char)c)
                        return ((char *)curr);
                    curr++;
                }
        }
        if ((wd - 0x0101010101010101)
            & ~wd & 0x8080808080808080) /* End of string and character not found, exit */
            return (NULL);
    str++;
    }
}

它运行良好，但我的 has_char 效率很低，它测试了 8 次字符值。有没有办法进行独特的测试(掩码？)，如果该字符出现在单词中则返回 1，如果不出现则返回 0？

感谢您的帮助!

Answer 1

很好，这里是要求的精确代码:

// Return a non-zero mask if any of the bytes are zero/null, as per your original code
inline uint64_t any_zeroes(uint64_t value) {
    return (value - 0x0101010101010101) & ~value & 0x8080808080808080;
}

char *strchr(const char *s, int ch) {
    // Pre-generate a 64-bit comparison mask with the character at every byte position
    uint64_t mask = (unsigned char) ch * 0x0101010101010101;
    // Access the string 64-bits at a time.
    // Beware of alignment requirements on most platforms.
    const uint64_t *word_ptr = (const uint64_t *) s;

    // Search through the string in 8-byte chunks looking for either any character matches
    // or any null bytes
    uint64_t value;
    do {
        value = *word_ptr++:
        // The exclusive-or value ^ mask will give us 0 in any byte field matching the char
        value = any_zeroes(value) | any_zeroes(value ^ mask);
    } while(!value);

    // Wind-down and locate the final character. This may be done faster by looking at the
    // previously generated zero masks but doing so requires us to know the byte-order
    s = (const char *) --word_ptr;
    do {
        if(*s == (char) ch)
            return (char *) s;
    } while(*s++);
    return NULL;
}

当心:写在我的头顶上。