Checksums (again)

Wed, 30 Mar 1988 06:44:04.83 EST

Having come in at only at the tail end of this discussion, I don't know
if anyone has pointed out that, assuming a packet length of < 2**16-1
words, the checksum algorithm can wait to add back all the carry bits
until *after* the checksum loop is completed. I.e.:

while (computing-the-checksum) {
    checksum += buf[i++];
checksum = checksum && 0xFFFF + (checksum >> 16);
checksum = checksum && 0xFFFF + (checksum >> 16); /* sic - the first carry */
                                                  /* "add back" may cause */
                                                  /* a second carry out */

Using this technique, and unrolling the loop to do 32 additions in line,
I was able to reduce the average number of instructions per short word
from ~10 to 3+ on an IBM RT PC (since the RT is a register-to-register
RISC CPU, 3 instructions per short word is the minimum to load the word,
add to the checksum and increment the pointer). This optimization
reduced the time spent in the RT 4.2BSD checksum routine from 10% to
about 1% on large TCP data transfers, with a resulting increase in
throughput of about 10%.

- Ralph Droms
  Department of Computer Science
  Bucknell University


This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:41:32 GMT