On Sun, Jun 27, 2004 at 07:58:25PM +0000, Robert Reimiller wrote:
> I missed the beginning of this thread, but one simple way to detect
> errors is a fletcher's checksum. I use an 8 bit fletcher's checksum
> (which really results in 2 bytes) in CNP:
>
> www.certsoft.com/cnp11.pdf
>
> There is also a 16 bit version for longer messages. Example of a routine
> in PIC assembler:
> ;
> ; Calculate Checksum, xtemp has new byte. Returns with w=xtemp
> ;
> dofletch movf    xtemp,w
>         addwf   crch
>         btfsc   status,C
>         incf    crch
>         movf    crch,w
>         addwf   crcl
>         btfsc   status,C
>         incf    crcl
>         movf    xtemp,w                 ; restore w
>         return
>
> Or, in C18:
>
> void update_fletch (byte b)
> begin
>
>   crch += b ;
>   if (STATUSbits.C)
>     crch++ ; /* propogate 1's complement carry */
>   crcl += crch ;
>   if (STATUSbits.C)
>     crcl++ ;
> end
>
> In both cases crch and crcl are cleared to zero before proceeding.

I read up on Fletcher's and one of its sucessors Adler-32. They make sense
from a conceptual standpoint:

* Compute a checksum of the message.
* Then compute a checksum of the checksums.
* Keep both sums in range by dividing by a prime(Adler32)/
  nearly prime(Fletcher's) number and tracking the remainders.
* Send both checksums as the checksum for the message.

Fletcher's is small, fast, easy to compute. But it's weak because the 255
divisor has factors, which means that changes in certain bytes of the message
can go undetected. John Payson has posted several discussions on the subject
in comp.realtime about these weaknesses. He points out that Fletcher would
be much much stronger if the divisor were prime. The closest prime number
to 256 is 251. So an much improved Fletcher's can be had by computing the
sum modulo 251.

Now of course we don't want to divide by 251 anymore than we want to divide
by 255. The idea is the same: when the sum overflows adjust the result. The
carry marks a divide by 256 but takes 5 extra from the remainder of the divide
by 251. So you have to add it back. However there is also 5 difference between
the modulo range of 251 and a byte. So if the value is above 250, we have to
subtract 251. But because of the natural modulo 256 this can be accomplished
by adding 5 (i.e. 252 + 5 -> 257 % 256 -> 1 which is the same as 252 % 251).

So there are 4 ranges of numbers we need to be concerned with:

0-250 with no carry   : Do nothing
251-255 with no carry : Add 5
0-245 with carry      : Add 5
246-255 with carry    : Add 10

Now I think that it can be ordered so that with a carry you add 5 and then
if the current value is greater than 250 then add another 5. I think that
takes care of all the conditions. So the modified C code would be

crch += b;
if (STATUSbits,C)
   crch += 5; /* OK if it overflows */
if (crch > 250)
   crch += 5; /* Will definitely overflow. Still OK */

crcl += crch;
if (STATUSbits,C)
   crcl += 5; /* OK if it overflows */
if (crch > 250)
   crcl += 5; /* Will definitely overflow. Still OK */

This is much stronger than the original Fletchers as long as the packet size
is less than 251 bytes. And with almost all PIC communication, it'll be less
than 251 bytes.

The John Payson post that talks about the issues is here:

http://tinyurl.com/2o3ce

So I think that finally close to being satisfied. An 8 bit Fletcher's with
a modulo 251 remainder is strong and is easy to understand. Also since it's
just an series of adds (and two compares) it should cost very little
computationally. Also it doesn't require tables for fast computation like
CRC does.

I'll implement it in my test harness when I get a chance.

I've learned a lot about checksums in the last 48 hours. This discussion
has be really cool.

BAJ

--
http://www.piclist.com hint: The PICList is archived three different
ways.  See http://www.piclist.com/#archives for details.