Optimizing CRC16 routine.

[HenrikOlsson]

Hi everyone,
This is kind of a doublepost as I originally put this question as a response in this thread without noticing the thread was in the wishlist section of the forum. Hopefully it gets a bit more attention here.

Allright, I'm working a MODBUS stack for PBP. I found a CRC routine (I think it was in another thread here) which I've modified slightly and it works nicely. The problem is that it is, or seems, quite slow. Here's the current code:

MB_CRC = 65535
MB_k = MB_Buffer_Ptr - 3                   ' Find out where in the array to stop.
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
RETURN

This thing takes 1730 cycles, including a GOSUB and RETURN, to calculate the CRC value for 9 bytes (123456789). In the tread I linked to above Darrel has a, what looks to me, very similar routined which is said to do it in 825 cycles. For reference, here's Darrels 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

As you can see it's very simmilar, it uses another polynominal (which I don't think should make any difference (?)) and it shifts to the left instead of the right so it's another kind of CRC than what I need or I'd use it directly.

Does anyone have any idea why mine is so much slower than Darrels and/or what I might do to speed it up? MODBUS frames can get quite large and currently it takes more than 12000 cycles to go thru a frame of 67 bytes.

Thanks!
/Henrik.

[cncmachineguy]

Not saying I get this whole CRC thing, just looking at the 2 snippits, the biggest thing I see is you have a nested loop and Darrel doesn't. But that seems like it would change things by more than double. (approx difference between the 2)

Try using his poly instead of yours in your code to see if that changes your timing. I don't know if you can just do that, but if so it will eliminate that as a factor.

[HenrikOlsson]

Hi Bert,
I tested with $1021 instead of $A001 as the poly and it changed from 1730 to 1682 cycles - still nowhere nere ~800.

Yes, mine iterates thru the array of 9 bytes (in this case) in one go while Darrels would have to be called 9 times with a new byte in CRC_In each time. I don't think that is what makes it that much slower.

I'm new to this CRC thing as well and don't yet fully understand it enough to try to come with a completely different aproach.

Thanks!
/Henrik.

[cncmachineguy]

What if you combine these 2 lines:

 MB_CRC = MB_CRC >> 1          
 MB_CRC = $A001 ^ MB_CRC

to be this:

 MB_CRC = (MB_CRC >> 1) ^ $A001 ; or try DT's poly here just for consistancy

This would kinda make sense to me as why yours might be ~twice as long, PBP may be creating double code to do it in 2 steps.

[HenrikOlsson]

Hi,
Thank you for your ideas, I appreciate it.

Unfortunately it's the opposite of what you think. Originally I did have those two lines combined but splitting the statement into two increased the performance by ~9% (it went from 1894 to 1730 cycles for the 9 test-bytes) it also saved me 8 bytes of program space - which is secondary but still nice.

/Henrik.

[Mike, K8LH]

Greetings Henrik,

Is there a chance you have a lot of overhead associated with array handling? Have you looked at the assembly language generated by that routine?

I checked out the inner loop using BoostC and found worst case cycle times of 123 cycles in a "for/next" loop and 100 cycles in a "do/while" loop.

Cheerful regards, Mike

  crcword ^= work;         // 123 cycles (BoostC)
  for(char i=0; i<8; i++)  //                      
  { crcword >>= 1;         //
    if(status.C)           //
      crcword ^= 0x0A01;   //
  }

  crcword ^= work; i = 0;   // 100 cycles (BoostC)
  do {                      //
    crcword >>= 1;          //
    if(status.C)            //
      crcword ^= 0x0A01;    //
    i++;                    //
  } while(i.3 == 0);        //

[HenrikOlsson]

Hi Mike,
I'm using TMR1 to measure the execution time of the routine. I just moved the starting and stopping of the timer so it's around the inner FOR-NEXT loop. In other words the timer is started before the inner FOR and stopped after the inner NEXT effectively excluding the array handling of the outer FOR-NEXT loop from the timing.

This time I got 1533 cycles.

So, as far as I can see it is the inner loop that is eating away the time and I still don't understand why. I'll try a DO-WHILE construct instead of the FOR-NEXT and see what I'll get.

Thanks!
/Henrik.

[Mike, K8LH]

... <snip> ... I'm using TMR1 to measure the execution time of the routine ... <snip> ...

Could that be a problem? Do you have anything similar to the MPLAB Simulator Stopwatch?

... <snip>... This time I got 1533 cycles ... <snip> ...

My goodness, that doesn't sound quite right. That's close to what you got when you were processing nine bytes. Could there be a problem with the method you're using to count cycles?

I would expect you to get code similar to the assembler code generated from my BoostC "Do/While" loop;

  crcword ^= work; i = 8;   //
0040  0845  	MOVF crc16_00000_arg_work, W
0041  06B7  	XORWF gbl_crcword, F
0042  3008  	MOVLW 0x08
0043  00C6  	MOVWF crc16_00000_1_i

  do {                      //
0044        label5

    crcword >>= 1;          //
0044  36B8  	LSRF gbl_crcword+D'1', F
0045  0CB7  	RRF gbl_crcword, F

    if(status.C)            //
0046  1C03  	BTFSS gbl_status,0
0047  284C  	GOTO	label6
004C        label6

      crcword ^= 0x0A01;    //
0048  3001  	MOVLW 0x01
0049  06B7  	XORWF gbl_crcword, F
004A  300A  	MOVLW 0x0A
004B  06B8  	XORWF gbl_crcword+D'1', F

  } while(--i);             //
004C  03C6  	DECF crc16_00000_1_i, F
004D  1D03  	BTFSS STATUS,Z
004E  2844  	GOTO	label5
}

[HenrikOlsson]

Hi Mike,
I tried a DO-WHILE construct and I'm quite surprised by the results. I moved the starting and stopping back to where I had it originally and with the DO-WHILE I get 1496 cycles instead of 1730 for the 9 test-bytes. A 67 byte array, previously taking ~12600 cycles now executes in ~10800. Getting there....

Here's the current ASM code:

0012A0                    M _MB_CRC_16
0012A0 6831               M         setf    _MB_CRC
0012A2 6832               M         setf    (_MB_CRC) + 1
0012A4 0E03               M         movlw   003h
0012A6 5C3F               M         subwf   _MB_Buffer_Ptr, W
0012A8 6E42               M         movwf   _MB_k
0012AA 6A40               M         clrf    _MB_i
0012AC                    M L00108
0012AC 0004               M         clrwdt
0012AE 5040               M         movf    _MB_i, W
0012B0 5C42               M         subwf   _MB_k, W
0012B2 A0D8               M         btfss   STATUS, C
0012B4 EF80 F009          M         goto    L00109
0012B8 5040               M         movf    _MB_i, W
0012BA 0F56               M         addlw   low (_MB_Buffer)
0012BC 6EE9               M         movwf   FSR0L
0012BE 0E01               M         movlw   (_MB_Buffer) >> 8
0012C0 6AEA               M         clrf    FSR0H
0012C2 22EA               M         addwfc  FSR0H, F
0012C4 CFEF F013          M         movff   INDF0, T1
0012C8 5013               M         movf    T1,  W
0012CA 1A31               M         xorwf   _MB_CRC, F
0012CC 6A41               M         clrf    _MB_j
0012CE                    M L00110
0012CE 0004               M         clrwdt
0012D0 B641               M         btfsc   _MB_j, 003h
0012D2 EF7D F009          M         goto    L00111
0012D6 0004               M         clrwdt
0012D8 A031               M         btfss   _MB_CRC, 000h
0012DA EF78 F009          M         goto    L00112
0012DE 90D8               M         bcf     STATUS, C
0012E0 3232               M         rrcf    _MB_CRC + 1, F
0012E2 3231               M         rrcf    _MB_CRC, F
0012E4 0E01               M         movlw   low (0A001h)
0012E6 1A31               M         xorwf   _MB_CRC, F
0012E8 0EA0               M         movlw   (0A001h) >> 8
0012EA 1A32               M         xorwf   _MB_CRC + 1, F
0012EC EF7B F009          M         goto    L00113
0012F0                    M L00112
0012F0 90D8               M         bcf     STATUS, C
0012F2 3232               M         rrcf    _MB_CRC + 1, F
0012F4 3231               M         rrcf    _MB_CRC, F
0012F6                    M L00113
0012F6 2A41               M         incf    _MB_j, F
0012F8 D7EA               M         bra     L00110
0012FA                    M L00111
0012FA 2A40               M         incf    _MB_i, F
0012FC A0D8               M         btfss   STATUS, C
0012FE D7D6               M         bra     L00108
001300                    M L00109
001300 0012               M         return

/Henrik.

[Ioannis]

Hi Henrik.

How did you declare MB_i variable? Byte or Word?

Also instead of this:

MB_CRC = 65535
MB_k = MB_Buffer_Ptr - 3                   ' Find out where in the array to stop.
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
RETURN

try this one:

MB_CRC = 65535
MB_k = MB_Buffer_Ptr - 3                   ' Find out where in the array to stop.
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                      
        MB_CRC = MB_CRC >> 1
        If MB_CRC.Bit0 THEN  MB_CRC = $A001 ^ MB_CRC               ' If the LSB is set
                               ' and EXOR it with out polynomial for MODBUS CRC-16 ($A001)
    Next                                   ' Next bit in the byte
NEXT                                       ' Next byte in the frame
RETURN

Ioannis