c++ - 替换少量字节时如何在大字节数组上重新计算 CRC32

Question

我有一个问题，我有一个大字节数组(通常 >1K 长度)作为输入，它具有计算的 CRC32。我需要用不同的值替换一小部分数组，然后重新计算 CRC。有没有一种有效的方法可以在不遍历整个原始字节数组的情况下执行此操作？我怀疑在数学上可以将原始 CRC、要替换的字节、新字节作为输入，并使用一种算法计算新的 CRC，该算法的循环大小只是要替换的字节数，但它超出了我的范围专业知识，因此，只是一个怀疑。谢谢，

Answer 1

是的，这是可以做到的。尽管在 1K 字节级别，重新计算整个事情的 CRC 很可能会更快。

正如 Dmitry Rubanovich 所指出的，您可以利用 CRC 是一个线性函数这一事实，其中加法被异或取代。然而，您可以做得更好，而不是仅仅避免重新计算直到第一次更改。只要你有一长串没有变化，这是两条消息的异或中的一长串零，你就可以在 O(log(n)) 时间而不是 O(n) 时间。

这样做的方法是生成一系列 32x32 位矩阵，每个矩阵代表将 2 的幂零字节应用于 CRC。例如。 1、2、4、8 等零字节。这可以提前完成，生成静态表。然后，例如，为了通过 137 个零演化 CRC，您将当前 CRC 作为位 vector 乘以 128、8 和 1 个零的矩阵。矩阵乘法在GF(2)之上，即用异或代替加法，用与运算代替乘法。

您可以在 zlib function for combining CRC's 中看到如何完成此操作的示例.

使用指令计数的快速计算表明，对于长度超过 300 字节的零字符串，对数方法的平均速度更快。