具有已知 CRC 的连接输入的 CRC

Question

如果我有子串 S ₀ , S ₁ , ... S _n与计算的 CRCs C ₀ , C ₁ , ... C _n，我是否能够确定连接输入 S ₀ S ₁的 CRC C _0...n ...S _n比线性处理整个字符串的效率要高得多？

显然， C _0...n = CRC(S _1...n，用 C ₀初始化)，但我想知道 C _0...n = f(C ₀ ,C ₁ ,... C _n ) 用于某些具有 O(n) 复杂度的 f() 而不是 O(|S ₀ S ₁ ...S _n |)。

Answer 1

是的。您可以crc32_combine()在zlib的实现中看到如何。它需要crc1、crc2和len2，其中len2是crc2计算块中的字节数。它需要 O(log( len2)) 时间。可以对以下块重复组合。

该方法是继续对CRC计算crc1，用以下的len2零个字节，然后异或crc2。的len2字节施加具有零操作被重复平方并应用于每个1比特len2，这允许O（日志（len2））执行时间。该例程于 2004 年添加到 zlib。