rfc1071.txt

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

RFC 1071            Computing the Internet Checksum       September 1988


4.  Implementation Examples

   In this section we show examples of Internet checksum implementation
   algorithms that have been found to be efficient on a variety of
   CPU's.  In each case, we show the core of the algorithm, without
   including environmental code (e.g., subroutine linkages) or special-
   case code.

4.1  "C"

   The following "C" code algorithm computes the checksum with an inner
   loop that sums 16-bits at a time in a 32-bit accumulator.

   in 6
       {
           /* Compute Internet Checksum for "count" bytes
            *         beginning at location "addr".
            */
       register long sum = 0;

        while( count > 1 )  {
           /*  This is the inner loop */
               sum += * (unsigned short) addr++;
               count -= 2;
       }

           /*  Add left-over byte, if any */
       if( count > 0 )
               sum += * (unsigned char *) addr;

           /*  Fold 32-bit sum to 16 bits */
       while (sum>>16)
           sum = (sum & 0xffff) + (sum >> 16);

       checksum = ~sum;
   }


















Braden, Borman, & Partridge                                     [Page 7]

RFC 1071            Computing the Internet Checksum       September 1988


4.2  Motorola 68020

   The following algorithm is given in assembler language for a Motorola
   68020 chip.  This algorithm performs the sum 32 bits at a time, and
   unrolls the loop with 16 replications.  For clarity, we have omitted
   the logic to add the last fullword when the length is not a multiple
   of 4.  The result is left in register d0.

   With a 20MHz clock, this routine was measured at 134 usec/kB summing
   random data.  This algorithm was developed by Van Jacobson.


       movl    d1,d2
       lsrl    #6,d1       | count/64 = # loop traversals
       andl    #0x3c,d2    | Then find fractions of a chunk
       negl    d2
       andb    #0xf,cc     | Clear X (extended carry flag)

       jmp     pc@(2$-.-2:b,d2)  | Jump into loop

   1$:     | Begin inner loop...

       movl    a0@+,d2     |  Fetch 32-bit word
       addxl   d2,d0       |    Add word + previous carry
       movl    a0@+,d2     |  Fetch 32-bit word
       addxl   d2,d0       |    Add word + previous carry

           | ... 14 more replications
   2$:
       dbra    d1,1$   | (NB- dbra doesn't affect X)

       movl    d0,d1   | Fold 32 bit sum to 16 bits
       swap    d1      | (NB- swap doesn't affect X)
       addxw   d1,d0
       jcc     3$
       addw    #1,d0
   3$:
       andl    #0xffff,d0
















Braden, Borman, & Partridge                                     [Page 8]

RFC 1071            Computing the Internet Checksum       September 1988


4.3  Cray

   The following example, in assembler language for a Cray CPU, was
   contributed by Charley Kline.  It implements the checksum calculation
   as a vector operation, summing up to 512 bytes at a time with a basic
   summation unit of 32 bits.  This example omits many details having to
   do with short blocks, for clarity.

   Register A1 holds the address of a 512-byte block of memory to
   checksum.  First two copies of the data are loaded into two vector
   registers.  One is vector-shifted right 32 bits, while the other is
   vector-ANDed with a 32 bit mask. Then the two vectors are added
   together.  Since all these operations chain, it produces one result
   per clock cycle.  Then it collapses the result vector in a loop that
   adds each element to a scalar register.  Finally, the end-around
   carry is performed and the result is folded to 16-bits.

         EBM
         A0      A1
         VL      64            use full vectors
         S1      <32           form 32-bit mask from the right.
         A2      32
         V1      ,A0,1            load packet into V1
         V2      S1&V1            Form right-hand 32-bits in V2.
         V3      V1>A2            Form left-hand 32-bits in V3.
         V1      V2+V3            Add the two together.
         A2      63            Prepare to collapse into a scalar.
         S1      0
         S4      <16           Form 16-bit mask from the right.
         A4      16
   CK$LOOP S2    V1,A2
         A2      A2-1
         A0      A2
         S1      S1+S2
         JAN     CK$LOOP
         S2      S1&S4           Form right-hand 16-bits in S2
         S1      S1>A4           Form left-hand 16-bits in S1
         S1      S1+S2
         S2      S1&S4           Form right-hand 16-bits in S2
         S1      S1>A4           Form left-hand 16-bits in S1
         S1      S1+S2
         S1      #S1            Take one's complement
         CMR            At this point, S1 contains the checksum.











Braden, Borman, & Partridge                                     [Page 9]

RFC 1071            Computing the Internet Checksum       September 1988


4.4  IBM 370

   The following example, in assembler language for an IBM 370 CPU, sums
   the data 4 bytes at a time.  For clarity, we have omitted the logic
   to add the last fullword when the length is not a multiple of 4, and
   to reverse the bytes when necessary.  The result is left in register
   RCARRY.

   This code has been timed on an IBM 3090 CPU at 27 usec/KB when
   summing all one bits.  This time is reduced to 24.3 usec/KB if the
   trouble is taken to word-align the addends (requiring special cases
   at both the beginning and the end, and byte-swapping when necessary
   to compensate for starting on an odd byte).

   *      Registers RADDR and RCOUNT contain the address and length of
   *              the block to be checksummed.
   *
   *      (RCARRY, RSUM) must be an even/odd register pair.
   *      (RCOUNT, RMOD) must be an even/odd register pair.
   *
   CHECKSUM  SR    RSUM,RSUM       Clear working registers.
             SR    RCARRY,RCARRY
             LA    RONE,1          Set up constant 1.
   *
             SRDA  RCOUNT,6        Count/64 to RCOUNT.
             AR    RCOUNT,RONE       +1 = # times in loop.
             SRL   RMOD,26         Size of partial chunk to RMOD.
             AR    RADDR,R3        Adjust addr to compensate for
             S     RADDR,=F(64)      jumping into the loop.
             SRL   RMOD,1          (RMOD/4)*2 is halfword index.
             LH    RMOD,DOPEVEC9(RMOD) Use magic dope-vector for offset,
             B     LOOP(RMOD)          and jump into the loop...
   *
   *             Inner loop:
   *
   LOOP      AL    RSUM,0(,RADDR)   Add Logical fullword
             BC    12,*+6             Branch if no carry
             AR    RCARRY,RONE        Add 1 end-around
             AL    RSUM,4(,RADDR)   Add Logical fullword
             BC    12,*+6             Branch if no carry
             AR    RCARRY,RONE        Add 1 end-around
   *
   *                    ... 14 more replications ...
   *
             A     RADDR,=F'64'    Increment address ptr
             BCT   RCOUNT,LOOP     Branch on Count
    *
    *            Add Carries into sum, and fold to 16 bits
    *
             ALR   RCARRY,RSUM      Add SUM and CARRY words
             BC    12,*+6              and take care of carry



Braden, Borman, & Partridge                                    [Page 10]

RFC 1071            Computing the Internet Checksum       September 1988


             AR    RCARRY,RONE
             SRDL  RCARRY,16        Fold 32-bit sum into
             SRL   RSUM,16            16-bits
             ALR   RCARRY,RSUM
             C     RCARRY,=X'0000FFFF' and take care of any
             BNH   DONE                     last carry
             S     RCARRY,=X'0000FFFF'
   DONE      X     RCARRY,=X'0000FFFF' 1's complement














































Braden, Borman, & Partridge                                    [Page 11]

RFC 1071            Computing the Internet Checksum       September 1988


     IEN 45
     Section 2.4.4.5
















                       TCP Checksum Function Design



                            William W. Plummer


                       Bolt Beranek and Newman, Inc.
                             50 Moulton Street
                           Cambridge MA   02138


                                5 June 1978























Braden, Borman, & Partridge                                    [Page 12]

RFC 1071            Computing the Internet Checksum       September 1988