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

Question

背景:

我有一段1024字节的内存.最后1020个字节将始终相同.前4个字节将改变(产品的序列号).我需要CRC-16 CCITT为整个内存部分计算(0xFFFF起始,0x1021掩码)CRC_WHOLE.

题:

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

CRC_WHOLE = XOR(CRC_A, CRC_B)

我知道这个公式不起作用(尝试过),但我希望存在类似的东西.

Answer 1

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

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

更新:

以下是2008年的一篇文章,其中详细解释了@ArtemB发现的(我已经忘记了):

crc32_combine()在zlib中基于两个关键技巧.接下来,我们抛开标准32位CRC的前置和后置条件这一事实.我们可以稍后处理.现在假设没有这种条件的CRC,因此从填充零的寄存器开始.

技巧#1:CRC是线性的.因此,如果你有流X和流Y相同的长度和独占 - 或两个流逐位获得Z,即Z = X ^ Y(使用C表示法为exclusive-or),则CRC(Z )= CRC(X)^ CRC(Y).对于手头的问题,我们有两个不同长度的流A和B,我们想要连接到流Z.我们可用的是CRC(A)和CRC(B).我们想要的是一种快速计算CRC(Z)的方法.诀窍是构造X = A与长度(B)零比特连接,并且Y =长度(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机器并不是一件容易的事.每个零都会改变寄存器内容.因此要获得CRC(A0),我们需要将寄存器设置为CRC(A),然后通过它运行长度(B)零.那么我们可以使用CRC(B)= CRC(0B)来排除或者得到结果,并且得到我们想要的结果,即CRC(Z)= CRC(AB).瞧!

嗯,实际上瞧瞧是不成熟的.我对这个答案一点也不满意.我不希望计算花费时间与B的长度成比例.与简单地将寄存器设置为CRC(A)并运行B流通过相比,这不会节省任何时间.我认为必须有一种更快的方法来计算将n零点馈入CRC机器的效果(其中n =长度(B)).这导致我们:

技巧#2:CRC机器是线性状态机.如果我们知道我们什么时候喂零到机器时发生的线性变换,那么我们可以做这种转变操作,以更有效地发现,从进料到成果转化ñ零到机器中.

将单个零位馈送到CRC机器的转换完全由32×32二进制矩阵表示.为了应用变换,我们将矩阵乘以寄存器,将寄存器作为32位列向量.对于二进制的矩阵乘法(即在2的伽罗瓦域上),乘法的作用是由"和"进行的,并且加法的作用是通过"异或"来进行的.

构造魔术矩阵有几种不同的方法,表示通过将CRC机器馈送到单个零位而引起的变换.一种方法是观察矩阵的每一列是当你的寄存器开始时只有一个矩阵所得到的.因此第一列是当寄存器为100时得到的...然后输入零,第二列来自0100 ......等等(这些被称为基础向量.)你可以看到这一列简单地通过与这些向量进行矩阵乘法.矩阵乘法选择对应于单个列的位置的矩阵的列.

现在为了诀窍.一旦我们有了魔术矩阵,我们就可以将初始寄存器内容搁置一段时间,而是将变换用于一个零来计算n个 零的变换.我们可以将矩阵的n个副本相乘,得到n个零的矩阵.但这比仅 通过机器运行n零更糟糕.然而,有一种简单的方法可以避免大多数矩阵乘法得到相同的答案.假设我们想知道运行八个零位或一个字节的转换.让我们调用表示运行一个零的魔术矩阵:M.我们可以进行七次矩阵乘法得到R = MxMxMxMxMxMxMxM.相反,让我们从MxM开始并调用P.然后PxP是MxMxMxM.让我们称之为Q.然后QxQ是R.所以现在我们已经将七次乘法减少到三次.P = M×M,Q = PxP,R = QxQ.

现在我确定你会得到任意n个零的想法.我们可以非常快速地生成变换矩阵M _k,其中M _k是用于运行2 ^k零的变换.(在上面的段落中,M ₃是R.)我们可以使M ₁到M _k只有k个 矩阵乘法,从M ₀ = M开始 .k只需要与n的二进制表示中的位数一样大.然后我们可以选择那些在n的二进制表示中有一个矩阵的矩阵,并将它们相乘以获得通过CRC机器运行n个零的转换.因此,如果n = 13,则计算M ₀ x M ₂ x M ₃.

如果j是n的二进制表示中的一个的数,那么我们只有j - 1个矩阵乘法.所以我们总共有k + j - 1个矩阵乘法,其中j <= k = floor(logbase2(n)).

现在我们将快速构造的矩阵用于n个零,并将其乘以CRC(A)得到CRC(A0).我们可以在O(log(n))时间内计算CRC(A0),而不是O(n)时间.我们独家或与CRC(B)和Voila一起!(这次真的),我们有CRC(Z).

这就是zlib的crc32_combine()作用.

我将把它留作读者的练习,以便如何处理CRC寄存器的前后调节.您只需要应用上面的线性度观察.提示:您不需要知道长度(A).实际上crc32_combine()只需要三个参数:CRC(A),CRC(B)和长度(B)(以字节为单位).

Answer 2

下面是 CRC(A0) 替代方法的示例 C 代码。CRC 可以通过乘法向前循环 n 位，而不是使用矩阵 (CRC \xc2\xb7 ((2^n)%POLY)%POLY 。因此，重复平方是对整数而不是矩阵执行的。如果n是常数，则可以预先计算(2^n)%POLY。

\n

/*  crcpad.c  - crc - data has a large number of trailing zeroes */\n\n#include <stdio.h>\n#include <stdlib.h>\n\ntypedef unsigned char       uint8_t;\ntypedef unsigned int       uint32_t;\n\n#define POLY (0x04c11db7u)\n\nstatic uint32_t crctbl[256];\n\nvoid GenTbl(void)                       /* generate crc table */\n{\nuint32_t crc;\nuint32_t c;\nuint32_t i;\n    for(c = 0; c < 0x100; c++){\n        crc = c<<24;\n        for(i = 0; i < 8; i++)\n            /* assumes twos complement */\n            crc = (crc<<1)^((0-(crc>>31))&POLY);\n        crctbl[c] = crc;\n    }\n}\n\nuint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */\n{\nuint32_t crc = 0u;\n    while(size--)\n        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];\n    return(crc);\n}\n\n/* carryless multiply modulo crc */\nuint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */\n{\nuint32_t pd = 0;\nuint32_t i;\n    for(i = 0; i < 32; i++){\n        /* assumes twos complement */\n        pd = (pd<<1)^((0-(pd>>31))&POLY);\n        pd ^= (0-(b>>31))&a;\n        b <<= 1;\n    }\n    return pd;\n}\n\n/* exponentiate by repeated squaring modulo crc */\nuint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */\n{\nuint32_t prd = 0x1u;                    /* current product */\nuint32_t sqr = 0x2u;                    /* current square */\n    while(p){\n        if(p&1)\n            prd = MpyModCrc(prd, sqr);\n        sqr = MpyModCrc(sqr, sqr);\n        p >>= 1;\n    }\n    return prd;\n}\n\n/* # data bytes */\n#define DAT  ( 32)\n/* # zero bytes */\n#define PAD  (992)\n/* DATA+PAD */\n#define CNT (1024)\n\nint main()\n{\nuint32_t pmc;\nuint32_t crc;\nuint32_t crf;\nuint32_t i;\nuint8_t *msg = malloc(CNT);\n\n    for(i = 0; i < DAT; i++)           /* generate msg */\n        msg[i] = (uint8_t)rand();\n    for( ; i < CNT; i++)\n        msg[i] = 0;\n    GenTbl();                           /* generate crc table */\n    crc = GenCrc(msg, CNT);             /* generate crc normally */\n    crf = GenCrc(msg, DAT);             /* generate crc for data */\n    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */\n    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */\n    printf("%08x %08x\\n", crc, crf);\n    free(msg);\n    return 0;\n}\n

\n

使用内部函数进行无进位乘法的示例 C 代码，pclmulqdq == _mm_clmulepi64_si128：

\n

/*  crcpadm.c  - crc - data has a large number of trailing zeroes */\n/*                     pclmulqdq intrinsic version                */\n\n#include <stdio.h>\n#include <stdlib.h>\n#include <intrin.h>\n\ntypedef unsigned char       uint8_t;\ntypedef unsigned int       uint32_t;\ntypedef unsigned long long uint64_t;\n\n#define POLY  (0x104c11db7ull)\n#define POLYM ( 0x04c11db7u)\n\nstatic uint32_t crctbl[256];\n\nstatic __m128i poly;                    /* poly */\nstatic __m128i invpoly;                 /* 2^64 / POLY */\n\nvoid GenMPoly(void)                     /* generate __m12i8 poly info */\n{\nuint64_t N = 0x100000000ull;\nuint64_t Q = 0;\n    for(size_t i = 0; i < 33; i++){\n        Q <<= 1;\n        if(N&0x100000000ull){\n            Q |= 1;\n            N ^= POLY;\n        }\n        N <<= 1;\n    }\n    poly.m128i_u64[0] = POLY;\n    invpoly.m128i_u64[0] = Q;\n}\n\nvoid GenTbl(void)                       /* generate crc table */\n{\nuint32_t crc;\nuint32_t c;\nuint32_t i;\n    for(c = 0; c < 0x100; c++){\n        crc = c<<24;\n        for(i = 0; i < 8; i++)\n            /* assumes twos complement */\n            crc = (crc<<1)^((0-(crc>>31))&POLYM);\n        crctbl[c] = crc;\n    }\n}\n\nuint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */\n{\nuint32_t crc = 0u;\n    while(size--)\n        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];\n    return(crc);\n}\n\n/* carryless multiply modulo crc */\nuint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */\n{\n__m128i ma, mb, mp, mt;\n    ma.m128i_u64[0] = a;\n    mb.m128i_u64[0] = b;\n    mp = _mm_clmulepi64_si128(ma, mb, 0x00);      /* p[0] = a*b */\n    mt = _mm_clmulepi64_si128(mp, invpoly, 0x00); /* t[1] = (p[0]*((2^64)/POLY))>>64 */\n    mt = _mm_clmulepi64_si128(mt, poly, 0x01);    /* t[0] = t[1]*POLY */\n    return mp.m128i_u32[0] ^ mt.m128i_u32[0];     /* ret =  p[0] ^ t[0] */\n}\n\n/* exponentiate by repeated squaring modulo crc */\nuint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */\n{\nuint32_t prd = 0x1u;                    /* current product */\nuint32_t sqr = 0x2u;                    /* current square */\n    while(p){\n        if(p&1)\n            prd = MpyModCrc(prd, sqr);\n        sqr = MpyModCrc(sqr, sqr);\n        p >>= 1;\n    }\n    return prd;\n}\n\n/* # data bytes */\n#define DAT  ( 32)\n/* # zero bytes */\n#define PAD  (992)\n/* DATA+PAD */\n#define CNT (1024)\n\nint main()\n{\nuint32_t pmc;\nuint32_t crc;\nuint32_t crf;\nuint32_t i;\nuint8_t *msg = malloc(CNT);\n\n    GenMPoly();                         /* generate __m128 polys */\n    GenTbl();                           /* generate crc table */\n    for(i = 0; i < DAT; i++)            /* generate msg */\n        msg[i] = (uint8_t)rand();\n    for( ; i < CNT; i++)\n        msg[i] = 0;\n    crc = GenCrc(msg, CNT);             /* generate crc normally */\n    crf = GenCrc(msg, DAT);             /* generate crc for data */\n    pmc = PowModCrc(PAD*8);             /* pmc = pow(2,PAD*8)%crc */\n    crf = MpyModCrc(crf, pmc);          /* crf = (crf*pmc)%crc */\n    printf("%08x %08x\\n", crc, crf);\n    free(msg);\n    return 0;\n}\n

\n