增量式修改检验和（IP, TCP, UDP）算法的研究和实现

/*
* Author: Godbach
* E-mail:nylzhaowei@163.com
* 本文可以自由转载，但请标明出处，并保证本文的完整 *** 。
*/
对于数据包中检验和的计算，很多讲TCP/IP协议的书中都讲过，RFC1071是讨论计算检验和的文档。传统的计算方法都是需要将整个数据报文的数据（IP报文是计算IP头部的数据）进行反 *** 求和。

但在实际的应用中，存在对收到的数据包进行修改若干个地方，并回送至发送方或者转发的情况。这个时候，就涉及的重新计算数据包的检验和。最常见的可能就是，将收到的数据包的TTL字段减1，并转发的情况。如果仍旧按照传统的计算检验和的方式进行计算，特别是当数据包长度很大时，为了重新计算校验和而将整个数据包的数据遍历一边，反 *** 求和，效率肯定比较低。

一、增量修改检验和的实现

解决的方法就是采用增量式修改检验和的方法。该方法是由RFC1141提出的。这里进行以下简单的变通，将增量式修改检验和的公式列出来：
HC -- 数据包中旧的检验和
HC'-- 数据包中新的检验和
m  -- 数据包中某个域(16-bit字)修改前的值
m' -- 数据包中某个域(16-bit字)修改后的值

那么，修改某个域之后的校验和HC'与HC，m 和m'的关系如下：
    HC' = HC + m + ~m'        （公式1）

具体实现的C代 *** 如下：
/*implemented according with RFC 1071 and 1141*/

static    unsigned short csum_incremental_update ( unsigned short old_csum ,

                unsigned short old_field ,

                unsigned short new_field )

{

    unsigned long csum = old_csum + old_field + ( ~ new_field & 0xFFFF ) ;

    csum = ( csum > > 16 ) + ( csum & 0xFFFF ) ;

    csum + =    ( csum > > 16 ) ;

    return csum ;

}
这个时候，如果修改了IP头部的TTL值，将取修改前的TTL域所在的16-bit字的值为old_field, 修改后的为new_field, 并取出就得检验和old_csum，通过调用该函数即可计算出新的检验和。
当然该函数每次只能计算一个16-bit字，如果对数据包中修改了过多的16-bit字，那么它的 *** 能将会如何呢。

用TCP数据包做测试。而且该TCP数据包为三次握手时的数据包，仅有头部，没有数据部分。对该数据包修改了8个不同的16-bit字，调用该函数8次所需的时间仍旧不到传统计算方法的一半。可见，效果适合明显的。

二、增量修改检验和的完善
1. RFC1071和1141所提出的增量式修改检验有一个BUG，就是按照公式1计算新的检验和时，有可能出现计算结果为0xFFFF的情形，可以参看RFC1624给出的例子。如果检验和为0xFFFF,则意味着数据包中所有部分相加的结果为0x0000。这是不可能的。因此，RFC1624提出了对这个BUG的改进方法，见公式2：
    HC' = ~(~HC + ~m + m')        （公式2）
公式2先对旧的检验和和某个域的值取反，加上新的域值之后，将整体的和再次取反得出新的检验和。
具体实现的C代 *** 如下：
/*implemented according with RFC 1624, modified the algorithm from RFC 1071 and 1141*/

static    unsigned short csum_incremental_update_modified ( unsigned short old_csum , TAG标签 : 算法 研究 实现 修改 检验 增量 数据 csum unsigned 计算