大部分静态数据流的CRC计算 [英] CRC Calculation Of A Mostly Static Data Stream

问题描述

背景：

我有一部分内存，1024字节。最后的1020个字节将始终相同。前4个字节将更改（产品的序列号）。我需要为整个内存段计算 CRC-16 CCITT （0xFFFF起始，0x1021掩码）， code> CRC_WHOLE 。

问题：

是否可能仅计算前4个字节的CRC， CRC_A ，然后应用下面的函数来计算完整的CRC？我们可以假定最后1020个字节的校验和 CRC_B 是已知的。

  CRC_WHOLE = XOR（CRC_A，CRC_B）
  

我知道此公式无效（尝试过），但我希望存在类似的东西。

解决方案

是。您可以在 zlib 的 crc32_combine（）中查看。如果您有两个序列A和B，则AB的纯CRC是A0的CRC与0B的CRC的异或，其中0表示一系列零字节，具有相应序列的长度，即B

对于您的应用程序，您可以预先计算一个运算符，该运算符可以非常快速地将1020个零应用于前四个字节的CRC。然后，您可以使用预先计算的1020字节CRC进行异或运算。

更新：

这是我的2008年文章，其中有@ArtemB发现的详细解释（我忘了）：

<$ c $ zlib中的c> crc32_combine（）基于两个关键技巧。对于以下内容，
搁置了一个事实，即标准的32位CRC在
之前和之后进行了处理。我们可以稍后处理。现在假设CRC的
没有这样的条件，因此从填充有
零的寄存器开始。

技巧＃1：CRC是线性的。因此，如果您有
的流X和Y相同的长度，并且互斥或两个流逐位获得Z，则
即Z = X ^ Y（使用C表示独占-或），则CRC（Z）=
CRC（X）^ CRC（Y）。对于当前的问题，我们有两个不同长度的流A和B
，我们希望将它们连接到流Z中。我们可以使用的
是CRC（A）和CRC（B）。我们想要的是一种快速的方法
计算CRC（Z）。诀窍是构造X = A与
的length（B）零位串联，Y = length（A）零位的B串联。
因此，如果我们简单地通过$ b的并置来表示串联$ b符号，X = A0，Y = 0B，然后X ^ Y = Z = AB。然后我们有CRC（Z）=
CRC（A0）^ CRC（0B）。

现在我们需要知道CRC（A0）和CRC（0B ）。 CRC（0B）很简单。如果我们以零开头将
一堆零送入CRC机器，寄存器
仍将填充零。好像我们什么也没做。
因此，CRC（0B）= CRC（B）。

CRC（A0）需要更多工作。取一个非零的CRC并将
的零送入CRC机器并不孤单。每个零都会改变
的寄存器内容。因此，要获得CRC（A0），我们需要将寄存器
设置为CRC（A），然后将length（B）的值设为0。然后我们可以对
进行异或运算，或者将其结果与CRC（B）= CRC（0B），得到所需的
，即CRC（Z）= CRC（AB）。瞧！

嗯，实际上瞧是不成熟的。我对
的答案完全不满意。我不希望计算花费的时间
与B的长度成正比。与
相比，仅将寄存器设置为CRC（A）并运行B流$不会节省任何时间。 b $ b通过。我认为必须有一种更快的方法来计算将 n 个零送入CRC机器的效果
（其中 n = length（B））。因此
导致我们：

技巧＃2：CRC机器是线性状态机。如果我们知道在向机器输入零时发生的
线性变换，即
，那么我们可以对该变换进行运算以更有效地
查找由馈给导致的变换n 将零放入
机器中。

将单个零比特送入CRC机器
的转换完全由a表示32x32二进制矩阵。为了应用
变换，我们将矩阵乘以寄存器，将
寄存器作为32位列向量。对于
二进制的矩阵乘法（即在2的Galois字段上），乘法
的作用是and'ing，加法的作用是排他性-
或

有几种不同的构造魔术矩阵的方式，即
表示由CRC机给
一个零所引起的变换。一点。一种方法是观察矩阵
的每一列是从寄存器
中的单个寄存器开始时得到的结果。因此，第一列是在寄存器为100 ...
然后输入零时得到的结果，第二列从
0100 ...开始，以此类推（以此类推）。基本向量。）您可以简单地通过对这些向量进行矩阵乘法来看到
。
矩阵乘法选择与单个位置对应的矩阵
列。

现在该技巧了。一旦有了魔幻矩阵，我们就可以将
的初始寄存器内容留出一会儿，然后使用
转换为一个零来计算 n $ b的转换$ b零。我们可以将矩阵的 n 个副本相乘在一起，得到 n 个零的矩阵
。但这甚至比只在机器上运行 n
零更糟。但是，有一种简单的方法可以避免大多数
的矩阵乘法得到相同的答案。假设我们
想知道运行八个零位或一个
字节的转换。我们称魔术矩阵代表通过0运行一个
零：M。我们可以做七个矩阵乘法以获得R =
MxMxMxMxMxMxMxM。相反，让我们从MxM开始，并称其为P。然后
PxP是MxMxMxM。我们将其称为Q。然后QxQ为R。所以现在
将七个乘法减为三个。 P = MxM，Q = PxP，R =
QxQ。

现在，我敢肯定，您会想到任意n个零。我们
可以非常快速地生成转换矩阵M _k ，其中M _k 是运行2 ^{k 的
转换。 em>} 归零。 （在上面的
段落中，M ₃ 是R。）我们可以只用 k使M ₁ 到M _k
矩阵乘法，从M ₀ = M开始。 k 只需与
一样大，就可以 n 的二进制表示形式。我们可以
然后选择在 n 的二进制
表示形式中存在的那些矩阵，并将它们相乘得到运行 n <的
转换。 / em>通过CRC机为零。因此，如果 n =
13，计算M ₀ x M ₂ x M ₃ 。

如果 j 是 n 的二进制表示形式中的一个数字，则我们
仅具有 j -另外1个矩阵乘法。因此，我们总共有 k
+ j -1个矩阵乘法，其中 j < = k = floor（logbase2（ n ））。

现在，我们采用快速构造的 n 零矩阵，然后将
乘以CRC（A）得到CRC（A0）。我们可以在O（log（n））
时间而不是O（n）时间中计算CRC（A0）。我们与CRC（B）和
Voila互斥！ （这次是真的），我们有CRC（Z）。

这就是zlib的 crc32_combine（）的作用。 / p>

我将把它作为读者的练习，讨论如何在CRC寄存器的条件处理之前和之后处理
。您只需要
应用上面的线性观测值即可。提示：您不需要知道
的长度（A）。实际上， crc32_combine（）仅采用三个参数：
CRC（A），CRC（B）和length（B）（以字节为单位）。

Background:

I have a section of memory, 1024 bytes. The last 1020 bytes will always be the same. The first 4 bytes will change (serial number of a product). I need to calculate the CRC-16 CCITT (0xFFFF starting, 0x1021 mask) for the entire section of memory, CRC_WHOLE.

Question:

Is it possible to calculate the CRC for only the first 4 bytes, CRC_A, then apply a function such as the one below to calculate the full CRC? We can assume that the checksum for the last 1020 bytes, CRC_B, is already known.

CRC_WHOLE = XOR(CRC_A, CRC_B)

I know that this formula does not work (tried it), but I am hoping that something similar exists.

解决方案

Yes. You can see how in zlib's crc32_combine(). If you have two sequences A and B, then the pure CRC of AB is the exclusive-or of the CRC of A0 and the CRC of 0B, where the 0's represent a series of zero bytes with the length of the corresponding sequence, i.e. B and A respectively.

For your application, you can pre-compute a single operator that applies 1020 zeros to the CRC of your first four bytes very rapidly. Then you can exclusive-or that with the pre-computed CRC of the 1020 bytes.

Update:

Here is a post of mine from 2008 with a detailed explanation that @ArtemB discovered (that I had forgotten about):

crc32_combine() in zlib is based on two key tricks. For what follows, we set aside the fact that the standard 32-bit CRC is pre and post- conditioned. We can deal with that later. Assume for now a CRC that has no such conditioning, and so starts with the register filled with zeros.

Trick #1: CRCs are linear. So if you have stream X and stream Y of the same length and exclusive-or the two streams bit-by-bit to get Z, i.e. Z = X ^ Y (using the C notation for exclusive-or), then CRC(Z) = CRC(X) ^ CRC(Y). For the problem at hand we have two streams A and B of differing length that we want to concatenate into stream Z. What we have available are CRC(A) and CRC(B). What we want is a quick way to compute CRC(Z). The trick is to construct X = A concatenated with length(B) zero bits, and Y = length(A) zero bits concatenated with B. So if we represent concatenation simply by juxtaposition of the symbols, X = A0, Y = 0B, then X^Y = Z = AB. Then we have CRC(Z) = CRC(A0) ^ CRC(0B).

Now we need to know CRC(A0) and CRC(0B). CRC(0B) is easy. If we feed a bunch of zeros to the CRC machine starting with zero, the register is still filled with zeros. So it's as if we did nothing at all. Therefore CRC(0B) = CRC(B).

CRC(A0) requires more work however. Taking a non-zero CRC and feeding zeros to the CRC machine doesn't leave it alone. Every zero changes the register contents. So to get CRC(A0), we need to set the register to CRC(A), and then run length(B) zeros through it. Then we can exclusive-or the result of that with CRC(B) = CRC(0B), and we get what we want, which is CRC(Z) = CRC(AB). Voila!

Well, actually the voila is premature. I wasn't at all satisfied with that answer. I didn't want a calculation that took a time proportional to the length of B. That wouldn't save any time compared to simply setting the register to CRC(A) and running the B stream through. I figured there must be a faster way to compute the effect of feeding n zeros into the CRC machine (where n = length(B)). So that leads us to:

Trick #2: The CRC machine is a linear state machine. If we know the linear transformation that occurs when we feed a zero to the machine, then we can do operations on that transformation to more efficiently find the transformation that results from feeding n zeros into the machine.

The transformation of feeding a single zero bit into the CRC machine is completely represented by a 32x32 binary matrix. To apply the transformation we multiply the matrix by the register, taking the register as a 32 bit column vector. For the matrix multiplication in binary (i.e. over the Galois Field of 2), the role of multiplication is played by and'ing, and the role of addition is played by exclusive- or'ing.

There are a few different ways to construct the magic matrix that represents the transformation caused by feeding the CRC machine a single zero bit. One way is to observe that each column of the matrix is what you get when your register starts off with a single one in it. So the first column is what you get when the register is 100... and then feed a zero, the second column comes from starting with 0100..., etc. (Those are referred to as basis vectors.) You can see this simply by doing the matrix multiplication with those vectors. The matrix multiplication selects the column of the matrix corresponding to the location of the single one.

Now for the trick. Once we have the magic matrix, we can set aside the initial register contents for a while, and instead use the transformation for one zero to compute the transformation for n zeros. We could just multiply n copies of the matrix together to get the matrix for n zeros. But that's even worse than just running the n zeros through the machine. However there's an easy way to avoid most of those matrix multiplications to get the same answer. Suppose we want to know the transformation for running eight zero bits, or one byte through. Let's call the magic matrix that represents running one zero through: M. We could do seven matrix multiplications to get R = MxMxMxMxMxMxMxM. Instead, let's start with MxM and call that P. Then PxP is MxMxMxM. Let's call that Q. Then QxQ is R. So now we've reduced the seven multiplications to three. P = MxM, Q = PxP, and R = QxQ.

Now I'm sure you get the idea for an arbitrary n number of zeros. We can very rapidly generate transformation matrices M_k, where M_k is the transformation for running 2^k zeros through. (In the paragraph above M₃ is R.) We can make M₁ through M_k with only k matrix multiplications, starting with M₀ = M. k only has to be as large as the number of bits in the binary representation of n. We can then pick those matrices where there are ones in the binary representation of n and multiply them together to get the transformation of running n zeros through the CRC machine. So if n = 13, compute M₀ x M₂ x M₃.

If j is the number of one's in the binary representation of n, then we just have j - 1 more matrix multiplications. So we have a total of k + j - 1 matrix multiplications, where j <= k = floor(logbase2(n)).

Now we take our rapidly constructed matrix for n zeros, and multiply that by CRC(A) to get CRC(A0). We can compute CRC(A0) in O(log(n)) time, instead of O(n) time. We exclusive or that with CRC(B) and Voila! (really this time), we have CRC(Z).

That's what zlib's crc32_combine() does.

I will leave it as an exercise for the reader as to how to deal with the pre and post conditioning of the CRC register. You just need to apply the linearity observations above. Hint: You don't need to know length(A). In fact crc32_combine() only takes three arguments: CRC(A), CRC(B), and length(B) (in bytes).

这篇关于大部分静态数据流的CRC计算的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！