RFC 1071 (rfc1071) - Page 2 of 24
Computing the Internet checksum
Alternative Format: Original Text Document
RFC 1071 Computing the Internet Checksum September 1988 A, B, C, D, ... , Y, Z. Using the notation [a,b] for the 16-bit integer a*256+b, where a and b are bytes, then the 16-bit 1's complement sum of these bytes is given by one of the following: [A,B] +' [C,D] +' ... +' [Y,Z] [1] [A,B] +' [C,D] +' ... +' [Z,0] [2] where +' indicates 1's complement addition. These cases correspond to an even or odd count of bytes, respectively. On a 2's complement machine, the 1's complement sum must be computed by means of an "end around carry", i.e., any overflows from the most significant bits are added into the least significant bits. See the examples below. Section 2 explores the properties of this checksum that may be exploited to speed its calculation. Section 3 contains some numerical examples of the most important implementation techniques. Finally, Section 4 includes examples of specific algorithms for a variety of common CPU types. We are grateful to Van Jacobson and Charley Kline for their contribution of algorithms to this section. The properties of the Internet checksum were originally discussed by Bill Plummer in IEN-45, entitled "Checksum Function Design". Since IEN-45 has not been widely available, we include it as an extended appendix to this RFC. 2. Calculating the Checksum This simple checksum has a number of wonderful mathematical properties that may be exploited to speed its calculation, as we will now discuss. (A) Commutative and Associative As long as the even/odd assignment of bytes is respected, the sum can be done in any order, and it can be arbitrarily split into groups. For example, the sum [1] could be split into: ( [A,B] +' [C,D] +' ... +' [J,0] ) +' ( [0,K] +' ... +' [Y,Z] ) [3] Braden, Borman, & Partridge
