Talk:Fletcher's checksum

It seems to me that the magic constant "360" is subopmtimal. Either it should be changed to "720", as "len" denotes the number of bytes rather than 16-bit words, or, "len" should be changed to denote the number of 16-bit words.

To illustrate this, in the worst case, all 16-bit words on input are equal to 65535. In that case sum2 = 65535 + 2*65535 + 3*65535 ... + 361*65535 = (361*362/2)*65535 = 4282122435 < 4294967296 = 2^32. So we still don't overflow, although the length of the array is 722 bytes in this case. (The sum contains 361 uint16's instead of 360 as sum1 is initialized to 65536).

193.85.150.3 (talk) 15:24, 3 October 2011 (UTC)

Surely an article about Fletcher's checksum should demonstrate the algorithm and not 3 tricks on how to get it fast. It makes it harder to follow the algorithm's purpose and the optimizations are language specific.

Even if the C syntax is used, it should be in the simplest way to illustrate what the algorithm is trying to achieve.

The C code presented operates on a number of 16-bit words, rather than a (possibly odd) number of bytes; this should be noted in the example. The final value is dependent on the endianness of the architecture, this should also be noted. —Preceding unsigned comment added by 217.37.158.157 (talk) 16:16, 20 February 2008 (UTC)

A less complex implementation

I thought this might be clearer, for illustrating the algorithm. I am unsure about its edge-cases for 0xff with respect to one's complement, though. Please test.

uint16_t fletcher8(const uint8_t *d, size_t length) {
    uint16_t a = 0;
    uint16_t b = 0;

    for (size_t i = 0; i < length; i++) {
        a += d[i];
        a = (a & 0xff) + (a >> 8);

        b += a;
        b = (b & 0xff) + (b >> 8);
    }

    return a << 8 | b;
}

I think it's also worth spending time in this article explaining the reduction for one's complement, which is essentially an implementation quirk to work-around using two's complement machines, and not part of the algorithm itself. The algorithm itself assumes one's complement addition exists.

And I agree with the comment above, suggesting the algorithm itself is stated here (perhaps in pseudo-code), rather than presenting optimised implementations. Personally I find those confusing. Kate (talk) 22:58, 12 August 2008 (UTC)

This is original research. The proper role of the article in Wikipedia is to clearly describe the algorithm and its uses, not to try to show the most efficient language-specific implementations, especially ones which explicitly disclaim their possible accuracy.  Xihr  05:41, 13 August 2008 (UTC)

In that case, the article currently consists almost entirely of original research, since it doesn't explain the algorithm in an abstract sense at all: it only provides some implementations, and a few "tips and tricks" for providing efficient implementations.

I think all those implementations ought to go, and either pseudo code provided instead, or a clear and simple implementation (as I've tried to do above) as a previous commenter suggested.

As for accuracy, have you looked at the current implementations? They explicitly state they have different behaviour to the original algorithm, particularly for their ranges. Kate (talk) 15:33, 16 August 2008 (UTC)

The "efficient 8 bit implementation" algo on the wiki gets me different results than my own implementation after reading the rfc or like the implementations described here [1]. It's also difficult to read. But maybe i'm wrong and it's right, so i'm writing here. My suggestion for a pseudocode is like this:

function fletcher16( byte data[] )
{
    byte a = 0;
    byte b = 0;
    for i = 0 to length( data )-1 do
    {
        a = a + data[i]
        b = b + a;
    }
    return concat( b, a );
}

Edit: The difference is probably cause of the 1s complement. Still this article is strange to readMrMuffiny (talk) 08:40, 31 July 2009 (UTC)

An unoptimized version

I've attempted an unoptimized version (based on the code in the optimized version, minus the modulo tricks). I haven't tested or even compiled it though:

uint32_t fletcher32( uint16_t *data, size_t len )
{
        uint32_t sum1 = 0, sum2 = 0;
 
        while (len) {
                --len;

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

                sum1 %= 0xffff;
                sum2 %= 0xffff;
        }
        /* ensure sum1 and sum2 are nonzero */
        if (sum1 == 0) sum1 = 0xffff;
        if (sum2 == 0) sum2 = 0xffff;
        return sum2 << 16 | sum1;
}

This is intended as a partial solution to the problems raised by talk. - 86.172.2.56 (talk) 04:26, 30 November 2009 (UTC)

runxctry's suggestions

I've recently had the privilege of implementing Fletcher's algorithm. This wiki page and help page was invaluable. It was, however, still necessary to pull up Fletcher's original IEEE article, as this page doesn't have enough information. My suggestions are as follows:

• Sorely lacking is a treatment of how to calculate the check bytes.
• The optimized code on the main page needs to be moved to its own section, and small optimizations need to be more clearly described.
• An unoptimized code section that includes the above code (User 86.172.2.56) should be included. It needs to be labelled as one's complement arithmetic. Another version needs to be implemented for two's complement. I'll do it below.

uint32_t fletcher32( uint16_t *data, size_t len )
{
        uint16_t sum1 = 0, sum2 = 0;
 
        while (len) {
                --len;

                sum1 += *data++;
                sum2 += sum1;
        }
        return sum2 << 16 | sum1;
}

dcurtis's suggestions

The main example calculation caption doesn't make sense to me. Shouldn't the check bits actually be 0x03 and 0x04? — Preceding unsigned comment added by Dcurtis (talk • contribs) 14:32, 24 September 2011 (UTC)

Modulo 255 is not the same as And 255

The source code snippets appear to suggest that x%255 is the same as x&0xff which it is not. x%256 would be. — Preceding unsigned comment added by 212.166.112.250 (talk) 15:54, 10 November 2011 (UTC)

Optimization incorrect?

I think the limit of 360 in the optimized example is incorrect, and should be 359. Here's the reasoning:

• Since the code only does partial reduction each outer loop, the starting values for sum1 and sum2 are at most 2×0xffff = 0x1fffe.
• The largest number that can be accumulated in sum2 without wrapping is 65537×0xffff = 0xffffffff
• Assuming the data being summed is all 0xffff, after n iterations, sum1 is (n+2)×0xffff, and sum2 is 0xffff×(n+1)×(n+4)/2.
• The number of multiples of 0xffff in sum2 after n iterations is f(n) = 2+3+...+(2+n) = (n+1)×(n+4)/2. This evaluates to f(359) = 65340 ≤ 65537 < f(360) = 65702.
• If sum1 and sum2 started at 1×0xffff, then the limit would be g(n) = 1+2+...+(1+n) = (n+1)×(n+2)/2, and g(360) = 65341, which would be okay.

The same logic applies to the 8-bit code, where f(20) = 252 ≤ 257 < f(21) = 275. Again, g(21) = 253 ≤ 257.

Since this seems to be solid, I have updated the article. Comments? 71.41.210.146 (talk) 19:56, 28 March 2012 (UTC)

Optimizations that aren't optimizations

Why are the two optimizations given any faster than any other? Modern compilers are much better at optimizing the code to the target platform than any user could. Even more so the "optimized" examples do many more calculations and use obscure C syntax (which does not! change the optimization).

	sum2 += sum1 += *data++;

is no more optimized than

	++data;

	sum1 += *data;

	sum2 += sum1;

and it is worse because it prevents the compiler from doing as much optimization as it could because incrementing the pointer is worse than using an index into an array.

More so the non-optimized example given should not be using 16 bit integers, it should use two 8bit integers and let the overflow occur which does an automatic modulus.