2

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

我有许多 128 位块，并希望查看它们是否与 1 的数量等于 0 的数量的模式匹配，例如 010101 .... 或 00110011 ... 或 0000111100001111 ... 但不是 001001001。 ..

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

010101... 情况很简单，就是 0xAAAA... 或 0x5555.... 但是随着模式变长，排列变长。目前我使用重复移位值，例如这个问题中概述的最快的方法来扫描位流中的位模式，但更快的方法会很好，因为我在这个例程中花费了所有 CPU 的 70%。其他海报有针对一般情况的解决方案，但我希望我的模式的对称性质可能会带来更优化的东西。

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

完美解决方案的其他限制条件是汇编指令数量少，没有非常随机的内存访问（即，大彩虹表并不理想）。

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

我最感兴趣的是 0011 和 0000,1111 和 0000,0000,1111,1111 和 16 个零/一和 32 个零/一（逗号仅供阅读）的模式，其中每个模式在 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。

4

4 回答 4

2

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

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;

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

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

于 2013-03-22T02:06:05.320 回答
1

这类问题的通用解决方案是为模式创建一个好的散列函数，并将每个模式存储在一个散列图中。一旦为模式创建了哈希映射，然后尝试使用输入流在表中查找。我还没有代码，但如果你对代码感到震惊，请告诉我。请发布它，我可以处理它。

于 2013-03-22T02:38:14.017 回答
1

模式在 128 个流中自我重复的限制使得组合的数量受到限制，并且序列将具有易于检查的属性：

需要反复检查高低部分是否相同；如果它们是相反的，请检查该特定长度是否包含连续的长度。

 8-bit repeat at offset 3:  00011111 11100000 00011111 11100000
 ==> high and low 16 bits are the same
 00011111 11100000 ==> high and low parts are inverted.
 Not same, nor inverted means rejection of pattern.

在这一点上，需要检查是否有一系列的 - 在左侧添加“1”并检查它是否是 2 的幂：n==(n & -n) 是教科书的检查。

于 2013-03-22T05:28:42.837 回答
1

我考虑过制作一个状态机，所以每个下一个字节（16 个字节中）都会推进它的状态，并且在大约 16 个状态转换之后，你就会识别出模式。但这看起来不太有希望。数据结构和逻辑看起来更复杂。

相反，为什么不预先计算所有这 126 个模式（从 01 到 32 个零 + 32 个），对它们进行排序并执行二进制搜索？这会给你最多 7 次二进制搜索迭代。而且您不需要存储每个模式的所有 16 个字节，因为它的一半是相同的。这为您提供了 126*16/2=1008 字节的模式数组。您还需要每个模式 2 个字节来存储零（一）次运行的长度以及相对于您认为未移位的任何模式的移位。也就是一共126*(16/2+2)=1260字节的数据（对数据缓存应该是温和的）和非常简单微小的二分查找算法。基本上，它只是对您在问题中提到的答案的改进。

您可能想在 4-5 次二进制搜索迭代后尝试切换到线性搜索。这可能会对整体算法产生一点推动作用。

最终，获胜者由测试/分析决定。这就是您应该做的，获得一些实现并在真实系统中的真实数据上进行比较。

于 2013-03-22T05:58:12.783 回答