Anyone with CRC experience?

Paul Baker · 2007-12-20 04:04

I am writng a CRC object (first in spin then in assembly) and have the CRC16 CCITT working correctly but the CRC8 and CRC32 routines are not working. With the help of online calculators I figured out I need to reverse the data and reverse the result, but I am a little unlcear where in the code this occurs,·I found some code described as inverted/reversed/reflected but it too didnt produce the value expected. Here's the two routines,

PUB crc8bitwise(pBuf, buflen, poly, initial): crc | i,j
  crc := initial
  repeat i from 0 to buflen - 1
    crc ^= BYTE[noparse][[/noparse]pBuf][noparse][[/noparse]i]
    repeat j from 0 to 7
      if crc & $80
        crc := (crc << 1) ^ poly
      else
        crc <<= 1
  crc &= $ff
 
 
PUB crc8bitreverse(pBuf, buflen, poly, initial) : crc | i, j
  crc := initial
  repeat i from 0 to buflen - 1
    crc ^= BYTE[noparse][[/noparse]pBuf][noparse][[/noparse]i]
    repeat j from 0 to 7
      if crc & $01
        crc := (crc >> 1) ^ poly
      else
        crc >>= 1

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer

Parallax, Inc.

Timothy D. Swieter · 2007-12-20 06:34

Paul -
I am not a CRC expert.· For a recent product design I had to implement a CRC for a wireless communication.· I programmed the base station which had·a Propeller and my design firm programmed the recevier.· We agreed to use a CRC-8.· I Googgled and read several resources but I admit I don't fully understand that math.· Based on a couple examples I found and an on-line calculator I created the below code.· This works to create a CRC-8 based on the polynomial described in the comments.

PRI crc8(_byte0add, _numbyte) : crc | tmpBit, tmpByte
 
''This routine calculates a CRC-8 byte based on the bytes feed to it
''This calculation uses the polynomial x^8 + x^2 + x + 1 = 1_0000_0111 (yes this is correct)
 
  crc := 0
  repeat tmpByte from 0 to (_numbyte-1)
    crc := crc ^ byte[noparse][[/noparse]_byte0add][noparse][[/noparse]tmpByte]
    repeat tmpBit from 0 to 7
      if (crc & $80) <> 0
        crc := (crc << 1) ^ %1_0000_0111
      else
        crc <<= 1
  crc := crc & $FF

This routine looks very much like the routine you posted except for a few changes in the naming of variables and that my routine is 'written out' a little more than your.· If I remember correctly I built this routine around psuedo code found in a datasheet or appnote for a one-wire chip - I think (my memory is vague).· Note that the polynomial is 9 bits instead of 8 bits, I remember this holding me up.· What polynomial are you using?· What are you using for initial?

Coding first in Spin in then into ASM is so easy with the Prop - I love this aspect of the language.· I like prototyping in Spin and then when I have confidence I optimize it to ASM.·

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter
tdswieter.com

One little spark of imagination is all it takes for an idea to explode

deSilva · 2007-12-20 08:56

Just in case you missd these:

http://www.8052.com/codelib/crc16.zip
http://www.8052.com/codelib/CRC_16.asm
http://www.8052.com/codelib/CRC_16.A51
http://www.atmel.com/dyn/resources/prod_documents/doc1143.pdf

Paul Baker · 2007-12-20 09:36

Figured it out:

PUB crc8bitwise(pBuf, buflen, poly, initial): crc | i,j
  crc := initial
  repeat i from 0 to buflen - 1
    crc ^= [color=red]([/color]BYTE[noparse][[/noparse]pBuf][noparse][[/noparse]i] [color=red]>< 8)[/color]
    repeat j from 0 to 7
      if crc & $80
        crc := (crc << 1) ^ poly
      else
        crc <<= 1
  crc &= $ff
  [color=red]crc ><= 8[/color]

What's in red are the changes made, just needed to spin a few bytes around. Thanks for your input guys.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer

Parallax, Inc.

Timothy D. Swieter · 2007-12-20 09:48

Glad you figured it out Paul. So, what are you cooking up that needs the CRC routines?

Boy, almost every time I review someone elses code I learn something new. Your posts in this thread in particular Paul. There are several things I realize I could code more effeciently and then there is the "><" operator which I didn't realize existed. Thank you!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter
tdswieter.com

One little spark of imagination is all it takes for an idea to explode

Paul Baker · 2007-12-20 11:25

Couple things I've been kicking around, a SNAP protocol layer on top of Beau's high speed serial driver and a high speed native SD driver, both require CRCs in thier implementation.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer

Parallax, Inc.

Nick Mueller · 2007-12-20 11:48

Should you still need the algorithm, I have one in C for the CCITT-CRC (which is 8 bits sorry, 16 bits) and a lot of other Checksum-algorithms and CRCs.

Maybe you can get your hands on the book "Practical Algorithms for Programmers" A. Binstock, J. Rex; Addison Wesley; 1995.
Great book anyhow.

Nick

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Never use force, just go for a bigger hammer!

The DIY Digital-Readout for mills, lathes etc.:
YADRO

Post Edited (Nick Mueller) : 12/20/2007 11:55:20 AM GMT

Paul Baker · 2007-12-20 22:04

Thanks for the offer, the CRC16 CCITT fell together and worked on the first try, because the data and result are piped straight in and out. But the CRC8 and CRC32 implementations used in SNAP require the reversing of bits. I have all routines operating correctly now except the table driven byte-wise CRC32, I have a feeling that error is arising from the fact the CRC32 has an inital starting point which isn't zero. But fiddling with the inital value of the table generation and the byte-wise routine didn't fix it.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Paul Baker
Propeller Applications Engineer

Parallax, Inc.

Nick Mueller · 2007-12-20 22:09

> except the table driven byte-wise CRC32,

This one is also in the book I named.

Nick

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Never use force, just go for a bigger hammer!

The DIY Digital-Readout for mills, lathes etc.:
YADRO

Anyone with CRC experience?

Comments