注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

天道酬勤 玩物丧志

用勇气去改变可以改变的事情,用胸怀去包容无法改变的事情,用智慧去判断两者的区别

 
 
 

日志

 
 

【转载】RFC1071——计算Internet校验和  

2014-02-09 21:37:05|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
Network Working Group                                          R.   Braden
Request for Comments: 1071                                            ISI
                                                               D.   Borman
                                                            Cray Research
                                                             C. Partridge
                                                         BBN Laboratories
                                                           September 1988

计算Internet校验和
本备忘录简介

  本备忘录概述了高效计算Internet校验和的技巧和算法。它不是标准实现方法,但却是非常有用的一组。本备忘录可以不受限制的分发。
1、导言

  本备忘录讨论高效计算运用于标准Internet协议,如IP、UDP和TCP等上面的Internet校验和的方法。

  有效的校验和实现应当具有良好的性能。随着协议处理的其他部分的实现方法简化的发展,校验和的计算逐渐成为限制协议性能,如TCP,的因素之一。通常情况下是采用各种依赖机器的可能方法来手动寻找合适的校验和例程。每TCP数据字节所费的一微秒的若干分之一的时间改善都可以显著地节省CPU运算时间。

  概括地说,Internet校验和算法是非常简单的:

  (1)待校验的相邻字节成对组成16比特整数并计算其和的二进制反码。

  (2)为了生成校验和,校验和区域本身应当先置0,并和待校验数据相加,其和进行二进制反码运算后赋给校验和区域。

  (3)检查校验和时,将所有字节,包括校验和,进行相加并求二进制反码。如果结果为全1(即二进制反码算术中的0),检查通过。

  假定校验和的计算是按照A、B、C、D、…、Y、Z等字节的顺序进行。使用符号[a,b]来表示16比特整数a*256+b,这里a和b均为字节。则求这些字节和的16比特二进制反码可按如下形式进行:

    [A,B] +' [C,D] +' ... +' [Y,Z] [1]

    [A,B] +' [C,D] +' ... +' [Z,0] [2]

  这里+'表示二进制反码相加。上述形式对应于偶数个或奇数个字节。

  在采用二进制补码方式的机器上,二进制反码运算应当采用“循环进位”的方式,也就是最高位产生的任何溢出都应当加到最低位上。参看下面的例子。

  第二部份探讨本校验和可能被用来加速运算的特性。第三部份包含最重要的实现技巧的一些数例。最后,第四部份给出了一些通用CPU类型的特定算法。我们非常感激Van Jacobson和Charley Kline为本章给出的算法。

  Internet校验和的特性最初由Bill Plummer在IEN-45中探讨,文章名为“Checksum Function Design”。由于IEN-45已经不能被广泛获得,我们把它做为本RFC的附件之一。
2、校验和计算

  本校验和示例运用了一系列奇妙地可以加速计算的算术特性,我们将在下面讨论这些特性。
  (A)交换和结合

  既然有奇偶字节可能,求和就可以按任何顺序进行,并且可以任意地分组。

  例如,和[1]可以被分成下列形式:

    ([A,B] +' [C,D] +' ... +' [J,0]) +' ([0,K] +' ... +' [Y,Z]) [3]
  (B)字节顺序无关

  16比特整数可以按任一顺序求和。因此,如果我们计算如下形式的和:

    [B,A] +' [D,C] +' ... +' [Z,Y] [4]

  其结果除了字节次序被交换了外等同于形式[1]的和。为了明白为什么会这样,只要观察一下两种顺序中从第15比特到第0比特和从第7比特到第8比特的进位是相同的就可以知道了。换句话说,相应地交换字节顺序只是简单地循环和数中的比特位,而不改变它们内存的顺序。

  因此,求和可以不考虑底层硬件的字节顺序(“big-endian”或者“litter-endian”)。例如假定在采用“litter- endian”顺序的系统中计算内存当中采用“big-endian”顺序的数据。每一个取出的16比特字都将交换字节顺序,如同求形式[4]的和,但是,当把结果写回到内存中去时其字节顺序又将被交换回来。

  字节交换也可被用于处理边界赋值问题。例如,如果形式[3]中的第二部分的和在它加到第一部分之前进行了字节交换,其也可以按如下形式计算,无须考虑其奇偶起点:

    [K,L] +' ... +' [Z,0]

  具体参看下面的例子。
  (C)并行求和

  在字长为16比特倍数的机器上,可能开发出更有效的实现方法。因为加法满足结合律,我们不需要按它们出现的顺序相加。相反我们可以采用更大的字长来“并行”相加它们。

  只需简单地按照本机的字长进行二进制反码加法就可以并行求校验和。例如在一台32位字长计算机上我们可以一次加4个字节:[A,B,C,D] +' ...。当结果计算出来后,在16位寄存器当中对其相加从而把32位“折叠”成16位。每一16比特相加产生的进位同样按照循环进位的方式处理。

  另外,字节顺序在这里也无关紧要,我们可以计算如下的32比特字:[D,C,B,A] +' ...或[B,A,D,C] +' ...,只要把最终的16比特和的字节顺序交换过来就可以了。具体参见下面的例子。任何把偶序数据字节合成一个结果并把奇序数据字节合成另一个结果的排列都是允许的。

  这里还有一些编码技巧可用来加速校验和的计算。
  (1)延迟进位

  把循环进位推迟到主求和循环结束也许会更有效率,这个依赖于机器。

  一种途径就是在32比特加法器中进行16比特求和,这样溢出就被放到了高16位中。这种方法可以避免使用进位敏感指令但需要两倍于在32比特寄存器相加的加法运算。速度提高取决于具体的硬件体系。
  (2)展开循环

  为了减少循环的系统开销,“展开”内层求和循环通常是比较有用的,即在一重循环中使用多个加法指令。这个技巧通常可以显著的节省时间,即使它可能使程序的逻辑变得更为复杂。
  (3)合并数据拷贝

  如同校验和计算,从内存当中按字节复制数据也是相当大的系统开销。在这两种情况下,基本瓶颈是内存总线,也就是说数据能够多快被取过来。在一些机器在(特别是相当慢而且简单的微型计算机),合并内存到内存的拷贝和校验和计算可以显著地减少系统开销,因为只需一次取数据。
  (4)增量更新

  最后,当数据包头某个域更新后有时可以避免完全重新计算校验和。最好的例子就是网关改变IP数据包头中的TTL域,当然还有很多其他的例子(比如当更新源路由时)。在这些时候不扫描消息或数据报就更新校验和是可能的。

  简单地把改变了的16比特整数的差加到原先的校验和上就可以更新校验和。注意到每一个16比特整数都有其对应的加性逆元素并且加法是满足结合律的就可以知道为什么可以这样做了。如下所示,原始数据为m、新值为m'、旧校验和为C,则新校验和C'为:

    C' = C + (-m) + m' = C + (m' - m)
3、数例

  下面给出在二进制补码机器上进行二进制反码求和的例子。本例子表明按字节顺序、16比特字的正常顺序和交换后顺序以及32比特的三种不同顺序来计算校验和结果是相同的。所有的数据采用16进制表示。
    Byte-by-byte     "Normal" Order     Swapped Order
Byte 0/1:         00         01             0001             0100     
Byte 2/3:         f2         03             f203             03f2     
Byte 4/5:         f4         f5             f4f5             f5f4     
Byte 6/7:         f6         f7             f6f7             f7f6     
        ---         ---             -----             -----     
Sum1:         2dc         1f0             2ddf0             1f2dc     
        dc         f0             ddf0             f2dc     
Carrys:         1         2             2             1     
        --         --             ----             ----     
Sum2:         dd         f2             ddf2             f2dd     
Final Swap:         dd         f2             ddf2             ddf2     
Byte 0/1/2/3:         0001f203             010003f2             03f20100     
Byte 4/5/6/7:         f4f5f6f7             f5f4f7f6             f7f6f5f4     
        ---------             ---------             ---------     
Sum1:         0f4f7e8fa             0f6f4fbe8             0fbe8f6f4     
Carries:         0             0             0     
Top half:         f4f7             f6f4             fbe8     
Bottom half:         e8fa             fbe8             f6f4     
        -----             -----             -----     
Sum2:         1ddf1             1f2dc             1f2dc     
        ddf1             f2dc             f2dc     
Carrys:         1             1             1     
        ----             ----             ----     
Sum3:         ddf2             f2dd             f2dd     
Final Swap:         ddf2             ddf2             ddf2     

  最后给出将结果分成两组,第二组从奇序边界开始的例子。
    Byte-by-byte     Normal Order
Byte 0/1:         00         01             0001     
Byte 2/ :         f2         (00)             f200     
        ---         ---             -----     
Sum1:         f2         01             f201     
Byte 4/5:         03         f4             03f4     
Byte 6/7:         f5         f6             f5f6     
Byte 8/ :         f7         (00)             f700     
        ---         ---             -----     
Sum2:                             1f0ea     
                            f0ea     
Carry:                             1     
                            ----     
Sum3:                             f0eb     
Sum1:                             f201     
Sum3 byte swapped:                             ebf0     
                            -----     
Sum4:                             1ddf1     
                            ddf1     
Carry:                             1     
                            ----     
                            ddf2     
                
4、实现示例

  本节我们给出不同CPU上已知的高效Internet校验和实现算法。每种情况我们只给出算法的核心部分,而没有包括环境代码(例如,子例程连接)或特定例子代码。
4.1“C”

   下列的“C”语言计算校验和算法包含一个内部循环用来在32位加法器中计算16位数据和。

     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;    
     }    

4.2 Motorola 68020

  下列算法用Motorola 68020汇编语言实现。本算法执行32位数据相加,并使用16次重复代替循环。为了表示清楚,我们省略了当长度不是4的倍数时在末尾增加字的逻辑结构。结果位于寄存器d0

  当时钟频率为20MHz时,本例程对随机数据的加法可达到134 usec/kB。本算法由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     

4.3 Cray

  下列算法由Charley Kline用Cray汇编语言实现。它采用向量操作方式实现了校验和计算,用基本的32比特加法单元一次运算512比特。本例为了表示清楚省略了当处理短小数据时的许多细节。

  寄存器A1保存用于求和的512字节块的地址。首先该数据的两个拷贝被装入两个向量寄存器。一个执行32位向量右移,另一个执行32位向量与。然后这两个向量相加。由于所有的这些操作是链式结构,每一个时钟周期产生一个结果。接着将结果向量的每一个元素加到一个标量寄存器中。最后执行循环进位并将结果合并成16位。

           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.     

4.4 IBM 370

  下面的算法用IBM 370汇编语言实现,一次加4个字节数据。为了表示清楚,我们省略了当长度不是4的倍数时在末尾增加字和必要时颠倒字节顺序的逻辑结构。结果存于寄存器RCARRY。

  本代码在IBM 3090上可达到27 usec/KB的速度。如果将加数按节对齐(需要专门的结构来处理开始和末尾及当开始于奇序字节时必要的校正),本时间将减少到24.3 usec/KB。

     *        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       

               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
  评论这张
 
阅读(455)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018