Jim Main wrote:
>
> I need to attach checksums to strings outgoing, and check checksums attached
> to strings received.
>
> The checksum being the sum of all the data '1' s in the bytes of the string.
>
> Is there an easy way to do this??
>

Jim,

The generic way to do what you want is:

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

As far as easy... Take a whack at it! I'll just address a few different ways to
count bits.

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.

Anyway, this is part of the answer to your question.


Scott