Fletcher bug report

[sierrafoxtrot]

Bug report from Colen Garoutte-Carson back in December 31st, 2014 via email.

Hi. I was combing through the internet looking for some fletcher32 algorithms to compare my own against, for correctness. Surprisingly, this particular algorithm has a lot of bad versions out there.

Your fletcher32.cc in SRecord 1.64 appears to be close to correct, but a slight change has been made that breaks it, making it no longer the fletcher32 algoritm.

From your response to someone opening a bug on it(?) :

So the important thing to note is that data is read 8 bits at a time and then assembled into 16bit values before loading into the accumulators. The algorithm is otherwise uncanged.
<<<

Note that your implementation does not actually assemble 8-bit bytes into a 16-bit accumulator. It sums one 8-bit byte at a time, into the simple sum1 register. Because you adding only 8-bits at a time between rounds of sum2, you are getting a completely different value than someone who properly advanced 16-bits per round of sum2 (half as frequently).

Note the following line from the Wikipedia page:

sum2 += sum1 += *data++;

In their case, data is a uint16_t, so this reads 16-bits, and the increment advances 16-bits. To correctly handle 8-bit bytes, you would need to accumulate 2 at a time into a 16-bit integer (to be endian-safe) and pass that accumulator in place of "data++" to the above line. Instead, your equivalent code is:

    sum1 += *data++;
    sum2 += sum1;

In your case, data is a "const unsigned char*". Yet, the rest of the function is unchanged?(!?). So, functionally, your implementation is generating something very different from a fletcher32 result.

Note the smoking gun: You preserved the 360 constant. (If you initialize to 0xFFFF, you need 359 instead, Wikipedia has since been corrected. 360 assumes the sums are init'ed to zero). Since you are only adding an 8-bit value at a time, 360 is a completely irrelevant number. The number of rounds you would need to make before you could overflow a 32-bit (16x2) sum2, would be closer to 5802. Take a look at Adler32, which functions in a similar way to what you have created. Adler32 processes 8-bit bytes into a 32-bit result directly, mods by 65521, and overflows after 5552.

[sierrafoxtrot]

Part way through a code review but completed a comparison of output with an independent implementation in GRISHNOV's Fletcher_checksum. Output is identical for both Fletcher 16 & 32 but I"ll keep digging.