CRC32 returns unexpected result Topic is solved

Technical questions regarding the xTIMEcomposer, xSOFTip Explorer and Programming with XMOS.
User avatar
dsteinwe
Experienced Member
Posts: 73
Joined: Wed Jun 29, 2016 8:59 am

CRC32 returns unexpected result

Postby dsteinwe » Wed Jan 06, 2021 12:46 pm

Hi,

I have created (under Linux) a file with following byte sequence: 0x61, 0x62, 0x63, 0x64. When I calculate the CRC32 in the cli, it returns "ed82cd11". This is consistent with the results of online calculators, found e.g. on https://crccalc.com/. To get this result, the initial value should be set to 0xFFFFFFFF and the polynom to 0x04C11DB7.

I thought, it should be simple to reproduce the result with a xmos using following code:

Code: Select all

    unsigned v = 0x64636261;
    unsigned c = 0xFFFFFFFF;
    unsigned p = 0x04C11DB7;
    crc32(c, v, p);
    printf("CRC: 0x%x; inv: 0x%x\n", c, ~c);
    printf("Should be: 0xED82CD11; inv: 0x127D32EE \n");
But I get a different result:
CRC: 0x618cec1a; inv: 0x9e7313e5
Should be: 0xED82CD11; inv: 0x127D32EE
I have reversed the byte order, but the result is even wrong. Can you give me a hint, how to get the correct result?

Thanks!
View Solution
User avatar
akp
Respected Member
Posts: 479
Joined: Thu Nov 26, 2015 11:47 pm

Postby akp » Thu Jan 07, 2021 12:41 pm

I took a look at mii_master.xc to see how to do the calculation you want. Note that you've got to bit reverse the polynomial.

Try

Code: Select all

      unsigned v = 0x64636261;
      unsigned c = 0;
      unsigned p = 0xEDB88320; 
      v ^= 0xFFFFFFFF;
      crc32(c, v, p);
      crc32(c, 0xFFFFFFFF, p);
      printf("CRC: 0x%x; inv: 0x%x\n", c, ~c);
Or another way of putting it...

Code: Select all

      unsigned v = 0x64636261;
      unsigned c = 0;
      unsigned p = 0xEDB88320; 
      crc32(c, ~v, p); // invert the first word, subsequent aren't inverted
      crc32(c, ~0, p);
      printf("CRC: 0x%x; inv: 0x%x\n", c, ~c);
User avatar
dsteinwe
Experienced Member
Posts: 73
Joined: Wed Jun 29, 2016 8:59 am

Postby dsteinwe » Thu Jan 07, 2021 6:21 pm

@akp: Thank you, your answer helped me. Based on your post, I have figured out following, that may be help others, too:

1. The polynom 0xEDB88320 is the bit-reversed value of 0x04C11DB7. You can do it with a "bitrev()" and a "#include <xclib.h>".

2. Your first instruction crc32(0, 0x64636261, 0xEDB88320) is equivalent to ~0x64636261. I have tested it with following code:

Code: Select all

printf("Start\n");
for (unsigned i = 0; i < 0xFFFFFFFF; i++) {
	unsigned c = 0;
	unsigned v = ~i;
	crc32(c, v, 0xEDB88320);
	if (c != ~i) printf("i = 0x%x; c = 0x%x != ~i = 0x%x\n", i, c, ~i);
}
printf("End\n");

It seems to be valid for all other polynoms, but I haven't tested it and I have no mathematically explanation, why it is so.

3. Based on the example code of https://github.com/xmos/lib_ethernet/bl ... _master.xc
I can successfully calculate the crc32 for one or multiple words with following code:

Code: Select all

unsigned calcCRC32(unsigned values[n], unsigned n) {
    unsigned poly = 0xEDB88320;
    unsigned crc = 0;

    if (n == 0) return 0;
    crc32(crc, ~values[0], poly); // eq. to crc = ~values[0];
    for (int i = 1; i < n; i++) {
        crc32(crc, values[i], poly);
    }

    crc32(crc, ~0, poly);
    return crc;
}


4. For none 32bit values you can use the function "crcn()". Unfortunately, I wasn't able to reproduce the result of a single byte with this function. My result differs from https://crccalc.com/?crc=61&method=crc3 ... uttype=hex. Maybe you have a suggestion.
User avatar
akp
Respected Member
Posts: 479
Joined: Thu Nov 26, 2015 11:47 pm

Postby akp » Thu Jan 07, 2021 7:59 pm

Re 2.

The definition of the crc32 instruction (e.g. see xs1.h though the syntax is a little off where it combines crc and checksum) shows why this is the case. The xor with the polynomial doesn't take place at all when the input crc is 0. So c = 0; crc32(c,~v, p); is equivalent to c = ~v.

Re 4.

If the number of input bytes is < 4 then you have to do some final xor. I am not sure why. Try this modification of your code to take any number of bytes rather than words and it should match the online calculators.

Code: Select all

unsigned calcCRC32(unsigned values[], unsigned n_bytes)
{
    unsigned poly = 0xEDB88320;
    unsigned crc = 0;

    if( 0 == n_bytes )
    {
      return 0;
    }
    // handle first word properly in case n_bytes < 4
    if( n_bytes < 4 )
    {
      crcn(crc, ~values[0], poly, 8*n_bytes);
      crc32(crc, ~0, poly);
      crc ^= 0xFFFFFFFFul >> (8*n_bytes);
    }
    else
    {
      unsigned n = n_bytes >> 2;
      unsigned rem_bytes = n_bytes - n*4;
      crc32(crc, ~values[0], poly);
      // handle remaining full words
      for (int i = 1; i < n; i++) {
          crc32(crc, values[i], poly);
      }
      // handle remaining bytes
      if( rem_bytes )
      {
        crcn(crc, values[n], poly, 8*rem_bytes);
      }
      crc32(crc, ~0, poly);
    }

    return crc;
}
Here's my test code:

Code: Select all

      unsigned v[] = {0x64636261, 0x68676665, 0x69};
      printf("CRC of 0x61: 0x%x\n", calcCRC32(v, 1));
      printf("CRC of 0x61 0x62: 0x%x\n", calcCRC32(v, 2));
      printf("CRC of 0x61 0x62 0x63: 0x%x\n", calcCRC32(v, 3));
      printf("CRC of 0x61 0x62 0x63 0x64: 0x%x\n", calcCRC32(v, 4));
      printf("CRC of 0x61 0x62 0x63 0x64 0x65: 0x%x\n", calcCRC32(v, 5));
      printf("CRC of 0x61 0x62 0x63 0x64 0x65 0x66: 0x%x\n", calcCRC32(v, 6));
      printf("CRC of 0x61 0x62 0x63 0x64 0x65 0x66 0x67: 0x%x\n", calcCRC32(v, 7));
      printf("CRC of 0x61 0x62 0x63 0x64 0x65 0x66 0x67 0x68: 0x%x\n", calcCRC32(v, 8));
      printf("CRC of 0x61 0x62 0x63 0x64 0x65 0x66 0x67 0x68 0x69: 0x%x\n", calcCRC32(v, 9));
User avatar
dsteinwe
Experienced Member
Posts: 73
Joined: Wed Jun 29, 2016 8:59 am

Postby dsteinwe » Thu Jan 07, 2021 8:40 pm

I agree with you, the need of the line

Code: Select all

crc ^= 0xFFFFFFFFul >> (8*n_bytes);
is weird. However, I'm very happy that you have shared this code. Thanks a lot!
User avatar
akp
Respected Member
Posts: 479
Joined: Thu Nov 26, 2015 11:47 pm

Postby akp » Thu Jan 07, 2021 8:43 pm

No problem, I think this thread may be helpful to others, too. Good luck!

Who is online

Users browsing this forum: No registered users and 9 guests