CRC Calculator Routine

[timmers]

Having just busted CRC calculations, could we have a neat built in polynomial calculator. With the increasing need for CRC calculations it would save an awful lot of work for someone embarking into data comms or storage projects.

We have written some code for calculating a 16 bit poly and at 4Mhz it takes 2 milliseconds to execute! I am sure this could be halved with some natty code.

Tim.

[Darrel Taylor]

We have written some code for calculating a 16 bit poly and at 4Mhz it takes 2 milliseconds to execute! I am sure this could be halved with some natty code.
Is that 2 mS per byte?

Just timed my CRC routines at 4Mhz and it's ~825uS per byte for 16-bit Algorithm's, and ~710uS for 8-bit ones. Of course they all vary a little depending on the polynomial, initial value and whether there's a final XOR or bit reversal or not.

For the most part ... A little less than half. :)
<br>

[Darrel Taylor]

Oh, and I forgot about this ...

This was my first version.
It was for CRC-16, but I later found that there are many versions of CRC-16.
Even if they have the same "Polynomial".

Might give you some idea's ....

CRC VAR WORD
CRC_IN VAR BYTE
Idx VAR BYTE
CRC_Len CON 16
CRC_Poly CON $1021 ; x16 + x12 + x5 + 1

;-----CRC-16 -----------------------------------------------------
CRC16:
CRC.HighByte = CRC.HighByte ^ CRC_IN
FOR Idx = 0 to 7
IF CRC.0(CRC_Len-1) THEN
CRC = (CRC << 1) ^ CRC_Poly
ELSE
CRC = CRC << 1
ENDIF
NEXT Idx
RETURN


That's actually faster than my previous measurements.
But the other program can do any polynomial version, which is probably more than you need. :)
<br>

[timmers]

Hi Darrel,
Its 2mS for the whole CRC routine. I simply toggle a pin at the start of the subroutine and again at the exit. It is working through 8 or so bytes to calculate the CRC value.

Out of interest, could you expand upon the line :-
IF CRC.0(CRC_Len-1) THEN
I don't understand the purpose or method of the code in parenthesis.

Thanks,
Tim.

[Darrel Taylor]

In the context of that program ...

IF CRC.0(CRC_Len-1) THEN

compiles to the exact same thing as ...

IF CRC.15 THEN

And at the assembly level, it's 2 instructions ...

&nbsp; btfss _CRC + 1, 7
&nbsp; goto TestFailed

This allows the CRC length to be changed via a constant, with the least amount of code.
And gets around the desire to use a variable or constant as the bit number.

IF CRC.CRC_Len THEN ; This notation doesn't work.
<hr>
The CRC.0(x) notation tells PBP to treat the variable as a BIT array, and is discussed in these threads.

Bits, Bytes Words and Arrays (Melanie)
http://www.picbasic.co.uk/forum/showthread.php?t=544

Indexing Port Pins (Bruce)
http://www.picbasic.co.uk/forum/showthread.php?t=3753

hth,

[Darrel Taylor]

Oh shoot, and I just went back and looked at how I timed my CRC routines, and the ~825uS was for a 9-byte array with the chars "123456789".

That would have sounded so much better in my first post. :o
<br>

[aratti]

Darell is it too much asking what CRC stand for?

Al.

[Darrel Taylor]

Darell is it too much asking what CRC stand for?

Al.
Too much ... nope.
Too little ... maybe. :)

Cyclic Redundancy Check
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
<br>

[aratti]

Darrel, thank you for the link.

Al.

[timmers]

Darrel,

Thanks for explaining that, you are a mine of information. I would have just used -
IF CRC.15 THEN
CRC =CRC *2 'shift left one bit

You obviously know pbp intricately, and maybe need more time in the pub! I would certainly buy you a few beers:D

Tim.

[HenrikOlsson]

Hi,
I'm struggling with this as well. I have the follwing CRC routine working properly:

MB_CRC = 65535 ' Initialize CRC value
MB_k = MB_Buffer_Ptr - 3 ' Find out where in the array to stop.

T1CON = 1

FOR MB_i = 0 to MB_k ' Iterate thru the frame, stop before the last two bytes which are the actual CRC.
MB_CRC = MB_CRC ^ MB_Buffer[MB_i] ' Bitwise EXOR the current low byte of the CRC "value" with the byte in the buffer

FOR MB_j = 0 to 7 ' Cycle thru the low byte of the CRC value
If MB_CRC.Bit0 THEN ' If the LSB is set
MB_CRC = MB_CRC >> 1 ' We shift CRC on bit to the right....
MB_CRC = $A001 ^ MB_CRC ' and EXOR it with out polynomial for MODBUS CRC-16 ($A001)
ELSE
MB_CRC = MB_CRC >> 1 ' If the LSB is not set we simply shift CRC one bit to the right.
ENDIF
NEXT ' Next bit in the byte

NEXT ' Next byte in the frame

T1CON = 0

RETURN

This works properly for what I'm doing (MODBUS) but is painfully slow. Darrel said he got 825us for 9 bytes @4Mhz. This thing takes 2837 cycles for 9 bytes....

Giving it 67 bytes and it it takes ~14000 cycles to return the 16 bit CRC value.

To my naked eye this looks fairly close to the Darrels routine but this uses another polynomial (which I can't see making any difference time wise) and it's "reversed".

I've rearanged a couple of things, splitting statements in two etc which has gained me a bit of performance but now I seem to be stuck. Again, it works properly which is the most important thing but can anyone tells me what the h..l is taking so long ;-)

Thanks!
/Henrik.

[HenrikOlsson]

Hello again,
Seems like I was a bit off in my timings as I was actually feeding the CRC routined more bytes than I thought (I measured the time for the incomming AND outgoing frames) so it's a bit better but still not near Darrels numbers.

I've moved the starting and stopping of the timer so it's "around" the GOSUB that calls the CRC routine so the numbers below includes jumping to and from the routine.

If I feed it the same 9 bytes is in Darrels example (123456789) it takes 1730 cycles to execute while Darrels routine does it half of that time. For a 67 byte array it takes ~12600 cycles, obviously depending sligthly on what's "in" the bytes.....

If anyone has any pointer to how I could increase the performance of this I'm all ears.

Thanks!
/Henrik.

[mr.sneezy]

Looking for some confirmation that DT's CRC calculation routine will work with CRC-8.

This is two typical samples of what I have incomming from a Fine Offset WH2081 weather station transmitter.
FF AD 42 CB 16 05 06 00 6C 0E 87
FF AD 42 CC 16 05 08 00 6C 0C 0D

FF is a preamble, and the last byte is CRC-8 using the polynomial x^8 + x^5 + x^4 + 1 (which I think becomes the constant $131 for calculations).
The middle 9 bytes are data, and used for the CRC byte sent by the TX.

Do I have it right that DT's code could be used directly if the CRC_Len and CRC_poly constants are changed as below ?

CRC VAR WORD
CRC_IN VAR BYTE
Idx VAR BYTE
CRC_Len CON 8
CRC_Poly CON $131 ; x^8 + x^5 + x^4 + 1

;-----CRC-16 -----------------------------------------------------
CRC16:
CRC.HighByte = CRC.HighByte ^ CRC_IN
FOR Idx = 0 to 7
IF CRC.0(CRC_Len-1) THEN
CRC = (CRC << 1) ^ CRC_Poly
ELSE
CRC = CRC << 1
ENDIF
NEXT Idx
RETURN

If so, is it just a matter of setting the CRC_IN byte to each value of the nine data bytes in turn while looping through CRC16: each time, the wanted result being the value of CRC after the ninth loop ?
Or is there stuff to be done after each result of subroutine CRC16 ?

Thanks if anyone can confirm that for me before I try to hack my receiver code to pieces.
Martin

[Darrel Taylor]

Confirmation denied!

The 8-bit polynomial for x^8 + x^5 + x^4 + 1 would be $31.
And the routine for 8-bit CRC's is different.



CRC VAR BYTE
CRC_IDX VAR BYTE
CRC_IN VAR BYTE
CRC_Poly CON $31

CRC8:
FOR CRC_IDX = 0 to 7
IF (CRC.7 ^ CRC_IN.7) THEN
CRC = (CRC << 1) ^ CRC_Poly
ELSE
CRC = CRC << 1
ENDIF
CRC_IN = CRC_IN << 1
NEXT CRC_IDX
RETURN

This test code ...

X VAR BYTE

CRC = 0
FOR X = 0 TO 8
LOOKUP X,[$AD, $42, $CB, $16, $05, $06, $00, $6C, $0E], CRC_IN
HSEROUT [HEX2 CRC_IN," "]
GOSUB CRC8
NEXT X
HSEROUT ["= ",HEX2 CRC,13,10,13,10]

CRC = 0
FOR X = 0 TO 8
LOOKUP X,[$AD, $42, $CC, $16, $05, $08, $00, $6C, $0C], CRC_IN
HSEROUT [HEX2 CRC_IN," "]
GOSUB CRC8
NEXT X
HSEROUT ["= ",HEX2 CRC,13,10,13,10]


Returns these results ...

AD 42 CB 16 05 06 00 6C 0E = 87

AD 42 CC 16 05 08 00 6C 0C = 0D

[mr.sneezy]

denied :eek:

Oh no not again.

I took my best shot at it based on looking at some online CRC calculators and the CRC Wiki and thought it might work for what I wanted.
Now that I've been corrected I'll test the CRC routine when I get back to my coding shortly.

Thanks Darrel,
Martin

[mr.sneezy]

Hey Darrel,

If you have time, could you show me how you went from a polynomial to the constant used in the code ?
I was using this web based calculator to try to understand it, but I'm missing something, as I can't match your $31.
http://ghsi.de/CRC/index.php?Polynom=100110001&Message=AD42CB160506006C0E%0D%0A

[Darrel Taylor]

The highest bit of a polynomial is assumed to be 1, and is not included in the value used in the formula.
It's presence in the polynomial indicates the length of the final CRC result.

With x^8 + x^5 + x^4 + 1 ...
The x^8 indicates that it is an 8-bit CRC, and it's bit position is not used.

From there, you just stick the bits in a value to be used in the formula.

x^8 + x^5 + x^4 + 1

7 6 5 4 3 2 1 0
------------------------
0 0 1 1 0 0 0 1
-------------------------
$ 3 1
The polynomial for plain CRC16 is x^16 + x^15 + x^2 + x^0
So it's a 16-bit CRC, the x^16 is not used, and the poly value is $8005.
Note that + x^0 is the same as + 1.

The calculator you pointed to forces you to put the highest bit in the constant so it knows the length of the CRC.
Otherwise, it's the same value ... $31.

HTH

[mr.sneezy]

Hi Darrel,

I can now also confirm your CRC calculation code works well. Finally got back to my weather station receiver coding and added the CRC routines. No problems at all, works as advertised.

Part of the delay was obtaining a bigger PIC to expand my code. Eventually got some PIC16F1509's.

Regards,
Martin

PS. I saw your 'lost youth' sig message above. I think I did see your youth recently, but it was moving farther away from you at the time, and doesn't look like it's going to be coming back any time soon :P

[Darrel Taylor]

Great!
I'm glad it you got it working.

And that's also great you saw my Youth. That means it's still around somewhere.
Maybe I should offer a reward?

http://www.pbpgroup.com/files/SIGIMG/lostyouth.gif