（转）checksum算法

转自：http://www.falaosao.net/?p=1344

本质就是计算所有数据的和，存入checksum，然后在接受端也一样操作，同时加上取反后的checksum，若为全1表示＂准确＂

在发送数据时，为了计算数IP据报的校验和。应该按如下步骤：

(1) 把IP数据报的校验和字段置为0。

(2) 把首部看成以16位为单位的数字组成，依次进行二进制反码求和。

(3) 把得到的结果存入校验和字段中。

在接收数据时，计算数据报的校验和相对简单，按如下步骤：

（1）把首部看成以16位为单位的数字组成，依次进行二进制反码求和，包括校验和字段。

（2）检查计算出的校验和的结果是否等于零。

（3）如果等于零，说明被整除，校验是和正确。否则，校验和就是错误的，协议栈要抛弃这个数据包。

Linux 2.6内核中的校验算法，使用汇编语言编写的，显然效率要高些

/usr/src/linux-2.6.23/include/asm-i386/checksum.h

static inline __sum16 ip_fast_csum(const void *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"
: "=r" (sum), "=r" (iph), "=r" (ihl)
: "1" (iph), "2" (ihl)
: "memory");
return (__force __sum16)sum;
}

(1) 将IP头部(包括可选项)以32位为单位进行进位加法运算

(2) 将sum的低16位和高16位相加

(3) 取反

1b -- 1 before

在这个函数中，第一个参数显然就是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;
}