[Note to nonNative English PICLIST members - the subject is an allusion to
the children's story "Goldilocks and the Three Bears"]

We often find ourselves embedding PICs in systems that require relatively
reliable communications over some sort of serial link.

There is a whole gamut of message security coding techniques that have been
used over the years. At the low end we start with 'send-it-and-pray'
followed by various sorts of additive and xor checksum routines. As
complexity increases we move through various types of CRC algorithms and
finally into the territory of some very sophisticated forward error
correction (FEC) schemes.

In the world of PICs we are often caught between the too-cold porridge of
inadequate but simple checksum algorithms and the too-hot porridge of
complex and expensive (in time and/or space) CRC algorithms.

With this message I am posting some code I use to provide an 8-bit CRC using
a 4-bit-at-a-time table-driven method. This algorithm sits comfortably
between slower/smaller bit-at-a-time methods and faster/larger
byte-at-a-time methods.

Note that an 8-bit CRC is quite adequate for the short messages typically
sent by PIC applications. Extension to a 16-bit CRC won't catch many
additional probable errors for most types of error patterns on a serial
link.

This PIC code was derived from a Fortran77 conversion of an ancient Z80
implementation of what was referred to as a 'Bose-Chaudhuri' CRC.

--- here is the code ---

; Define a macro to update a crc register:
;
; Updates the CRC stored in 'crcreg' (specified in the macro call)
; with the four LSBits of W
;
; Uses the register 'temp' (specified in the macro call) as a
; temporary.
;
; There is no need to clear the upper bits of W before using
; the macro.
;
; PCLATH must be set to the page containing the routine
; 'crc_table_lookup' before using the macro.
;
; Each macro invocation always uses exactly 13 cycles, this is
; a useful property in isochronous code
;
; On exit:
;    'crcreg' is updated to the new CRC value
;    'temp' is trashed
;    W contains the updated CRC

CRC_UPDATE macro crcreg,temp

; --  Get table entry based on LSBits of current
; -- CRC and 4 bits to be included in CRC
    xorwf   crcreg,W
    call    crc_table_lookup

; -- Save table value
    movwf   temp

; -- Get MSBits of old CRC in LSBits of W
    swapf   crcreg,W
    andlw   0x0F

; -- Merge with value from table
    xorwf   temp,W

; -- Save updated CRC
    movwf   crcreg
 endm

; Define the subroutine used to lookup the CRC table value for
; 4 bits of data. Each call to this routine consumes exactly 7 cycles,
; including call and return.
;
; On entry:
;    LSBits of W are index of table entry
;    MSBits of W are ignored
; On exit:
;    W is table entry

crc_table_lookup:
    andlw   0x0F
    addwf   PCL,F
    dt 0x00,0x98,0x83,0x1B
    dt 0xB5,0x2D,0x36,0xAE
    dt 0xD9,0x41,0x5A,0xC2
    dt 0x6C,0xF4,0xEF,0x77

;;===========
; using the routine is relatively simple.
;

; --- The transmit logic looks like this:

; 1: Preinitialize the CRC shift register to the polynomial (which is 0xD9)

    movlw    0xD9
    movwf    my_crcreg

; 2: For each byte of data, process each of the two nibbles

[assume 'out_byte' is outgoing byte]

; -- include LSBits in CRC
    movf    out_byte,W
    CRC_UPDATE    my_crcreg,temp01

; -- include MSBits in CRC
    swapf    out_byte,W
    CRC_UPDATE    my_crcrec,temp01

; 3: Send the accumulated CRC over the link

    movf    my_crcreg,W
    call      whatever_to_send_the_byte

; --- The receive logic looks like this:

; 1: Preinitialize the CRC shift register to the polynomial (which is 0xD9)

    movlw    0xD9
    movwf    my_crcreg

; 2: For each byte of data, process each of the two nibbles

[assume 'in_byte' is incoming byte]

; -- include LSBits in CRC
    movf    in_byte,W
    CRC_UPDATE    my_crcreg,temp01

; -- include MSBits in CRC
    swapf    in_byte,W
    CRC_UPDATE    my_crcrec,temp01

; 3: After all data has been received, check the resulting CRC

    movf    my_crcreg,F
    skpz
    goto    crc_error

Bob Ammerman
RAm Systems
(contract development of high performance, high function, low-level
software)

--
http://www.piclist.com hint: PICList Posts must start with ONE topic:
[PIC]:,[SX]:,[AVR]: ->uP ONLY! [EE]:,[OT]: ->Other [BUY]:,[AD]: ->Ads