Checksum

  1. 1. 校验和
    1. 1.1. 校验和性质
      1. 1.1.1. Commutative and Associative
      2. 1.1.2. Byte Order Independence
      3. 1.1.3. Parallel Summation
    2. 1.2. Coding Techniques
      1. 1.2.1. Incremental Update

校验和

选择一系列八进制数A, B, C, D, …, Y, Z

选8进制是因为8个bit为一个byte

使用记号[a,b]表示一个16进制数,其中a,b分别为8进制数,且a,b分别为这个16进制数的高八位与低八位。

则反码和(complement sum)为以下二者之一:

[1] \([A, B] +' [C, D] +' \cdots +' [Y, Z]\)

[2] \([A, B] +' [C, D] +' \cdots +' [Z, 0]\)

其中, \(+'\)表示反码相加(complement addition)。存在两种情况的原因是字节数可能为奇,可能为偶。其中为奇则补0

进位采用循环进位(end around carry)的方式,即溢出回卷。

\(\because Checksum = \sim (number1 + nubmer2 + \cdots + numberN)\)

\(\therefore Checksum + (number1 + nubmer2 + \cdots + numberN) = 0xFFFF\)

校验和性质

Commutative and Associative

反码和的计算可以以任意顺序,且可以任意分组计算——即满足交换率和结合率。

如[1]可以写作:

\(([A, B] +' [C, D] +' \cdots +' [J,0]) +' ([0, K] + \cdots+' [Y, Z])\)

Byte Order Independence

所有16 bit数的反码和计算可以用任意byte顺序,仅需要保证所有字节为同一顺序即可。

如[1]可以写作:

\([B, A] +' [D, C] +' \cdots +' [Z, Y]\)

当然,最后的结果的byte位也是按此顺序的。

原因可这样想

我们取旧的数为\([A,B]\),其中A由高到低为15-8位,B由高到低为7-0位。则这个字可如下表示:

15  8 7   0
+--------|--------+
|  A  |  B  |

在跨字节进位过程中,进位仅出现在7->8, 15->0。

此时交换A, B位置为\([B, A]\),则这个字可如下表示:

7  0 15   8
+--------|--------+
|  B  |  A  |

则此时在跨字节进位过程中,进位仍出现在7->8, 15->0。

故最后的结果也仅仅是调换了byte位置而已,并不影响他们本身的数字绝对大小。

这个性质也就保证了在不同CPU上(尤指对16位数的高位、低位计算方法不同的CPU),计算出的结果相同。

Parallel Summation

由于有第一个性质,即满足交换率与结合率,也就没有计算顺序限制。无需按数字在byte流中出现的顺序计算。因而可以将其在塞入一个更大的数,如32位中,进行一种类似“并行”的运算。

如在32-bit计算机中,可以如下计算[1]式:

\([A, B, C, D] +' \cdots\)

而后将其高16位与低16位相加,从而得到的即为所需校验和,且与[1]所得结果相同。个中原因分析参考性质2.

Coding Techniques

Incremental Update

避免重新计算整个数据报即可更新Checksum

记旧Checksum为C,新Checksum为C‘。原始数据报和为m,更改后新的数据报和为m’

\(C + (0xFFFF - m) = C' + (0xFFFF - m') = 0xFFFF\)

\(C' = C + (m' - m)\)

此即完成了更新。


运算例子:(以下所有数为16进制表示)

Byte-by-Byte “Normal”
Order
Swapped
Order
Byte 0/1 00 01 0001 0100
Byte 2/3 f2 03 f203 03f2
Byte 4/5 f4 f5 f4f5 f5f4
Byte 6/7 f6 f7 f6f7 f7f6
Sum1 2dc 1f0 2ddf0 1f2dc
Sum2 dd f2 ddf2 f2dd
Final Swap dd f2 ddf2 ddf2
Byte-by-Byte “Normal”
Order
Swapped
Order
Byte 0/1/2/3 0001 f203 010003f2 03f20100
Byte 4/5/6/7 f4f5 f6f7 f5f4f7f6 f7f6f5f4
Sum1 f4f7 e8fa f6f4fbe8 fbe8f6f4
Top half f4f7 f6f4 fbe8
Botton half e8fa fbe8 f6f4
Sum2 1ddf1 1f2dc 1f2dc
Sum3 ddf2 f2dd f2dd
Final Swap ddf2 ddf2 ddf2

参考资料:

RFC1071