fletcher32 calculates wrong results

[daniel-mohr]

Sorry, but there is a bug. It comes in with 33afeaa5984d800a14aec638c3645b9450183f87. I do not see quickly the problem. I will try to look at it later.

Using the following sketch I get not the same result calculating using fletcher32 or Fletcher32. I also implemented a very basic own one which gives the same result as Fletcher32.

The output on an Arduino Nano (ATmega 328P):

Fletcher32 Checksum: 2998243001 != 2998243001 != 2998243001
Fletcher32 Checksum: 2182261859 != 2182261859 != 2182261859
Fletcher32 Checksum: 1982769044 != 1982769044 != 1982769044
Fletcher32 Checksum: 1978223466 != 1978223466 != 1978223466
Fletcher32 Checksum: 531239522 != 531239522 != 531239522
Fletcher32 Checksum: 4106226194 != 4106226194 != 4106226194
Fletcher32 Checksum: 4198634381 != 4198634381 != 4198634381
Fletcher32 Checksum: 165916914 != 165851378 != 165916914 <<<<<<<<<< ERROR
Fletcher32 Checksum: 4272779253 != 4272779253 != 4272779253
Fletcher32 Checksum: 3515832009 != 3515832009 != 3515832009
Fletcher32 Checksum: 4117326111 != 4117326111 != 4117326111
Fletcher32 Checksum: 1850499566 != 1850499566 != 1850499566
Fletcher32 Checksum: 122596904 != 122531368 != 122596904 <<<<<<<<<< ERROR
Fletcher32 Checksum: 605022322 != 605022322 != 605022322
Fletcher32 Checksum: 3315359866 != 3315359866 != 3315359866
Fletcher32 Checksum: 31964681 != 31899145 != 31964681 <<<<<<<<<< ERROR
...

The output on an Arduino MKRZERO (SAMD21):

Fletcher32 Checksum: 780509277 != 780509277 != 780509277
Fletcher32 Checksum: 150721686 != 150656150 != 150721686 <<<<<<<<<< ERROR
Fletcher32 Checksum: 478771874 != 478706338 != 478771874 <<<<<<<<<< ERROR
Fletcher32 Checksum: 3512242870 != 3512242870 != 3512242870
Fletcher32 Checksum: 3690339436 != 3690339436 != 3690339436
Fletcher32 Checksum: 657660082 != 657594546 != 657660082 <<<<<<<<<< ERROR
Fletcher32 Checksum: 4198794805 != 4198794805 != 4198794805
Fletcher32 Checksum: 3146081874 != 3146081874 != 3146081874
Fletcher32 Checksum: 3517298731 != 3517298731 != 3517298731
Fletcher32 Checksum: 1271430246 != 1271430246 != 1271430246
Fletcher32 Checksum: 1152627280 != 1152627280 != 1152627280
Fletcher32 Checksum: 4121123470 != 4121123470 != 4121123470
Fletcher32 Checksum: 1401975901 != 1401975901 != 1401975901
Fletcher32 Checksum: 2114453526 != 2114519061 != 2114453526 <<<<<<<<<< ERROR
...

And here the used sketch:

#include "Arduino.h"

#include <Fletcher.h>
#include <Fletcher32.h>

#ifdef ARDUINO_ARCH_AVR
#define MAX_LEN 1024
#else
#define MAX_LEN 16384
#endif

uint32_t myfletcher32(uint16_t *data, const uint16_t length)
{
  uint32_t s1 = 0;
  uint32_t s2 = 0;
  for (uint16_t i = 0; i < length; i++)
  {
    s1 = (s1 + data[i]) % ((((uint32_t) 1) << 16) - 1);
    s2 = (s2 + s1) % ((((uint32_t) 1) << 16) - 1);
  }
  return (s2 << 16) | s1;
}

void test_fletcher32() {
  const uint16_t max_len = MAX_LEN / 2;
  uint16_t values[max_len];
  for (uint16_t i = 0; i < max_len; i++) {
    values[i] = (uint16_t) random(0, ((uint32_t) 1) << 16);
  }
  Fletcher32 checksum_instance;
  checksum_instance.begin();
  for (uint16_t i = 0; i < max_len; i++) {
    checksum_instance.add(values[i]);
  }
  uint32_t checksum1 = checksum_instance.getFletcher();
  uint32_t checksum2 = fletcher32(values, max_len);
  uint32_t checksum3 = myfletcher32(values, max_len);
  Serial.print("Fletcher32 Checksum: ");
  Serial.print(checksum1);
  Serial.print(" != ");
  Serial.print(checksum2);
  Serial.print(" != ");
  Serial.print(checksum3);
  if ((checksum1 != checksum2) || (checksum2 != checksum3)) {
    Serial.println(" <<<<<<<<<< ERROR");
  } else {
    Serial.println();
  }
}

void setup()
{
  Serial.begin(115200);
  while (!Serial);
}

void loop() {
  test_fletcher32();
  delay(1000);
}

[daniel-mohr]

The bit shift is not the same as modulo. It just corrects a small overflow. So using it together with delay the modulo does not work.

You mentioned this typo already in fletcher16.

[RobTillaart]

The bit shift is not the same as modulo. It just corrects a small overflow. So using it together with delay the modulo does not work. You mentioned this typo already in fletcher16.

Yes, It only works for small overflows, and the sum of (s1 & xxxx) + (s1 >> bits) should not be beyond the modulo number. So it should work in the add() in the classes, as it is done after every addition.

Would it be possible to add your test code to find the bug to the unit test ? In the test folder?

[RobTillaart]

@daniel-mohr Do you expect the 64 bit version to work? It will take a lot of time (I mean a LOT) to test this as the loop takes long to "overflow".

The optimization for the 64 bit function is hard to test and probably called not that much. The gain is minimal given that the loop itself takes far more time.

So can you roll back the 64 bit version too?

[daniel-mohr]

Yes, good idea to put it in as unit test. I never did this. But I will try this later.

Oh, sorry, I skipped fletcher64. But I expect it's the same. Let us see if I can somehow manage to check this as a unittest.

[RobTillaart]

unit tests are pretty straightforward in this, just compare a value with the function return.

To make the output 'debug able' do not put more than ~20 or so tests in a single unit test (or print some divider whatever).

[RobTillaart]

Note I updated your sketch above to get syntax highlighting.
Add cpp after the three backquotes