CRC confusion (solved)

ManAtWork

I know how to calculate a CRC and I've even already managed to write a CRC16 function using the CRCNIB instruction. However, I'm just a little confused how it is properly used.

I have a packet of 12 bytes I send over a serial line, 10 bytes payload and 2 bytes CRC. I calculate the CRC and write it to the end of the buffer, then I send out all 12 bytes.

My problem is that the other side is not a propeller but an ARM chip. I can't receive the first 10 bytes seperately, calculate the CRC and compare it to the last 2 bytes. I have to receive all the 12 bytes continously and calculate the CRC over all 12 bytes. (receiving has to be done with DMA in a single block because the ARM has not enough power to bit bang single bytes)

I know that there is some trick to prepare the CRC of the sender in such a way that the receiver will see a CRC of zero when he includes the sender CRC in the calculation. Unfortunatelly, I have forgotten how this works. I think, I have to add some padding bytes or use a different start value... Anybody knows what to do?

macca

ManAtWork wrote: »

I know that there is some trick to prepare the CRC of the sender in such a way that the receiver will see a CRC of zero when he includes the sender CRC in the calculation. Unfortunatelly, I have forgotten how this works. I think, I have to add some padding bytes or use a different start value... Anybody knows what to do?

I think you may look at the source code for xmodem and zmodem protocols where these tricks are used.

As far as I remember (and looking at some source code), for CRC16 just initialize it at 0 and the final CRC will be zero as well.

Here is an excerpt of a ZModem routine (see the Z_UpdateCRC calls):

static int _Z_GetBinaryHeader(hdr)
register unsigned char * hdr;
{
    register int c;
    register unsigned int crc;
    register int n;

#ifdef DEBUG
    show_debug_name("Z_GetBinaryHeader");
#endif

    if ((c = Z_GetZDL()) & ~0xFF) {
        return c;
    }
    Rxtype = c;
    crc = Z_UpdateCRC(c, 0);

    for (n = 4; --n >= 0;) {
        if ((c = Z_GetZDL()) & ~0xFF) {
            return c;
        }
        crc = Z_UpdateCRC(c, crc);
        *hdr++ = (unsigned char)(c & 0xff);
    }
    if ((c = Z_GetZDL()) & ~0xFF) {
        return c;
    }

    crc = Z_UpdateCRC(c, crc);
    if ((c = Z_GetZDL()) & ~0xFF) {
        return c;
    }

    crc = Z_UpdateCRC(c, crc);
    if (crc & 0xFFFF) {
        z_message(msgtxt[M_CRC_MSG]);
        return ERROR;
    }

    return Rxtype;
}                                                /* _Z_GetBinaryHeader */

Hope this helps.

Rayman

I wonder if it works similar to what is in ymodem…

Here's the code for sending a packet and doing crc for prop1:

    'send packet
    repeat i from 0 to 127
      ser.tx(pdata[i])

      crc:=UpdateCRC(pdata[i],crc)
       

    ser.tx((crc>>8)&$FF)
    ser.tx(crc&$FF)

PRI UpdateCRC(data,crc):newcrc|i,icrc
 'look here:http://web.mit.edu/6.115/www/miscfiles/amulet/amulet-help/xmodem.htm

  crc:=crc^(data<<8)
  repeat i from 0 to 7
    if crc&$8000
      crc:=((crc<<1)&$FFFF)^$1021
    else
      crc:=(crc<<=1)&$FFFF

  return crc&$FFFF

Rayman

I wrote that but didn't send it until macca mentioned something similar...

ManAtWork

Yes, I also thought it would be that simple. Unfortunatelly, it didn't work the first go.

test_buffer			' send Frame to HV-Unit (12 bytes)
		byte 	0,1,2,3,4,5,6,7,8,9
sendCrc		word	0

This gave me the following CRC values (after each byte):

0000 ' obviously correct
1021 ' this is equal to the polynomial
1373
6131
0D03
8208
D90C
26B3
76AC
2378 ' final CRC value after 10th byte

Now, I placed the calculated CRC into the buffer

test_buffer			' send Frame to HV-Unit (12 bytes)
		byte 	0,1,2,3,4,5,6,7,8,9
sendCrc		word	$2378

... and ran the test again, this time with all 12 bytes. The result is

...
2378 ' CRC value after 10th byte
939E
39DB ' not Zero :-(

But then I remembered that the last time I programmed an YModem protocol was on a big endian machine (Commodore Amiga with Motorola CPU).
I tried swapping the byte order.

test_buffer			' send Frame to HV-Unit (12 bytes)
		byte 	0,1,2,3,4,5,6,7,8,9
sendCrc		word	$7823

And... guess what... now it also works on the propeller!
So that's the trick: The byte order must match the shifting direction of the CRC generator. Shifting left means high byte first.

So, although your code example didn't help me immediately it pointed me in the right direction. Thanks!

ManAtWork

I meant in Macca's code it wasn't immediately clear.

ser.tx((crc>>8)&$FF)
    ser.tx(crc&$FF)

That's obvious. Thanks Rayman, I haven't seen your post while writing my previous one.

ManAtWork

To leave something useful for the search engine I post my code:

CON
  polynomial = $11021 ' polynomial has to be reversed because of
  revpoly    = $8408  ' the P2 shifting right instead of left

VAR
  long  crc   

PUB crc16 (b): c | p
' data byte in, crc word out
  c:= crc
  p:= revpoly
  asm
    shl  b,#24
    setq b
    crcnib c,p
    crcnib c,p
  endasm
  crc:= c
  asm
    rev c
    shr c,#16
  endasm

PUB setStart (c)
  asm
    rev c
    shr c,#16
  endasm
  crc:= c

PUB isZero : z
  return crc==0

The code is verified against the results I got from the ARM chip (SAMC21E17 from Atmel) so it is compatible to the CCITT standard. Please note that the internal revpoly constant and crc variable are bit-reversed for efficiency reasons. You have to use the return value of the crc16 function which has the correct bit order.

Cluso99

CRC's are not simple. There are a few websites where you can paste a string and get the CRC out.

You need to work out what to start with (load your crc variable with initially), and you need to work out if you need to reverse the bits. Once you work out these two things, the crc should fall into place. There is an old P2 thread somewhere where I worked this out but it may just be simpler to look for the website.