Talk:Fletcher's checksum

Computing Start‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

It seems to me that in n iterations you sum n+1 terms, from 2 through 2+n. So I'd say that in the above calculation, you'd have to have f(n) = 3+4+...+(2+n) = n×(n+5)/2. The results are off by 2 from yours, but the inequalities still hold, so I tend to agree with the modification to the article. And thank you for pointing out your reasoning. Martin von Gagern (talk) 16:38, 21 November 2012 (UTC)[reply]

The value should be 360, not 359. The assumptions above are not correct.

After 360 iterations, the maximum value of sum1 is 0x168FE97. It is never possible for sum1 to begin an iteration with a value of 0x1FFFE.
After 360 iterations, the maximum value of sum2 is 0xFF3C00C3. In which case, the start value for sum2 is 0xFFFF.
A slightly worse result for the starting value of sum2 is if the final value is 0xFF3BFFFF. In which case the start value for sum2 is 0x1FF3A.
Theoretically, the largest value for sum2 is 0xFFFFFFFF. However, in this algorithm it cannot attain a value higher than 0xFF3C00C3.
The assumptions were faulty, the derived equations are also faulty.
It only takes a few minutes to paste the code into a C file and demonstrate that 360 does not overflow, but 361 does overflow.

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

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

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. Ergzay (talk) 21:41, 21 October 2012 (UTC)[reply]

Confusing - Choice of modulus

I found the article very confusing, until I reached the second paragraph of the Fletcher-16 section. Alarm bells were going off in my head. I'd bet my experience isn't unique; I propose moving this paragraph up to where the selection of modulus is first discussed, and 255 is mentioned.--Elvey (talk) 08:43, 30 December 2012 (UTC)[reply]

Section "Example calculation of the Fletcher checksum" makes no sense

The section "Example calculation of the Fletcher checksum" makes no sense. First of all, what type of Fletcher checksum is this? Is it Fletcher-16? If it is Flether-16, then the result does not match the result of the C code in a later section. Also, the C code makes a lot more sense to me than the English description and table presented in "Example calculation of the Fletcher checksum". I think the C code is correct, and the section "Example calculation of the Fletcher checksum" is either incorrect or is using an algorithm that is not specified. I am not sure so I will not change anything.
Fluoborate (talk) 00:42, 28 May 2013 (UTC)[reply]

Thanks for the suggestions

I've tried to make it somewhat more clear. Runxctry (talk) 20:39, 28 May 2013 (UTC)[reply]
The example actually covers the procedure of calculating the checksum bytes . The Fletcher-16 C-code covers checking the checksum ( result should be 0 ) but it doesn't cover calculating the check bytes. Runxctry (talk) 20:53, 28 May 2013 (UTC)[reply]