算法原理：
假定 output[2] 为输出结果，input[n]为待计算校验和的内存块。
1）所有奇数位[0,2,4……] byte 累加进 结果的奇数位内存 output[0]，如果溢出，则进位给偶数位的 output[1]；
2）所有偶数位[1,3,5……] byte 累加进 结果的偶数位内存 output[1]，如果溢出，则进位给奇数位的 output[0]；
3）最后对 output[2] 求反码即可
示例代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import struct
import sys def ip_cksum(s): a = 0
b = 0 # 偶数序号的 unsigned char 互相累加
for i in xrange(0, len(s), 2):
a += struct.unpack('B', s[i])[0] # 奇数序号的 unsigned char 互相累加
for i in xrange(1, len(s), 2):
b += struct.unpack('B', s[i])[0] # 缩小值为 unsigned char
while a > 256 or b > 256:
b += a/256 # a 超过 byte 的部分进位给 b
a = a%256 a += b/256 # b 超过 byte 的部分进位给 a
b = b%256 # 取反
a = ~a & 0xff
b = ~b & 0xff # 校验和作为字符串
v = chr(a) + chr(b) # 校验和作为 unsigned short
v = struct.unpack('H', v)[0] return v if __name__ == '__main__':
for i in sys.argv[1:]:
print ip_cksum(i)
关于TCP/IP 校验和计算的代码，网上很多，但不少都有些问题，这里作一番简单分析
1.最尾部 byte 处理依赖机序
来自 http://locklessinc.com/articles/tcp_checksum/ 的 C 代码片段：
unsigned short checksum1(const char *buf, unsigned size)
{
unsigned sum = ;
int i; /* Accumulate checksum */
for (i = ; i < size - ; i += )
{
unsigned short word16 = *(unsigned short *) &buf[i];
sum += word16;
} /* Handle odd-sized case */
if (size & )
{
unsigned short word16 = (unsigned char) buf[i];
sum += word16;
} /* Fold to get the ones-complement result */
while (sum >> ) sum = (sum & 0xFFFF)+(sum >> ); /* Invert to get the negative in ones-complement arithmetic */
return ~sum;
}
注意第16行，对于buffer 长度非偶数情况的处理， 导致此代码只可在 Little-Endian (如x86) 机器上运行。只需对最后一个 byte 补一个’\0'的 byte，凑够两个 byte 然后转为 unsinged short 相加即可。
2.多内存块的计算
来自 python 网络包创建、解析库 dpkt 的代码 dpkt.py
try:
import dnet
def in_cksum_add(s, buf):
return dnet.ip_cksum_add(buf, s)
def in_cksum_done(s):
return socket.ntohs(dnet.ip_cksum_carry(s))
except ImportError:
import array
def in_cksum_add(s, buf):
n = len(buf)
cnt = (n / 2) * 2
a = array.array('H', buf[:cnt])
if cnt != n:
a.append(struct.unpack('H', buf[-1] + '\x00')[0])
return s + sum(a)
def in_cksum_done(s):
s = (s >> 16) + (s & 0xffff)
s += (s >> 16)
return socket.ntohs(~s & 0xffff)
它这里会有两个实现，一个是调用dnet库的实现（见2-6行），一个是用python自己实现的版本（见8-19行）。
dnet 库是 C 实现的一个库，但和 dpkt 库是同一个作者，这里都有一个共同的问题：对于 in_cksum_add 进的内存块，如果为奇数长度，则尾部会追加一个byte '\x00' （见14行），这里就导致了问题。其实呢，尾部的那个 byte 应该留给下一个接下来的内存块一起计算，当且仅当所有的内存块都处理完毕（即 in_cksum_done 时），多余一个 byte 时才该追加 byte '\x00'。
3.经典的实现
来自 wireshark 的 in_cksum.c
/*
* Checksum routine for Internet Protocol family headers (Portable Version).
*
* This routine is very heavily used in the network
* code and should be modified for each CPU to be as fast as possible.
*/ #define ADDCARRY(x) {if ((x) > 65535) (x) -= 65535;}
#define REDUCE {l_util.l = sum; sum = l_util.s[0] + l_util.s[1]; ADDCARRY(sum);} int
in_cksum(const vec_t *vec, int veclen)
{
register const guint16 *w;
register int sum = ;
register int mlen = ;
int byte_swapped = ; union {
guint8 c[];
guint16 s;
} s_util;
union {
guint16 s[];
guint32 l;
} l_util; for (; veclen != ; vec++, veclen--) {
if (vec->len == )
continue;
w = (const guint16 *)(const void *)vec->ptr;
if (mlen == -) {
/*
* The first byte of this chunk is the continuation
* of a word spanning between this chunk and the
* last chunk.
*
* s_util.c[0] is already saved when scanning previous
* chunk.
*/
s_util.c[] = *(const guint8 *)w;
sum += s_util.s;
w = (const guint16 *)(const void *)((const guint8 *)w + );
mlen = vec->len - ;
} else
mlen = vec->len;
/*
* Force to even boundary.
*/
if (( & (unsigned long) w) && (mlen > )) {
REDUCE;
sum <<= ;
s_util.c[] = *(const guint8 *)w;
w = (const guint16 *)(const void *)((const guint8 *)w + );
mlen--;
byte_swapped = ;
}
/*
* Unroll the loop to make overhead from
* branches &c small.
*/
while ((mlen -= ) >= ) {
sum += w[]; sum += w[]; sum += w[]; sum += w[];
sum += w[]; sum += w[]; sum += w[]; sum += w[];
sum += w[]; sum += w[]; sum += w[]; sum += w[];
sum += w[]; sum += w[]; sum += w[]; sum += w[];
w += ;
}
mlen += ;
while ((mlen -= ) >= ) {
sum += w[]; sum += w[]; sum += w[]; sum += w[];
w += ;
}
mlen += ;
if (mlen == && byte_swapped == )
continue;
REDUCE;
while ((mlen -= ) >= ) {
sum += *w++;
}
if (byte_swapped) {
REDUCE;
sum <<= ;
byte_swapped = ;
if (mlen == -) {
s_util.c[] = *(const guint8 *)w;
sum += s_util.s;
mlen = ;
} else
mlen = -;
} else if (mlen == -)
s_util.c[] = *(const guint8 *)w;
}
if (mlen == -) {
/* The last mbuf has odd # of bytes. Follow the
standard (the odd byte may be shifted left by 8 bits
or not as determined by endian-ness of the machine) */
s_util.c[] = ;
sum += s_util.s;
}
REDUCE;
return (~sum & 0xffff);
}
1）92行是当前内存块还余一个 byte ，则会 s_util 等待下个内存卡再处理——恰当的处理前面提到的第二个问题
2）94行是所有内存块处理完毕后，对尾部最后一个 byte 的处理 ——恰当的处理了前面提到的第一个问题
3）看点：指针非对齐的情况下处理
50行会先将未对其的1个 byte 暂存，这样可迫使指针对齐，但又为了让同奇位、同偶位内存相加，所以使 sum<<8；81行，如果前面sum是已经左移过的，则再次 sum<<8，让sum回归最初的奇偶次序
注：REDUCE 宏实现的功能是将大于 short 的值(即大于65535)转化为 short 能表示的值.