algorithm - 零填充缓冲区/文件的 CRC32 计算

Question

如果我想计算大量连续零字节的 CRC32 值，是否可以使用给定零运行长度的常数时间公式？例如，如果我知道我有 1000 个字节全部用零填充，是否有办法避免 1000 次迭代的循环(只是一个例子，为了这个问题，零的实际数量是无限的)？

Answer 1

您可以在 O(log n) 时间而不是 O(1) 时间内计算应用 n 个零的结果。这是在 zlib 的 crc32_combine() 中完成的。构造一个二进制矩阵，表示将单个零位应用于 CRC 的操作。 32x32 矩阵将 32 位 CRC 与 GF(2) 相乘，其中加法由异或 (^) 代替，乘法由与 (&) 逐位代替。

然后可以对该矩阵求平方以获得两个零的运算符。将其平方以获得四个零的运算符。第三个是平方以获得八个零的运算符。依此类推。

现在可以根据要计算其 CRC 的 n 个零位中的一位将这组运算符应用于 CRC。

您可以为任意数量的零位预先计算生成的矩阵运算符，如果您碰巧知道您将经常应用那么多的零。然后它只是一个矩阵乘以一个向量，实际上是 O(1)。

您不需要使用此处另一个答案中建议的 pclmulqdq 指令，但如果您有它，那会更快一些。它不会改变操作的 O()。