+ Reply to Thread
Results 1 to 19 of 19
Thread: CRC Calculator Routine

 18th September 2009, 23:14 #1
CRC Calculator Routine
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.

 19th September 2009, 00:58 #2
Is that 2 mS per byte?
Just timed my CRC routines at 4Mhz and it's ~825uS per byte for 16bit Algorithm's, and ~710uS for 8bit 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>DT

 19th September 2009, 03:51 #3
Oh, and I forgot about this ...
This was my first version.
It was for CRC16, but I later found that there are many versions of CRC16.
Even if they have the same "Polynomial".
Might give you some idea's ....Code:CRC VAR WORD CRC_IN VAR BYTE Idx VAR BYTE CRC_Len CON 16 CRC_Poly CON $1021 ; x16 + x12 + x5 + 1 ;CRC16  CRC16: CRC.HighByte = CRC.HighByte ^ CRC_IN FOR Idx = 0 to 7 IF CRC.0(CRC_Len1) THEN CRC = (CRC << 1) ^ CRC_Poly ELSE CRC = CRC << 1 ENDIF NEXT Idx RETURN
But the other program can do any polynomial version, which is probably more than you need.
<br>DT

 20th September 2009, 09:49 #4
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_Len1) THEN
I don't understand the purpose or method of the code in parenthesis.
Thanks,
Tim.

 20th September 2009, 20:37 #5
In the context of that program ...
IF CRC.0(CRC_Len1) THEN
compiles to the exact same thing as ...
IF CRC.15 THEN
And at the assembly level, it's 2 instructions ...
btfss _CRC + 1, 7
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,DT

 20th September 2009, 20:45 #6
Oh shoot, and I just went back and looked at how I timed my CRC routines, and the ~825uS was for a 9byte array with the chars "123456789".
That would have sounded so much better in my first post.
<br>DT

 21st September 2009, 06:03 #7
Darell is it too much asking what CRC stand for?
Al.All progress began with an idea

 22nd September 2009, 01:31 #8
Too much ... nope.
Too little ... maybe.
Cyclic Redundancy Check
http://en.wikipedia.org/wiki/Cyclic_redundancy_check
<br>DT

 22nd September 2009, 08:53 #9
Darrel, thank you for the link.
Al.All progress began with an idea

 22nd September 2009, 09:53 #10
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
Tim.

 8th January 2011, 17:52 #11
Hi,
I'm struggling with this as well. I have the follwing CRC routine working properly:Code: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 CRC16 ($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
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.

 9th January 2011, 10:56 #12
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.

 31st January 2013, 08:28 #13
CRC8 with DT's routine ?
Looking for some confirmation that DT's CRC calculation routine will work with CRC8.
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 CRC8 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
;CRC16 
CRC16:
CRC.HighByte = CRC.HighByte ^ CRC_IN
FOR Idx = 0 to 7
IF CRC.0(CRC_Len1) 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

 1st February 2013, 06:09 #14
Re: CRC8 with DT's routine ?
Confirmation denied!
The 8bit polynomial for x^8 + x^5 + x^4 + 1 would be $31.
And the routine for 8bit CRC's is different.
Code: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
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]
Code:AD 42 CB 16 05 06 00 6C 0E = 87 AD 42 CC 16 05 08 00 6C 0C = 0D
DT

 3rd February 2013, 08:12 #15
Re: CRC Calculator Routine
denied
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

 14th February 2013, 12:21 #16
Re: CRC Calculator Routine
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...06006C0E%0D%0A

 14th February 2013, 17:09 #17
Re: CRC Calculator Routine
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 8bit 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.Code: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
So it's a 16bit 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.
HTHDT

 2nd May 2013, 10:23 #18
Re: CRC Calculator Routine
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

 3rd May 2013, 17:44 #19
Re: CRC Calculator Routine
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?
Similar Threads

Dallas CRC8 Routines
By Tom Estes in forum Code ExamplesReplies: 23Last Post:  8th May 2018, 18:07 
Calculating CRC for Modbus RTU
By tekart in forum mel PIC BASIC ProReplies: 9Last Post:  20th January 2010, 22:42 
CRC Calculations
By timmers in forum mel PIC BASIC ProReplies: 1Last Post:  16th June 2009, 17:10 
Sensirion CRC
By Tom Estes in forum Code ExamplesReplies: 3Last Post:  9th November 2007, 15:09 
Problems with CRC8 Calc in 1Wire
By JohnB in forum mel PIC BASIC ProReplies: 5Last Post:  16th March 2007, 22:01
Bookmarks