How to perform a CHECKSUM for data integrity (BYTE ORDER)

Question

Some time ago I required a function to perform a checksum to test data integrity while exchanging datagrams over internet. Those days I found this function and just copied/pasted and used it.

Checksum (void* buf, int bufsize) {
    register int            sum    = 0;
             word           answer = 0;
    register word           *w     = (word*) buf;
    register int            nleft  = bufsize;

    while (nleft > 1) {
        sum += *w++;
        nleft -= 2;
    }

    if (nleft == 1) {
        *(byte*)(&answer) = *(byte*)w;
        sum += answer;
    }

    sum = (sum>>16) + (sum&0xFFFF);
    sum += (sum>>16);
    answer = ~sum;
    return answer;
}

Today I am working on another program that requires checksum to ensure data integrity, but this time I wanted to see how it works and have one doubt.

The algorithm sums all the words of the data buffer, then adds the carries (high word, if any) to the sum and finally negates the sum (one's complement), so it is the checksum value.

My concrete questions are:

1. Are the words from the buffer expected to be in little or big endian? My intuition tells me that the word bytes should be in BIG ENDIAN (by convention) so the checksum is the same for any machine, but this algorithm simply sums the values (on a x86 platform - little endian), what if the other side is a big endian platform? Would it still work if I sum the byte values inverted for little endian and directly for big endian?

2. If the buffer size is odd, the last byte is added directly to the sum, but is it added just as a value OR as the LOW ORDER byte of a word (considering that the following byte is 0 - HIGH ORDER byte in little endian)?

It is for a simple communication protocol with checksum support but must ensure that it will work for any platform independently of its architecture.

Answer 1

Are the words from the buffer expected to be in little or big endian?

You can't know without a specific protocol in mind. The endianess of the protocol is sometimes called "network endianess". Traditionally most protocols use big endian, but there's no guarantees of that.

If the buffer size is odd, the last byte is added directly to the sum, but is it added just as a value OR as the LOW ORDER byte of a word (considering that the following byte is 0 - HIGH ORDER byte in little endian)?

Doesn't really matter, it will be bad for error detection either way - it will fail miserably for most double-bit errors. I would strongly suggest to use CRC instead: one of the standard CRC-16 or CRC-32 depending on data size.

Answer 2

1. Are the words from the buffer expected to be in little or big endian?

For networking (the "payload" of any packet sent or received over a network using any protocol); the buffer always contains octets (bytes), and the octets always arrive in the same order they were sent (there is no "byte order" issue).

Before software uses networking to send data over a network it converts something (e.g. a structure in a high level language) into a buffer of octets. This is called "serialization", and is necessary to avoid all kinds of portability disasters (not just "endianess", but things like compiler/implementation specific structure padding, floating point format differences, character set differences, etc).

After software receives data from a network it converts the buffer of octets into something (e.g. a structure in a high level language). This is called "de-serialization". It involves 3 purposes:

• sanity checks (trying to make sure that you received what you think you should have received)
• authorization (trying to make sure that sender is correct, and isn't a malicious attacker)
• converting the buffer of octets back into something (e.g. a structure in a high level language).

Neither of these things (serialization and de-serialization) are part of the networking itself - they're "before networking" and "after networking" and not "in the middle of networking".

Note that (based on your questions) you've assumed that the buffer is a high-level structure and failed to serialize/de-serialize; so your code (including your checksum) is broken and will fail (and probably not just because of "endianess").

2. If the buffer size is odd, the last byte is added directly to the sum, but is it added just as a value OR as the LOW ORDER byte of a word (considering that the following byte is 0 - HIGH ORDER byte in little endian)?

Yes.

Note that the main part of the checksum calculation (that incorrectly assumes that "buffer of octets" are words) will break due to "endianess" (if sender and receiver have different endianess, the checksum check "will" (see note) fail for all messages larger than 1 octet). The simple way to avoid that is to use "sum of bytes" (instead of "sum of words"). A better way to avoid that is to a more sophisticated checksum (e.g. CRC-32, which is used by TCP).

Note: with a 16-bit checksum there's at least 1 chance in 65536 that the checksum will pass accidentally due to luck alone; and the "sum of anything" approach is susceptible to various failures (e.g. if the sender or receiver got the message size wrong and there's lots of zeros on the end that shouldn't be there, then the "incorrect zeros" won't effect the checksum). This means that when sender and receiver use the same endianess there's a "worse than 1 in 65536" chance that the checksum will pass when it shouldn't; and it also means that when sender and receiver use different endianess and the message is larger than 1 octet there's a "better than 1 in 65536" chance that the checksum will pass when it "should".