| 1 |
<pre>Network Working Group R. Braden |
| 2 |
Request for Comments: 1071 ISI |
| 3 |
D. Borman |
| 4 |
Cray Research |
| 5 |
C. Partridge |
| 6 |
BBN Laboratories |
| 7 |
September 1988 |
| 8 |
|
| 9 |
|
| 10 |
<span class="h1">Computing the Internet Checksum</span> |
| 11 |
|
| 12 |
|
| 13 |
Status of This Memo |
| 14 |
|
| 15 |
This memo summarizes techniques and algorithms for efficiently |
| 16 |
computing the Internet checksum. It is not a standard, but a set of |
| 17 |
useful implementation techniques. Distribution of this memo is |
| 18 |
unlimited. |
| 19 |
|
| 20 |
<span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. Introduction</span> |
| 21 |
|
| 22 |
This memo discusses methods for efficiently computing the Internet |
| 23 |
checksum that is used by the standard Internet protocols IP, UDP, and |
| 24 |
TCP. |
| 25 |
|
| 26 |
An efficient checksum implementation is critical to good performance. |
| 27 |
As advances in implementation techniques streamline the rest of the |
| 28 |
protocol processing, the checksum computation becomes one of the |
| 29 |
limiting factors on TCP performance, for example. It is usually |
| 30 |
appropriate to carefully hand-craft the checksum routine, exploiting |
| 31 |
every machine-dependent trick possible; a fraction of a microsecond |
| 32 |
per TCP data byte can add up to a significant CPU time savings |
| 33 |
overall. |
| 34 |
|
| 35 |
In outline, the Internet checksum algorithm is very simple: |
| 36 |
|
| 37 |
(1) Adjacent octets to be checksummed are paired to form 16-bit |
| 38 |
integers, and the 1's complement sum of these 16-bit integers is |
| 39 |
formed. |
| 40 |
|
| 41 |
(2) To generate a checksum, the checksum field itself is cleared, |
| 42 |
the 16-bit 1's complement sum is computed over the octets |
| 43 |
concerned, and the 1's complement of this sum is placed in the |
| 44 |
checksum field. |
| 45 |
|
| 46 |
(3) To check a checksum, the 1's complement sum is computed over the |
| 47 |
same set of octets, including the checksum field. If the result |
| 48 |
is all 1 bits (-0 in 1's complement arithmetic), the check |
| 49 |
succeeds. |
| 50 |
|
| 51 |
Suppose a checksum is to be computed over the sequence of octets |
| 52 |
|
| 53 |
|
| 54 |
|
| 55 |
<span class="grey">Braden, Borman, & Partridge [Page 1]</span></pre> |
| 56 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span> |
| 57 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 58 |
|
| 59 |
|
| 60 |
A, B, C, D, ... , Y, Z. Using the notation [a,b] for the 16-bit |
| 61 |
integer a*256+b, where a and b are bytes, then the 16-bit 1's |
| 62 |
complement sum of these bytes is given by one of the following: |
| 63 |
|
| 64 |
[A,B] +' [C,D] +' ... +' [Y,Z] [<a href="#ref-1" title=""A Protocol for Packet Network Communications,"">1</a>] |
| 65 |
|
| 66 |
[A,B] +' [C,D] +' ... +' [Z,0] [<a href="#ref-2" title=""The Organization of Computer Resources into a Packet Radio Network"">2</a>] |
| 67 |
|
| 68 |
where +' indicates 1's complement addition. These cases |
| 69 |
correspond to an even or odd count of bytes, respectively. |
| 70 |
|
| 71 |
On a 2's complement machine, the 1's complement sum must be |
| 72 |
computed by means of an "end around carry", i.e., any overflows |
| 73 |
from the most significant bits are added into the least |
| 74 |
significant bits. See the examples below. |
| 75 |
|
| 76 |
<a href="#section-2">Section 2</a> explores the properties of this checksum that may be |
| 77 |
exploited to speed its calculation. <a href="#section-3">Section 3</a> contains some |
| 78 |
numerical examples of the most important implementation |
| 79 |
techniques. Finally, <a href="#section-4">Section 4</a> includes examples of specific |
| 80 |
algorithms for a variety of common CPU types. We are grateful |
| 81 |
to Van Jacobson and Charley Kline for their contribution of |
| 82 |
algorithms to this section. |
| 83 |
|
| 84 |
The properties of the Internet checksum were originally |
| 85 |
discussed by Bill Plummer in IEN-45, entitled "Checksum Function |
| 86 |
Design". Since IEN-45 has not been widely available, we include |
| 87 |
it as an extended appendix to this RFC. |
| 88 |
|
| 89 |
2. Calculating the Checksum |
| 90 |
|
| 91 |
This simple checksum has a number of wonderful mathematical |
| 92 |
properties that may be exploited to speed its calculation, as we |
| 93 |
will now discuss. |
| 94 |
|
| 95 |
|
| 96 |
(A) Commutative and Associative |
| 97 |
|
| 98 |
As long as the even/odd assignment of bytes is respected, the |
| 99 |
sum can be done in any order, and it can be arbitrarily split |
| 100 |
into groups. |
| 101 |
|
| 102 |
For example, the sum [<a href="#ref-1" title=""A Protocol for Packet Network Communications,"">1</a>] could be split into: |
| 103 |
|
| 104 |
( [A,B] +' [C,D] +' ... +' [J,0] ) |
| 105 |
|
| 106 |
+' ( [0,K] +' ... +' [Y,Z] ) [<a href="#ref-3" title=""CPODA - A Demand Assignment Protocol for SatNet"">3</a>] |
| 107 |
|
| 108 |
|
| 109 |
|
| 110 |
|
| 111 |
|
| 112 |
|
| 113 |
|
| 114 |
<span class="grey">Braden, Borman, & Partridge [Page 2]</span></pre> |
| 115 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span> |
| 116 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 117 |
|
| 118 |
|
| 119 |
(B) Byte Order Independence |
| 120 |
|
| 121 |
The sum of 16-bit integers can be computed in either byte order. |
| 122 |
Thus, if we calculate the swapped sum: |
| 123 |
|
| 124 |
[B,A] +' [D,C] +' ... +' [Z,Y] [<a href="#ref-4" title=""Specifications for the Interconnection of a Host and an IMP"">4</a>] |
| 125 |
|
| 126 |
the result is the same as [<a href="#ref-1" title=""A Protocol for Packet Network Communications,"">1</a>], except the bytes are swapped in |
| 127 |
the sum! To see why this is so, observe that in both orders the |
| 128 |
carries are the same: from bit 15 to bit 0 and from bit 7 to bit |
| 129 |
8. In other words, consistently swapping bytes simply rotates |
| 130 |
the bits within the sum, but does not affect their internal |
| 131 |
ordering. |
| 132 |
|
| 133 |
Therefore, the sum may be calculated in exactly the same way |
| 134 |
regardless of the byte order ("big-endian" or "little-endian") |
| 135 |
of the underlaying hardware. For example, assume a "little- |
| 136 |
endian" machine summing data that is stored in memory in network |
| 137 |
("big-endian") order. Fetching each 16-bit word will swap |
| 138 |
bytes, resulting in the sum [<a href="#ref-4" title=""Specifications for the Interconnection of a Host and an IMP"">4</a>]; however, storing the result |
| 139 |
back into memory will swap the sum back into network byte order. |
| 140 |
|
| 141 |
Byte swapping may also be used explicitly to handle boundary |
| 142 |
alignment problems. For example, the second group in [<a href="#ref-3" title=""CPODA - A Demand Assignment Protocol for SatNet"">3</a>] can be |
| 143 |
calculated without concern to its odd/even origin, as: |
| 144 |
|
| 145 |
[K,L] +' ... +' [Z,0] |
| 146 |
|
| 147 |
if this sum is byte-swapped before it is added to the first |
| 148 |
group. See the example below. |
| 149 |
|
| 150 |
(C) Parallel Summation |
| 151 |
|
| 152 |
On machines that have word-sizes that are multiples of 16 bits, |
| 153 |
it is possible to develop even more efficient implementations. |
| 154 |
Because addition is associative, we do not have to sum the |
| 155 |
integers in the order they appear in the message. Instead we |
| 156 |
can add them in "parallel" by exploiting the larger word size. |
| 157 |
|
| 158 |
To compute the checksum in parallel, simply do a 1's complement |
| 159 |
addition of the message using the native word size of the |
| 160 |
machine. For example, on a 32-bit machine we can add 4 bytes at |
| 161 |
a time: [A,B,C,D]+'... When the sum has been computed, we "fold" |
| 162 |
the long sum into 16 bits by adding the 16-bit segments. Each |
| 163 |
16-bit addition may produce new end-around carries that must be |
| 164 |
added. |
| 165 |
|
| 166 |
Furthermore, again the byte order does not matter; we could |
| 167 |
instead sum 32-bit words: [D,C,B,A]+'... or [B,A,D,C]+'... and |
| 168 |
then swap the bytes of the final 16-bit sum as necessary. See |
| 169 |
the examples below. Any permutation is allowed that collects |
| 170 |
|
| 171 |
|
| 172 |
|
| 173 |
<span class="grey">Braden, Borman, & Partridge [Page 3]</span></pre> |
| 174 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span> |
| 175 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 176 |
|
| 177 |
|
| 178 |
all the even-numbered data bytes into one sum byte and the odd- |
| 179 |
numbered data bytes into the other sum byte. |
| 180 |
|
| 181 |
|
| 182 |
There are further coding techniques that can be exploited to speed up |
| 183 |
the checksum calculation. |
| 184 |
|
| 185 |
(1) Deferred Carries |
| 186 |
|
| 187 |
Depending upon the machine, it may be more efficient to defer |
| 188 |
adding end-around carries until the main summation loop is |
| 189 |
finished. |
| 190 |
|
| 191 |
One approach is to sum 16-bit words in a 32-bit accumulator, so |
| 192 |
the overflows build up in the high-order 16 bits. This approach |
| 193 |
typically avoids a carry-sensing instruction but requires twice |
| 194 |
as many additions as would adding 32-bit segments; which is |
| 195 |
faster depends upon the detailed hardware architecture. |
| 196 |
|
| 197 |
(2) Unwinding Loops |
| 198 |
|
| 199 |
To reduce the loop overhead, it is often useful to "unwind" the |
| 200 |
inner sum loop, replicating a series of addition commands within |
| 201 |
one loop traversal. This technique often provides significant |
| 202 |
savings, although it may complicate the logic of the program |
| 203 |
considerably. |
| 204 |
|
| 205 |
(3) Combine with Data Copying |
| 206 |
|
| 207 |
Like checksumming, copying data from one memory location to |
| 208 |
another involves per-byte overhead. In both cases, the |
| 209 |
bottleneck is essentially the memory bus, i.e., how fast the |
| 210 |
data can be fetched. On some machines (especially relatively |
| 211 |
slow and simple micro-computers), overhead can be significantly |
| 212 |
reduced by combining memory-to-memory copy and the checksumming, |
| 213 |
fetching the data only once for both. |
| 214 |
|
| 215 |
(4) Incremental Update |
| 216 |
|
| 217 |
Finally, one can sometimes avoid recomputing the entire checksum |
| 218 |
when one header field is updated. The best-known example is a |
| 219 |
gateway changing the TTL field in the IP header, but there are |
| 220 |
other examples (for example, when updating a source route). In |
| 221 |
these cases it is possible to update the checksum without |
| 222 |
scanning the message or datagram. |
| 223 |
|
| 224 |
To update the checksum, simply add the differences of the |
| 225 |
sixteen bit integers that have been changed. To see why this |
| 226 |
works, observe that every 16-bit integer has an additive inverse |
| 227 |
and that addition is associative. From this it follows that |
| 228 |
given the original value m, the new value m', and the old |
| 229 |
|
| 230 |
|
| 231 |
|
| 232 |
<span class="grey">Braden, Borman, & Partridge [Page 4]</span></pre> |
| 233 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span> |
| 234 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 235 |
|
| 236 |
|
| 237 |
checksum C, the new checksum C' is: |
| 238 |
|
| 239 |
C' = C + (-m) + m' = C + (m' - m) |
| 240 |
|
| 241 |
|
| 242 |
<span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Numerical Examples</span> |
| 243 |
|
| 244 |
We now present explicit examples of calculating a simple 1's |
| 245 |
complement sum on a 2's complement machine. The examples show the |
| 246 |
same sum calculated byte by bye, by 16-bits words in normal and |
| 247 |
swapped order, and 32 bits at a time in 3 different orders. All |
| 248 |
numbers are in hex. |
| 249 |
|
| 250 |
Byte-by-byte "Normal" Swapped |
| 251 |
Order Order |
| 252 |
|
| 253 |
Byte 0/1: 00 01 0001 0100 |
| 254 |
Byte 2/3: f2 03 f203 03f2 |
| 255 |
Byte 4/5: f4 f5 f4f5 f5f4 |
| 256 |
Byte 6/7: f6 f7 f6f7 f7f6 |
| 257 |
--- --- ----- ----- |
| 258 |
Sum1: 2dc 1f0 2ddf0 1f2dc |
| 259 |
|
| 260 |
dc f0 ddf0 f2dc |
| 261 |
Carrys: 1 2 2 1 |
| 262 |
-- -- ---- ---- |
| 263 |
Sum2: dd f2 ddf2 f2dd |
| 264 |
|
| 265 |
Final Swap: dd f2 ddf2 ddf2 |
| 266 |
|
| 267 |
|
| 268 |
Byte 0/1/2/3: 0001f203 010003f2 03f20100 |
| 269 |
Byte 4/5/6/7: f4f5f6f7 f5f4f7f6 f7f6f5f4 |
| 270 |
-------- -------- -------- |
| 271 |
Sum1: 0f4f7e8fa 0f6f4fbe8 0fbe8f6f4 |
| 272 |
|
| 273 |
Carries: 0 0 0 |
| 274 |
|
| 275 |
Top half: f4f7 f6f4 fbe8 |
| 276 |
Bottom half: e8fa fbe8 f6f4 |
| 277 |
----- ----- ----- |
| 278 |
Sum2: 1ddf1 1f2dc 1f2dc |
| 279 |
|
| 280 |
ddf1 f2dc f2dc |
| 281 |
Carrys: 1 1 1 |
| 282 |
---- ---- ---- |
| 283 |
Sum3: ddf2 f2dd f2dd |
| 284 |
|
| 285 |
Final Swap: ddf2 ddf2 ddf2 |
| 286 |
|
| 287 |
|
| 288 |
|
| 289 |
|
| 290 |
|
| 291 |
<span class="grey">Braden, Borman, & Partridge [Page 5]</span></pre> |
| 292 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span> |
| 293 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 294 |
|
| 295 |
|
| 296 |
Finally, here an example of breaking the sum into two groups, with |
| 297 |
the second group starting on a odd boundary: |
| 298 |
|
| 299 |
|
| 300 |
Byte-by-byte Normal |
| 301 |
Order |
| 302 |
|
| 303 |
Byte 0/1: 00 01 0001 |
| 304 |
Byte 2/ : f2 (00) f200 |
| 305 |
--- --- ----- |
| 306 |
Sum1: f2 01 f201 |
| 307 |
|
| 308 |
Byte 4/5: 03 f4 03f4 |
| 309 |
Byte 6/7: f5 f6 f5f6 |
| 310 |
Byte 8/: f7 (00) f700 |
| 311 |
--- --- ----- |
| 312 |
Sum2: 1f0ea |
| 313 |
|
| 314 |
Sum2: f0ea |
| 315 |
Carry: 1 |
| 316 |
----- |
| 317 |
Sum3: f0eb |
| 318 |
|
| 319 |
Sum1: f201 |
| 320 |
Sum3 byte swapped: ebf0 |
| 321 |
----- |
| 322 |
Sum4: 1ddf1 |
| 323 |
|
| 324 |
Sum4: ddf1 |
| 325 |
Carry: 1 |
| 326 |
----- |
| 327 |
Sum5: ddf2 |
| 328 |
|
| 329 |
|
| 330 |
|
| 331 |
|
| 332 |
|
| 333 |
|
| 334 |
|
| 335 |
|
| 336 |
|
| 337 |
|
| 338 |
|
| 339 |
|
| 340 |
|
| 341 |
|
| 342 |
|
| 343 |
|
| 344 |
|
| 345 |
|
| 346 |
|
| 347 |
|
| 348 |
|
| 349 |
|
| 350 |
<span class="grey">Braden, Borman, & Partridge [Page 6]</span></pre> |
| 351 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span> |
| 352 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 353 |
|
| 354 |
|
| 355 |
<span class="h2"><a class="selflink" id="section-4" href="#section-4">4</a>. Implementation Examples</span> |
| 356 |
|
| 357 |
In this section we show examples of Internet checksum implementation |
| 358 |
algorithms that have been found to be efficient on a variety of |
| 359 |
CPU's. In each case, we show the core of the algorithm, without |
| 360 |
including environmental code (e.g., subroutine linkages) or special- |
| 361 |
case code. |
| 362 |
|
| 363 |
<span class="h3"><a class="selflink" id="section-4.1" href="#section-4.1">4.1</a> "C"</span> |
| 364 |
|
| 365 |
The following "C" code algorithm computes the checksum with an inner |
| 366 |
loop that sums 16-bits at a time in a 32-bit accumulator. |
| 367 |
|
| 368 |
in 6 |
| 369 |
{ |
| 370 |
/* Compute Internet Checksum for "count" bytes |
| 371 |
* beginning at location "addr". |
| 372 |
*/ |
| 373 |
register long sum = 0; |
| 374 |
|
| 375 |
while( count > 1 ) { |
| 376 |
/* This is the inner loop */ |
| 377 |
sum += * (unsigned short) addr++; |
| 378 |
count -= 2; |
| 379 |
} |
| 380 |
|
| 381 |
/* Add left-over byte, if any */ |
| 382 |
if( count > 0 ) |
| 383 |
sum += * (unsigned char *) addr; |
| 384 |
|
| 385 |
/* Fold 32-bit sum to 16 bits */ |
| 386 |
while (sum>>16) |
| 387 |
sum = (sum & 0xffff) + (sum >> 16); |
| 388 |
|
| 389 |
checksum = ~sum; |
| 390 |
} |
| 391 |
|
| 392 |
|
| 393 |
|
| 394 |
|
| 395 |
|
| 396 |
|
| 397 |
|
| 398 |
|
| 399 |
|
| 400 |
|
| 401 |
|
| 402 |
|
| 403 |
|
| 404 |
|
| 405 |
|
| 406 |
|
| 407 |
|
| 408 |
|
| 409 |
<span class="grey">Braden, Borman, & Partridge [Page 7]</span></pre> |
| 410 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span> |
| 411 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 412 |
|
| 413 |
|
| 414 |
<span class="h3"><a class="selflink" id="section-4.2" href="#section-4.2">4.2</a> Motorola 68020</span> |
| 415 |
|
| 416 |
The following algorithm is given in assembler language for a Motorola |
| 417 |
68020 chip. This algorithm performs the sum 32 bits at a time, and |
| 418 |
unrolls the loop with 16 replications. For clarity, we have omitted |
| 419 |
the logic to add the last fullword when the length is not a multiple |
| 420 |
of 4. The result is left in register d0. |
| 421 |
|
| 422 |
With a 20MHz clock, this routine was measured at 134 usec/kB summing |
| 423 |
random data. This algorithm was developed by Van Jacobson. |
| 424 |
|
| 425 |
|
| 426 |
movl d1,d2 |
| 427 |
lsrl #6,d1 | count/64 = # loop traversals |
| 428 |
andl #0x3c,d2 | Then find fractions of a chunk |
| 429 |
negl d2 |
| 430 |
andb #0xf,cc | Clear X (extended carry flag) |
| 431 |
|
| 432 |
jmp pc@(2$-.-2:b,d2) | Jump into loop |
| 433 |
|
| 434 |
1$: | Begin inner loop... |
| 435 |
|
| 436 |
movl a0@+,d2 | Fetch 32-bit word |
| 437 |
addxl d2,d0 | Add word + previous carry |
| 438 |
movl a0@+,d2 | Fetch 32-bit word |
| 439 |
addxl d2,d0 | Add word + previous carry |
| 440 |
|
| 441 |
| ... 14 more replications |
| 442 |
2$: |
| 443 |
dbra d1,1$ | (NB- dbra doesn't affect X) |
| 444 |
|
| 445 |
movl d0,d1 | Fold 32 bit sum to 16 bits |
| 446 |
swap d1 | (NB- swap doesn't affect X) |
| 447 |
addxw d1,d0 |
| 448 |
jcc 3$ |
| 449 |
addw #1,d0 |
| 450 |
3$: |
| 451 |
andl #0xffff,d0 |
| 452 |
|
| 453 |
|
| 454 |
|
| 455 |
|
| 456 |
|
| 457 |
|
| 458 |
|
| 459 |
|
| 460 |
|
| 461 |
|
| 462 |
|
| 463 |
|
| 464 |
|
| 465 |
|
| 466 |
|
| 467 |
|
| 468 |
<span class="grey">Braden, Borman, & Partridge [Page 8]</span></pre> |
| 469 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span> |
| 470 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 471 |
|
| 472 |
|
| 473 |
<span class="h3"><a class="selflink" id="section-4.3" href="#section-4.3">4.3</a> Cray</span> |
| 474 |
|
| 475 |
The following example, in assembler language for a Cray CPU, was |
| 476 |
contributed by Charley Kline. It implements the checksum calculation |
| 477 |
as a vector operation, summing up to 512 bytes at a time with a basic |
| 478 |
summation unit of 32 bits. This example omits many details having to |
| 479 |
do with short blocks, for clarity. |
| 480 |
|
| 481 |
Register A1 holds the address of a 512-byte block of memory to |
| 482 |
checksum. First two copies of the data are loaded into two vector |
| 483 |
registers. One is vector-shifted right 32 bits, while the other is |
| 484 |
vector-ANDed with a 32 bit mask. Then the two vectors are added |
| 485 |
together. Since all these operations chain, it produces one result |
| 486 |
per clock cycle. Then it collapses the result vector in a loop that |
| 487 |
adds each element to a scalar register. Finally, the end-around |
| 488 |
carry is performed and the result is folded to 16-bits. |
| 489 |
|
| 490 |
EBM |
| 491 |
A0 A1 |
| 492 |
VL 64 use full vectors |
| 493 |
S1 <32 form 32-bit mask from the right. |
| 494 |
A2 32 |
| 495 |
V1 ,A0,1 load packet into V1 |
| 496 |
V2 S1&V1 Form right-hand 32-bits in V2. |
| 497 |
V3 V1>A2 Form left-hand 32-bits in V3. |
| 498 |
V1 V2+V3 Add the two together. |
| 499 |
A2 63 Prepare to collapse into a scalar. |
| 500 |
S1 0 |
| 501 |
S4 <16 Form 16-bit mask from the right. |
| 502 |
A4 16 |
| 503 |
CK$LOOP S2 V1,A2 |
| 504 |
A2 A2-1 |
| 505 |
A0 A2 |
| 506 |
S1 S1+S2 |
| 507 |
JAN CK$LOOP |
| 508 |
S2 S1&S4 Form right-hand 16-bits in S2 |
| 509 |
S1 S1>A4 Form left-hand 16-bits in S1 |
| 510 |
S1 S1+S2 |
| 511 |
S2 S1&S4 Form right-hand 16-bits in S2 |
| 512 |
S1 S1>A4 Form left-hand 16-bits in S1 |
| 513 |
S1 S1+S2 |
| 514 |
S1 #S1 Take one's complement |
| 515 |
CMR At this point, S1 contains the checksum. |
| 516 |
|
| 517 |
|
| 518 |
|
| 519 |
|
| 520 |
|
| 521 |
|
| 522 |
|
| 523 |
|
| 524 |
|
| 525 |
|
| 526 |
|
| 527 |
<span class="grey">Braden, Borman, & Partridge [Page 9]</span></pre> |
| 528 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span> |
| 529 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 530 |
|
| 531 |
|
| 532 |
<span class="h3"><a class="selflink" id="section-4.4" href="#section-4.4">4.4</a> IBM 370</span> |
| 533 |
|
| 534 |
The following example, in assembler language for an IBM 370 CPU, sums |
| 535 |
the data 4 bytes at a time. For clarity, we have omitted the logic |
| 536 |
to add the last fullword when the length is not a multiple of 4, and |
| 537 |
to reverse the bytes when necessary. The result is left in register |
| 538 |
RCARRY. |
| 539 |
|
| 540 |
This code has been timed on an IBM 3090 CPU at 27 usec/KB when |
| 541 |
summing all one bits. This time is reduced to 24.3 usec/KB if the |
| 542 |
trouble is taken to word-align the addends (requiring special cases |
| 543 |
at both the beginning and the end, and byte-swapping when necessary |
| 544 |
to compensate for starting on an odd byte). |
| 545 |
|
| 546 |
* Registers RADDR and RCOUNT contain the address and length of |
| 547 |
* the block to be checksummed. |
| 548 |
* |
| 549 |
* (RCARRY, RSUM) must be an even/odd register pair. |
| 550 |
* (RCOUNT, RMOD) must be an even/odd register pair. |
| 551 |
* |
| 552 |
CHECKSUM SR RSUM,RSUM Clear working registers. |
| 553 |
SR RCARRY,RCARRY |
| 554 |
LA RONE,1 Set up constant 1. |
| 555 |
* |
| 556 |
SRDA RCOUNT,6 Count/64 to RCOUNT. |
| 557 |
AR RCOUNT,RONE +1 = # times in loop. |
| 558 |
SRL RMOD,26 Size of partial chunk to RMOD. |
| 559 |
AR RADDR,R3 Adjust addr to compensate for |
| 560 |
S RADDR,=F(64) jumping into the loop. |
| 561 |
SRL RMOD,1 (RMOD/4)*2 is halfword index. |
| 562 |
LH RMOD,DOPEVEC9(RMOD) Use magic dope-vector for offset, |
| 563 |
B LOOP(RMOD) and jump into the loop... |
| 564 |
* |
| 565 |
* Inner loop: |
| 566 |
* |
| 567 |
LOOP AL RSUM,0(,RADDR) Add Logical fullword |
| 568 |
BC 12,*+6 Branch if no carry |
| 569 |
AR RCARRY,RONE Add 1 end-around |
| 570 |
AL RSUM,4(,RADDR) Add Logical fullword |
| 571 |
BC 12,*+6 Branch if no carry |
| 572 |
AR RCARRY,RONE Add 1 end-around |
| 573 |
* |
| 574 |
* ... 14 more replications ... |
| 575 |
* |
| 576 |
A RADDR,=F'64' Increment address ptr |
| 577 |
BCT RCOUNT,LOOP Branch on Count |
| 578 |
* |
| 579 |
* Add Carries into sum, and fold to 16 bits |
| 580 |
* |
| 581 |
ALR RCARRY,RSUM Add SUM and CARRY words |
| 582 |
BC 12,*+6 and take care of carry |
| 583 |
|
| 584 |
|
| 585 |
|
| 586 |
<span class="grey">Braden, Borman, & Partridge [Page 10]</span></pre> |
| 587 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span> |
| 588 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 589 |
|
| 590 |
|
| 591 |
AR RCARRY,RONE |
| 592 |
SRDL RCARRY,16 Fold 32-bit sum into |
| 593 |
SRL RSUM,16 16-bits |
| 594 |
ALR RCARRY,RSUM |
| 595 |
C RCARRY,=X'0000FFFF' and take care of any |
| 596 |
BNH DONE last carry |
| 597 |
S RCARRY,=X'0000FFFF' |
| 598 |
DONE X RCARRY,=X'0000FFFF' 1's complement |
| 599 |
|
| 600 |
|
| 601 |
|
| 602 |
|
| 603 |
|
| 604 |
|
| 605 |
|
| 606 |
|
| 607 |
|
| 608 |
|
| 609 |
|
| 610 |
|
| 611 |
|
| 612 |
|
| 613 |
|
| 614 |
|
| 615 |
|
| 616 |
|
| 617 |
|
| 618 |
|
| 619 |
|
| 620 |
|
| 621 |
|
| 622 |
|
| 623 |
|
| 624 |
|
| 625 |
|
| 626 |
|
| 627 |
|
| 628 |
|
| 629 |
|
| 630 |
|
| 631 |
|
| 632 |
|
| 633 |
|
| 634 |
|
| 635 |
|
| 636 |
|
| 637 |
|
| 638 |
|
| 639 |
|
| 640 |
|
| 641 |
|
| 642 |
|
| 643 |
|
| 644 |
|
| 645 |
<span class="grey">Braden, Borman, & Partridge [Page 11]</span></pre> |
| 646 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-12" ></span> |
| 647 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 648 |
|
| 649 |
|
| 650 |
IEN 45 |
| 651 |
<a href="#section-2.4.4.5">Section 2.4.4.5</a> |
| 652 |
|
| 653 |
|
| 654 |
|
| 655 |
|
| 656 |
|
| 657 |
|
| 658 |
|
| 659 |
|
| 660 |
|
| 661 |
|
| 662 |
|
| 663 |
|
| 664 |
|
| 665 |
|
| 666 |
|
| 667 |
|
| 668 |
TCP Checksum Function Design |
| 669 |
|
| 670 |
|
| 671 |
|
| 672 |
William W. Plummer |
| 673 |
|
| 674 |
|
| 675 |
Bolt Beranek and Newman, Inc. |
| 676 |
50 Moulton Street |
| 677 |
Cambridge MA 02138 |
| 678 |
|
| 679 |
|
| 680 |
5 June 1978 |
| 681 |
|
| 682 |
|
| 683 |
|
| 684 |
|
| 685 |
|
| 686 |
|
| 687 |
|
| 688 |
|
| 689 |
|
| 690 |
|
| 691 |
|
| 692 |
|
| 693 |
|
| 694 |
|
| 695 |
|
| 696 |
|
| 697 |
|
| 698 |
|
| 699 |
|
| 700 |
|
| 701 |
|
| 702 |
|
| 703 |
|
| 704 |
<span class="grey">Braden, Borman, & Partridge [Page 12]</span></pre> |
| 705 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-13" ></span> |
| 706 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 707 |
|
| 708 |
|
| 709 |
Internet Experiment Note 45 5 June 1978 |
| 710 |
TCP Checksum Function Design William W. Plummer |
| 711 |
|
| 712 |
1. Introduction |
| 713 |
|
| 714 |
Checksums are included in packets in order that errors |
| 715 |
encountered during transmission may be detected. For Internet |
| 716 |
protocols such as TCP [<a href="#ref-1" title=""A Protocol for Packet Network Communications,"">1</a>,<a href="#ref-9" title=""Specification of Internetwork Transmission Control Program Version 3"">9</a>] this is especially important because |
| 717 |
packets may have to cross wireless networks such as the Packet |
| 718 |
Radio Network [<a href="#ref-2" title=""The Organization of Computer Resources into a Packet Radio Network"">2</a>] and Atlantic Satellite Network [<a href="#ref-3" title=""CPODA - A Demand Assignment Protocol for SatNet"">3</a>] where |
| 719 |
packets may be corrupted. Internet protocols (e.g., those for |
| 720 |
real time speech transmission) can tolerate a certain level of |
| 721 |
transmission errors and forward error correction techniques or |
| 722 |
possibly no checksum at all might be better. The focus in this |
| 723 |
paper is on checksum functions for protocols such as TCP where |
| 724 |
the required reliable delivery is achieved by retransmission. |
| 725 |
|
| 726 |
Even if the checksum appears good on a message which has been |
| 727 |
received, the message may still contain an undetected error. The |
| 728 |
probability of this is bounded by 2**(-C) where C is the number |
| 729 |
of checksum bits. Errors can arise from hardware (and software) |
| 730 |
malfunctions as well as transmission errors. Hardware induced |
| 731 |
errors are usually manifested in certain well known ways and it |
| 732 |
is desirable to account for this in the design of the checksum |
| 733 |
function. Ideally no error of the "common hardware failure" type |
| 734 |
would go undetected. |
| 735 |
|
| 736 |
An example of a failure that the current checksum function |
| 737 |
handles successfully is picking up a bit in the network interface |
| 738 |
(or I/O buss, memory channel, etc.). This will always render the |
| 739 |
checksum bad. For an example of how the current function is |
| 740 |
inadequate, assume that a control signal stops functioning in the |
| 741 |
network interface and the interface stores zeros in place of the |
| 742 |
real data. These "all zero" messages appear to have valid |
| 743 |
checksums. Noise on the "There's Your Bit" line of the ARPANET |
| 744 |
Interface [<a href="#ref-4" title=""Specifications for the Interconnection of a Host and an IMP"">4</a>] may go undetected because the extra bits input may |
| 745 |
cause the checksum to be perturbed (i.e., shifted) in the same |
| 746 |
way as the data was. |
| 747 |
|
| 748 |
Although messages containing undetected errors will occasionally |
| 749 |
be passed to higher levels of protocol, it is likely that they |
| 750 |
will not make sense at that level. In the case of TCP most such |
| 751 |
messages will be ignored, but some could cause a connection to be |
| 752 |
aborted. Garbled data could be viewed as a problem for a layer |
| 753 |
of protocol above TCP which itself may have a checksuming scheme. |
| 754 |
|
| 755 |
This paper is the first step in design of a new checksum function |
| 756 |
for TCP and some other Internet protocols. Several useful |
| 757 |
properties of the current function are identified. If possible |
| 758 |
|
| 759 |
- 1 - |
| 760 |
|
| 761 |
|
| 762 |
|
| 763 |
<span class="grey">Braden, Borman, & Partridge [Page 13]</span></pre> |
| 764 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-14" ></span> |
| 765 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 766 |
|
| 767 |
|
| 768 |
Internet Experiment Note 45 5 June 1978 |
| 769 |
TCP Checksum Function Design William W. Plummer |
| 770 |
|
| 771 |
these should be retained in any new function. A number of |
| 772 |
plausible checksum schemes are investigated. Of these only the |
| 773 |
"product code" seems to be simple enough for consideration. |
| 774 |
|
| 775 |
2. The Current TCP Checksum Function |
| 776 |
|
| 777 |
The current function is oriented towards sixteen-bit machines |
| 778 |
such as the PDP-11 but can be computed easily on other machines |
| 779 |
(e.g., PDP-10). A packet is thought of as a string of 16-bit |
| 780 |
bytes and the checksum function is the one's complement sum (add |
| 781 |
with end-around carry) of those bytes. It is the one's |
| 782 |
complement of this sum which is stored in the checksum field of |
| 783 |
the TCP header. Before computing the checksum value, the sender |
| 784 |
places a zero in the checksum field of the packet. If the |
| 785 |
checksum value computed by a receiver of the packet is zero, the |
| 786 |
packet is assumed to be valid. This is a consequence of the |
| 787 |
"negative" number in the checksum field exactly cancelling the |
| 788 |
contribution of the rest of the packet. |
| 789 |
|
| 790 |
Ignoring the difficulty of actually evaluating the checksum |
| 791 |
function for a given packet, the way of using the checksum |
| 792 |
described above is quite simple, but it assumes some properties |
| 793 |
of the checksum operator (one's complement addition, "+" in what |
| 794 |
follows): |
| 795 |
|
| 796 |
(P1) + is commutative. Thus, the order in which |
| 797 |
the 16-bit bytes are "added" together is |
| 798 |
unimportant. |
| 799 |
|
| 800 |
(P2) + has at least one identity element (The |
| 801 |
current function has two: +0 and -0). This |
| 802 |
allows the sender to compute the checksum |
| 803 |
function by placing a zero in the packet checksum |
| 804 |
field before computing the value. |
| 805 |
|
| 806 |
(P3) + has an inverse. Thus, the receiver may |
| 807 |
evaluate the checksum function and expect a zero. |
| 808 |
|
| 809 |
(P4) + is associative, allowing the checksum field |
| 810 |
to be anywhere in the packet and the 16-bit bytes |
| 811 |
to be scanned sequentially. |
| 812 |
|
| 813 |
Mathematically, these properties of the binary operation "+" over |
| 814 |
the set of 16-bit numbers forms an Abelian group [<a href="#ref-5" title=""Elements of Abstract Algebra"">5</a>]. Of course, |
| 815 |
there are many Abelian groups but not all would be satisfactory |
| 816 |
for use as checksum operators. (Another operator readily |
| 817 |
|
| 818 |
- 2 - |
| 819 |
|
| 820 |
|
| 821 |
|
| 822 |
<span class="grey">Braden, Borman, & Partridge [Page 14]</span></pre> |
| 823 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-15" ></span> |
| 824 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 825 |
|
| 826 |
|
| 827 |
Internet Experiment Note 45 5 June 1978 |
| 828 |
TCP Checksum Function Design William W. Plummer |
| 829 |
|
| 830 |
available in the PDP-11 instruction set that has all of these |
| 831 |
properties is exclusive-OR, but XOR is unsatisfactory for other |
| 832 |
reasons.) |
| 833 |
|
| 834 |
Albeit imprecise, another property which must be preserved in any |
| 835 |
future checksum scheme is: |
| 836 |
|
| 837 |
(P5) + is fast to compute on a variety of machines |
| 838 |
with limited storage requirements. |
| 839 |
|
| 840 |
The current function is quite good in this respect. On the |
| 841 |
PDP-11 the inner loop looks like: |
| 842 |
|
| 843 |
LOOP: ADD (R1)+,R0 ; Add the next 16-bit byte |
| 844 |
ADC R0 ; Make carry be end-around |
| 845 |
SOB R2,LOOP ; Loop over entire packet. |
| 846 |
|
| 847 |
( 4 memory cycles per 16-bit byte ) |
| 848 |
|
| 849 |
On the PDP-10 properties P1-4 are exploited further and two |
| 850 |
16-bit bytes per loop are processed: |
| 851 |
|
| 852 |
LOOP: ILDB THIS,PTR ; Get 2 16-bit bytes |
| 853 |
ADD SUM,THIS ; Add into current sum |
| 854 |
JUMPGE SUM,CHKSU2 ; Jump if fewer than 8 carries |
| 855 |
LDB THIS,[POINT 20,SUM,19] ; Get left 16 and carries |
| 856 |
ANDI SUM,177777 ; Save just low 16 here |
| 857 |
ADD SUM,THIS ; Fold in carries |
| 858 |
CHKSU2: SOJG COUNT,LOOP ; Loop over entire packet |
| 859 |
|
| 860 |
( 3.1 memory cycles per 16-bit byte ) |
| 861 |
|
| 862 |
The "extra" instruction in the loops above are required to |
| 863 |
convert the two's complement ADD instruction(s) into a one's |
| 864 |
complement add by making the carries be end-around. One's |
| 865 |
complement arithmetic is better than two's complement because it |
| 866 |
is equally sensitive to errors in all bit positions. If two's |
| 867 |
complement addition were used, an even number of 1's could be |
| 868 |
dropped (or picked up) in the most significant bit channel |
| 869 |
without affecting the value of the checksum. It is just this |
| 870 |
property that makes some sort of addition preferable to a simple |
| 871 |
exclusive-OR which is frequently used but permits an even number |
| 872 |
of drops (pick ups) in any bit channel. RIM10B paper tape format |
| 873 |
used on PDP-10s [<a href="#ref-10" title=""PDP-10 Reference Handbook"">10</a>] uses two's complement add because space for |
| 874 |
the loader program is extremely limited. |
| 875 |
|
| 876 |
- 3 - |
| 877 |
|
| 878 |
|
| 879 |
|
| 880 |
|
| 881 |
<span class="grey">Braden, Borman, & Partridge [Page 15]</span></pre> |
| 882 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-16" ></span> |
| 883 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 884 |
|
| 885 |
|
| 886 |
Internet Experiment Note 45 5 June 1978 |
| 887 |
TCP Checksum Function Design William W. Plummer |
| 888 |
|
| 889 |
Another property of the current checksum scheme is: |
| 890 |
|
| 891 |
(P6) Adding the checksum to a packet does not change |
| 892 |
the information bytes. Peterson [<a href="#ref-6" title=""Error Correcting Codes"">6</a>] calls this a |
| 893 |
"systematic" code. |
| 894 |
|
| 895 |
This property allows intermediate computers such as gateway |
| 896 |
machines to act on fields (i.e., the Internet Destination |
| 897 |
Address) without having to first decode the packet. Cyclical |
| 898 |
Redundancy Checks used for error correction are not systematic |
| 899 |
either. However, most applications of CRCs tend to emphasize |
| 900 |
error detection rather than correction and consequently can send |
| 901 |
the message unchanged, with the CRC check bits being appended to |
| 902 |
the end. The 24-bit CRC used by ARPANET IMPs and Very Distant |
| 903 |
Host Interfaces [<a href="#ref-4" title=""Specifications for the Interconnection of a Host and an IMP"">4</a>] and the ANSI standards for 800 and 6250 bits |
| 904 |
per inch magnetic tapes (described in [<a href="#ref-11" title=""Understanding Cyclic Redundancy Codes"">11</a>]) use this mode. |
| 905 |
|
| 906 |
Note that the operation of higher level protocols are not (by |
| 907 |
design) affected by anything that may be done by a gateway acting |
| 908 |
on possibly invalid packets. It is permissible for gateways to |
| 909 |
validate the checksum on incoming packets, but in general |
| 910 |
gateways will not know how to do this if the checksum is a |
| 911 |
protocol-specific feature. |
| 912 |
|
| 913 |
A final property of the current checksum scheme which is actually |
| 914 |
a consequence of P1 and P4 is: |
| 915 |
|
| 916 |
(P7) The checksum may be incrementally modified. |
| 917 |
|
| 918 |
This property permits an intermediate gateway to add information |
| 919 |
to a packet, for instance a timestamp, and "add" an appropriate |
| 920 |
change to the checksum field of the packet. Note that the |
| 921 |
checksum will still be end-to-end since it was not fully |
| 922 |
recomputed. |
| 923 |
|
| 924 |
3. Product Codes |
| 925 |
|
| 926 |
Certain "product codes" are potentially useful for checksuming |
| 927 |
purposes. The following is a brief description of product codes |
| 928 |
in the context of TCP. More general treatment can be found in |
| 929 |
Avizienis [<a href="#ref-7" title=""A Study of the Effectiveness of Fault- Detecting Codes for Binary Arithmetic"">7</a>] and probably other more recent works. |
| 930 |
|
| 931 |
The basic concept of this coding is that the message (packet) to |
| 932 |
be sent is formed by transforming the original source message and |
| 933 |
adding some "check" bits. By reading this and applying a |
| 934 |
(possibly different) transformation, a receiver can reconstruct |
| 935 |
|
| 936 |
- 4 - |
| 937 |
|
| 938 |
|
| 939 |
|
| 940 |
<span class="grey">Braden, Borman, & Partridge [Page 16]</span></pre> |
| 941 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-17" ></span> |
| 942 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 943 |
|
| 944 |
|
| 945 |
Internet Experiment Note 45 5 June 1978 |
| 946 |
TCP Checksum Function Design William W. Plummer |
| 947 |
|
| 948 |
the original message and determine if it has been corrupted |
| 949 |
during transmission. |
| 950 |
|
| 951 |
Mo Ms Mr |
| 952 |
|
| 953 |
----- ----- ----- |
| 954 |
| A | code | 7 | decode | A | |
| 955 |
| B | ==> | 1 | ==> | B | |
| 956 |
| C | | 4 | | C | |
| 957 |
----- |...| ----- |
| 958 |
| 2 | check plus "valid" flag |
| 959 |
----- info |
| 960 |
|
| 961 |
Original Sent Reconstructed |
| 962 |
|
| 963 |
With product codes the transformation is Ms = K * Mo . That is, |
| 964 |
the message sent is simply the product of the original message |
| 965 |
Mo and some well known constant K . To decode, the received |
| 966 |
Ms is divided by K which will yield Mr as the quotient and |
| 967 |
0 as the remainder if Mr is to be considered the same as Mo . |
| 968 |
|
| 969 |
The first problem is selecting a "good" value for K, the "check |
| 970 |
factor". K must be relatively prime to the base chosen to |
| 971 |
express the message. (Example: Binary messages with K |
| 972 |
incorrectly chosen to be 8. This means that Ms looks exactly |
| 973 |
like Mo except that three zeros have been appended. The only |
| 974 |
way the message could look bad to a receiver dividing by 8 is if |
| 975 |
the error occurred in one of those three bits.) |
| 976 |
|
| 977 |
For TCP the base R will be chosen to be 2**16. That is, every |
| 978 |
16-bit byte (word on the PDP-11) will be considered as a digit of |
| 979 |
a big number and that number is the message. Thus, |
| 980 |
|
| 981 |
Mo = SIGMA [ Bi * (R**i)] , Bi is i-th byte |
| 982 |
i=0 to N |
| 983 |
|
| 984 |
Ms = K * Mo |
| 985 |
|
| 986 |
Corrupting a single digit of Ms will yield Ms' = Ms +or- |
| 987 |
C*(R**j) for some radix position j . The receiver will compute |
| 988 |
Ms'/K = Mo +or- C(R**j)/K. Since R and K are relatively prime, |
| 989 |
C*(R**j) cannot be any exact multiple of K. Therefore, the |
| 990 |
division will result in a non-zero remainder which indicates that |
| 991 |
Ms' is a corrupted version of Ms. As will be seen, a good |
| 992 |
choice for K is (R**b - 1), for some b which is the "check |
| 993 |
length" which controls the degree of detection to be had for |
| 994 |
|
| 995 |
- 5 - |
| 996 |
|
| 997 |
|
| 998 |
|
| 999 |
<span class="grey">Braden, Borman, & Partridge [Page 17]</span></pre> |
| 1000 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-18" ></span> |
| 1001 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1002 |
|
| 1003 |
|
| 1004 |
Internet Experiment Note 45 5 June 1978 |
| 1005 |
TCP Checksum Function Design William W. Plummer |
| 1006 |
|
| 1007 |
burst errors which affect a string of digits (i.e., 16-bit bytes) |
| 1008 |
in the message. In fact b will be chosen to be 1, so K will |
| 1009 |
be 2**16 - 1 so that arithmetic operations will be simple. This |
| 1010 |
means that all bursts of 15 or fewer bits will be detected. |
| 1011 |
According to [<a href="#ref-7" title=""A Study of the Effectiveness of Fault- Detecting Codes for Binary Arithmetic"">7</a>] this choice for b results in the following |
| 1012 |
expression for the fraction of undetected weight 2 errors: |
| 1013 |
|
| 1014 |
f = 16(k-1)/[32(16k-3) + (6/k)] where k is the message length. |
| 1015 |
|
| 1016 |
For large messages f approaches 3.125 per cent as k goes to |
| 1017 |
infinity. |
| 1018 |
|
| 1019 |
Multiple precision multiplication and division are normally quite |
| 1020 |
complex operations, especially on small machines which typically |
| 1021 |
lack even single precision multiply and divide operations. The |
| 1022 |
exception to this is exactly the case being dealt with here -- |
| 1023 |
the factor is 2**16 - 1 on machines with a word length of 16 |
| 1024 |
bits. The reason for this is due to the following identity: |
| 1025 |
|
| 1026 |
Q*(R**j) = Q, mod (R-1) 0 <= Q < R |
| 1027 |
|
| 1028 |
That is, any digit Q in the selected radix (0, 1, ... R-1) |
| 1029 |
multiplied by any power of the radix will have a remainder of Q |
| 1030 |
when divided by the radix minus 1. |
| 1031 |
|
| 1032 |
Example: In decimal R = 10. Pick Q = 6. |
| 1033 |
|
| 1034 |
6 = 0 * 9 + 6 = 6, mod 9 |
| 1035 |
60 = 6 * 9 + 6 = 6, mod 9 |
| 1036 |
600 = 66 * 9 + 6 = 6, mod 9 etc. |
| 1037 |
|
| 1038 |
More to the point, rem(31415/9) = rem((30000+1000+400+10+5)/9) |
| 1039 |
= (3 mod 9) + (1 mod 9) + (4 mod 9) + (1 mod 9) + (5 mod 9) |
| 1040 |
= (3+1+4+1+5) mod 9 |
| 1041 |
= 14 mod 9 |
| 1042 |
= 5 |
| 1043 |
|
| 1044 |
So, the remainder of a number divided by the radix minus one can |
| 1045 |
be found by simply summing the digits of the number. Since the |
| 1046 |
radix in the TCP case has been chosen to be 2**16 and the check |
| 1047 |
factor is 2**16 - 1, a message can quickly be checked by summing |
| 1048 |
all of the 16-bit words (on a PDP-11), with carries being |
| 1049 |
end-around. If zero is the result, the message can be considered |
| 1050 |
valid. Thus, checking a product coded message is exactly the |
| 1051 |
same complexity as with the current TCP checksum! |
| 1052 |
|
| 1053 |
- 6 - |
| 1054 |
|
| 1055 |
|
| 1056 |
|
| 1057 |
|
| 1058 |
<span class="grey">Braden, Borman, & Partridge [Page 18]</span></pre> |
| 1059 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-19" ></span> |
| 1060 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1061 |
|
| 1062 |
|
| 1063 |
Internet Experiment Note 45 5 June 1978 |
| 1064 |
TCP Checksum Function Design William W. Plummer |
| 1065 |
|
| 1066 |
In order to form Ms, the sender must multiply the multiple |
| 1067 |
precision "number" Mo by 2**16 - 1. Or, Ms = (2**16)Mo - Mo. |
| 1068 |
This is performed by shifting Mo one whole word's worth of |
| 1069 |
precision and subtracting Mo. Since carries must propagate |
| 1070 |
between digits, but it is only the current digit which is of |
| 1071 |
interest, one's complement arithmetic is used. |
| 1072 |
|
| 1073 |
(2**16)Mo = Mo0 + Mo1 + Mo2 + ... + MoX + 0 |
| 1074 |
- Mo = - ( Mo0 + Mo1 + ......... + MoX) |
| 1075 |
--------- ---------------------------------- |
| 1076 |
Ms = Ms0 + Ms1 + ... - MoX |
| 1077 |
|
| 1078 |
A loop which implements this function on a PDP-11 might look |
| 1079 |
like: |
| 1080 |
LOOP: MOV -2(R2),R0 ; Next byte of (2**16)Mo |
| 1081 |
SBC R0 ; Propagate carries from last SUB |
| 1082 |
SUB (R2)+,R0 ; Subtract byte of Mo |
| 1083 |
MOV R0,(R3)+ ; Store in Ms |
| 1084 |
SOB R1,LOOP ; Loop over entire message |
| 1085 |
; 8 memory cycles per 16-bit byte |
| 1086 |
|
| 1087 |
Note that the coding procedure is not done in-place since it is |
| 1088 |
not systematic. In general the original copy, Mo, will have to |
| 1089 |
be retained by the sender for retransmission purposes and |
| 1090 |
therefore must remain readable. Thus the MOV R0,(R3)+ is |
| 1091 |
required which accounts for 2 of the 8 memory cycles per loop. |
| 1092 |
|
| 1093 |
The coding procedure will add exactly one 16-bit word to the |
| 1094 |
message since Ms < (2**16)Mo . This additional 16 bits will be |
| 1095 |
at the tail of the message, but may be moved into the defined |
| 1096 |
location in the TCP header immediately before transmission. The |
| 1097 |
receiver will have to undo this to put Ms back into standard |
| 1098 |
format before decoding the message. |
| 1099 |
|
| 1100 |
The code in the receiver for fully decoding the message may be |
| 1101 |
inferred by observing that any word in Ms contains the |
| 1102 |
difference between two successive words of Mo minus the carries |
| 1103 |
from the previous word, and the low order word contains minus the |
| 1104 |
low word of Mo. So the low order (i.e., rightmost) word of Mr is |
| 1105 |
just the negative of the low order byte of Ms. The next word of |
| 1106 |
Mr is the next word of Ms plus the just computed word of Mr |
| 1107 |
plus the carry from that previous computation. |
| 1108 |
|
| 1109 |
A slight refinement of the procedure is required in order to |
| 1110 |
protect against an all-zero message passing to the destination. |
| 1111 |
This will appear to have a valid checksum because Ms'/K = 0/K |
| 1112 |
|
| 1113 |
- 7 - |
| 1114 |
|
| 1115 |
|
| 1116 |
|
| 1117 |
<span class="grey">Braden, Borman, & Partridge [Page 19]</span></pre> |
| 1118 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-20" ></span> |
| 1119 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1120 |
|
| 1121 |
|
| 1122 |
Internet Experiment Note 45 5 June 1978 |
| 1123 |
TCP Checksum Function Design William W. Plummer |
| 1124 |
|
| 1125 |
= 0 with 0 remainder. The refinement is to make the coding be |
| 1126 |
Ms = K*Mo + C where C is some arbitrary, well-known constant. |
| 1127 |
Adding this constant requires a second pass over the message, but |
| 1128 |
this will typically be very short since it can stop as soon as |
| 1129 |
carries stop propagating. Chosing C = 1 is sufficient in most |
| 1130 |
cases. |
| 1131 |
|
| 1132 |
The product code checksum must be evaluated in terms of the |
| 1133 |
desired properties P1 - P7. It has been shown that a factor of |
| 1134 |
two more machine cycles are consumed in computing or verifying a |
| 1135 |
product code checksum (P5 satisfied?). |
| 1136 |
|
| 1137 |
Although the code is not systematic, the checksum can be verified |
| 1138 |
quickly without decoding the message. If the Internet |
| 1139 |
Destination Address is located at the least significant end of |
| 1140 |
the packet (where the product code computation begins) then it is |
| 1141 |
possible for a gateway to decode only enough of the message to |
| 1142 |
see this field without having to decode the entire message. |
| 1143 |
Thus, P6 is at least partially satisfied. The algebraic |
| 1144 |
properties P1 through P4 are not satisfied, but only a small |
| 1145 |
amount of computation is needed to account for this -- the |
| 1146 |
message needs to be reformatted as previously mentioned. |
| 1147 |
|
| 1148 |
P7 is satisfied since the product code checksum can be |
| 1149 |
incrementally updated to account for an added word, although the |
| 1150 |
procedure is somewhat involved. Imagine that the original |
| 1151 |
message has two halves, H1 and H2. Thus, Mo = H1*(R**j) + H2. |
| 1152 |
The timestamp word is to be inserted between these halves to form |
| 1153 |
a modified Mo' = H1*(R**(j+1)) + T*(R**j) + H2. Since K has |
| 1154 |
been chosen to be R-1, the transmitted message Ms' = Mo'(R-1). |
| 1155 |
Then, |
| 1156 |
|
| 1157 |
Ms' = Ms*R + T(R-1)(R**j) + P2((R-1)**2) |
| 1158 |
|
| 1159 |
= Ms*R + T*(R**(j+1)) + T*(R**j) + P2*(R**2) - 2*P2*R - P2 |
| 1160 |
|
| 1161 |
Recalling that R is 2**16, the word size on the PDP-11, |
| 1162 |
multiplying by R means copying down one word in memory. So, |
| 1163 |
the first term of Ms' is simply the unmodified message copied |
| 1164 |
down one word. The next term is the new data T added into the |
| 1165 |
Ms' being formed beginning at the (j+1)th word. The addition is |
| 1166 |
fairly easy here since after adding in T all that is left is |
| 1167 |
propagating the carry, and that can stop as soon as no carry is |
| 1168 |
produced. The other terms can be handle similarly. |
| 1169 |
|
| 1170 |
- 8 - |
| 1171 |
|
| 1172 |
|
| 1173 |
|
| 1174 |
|
| 1175 |
|
| 1176 |
<span class="grey">Braden, Borman, & Partridge [Page 20]</span></pre> |
| 1177 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-21" ></span> |
| 1178 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1179 |
|
| 1180 |
|
| 1181 |
Internet Experiment Note 45 5 June 1978 |
| 1182 |
TCP Checksum Function Design William W. Plummer |
| 1183 |
|
| 1184 |
4. More Complicated Codes |
| 1185 |
|
| 1186 |
There exists a wealth of theory on error detecting and correcting |
| 1187 |
codes. Peterson [<a href="#ref-6" title=""Error Correcting Codes"">6</a>] is an excellent reference. Most of these |
| 1188 |
"CRC" schemes are designed to be implemented using a shift |
| 1189 |
register with a feedback network composed of exclusive-ORs. |
| 1190 |
Simulating such a logic circuit with a program would be too slow |
| 1191 |
to be useful unless some programming trick is discovered. |
| 1192 |
|
| 1193 |
One such trick has been proposed by Kirstein [<a href="#ref-8" title="Peter">8</a>]. Basically, a |
| 1194 |
few bits (four or eight) of the current shift register state are |
| 1195 |
combined with bits from the input stream (from Mo) and the result |
| 1196 |
is used as an index to a table which yields the new shift |
| 1197 |
register state and, if the code is not systematic, bits for the |
| 1198 |
output stream (Ms). A trial coding of an especially "good" CRC |
| 1199 |
function using four-bit bytes showed showed this technique to be |
| 1200 |
about four times as slow as the current checksum function. This |
| 1201 |
was true for both the PDP-10 and PDP-11 machines. Of the |
| 1202 |
desirable properties listed above, CRC schemes satisfy only P3 |
| 1203 |
(It has an inverse.), and P6 (It is systematic.). Placement of |
| 1204 |
the checksum field in the packet is critical and the CRC cannot |
| 1205 |
be incrementally modified. |
| 1206 |
|
| 1207 |
Although the bulk of coding theory deals with binary codes, most |
| 1208 |
of the theory works if the alphabet contains q symbols, where |
| 1209 |
q is a power of a prime number. For instance q taken as 2**16 |
| 1210 |
should make a great deal of the theory useful on a word-by-word |
| 1211 |
basis. |
| 1212 |
|
| 1213 |
5. Outboard Processing |
| 1214 |
|
| 1215 |
When a function such as computing an involved checksum requires |
| 1216 |
extensive processing, one solution is to put that processing into |
| 1217 |
an outboard processor. In this way "encode message" and "decode |
| 1218 |
message" become single instructions which do not tax the main |
| 1219 |
host processor. The Digital Equipment Corporation VAX/780 |
| 1220 |
computer is equipped with special hardware for generating and |
| 1221 |
checking CRCs [<a href="#ref-13" title=""Advanced Minicomputer Designed by Team Evaluation of Hardware/Software Tradeoffs"">13</a>]. In general this is not a very good solution |
| 1222 |
since such a processor must be constructed for every different |
| 1223 |
host machine which uses TCP messages. |
| 1224 |
|
| 1225 |
It is conceivable that the gateway functions for a large host may |
| 1226 |
be performed entirely in an "Internet Frontend Machine". This |
| 1227 |
machine would be responsible for forwarding packets received |
| 1228 |
|
| 1229 |
- 9 - |
| 1230 |
|
| 1231 |
|
| 1232 |
|
| 1233 |
|
| 1234 |
|
| 1235 |
<span class="grey">Braden, Borman, & Partridge [Page 21]</span></pre> |
| 1236 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-22" ></span> |
| 1237 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1238 |
|
| 1239 |
|
| 1240 |
Internet Experiment Note 45 5 June 1978 |
| 1241 |
TCP Checksum Function Design William W. Plummer |
| 1242 |
|
| 1243 |
either from the network(s) or from the Internet protocol modules |
| 1244 |
in the connected host, and for reassembling Internet fragments |
| 1245 |
into segments and passing these to the host. Another capability |
| 1246 |
of this machine would be to check the checksum so that the |
| 1247 |
segments given to the host are known to be valid at the time they |
| 1248 |
leave the frontend. Since computer cycles are assumed to be both |
| 1249 |
inexpensive and available in the frontend, this seems reasonable. |
| 1250 |
|
| 1251 |
The problem with attempting to validate checksums in the frontend |
| 1252 |
is that it destroys the end-to-end character of the checksum. If |
| 1253 |
anything, this is the most powerful feature of the TCP checksum! |
| 1254 |
There is a way to make the host-to-frontend link be covered by |
| 1255 |
the end-to-end checksum. A separate, small protocol must be |
| 1256 |
developed to cover this link. After having validated an incoming |
| 1257 |
packet from the network, the frontend would pass it to the host |
| 1258 |
saying "here is an Internet segment for you. Call it #123". The |
| 1259 |
host would save this segment, and send a copy back to the |
| 1260 |
frontend saying, "Here is what you gave me as #123. Is it OK?". |
| 1261 |
The frontend would then do a word-by-word comparison with the |
| 1262 |
first transmission, and tell the host either "Here is #123 |
| 1263 |
again", or "You did indeed receive #123 properly. Release it to |
| 1264 |
the appropriate module for further processing." |
| 1265 |
|
| 1266 |
The headers on the messages crossing the host-frontend link would |
| 1267 |
most likely be covered by a fairly strong checksum so that |
| 1268 |
information like which function is being performed and the |
| 1269 |
message reference numbers are reliable. These headers would be |
| 1270 |
quite short, maybe only sixteen bits, so the checksum could be |
| 1271 |
quite strong. The bulk of the message would not be checksumed of |
| 1272 |
course. |
| 1273 |
The reason this scheme reduces the computing burden on the host |
| 1274 |
is that all that is required in order to validate the message |
| 1275 |
using the end-to-end checksum is to send it back to the frontend |
| 1276 |
machine. In the case of the PDP-10, this requires only 0.5 |
| 1277 |
memory cycles per 16-bit byte of Internet message, and only a few |
| 1278 |
processor cycles to setup the required transfers. |
| 1279 |
|
| 1280 |
6. Conclusions |
| 1281 |
|
| 1282 |
There is an ordering of checksum functions: first and simplest is |
| 1283 |
none at all which provides no error detection or correction. |
| 1284 |
Second, is sending a constant which is checked by the receiver. |
| 1285 |
This also is extremely weak. Third, the exclusive-OR of the data |
| 1286 |
may be sent. XOR takes the minimal amount of computer time to |
| 1287 |
generate and check, but is not a good checksum. A two's |
| 1288 |
complement sum of the data is somewhat better and takes no more |
| 1289 |
|
| 1290 |
- 10 - |
| 1291 |
|
| 1292 |
|
| 1293 |
|
| 1294 |
<span class="grey">Braden, Borman, & Partridge [Page 22]</span></pre> |
| 1295 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-23" ></span> |
| 1296 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1297 |
|
| 1298 |
|
| 1299 |
Internet Experiment Note 45 5 June 1978 |
| 1300 |
TCP Checksum Function Design William W. Plummer |
| 1301 |
|
| 1302 |
computer time to compute. Fifth, is the one's complement sum |
| 1303 |
which is what is currently used by TCP. It is slightly more |
| 1304 |
expensive in terms of computer time. The next step is a product |
| 1305 |
code. The product code is strongly related to one's complement |
| 1306 |
sum, takes still more computer time to use, provides a bit more |
| 1307 |
protection against common hardware failures, but has some |
| 1308 |
objectionable properties. Next is a genuine CRC polynomial code, |
| 1309 |
used for checking purposes only. This is very expensive for a |
| 1310 |
program to implement. Finally, a full CRC error correcting and |
| 1311 |
detecting scheme may be used. |
| 1312 |
|
| 1313 |
For TCP and Internet applications the product code scheme is |
| 1314 |
viable. It suffers mainly in that messages must be (at least |
| 1315 |
partially) decoded by intermediate gateways in order that they |
| 1316 |
can be forwarded. Should product codes not be chosen as an |
| 1317 |
improved checksum, some slight modification to the existing |
| 1318 |
scheme might be possible. For instance the "add and rotate" |
| 1319 |
function used for paper tape by the PDP-6/10 group at the |
| 1320 |
Artificial Intelligence Laboratory at M.I.T. Project MAC [<a href="#ref-12" title="Robert C.">12</a>] |
| 1321 |
could be useful if it can be proved that it is better than the |
| 1322 |
current scheme and that it can be computed efficiently on a |
| 1323 |
variety of machines. |
| 1324 |
|
| 1325 |
|
| 1326 |
|
| 1327 |
|
| 1328 |
|
| 1329 |
|
| 1330 |
|
| 1331 |
|
| 1332 |
|
| 1333 |
|
| 1334 |
|
| 1335 |
|
| 1336 |
|
| 1337 |
|
| 1338 |
|
| 1339 |
|
| 1340 |
|
| 1341 |
|
| 1342 |
|
| 1343 |
|
| 1344 |
|
| 1345 |
- 11 - |
| 1346 |
|
| 1347 |
|
| 1348 |
|
| 1349 |
|
| 1350 |
|
| 1351 |
|
| 1352 |
|
| 1353 |
<span class="grey">Braden, Borman, & Partridge [Page 23]</span></pre> |
| 1354 |
<hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-24" ></span> |
| 1355 |
<span class="grey"><a href="./rfc1071">RFC 1071</a> Computing the Internet Checksum September 1988</span> |
| 1356 |
|
| 1357 |
|
| 1358 |
Internet Experiment Note 45 5 June 1978 |
| 1359 |
TCP Checksum Function Design William W. Plummer |
| 1360 |
|
| 1361 |
References |
| 1362 |
|
| 1363 |
[<a id="ref-1">1</a>] Cerf, V.G. and Kahn, Robert E., "A Protocol for Packet Network |
| 1364 |
Communications," IEEE Transactions on Communications, vol. |
| 1365 |
COM-22, No. 5, May 1974. |
| 1366 |
|
| 1367 |
[<a id="ref-2">2</a>] Kahn, Robert E., "The Organization of Computer Resources into |
| 1368 |
a Packet Radio Network", IEEE Transactions on Communications, |
| 1369 |
vol. COM-25, no. 1, pp. 169-178, January 1977. |
| 1370 |
|
| 1371 |
[<a id="ref-3">3</a>] Jacobs, Irwin, et al., "CPODA - A Demand Assignment Protocol |
| 1372 |
for SatNet", Fifth Data Communications Symposium, September |
| 1373 |
27-9, 1977, Snowbird, Utah |
| 1374 |
|
| 1375 |
[<a id="ref-4">4</a>] Bolt Beranek and Newman, Inc. "Specifications for the |
| 1376 |
Interconnection of a Host and an IMP", Report 1822, January |
| 1377 |
1976 edition. |
| 1378 |
|
| 1379 |
[<a id="ref-5">5</a>] Dean, Richard A., "Elements of Abstract Algebra", John Wyley |
| 1380 |
and Sons, Inc., 1966 |
| 1381 |
|
| 1382 |
[<a id="ref-6">6</a>] Peterson, W. Wesley, "Error Correcting Codes", M.I.T. Press |
| 1383 |
Cambridge MA, 4th edition, 1968. |
| 1384 |
|
| 1385 |
[<a id="ref-7">7</a>] Avizienis, Algirdas, "A Study of the Effectiveness of Fault- |
| 1386 |
Detecting Codes for Binary Arithmetic", Jet Propulsion |
| 1387 |
Laboratory Technical Report No. 32-711, September 1, 1965. |
| 1388 |
|
| 1389 |
[<a id="ref-8">8</a>] Kirstein, Peter, private communication |
| 1390 |
|
| 1391 |
[<a id="ref-9">9</a>] Cerf, V. G. and Postel, Jonathan B., "Specification of |
| 1392 |
Internetwork Transmission Control Program Version 3", |
| 1393 |
University of Southern California Information Sciences |
| 1394 |
Institute, January 1978. |
| 1395 |
|
| 1396 |
[<a id="ref-10">10</a>] Digital Equipment Corporation, "PDP-10 Reference Handbook", |
| 1397 |
1970, pp. 114-5. |
| 1398 |
|
| 1399 |
[<a id="ref-11">11</a>] Swanson, Robert, "Understanding Cyclic Redundancy Codes", |
| 1400 |
Computer Design, November, 1975, pp. 93-99. |
| 1401 |
|
| 1402 |
[<a id="ref-12">12</a>] Clements, Robert C., private communication. |
| 1403 |
|
| 1404 |
[<a id="ref-13">13</a>] Conklin, Peter F., and Rodgers, David P., "Advanced |
| 1405 |
Minicomputer Designed by Team Evaluation of Hardware/Software |
| 1406 |
Tradeoffs", Computer Design, April 1978, pp. 136-7. |
| 1407 |
|
| 1408 |
- 12 - |
| 1409 |
|
| 1410 |
|
| 1411 |
|
| 1412 |
Braden, Borman, & Partridge [Page 24] |
| 1413 |
</pre> |