Computing the Internet checksum
RFC 1071
Document  Type 
RFC  Informational
(September 1988; Errata)
Updated by RFC 1141



Authors  
Last updated  20200121  
Stream  Legacy stream  
Formats  plain text html pdf htmlized (tools) htmlized with errata bibtex  
Stream  Legacy state  (None)  
Consensus Boilerplate  Unknown  
RFC Editor Note  (None)  
IESG  IESG state  RFC 1071 (Informational)  
Telechat date  
Responsible AD  (None)  
Send notices to  (None) 
Network Working Group R. Braden Request for Comments: 1071 ISI D. Borman Cray Research C. Partridge BBN Laboratories September 1988 Computing the Internet Checksum Status of This Memo This memo summarizes techniques and algorithms for efficiently computing the Internet checksum. It is not a standard, but a set of useful implementation techniques. Distribution of this memo is unlimited. 1. Introduction This memo discusses methods for efficiently computing the Internet checksum that is used by the standard Internet protocols IP, UDP, and TCP. An efficient checksum implementation is critical to good performance. As advances in implementation techniques streamline the rest of the protocol processing, the checksum computation becomes one of the limiting factors on TCP performance, for example. It is usually appropriate to carefully handcraft the checksum routine, exploiting every machinedependent trick possible; a fraction of a microsecond per TCP data byte can add up to a significant CPU time savings overall. In outline, the Internet checksum algorithm is very simple: (1) Adjacent octets to be checksummed are paired to form 16bit integers, and the 1's complement sum of these 16bit integers is formed. (2) To generate a checksum, the checksum field itself is cleared, the 16bit 1's complement sum is computed over the octets concerned, and the 1's complement of this sum is placed in the checksum field. (3) To check a checksum, the 1's complement sum is computed over the same set of octets, including the checksum field. If the result is all 1 bits (0 in 1's complement arithmetic), the check succeeds. Suppose a checksum is to be computed over the sequence of octets Braden, Borman, & Partridge [Page 1] RFC 1071 Computing the Internet Checksum September 1988 A, B, C, D, ... , Y, Z. Using the notation [a,b] for the 16bit integer a*256+b, where a and b are bytes, then the 16bit 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 IEN45, entitled "Checksum Function Design". Since IEN45 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 [Page 2] RFC 1071 Computing the Internet Checksum September 1988 (B) Byte Order Independence The sum of 16bit integers can be computed in either byte order. Thus, if we calculate the swapped sum: [B,A] +' [D,C] +' ... +' [Z,Y] [4] the result is the same as [1], except the bytes are swapped in the sum! To see why this is so, observe that in both orders the carries are the same: from bit 15 to bit 0 and from bit 7 to bit 8. In other words, consistently swapping bytes simply rotatesShow full document text