详解TCP/IP协议族中的Checksum（头部校验和）

2018-02-28

前言

Checksum算法广泛应用于TCP/IP协议族，用于校验IP、TCP、UDP数据。以IP协议为例，如下图：

IP协议

其中大部分字段看看文档就能明白，只是头部校验和checksum字段，协议中没有提供算法和示例。以下内容将详细介绍checksum的原理和算法，并提供C、PHP、Node.js的函数源码。


计算和校验的过程

在通信中，需要迅速校验数据的完整性和准确性，于是有了checksum。其过程如下：

  1. 发送方对数据中每16位进行二进制反码求和，同时将进位加到校验和的低字节上（记为a），再取反（记为-a），插入到头部中，发到网络中；
  2. 接收方拿到数据，按每16位进行二进制反码求和，同时将进位加到校验和的低字节上（记为b）；
  3. 如果传输过程中，每个比特都没有改变，那么接收方的校验和（b=a-a）应该是0，那么数据传输正确；
  4. 如果校验和不为0，那么收到的数据是错的，丢弃。


举例：

4500 0073 0000 4000 4011 b861 c0a8 0001 c0a8 00c7 0035
 e97c 005f 279f 1e4b 8180 ...


这是一份IP报文，参考前文IP协议示意图，加粗部分为这份报文的头部，标红部分为头部的 Header checksum 字段。发送方的计算过程如下：

  1. 发送方先确定头部除了checksum字段的其他内容（上述加粗不标红部分），这时标红的checksum字段还没算出来所以是未知的。把除了checksum字段的头部内容按每16位求和： 4500 + 0073 + 0000 + 4000 + 4011 + c0a8 + 0001 + c0a8 + 00c7 = 2479C (转化为十进制就是149404)
  2. 转化为二进制： 0010 0100 0111 1001 1100
  3. 发现超过16位了，把进位部分和不进位的部分相加： 0010 + 0100 0111 1001 1100 = 0100 0111 1001 1110 （如果加完还是超过16位，则重复这个过程）
  4. 按位取反： 0100 0111 1001 1110 （取反前） 1011 1000 0110 0001 （取反后）
  5. 得到checksum字段的值1011 1000 0110 0001（B861），插入到头部指定位置，得到上述报文，发给接收方。


好，接收方现在收到了上述报文，报文头部也含有checksum字段了，该校验一下头部数据是否完整且准确。接收方校验过程如下：

  1. 把包括checksum字段的头部内容按每16位求和： 4500 + 0073 + 0000 + 4000 + 4011 + b861 + c0a8 + 0001 + c0a8 + 00c7 = 2fffd
  2. 进位部分和不进位部分相加，直到不进位： fffd + 2 = ffff
  3. 取反，得到0，校验正确。


上述求和过程，接收方比发送方多加了一个checksum校验位，而这个校验位刚好是其他数据求和的取反。因此数据正确时，接收方校验完总是0，而与校验位在数据中的位置无关。


Checksum特性

  1. 计算和校验和简单、快速；
  2. 对数据的长度无限制；
  3. 奇偶数不影响结果；
  4. 不依赖系统是大端小端，通用于接入网络的各种设备。


前三点好理解。第四点因为checksum求和时，大小端得到的结果相同，只是字节顺序相应地也交换了。举例：


数据：0xF1 0xF2 0xF3 0xF4 0xF5


大端：

0xF1F2 + 0xF3F4 + 0xF500 =0x02DAE6 // 求和

0xDAE6 + 0x02 = 0xDAE8 // 进位

0xDAE8 => 0x2517 // 取反


小端：

0xF2F1 + 0xF4F3 + 0x00F5 = 0x01E8D9 // 求和

0xE8D9 + 0x01 = 0xE8DA // 进位

0xE8DA => 0x1725 // 取反


大端的0x2517和小端的0x1725是一致的。这也是checksum使用反码的原因之一。如果你用原码或补码计算上述过程，就会发现大小端结果是不一致的。


源码

C：

unsigned short CheckSum(unsigned short * addr, int size) {
    unsigned long ckSum = 0;
    // 按每16位求和
    while (size > 1) {
        ckSum += *(unsigned short*)addr++;
        size -= 2
    }
    // 如果数据长度为奇数，再补一个空字节
    if (size > 0) {
        char left_over[2] = {0};
        left_over[0] = *addr;
        ckSum += * (unsigned short*) left_over;
    }
    // 进位相加，直到没有进位
    while (cksum >> 16)
        ckSum = (ckSum & 0xffff) + (ckSum >> 16);
    // 返回反码
    return ~cksum;
}


PHP：

function CheckSum($buff, $size) {
    $cksum = 0;
    $index = 0;
    // 按每16位求和
    while ($size > 1) {
        $cksum += unpack("S*",substr($buff, $index, 2))[1];
        $index += 2;
        $size -= 2;
    }
    // 如果数据长度为奇数，再补一个空字节
    if ($size) {
        $cksum += ord(substr($buff, -1 * $size));
    }
    // 进位相加，直到没有进位
    while ($cksum >> 16)
        $cksum = ($cksum >> 16) + ($cksum & 0xffff);
    // 返回反码
    return ~$cksum;
}


Node.js：

function CheckSum (buf, size) {
    var cksum = 0, start = 0;
    // 按每16位求和
    while (size > 1) {
        cksum += buf.readUInt16LE(start);
        start += 2;
        size -= 2;
    }
    // 如果数据长度为奇数，再补一个空字节
    if (size) {
        cksum += buf.readUIntLE(start);
    }
    // 进位相加，直到没有进位
    while (cksum >> 16)
        cksum = (cksum >> 16) + (cksum & 0xffff);
    // 返回反码
    return ~cksum;    
};


顺便安利一个Node.js的库node-checksum，直接运行“npm install node-checksum”就能用了。这个库的作者是我现在的老大 程序员小卡，感谢他的指导。



参考文献

  1. Internet Protocol specification (rfc791)
  2. Computing the Internet Checksum (rfc1071)
  3. wikipedia：IPv4 header checksum




本文未经许可禁止转载，如需转载关注微信公众号【工程师加一】并留言。