Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!spool.mu.edu!agate!darkstar!cs.washington.edu
From: pinch@cs.washington.edu (Ricardo Pincheira)
Newsgroups: comp.os.research
Subject: checksumming algorithms
Message-ID: <16175@darkstar.ucsc.edu>
Date: 23 May 91 23:06:03 GMT
Article-I.D.: darkstar.16175
Sender: usenet@darkstar.ucsc.edu
Organization: Computer Science & Engineering, U. of Washington, Seattle
Lines: 24
Approved: comp-os-research@jupiter.ucsc.edu

I would greatly appreciate pointers to surveys, tutorials, "must read"
papers, etc on checksumming algorithms.  The only one I am familiar with
is 1's complement addition, as used for the internet (TCP/IP) protocols.

The motivation for posting this request is actually quite interesting.
1's complement addition requires a wrap-around carry, ie, a carry out
of the high bit has to be added back at the low end.  It turns out that
in some (2's complement) machines it is easy to preserve the carry bit,
so that you can add it back in.  For example, the VAX has a carry
condition code and an "add with carry" instruction which uses the value
of the carry condition code as a carry-in for the addition.  In other
machines, such as the MIPS processors, to avoid losing the carry, one
has to use workarounds that imply a substantial performance hit.  In
the MIPS, one possibility is to do the addition only 16 bits at a time,
so that carry outs get saved in the high order 16 bits of the
cumulative sum.  These can be added back in later.  Naturally, things
run more slowly than if the sum were done 32 bits at a time.

Anyways, the point is to learn about checksumming algorithms that are
"more appropriate" for the latter kinds of machines.

Thanks very much.

Ricardo Pincheira