是否可以从CRC校验和末尾删除填充 [英] Is it possible to remove padding at the end from CRC checksum

问题描述

例如，我计算了一个1024 KB文件的CRC校验和，该文件在文件末尾包含22 KB的零填充。

For example, I calculated CRC checksum of a file of size 1024 KB and file includes 22 KB of padding of zeros at the end of the file.

如果给定的校验和为1024 KB，并且给定文件的零填充的大小为

If given checksum of 1024 KB and size of the padding of zeros of given file

是否可以不通过而计算文件的校验和。在上述情况下，即获得文件的1002 KB校验和。假设我们不必再次重新计算校验和，并重复使用填充已为整个文件计算的校验和。

Is it possible to calculate the checksum of the file without the passing. That is in above case getting the checksum of 1002 KB of the file. Assuming we don't have to recalculate the checksum again and reuse the checksum already calculated for the entire file with padding.

推荐答案

之后计算正常的CRC，可以将CRC反向循环到尾随零，但可以使用无进位乘法来代替对CRC的实际反向循环：

After a normal CRC is calculated, a CRC can be "reverse cycled" backwards past the trailing zeroes, but rather than actually reverse cycling the CRC, a carryless multiply can be used:

new crc = (crc · (pow(2,-1-reverse_distance)%poly))%poly

-1表示CRC的循环周期。对于CRC32，周期为2 ^ 32-1 = 0xffffffff。

The -1 represents the cyclic period for a CRC. For CRC32, the period is 2^32-1 = 0xffffffff .

通过生成pow（2，-1-（i * 8））％poly的表）对于i = 1到n，时间复杂度可以降低为O（1），先进行表查找，然后进行无进位乘法模多项式（32次迭代）。

By generating a table for pow(2,-1-(i*8))%poly) for i = 1 to n, time complexity can be reduced to O(1), doing a table lookup followed by a carryless multiply mod polynomial (32 iterations).

代码，用于包含14个数据字节，18个零字节的32字节消息，新的crc位于msg [{14,15,16,17}]处。在将新的字节存储在消息中之后，对缩短的消息的常规CRC计算将为零。示例代码不使用表，并且pow（2，-1-（n * 8））％poly）计算的时间复杂度为O（log2（n））。

Example code for a 32 byte message with 14 data bytes, 18 zero bytes, with the new crc to be located at msg[{14,15,16,17}]. After the new bytes are stored in the message, a normal CRC calculation on the shortened message will be zero. The example code doesn't use a table, and the time complexity is O(log2(n)) for the pow(2,-1-(n*8))%poly) calculation.

#include <stdio.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

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++)
            crc = (crc<<1)^((0-(crc>>31))&0x04c11db7);
        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++){
        pd = (pd<<1)^((0-(pd>>31))&0x04c11db7u);
        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;
}

/*  message 14 data, 18 zeroes */
/*  parities = crc cycled backwards 18 bytes */

int main()
{
uint32_t pmr;
uint32_t crc;
uint32_t par;
uint8_t msg[32] = {0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,
                   0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x00,0x00,
                   0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
                   0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00};

    GenTbl();                           /* generate crc table */
    pmr = PowModCrc(-1-(18*8));         /* pmr = pow(2,-1-18*8)%crc */
    crc = GenCrc(msg, 32);              /* generate crc including 18 zeroes */
    par = MpyModCrc(crc, pmr);          /* par = (crc*pmr)%crc = new crc */
    crc = GenCrc(msg, 14);              /* generate crc for shortened msg */
    printf("%08x %08x\n", par, crc);    /* crc == par */
    msg[14] = (uint8_t)(par>>24);       /* store parities in msg */
    msg[15] = (uint8_t)(par>>16);
    msg[16] = (uint8_t)(par>> 8);
    msg[17] = (uint8_t)(par>> 0);
    crc = GenCrc(msg, 18);              /* crc == 0 */
    printf("%08x\n", crc);

    return 0;
}

这篇关于是否可以从CRC校验和末尾删除填充的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！