tcp-ip效验及理解.doc

本文结合网上资料记当个人对效验和算法的理解：

1、算法推导： 1
2、算法： 1
3.实例(运算过程) 2
4、 实现代码： 5

1、算法推导：
具体算法见后。
整个算法可理解为 ~（a + ～a） = 0；

发送方: 先置checksum = 0 ，假设各单元求和为 sum1 = m + n * 2^16 。那么n即为溢出 的高位。 所以得出 checksum = ~ (m+n) 。
接收方：（在传输无误情况下）
各单元求和 sum2 = sum1 + checksum
= m + n * 2^16 + ( ~ (m+n) )
同样接收方也会将溢出的高位加至低位，n * 2^16 中 n 为已知的高位所以先处理 [不管m + (~(m+n))是否还溢出] 。
所以sum2 = m + n + ( ~ (m+n) ) = (m + n )+ ( ~ (m+n) )
所以 ~ sum2 = 0;

跟据以上推导，不管采用大端 还是 小端 模式 ，只要发送方和接收方采用的模式一样，那么发送方和接收方算出的sum1（除去checksum字段后其它字段的和）都肯定一样。所以上述推导仍然成立。

2、算法：
1、发送方
　　i)将校验和字段置为0,然后将IP包头按16比特分成多个单元，如包头长度不是16比特的倍数，则用0比特填充到16比特的倍数；

　　ii)对各个单元采用反码加法运算(即高位溢出位会加到低位,通常的补码运算是直接丢掉溢出的高位),将得到的和的反码填入校验和字段；

　　iii)发送数据包。

2、接收方
　　i)将IP包头按16比特分成多个单元，如包头长度不是16比特的倍数，则用0比特填充到16比特的倍数；

　　ii)对各个单元采用反码加法运算，检查得到的和是否符合是全1(有的实现可能对得到的和会取反码，然后判断最终值是不是全0)；

iii) 如果是全1则进行下步处理,否则意味着包已变化从而丢弃之。需要强调的是反码和是采用高位溢出加到低位的，如3比特的反码和运 算：100b+101b=010b(因为100b+101b=1001b,高位溢出1，其应该加到低位，即001b+1b(高位溢出位)=010b)。

3.实例(运算过程)
请看我用ominipeek的抓包

I.将校验和字段置为0,然后将IP包头按16比特分成多个

校验和Header Checksum：0x618D将其重置为0X0000
将IP包头分段：
　　　　　　　　1.　　0x4500
　　　　　　　　2.　　0x0029
　　　　　　　　3.　　0x44F1
　　　　　　　　4.　　0x4000
　　　　　　　　5.　　0x8006
　　　　　　　　6.　　0x0000 ------->这个为Header Checksum的值，我们前面将其重置为0了
　　　　　　　　7.　　0xC0A8
　　　　　　　　8.　　0x01AE
　　　　　　　　9.　　0x4A7D
+　　　　　　　10.　　0x477D
-------------------------------------------------------
将1至10相加求出来的和为：0x29E70
II.对各个单元采用反码加法运算(即高位溢出位会加到低位,通常的补码运算是直接丢掉溢出的高位),将得到的和的反码填入校验和字段
0x0002+0x9E70=0x9E72
0x9E72二进制为：1001 1110 0111 0010
反码为：0110 0001 1000 1101
0110 0001 1000 1101的16进制为：0x618D
看看这个 是否与IP包头中的Checksum相同
==========================================================
当接收到IP对其进行检测
III.对各个单元采用反码加法运算，检查得到的和是否符合是全1(有的实现可能对得到的和会取反码，然后判断最终值是不是全0)
当收到IP数据局包的时候，要验证IP头是否正确，则可以这样进行
　　　　　　　　1.　　0x4500
　　　　　　　　2.　　0x0029
　　　　　　　　3.　　0x44F1
　　　　　　　　4.　　0x4000
　　　　　　　　5.　　0x8006
　　　　　　　　6.　　0x618D ------->这个为Header Checksum的值
　　　　　　　　7.　　0xC0A8
　　　　　　　　8.　　0x01AE
　　　　　　　　9.　　0x4A7D
+　　　　　　　10.　　0x477D
-------------------------------------------------------
将1至10相加求出来的和为：0x2FFD
对各个单元采用反码加法运算(即高位溢出位会加到低位,通常的补码运算是直接丢掉溢出的高位),将得到的和的反码填入校验和字段：
0x0002+0x0FFD=0xFFFF
0xFFFF二进制为：1111 1111 1111 1111
1111 1111 1111 1111反码为：0
====================================================
4、 实现代码：
　网上流传多组实现,常见的有如下两种(如追求效率可改写为汇编代码):

　　1、RFC1071源码

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeH

　　unsignedshort csum(unsignedchar *addr,int count)

　　{

　　/* Compute Internet Checksum for "count" bytes

　　* beginning at location "addr".

　　*/

　　registerlong sum= 0;

　　while( count> 1 )

　　{

　　/* This is the inner loop*/

　　sum+= * (unsignedshort) addr++;

　　count-= 2;

　　}

　　/* Add left-over byte, if any*/

　　if( count> 0 )

　　sum+= * (unsignedchar *) addr;

　　/* Fold 32-bit sum to 16 bits*/

　　while (sum>>16)

　　sum= (sum& 0xffff)+ (sum>> 16);

　　return ~sum;

　　}　第一个while循环是做普通加法(2进制补码加法),因为IP包头和TCP整个报文段比较短(没达到2^17数量级),所以不可能导致4字节的sum溢出(unsigned long 一般至少为4字节)).
　 　紧接着的一个判断语句是为了能处理输入数据是奇数个字节的这种情况.再接着的数据循环是实现反码算法(在前面的普通加法得到的数据的基础上),由反码和 的高位溢出加到低位的性质,可得到"32位的数据的高位比特移位16比特,再加上原来的低16比特,不影响最终结果" 这个等价运算,因为sum的最初值(刚开始循环时)可能很大,所以这个等价运算需循环进行,直到sum的高比特(16比特以上)全为0.对于32 位的 sum,事实上这个运算循环至多只有两轮,所以也有程序直接用两条"sum = (sum & 0xffff) + (sum >> 16);"代替了整个循环.最后,对和取反返回.
　　2、对数据长度没限制的实现

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeH

　　unsignedshort cksum (struct ip*ip,int len)

　　{

　　long sum= 0;/* assume 32 bit long, 16 bit short*/

　　while ( len>1 )

　　{

　　sum+= *((unsignedshort *) ip)++;

　　if (sum& 8x00000000)/* if high-order bit set, fold*/

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

　　len-= 2;

　　}

　　if ( len )/* take care of left over byte*/

　　sum+= ( unsignedshort )* (unsignedlchar *) ip;

　　while ( sum>> 16)

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

　　return ~sum;}　　这个实现与前面的一个的最大的不同是对数据的长度没什么限制了,因为它在第一个循环的加法运算中实时检测sum的高位的值,一旦发现其有溢出的危险,就及时运用等价运算关系消除了这个危险.
内容导航
5、几个细节问题
　　1、数据部分改变时的重校验
　　考虑这样的应用场景:路由器转发IP报文时,有可能只更改了IP数据包头的部分内容(如更改了TTL,分片了或SNAT更改了源IP等~~~),却需要重校验的问题.为提高转发效率,要求重校验算法尽可能快,故出现了如下所示的重校验算法(只是一个简单的示例):

Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeH

　　UpdateTTL(struct ip_hdr*ipptr, unsignedchar n)

　　{

　　unsignedlong sum;

　　unsignedshort old;

　　old= ntohs(*(unsignedshort *)&ipptr->ttl);

　　ipptr->ttl-= n;

　　sum= old+ (~ntohs(*(unsignedshort *)&ipptr->ttl)& 0xffff);

　　sum+= ntohs(ipptr->Checksum);

　　sum= (sum& 0xffff)+ (sum>>16);

　　ipptr->Checksum= htons(sum+ (sum>>16));

　　}　 　算法的实现依据是这样的.假设包头原校验和为~C,改变的字段的原始值是m,更改后的值是m',设~C'为重校验和,则有 ~C' = ~(C+(-m)+m') = ~C+(m-m') = ~C+m+~m'等价关系的成立基于反码的运算性质:取反运算满足结合律,按位取反运算与符号取反(及相反数)是等价的(即~C=-C).
　　如果有多个字段改变，只是上面的公式中的m和m'有多个而已，直接用反码加法搞定即可。
　　2、为什么采用反码和运算
　　IP数据包校验要求速度快,所以只采用了简单的和校验,为什么采用反码和而不是补码和呢?
　　i)反码和的溢出有后效性(蔓延性)
　　反码和将高位溢出加到低位,导致这个溢出会对后面操作有永久影响,有后效性;而补码和直接将高位和溢出,导致这个溢出对后面的操作再无影响,因此无后效性
　　ii)反码校验无需考虑字节序
　　正因为反码和的溢出有后效性,导致大端字节序(big-endian)和小端字节序(little-endian)对同一数据序列(如两个16比特的序列)产生的校验和也只是字节序相反，而补码和因为将溢出丢掉了,不同字节序之间的校验和大不相同且没什么联系。
　 　基于以上的理由，校验和运算既可选择在数据被转换成网络字节序前，也可选择在之后，只要保证被校验的字段和填写的校验和字段的字节序保持一致就可以了。 (这其实可以看作是负负得正，计算校验和与字节序有关，然后写校验和字段与字节序有关，然后直接计算校验和再写校验和字段则与字节序无关。)
6、参考文章