Bit shifting in internet checksums.

Question

This is almost certainly a very silly question, but for some reason I'm having trouble with internet checksum calculations. All of the algorithms basically look something like this:

WORD chksm(WORD *startpos, WORD checklen){
ulong sum = 0;
WORD answer = 0;

while (checklen > 1)
{
 sum += *startpos++;
 checklen -= 2;
}

if (checklen == 1)
{
 *(BYTE *)(&answer) = *(BYTE *)startpos;
 sum += answer;
}

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

return answer;}

I'm clear on everything except for the line:

sum += (sum >> 16);

It looks like the line immediately before it adds the top 16 bits to the bottom 16 bits, leaving all zeroes in the top 16 bits. If that's the case, then wouldn't sum >> 16 now be equal to zero? And if so, why is that line there?

Or am I (likely) just having a complete mental failure today?

Answer 1

You are almost right.

The high 16 bits could have been 1 due to a carry.

For example, FFFF + FFFF => 1FFFE, or perhaps FFFF + 1 => 10000.

Answer 2

I thought that a ulong was 32 bits wide which means that:

sum = (sum >> 16) + (sum & 0xffff)
sum += (sum >> 16);

Adds the top sicteen bits and bottom sisteen bits together. And then the next line makes sum the result of the top sixteen bits; which could have a one in it due to a carry operation.