Talk:Fletcher's checksum

Tip: Anchors are case-sensitive in most browsers.

This article links to one or more target anchors that no longer exist.

[[Endianness#Little|little-endian]] The anchor (#Little) has been deleted by other users before.

Please help fix the broken anchors. You can remove this template after fixing the problems. | Reporting errors

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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?[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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?[edit]

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[edit]

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[edit]

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]

Why not clean up the code at the same time? The source shown here is demented.

This Article is dangerous[edit]

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]

It means that all calculations are performed modulo 256 (or modulo 65,536 for the 16-bit version), so overflow and underflow are both well-defined. DES (talk) 13:29, 17 October 2017 (UTC)[reply]

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

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]

I assume Tempel meant + as you suspect. I'll remove the entire section. DES (talk) 13:36, 17 October 2017 (UTC)[reply]

I've replaced the bogus “optimized” code (which produces different output) with my own thoroughly tested implementation based on the Nakassis paper. DES (talk) 16:39, 17 October 2017 (UTC)[reply]

Please bring back the optimized code which used shifts and adds instead of the % operator. It is useful for implementing fletcher checksums in hardware (ie FPGA), or on embedded processors without hardware division. I strongly disagree with the removal of the hardware friendly implemention. You could simply add a note stating that it disagrees with the % operator for the value of 0x1FFFF % 0xFFFF (which as far as I know is the only value for which it returns an incorrect result). — Preceding unsigned comment added by 73.78.143.185 (talk) 02:04, 24 October 2017 (UTC)[reply]

No. It produces the wrong result. But feel free to create a page for “Checksum that sort of looks like Fletcher's but isn't, really” and put your “optimized” code there. DES (talk) 18:27, 30 October 2017 (UTC)[reply]

Test vectors don't specify endian-ness and padding[edit]

I'm amazed, but pleased, that the example implementations and test vectors in this article haven't fallen foul of Wikipedia's prohibition on Original Research, but that's not what I'm here to talk about.

The test vectors for Fletcher-16 and Fletcher-32 would be more useful if the endian-ness of the conversion of the ASCII characters to 16- and 32-bit blocks were stated and how the given word (vector) has been padded to a whole number of blocks. GrahamDavies (talk) 13:58, 27 April 2018 (UTC)[reply]

I'm working on an implementation of Fletcher-32 for a field firmware update application and my host-side Perl script agrees with the given results, so I can help with that. GrahamDavies (talk) 15:08, 27 April 2018 (UTC)[reply]

A Commons file used on this page has been nominated for speedy deletion[edit]

The following Wikimedia Commons file used on this page has been nominated for speedy deletion:

Quantum Communications (5884515854).jpg

You can see the reason for deletion at the file description page linked above. —Community Tech bot (talk) 00:06, 12 December 2019 (UTC)[reply]