Re: Checksums (again)


Dave Borman (dab%oliver.CRAY.COM@uc.msc.umn.edu)
Wed, 30 Mar 88 11:29:58 CST


> 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 */

You can only wait to do the folding in of checksum overflow if
you are adding 16 bit quantites in a 32 bit sum. The BSD
implementation adds 32 bits at a time in a 32 bit sum, so you
have to add in the carry bit as you go. On just about any machine
it will probaboy be faster to do one memory reference to get the
32 bit quantity, and then add in the carry, rather than doing two 16
bit memory references. (As a side note, on a CRAY computer you do
not have a carry bit, so we do the sum by reading up 64 bit quantities,
splitting them into two 32 bit quantites, and summing into a 64 bit
sum. We then add in all the carry bits at the end.)
                        -Dave Borman
                        CRAY Research, Inc.
-------



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