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. — Preceding unsigned comment added by 71.56.235.30 (talk) 01:00, 29 September 2013 (UTC)[reply]

I agree with 71.56.235.30. You can use sagemath code to demonstrate it (http://sagecell.sagemath.org/). Barrypp (talk) 05:34, 31 March 2014 (UTC)[reply]

   @interact
   def _(i=(300..400)):print "%d~0x%x"%((i+2)*(i+1)/2,0xffff*(i+2)*(i+1)/2)

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]

comparison to DJB2?

The DJB2 string hashing algorithm (http://www.cse.yorku.ca/~oz/hash.html) is a position-dependent algorithm that can also be used as a high-performance checksum. Is it worth a mention in the article? — Preceding unsigned comment added by Yoyoyvr (talk • contribs) 19:40, 26 April 2014 (UTC)[reply]

I don't know about a comparison, it might be a good idea, but certainly a "See also" section with it would be a good idea.Yb2 (talk) 05:41, 13 October 2015 (UTC)[reply]

Hashes and checksums have different goals and properties and are not interchangeable, thus a comparison between Fletcher and DJB2 is inappropriate. DES (talk) 15:13, 13 October 2015 (UTC)[reply]

Hex

Is there any good reason that all the numbers are in hex format? It doesn't add anything that I can see, but it does add a layer of obfuscation, especially for newcomers.Yb2 (talk) 05:33, 13 October 2015 (UTC)[reply]

If you know enough to understand the technical part of the article, you know enough to understand hexadecimal notation. DES (talk) 14:51, 13 October 2015 (UTC)[reply]

Licence

This page contains a number of C implementations. It would be useful to clarify the licence terms, e.g. any authors who wish to be attributed. 81.136.177.66 (talk) 11:08, 5 April 2016 (UTC)sequoia2009[reply]

This Article is dangerous

This is the original description of the 16 bit Fletcher checksum from the referenced document RFC 1146:

"The 8-bit Fletcher Checksum Algorithm is calculated over a sequence of data octets (call them D[1] through D[N]) by maintaining 2 unsigned 1's-complement 8-bit accumulators A and B whose contents are initially zero, and performing the following loop where i ranges from 1 to N:

       A := A + D[i]
       B := B + A

It can be shown that at the end of the loop A will contain the 8-bit 1's complement sum of all octets in the datagram, and that B will contain (N)D[1] + (N-1)D[2] + ... + D[N].

The octets covered by this algorithm should be the same as those over which the standard TCP checksum calculation is performed, with the pseudoheader being D[1] through D[12] and the TCP header beginning at D[13]. Note that, for purposes of the checksum computation, the checksum field itself must be equal to zero.

At the end of the loop, the A goes in the first byte of the TCP checksum and B goes in the second byte.

Note that, unlike the OSI version of the Fletcher checksum, this checksum does not adjust the check bytes so that the receiver checksum is 0."

This is in the past the main implementation, because it's the simplest and fastest one to calculate. This is important for implementation on poor HW plattforms, where the fletcher checksum is a good alternative for a CRC, but only when no divisions are needed. So it makes no sense discussing the best modulus as this generates different checksums. The modulus is dictated by the framework requirements. It's important to mention that the modulus for simplest and original implemention for a 16 bit sum is 256 and for a 32 bit sum is 65536.

In the meantime this article has produced in many cases wrong and incompatible or partial impelemtations, as for example in the famous tool SRecord. Therefore this article is extremly harmful and damaging, as many people have lost much time in finding out where the reasion is for their problems with fletcher. Especially the examples are dangerous, because there is no explanation for this set of problems concering compatibility. Everybody reading this article is thinking your examples are generating a compatible checksum for all purposes, which is not right. This should be clarified!!! — Preceding unsigned comment added by 91.103.115.13 (talk) 14:11, 13 July 2016 (UTC)[reply]

The article is correct. For reference, please read Fletcher's original paper, keeping in mind the difference between ones' complement and two's complement. The only ambiguity in the paper (which I haven't seen resolved anywhere else) is that it does not address padding. DES (talk) 07:59, 14 July 2016 (UTC)[reply]

Can anyone explain what the RFC could possibly have meant by an "unsigned 1's-complement 8-bit accumulator"? I don't know of any sense in which a storage location can be regarded as both unsigned and 1's-complement at the same time. The concepts of 1's-complement and 2's-complement refer exclusively to how negative numbers are stored and do not apply to unsigned storage. I'm pretty sure the text "1's-complement" is extraneous as Fletcher's checksum calculations never involve negative values. 98.247.224.9 (talk) 05:57, 16 October 2017 (UTC)[reply]

Overview for "2K - 1 optimized" should use + (plus) not | (binary or)

The section shows "(sum & 255) | (sum >> 8)" - I understand "|" as "binary or". And if I got that right, then that line is technically wrong. Instead, it should read "(sum & 255) | (sum >> 8)", as it can also be seen in the code examples, as well as empirical testing that proves that the calculated checksums are only correct if + instead of | is used. Agreed? Tempel (talk) 11:56, 30 April 2017 (UTC)[reply]

Agreed. Note that both versions produce an incorrect result, they're just incorrect in different ways. Not much of an optimization if you need to exchange checksums with other implementations... DES (talk) 12:20, 5 May 2017 (UTC)[reply]

In which case "(sum & 255) + (sum >> 8)" is incorrect? --Cactus26 (talk) 06:48, 27 June 2017 (UTC)[reply]

Unless I've had a stroke tonight, this comment must be in error too. It says that "(sum & 255) | (sum >> 8)" is wrong and should be "(sum & 255) | (sum >> 8)" (the exact same string) instead. I'm pretty sure I know what the second string was meant to be, but just in case I DID just have a stroke, I'll refrain from shooting my mouth off. 98.247.224.9 (talk) 06:06, 16 October 2017 (UTC)[reply]