CRC计算减少

Question

我有一个关于 CRC 计算的数学和编程相关问题，以避免在您必须只更改块的一小部分时重新计算块的完整 CRC。

我的问题如下：我有一个 1K 块的 4 字节结构，每个结构代表一个数据字段。完整的 1K 块在末尾有一个 CRC16 块，在整个 1K 上计算。当我只需要更改一个 4 字节结构时，我应该重新计算整个块的 CRC，但我正在寻找更有效的解决方案来解决这个问题。某处：

我取全1K块电流CRC16
我在旧的 4 字节块上计算了一些东西
I "subtract" 在第 2 步从完整的 1K CRC16
我在新的 4 字节块上计算一些东西
我"add"步骤4得到的东西到步骤3得到的结果

总而言之，我正在考虑这样的事情：

CRC（新-完整）= [CRC（旧-完整）- CRC（块-旧）+ CRC（块-新）]

但我缺少背后的数学知识以及如何获得此结果，同时考虑 "general formula"。

提前致谢。

Answer 1

CRC取决于之前计算的数据的CRC。所以唯一的优化是，将数据逻辑分成 N 段，并为每个段存储计算出的 CRC 状态。

然后，例如修改第 6 段（0..9），获取第 5 段的 CRC 状态，并继续计算从第 6 段开始到 9 结束的 CRC。

不管怎样，CRC 计算还是很快的。所以想想，如果值得。

Answer 2

CRC 实际上使这件事变得容易。

在查看此内容时，我确定您已经开始阅读 CRC 是使用 GF(2) 上的多项式计算的，并且可能会跳过该部分以直接查看有用的信息。好吧，听起来你可能是时候回头看一遍那些东西并重读几次，这样你才能真正理解它。

但无论如何...

由于 CRC 的计算方式，它们有一个属性，给定两个块 A 和 B，CRC(A xor B) = CRC(A) xor CRC(B)

所以你可以做的第一个简化是你只需要计算改变位的CRC。您实际上可以预先计算块中每个位的 CRC，这样当您更改一点时，您可以将它的 CRC 异或到块的 CRC。

CRC 还具有属性即 CRC(A * B) = CRC(A * CRC(B))，其中 * 是 GF(2) 的多项式乘法。如果您在末尾用零填充块，则不要对 CRC(B) 执行此操作。

这样您就可以使用更小的预先计算的 table。 "Polynomial multiplication over GF(2)"是二进制卷积，所以乘以1000相当于移位3位。有了这个规则，就可以预先计算出每个字段的偏移量的CRC。然后只需将更改的位乘以（卷积）偏移量 CRC（计算时没有零填充），计算这 8 个字节的 CRC，并将它们异或到块 CRC。

Answer 3

CRC是由输入流形成的长整数和多项式对应的短整数的余数，比如p。

如果你改变中间的一些位，这相当于对被除数的扰动n 2^k，其中n是扰动部分的长度，k是数字接下来的位数。

因此，您需要计算余数的扰动，(n 2^k) mod p。您可以使用

来解决这个问题

(n 2^k) mod p = (n mod p) (2^k mod p)

第一个因素就是 n 的 CRC16。另一个因素可以通过基于平方的幂算法在 Log k 操作中有效地获得。

Answer 4

取初始的 1024 字节块 A 和新的 1024 字节块 B。异或它们得到块 C。因为你只更改了四个字节，C 将是一堆零，四个字节是前四个字节和新四个字节的异或，以及更多的零。

现在计算块 C 的 CRC-16，但不进行任何预处理或 post 处理。我们将其称为 CRC-16'。（我需要查看您正在使用的特定 CRC-16 以了解该处理是什么，如果有的话。）独占或块 A 的 CRC-16 与块 C 的 CRC-16'，您现在有区块 B 的 CRC-16

乍一看，与仅计算块 B 的 CRC 相比，这似乎没有太大的收获。但是，有一些技巧可以快速计算一堆零的 CRC。首先，更改的四个字节之前的零给出 CRC-16' 零，无论有多少个零。因此，您只需开始使用前四个字节和新四个字节的异或来计算 CRC-16'。

现在您继续计算更改字节后剩余的 n 个零的 CRC-16'。通常需要 O(n) 时间来计算 n 字节的 CRC。但是，如果您知道它们全为零（或全为某个常数值），则可以在 O(log n) 时间内计算出来。您可以在 zlib's crc32_combine() routine 中查看如何完成此操作的示例，并将其应用于您的 CRC。

给定您的 CRC-16/DNP 参数，下面的 zeros() 例程将在 O(log n) 时间内将请求的零字节数应用于 CRC .

// Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC
// polynomial, reflected. For speed, this requires that a not be zero.
uint16_t multmodp(uint16_t a, uint16_t b) {
    uint16_t m = (uint16_t)1 << 15;
    uint16_t p = 0;
    for (;;) {
        if (a & m) {
            p ^= b;
            if ((a & (m - 1)) == 0)
                break;
        }
        m >>= 1;
        b = b & 1 ? (b >> 1) ^ 0xa6bc : b >> 1;
    }
    return p;
}

// Table of x^2^n modulo p(x).
uint16_t const x2n_table[] = {
    0x4000, 0x2000, 0x0800, 0x0080, 0xa6bc, 0x55a7, 0xfc4f, 0x1f78,
    0xa31f, 0x78c1, 0xbe76, 0xac8f, 0xb26b, 0x3370, 0xb090
};

// Return x^(n*2^k) modulo p(x).
uint16_t x2nmodp(size_t n, unsigned k) {
    k %= 15;
    uint16_t p = (uint16_t)1 << 15;
    for (;;) {
        if (n & 1)
            p = multmodp(x2n_table[k], p);
        n >>= 1;
        if (n == 0)
            break;
        if (++k == 15)
            k = 0;
    }
    return p;
}

// Apply n zero bytes to crc.
uint16_t zeros(uint16_t crc, size_t n) {
    return multmodp(x2nmodp(n, 3), crc);
}

CRC计算减少

CRC calculation reduction

c

math

crc

crc16