pinch@cs.washington.edu (Ricardo Pincheira) (05/24/91)
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
craig@sics.se (Craig Partridge) (05/27/91)
In <16175@darkstar.ucsc.edu> pinch@cs.washington.edu (Ricardo Pincheira) writes: >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. SIGCOMM Computer Communication Review did a series of papers on checksumming. Probably the two key articles are: Braden, Borman & Partridge on the Internet Checksum in April '89 Sklower on the OSI Checksum in October '89 I believe both papers reference all interesting prior work. Craig