分类:
2009-10-30 23:34:29
IP校验和详解
一、校验和算法
之前一直只知道IP校验和算法反码求和相关的,但具体细节不清楚,今天了解了下。
IP校验和主要是用来保证数据(IP包头)的完整性的.它用的算法非常简单,就是反码求和校验.需要注意的是反码求和又叫1的补码(one'scomplement),而2的补码就是我们通常说的补码求和了.校验算法具体如下.
1、发送方
i)将校验和字段置为0,然后将IP包头按16比特分成多个单元,如包头长度不是16比特的倍数,则用0比特填充到16比特的倍数;
ii)对各个单元采用反码加法运算(即高位溢出位会加到低位,通常的补码运算是直接丢掉溢出的高位),将得到的和的反码填入校验和字段;
iii)发送数据包.
2、接收方
i)将IP包头按16比特分成多个单元,如包头长度不是16比特的倍数,则用0比特填充到16比特的倍数;
ii)对各个单元采用反码加法运算,检查得到的和是否符合是全1(有的实现可能对得到的和会取反码,然后判断最终值是不是全0);
iii)如果是全1则进行下步处理,否则意味着包已变化从而丢弃之.
二、校验和源码
网上流传多组实现,常见的有如下两种(如追求效率可改写为汇编代码):
1、RFC1071源码
unsigned short csum(unsigned char *addr, int count) { /* 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); 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、对数据长度没限制的实现
unsigned short cksum (struct ip *ip, int len) { long sum = 0; /* assume 32 bit long, 16 bit short */ while ( len >1 ) { sum += *((unsigned short *) 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 += ( unsigned short ) * (unsignedl char *) ip; while ( sum >> 16) sum =(sum & 0xFFFF) + (sum>> 16); return ~sum; } |
三、几个细节问题
1、数据部分改变时的重校验
考虑这样的应用场景:路由器转发IP报文时,有可能只更改了IP数据包头的部分内容(如更改了TTL,分片了或SNAT更改了源IP等~~~),却需要重校验的问题.为提高转发效率,要求重校验算法尽可能快,故出现了如下所示的重校验算法(只是一个简单的示例):
UpdateTTL(struct ip_hdr *ipptr, unsigned char n) { unsigned long sum; unsigned short old; old = ntohs(*(unsigned short *)&ipptr->ttl); ipptr->ttl -= n; sum = old + (~ntohs(*(unsigned short *)&ipptr->ttl) & 0xffff); sum += ntohs(ipptr->Checksum); sum = (sum & 0xffff) + (sum>>16); ipptr->Checksum = htons(sum + (sum>>16)); } |
四、参考文章
http://blog.chinaunix.net/u/20/showart_438512.html,关于IP校验和的
http://blog.chinaunix.net/u/12313/showart_176114.html,关于网络校验和的
,关于IP校验和的
http://blog.chinaunix.net/u/20/showart_438418.html,关于补码和反码的