Implementing the Internet Checksum in Hardware
RFC 1936

Document Type RFC - Informational (April 1996; Errata)
Was draft-rfced-info-touch (individual)
Last updated 2013-03-02
Stream Legacy
Formats plain text pdf htmlized with errata bibtex
Stream Legacy state (None)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state RFC 1936 (Informational)
Telechat date
Responsible AD (None)
Send notices to (None)
Network Working Group                                           J. Touch
Request For Comments: 1936                                     B. Parham
Category: Informational                                              ISI
                                                              April 1996

             Implementing the Internet Checksum in Hardware

Status of This Memo

   This memo provides information for the Internet community.  This memo
   does not specify an Internet standard of any kind.  Distribution of
   this memo is unlimited.

Abstract

   This memo presents a techniques for efficiently implementing the
   Internet Checksum in hardware. It includes PLD code for programming a
   single, low cost part to perform checksumming at 1.26 Gbps.

Introduction

   The Internet Checksum is used in various Internet protocols to check
   for data corruption in headers (e.g., IP) [4] and packet bodies (e.g,
   UDP, TCP) [5][6]. Efficient software implementation of this checksum
   has been addressed in previous RFCs [1][2][3][7].

   Efficient software implementations of the Internet Checksum algorithm
   are often embedded in data copying operations ([1], Section 2). This
   copy operation is increasingly being performed by dedicated direct
   memory access (DMA) hardware. As a result, DMA hardware designs are
   beginning to incorporate dedicated hardware to compute the Internet
   Checksum during the data transfer.

   This note presents the architecture of an efficient, pipelined
   Internet Checksum mechanism, suitable for inclusion in DMA hardware
   [8]. This design can be implemented in a relatively inexpensive
   programmable logic device (PLD) (1995 cost of $40), and is capable of
   supporting 1.26 Gbps transfer rates, at 26 ns per 32-bit word.
   Appendix A provides the pseudocode for such a device. This design has
   been implemented in the PC-ATOMIC host interface hardware [8]. We
   believe this design is of general use to the Internet community.

Touch & Parham               Informational                      [Page 1]
RFC 1936    Implementing the Internet Checksum in Hardware    April 1996

   The remainder of this document is organized as follows:

            Review of the Internet Checksum
            One's Complement vs. Two's Complement Addition
            Interfaces
            Summary
            Appendix A - PLD source code

Touch & Parham               Informational                      [Page 2]
RFC 1936    Implementing the Internet Checksum in Hardware    April 1996

A Review of the Internet Checksum

   The Internet Checksum is used for detecting corruption in a block of
   data [1]. It is initialized to zero, and computed as the complement
   of the ones-complement sum of the data, taken in 16-bit units. A
   subsequent checksum of the data and checksum together should generate
   a zero checksum if no errors are detected.

   The checksum allows [1]:

            - byte order "independence"
                    reordered output is equivalent to reordered input
            - 16-bit word-order independence
                    reordering 16-bit words preserves the output
            - incremental computation
            - deferred carries
            - parallel summation
                    a result of deferred carries, incremental
                    computation, and 16-bit word order independence

   This note describes an implementation that computes two partial
   checksums in parallel, over the odd and even 16-bit half-words of
   32-bit data. The result is a pair of partial checksums (odd and
   even), which can be combined, and the result inverted to generate the
   true Internet Checksum. This technique is related to the long-word
   parallel summation used in efficient software implementations [1].

            +------------------+     +------------------+
            |  high half-word  |     |  low half-word   |
            | ones-complement  |     | ones-complement  |
            | partial checksum |     | partial checksum |
            +------------------+     +------------------+
                                \   /
                                  * (ones-complement sum)
                                  |
                         +------------------+
                         | partial checksum |
                         +------------------+
                                  |
                                  * (ones-complement negative)
                                  |
                        +-------------------+
                        |       final       |
                        | Internet Checksum |
                        +-------------------+

Touch & Parham               Informational                      [Page 3]
RFC 1936    Implementing the Internet Checksum in Hardware    April 1996

One's Complement vs. Two's Complement Addition

   The Internet Checksum is composed of a ones-complement lookahead
Show full document text