Fletcher32: is the limit of 360 in Wikipedia wrong?

Question

The Wikipedia article about the Fletcher checksum (currently) says that for Fletcher 32, the sums need to be reduces after 360 steps. However, according to my test, it is enough to reduce after 720 steps. Is the limit of 360 in Wikipedia simply wrong, or did I make a mistake in my test?

Bonus points for any other possible optimization :-) Except for hardcoding the limit.

My test case (Java, but the same applies to C or C#):

public static void main(String... args) {
    byte[] data = new byte[2 * 1024];
    Arrays.fill(data, (byte) 255);
    for (int limit = 1; limit <= 721; limit++) {
        System.out.println("Test limit " + limit);
        for (int i = 0; i < data.length; i += 2) {
            if (getFletcher32(data, i, 1) != getFletcher32(data, i, limit)) {
                System.out.println("Stop at limit=" + limit + " index=" + i);
                return;
            }
        }
    }
}

// bytes: the data
// length: the number of bytes (must be an even number)
// limit: when to reduce the sums (only used for testing)
static int getFletcher32(byte[] bytes, int length, int limit) {
    int s1 = 0xffff, s2 = 0xffff;
    for (int i = 0; i < length;) {
        for (int end = Math.min(i + limit, length); i < end;) {
            int x = ((bytes[i++] & 0xff) << 8) | (bytes[i++] & 0xff);
            s2 += s1 += x;
        }
        s1 = (s1 & 0xffff) + (s1 >>> 16);
        s2 = (s2 & 0xffff) + (s2 >>> 16);
    }
    s1 = (s1 & 0xffff) + (s1 >>> 16);
    s2 = (s2 & 0xffff) + (s2 >>> 16);
    return (s2 << 16) | s1;
}

The test prints:

Test limit 1
Test limit 2
...
Test limit 720
Test limit 721
Stop at limit=721 index=721

Meaning the result is the same for limit 1 up to 720, and only with limit 721 the checksum is different (meaning, it is incorrect).

Answer 1

I realised my mistake now, and see that both Wikipedia and my implementation are correct...

The reason is, the Wikipedia article uses a limit of 360 words (each word two bytes), while my implementation uses a limit of 720 bytes.

As for optimizations: possibly the final reduction step could be simplified a little bit, but that wouldn't change much.

Answer 2

I see I was pretty wrong with my old answer, so I wrote this trivial loop which checks for int overflow:

long s1 = 0xffff, s2 = 0xffff;
for (int n=0; ; ++n) {
    final int a = 0xff;
    final int b = 0xff;
    final int x = (a << 8) | b;
    s2 += s1 += x;
    System.out.format("%4d %08X %08X\n", n, s1, s2);
    if ((s2 & 0xFFFFFFFFL) != s2) break;
}

The output ends with

358 0167FE98 FDD3022C
359 0168FE97 FF3C00C3
360 0169FE96 100A5FF59

which shows us that we must stop before the 360th iteration in order for s2 not to overflow.

---

There's one difference to the presented algorithm. The line

return (s2 << 16) | s1;

should read

return (s2 << 16) | (s1 & 0xffff);

as the original type is uint16_t, but this doesn't matter, because of s1 being small.