c++ - 在 128 位的小流中找到重复的对称位模式

Question

如何快速扫描完全相等的重复二进制模式的 128 位组，例如 010101... 或 0011001100...？

我有一些 128 位的 block ，想看看它们是否匹配 1 的数量等于 0 的数量的模式，例如 010101.... 或 00110011... 或 0000111100001111... 但是不是 001001001...

问题是模式可能不会从它们的边界开始，所以模式 00110011.. 可能以 0110011... 开始，并且也会移动 1 位结束(注意 128 位不是循环的，所以开始不是加入到最后)

010101... 的情况很简单，它只是 0xAAAA... 或 0x5555...。但是随着模式变长，排列变长。目前我使用重复的移位值，例如这个问题 Fastest way to scan for bit pattern in a stream of bits 中概述的值但速度更快会更好，因为我在此例程中花费了所有 CPU 的 70%。其他张贴者有针对一般情况的解决方案，但我希望我的模式的对称性可能会带来更优化的结果。

如果有帮助，我只对最长 63 位的模式感兴趣，并且最感兴趣的是 2 种模式的力量(0101...00110011...0000111100001111...等)，而 5 个模式/存在 5 个零，这些非 2 次幂序列小于 0.1%，因此如果它有助于常见情况更快地进行，可以忽略。

完美解决方案的其他限制是汇编程序指令数量少，没有疯狂随机的内存访问(即大彩虹表不理想)。

编辑。更精确的图案细节。

我最感兴趣的模式是 0011 和 0000,1111 和 0000,0000,1111,1111 和 16zeros/ones 和 32 zeros/ones(逗号仅用于可读性)，其中每个模式在 128 位内连续重复。重复部分的长度不是 2、4、8、16、32 位的模式不那么有趣，可以忽略。 (例如 000111...)

扫描的复杂性在于模式可能从任何位置开始，而不仅仅是在 01 或 10 过渡处。因此，例如，以下所有内容都将匹配 00001111 的 4 位重复模式...(为了便于阅读，每第 4 位逗号)(省略号表示相同地重复)

0000,1111.... 或 0001,1110... 或 0011,1100... 或 0111,1000... 或 1111,0000... 或 1110,0001... 或 1100,0011。 .. 或 1000,0111

在 128 位中，需要重复相同的模式，出现两种不同的模式并不重要。例如，这不是一个有效的模式。 0000,1111,0011,0011... 因为我们已经从 4 位重复更改为 2 位重复。

我已经验证了 1 的个数是 64，这对于所有 2 的幂模式都是正确的，现在需要确定有多少位组成了重复模式 (2,4,8,16,32) 以及有多少位模式改变了。例如模式 0000,1111 是一个 4 位模式，移位 0。而 0111,1000... 是一个 4 位模式移位 3。

Answer 1

让我们从模式确实从边界开始的情况开始。您可以检查第一位并使用它来确定您的状态。然后开始遍历你的 block ，检查第一位，增加计数，左移并重复直到你发现你得到了相反的位。您现在可以使用此初始长度作为位集长度。将计数重置为 1，然后计算下一组相反的位。当你切换时，检查长度与初始长度，如果它们不相等则出错。这是一个快速函数 - 对于字符，它似乎按预期工作，并且扩展它以处理 32 字节的 block 应该不会太难。

unsigned char myblock = 0x33;
unsigned char mask = 0x80, prod = 0x00;
int setlen = 0, count = 0, ones=0;

prod = myblock & mask;
if(prod == 0x80)
  ones = 1;

for(int i=0;i<8;i++){
  prod = myblock & mask;
  myblock = myblock << 1;
  if((prod == 0x80 && ones) || (prod == 0x00 && !ones)){
    count++;
  }else{
    if(setlen == 0) setlen = count;
    if(count != setlen){
      printf("Bad block\n");
      return -1;
    }
    count = 1;
    ones = ( ones == 1 ) ? 0 : 1;
  }
}

printf("Good block of with % repeating bits\n",setlen);
return setlen;

现在要处理有偏移的 block ，我建议计算位数直到第一次“翻转”。存储这个数字，然后运行上面的例程，直到你找到最后一段，它的长度应该与其余的集合不相等。将初始位添加到最后一段的长度，然后您应该能够正确地将它与其余集合的大小进行比较。

这段代码非常小，通过缓冲区进行位移应该不需要 CPU 做太多工作。我很想知道这个解决方案最终与您当前的解决方案相比效果如何。