优化单个字节的字符串搜索

Question

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

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

那么，有哪些加速搜索的替代算法？

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

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

所以，假设我们的搜索字符是 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))))

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

此时您可以从表达式的 return 值中获取匹配字节（或多个字节）的位置，例如如果最低有效字节与该值匹配，则该值将为 0x00000080。

优化单个字节的字符串搜索

optimizing string search for a single byte

c++

string-search