大多数静态数据流的 CRC 计算

背景：

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

问题：

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

CRC_WHOLE = XOR(CRC_A, CRC_B)

我知道这个公式不起作用（尝试过），但我希望存在类似的东西。

是的。你可以看到如何在zlib's crc32_combine()。如果有两个序列 A 和 B，则 AB 的纯 CRC 是 A0 的 CRC 和 0B 的 CRC 的异或，其中 0 代表一系列零字节以及相应序列的长度，即 B和 A 分别。

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

Update:

这是我 2008 年发表的一篇文章，其中包含 @ArtemB 发现的详细解释（我已经忘记了）：

crc32_combine()zlib 中的方法基于两个关键技巧。对于接下来的内容， 我们不考虑标准 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 连接。 因此，如果我们简单地通过并置来表示串联 符号，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)，然后通过它运行长度(B) 零。那么我们就可以 与 CRC(B) = CRC(0B) 进行异或，我们得到 我们想要的是 CRC(Z) = CRC(AB)。瞧！

好吧，实际上瞧现在还为时过早。我一点都不满意 那个答案。我不想进行需要时间的计算 与 B 的长度成正比。相比之下，这不会节省任何时间 只需将寄存器设置为 CRC(A) 并运行 B 流 通过。我认为必须有一种更快的方法来计算效果 喂养的nCRC 机器中的零（其中n= 长度(B))。所以 这导致我们：

技巧#2：CRC 机是一个线性状态机。如果我们知道 当我们向机器输入零时发生线性变换， 然后我们可以更有效地对该转换进行操作 找到喂养所产生的转化n零入 机器。

将单个零位送入 CRC 机的改造 完全由32x32的二进制矩阵表示。要应用 变换我们将矩阵乘以寄存器，取 寄存器为 32 位列向量。对于矩阵乘法 二进制（即在 2 的伽罗瓦域上），乘法的作用 由and'ing扮演，加法的角色由exclusive-扮演 或'ing。

有几种不同的方法来构建魔法矩阵 表示向 CRC 机器馈送 a 所引起的转变 单个零位。一种方法是观察矩阵的每一列 是当你的寄存器以一个开始时你得到的 它。所以第一列是当寄存器为 100 时你得到的...... 然后输入一个零，第二列来自于 0100...等（这些被称为基向量。）你可以看到 只需与这些向量进行矩阵乘法即可。 矩阵乘法选择矩阵的列 对应单个位置。

现在来说说技巧。一旦我们有了魔法矩阵，我们就可以搁置 初始寄存器内容一段时间，而是使用 一个零的变换来计算变换n零。我们可以乘以n矩阵的副本一起得到 矩阵为n零。但这比仅仅运行更糟糕n通过机器归零。然而，有一个简单的方法可以避免大多数 这些矩阵乘法得到相同的答案。假设我们 想知道运行八个零位或一个的转换 字节通过。让我们把代表运行的魔法矩阵称为 零到：M。我们可以进行七次矩阵乘法来得到 R = MxMxMxMxMxMxMxM。相反，让我们从 MxM 开始并将其称为 P。然后 PxP 是 MxMxMxM。我们称其为 Q。那么 QxQ 就是 R。所以现在我们已经 将七次乘法减少为三次。 P = MxM，Q = PxP，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是二进制表示中的个数n， 然后我们 只是有j- 多 1 次矩阵乘法。所以我们总共有k

• j- 1 次矩阵乘法，其中j <= k= 地板（logbase2（n)).

现在我们将快速构建的矩阵n零，并相乘 通过 CRC(A) 得到 CRC(A0)。我们可以在 O(log(n)) 中计算 CRC(A0) 时间，而不是 O(n) 时间。我们排除或与 CRC(B) 和 瞧！ （真的，这一次），我们有 CRC(Z)。

这就是 zlib 的crc32_combine() does.

我将把它作为如何处理的练习留给读者 CRC 寄存器的预处理和后处理。你只需要 应用上面的线性观察。提示：你不需要知道 长度（A）。实际上crc32_combine()仅需要三个参数： CRC(A)、CRC(B) 和长度(B)（以字节为单位）。