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

Question

背景：

我有一段内存，共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)

我知道这个公式不起作用(已经尝试过了)，但我希望存在类似的东西。

- mblem22

---

有一个技术解决方案，如下所述。但是考虑到所需的努力和产生的效益，这是否值得呢？与仅对1024字节进行直接CRC相比，您希望获得什么好处？ - Craig McQueen

Answer 1

是的。您可以在zlib的crc32_combine()中看到如何操作。如果有两个序列A和B，则AB的纯CRC是A0的CRC和0B的CRC的异或，其中0表示具有相应序列长度的零字节序列，即分别为B和A。

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

更新：

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

The crc32_combine() function in zlib utilizes two key tricks for computation. For now, we will disregard the fact that the standard 32-bit CRC is pre and post-conditioned. Let us assume that the CRC has no such conditioning and starts with a register filled with zeros.

Trick #1: CRCs are linear. If we have two streams of identical length, X and Y, and we perform an exclusive-or operation between the two bit-by-bit to get Z (i.e., Z = X ^ Y), then CRC(Z) = CRC(X) ^ CRC(Y). In this problem, we have two streams, A and B, which have different lengths, and we want to concatenate them into stream Z. We have access to CRC(A) and CRC(B) but need 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. Using simple juxtaposition to represent concatenation, X = A0 and Y = 0B. Thus, X^Y = Z = AB, and we can calculate CRC(Z) as CRC(A0) ^ CRC(0B).

现在我们需要知道CRC(A0)和CRC(0B)。计算CRC(0B)很容易。如果我们从零开始向CRC机器输入一堆零，那么寄存器仍然填满了零。所以就好像我们什么也没做。因此CRC(0B) = CRC(B)。

然而，计算CRC(A0)需要更多的工作。将零输入到非零CRC机器中并不会使其保持不变。每个零都会改变寄存器内容。因此，要获取CRC(A0)，我们需要将寄存器设置为CRC(A)，然后运行长度为B的零。然后我们可以将其结果与CRC(B) = CRC(0B)异或，得到我们想要的CRC(Z) = CRC(AB)。哇！

实际上，Voila还为时过早。我对那个答案一点也不满意。我不想要一个与B的长度成比例的计算。这与简单地将寄存器设置为CRC（A）并通过B流运行不节省时间。我想知道有更快的方法来计算将n个零输入到CRC机器中的效果（其中n = B的长度）。所以这就引导我们到：

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

将单个零位馈入CRC机器的变换完全由32x32二进制矩阵表示。要应用变换，我们将矩阵乘以寄存器，将寄存器作为32位列向量。对于二进制矩阵乘法（即在Galois Field of 2上），乘法的作用是and'ing，加法的作用是exclusive-or'ing。

有几种不同的方法可以构建表示输入单个零位给CRC机器所引起的转换的魔方阵。其中一种方法是观察魔方阵的每列，当您的寄存器以一个1位开始时，即可得到该列。因此，第一列是在寄存器为100...时并输入一个0所得到的，第二列来自于以0100...开头，等等（这些被称为基向量）。通过使用这些向量进行矩阵乘法便可轻松地看出这一点。矩阵乘法选择与单个1位置相对应的魔方阵列。

现在来介绍这个技巧。一旦我们有了魔术矩阵，我们就可以暂时搁置初始寄存器内容，而是使用一个零的变换计算n个零的变换。我们可以只是将矩阵的n份副本相乘以获得n个零的矩阵。但是，这甚至比直接运行n个零更糟糕。然而，有一种简单的方法可以避免大部分矩阵乘法，并获得相同的答案。假设我们想知道运行8个零位或一个字节所需的转换。让我们称代表运行一个零的神奇矩阵为M。我们可以进行七次矩阵乘法以获得R = MxMxMxMxMxMxMxM。相反，让我们从MxM开始，并将其称为P。然后PxP为MxMxMxM。让我们将其称为Q。然后QxQ为R。因此，现在我们将七次乘法减少到三次。P = MxM，Q = PxP，R = QxQ。

现在我确定你已经了解了任意数量的零的概念。 我们可以非常快速地生成变换矩阵M_k，其中M_k是运行2^k个零的转换。（在上面的段落中，M₃是R。）我们可以使用仅k个矩阵乘法从M₀= M开始生成M₁到M_k。 k只需要与n的二进制表示中的位数一样大即可。然后，我们可以选择那些在n的二进制表示中为1的矩阵，并将它们相乘以获得通过CRC机器运行n个零的变换。因此，如果n = 13，则计算M₀ x M₂ x M₃。

如果n的二进制表示中有j个1，那么我们只需要再进行j-1次矩阵乘法即可。因此，我们总共需要k次乘法。

• j-1次矩阵乘法，其中j<=k=floor(logbase2(n))。

现在，我们将快速构建的n个零的矩阵与CRC(A)相乘，以获得CRC(A0)。我们可以在O(log(n))时间内计算出CRC(A0)，而不是O(n)时间。然后，我们将其与CRC(B)异或，就得到了CRC(Z)。

这就是zlib的函数所做的事情。

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

- Mark Adler

---

非常棒的简明回答。感谢您的帮助！ - mblem22

与其将矩阵提高到幂次方，不如将整数（2）提高到幂次方（模CRC多项式），然后将CRC乘以（2 ^ n）％poly以循环n位。我在我的答案中发布了示例代码。 - rcgldr

@rcgldr 这就是zlib 当前的实现方式。 - Mark Adler

@MarkAdler - 一个类似的问题最早发生在1990年左右，适用于早期的DAT/DDS磁带格式，其中C2 Reed Solomon奇偶校验字节存储在编码字的中间。早期的计划是对编码器进行正常循环计算奇偶校验字节向后n位通过无进位乘以2^(255-n)，但由于ECC处理擦除和错误，"编码"被实现通过将奇偶校验字节标记为擦除并执行校正，从而驱动器最终没有真正的编码器。 - rcgldr

@Arash 评论区不是提问的地方。你需要提出一个新问题。同时，你还需要提供更多关于你想要做什么的信息。据我理解，CRC总是在运行时计算的。 - Mark Adler

Answer 2

以下是一种替代CRC（A0）的方法的示例C代码。与使用矩阵不同，可以通过乘以（CRC· ((2 ^ n％POLY）％POLY）将CRC向前循环n位。因此，重复平方是在整数而不是矩阵上执行的。如果n是常量，则可以预先计算（2 ^ n％POLY）。

```c 以下是 CRC（A0）的另一种方法的示例C代码。与使用矩阵不同，可以通过乘以（CRC·((2^n)%POLY)％POLY）来使CRC向前循环n位。因此，重复的平方运算是在整数上进行而不是矩阵。如果n是恒定的，则可以预先计算（2^n％POLY）。

```

/*  crcpad.c  - crc - data has a large number of trailing zeroes */

#include <stdio.h>
#include <stdlib.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

#define POLY (0x04c11db7u)

static uint32_t crctbl[256];

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            /* assumes twos complement */
            crc = (crc<<1)^((0-(crc>>31))&POLY);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
uint32_t pd = 0;
uint32_t i;
    for(i = 0; i < 32; i++){
        /* assumes twos complement */
        pd = (pd<<1)^((0-(pd>>31))&POLY);
        pd ^= (0-(b>>31))&a;
        b <<= 1;
    }
    return pd;
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if(p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/* # data bytes */
#define DAT  ( 32)
/* # zero bytes */
#define PAD  (992)
/* DATA+PAD */
#define CNT (1024)

int main()
{
uint32_t pmc;
uint32_t crc;
uint32_t crf;
uint32_t i;
uint8_t *msg = malloc(CNT);

    for(i = 0; i < DAT; i++)           /* generate msg */
        msg[i] = (uint8_t)rand();
    for( ; i < CNT; i++)
        msg[i] = 0;
    GenTbl();                           /* generate crc table */
    crc = GenCrc(msg, CNT);             /* generate crc normally */
    crf = GenCrc(msg, DAT);             /* generate crc for data */
    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */
    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */
    printf("%08x %08x\n", crc, crf);
    free(msg);
    return 0;
}

使用无进位乘法指令的C语言示例代码，pclmulqdq == _mm_clmulepi64_si128：

/*  crcpadm.c  - crc - data has a large number of trailing zeroes */
/*                     pclmulqdq intrinsic version                */

#include <stdio.h>
#include <stdlib.h>
#include <intrin.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;
typedef unsigned long long uint64_t;

#define POLY  (0x104c11db7ull)
#define POLYM ( 0x04c11db7u)

static uint32_t crctbl[256];

static __m128i poly;                    /* poly */
static __m128i invpoly;                 /* 2^64 / POLY */

void GenMPoly(void)                     /* generate __m12i8 poly info */
{
uint64_t N = 0x100000000ull;
uint64_t Q = 0;
    for(size_t i = 0; i < 33; i++){
        Q <<= 1;
        if(N&0x100000000ull){
            Q |= 1;
            N ^= POLY;
        }
        N <<= 1;
    }
    poly.m128i_u64[0] = POLY;
    invpoly.m128i_u64[0] = Q;
}

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            /* assumes twos complement */
            crc = (crc<<1)^((0-(crc>>31))&POLYM);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
__m128i ma, mb, mp, mt;
    ma.m128i_u64[0] = a;
    mb.m128i_u64[0] = b;
    mp = _mm_clmulepi64_si128(ma, mb, 0x00);      /* p[0] = a*b */
    mt = _mm_clmulepi64_si128(mp, invpoly, 0x00); /* t[1] = (p[0]*((2^64)/POLY))>>64 */
    mt = _mm_clmulepi64_si128(mt, poly, 0x01);    /* t[0] = t[1]*POLY */
    return mp.m128i_u32[0] ^ mt.m128i_u32[0];     /* ret =  p[0] ^ t[0] */
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if(p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/* # data bytes */
#define DAT  ( 32)
/* # zero bytes */
#define PAD  (992)
/* DATA+PAD */
#define CNT (1024)

int main()
{
uint32_t pmc;
uint32_t crc;
uint32_t crf;
uint32_t i;
uint8_t *msg = malloc(CNT);

    GenMPoly();                         /* generate __m128 polys */
    GenTbl();                           /* generate crc table */
    for(i = 0; i < DAT; i++)            /* generate msg */
        msg[i] = (uint8_t)rand();
    for( ; i < CNT; i++)
        msg[i] = 0;
    crc = GenCrc(msg, CNT);             /* generate crc normally */
    crf = GenCrc(msg, DAT);             /* generate crc for data */
    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */
    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */
    printf("%08x %08x\n", crc, crf);
    free(msg);
    return 0;
}

- rcgldr

---

我们能否在不添加0的情况下计算每个片段的CRC？考虑一个文件有2个片段（该文件具有CRC）。 - Arash

@Arash - 示例代码计算CRC时好像添加了0，但实际上没有附加任何0到数据中。 - rcgldr