Re: [lwip-devel] Checksum optimizations

[David Empson]

Bill Auerbach wrote:

> In the inet_chksum.c code, there are 6 occurrences of:
>
>    while ((acc >> 16) != 0) {
>      acc = (acc & 0xffffUL) + (acc >> 16);
>    }
>
> Is it not true that the loop can run a maximum of once?

 

If acc is at least 0x1FFFFUL prior to this loop, then it can iterate twice, but never more than twice. The maximum value possible after the first iteration is 0xFFFFUL + 0xFFFFUL = 0x1FFFEUL, so the second iteration (if required) will add 1 to the low order 16 bits and cannot carry.

 

> Wouldn’t this be slightly more efficient?
>
>    if ((acc >> 16) != 0) {
>      acc = (acc & 0xffffUL) + 1;
>    }

 

That is not correct if acc might be greater than 0x1FFFEUL.

 

There are some places in the source code where multiple items have been added to the accumulator prior to executing the while loop to readjust the checksum to fit in 16 bits. If more than one 16-bit value was added to the accmulator then it can exceed 0x1FFFEUL and your code will produce the wrong checksum.

 

The following code is correct in all situations:

 

if ((acc >> 16) != 0) {
 acc = (acc & 0xffffUL) + (acc >> 16);
 if ((acc >> 16) != 0) {
  acc = (acc & 0xffffUL) + 1;
 }
}

 

The first 'if' could be omitted if there is a high probability that it will be true.

 

The while loop is likely to produce smaller code and is more readible, but the unrolled version might be faster.

 

I agree that in the cases where a single item has been added to the checksum (which had already been corrected to 16 bits) then your simplication is possible.

 

The specific cases I noticed:

 

inet_chksum_pseudo and inet_chksum_pseudo_partial use this while loop twice. The first instance (in the main loop iterating through all pbufs) can be simplified but the second one cannot, because multiple items were added to the accumulator prior to correcting it.

 

inet_chksum has a completely unnecessary use of this loop, as you noted, because LWIP_CHKSUM returns a 16-bit value and it is impossible to have a a nonzero value in the high order 16 bits.

 

inet_chksum_pbuf's use of this while loop can also be simplified as per your suggestion.

 

In every other instance, the while loop (or my unrolled version) is necessary, because multiple items have been added to the accumulator.