Computing the Internet checksum
RFC 1071

Document Type RFC - Informational (September 1988; Errata)
Updated by RFC 1141
Last updated 2016-04-08
Stream Legacy
Formats plain text pdf html 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 hand-craft the checksum routine, exploiting
   every machine-dependent 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 16-bit
        integers, and the 1's complement sum of these 16-bit integers is
        formed.

   (2)  To generate a checksum, the checksum field itself is cleared,
        the 16-bit 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 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                                     [Page 2]
RFC 1071            Computing the Internet Checksum       September 1988

   (B)  Byte Order Independence

        The sum of 16-bit 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 rotates
Show full document text