问CRC计算约简

EN

取初始的1024字节块A和新的1024字节块B排它，或者它们得到块C。因为你只改变了四个字节，C将是一串零，四个字节是排他性的，或者是前一个和新的四个字节，还有一串更多的零。

现在计算C块的CRC-16，但不需要任何预处理或后处理。我们称之为CRC-16‘。(我需要看看具体的CRC-16，如果有的话，你用它来看那个处理是什么。)A区的CRC-16与C区的CRC-16‘是排他性的--或CRC-16，现在你有区块B的CRC-16。

乍一看，与仅仅计算块B的CRC相比，这似乎不是很大的收获。然而，快速计算一堆零的CRC是有窍门的。首先，更改的四个字节之前的零给出一个CRC-16‘值为零，不管有多少个零。因此，您只需开始计算CRC-16‘的排他性-或以前的和新的四个字节。

现在，在更改字节之后，继续计算剩余n个零上的CRC-16‘。通常，计算n个字节上的CRC需要O(n)时间。但是，如果您知道它们都是零(或所有一些常量值)，则可以在O(log )时间内计算。您可以看到在 routine中如何这样做的示例，并将其应用于您的CRC。

给定您的CRC-16/DNP参数，下面的zeros()例程将在O(log )时间内将所请求的零字节数应用于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);
}

儿童权利委员会实际上使这是一件容易的事情。

在研究这个问题时，我相信你已经开始读到CRCs是用GF(2)上的多项式计算的，并且可能跳过了这一部分，得到了立即有用的信息。好吧，听起来好像是时候让你重温一下这些东西，然后再读几遍，这样你才能真正理解它。

但不管怎样..。

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

所以你可以做的第一个简化就是，你只需要计算改变比特的CRC。实际上，您可以预先计算块中每个位的CRCs，这样当您更改一个位时，您就可以将它的CRC转换为块的CRC。

CRCs还具有CRC(A * B) = CRC(A * CRC(B))的性质，其中*是GF(2)上的多项式乘法。如果在结束时将块填充为零，则不要对CRC(B)这样做。

这使您可以使用一个较小的预先计算的表。“GF(2)上的多项式乘法”是二进制卷积，因此乘以1000等于移位3位。使用此规则，您可以预先计算每个字段的偏移量的CRC值。然后，只需将改变的位乘以偏移CRC (没有零填充计算)，计算这8位位的CRC值，然后将它们转到块CRC中。

p说，CRC是输入流形成的长整数的剩余部分，以及对应于多项式的短整数。

如果你在中间改变了一些位，这就相当于n 2^k对分红的扰动，其中n有扰动段的长度，k是后面的位数。

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

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

第一个因素就是CRC16 of n。利用基于方阵的幂算法可以有效地获得Log k运算中的另一个因子。