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.