（最有效的方式通过crc32校验和恢复字符串的一部分？

Question

存在一个字符串$ s（例如This is a test string. Just a test string. 123456. abcde），为其计算校验和crc32 $ c（e18032fa）。现在我们“丢失” $ s的1、2、3或4个连续字节。如何从损坏的字符串中重建原始字符串？

我的想法是“强行强制”，例如，如果缺少2个字节（显示为*）：

$input = 'This is a t**t string. Just a test string. 123456. abcde';
$input = explode('**', $input);
$part_before = $input[0];
$part_behind = $input[1];
for($i = 0; $i <= 255; $i++){
  for($ii = 0; $ii <= 255; $ii++){
    $word = $part_before.chr($i).chr($ii).$part_behind;
    if(hash('crc32b', $word) === $crc){
      return $word;
    }
  }
}

但是，特别是对于四个字节，这非常耗时。

还有更好的方法吗？我真的是这样。

感谢您的提前帮助。

Answer 1

如果前向crc包括左移，然后进行xor，然后反向循环涉及xor；如果lsb == 1，则进行右移。如果前向crc涉及一个右移，然后是xor，那么如果msb == 1，则反向循环涉及一个xor，然后是左移位。

[如果丢失的字节位置未知，则存在一个问题，充其量（取决于所使用的多项式），通常，CRC32单脉冲串校正通常限制为15位，而不是2个字节，并且仅当CRC多项式具有足够的1时才这样。位。但是，由于单个脉冲串仅限于字节边界，因此多项式和最大消息长度的组合可能允许两个字节的脉冲串校正。除了涉及在某个最大大小的消息中的任意字节边界上涉及两个字节模式的所有组合（否则为全零数组）的蛮力测试之外，我不知道如何证明这在特定情况下有效。对于带有pclmulqdq指令的X86（自2010年以来，大多数X86），使用pclmulqdq和xmm寄存器有一个基于汇编的非常快速的CRC生成器。