零填充缓冲区/文件的CRC32计算 [英] CRC32 Calculation for Zero Filled Buffer/File

问题描述

如果我想为大量连续的零字节计算CRC32值，给定零位游程的长度，是否可以使用恒定时间公式？例如，如果我知道我的1000个字节全部填充了零，是否有一种方法可以避免循环进行1000次迭代（仅举一个例子，为解决这个问题，实际的零个数是无界的）？

If I want to calculate the CRC32 value for a large number of consecutive zero bytes, is there a constant time formula I can use given the length of the run of zeros? For example, if I know I have 1000 bytes all filled with zeros, is there a way to avoid a loop with 1000 iterations (just an example, actual number of zeros is unbounded for the sake of this question)?

推荐答案

您可以计算应用 n 零的结果不是在O（1）时间内，而是在O（log n ）时间。这是在zlib的 crc32_combine（）中完成的。构建二进制矩阵，该二进制矩阵表示将单个零位应用于CRC的操作。 32x32矩阵将GF（2）上的32位CRC相乘，其中加法被异或（^）取代，乘法被和（&）一点一点地取代。

You can compute the result of applying n zeros not in O(1) time, but in O(log n) time. This is done in zlib's crc32_combine(). A binary matrix is constructed that represents the operation of applying a single zero bit to the CRC. The 32x32 matrix multiplies the 32-bit CRC over GF(2), where addition is replaced by exclusive-or (^) and multiplication is replaced by and (&), bit by bit.

然后可以对矩阵求平方以得到两个零的运算符。求平方得到四个零。第三个平方被平方以得到八个零的运算符。

Then that matrix can be squared to get the operator for two zeros. That is squared to get the operator for four zeros. The third one is squared to get the operator for eight zeros. And so on as needed.

现在，可以基于数量为零的 n 中的一位将运算符集应用于CRC。

Now that set of operators can be applied to the CRC based on the one bits in the number n of zero bits that you want to compute the CRC of.

如果您碰巧知道自己将经常精确地应用确切的频率，则可以为任意数量的零位预先计算所得的矩阵运算符。那么多的零。那么它只是一个矩阵乘以一个向量，实际上就是O（1）。

You can precompute the resulting matrix operator for any number of zero bits, if you happen to know you will be frequently applying exactly that many zeros. Then it is just one matrix multiplication by a vector, which is in fact O(1).

您不需要使用 pclmulqdq 指令在此处的另一个答案中建议，但是如果有的话，那会更快一些。不会更改操作的O（）。

You do not need to use the pclmulqdq instruction suggested in another answer here, but that would be a little faster if you have it. It would not change the O() of the operation.

这篇关于零填充缓冲区/文件的CRC32计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！