Optimizing CRC16 routine.

[HenrikOlsson]

Hi everyone,
This is kind of a doublepost as I originally put this question as a response in this thread (http://www.picbasic.co.uk/forum/showthread.php?t=11790) 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.

[Mike, K8LH]

The inner loop starts at label "L00110" and uses about 18 instruction cycles (worst case) each loop iteration for a whopping total of right around 144 cycles per byte processed.

I have not check the rest of the code. I must get back to my studies.

Cheerful regards, Mike

[cncmachineguy]

Hi Henrik,
here is the snippit I am testing:


Main: 'DO WHATEVER YOU WANT HERE
tmr1=0
t1con = 1
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
t1con = 0
stopnow:
goto stopnow



This takes 169 cycles according to TMR1 setup as you see here. I have tried with both $A001 and $1021. Both are the same. Does this fall in line with what you have?

BTW, MPLAB stopwatch reports the same

Next I think I will try out DT's snippet

[Mike, K8LH]

I just realized that PBP assembler code is using two word "goto" instructions for those short branches instead of one word "bra" instructions. That makes it worst case 20 cycles instead of 18 cycles per interation through the inner loop (160 cycles per byte). Ouch!

[HenrikOlsson]

Bert,
That is exactly like I had it when trying to exclude the outer array handling loop from the timing. I ran 9 bytes thru and got ~1530 cycles. 1530/9=170 cycles per byte and your test shows 169 - so that matches pretty well. I DID get a slight difference when I changed the poly and I guess that depends on the actual value of the byte going thru the routine, if you run the 9 byte sequence 123456789 thru it you should see a slight difference between the two polynomial values.

Mike,
So obviously BoostC compiles this to faster code but doesn't the BoostC compiled code you posted use GOTO as well?

Question is why there's such a difference between Darrel's code and the one I'm using. The poly itself does make a slight difference, I've verified that but it's still way off. I haven't actually verified the claimed 825us (I've no reason to doubt it) but I'll do that tonight just to make sure.

Thanks a lot guys, I appreciate the help!
/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

[Mike, K8LH]

Mike,
So obviously BoostC compiles this to faster code but doesn't the BoostC compiled code you posted use GOTO as well?

I posted 16F1827 code. A slightly unfair comparison because 18F devices don't have a "lsrf" instruction.

I didn't realize you were using an 18F until you posted your assembler output, and so I tested the following code which is similar to yours, for an 18F in BoostC;


MB_CRC ^= work; //
for(MB_j=0; MB_j<8; MB_j++) //
{ if(MB_CRC.0) //
{ MB_CRC >>= 1; //
MB_CRC ^= 0xA001; //
}
else //
{ MB_CRC >>= 1; //
}
} // Next bit in the byte

Here's the BoostC output which uses "bra" instructions and runs in about 115 cycles (worst case);


0008 label1
0008 500A MOVF gbl_work, W
000A 1A05 XORWF gbl_MB_CRC, F
000C 6A09 CLRF gbl_MB_j
000E label2
000E 0E08 MOVLW 0x08
0010 6009 CPFSLT gbl_MB_j
0012 D7FA BRA label1
0014 A005 BTFSS gbl_MB_CRC,0
0016 D008 BRA label3
0018 90D8 BCF STATUS,C
001A 3206 RRCF gbl_MB_CRC+D'1', F
001C 3205 RRCF gbl_MB_CRC, F
001E 0E01 MOVLW 0x01
0020 1A05 XORWF gbl_MB_CRC, F
0022 0EA0 MOVLW 0xA0
0024 1A06 XORWF gbl_MB_CRC+D'1', F
0026 D003 BRA label4
0028 label3
0028 90D8 BCF STATUS,C
002A 3206 RRCF gbl_MB_CRC+D'1', F
002C 3205 RRCF gbl_MB_CRC, F
002E label4
002E 2A09 INCF gbl_MB_j, F
0030 D7EE BRA label2

[Mike, K8LH]

Mike,
So obviously BoostC compiles this to faster code but doesn't the BoostC compiled code you posted use GOTO as well?

Please forgive me if it seems I was suggesting one compiler is better than another. I'm just trying to help you characterize loop timing but I don't have PBP.

Cheerful regards, Mike

[HenrikOlsson]

Mike,
Not at all - at least I didn't read it like that and your help is much appreciated! I'm not that good at assembler though (hence the need for PBP ;-) ) Sorry for not mentioning I was using an 18 series PIC, I should've thought about that.

Ioannis,
MB_i is declared as a BYTE.

At this point the best I've got is (was) this:

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

MB_j = 0

DO WHILE MB_j.3 = 0
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
MB_j = MB_j + 1
LOOP
NEXT ' Next byte in the frame
RETURN
This works and does the 9 byte test-array in 1496 cycles which is faster than with the FOR-NEXT loop I originally had. I then tried changing the meat of it to:

DO WHILE MB_j.3 = 0
MB_CRC = MB_CRC >> 1
If MB_CRC.BIT0 THEN MB_CRC = $A001 ^ MB_CRC
MB_j = MB_j + 1
LOOP
This runs a little bit faster, 1394 cycles, but it calculates the wrong CRC value. This is because, the shifts is done before checking BIT0 while in the working code it checks BIT0 THEN shifts and XOR's (or not).

Since the shift right command uses the RRCF instruction which shifts thru the CARRY flag I tried:

DO WHILE MB_j.3 = 0
MB_CRC = MB_CRC >> 1
If STATUS.0 THEN MB_CRC = $A001 ^ MB_CRC 'Check carry, XOR if set.
MB_j = MB_j + 1
LOOP
This runs in 1414 cycles and produces the correct CRC value. Can anyone see any potential issues with doing it like this?

All in all we've gone from 1730 to 1414 cycles, that's a ~22% increase - not bad! I wonder what more we can squeeze out of it? ;-)

Thanks guys!
/Henrik.

[Ioannis]

I am pretty sure I put the shift inside the loop.

OK, why Darrel's routine is faster? Maybe is the shift? Can it be that Left Shift is faster than Right?

I see no other obvious reason.

Interresting.

Ioannis

[HenrikOlsson]

I am pretty sure I put the shift inside the loop
Absolutely, but shifting before checking bit0 is different from checking bit0 before shifting ;-)

I haven't yet tried Darrels version but I have looked at the ASM code it compiles to and as far as I can see it's now "longer" than what my current code compiles to. I'm actually starting to doubt it'll do the 9 byte test sequence in 825 cycles. Darrel, are you there?

Thanks!
/Henrik.

[Bruce]

Run Darrels' example through MPSIM with the stopwatch to see if it really takes only 825 cycles to process 9 bytes through his CRC routine.

Yours looks pretty darn tight as-is.