在比特流中扫描比特模式的最快方法

使用简单的暴力有时是好的。

我认为precalc会将单词的值全部移位,并将它们放在16整数中 所以你得到了这样一个数组(假设 int 它的宽度是它的两倍 short )

 unsigned short pattern = 1234;
 unsigned int preShifts[16];
 unsigned int masks[16];
 int i;
 for(i=0; i<16; i++)
 {
      preShifts[i] = (unsigned int)(pattern<<i);  //gets promoted to int
      masks[i] = (unsigned int) (0xffff<<i);
 }

所以基本上是这样的:

  int numMatch(unsigned short curWord, unsigned short prevWord)
  {
       int numHits = 0;
       int combinedWords = (prevWord<<16) + curWord;

       int i=0;
       for(i=0; i<16; i++)
       {
             if((combinedWords & masks[i]) == preShifsts[i]) numHits++;
       }
       return numHits;
  }

假设编译过程与编写过程大致相同,则此过程的时间成本为每个输入字16次检查。每输入一位,这就有一个 & 和 == ,以及分支或其他条件增量。以及每一位掩码的表查找。

不需要查表;而是右移 combined 如图所示,我们的asm效率显著提高 in another answer 它还显示了如何在x86上使用SIMD对此进行矢量化。

您可以首先使用包含256个条目的表来检查位流中的每个字节(如果它包含在您要查找的16位字中)。你的桌子

unsigned char table[256];
for (int i=0; i<256; i++)
  table[i] = 0; // initialize with false
for (i=0; i<8; i++)
  table[(word >> i) & 0xff] = 1; // mark contained bytes with true

然后,您可以使用

for (i=0; i<length; i++) {
  if (table[bitstream[i]]) {
    // here comes the code which checks if there is really a match
  }
}

由于256个表项中最多有8个不是零,因此平均而言,您只需仔细查看每个第32个位置。只有对于这个字节(加上前一个字节和后一个字节),您才能使用位操作或reinier建议的一些掩蔽技术来查看是否存在匹配。

代码假定您使用小的尾端字节顺序。字节中位的顺序也可能是一个问题(每个已经实现CRC32校验和的人都知道)。

alt text http://img70.imageshack.us/img70/8711/80541519.jpg

在这里,在第一个样本中检查1到8,在下一个样本中检查9到16,依此类推。现在当我们正在寻找一个 图案 ,我们将找到本协议的所有8种可能的安排(如下所示) 图案

正在初始化查找表:

让我们举个例子 0111011101110111 作为一个 找到。现在考虑第四种排列方式。左边的部分是 XXX01110 . 按左部分填充左查找表的所有图纸( )与 00010000 . 1表示输入排列的起始位置 图案 . 因此,左查找表后面的8个RAW将由16填充( 00010000 ).

00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110

安排的中间部分是 11101110 ).

111XXXXX . 带索引的所有RAW(32个RAW) 111XXXXX 将于16日前填补空缺( 00010000 ).

XX011101 在左查找表和 11101110 在中间查找表和 111XXXXX 00100010 按第七种安排。

搜索模式:

计数 如下所示: 左边 是左查找表, 是中间查找表和 正当 是右查找表。

Count = Left[Byte0] & Middle[Byte1] & Right[Byte2];

计数 图案

我可以给出一些经过测试的示例代码。

    for( RightShift = 0; RightShift < 8; RightShift++ )
    {
        LeftShift = 8 - RightShift;

        Starting = 128 >> RightShift;

        Byte = MSB >> RightShift;

        Count = 0xFF >> LeftShift;

        for( i = 0; i <= Count; i++ )
        {
            Index = ( i << LeftShift ) | Byte;

            Left[Index] |= Starting;
        }

        Byte = LSB << LeftShift;

        Count = 0xFF >> RightShift;

        for( i = 0; i <= Count; i++ )
        {
            Index = i | Byte;

            Right[Index] |= Starting;
        }

        Index = ( unsigned char )(( Pattern >> RightShift ) & 0xFF );

        Middle[Index] |= Starting;
    }

搜索模式:

数据 左边 中间的 是中间查找表和 正当 是右查找表。

for( int Index = 1; Index < ( StreamLength - 1); Index++ )
{
    Count = Left[Data[Index - 1]] & Middle[Data[Index]] & Right[Data[Index + 1]];

    if( Count )
    {
        TotalCount += GetNumberOfOnes( Count );
    }
}

限制:

图案 如果它被放置在流缓冲区的最末端。以下代码需要在循环后添加以克服此限制。

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

优点:

这个算法只需要 N-1 找到目标的逻辑步骤 图案 N

我有钱 Knuth-Morris-Pratt 带有两个字符的字母表。

我将实现一个具有16个状态的状态机。

每个状态表示有多少接收位符合模式。如果下一个接收的位与模式的下一位一致,则机器进入下一个状态。如果情况并非如此,则机器返回到第一个状态(或者,如果模式的开头可以与较小数量的接收位匹配,则返回到另一个状态)。

原子小鼠

• Knuth-Morris-Pratt

看起来不错,直到我考虑了Luke和MSalter关于详细信息的要求。

事实证明,这些细节可能表明一种比KMP更快的方法。KMP文章链接到

• Boyer Moore

对于搜索模式为“AAAAA”的特定情况。对于多模式搜索

• Rabin-Karp

可能最合适。

您可以找到进一步的介绍性讨论 here .

我要做的是创建16个前缀和16个后缀。然后为每个16位输入块确定最长后缀匹配。如果下一个块的前缀匹配长度,那么就得到了一个匹配 (16-N)

后缀匹配实际上不需要16个比较。但是,这需要根据模式字进行预计算。例如,如果patternword是101010101010101010,则可以首先测试16位输入块的最后一位。如果该位为0,则只需测试…10101010即可。如果最后一位是1,则需要测试…1010101是否足够。每个都有8个,总共1+8个比较。如果patternword是1111110000,您仍然需要测试输入的最后一位是否匹配后缀。如果该位为1,则必须进行12个后缀匹配(regex:1{1,12}),但如果为0,则只有4个可能的匹配(regex 1111 1111 1111 0{1,4}),同样平均进行9次测试。添加 16-N 前缀匹配,您可以看到每16位块只需要10次检查。

unsigned int const pattern = pattern to search for
unsigned int accumulator = first three input bytes

do
{
  bool const found = ( ((accumulator   ) & ((1<<16)-1)) == pattern )
                   | ( ((accumulator>>1) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>2) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>3) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>4) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>5) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>6) & ((1<<16)-1)) == pattern );
                   | ( ((accumulator>>7) & ((1<<16)-1)) == pattern );
  if( found ) { /* pattern found */ }
  accumulator >>= 8;

  unsigned int const data = next input byte
  accumulator |= (data<<8);
} while( there is input data left );

任何 O(n logn)时间内的位模式。计算位掩码与输入的互相关。大小分别为n和n'的序列x和掩模y的互相关定义如下:

R(m) = sum  _ k = 0 ^ n' x_{k+m} y_k

然后出现与掩码完全匹配的位模式,其中R(m)=Y,其中Y是位掩码中的位模式之和。

因此,如果您试图匹配位模式

[0 0 1 0 1 0]

[ 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1]

那你必须用面具

[-1 -1  1 -1  1 -1]

可以在O(n logn)时间内使用FFT实现互相关。

一种更简单的实现方法 @Toad's simple brute-force algorithm that checks every bit-position 是将数据移动到位,而不是移动掩码。不需要任何数组,只需右移就可以了 combined >>= 1 uint16_t .)

(在多个问题中,我注意到创建一个掩码的效率往往低于仅仅移出不需要的位。)

(正确处理 uint16\u t

// simple brute-force scalar version, checks every bit position 1 at a time.
long bitstream_search_rshift(uint8_t *buf, size_t len, unsigned short pattern)
{
        uint16_t *bufshort = (uint16_t*)buf;  // maybe unsafe type punning
        len /= 2;
        for (size_t i = 0 ; i<len-1 ; i++) {
                //unsigned short curWord = bufshort[i];
                //unsigned short prevWord = bufshort[i+1];
                //int combinedWords = (prevWord<<16) + curWord;

                uint32_t combined;                                // assumes little-endian
                memcpy(&combined, bufshort+i, sizeof(combined));  // safe unaligned load

                for(int bitpos=0; bitpos<16; bitpos++) {
                        if( (combined&0xFFFF) == pattern)     // compiles more efficiently on e.g. old ARM32 without UBFX than (uint16_t)combined
                                return i*16 + bitpos;
                        combined >>= 1;
                }
        }
        return -1;
}

这相当重要 更多 对于大多数ISA(如x86、AARC64和ARM),从具有最新gcc和clang的阵列加载掩码的效率要高于从阵列加载掩码的效率。

编译器将循环完全展开16倍,因此可以将位字段提取指令与立即操作数(如ARM)一起使用 ubfx PowerPC rwlinm 旋转左+立即掩码(位范围),将16位提取到32位或64位寄存器的底部,在那里可以进行常规比较和分支。实际上并没有一个右移1的依赖链。

在x86上,CPU可以进行忽略高位的16位比较,例如。 cmp cx,dx 右移后 combined 在里面 edx

某些ISA的一些编译器在@Toad版本上的工作与此一样出色,例如,PowerPC的clang使用 rlwinm 屏蔽16位范围的 合二为一 使用immediates,它将所有16个预移位模式值保留在16个寄存器中,因此无论哪种方式,不管rlwinm是否具有非零旋转计数,都只是rlwinm/compare/branch。但是右移版本不需要设置16个tmp寄存器。 https://godbolt.org/z/8mUaDI

AVX2蛮力

有(至少)两种方法可以做到这一点:

• 广播单个dword,并在继续之前使用可变移位检查其所有位位置。可能很容易找到匹配的位置。(如果你想的话,可能不太好 所有匹配项。)
• 向量加载,并并行迭代多个数据窗口的位位置。可以使用从相邻字(16位)开始的未对齐加载来重叠奇偶向量,以获得dword(32位)窗口。否则,您将不得不在128位通道上随机移动,最好是16位粒度,这将需要2条没有AVX512的指令。

使用64位元素移位而不是32位,我们可以检查多个相邻的16位窗口,而不是总是忽略上16位(其中零被移入)。但我们仍然在SIMD元素边界处有一个中断,零被移入,而不是来自更高地址的实际数据。(未来的解决方案:AVX512VBMI2双移位 VPSHRDW ,是的SIMD版本 SHRD .)

也许这样做是值得的,然后再来看看我们在一个数组中每个64位元素顶部遗漏的4x 16位元素 __m256i . 可能是将多个向量的剩余部分组合起来。

// simple brute force, broadcast 32 bits and then search for a 16-bit match at bit offset 0..15

#ifdef __AVX2__
#include <immintrin.h>
long bitstream_search_avx2(uint8_t *buf, size_t len, unsigned short pattern)
{
    __m256i vpat = _mm256_set1_epi32(pattern);

    len /= 2;
    uint16_t *bufshort = (uint16_t*)buf;
    for (size_t i = 0 ; i<len-1 ; i++) {
        uint32_t combined; // assumes little-endian
        memcpy(&combined, bufshort+i, sizeof(combined));  // safe unaligned load
        __m256i v = _mm256_set1_epi32(combined);
//      __m256i vlo = _mm256_srlv_epi32(v, _mm256_set_epi32(7,6,5,4,3,2,1,0));
//      __m256i vhi = _mm256_srli_epi32(vlo, 8);

        // shift counts set up to match lane ordering for vpacksswb

        // SRLVD cost: Skylake: as fast as other shifts: 1 uop, 2-per-clock
        // * Haswell: 3 uops
        // * Ryzen: 1 uop, but 3c latency and 2c throughput.  Or 4c / 4c for ymm 2 uop version
        // * Excavator: latency worse than PSRLD xmm, imm8 by 1c, same throughput. XMM: 3c latency / 1c tput.  YMM: 3c latency / 2c tput.  (http://users.atw.hu/instlatx64/AuthenticAMD0660F51_K15_BristolRidge_InstLatX64.txt)  Agner's numbers are different.
        __m256i vlo = _mm256_srlv_epi32(v, _mm256_set_epi32(11,10,9,8,    3,2,1,0));
        __m256i vhi = _mm256_srlv_epi32(v, _mm256_set_epi32(15,14,13,12,  7,6,5,4));

        __m256i cmplo = _mm256_cmpeq_epi16(vlo, vpat);  // low 16 of every 32-bit element = useful
        __m256i cmphi = _mm256_cmpeq_epi16(vhi, vpat);

        __m256i cmp_packed = _mm256_packs_epi16(cmplo, cmphi); // 8-bit elements, preserves sign bit
        unsigned cmpmask = _mm256_movemask_epi8(cmp_packed);
        cmpmask &= 0x55555555;  // discard odd bits
        if (cmpmask) {
            return i*16 + __builtin_ctz(cmpmask)/2;
        }
    }
    return -1;
}
#endif

这对于通常很快找到命中的搜索非常有用,尤其是在少于前32字节的数据中。这对于大型搜索来说并不坏(但仍然是纯粹的暴力,一次只检查一个单词),在Skylake上可能并不比并行检查多个窗口的16个偏移量差。

这是对SkyLink的调整,在其他CPU上,变量移位效率较低,你可能只考虑偏移量为1…7的7个变量移位,然后通过移位来创建偏移量8。15。或者完全是别的什么。

with gcc/clang (on Godbolt) ,具有直接从内存进行广播的内部循环。(优化 memcpy set1() 变成一个 vpbroadcastd )

导栓连杆上还包括一个测试 main 它在一个小数组上运行。(自上次调整后,我可能没有进行过测试,但我在早些时候进行了测试,packing+bit-scan的东西确实有效。)

## clang8.0  -O3 -march=skylake  inner loop
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
        vpbroadcastd    ymm3, dword ptr [rdi + 2*rdx]   # broadcast load
        vpsrlvd ymm4, ymm3, ymm1
        vpsrlvd ymm3, ymm3, ymm2             # shift 2 ways
        vpcmpeqw        ymm4, ymm4, ymm0
        vpcmpeqw        ymm3, ymm3, ymm0     # compare those results
        vpacksswb       ymm3, ymm4, ymm3     # pack to 8-bit elements
        vpmovmskb       ecx, ymm3            # scalar bitmask
        and     ecx, 1431655765              # see if any even elements matched
        jne     .LBB0_4            # break out of the loop on found, going to a tzcnt / ... epilogue
        add     rdx, 1
        add     r8, 16           # stupid compiler, calculate this with a multiply on a hit.
        cmp     rdx, rsi
        jb      .LBB0_2                    # } while(i<len-1);
        # fall through to not-found.

这是8 uops的工作量+3 uops的循环开销(假设and/jne和cmp/jb的宏融合,我们将在Haswell/Skylake上得到)。在AMD上,256位指令是多个UOP,这将更加复杂。

当然,也可以使用纯右移立即将所有元素移动1,然后 并行检查多个窗口 而不是同一窗口中的多个偏移。

没有有效的可变移位(尤其是根本没有AVX2) ,这对于大型搜索来说会更好,即使它需要更多的工作来确定第一次点击的位置,以防出现 是 成功。(在找到最低元素以外的某个命中后,需要检查所有早期窗口的所有剩余偏移。)

也许你应该在一个向量(vec_str)中流入你的比特流,在另一个向量(vec_pattern)中流入你的模式,然后像下面的算法那样做

i=0
while i<vec_pattern.length
    j=0
    while j<vec_str.length
            if (vec_str[j] xor vec_pattern[i])
                i=0
                j++

(希望算法正确)

void find_matches(unsigned char* sequence, int n_sequence, unsigned short pattern) {
    if (n_sequence < 2)
        return; // 0 and 1 byte bitstring can't match a short

    // Calculate a lookup table that shows for each byte at what bit offsets
    // the pattern could match.
    unsigned int match_offsets[256];
    for (unsigned int in_byte = 0; in_byte < 256; in_byte++) {
        match_offsets[in_byte] = 0xFF;
        for (int bit = 0; bit < 24; bit++) {
            match_offsets[in_byte] <<= 1;
            unsigned int mask = (0xFF0000 >> bit) & 0xFFFF;
            unsigned int match_location = (in_byte << 16) >> bit;
            match_offsets[in_byte] |= !((match_location ^ pattern) & mask);
        }
    }

    // Go through the input 2 bytes at a time, looking up where they match and
    // anding together the matches offsetted by one byte. Each bit offset then
    // shows if the input sequence is consistent with the pattern matching at
    // that position. This is anded together with the large offsets of the next
    // result to get a single match over 3 bytes.
    unsigned int curr, next;
    curr = 0;
    for (int pos = 0; pos < n_sequence-1; pos+=2) {
        next = ((match_offsets[sequence[pos]] << 8) | 0xFF) & match_offsets[sequence[pos+1]];
        unsigned short match = curr & (next >> 16);
        if (match)
            output_match(pos, match);
        curr = next;
    }
    // Handle the possible odd byte at the end
    if (n_sequence & 1) {
        next = (match_offsets[sequence[n_sequence-1]] << 8) | 0xFF;
        unsigned short match = curr & (next >> 16);
        if (match)
            output_match(n_sequence-1, match);
    }
}

void output_match(int pos, unsigned short match) {
    for (int bit = 15; bit >= 0; bit--) {
        if (match & 1) {
            printf("Bitstring match at byte %d bit %d\n", (pos-2) + bit/8, bit % 8);
        }
        match >>= 1;
    }
}

这个循环的主循环有18条指令长,每次迭代处理2个字节。如果安装成本不是一个问题,那么这应该是最快的。