locationchecksumcrc

The difference of location of Checksum and CRC. WHY?


I have a question while studying CRC and checksum.

CRC is located at tail, but checksum is located at header. I thought because of complication of CRC and checksum. CRC is more complicate, so it locates header, but checksum is less complicate, so it locates tail. Is it right?

Why is that?


Solution

  • In the case of transmitted or received data, hardware implementations generally generate a CRC or checksum while data is being transmitted, and then transmit the CRC or checksum (so the CRC or checksum would be at the end of data). This eliminates the need to buffer more than what is needed to hold the CRC or checksum and a unit of transmission (such as a byte).

    For a message in memory, the CRC parity bytes or checksum can be located anywhere within a message. For a checksum, this is straight forward, but for a CRC, the CRC has to be generated normally, then cycled backwards and stored into where it will be located in a message. The backward cycling can be optimized as shown in the second part of my answer.


    Checksums can be anywhere in a message, since the calculation is easy.

    Intel hex format is/was a fairly common format for storing binary data in a text file, and has the checksum after the end of data on each line of a text file:

    https://en.wikipedia.org/wiki/Intel_HEX#Record_structure

    IPv4 header puts the checksum on message_word[5]:

    https://en.wikipedia.org/wiki/IPv4_header_checksum#Calculating_the_IPv4_header_checksum


    It is possible to have the CRC parities anywhere in a message. The parity bytes are zeroed, a normal CRC is calculated, then the CRC is "reverse cycled" to the location for where it will be stored. Rather than actually reversing the CRC, a carryless multiply can be used:

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

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

    Example code for a 32 byte message with 14 data byte, 4 parity bytes, 14 data bytes. After the parity bytes are stored in the message, a normal CRC calculation on the message will be zero.

    #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, 4 parities, 14 data */
    /*  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,0x13,0x14,0x15,0x16,0x17,0x18,
                       0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20};
    
        GenTbl();                           /* generate crc table */
        pmr = PowModCrc(-1-(18*8));         /* pmr = pow(2,-1-18*8)%crc */
        crc = GenCrc(msg, 32);              /* generate crc */
        par = MpyModCrc(crc, pmr);          /* par = (crc*pmr)%crc */
        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, 32);              /* crc == 0 */
        printf("%08x\n", crc);
    
        return 0;
    }