TCP/IP 体系中有两种校验机制:CRC 校验与校验和,用于保证消息的完整性。CRC 校验用于整个以太网帧的校验,32 位的校验码被添加到以太网帧的最后四个字节。更为常用的是校验和机制,被用于 IP,ICMP,TCP,UDP 等三四层协议中。
作者:李凡
来源:https://zhuanlan.zhihu.com/p/61236878
运算机制
校验和机制的运算很简单,计算方法为将校验范围内的字节取反相加,校验方法为将校验范围内的字节与校验和相加,如果结果为 1 ,则代表没有传输错误发生。
取反相加
取反相加,相加就相加了,为什么要取反?取反是因为上文提到的校验方式:
发送的消息字段为 1011,校验和取反相加:0100,最终发送的消息为 1011 0100
接收端验证消息时,将消息字段与校验和字段通通相加,得到:1011 + 0100 = 1111,全部为1,所以没有错误发生。
可见取反相加是为了能在校验时,直接将消息字段和校验码相加,通过结果是否为全 1 来判断是否有错误。利用的是二进制加法 1+1 = 0 的特性。
作为对比,小明同学提出一种不需要取反的方法,发送端消息字段相加得到校验位。接收端只将消息字段相加,然后和校验字段做比较。相当于发送端节省了取反的开销,而接收端的开销从做一次二进制加法+与全1做比较 变成 一次比较(数据字段相加后与校验和字段比较)。那么两种方法孰优孰劣?为什么 TCP/IP 选择了前者。作者目前的理解是,当时的设计者基于当时的硬件开销状况,选择了目前使用的这套校验机制。可能现在的开销情况会有所不同,需要一些更细致的硬件实现细节和实验来了解。
多做无功
显然校验和只能发现奇数位错误,曾经学过通信原理的小明同学表示,为什么不用汉明码,最小码距 3 ,可以检 2 个错,还能纠 1 个错。对于在三层以上使用的校验和来说,检错太多可以算得上是多做无功,因为数据已经通过了二层的检验机制,去除了那些受到了严重错误的数据。过大的校验开销并不实用。
溢出处理
两个数相加,可能是 8 位,也可能是 16 位,亦或者是 32 位,总有可能会溢出,这多了一位如何是好。
简单 把这溢出的 1 加到最低位去
这里只需要一个固定的生成/验证校验机制,并不是运算。
那如果又溢出了呢?
那就再加到最低位去。
能少做就少做
对每个数先取反再相加似乎很麻烦,把每个数加起来再取反好像容易多了,并且两者是相同的。
1011 取反-> 0100 0110 取反-> 1001 取反相加 1101
直接相加-> 10001 处理溢出 -> 0010 取反 -> 1101 两者相同
在 LwIP 实现中,使用将所有校验区域字段相加再取反的方式,减少了每次取反的操作开销。
校验和的宽度
在 IP 数据报首部校验中,校验和的宽度为 16bit ,两个字节。校验和本身的长度决定了累加字段的宽度。IP 首部校验和计算中,以两个字节为单位进行累加。
字节0 字节1 + 字节2 字节3 + .....+校验和字节0 校验和字节1.
在校验和程序中,按照主机字节序进行计算,即低地址在前,最后将生成的校验和转换为网络字节序。需要转换因为校验和的宽度为 16 位,如果校验只有 1 个字节,那么就无所谓字节序的转换了。
在将两个字节组成 16 位待累加数时,低地址的字节在高位,这对应于协议中字节的位置,具体可以参见下方的 LwIP 程序实现。
LwIP 的校验和实现
LwIP 提供了不只一种校验的标准实现方式,多种方式可以通过定义在 lwipopts.h 中的宏定义进行切换。
校验和相关的函数位于 LwIP 根目录下的 /core/inet\_chksum.c 中。inet\_chksum 函数为校验和计算提供统一的入口,接收两个参数:校验区域的开始地址以及校验区域的字节长度。
inet\_chksum 函数中调用了真正的校验和计算函数,我们首先分析 v1.4.1 版本中的校验和函数:
V1.4.1 版本的标准校验和程序
static u16_t
lwip_standard_chksum(void *dataptr, u16_t len)
{
u32_t acc; //32位累加数
u16_t src; //16位待累加数
u8_t *octetptr; //取地址指针
acc = 0;
octetptr = (u8_t*)dataptr;
while (len > 1) {
src = (*octetptr) << 8; //获得第一个字节,比如字节0
octetptr++; //地址累加
src |= (*octetptr); //获得第二个字节,与第一个字节拼接成 字节0 字节1 16bit待运算数据
octetptr++;
acc += src; //累加待运算数
len -= 2; //消灭了两个校验区域内的字节
}
if (len > 0) { //在离开上方 len > 1 的 while之后,如果进入这个 if 语句代表 len = 1,
src = (*octetptr) << 8; //只剩下一字节需要处理,将其放到高8位,低8位置0
acc += src;
}
//完成了所有数的累加后,开始处理进位。
//溢出的机制是,如果发生了溢出,则无视溢出的 1 ,将 1 加到求和结果中
//LwIP 这里的处理是:不关心每次溢出的产生,将所有数完成求和后,统一将高 16 位(溢出数)加到低 16 位(求和数)
//溢出数就相当于溢出的总次数,每次溢出加1,那么将溢出次数统一加到结果中即可
acc = (acc >> 16) + (acc & 0x0000ffffUL);
//在完成上一次操作后,可能又发生了溢出,再执行一次同样的操作,请问是否可能再发生溢出?
if ((acc & 0xffff0000UL) != 0) {
acc = (acc >> 16) + (acc & 0x0000ffffUL);
}
//将校验和转换为网络字节序
return htons((u16_t)acc);
}
这里讨论几个问题,一是 LwIP 实现中校验和的溢出处理。我们之前说到如果发生了溢出,则无视溢出的 1 ,将 1 加到求和结果中。这是从每次计算->处理溢出的思路上来说的。
LwIP 实现中,通过声明一个 32 位的累加数,先将所有的 16bit数累加,得到溢出的总数(累加数的高 16 位),一起加到校验和结果(低 16 位)中。
这里存在两个问题:16bit 数累加时,如果有 2^16 个数累加,那么会使 32 位数本身发生溢出,但好在目前人类还没提出这么长的协议,所有不用担心 32 位数的溢出问题。
另一个问题是,如果将溢出数与结果数累加后,有可能再次溢出 1 ,所以在完成第一次高 16 位与低 16 位的运算后,需要再进行一次该运算,第二次运算不可能产生溢出。(可以用最极端的情况考虑下 16bit 全1 与 16bit 全1 进行运算)
V2.0.2版本的标准校验和程序
V2.0 版本的默认标准校验和函数使用一种经过优化的校验和计算函数,在循环中一次计算 8字节,对开始和结束的非 8 字节对齐字节,则另行处理。
u16_t
lwip_standard_chksum(const void *dataptr, int len)
{
const u8_t *pb = (const u8_t *)dataptr; //取地址指针
const u16_t *ps;
u16_t t = 0;
const u32_t *pl;
u32_t sum = 0, tmp;
/* starts at odd byte address? */
int odd = ((mem_ptr_t)pb & 1); //判断地址是否为奇地址 即 0x1/0x3
if (odd && len > 0) { //缓存奇地址上的字节,存于 t 的高位
((u8_t *)&t)[1] = *pb++; //如果从奇地址开始,使用主机顺序
len--;
}
ps = (const u16_t *)(const void*)pb;
if (((mem_ptr_t)ps & 3) && len > 1) { //累加没有4字节对齐的 2字节 16位
sum += *ps++;
len -= 2;
}
pl = (const u32_t *)(const void*)ps;
while (len > 7) { //在循环中进行 8字节 累加
tmp = sum + *pl++; //累加 8 字节中的第一个 4 字节 32 位
if (tmp < sum) { //如果累加之后还比加数小,那说明发生了溢出,进行溢出处理
tmp++;
}
sum = tmp + *pl++;
if (sum < tmp) {
sum++;
}
len -= 8;
}
sum = FOLD_U32T(sum);
ps = (const u16_t *)pl;
while (len > 1) { //剩下超过两个字节,必定包含一个对齐的 16 位字
sum += *ps++;
len -= 2;
}
if (len > 0) {
((u8_t *)&t)[0] = *(const u8_t *)ps; //还剩下一个字节,放到缓存 t 的低位上
}
sum += t;
sum = FOLD_U32T(sum); //进行溢出处理操作 作用和之前版本的语句相同
sum = FOLD_U32T(sum); //直接进行两次高位和低位相加,而不再对是否溢出进行判断
if (odd) {
sum = SWAP_BYTES_IN_WORD(sum); //如果是从奇地址开始,累加和生成的顺序为主机字节序
//如果本身就是偶地址对齐,使用的是网络字节序,就不需要再进行一次转换
}
return (u16_t)sum;
}
新版本通过一次计算 8 字节,相比 1.4 版本中一次进行两字节运算,加快了校验和累加的速度。但这样一来就必须对非对齐的字节进行处理,因为需要计算的校验和字节数不一定是 8 字节对齐的。程序分别对开始和结束处的单字节数据和双字节数据做了处理。
程序的巧妙之处不少,如果校验和计算地址从奇地址开始,那么校验和的计算顺序使用主机字节序,反之则使用网络字节序。
另外将高 16 位加到低 16 位的操作会直接执行两次。先前的版本执行第二次相加操作时,会先进行一次判断。直接执行加法操作可能要比做判断快一些。
老实说,作者目前对这个函数的原理还只是略懂,这里暂时不继续展开了,欢迎有兴趣的读者一起讨论。
校验和的生成与判断
校验和的计算和校验都使用上述的校验和生成函数完成。在发送端生成校验时,校验和字段先填充为 0 ,计算完成后将结果填入校验和字段发送。接收端则直接对所有字段进行校验和计算,判断计算结果是否为全 1 。
一次错误的校验和经历
在一次自环测试中,使用网络助手发送某些字符串可以接收到同样的字符串,完成自环测试。但是某些字符串发送后却接收不到 。通过 Wireshark 抓包发现,字符所在的包收到了,但是因为 UDP 校验和错误没有被操作系统交付给应用层网络调试助手显示。
那么为什么有些字符串可以通过校验,有些字符串却会有校验和错误,而且发现他们的校验和总是比正确的校验和大 1。
通过检查发现,网络助手对端协议栈使用和 LwIP 1.4 版本类似的方法实现校验和,使用 32 位变量累加 16 位字段的校验和,但是没有处理 32 位变量的进位,导致在产生进位的情况下,校验和比正确的结果小 1,所以在取反后就比正确的结果大 1 。
校验和的错误实现会造成协议栈的错误,更糟糕的是这些错误似乎“偶尔”发生。
校验和计算的硬件实现
对于硬件 Verilog 来说,假设要校验的字段以数据流的形式输入,那么只要不断将输入的数据流相加,最后取反即可,也会在后续的文章中更详细地讨论硬件的实现。
结语
本文讨论校验和的实现方式以及一些细节问题,具体分析了 LwIP 中的两种软件实现,并将在后续的文章中继续讨论硬件校验和的实现。
推荐阅读
关注此系列,请关注专栏FPGA的逻辑