again CRC, I don't get it

Go To Last Post
9 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi there,

I know there are several posts about this and I browsed and read a lot in the net but I can not find the point where I am mistaken.
I'm doing a transmission from a PC program to an AVR which is using CRC. Don't get me wrong: it is working. I got the code from some example and the other part was done by someone else. But as I'm going to need this on some more platforms and occasions and in possibly more modes, I want to fully understand this. The PC part uses a table based on the 0x1021 polynome it starts like this :

    0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,
    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,
    0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6, 

and if I'm not mistaken these are the pre-calculated values for each value a byte can have. (Right?) It is widely used and seems correct.

Now on the AVR there is this code :

unsigned int calcrc(char *ptr, int count)
{
	unsigned long int crc;
	char i;
	crc = 0;
	while (--count >= 0)
	{
		crc = crc ^ (unsigned int) *ptr++ << 8;
		i = 8;
		do
		{
		if (crc & 0x8000)
			crc = crc << 1 ^ 0x1021;
		else
			crc = crc << 1;
		} while(--i);
	}
	return (unsigned int)(crc&0x0000FFFF);
}

If I now try to verify the values from 0 to 15 everything is ok, but when I try the value for 16 the table says 0x1231 while I'm calculating (manually following the code) 0x0210.
I'm just confused where I'm thinking wrong.
When I have the 16 << 8 it is 0x1000. Now three shifts as there is no 1 on MSB. Then there is the one , so one shift and XORING the 0x1021. Then another 4 shifts as we have the count from 8 to 0. There we are with 0x0210. Or not ?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Surely you can single step this in the simulator and see exactly how the calculation is done at every step?

Make the variables "volatile" if you want to "watch" them at each step.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

There are two ways to calculate a CRC. Table driven and looped. The table you show is for table driven, the code you show is looped. Table driven is much faster, probably over ten times faster than looped code, loop code is small but table driven needs a 512 byte table. As for how a CRC works, there are a few explanations on the web.

The polynomial does not get shifted! You get 8 bits of dats, add that into the current crc value, then loop for the 8 bits Xoring with the poly ifthe msb is set then shift the next bit. I think there is at least one pictorial explanation of crc on the web. Failing that, get out your pencil and paper. I've done it this way many times.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

thank you for your answers

Quote:
The polynomial does not get shifted! You get 8 bits of dats, add that into the current crc value, then loop for the 8 bits Xoring with the poly ifthe msb is set then shift the next bit. I think there is at least one pictorial explanation of crc on the web. Failing that, get out your pencil and paper. I've done it this way many times.

excuse me, but didn't I describe just that ? I did it pencil and paper ... could you do this easy example to show me where I'm wrong ? (Believe me, I read through a lot of sites) and as the code seems to be running ok, I seem to make a mistake when thinking through it.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

You showed the polynomial as being shifted!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Pencil and paper are prone to error (and misunderstanding of C promotion/truncation rules). Have you stepped the code in a simulator? What happened there?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

@Kartman
if you're XORING the polynomial into the CRC - then of course this value will be shifted if there are zeros - try it.

@clawson
just on it - the result is ok - as expected, now looking deeper

- found it : I counted wrong, in step 7 there is a '1' on 0x8000 position, so that in the next step the polynomial gets xored in again. and then I get 0x1231
thank you and sorry for bothering, sometimes it helps to whine and try to explain it :D

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Loop 1: Value = 0x1000, So shift left, Value = 0x2000
Loop 2: Value = 0x2000, So shift left, Value = 0x4000
Loop 3: Value = 0x4000, So Shift left, Value = 0x8000
Loop 4: Value = 0x8000, So shift and XOR, Value = 0x1021
Loop 5: Value = 0x1021, so Shift left, Value = 0x2042
Loop 6: Value = 0x2042, so shift left, Value = 0x4084
Loop 7: Value = 0x4084, so shift left, Value = 0x8108
Loop 8: Value = 0x8108, so shift and XOR, Value = 0x1231

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

cross - posted, thank you Joeks just updated the posting above