Checksum
概念
检验和 (
checksum)，在数据处理和数据通信领域中，用于 校验目的 的一组数据项的和，用来校验数据的完整性和准确性。
一般的 checksum 计算方法
-
把要计算
checksum的数据内容分成以每两个字节为一组的分组。如果最后剩余单个字节，补一个内容为 0 的字节。如数据：hello world
String: hello world h e l l o '空格' w o r l d HEX: 68 65 6C 6C 6F 20 77 6F 72 6C 64 BIN: 0110 1000 0110 0101 0110 1100 0110 1100 0110 1111 0010 0000 0111 0111 0110 1111 0111 0010 0110 1100 0110 0100分组：每16位一组
h e 0110 1000 0110 0101 l l 0110 1100 0110 1100 o '空格' 0110 1111 0010 0000 w o 0111 0111 0110 1111 r l 0111 0010 0110 1100 d 0 #补一个为 0 的字节 0110 0100 0000 0000 -
将所有分组（16bit）累加起来，累加过程中，如果结果溢出（超过16bit），将溢出的位作为新的分组累加上去
h e 0110 1000 0110 0101 l l + 0110 1100 0110 1100 ------------------------------------- = 1101 0100 1101 0001 o '空格' + 0110 1111 0010 0000 ------------------------------------- = 1 0100 0011 1111 0001 #溢出 #累加溢出位 0100 0011 1111 0001 + 0000 0000 0000 0001 #溢出数据 ------------------------------------- = 0100 0011 1111 0010 w o + 0111 0111 0110 1111 ------------------------------------- = 1011 1011 0110 0001 r l + 0111 0010 0110 1100 ------------------------------------- = 1 0010 1101 1100 1101 #溢出 #累加溢出位 0010 1101 1100 1101 + 0000 0000 0000 0001 #溢出数据 ------------------------------------- = 0010 1101 1100 1110 d 0 + 0110 0100 0000 0000 #补一个为0的字节 ------------------------------------- = 1001 0001 1100 1110 ~ ------------------------------------- 0110 1110 0011 0001 #取反后的值即为 checksum hex: 6E31 -
将最终累加得到的16bit值按位取反，得到checksum的值
1001 0001 1100 1110
按位取反得到：0110 1110 0011 0001 ==> 6E31
C 语言实现
#include
#include
/**
* 宿主机ubuntu18.04 x64是小端机器
*/
#define _LITTLE_ENDIAN_
//#define _BIG_ENDIAN_
#if defined(_LITTLE_ENDIAN_)
#define WORD_SWAP(v) ((unsigned short)(((v>>8)&0xff) | ((v<<8)&0xff00)))
#elif defined(_BIG_ENDIAN_)
#define WORD_SWAP(v) (v)
#endif
/**
* @Name - 计算校验和
* @Parameter *data - 要计算校验和的数据，非空指针
* @Parameter len - 要计算校验和的数据长度
*/
unsigned short cksum(unsigned char *data, int len)
{
unsigned int sum = 0;
unsigned short cksum = 0;
while (len > 1) {
sum += (*((unsigned short *)data));
len -= 2;
data += 2;
}
if (len > 0) { /* 每两个字节分组后剩余 1 byte */
#if defined(_LITTLE_ENDIAN_)
sum += *data;
#elif defined(_BIG_ENDIAN_)
sum += ((*data << 8) & 0xff00);
#endif
}
/* 把溢出位累加到sum */
while(sum >> 16) {
sum = (sum & 0xffff) | (sum >> 16);
}
cksum = (unsigned short)sum;
return WORD_SWAP(~cksum);
}
int main(int argc, char *argv[])
{
char *str = "hello world";
unsigned char data[] = { //hello world
0x68,0x65,
0x6C,0x6C,
0x6F,0x20,
0x77,0x6F,
0x72,0x6C,
0x64
};
printf("net byte order cksum = 0x%x\n", cksum(str, strlen(str)));
printf("net byte order cksum = 0x%x\n", cksum(data, sizeof(data)));
return 0;
}
run
┌──(shelmean?ubuntu)-[~/cksum]
└─$ gcc cksum.c -o cksum
┌──(shelmean?ubuntu)-[~/cksum]
└─$ ./cksum
net byte order cksum = 0x6e31
net byte order cksum = 0x6e31
应用
如 UDP 数据报中的应用
- 发送方在发送数据报之前，把 checksum 字段清空，然后计算整个报文的 checksum 值，把 checksum 值放入 checksum 字段
- 接收方收到这个数据之后，使用同样的 checksum 算法，计算整个 checksum，如果数据发送没有出错，则 checksum 计算出来应该是 0
即：~(~checksumval + checksumval) = 0
? ~checksumval是源数据中checksum字段清空后的所有数据的累加和
? checksumval是checksum字段的值
? 两部分累加后取反即是收到的数据的checksum
图示理解：
参考
【百度百科 校验和】
《Computer Networking A Top-Down Approach》