词条 | 二进制反码求和 |
释义 | 0和0相加是0,0和1相加是1,1和1相加是0但要产生一个进位1,加到下一列.若最高位相加后产生进位,则最后得到的结果要加1. IP/ICMP/IGMP/TCP/UDP等协议的校验和算法都是相同的,算法如下: 在发送数据时,为了计算IP数据包的校验和。应该按如下步骤: (1)把IP数据包的校验和字段置为0; (2)把首部看成以16位为单位的数字组成,依次进行二进制反码求和; (3)把得到的结果存入校验和字段中。 在接收数据时,计算数据包的校验和相对简单,按如下步骤: (1)把首部看成以16位为单位的数字组成,依次进行二进制反码求和,包括校验和字段; (2)检查计算出的校验和的结果是否等于零(反码应为16个0); (3)如果等于零,说明被整除,校验是和正确。否则,校验和就是错误的,协议栈要抛弃这个数据包。 所谓的二进制反码求和,即为先进行二进制求和,然后对和取反。 计算对IP首部检验和的算法如下: (1)把IP数据包的校验和字段置为0; (2)把首部看成以16位为单位的数字组成,依次进行二进制求和(注意:求和时应将最高位的进位保存,所以加法应采用32位加法); (3)将上述加法过程中产生的进位(最高位的进位)加到低16位(采用32位加法时,即为将高16位与低16位相加,之后还要把该次加法最高位产生的进位加到低16位) (4)将上述的和取反,即得到校验和。 其中,二进制反码求和的计算方法: 首先,我们计算如图B-1所示的部分和。我们把每一列相加,如果有进位,就加到下一列。注意以下几点: 1-->16 1 1-->15 * 1-->14 * 1-->13 * * 1 1-->12 * * * 1-->11 * * * * 1-->10 * * * * * 1 1-->9 * * * * * * * 1 1-->7 * * * * * * * * * 1-->6 * * * * * * * * * 1-->5 * * * * * * * * * 1-->4 * * * * * * * * * * 1-->3 * * * * * * * * * * * * 1 1-->2 * * * * * * * * * * * * 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 1 0 部分和 1 -->第15列的进位 1 -->第16列的进位 __________________________________ 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 和 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 校验和 图B-1 二进制记法的部分和 1,当我们加第1列(最右边一列)的时候,我们得到8。在二进制中,数8是1000。我们保留最右边的0,把其余的位进到第2列,第3列和第4列。 2,当我们加第2列时,我们计入从第1列来的进位。结果是7,它是二进制的0111。我们保留第一个位(最右边的),把其余011进位给第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 1 0 部分和 1 0 -->第15,16列的进位 __________________________________ 1 0 0 1 0 1 1 0 1 1 1 0 1 1 0 0 和 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 1 校验和 图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 ;\" "subl $4, %2 ;\" "jbe 2f ;\" "addl 4(%1), %0 ;\" "adcl 8(%1), %0 ;\" "adcl 12(%1), %0 ;\" "1: adcl 16(%1), %0 ;\" "lea 4(%1), %1 ;\" "decl %2 ;\" "jne 1b ;\" "adcl $0, %0 ;\" "movl %0, %2 ;\" "shrl $16, %0 ;\" "addw %w2, %w0 ;\" "adcl $0, %0 ;\" "notl %0 ;\" "2: ;\" /* 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; } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。