" id="b1img" alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO">
  • " alt="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" title="米课”N+1“思维建站-非官方免费技术支持,Wordpress/Zencart/Opencart建站、SEO" />
  • " alt="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" title="Windows/Linux服务器运维技术支持 环境搭建、应用发布、服务器管理、虚拟化、云计算" />
  • " alt="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" title="高校/小型企业网络运维与建设免费技术支持,网络规划、网络优化、故障排除、网络管理" />

校验和算法、校验和计算(二进制反码求和)

网络运维2009-08-05 itlogger阅读(6,399) 评论(2)
IP/ICMP/IGMP/TCP/UDP等协议的校验和算法都是相同的,算法如下:
在发送数据时,为了计算数IP据报的校验和。应该按如下步骤:
(1)把IP数据报的校验和字段置为0;
(2)把首部看成以16位为单位的数字组成,依次进行二进制反码求和;
(3)把得到的结果存入校验和字段中。
在接收数据时,计算数据报的校验和相对简单,按如下步骤:
(1)把首部看成以16位为单位的数字组成,依次进行二进制反码求和,包括校验和字段;
(2)检查计算出的校验和的结果是否等于零(反码应为16个1);
(3)如果等于零,说明被整除,校验是和正确。否则,校验和就是错误的,协议栈要抛弃这个数据包。
所谓的二进制反码求和,即为先进行二进制求和,然后对和取反。
计算对IP首部检验和的算法如下:
(1)把IP数据报的校验和字段置为0;
(2)把首部看成以16位为单位的数字组成,依次进行二进制求和(注意:求和时应将最高位的进位保存,所以加法应采用32位加法);
(3)将上述加法过程中产生的进位(最高位的进位)加到低16位(采用32位加法时,即为将高16位与低16位相加,之后还要把该次加法最高位产生的进位加到低16位)
(4)将上述的和取反,即得到校验和。
其中,二进制反码求和的计算方法:
首先,我们计算如图B-1所示的部分和。我们把每一列相加,如果有进位,就加到下一列。注意以下几点:
1————————第16列的进位
1 1————————第15列的进位
| 1
| 1 0
| | 1 1
| | | 1 0
| | | | 1 0
| | | | | 1 1
| | | | | | | 1 0
| | | | | | | | 1 0
| | | | | | | | | 1 1
| | | | | | | | | | 1 1
| | | | | | | | | | 1 0 0———–第3列的进位
| | | | | | | | | | | 1 0 0———–第2列的进位
| | | | | | | | | | | | | 1 1———第1列的进位
| | | | | | | | | | | | | | |
1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 1
1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0
0 0 0 0 1 1 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 1
0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0
0 1 0 0 1 0 0 1 0 1 0 0 1 1 1 1
0 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0
__________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 部分和
图B-1 二进制记法的部分和
1,当我们加第1列(最右边一列)的时候,我们得到7。在二进制中,数7是111。我们保留最右边的1,把其余的位进到第2列和第3列。
2,当我们加第2列时,我们计入从第1列来的进位。结果是8,它是二进制的1000。我们保留第一个位(最右边的),把其余100进位给第3列、第4列和第5列。
3,对每一列重复以上过程。
4,当我们加完最后一列时,我们有两个1没有列可以进行相加。这两个1在下一个步骤中应与部分和(Partial sum)相加。
B.1.2和
如果最后一列没有进位,那么部分和就是和。但是,如果还有额外的列(在本例中,有一个具有两行的列),那么就要把它加到部分和中,以便得出和。下图给出了这样的计算,现在我们得出了和。
1 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 部分和
1
1
____________________________________
1 0 0 1 0 1 1 0 1 1 1 0 1 0 1 1 和
0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 校验和
图B-2 二进制记法的和与校验和
B.1.2校验和
在计算出和以后,我们把每一个位求反码,得出检验和。图B-2也给出了检验和。二进制计算方法其实可以转换为十进制计算,原理相同。
算法的实现:
首先,查看了Linux 2.6内核中的校验算法,使用汇编语言编写的,显然效率要高些。代码如下:
unsigned short ip_fast_csum(unsigned char * iph,
unsigned int ihl)
{
unsigned int sum;
__asm__ __volatile__(
“movl (%1), %0 ;\n”
“subl $4, %2 ;\n”
“jbe 2f ;\n”
“addl 4(%1), %0 ;\n”
“adcl 8(%1), %0 ;\n”
“adcl 12(%1), %0 ;\n”
“1: adcl 16(%1), %0 ;\n”
“lea 4(%1), %1 ;\n”
“decl %2 ;\n”
“jne 1b ;\n”
“adcl $0, %0 ;\n”
“movl %0, %2 ;\n”
“shrl $16, %0 ;\n”
“addw %w2, %w0 ;\n”
“adcl $0, %0 ;\n”
“notl %0 ;\n”
“2: ;\n”
/* Since the input registers which are loaded with iph and ihl
are modified, we must also specify them as outputs, or gcc
will assume they contain their original values. */
: “=r” (sum), “=r” (iph), “=r” (ihl)
: “1” (iph), “2” (ihl)
: “memory”);
return(sum);
}
在这个函数中,第一个参数显然就是IP数据报的首地址,所有算法几乎一样。需要注意的是第二个参数,它是直接使用IP数据报头信息中的首部长度字段,不需要进行转换,因此,速度又快了(高手就是考虑的周到)。使用方法会在下面的例子代码中给出。
第二种算法就非常普通了,是用C语言编写的。我看了许多实现网络协议栈的代码,这个算法是最常用的了,即使变化,也无非是先取反后取和之类的。考虑其原因,估计还是C语言的移植性更好吧。下面是该函数的实现:
unsigned short checksum(unsigned short *buf,int nword)
{
unsigned long sum;
for(sum=0;nword>0;nword–)
sum += *buf++;
sum = (sum>>16) + (sum&0xffff);
sum += (sum>>16);
return ~sum;
}
转载请注明 :IT樵客
文章地址:http://www.itlogger.com/network/820.html
标签:
相关文章

2 thoughts on “校验和算法、校验和计算(二进制反码求和)

  1. 第一列相加是等于8吧

  2. 钢格板 回复@

    好文章,内容笔下生辉

发表评论

电子邮件地址不会被公开。 必填项已用*标注