CRC Calculator Routine


Closed Thread
Results 1 to 19 of 19
  1. #1
    timmers's Avatar
    timmers Guest

    Default 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.

  2. #2
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    Quote Originally Posted by timmers View Post
    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>
    DT

  3. #3
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    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 ....
    Code:
    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>
    DT

  4. #4
    timmers's Avatar
    timmers Guest


    Did you find this post helpful? Yes | No

    Default

    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.

  5. #5
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    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,
    DT

  6. #6
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    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.
    <br>
    DT

  7. #7
    Join Date
    May 2008
    Location
    Italy
    Posts
    825


    Did you find this post helpful? Yes | No

    Default

    Darell is it too much asking what CRC stand for?

    Al.
    All progress began with an idea

  8. #8
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default

    Quote Originally Posted by aratti View Post
    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>
    DT

  9. #9
    Join Date
    May 2008
    Location
    Italy
    Posts
    825


    Did you find this post helpful? Yes | No

    Default

    Darrel, thank you for the link.

    Al.
    All progress began with an idea

  10. #10
    timmers's Avatar
    timmers Guest


    Did you find this post helpful? Yes | No

    Default

    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.

  11. #11
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,516


    Did you find this post helpful? Yes | No

    Default

    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 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.

  12. #12
    Join Date
    Oct 2005
    Location
    Sweden
    Posts
    3,516


    Did you find this post helpful? Yes | No

    Default

    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.

  13. #13
    Join Date
    Nov 2008
    Posts
    96


    Did you find this post helpful? Yes | No

    Default CRC-8 with DT's routine ?

    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

  14. #14
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default Re: CRC-8 with DT's routine ?

    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.

    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
    This test code ...
    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 ...
    Code:
    AD 42 CB 16 05 06 00 6C 0E = 87
    
    AD 42 CC 16 05 08 00 6C 0C = 0D
    DT

  15. #15
    Join Date
    Nov 2008
    Posts
    96


    Did you find this post helpful? Yes | No

    Default 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

  16. #16
    Join Date
    Nov 2008
    Posts
    96


    Did you find this post helpful? Yes | No

    Default 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

  17. #17
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default 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 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.
    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
    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
    DT

  18. #18
    Join Date
    Nov 2008
    Posts
    96


    Did you find this post helpful? Yes | No

    Default 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

  19. #19
    Join Date
    Jul 2003
    Location
    Colorado Springs
    Posts
    4,959


    Did you find this post helpful? Yes | No

    Default 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

  1. Dallas CRC8 Routines
    By Tom Estes in forum Code Examples
    Replies: 23
    Last Post: - 8th May 2018, 19:07
  2. Calculating CRC for Modbus RTU
    By tekart in forum mel PIC BASIC Pro
    Replies: 9
    Last Post: - 20th January 2010, 23:42
  3. CRC Calculations
    By timmers in forum mel PIC BASIC Pro
    Replies: 1
    Last Post: - 16th June 2009, 18:10
  4. Sensirion CRC
    By Tom Estes in forum Code Examples
    Replies: 3
    Last Post: - 9th November 2007, 16:09
  5. Problems with CRC8 Calc in 1Wire
    By JohnB in forum mel PIC BASIC Pro
    Replies: 5
    Last Post: - 16th March 2007, 23:01

Members who have read this thread : 2

You do not have permission to view the list of names.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts