rfc1936.txt

来自「RFC 的详细文档！」· 文本 代码 · 共 1,180 行 · 第 1/3 页

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
   adder and a bit-wise inverter. A ones-complement adder can be built
   either using twos-complement components, or natively.

   A twos-complement implementation of a ones-complement adder requires
   either two twos-complement adders, or two cycles per add. The sum is
   performed, then the high-bit carry-out is propagated to the carry-in,
   and a second sum is performed. (ones-complement addition is {+1s} and
   twos-complement is {+2s})

            a {+1s} b == (a {+2s} b) + carry(a {+2s} b)

            e.g.,
                    halfword16 a,b;
                    word32 c;
                    a {+1s} b == r
            such that:
                    c = a {+2s} b;                          # sum value
                    r = (c & 0xFFFF) {+2s} (c >> 16);       # sum carry

   Bits of a twos-complement lookahead adder are progressively more
   complex in carry lookahead. (OR the contents of each row, where terms
   are AND'd or XOR'd {^})

            4-bit carry-lookahead 2's complement adder:
                    a,b : input data
                    p   : carry propagate, where pi = ai*bi = (ai)(bi)
                    g   : carry generate, where gi = ai + bi

            Out0 := a0 ^ b0 ^ ci

            Out1 := a1 ^ b1 ^ (cip0     + g0)

            Out2 := a2 ^ b2 ^ (cip0p1   + g0p1   + g1)

            Out3 := a3 ^ b3 ^ (cip0p1p2 + g0p1p2 + g1p2 + g2)

            Cout := cip0p1p2p3 + g0p1p2p3 + g1p2p3 + g2p3 + g3

   The true ones-complement lookahead adder recognizes that the carry-
   wrap of the twos-complement addition is equivalent to a toroidal
   carry-lookahead. Bits of a ones-complement lookahead adder are all
   the same complexity, that of the high-bit of a twos-complement
   lookahead adder. Thus the ones-complement sum (and thus the Internet
   Checksum) is bit-position independent. We replace `ci' with the `co'
   expression and reduce. (OR terms in each row pair).



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


            4-bit carry-lookahead 1's complement ring adder:

            Out0 = a0 ^ b0 ^ (g3       + g2p3     + g1p2p3   + g0p1p2p3)

            Out1 = a1 ^ b1 ^ (g3p0     + g2p3p0   + g1p2p3p0 + g0)

            Out2 = a2 ^ b2 ^ (g3p0p1   + g2p3p0p1 + g1       + g0p1)

            Out3 = a3 ^ b3 ^ (g3p0p1p2 + g2       + g1p2     + g0p1p2)

   A hardware implementation can use this toroidal design directly,
   together with conventional twos-complement fast-adder internal
   components, to perform a pipelined ones-complement adder [8].

   A VLSI implementation could use any full-lookahead adder, adapted to
   be toroidal and bit-equivalent, as above. In our PLD implementation,
   we implement the adders via 2- and 3-bit full-lookahead sub-
   components. The adder components are chained in a ring via carry bit
   registers.  This relies on delayed carry-propagation to implement a
   carry pipeline between the fast-adder stages.

            Full-lookahead adders in a toroidal pipeline

         +-+-+-+   +-+-+-+   +-+-+   +-+-+-+   +-+-+-+   +-+-+
         |i|i|i|   |i|i|i|   |i|i|   |i|i|i|   |i|i|i|   |i|i|
         |F|E|D|   |C|B|A|   |9|8|   |7|6|5|   |4|3|2|   |1|0|
         +-+-+-+   +-+-+-+   +-+-+   +-+-+-+   +-+-+-+   +-+-+
           "+"       "+"      "+"      "+"       "+"      "+"
         +-+-+-+   +-+-+-+   +-+-+   +-+-+-+   +-+-+-+   +-+-+
         |s|s|s|   |s|s|s|   |s|s|   |s|s|s|   |s|s|s|   |s|s|
         |F|E|D|   |C|B|A|   |9|8|   |7|6|5|   |4|3|2|   |1|0|
         +-+-+-+   +-+-+-+   +-+-+   +-+-+-+   +-+-+-+   +-+-+
         v     |   v     |   v   |   v     |   v     |   v   |   +--+
         |     ^   |     ^   |   ^   |     ^   |     ^   |   ^   v  |
         |      +-+       +-+     +-+       +-+       +-+     +-+   |
         |      |c|       |c|     |c|       |c|       |c|     |c|   |
         |      |5|       |4|     |3|       |2|       |1|     |0|   |
         |      +-+       +-+     +-+       +-+       +-+     +-+   |
         +----------------------------------------------------------+

   Implementation of fast-adders in PLD hardware is currently limited to
   3-bits, because an i-bit adder requires 4+2^i product terms, and
   current PLDs support only 16 product terms.  The resulting device
   takes at most 5 "idle" clock periods for the carries to propagate
   through the accumulation pipeline.






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


Interfaces

   The above device has been installed in a VL-Bus PC host interface
   card [8]. It has a hardware and software interface, defined as
   follows.

 Hardware Interface

   The Internet Checksum hardware appears as a single-port 32-bit
   register, with clock and control signals [8]:

                   +----------------------+
            CLR--->|                      |
            OE---->|  32-bit register as  |
            CLK--->|  2 adjacent 16-bit   |<---/---> 32-bit data bus
            ICLK-->| ones-complement sums |
            ADD--->|                      |
                   +----------------------+

            CLR    = zero the register
            OE     = write the register onto the data bus
            CLK    = clock to cycle the pipeline operation
            ICLK   = input data latch clock
            ADD    = initiating an add of latched input data

   CLR causes the contents of the checksum register and input latch to
   be zeroed. There is no explicit load; a CLR followed by a write of
   the load value to a dummy location is equivalent.

   The OE causes the register to be written to the data bus, or tri-
   stated.

   The CLK causes the pipeline to operate. If no new input data is
   latched to be added (via ICLK, ADD), a virtual "zero" is summed into
   the register, to permit the pipeline to empty.

   The ICLK (transparently) latches the value on the data bus to be
   latched internally, to be summed into the accumulator on the next ADD
   signal. The ADD signal causes the latched input data (ICLK) to be
   accumulated into the checksum pipeline. ADD and ICLK are commonly
   tied together. One 32-bit data value can be latched and accumulated
   into the pipeline adder every 26-ns clock, assuming data is stable
   when the ADD/ICLK signal occurs.

   The internal 32-bit register is organized as two 16-bit ones-
   complement sums, over the even and odd 16-bit words of the data
   stream. To compute the Internet Checksum from this quantity, ones-
   complement add the halves together, and invert the result.



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


 Software Interface

   The device is used as a memory-mapped register. The register is read
   by performing a read on its equivalent memory location.

   The device is controlled via an external memory-mapped register. Bits
   in this control register clear the device (set/clear the CLR line),
   and enable and disable the device (set/clear the ADD line). The CLR
   line can alternatively be mapped to a memory write, e.g., such that
   reading the location is a non-destructive read of the checksum
   register, and a write of any value clears the checksum register. The
   enable/disable control must be stored in an external register.

   The device is designed to operate in background during memory
   transfers (either DMA or programmed I/O). Once enabled, all transfers
   across that bus are summed into the checksum register. The checksum
   is available 5 clocks after the last enabled data accumulation. This
   delay is often hidden by memory access mechanisms and bus
   arbitration.  If required, "stall" instructions can be executed for
   the appropriate delay.

   For the following example, we assume that the device is located at
   CKSUMLOC. We assume that reading that location reads the checksum
   register, and writing any value to that location clears the register.
   The control register is located at CTLLOC, and the checksum
   enable/disable bit is CKSUMBIT, where 1 is enabled, and 0 is
   disabled.  To perform a checksum, a programmer would clear the
   register, (optionally initialize the checksum), initiate a series of
   transfers, and use the result:

            /******* initialization *******/
            *(CTLLOC) &= ~((ctlsize)(CKSUMBIT));     /* disable sum */
            (word32)(*(CKSUMLOC)) = 0;               /* clear reg   */
            *(CTLLOC) |= CKSUMBIT;                   /* enable sum  */
            { (optional) write initial value to a dummy location }

            /***** perform a transfer *****/
            { do one or more DMA or PIO transfers - read or write }

            /***** gather the results *****/
            *(CTLLOC) &= ~((ctlsize)(CKSUMBIT));     /* disable sum  */
            sum = (word32)(*(CKSUMLOC));             /* read sum     */
            sum = (sum & 0xFFFF) + (sum >> 16);      /* fold halves  */
            sum = (sum & 0xFFFF) + (sum >> 16);      /* add in carry */
            ipcksum = (halfword16)(~(sum & 0xFFFF)); /* 1's negative */






Touch & Parham               Informational                      [Page 7]