CRC计算减少

Question

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

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

1. 我采用完整的 1K block 电流 CRC16

2. 我在旧的 4 字节 block 上计算一些东西

3. 我从完整的 1K CRC16 中“减去”在步骤 2 中获得的内容

4. 我在新的 4 字节 block 上计算一些东西

5. 我将第 4 步获得的结果“添加”到第 3 步获得的结果

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

CRC(新-完整) = [CRC(旧-完整) - CRC( block -旧) + CRC( block -新)]

但我忽略了背后的数学原理以及如何获得此结果，同时还考虑了一个“通用公式”。

提前致谢。

Answer 1

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

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

乍一看，与仅计算 block 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);
}