PDA

View Full Version : CRC algorithm



jack
12-22-2012, 03:32 AM
I'm working on reverse-engineering an old file transfer protocol, with
Teensy 2.0.

I found a document which has what's claimed to be the CRC algorithm.

It does in fact work. I can monitor & record transactions, and the
algorithm gives the CRCs observed in the packets exchanged.

There's a line of code in the algorithm that worries me, though, be-
cause I don't fully understand it -

crc^=Byte;

for(i=0;i<8;i++) crc = (crc >> 1) ^ ((crc & 1)!=0 ? polynomial : 0); // ouch :(

Which lives inside a loop which feed it bytes from the packet being received.

I've tried re-stating it, and found this also gives a correct answer -

for ( i = 0; i < 8; i++ ) // ouch re-stated...
{
bit0 = crc & 1;
crc = crc >> 1;

if ( bit0 ) { crc = crc ^ polynomial; }
}

However, it is'nt glaringly obvious to me that the two statements are equivalent.

Can anyone see what I'm missing, or debunk it if it's wrong?

thanks, Jack

PaulStoffregen
12-22-2012, 02:34 PM
They look equivalent to me. One XORs by either the polynomial, or zero (causing no change), the other does the same thing by storing the condition in an explicit temporary variable, and then either does the XOR or skips it.

This is pretty standard CRC stuff, done the simplest and slowest way. A common speedup, which requires more memory, involves using a lookup table rather than looping over 8 bits. You can find a nice implementation in the OneWire library.

Teensy 3.0 also has a fast hardware CRC peripheral, but since you're using Teensy 2.0, it's not available.

jack
12-23-2012, 03:59 AM
Thanks. Having read that, I revisited my earlier calculations & found the error.

n xor 0 = n ... duh... :(

jack
12-23-2012, 12:10 PM
...Teensy 3.0 also has a fast hardware CRC peripheral

Thanks! I'll keep that in mind ...

Nantonos
12-24-2012, 09:45 AM
This may be helpful:

How to configure ARM Cortex-M4 hardware for CRC-16 (http://www.lammertbies.nl/forum/viewtopic.php?t=1838)

also, an example of using hardware CRC in Teensy 3.0 library for HopeRF RFM12B module (https://github.com/tht/T3Libs)

and


Before using the CRC module, you need to activate its clock. By default, all the on-chip peripherals have their clocks disabled, to save power. If you access an unclocked part of the chip, usually the result is a bus error, which effectively crashes your program. You probably need to add this line:


SIM_SCGC6 |= SIM_SCGC6_CRC;from 18th Kickstarter update (http://www.kickstarter.com/projects/paulstoffregen/teensy-30-32-bit-arm-cortex-m4-usable-in-arduino-a/posts/327096)

jack
12-24-2012, 05:31 PM
...This may be helpful...

Yes indeed! Thanks...

Jack

THT
12-25-2012, 05:45 PM
...This may be helpful...

Yes indeed! Thanks...

Jack

Using the hardware CRC unit is quite easy as soon as you've enable the CRC clock and use the correct data types in the CRC macros. I'm the one who asked the question in the already referenced forum and also the writer of the RFM12B library.

For me reveng (http://reveng.sourceforge.net) was very helpful too. It helps to validate all your results and is able to calculate the CRC parameters out of some example data.

So, if you've got a question regarding the CRC unit, just ask.

jack
12-27-2012, 09:02 PM
...So, if you've got a question...

I'll keep that in mind, thanks. Have not yet got to T3s - I will.

Jack

jack
12-27-2012, 09:07 PM
BTW, thanks for the pointer to reveng - Very cool. Just yesterday I banged out
a CRC calculator that runs on my calculator.

Jack