The May issue of “Dr Dobb’s Journal” focused on data communications and included articles on checksums. One article covered Fletcher’s Checksum, an algorithm faster than CRC and just as reliable as CRC, except it handles smaller blocks than CRC. CRC checksum will catch a 2 bit error in a 65,535 bit message, where as Fetcher will catch a 2 bit error in a 2040 bit message. The one thing I noticed about the algorithm was how easy it was to implement.
Fletcher’s Checksum is really two 8-bit checksums. This makes the algorithm easy to implement on any platform. Plus you only have to deal with two bytes instead of a 32 bit number, which would involve determining what order the 32 bit number is spread across bytes.
Below is a SuperBasic version of the checksum program. The function calc_fletcher calculates the Fletcher Checksum for a string of characters, calculates the “opposite” checksum, and appends it to the end of the string.
What I mean by “opposite” checksum is this: after the checksum is calculated (the two bytes), two other bytes are calculated so that when the whole message is processed at the receiving end, the checksum will equal 0. If the message is equal to say 10, the -10 is added to the message to bring the whole thing to 0.
The check_fletcher function calculates the Fletcher Checksum on the message (string) and returns it. If it returns 0, then the message was received with no errors, else there was some error in the message.
Those that are interested in 680XX assembly programming should check out the article. The text shows the algorithm in both C and 68000 assembly. The author then goes on to optimize both the C code and 68000 assembly code. The program goes from 17 lines of 68000 code to 4 lines of 68000 code.
** Fletcher's Checksum
** Structured SuperBasic program
**
string1$ = "This is test of Fletcher's Checksum"
string2$ = calc_fletcher$ (string1$)
results = check_fletcher(string2$)
IF results = 0 THEN
PRINT "Checksum is OK"
ELSE
PRINT "Checksum is Bad"
DEFine FuNCtion calc_fletcher$ ( str$ )
LOCal x, sum1, sum2, check1, check2, length
sum1 = 0
sum2 = 0
length = LEN(str$)
FOR x = 1 TO length
sum1 = ( sum1 + CODE(str$(x)) ) MOD 255
sum2 = ( sum1 + sum2 ) MOD 255
NEXT x
check1 = 255 - (( sum1 + sum2 ) MOD 255 )
check2 = 255 - (( sum1 + check1 ) MOD 255 )
str$ = str$ & CHR$(check1) & CHR$(check2)
RETURN str$
END DEFine calc_fletcher
DEFine FuNction check_fletcher ( str$ )
LOCal sum1, sum2, x, length
sum1 = 0
sum2 = 0
length = LEN(str$)
FOR x = 1 TO length
sum1 = ( sum1 + CODE(str$(x)) ) MOD 255
sum2 = ( sum1 + sum2 ) MOD 255
NEXT x
RETURN sum1+sum2
END DEFine check_fletcher