rfc1071.txt

<VC++网络游戏建摸与实现>源代码

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