CRC comparison and difference between similar algorithms

Question

I was reading about CRCs and I came across the CRC catalogue and this article on CRC-CCITT.

I implemented MyCrc16 (see below for code) based off on the second link.

Which just takes the bytes, in order, the bits in reverse order and shifts them, one by one, into the (initial) CRC, and then XORs with the polynomial to get the remainders, plus the augmentation at the end.

Now... I also had some pre-existing CRC16 implementation (OtherCrc16), which, according to the catalogue is CRC-16/CCITT-FALSE.

What I don't understand is why does the OtherCrc16 work? since the first byte of the input, and all the rest afterwards, are XORed with the (initial) CRC, not appended to it as does the other implementation. And when it iterates on the bits, it doesn't take into account what the first algorithm considers "shifting the input into the CRC", instead it just XORs with the polynomial if necessary.

Am I missing some property of the XOR operation? In my opinion the two algorithms should have the same output (not considering the augmentation of the first one of course), but they do not.

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

uint16_t MyCrc16(const unsigned char *data, int length, uint16_t poly, uint16_t crc)
{
        for(int byte=0; byte<length; ++byte)
        {
                for(int bit=7; bit>=0; --bit)
                {
                        bool doXor = false;
                        if(crc & 0x8000)
                        {
                                doXor = true;
                        }
                        crc <<= 1;
                        if(data[byte] & (1 << bit))
                        {
                                crc += 1;
                        }
                        if(doXor)
                        {
                                crc ^= poly;
                        }
                }
        }

        //augument the crc with 0s
        for(int i=0; i<16; i++)
        {
                bool doXor = false;
                if(crc & 0x8000)
                {
                        doXor = true;
                }

                crc = crc << 1;
                if(doXor)
                {
                        crc ^= poly;
                }
        }

        return crc;
}

uint16_t OtherCrc16(const unsigned char *data, int length, uint16_t poly, uint16_t crc)
{
        for(int i=0; i<length; i++)
        {
                crc = crc ^ (data[i] << 8);
                for (int bit = 0; bit< 8; bit++)
                {
                        bool doXor = false;
                        if(crc & 0x8000)
                        {
                                doXor = true;
                        }
                        crc <<=1;

                        if(doXor)
                        {
                                crc ^= poly;
                        }
                }
        }
        return crc;
}


int main(void) {
    // your code goes here
    uint16_t poly = 0x1021;

    unsigned char c[] = "123456789";
    printf("My CRC = %04x\n", MyCrc16(c, 9, poly, 0xffff));
    printf("Other CRC = %04x\n", OtherCrc16(c, 9, poly, 0xffff));
    return 0;
}

PS: Executable code: http://ideone.com/mKuQqQ

I did, I still cannot see why it's different when XORing the message into the CRC first... — Paul
You mean, you still cannot see why it's the same. That is very nicely explained in great detail in "10. A Slightly Mangled Table-Driven Implementation" in the CRC tutorial. — Mark Adler
@MarkAdler - it's different if the initial CRC value is not 0x0000. — rcgldr

rcgldr rcgldr · Accepted Answer · 2019-07-27T03:31:00

If the initial value of the CRC is zero, then both methods produce the same CRC. However, if the initial value of the CRC is non-zero, then MyCrc16 cycles that initial value 16 times before it starts including any data bits, as if it prefixed the data with 16 zero bits. For a non-zero initial CRC, MyCrc16 needs the initial value reversed cycled 16 times, so that after the initial value is cycled forwards 16 times, it's the same as the initial value used in OtherCrc16. For an initial value of 0xffff, reverse cycling it 16 times results in 0x84cf. The following change noted in comment will result in the two methods producing the same CRC:

    printf("My CRC = %04x\n", MyCrc16(c, 9, poly, 0x84cf));  /* change to 0x84cf */
    printf("Other CRC = %04x\n", OtherCrc16(c, 9, poly, 0xffff));

CRC comparison and difference between similar algorithms

1 Answers