c++ - 优化单个字节的字符串搜索

Question

一般而言，字符串搜索算法(如 Boyer-Moore)针对搜索字符串 较长的情况进行了优化。也就是说，Boyer-Moore 很棒，因为通过将搜索字符串与我们的文本对齐，如果搜索字符串的末尾与文本不匹配，我们可以跳过 N = len(search string) 个字符.

但是如果我们的搜索字符串真的很短怎么办？像单个字节或字符？在这种情况下，Boyer-Moore 帮助不大。

那么，有哪些替代算法可以加快搜索速度？

我知道许多优化的库搜索例程(如 C 中的 memchr)采用逐字读取输入字符串的策略，而不是逐字符读取的策略。因此在 64 位机器上，一次可以检查 8 个字节，而不是单个字节。

我想知道这些优化的字符串/字节搜索实际上是如何工作的。那么实际的比较是如何进行的呢？我知道它显然必须涉及位屏蔽 - 但我看不出执行所有位屏蔽比简单地逐个字符搜索更好。

因此，假设我们的搜索字符是 0xFF。忽略对齐问题，假设我们有一些输入缓冲区:void* buf。我们可以逐字阅读:

const unsigned char search_char = 0xFF;
unsigned char* bufptr = static_cast<unsigned char*>(buf);
unsigned char* bufend = bufptr + BUF_SIZE;

while (bufptr != bufend)
{
   // Ignore alignment concerns for now, assume BUF_SIZE % sizeof(uintptr_t) == 0
   //
   std::uinptr_t next_word = *reinterpret_cast<std::uintptr_t*>(bufptr);

   // ... but how do we compare next_word with our search char?

   bufptr += sizeof(std::uintptr_t);
}

我也意识到上面的代码不是严格可移植的，因为 std::uintptr_t 不能保证实际上是字的大小。但是，为了这个问题，我们假设 std::uinptr_t 等于处理器字长。 (实际的实现可能需要特定于平台的宏来获取实际的字长)

那么，我们如何实际检查字节 0xFF 是否出现在 next_word 的值中的任何位置？

我们当然可以使用 OR 操作，但似乎我们仍然需要执行大量的 OR'ing 和位移来检查 next_word 的每个字节, 在这一点上，这种优化是否真的比简单地逐个字符扫描更好是值得怀疑的。

Answer 1

您可以使用 this snippet from Bit Twiddling Hacks :

#define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL)
#define hasvalue(x,n) \
(haszero((x) ^ (~0UL/255 * (n))))

它有效地将每个字节与要测试的字符进行异或，然后确定是否有任何字节现在为零。

此时你可以从表达式的返回值中得到匹配字节(或多个字节)的位置，例如如果最低有效字节与该值匹配，则该值将为 0x00000080。