Optimizing CRC16 routine.

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