Implementing some CRC16 routines and checksums

Here is a program to calculate CRC-16 on a 16Cxx. The resulting CRC value is identical to that calculated by common archive programs, such as ZOO. Fast table-based CRC calculators for this polynomial are available as C source.

----- C source --------------------------------------------------------

unsigned CRC;

unsigned crc_16(char c)
{
   int i,j;

   for(i=0;i!=8;c>>=1,i++)
   {
      j=(c^CRC)&1;
      CRC>>=1;

      if(j)
         CRC^=0xa001;
   }
   return CRC;
}


----- 16CXX source ----------------------------------------------------

                Temp     = 0x20
                Count    = 0x21
                CRC_High = 0x22
                CRC_Low  = 0x23

loop            macro   reg,label
                decfsz  reg
                goto    label
                endm

                movlw   "h"
                call    CalcCRC
                movlw   "e"
                call    CalcCRC
                movlw   "l"
                call    CalcCRC
                movlw   "l"
                call    CalcCRC
                movlw   "o"
                call    CalcCRC
Halt            goto    Halt

                ; result=0x34d2 (you can check that with ZOO)

----- CRC subroutine --------------------------------------------------

CalcCRC         movwf   Temp                ; about 125 cycles on average
                movlw   8
                movwf   Count

CRC_Loop        movf    CRC_Low,w
                xorwf   Temp,w
                clrc
                rrf     CRC_High
                rrf     CRC_Low
                andlw   1
                bz      CRC_Skip

                movlw   0xa0
                xorwf   CRC_High
                movlw   0x01
                xorwf   CRC_Low

CRC_Skip        rrf     Temp
                loop    Count,CRC_Loop
                return

Thanks to Frank Vorstenbosch for this

Another alternative

This routine from Andrew Warren uses the standard X.25 (and XMODEM) polynomial: x^16+x^12+x^5+1.

It's not the fastest possible, but it does the job and doesn't take much code. It takes your message, one bit at a time (you have to write the code for that and put it at the LOOP label, since I don't know how your data's organized), and exits with the CRC in CRCHI:CRCLO. When I originally posted this code on the Microchip BBS, I wrote it on-line, so I haven't assembled or tested it:


       CRCHI   EQU     some register
       CRCLO   EQU     another register

               CLRF    CRCHI
               CLRF    CRCLO

               ;Append 16 "0"s to your message here.

       LOOP    ;If there are no more bits in your message, go to
               ;"DONE".  Otherwise, left-shift the next bit of your
               ;message into the carry here.

               RLF     CRCLO
               RLF     CRCHI

               SKPC
               GOTO    LOOP

               MOVLW   00100001B
               XORWF   CRCLO
               MOVLW   00010000B
               XORWF   CRCHI

               GOTO    LOOP

       DONE    ;The CRC is in "CRCHI" and "CRCLO".

Even simpler checksums

> A checksum can be just the sum of all the data '1' s in the bytes of the string. The generic way to do this is:

   check_sum = 0;
   for each byte in the string
      check_sum = check_sum + sum of bits in byte

There are several ways to count the number 1's in a byte. The three routines shown below are a few examples. The first is the one you typically see in programs that count bits; every bit is individually checked to see if it is 0 or 1. Everytime you get a 1, increment a counter. You don't want to use this routine.

The second routine only loops one time for each bit that is set; e.g. 00101000B only will loop twice. It's based on a clever algorithm that can clear the right most bit that is set in a byte.

The third one is based on a look up table. Here, the byte is broken into two nibbles and the look up table contains 16 entries. Each entry corresponds to the number of bits set in the offset of the table.

buffer0         equ     0x20
bits_counted    equ     0x21
a_byte          equ     0x23

        ORG     0               ;Reset Vector

        MOVF    a_byte,W
        CALL    RR_bitcount


        MOVF    a_byte,W
        CALL    bitcount

        MOVF    a_byte,W
        CALL    look_up_bits

stay    goto    stay

;*****************************************************
;RR_bitcount
;  Brute force shift and count.

RR_bitcount
        MOVWF   buffer0
        CLRF    bits_counted

RR1     CLRC
        RRF     buffer0,F       ;Get LSB and put in the carry
        SKPNC                   ;If LSB (i.e. C) is set
          INCF  bits_counted,F  ;then count it
        MOVF    buffer0,F
        SKPZ
          GOTO    RR1

        RETURN

;*****************************************************
;bitcount
;
; This algorithm loops one time for each bit that is set.
;It's based on an algorithm that deletes the right most
;bit in a byte. If the byte is 'b' then the algorithm is:
;  b = b & (b-1)
; for example if
;         b = xxxx1000
;       b-1 = xxxx0111
; b & (b-1) = xxxx0000   ;The right most bit of b is deleted
;
;This algorithm comes from a book titled "Efficient C", by
;Thomas Plum and Jim Brodie. They credit Kernighan and Ritchie
;for the original insight.
;
;     Inputs:  W - contains the byte whose bits need counting
;    Outputs:  bits_counted - # of bits that were set in W
;Memory Used:  buffer0

bitcount
        MOVWF   buffer0         ;Save a copy
        CLRF    bits_counted    ;

BC1     MOVF    buffer0,W       ;Get the byte. (affects Z too)
        SKPNZ                   ;If no more bits are set
          RETURN                ;  then we're done
        INCF    bits_counted,F  ;Found a bit
        DECF    buffer0,F       ;"b-1"
        ANDWF   buffer0,F       ;b = b & (b-1) Delete right most bit
        GOTO    BC1

;*****************************************************
;look_up_bits
;
; This routine breaks the byte into nibbles and then counts
;the number of bits in each nibble (via a look up table).
;

look_up_bits

        MOVWF   buffer0
        CLRF    bits_counted

        ANDLW   0x0f
        CALL    look_up
        ADDWF   bits_counted,F

        SWAPF   buffer0,W
        ANDLW   0x0f
        CALL    look_up
        ADDWF   bits_counted,F
        RETURN
look_up
        ADDWF   PCL,F

        RETLW   0  ;0
        RETLW   1  ;1
        RETLW   1  ;2  has only one bit set
        RETLW   2  ;3  has two bits set
        RETLW   1  ;4  ...
        RETLW   2  ;5
        RETLW   2  ;6
        RETLW   3  ;7
        RETLW   1  ;8
        RETLW   2  ;9
        RETLW   2  ;a
        RETLW   3  ;b
        RETLW   2  ;c
        RETLW   3  ;d
        RETLW   3  ;e
        RETLW   4  ;f
        END

For random data, the look up table is by far the fastest: 13 cycles.

The number of cycles the "bitcount" routine takes is 5 + 7*number of bits that are set i.e. between 5 and 61 cycles, or on average about 33 cycles. While this is slower than the look up table, it uses less code space. A typical compromise.

Thanks to Scott Dattalo for this