2
\$\begingroup\$

I was playing with TCP/IP, and came across this 16 bit checksum function:

unsigned short csum(unsigned short *ptr,int nbytes) 
{
    register long sum;
    unsigned short oddbyte;
    register short answer;

    sum=0;
    while(nbytes>1) {
        sum+=*ptr++;
        nbytes-=2;
    }
    if(nbytes==1) {
        oddbyte=0;
        *((u_char*)&oddbyte)=*(u_char*)ptr;
        sum+=oddbyte;
    }

    sum = (sum>>16)+(sum & 0xffff);
    sum = sum + (sum>>16);
    answer=(short)~sum;

    return(answer);
}

There were a few things that bothered me about it:

  1. Not using fixed size types (though the author himself stated in the code short was expected to be 16 bits for it to work)
  2. If the input buffer was too large (I believe larger than exactly 65535 bytes) the checksum wouldn't be correct, since the most significant 2 bytes of the checksum variable would overflow.

So I ended up rewriting it:

uint16_t checksum16(void *data, unsigned int bytes){
    uint16_t *data_pointer = (uint16_t *) data;
    uint32_t total_sum;

    while(bytes > 1){
        total_sum += *data_pointer++;
        //If it overflows to the MSBs add it straight away
        if(total_sum >> 16){
            total_sum = (total_sum >> 16) + (total_sum & 0x0000FFFF);
        }
        bytes -= 2; //Consumed 2 bytes
    }
    if(1 == bytes){
        //Add the last byte
        total_sum += *(((uint8_t *) data_pointer) + 1);
        //If it overflows to the MSBs add it straight away
        if(total_sum >> 16){
            total_sum = (total_sum >> 16) + (total_sum & 0x0000FFFF);
        }
        bytes -= 1;
    }

    return (~((uint16_t) total_sum));
}

Since it adds the carry bit right after the sum, you can feed it with a buffer of any size with no worries of the final checksum being incorrect.

After some small tests, the results seem to be matching. Do you guys see any possible bug while using that function? Or any further improvement?

I thought maybe I could add a statement to check if the number of bytes was larger than 65535, and only add the carry on each iteration if it was, otherwise adding the whole sum of carries at the end. That would improve the performance on the cases where the size of the buffer doesn't reach that limit (true to any IP packet, since the header length field is 16 bits, limiting the packet size to 65535).

\$\endgroup\$
  • 1
    \$\begingroup\$ I found this webpage to be a good read for optimizing IP checksums. \$\endgroup\$ – JS1 Jan 31 '17 at 2:54
  • \$\begingroup\$ just a general remark: you put the constant on the left side to prevent unwanted assignment in case one = is forgotten. You could catch that with a compiler warning -Wparentheses and just write it the more logical way with the constant on the right. That makes the code more readable and still prevents such a typo. \$\endgroup\$ – Frode Akselsen Feb 2 '17 at 2:03
4
\$\begingroup\$

Since this checksum function is only used for TCP packets, there is no need for supporting packets larger than 65535 bytes. Rather than adding needless overflow checks, you should restrict the bytes parameter by making that a uint16_t.

Note that both the original code and your improvement only work on big endian implementations, unless some outside code byteswapped the whole TCP packet, in which case the code only works on little endian implementations. The + 1 for accessing the last byte makes the latter more probable. This + 1 was not present in the original code, so chances are high that you introduced a bug. Did you test with odd-sized packet length?

You should make the spacing of the code consistent, either by removing all spaces around binary operators (not recommended) or inserting spaces at the appropriate places. Currently it is a mixture of both.

Since you don't modify the incoming buffer, you should declare that. Make the data const void *.

You don't need to write 1 == bytes, since any decent compiler will emit a warning if you would ever accidentally use a single = here. You should write the natural bytes == 1 instead, or if you fear typos, bytes > 0.

The bytes -= 1 is unnecessary and can be left out.

\$\endgroup\$
  • \$\begingroup\$ Actually the original checksum function works on both little endian and big endian. You just get a native endian checksum as a result, which is fine because normally you would compare against hdr->checksum which would also be native endian. The new one looks like it has a problem with the last byte. \$\endgroup\$ – JS1 Jan 31 '17 at 2:50
  • \$\begingroup\$ Now that is a nice design decision by the TCP inventors. Now that you mentioned that and I tried it with some code, I dimly remember that I learned that some ten years ago. \$\endgroup\$ – Roland Illig Jan 31 '17 at 3:13
  • \$\begingroup\$ You nailed it on the odd bytes bug, when you posted the answer I was ripping my hair trying to figure it. Still didn't came with a fix, was thinking total_sum += ((uint16_t) (*((uint8_t *) data_pointer)) << 8);, but it isn't working yet. I was reading the checksum RFC and @JS1 is right, the checksum design makes it byte order independent, except you'll get the result in the host endianess. I'll try to fix the bug and make it work on both little and big endian machines (mine is little endian). \$\endgroup\$ – IanC Jan 31 '17 at 8:01
  • \$\begingroup\$ Once the code is updated, should I post it on a different answer? \$\endgroup\$ – IanC Jan 31 '17 at 8:03
  • 1
    \$\begingroup\$ I strongly advise against making the bytes parameter uint16_t. It is too easy to make a mistake here. Just use size_t for buffer sizes everywhere; there is virtually no downside to that. Pros: also works for things that are not TCP packets, no warnings from the compiler about narrowing conversions. \$\endgroup\$ – G. Sliepen Jan 31 '17 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.