/[dtapublic]/sf_code/esrgdstb/common/suppmatls/papers_articles/embedded_control/crc_gen/crc_rw_021211a.htm
ViewVC logotype

Contents of /sf_code/esrgdstb/common/suppmatls/papers_articles/embedded_control/crc_gen/crc_rw_021211a.htm

Parent Directory Parent Directory | Revision Log Revision Log


Revision 27 - (show annotations) (download) (as text)
Sat Oct 8 07:04:15 2016 UTC (7 years, 8 months ago) by dashley
File MIME type: text/html
File size: 95067 byte(s)
Initial commit.
1 <html>
2
3 <head>
4 <title>A Painless Guide To CRC Error Detection Algorithms, By Ross Williams</title>
5 </head>
6
7 <div align="center">
8 <center>
9
10 <pre><big><big><big><strong>A PAINLESS GUIDE TO</strong></big></big></big></pre>
11 </center>
12 </div>
13 <div align="center"><center>
14
15 <pre><strong><big><big><big>CRC ERROR DETECTION ALGORITHMS</big></big>
16 </big>
17 <big><big>
18 </big></big></strong><em>&quot;Everything you wanted to know about CRC algorithms, but were afraid
19 to ask for fear that errors in your understanding might be detected.&quot;</em></pre>
20 </center></div>
21
22 <pre>
23 <small>Version : 3.
24 Date : 19 August 1993.
25 Author : Ross N. Williams.
26 Net : ross@guest.adelaide.edu.au.
27 FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
28 Company : Rocksoft^tm Pty Ltd.
29 Snail : 16 Lerwick Avenue, Hazelwood Park 5066, Australia.
30 Fax : +61 8 373-4911 (c/- Internode Systems Pty Ltd).
31 Phone : +61 8 379-9217 (10am to 10pm Adelaide Australia time).
32 Note : &quot;Rocksoft&quot; is a trademark of Rocksoft Pty Ltd, Australia.
33 Status : Copyright (C) Ross Williams, 1993. However, permission is
34 granted to make and distribute verbatim copies of this
35 document provided that this information block and copyright
36 notice is included. Also, the C code modules included
37 in this document are fully public domain.
38 Thanks : Thanks to Jean-loup Gailly (jloup@chorus.fr) and Mark Adler
39 (me@quest.jpl.nasa.gov) who both proof read this document
40 and picked out lots of nits as well as some big fat bugs.</small></pre>
41
42 <pre><strong><big>Table of Contents</big></strong></pre>
43
44 <pre><strong><big>
45 </big></strong> Abstract
46 1. Introduction: Error Detection
47 2. The Need For Complexity
48 3. The Basic Idea Behind CRC Algorithms
49 4. Polynomical Arithmetic
50 5. Binary Arithmetic with No Carries
51 6. A Fully Worked Example
52 7. Choosing A Poly
53 8. A Straightforward CRC Implementation
54 9. A Table-Driven Implementation
55 10. A Slightly Mangled Table-Driven Implementation
56 11. &quot;Reflected&quot; Table-Driven Implementations
57 12. &quot;Reversed&quot; Polys
58 13. Initial and Final Values
59 14. Defining Algorithms Absolutely
60 15. A Parameterized Model For CRC Algorithms
61 16. A Catalog of Parameter Sets for Standards
62 17. An Implementation of the Model Algorithm
63 18. Roll Your Own Table-Driven Implementation
64 19. Generating A Lookup Table
65 20. Summary
66 21. Corrections
67 A. Glossary
68 B. References
69 C. References I Have Detected But Haven't Yet Sighted</pre>
70
71 <pre><big><strong>Abstract
72 </strong></big>
73 This document explains CRCs (Cyclic Redundancy Codes) and their
74 table-driven implementations in full, precise detail. Much of the
75 literature on CRCs, and in particular on their table-driven
76 implementations, is a little obscure (or at least seems so to me).
77 This document is an attempt to provide a clear and simple no-nonsense
78 explanation of CRCs and to absolutely nail down every detail of the
79 operation of their high-speed implementations. In addition to this,
80 this document presents a parameterized model CRC algorithm called the
81 &quot;Rocksoft^tm Model CRC Algorithm&quot;. The model algorithm can be
82 parameterized to behave like most of the CRC implementations around,
83 and so acts as a good reference for describing particular algorithms.
84 A low-speed implementation of the model CRC algorithm is provided in
85 the C programming language. Lastly there is a section giving two forms
86 of high-speed table driven implementations, and providing a program
87 that generates CRC lookup tables.
88 </pre>
89
90 <pre><strong><big>1. Introduction: Error Detection
91 </big></strong>
92 The aim of an error detection technique is to enable the receiver of a
93 message transmitted through a noisy (error-introducing) channel to
94 determine whether the message has been corrupted. To do this, the
95 transmitter constructs a value (called a checksum) that is a function
96 of the message, and appends it to the message. The receiver can then
97 use the same function to calculate the checksum of the received
98 message and compare it with the appended checksum to see if the
99 message was correctly received. For example, if we chose a checksum
100 function which was simply the sum of the bytes in the message mod 256
101 (i.e. modulo 256), then it might go something as follows. All numbers
102 are in decimal.</pre>
103
104 <pre> Message : 6 23 4
105 Message with checksum : 6 23 4 33
106 Message after transmission : 6 27 4 33</pre>
107
108 <pre>In the above, the second byte of the message was corrupted from 23 to
109 27 by the communications channel. However, the receiver can detect
110 this by comparing the transmitted checksum (33) with the computer
111 checksum of 37 (6 + 27 + 4). If the checksum itself is corrupted, a
112 correctly transmitted message might be incorrectly identified as a
113 corrupted one. However, this is a safe-side failure. A dangerous-side
114 failure occurs where the message and/or checksum is corrupted in a
115 manner that results in a transmission that is internally consistent.
116 Unfortunately, this possibility is completely unavoidable and the best
117 that can be done is to minimize its probability by increasing the
118 amount of information in the checksum (e.g. widening the checksum from
119 one byte to two bytes).</pre>
120
121 <pre>Other error detection techniques exist that involve performing complex
122 transformations on the message to inject it with redundant
123 information. However, this document addresses only CRC algorithms,
124 which fall into the class of error detection algorithms that leave the
125 data intact and append a checksum on the end. i.e.:</pre>
126
127 <pre> &lt;original intact message&gt; &lt;checksum&gt;
128 </pre>
129
130 <pre><strong><big>2. The Need For Complexity
131 </big></strong>
132 In the checksum example in the previous section, we saw how a
133 corrupted message was detected using a checksum algorithm that simply
134 sums the bytes in the message mod 256:</pre>
135
136 <pre> Message : 6 23 4
137 Message with checksum : 6 23 4 33
138 Message after transmission : 6 27 4 33</pre>
139
140 <pre>A problem with this algorithm is that it is too simple. If a number of
141 random corruptions occur, there is a 1 in 256 chance that they will
142 not be detected. For example:</pre>
143
144 <pre> Message : 6 23 4
145 Message with checksum : 6 23 4 33
146 Message after transmission : 8 20 5 33</pre>
147
148 <pre>To strengthen the checksum, we could change from an 8-bit register to
149 a 16-bit register (i.e. sum the bytes mod 65536 instead of mod 256) so
150 as to apparently reduce the probability of failure from 1/256 to
151 1/65536. While basically a good idea, it fails in this case because
152 the formula used is not sufficiently &quot;random&quot;; with a simple summing
153 formula, each incoming byte affects roughly only one byte of the
154 summing register no matter how wide it is. For example, in the second
155 example above, the summing register could be a Megabyte wide, and the
156 error would still go undetected. This problem can only be solved by
157 replacing the simple summing formula with a more sophisticated formula
158 that causes each incoming byte to have an effect on the entire
159 checksum register.</pre>
160
161 <pre>Thus, we see that at least two aspects are required to form a strong
162 checksum function:</pre>
163
164 <pre> WIDTH: A register width wide enough to provide a low a-priori
165 probability of failure (e.g. 32-bits gives a 1/2^32 chance
166 of failure).</pre>
167
168 <pre> CHAOS: A formula that gives each input byte the potential to change
169 any number of bits in the register.</pre>
170
171 <pre>Note: The term &quot;checksum&quot; was presumably used to describe early
172 summing formulas, but has now taken on a more general meaning
173 encompassing more sophisticated algorithms such as the CRC ones. The
174 CRC algorithms to be described satisfy the second condition very well,
175 and can be configured to operate with a variety of checksum widths.
176 </pre>
177
178 <pre><strong><big>3. The Basic Idea Behind CRC Algorithms
179 </big></strong>
180 Where might we go in our search for a more complex function than
181 summing? All sorts of schemes spring to mind. We could construct
182 tables using the digits of pi, or hash each incoming byte with all the
183 bytes in the register. We could even keep a large telephone book
184 on-line, and use each incoming byte combined with the register bytes
185 to index a new phone number which would be the next register value.
186 The possibilities are limitless.</pre>
187
188 <pre>However, we do not need to go so far; the next arithmetic step
189 suffices. While addition is clearly not strong enough to form an
190 effective checksum, it turns out that division is, so long as the
191 divisor is about as wide as the checksum register.</pre>
192
193 <pre>The basic idea of CRC algorithms is simply to treat the message as an
194 enormous binary number, to divide it by another fixed binary number,
195 and to make the remainder from this division the checksum. Upon
196 receipt of the message, the receiver can perform the same division and
197 compare the remainder with the &quot;checksum&quot; (transmitted remainder).</pre>
198
199 <pre>Example: Suppose the the message consisted of the two bytes (6,23) as
200 in the previous example. These can be considered to be the hexadecimal
201 number 0617 which can be considered to be the binary number
202 0000-0110-0001-0111. Suppose that we use a checksum register one-byte
203 wide and use a constant divisor of 1001, then the checksum is the
204 remainder after 0000-0110-0001-0111 is divided by 1001. While in this
205 case, this calculation could obviously be performed using common
206 garden variety 32-bit registers, in the general case this is messy. So
207 instead, we'll do the division using good-'ol long division which you
208 learnt in school (remember?). Except this time, it's in binary:</pre>
209
210 <pre> ...0000010101101 = 00AD = 173 = QUOTIENT
211 ____-___-___-___-
212 9= 1001 ) 0000011000010111 = 0617 = 1559 = DIVIDEND
213 DIVISOR 0000.,,....,.,,,
214 ----.,,....,.,,,
215 0000,,....,.,,,
216 0000,,....,.,,,
217 ----,,....,.,,,
218 0001,....,.,,,
219 0000,....,.,,,
220 ----,....,.,,,
221 0011....,.,,,
222 0000....,.,,,
223 ----....,.,,,
224 0110...,.,,,
225 0000...,.,,,
226 ----...,.,,,
227 1100..,.,,,
228 1001..,.,,,
229 ====..,.,,,
230 0110.,.,,,
231 0000.,.,,,
232 ----.,.,,,
233 1100,.,,,
234 1001,.,,,
235 ====,.,,,
236 0111.,,,
237 0000.,,,
238 ----.,,,
239 1110,,,
240 1001,,,
241 ====,,,
242 1011,,
243 1001,,
244 ====,,
245 0101,
246 0000,
247 ----
248 1011
249 1001
250 ====
251 0010 = 02 = 2 = REMAINDER
252 </pre>
253
254 <pre>In decimal this is &quot;1559 divided by 9 is 173 with a remainder of 2&quot;.</pre>
255
256 <pre>Although the effect of each bit of the input message on the quotient
257 is not all that significant, the 4-bit remainder gets kicked about
258 quite a lot during the calculation, and if more bytes were added to
259 the message (dividend) it's value could change radically again very
260 quickly. This is why division works where addition doesn't.</pre>
261
262 <pre>In case you're wondering, using this 4-bit checksum the transmitted
263 message would look like this (in hexadecimal): 06172 (where the 0617
264 is the message and the 2 is the checksum). The receiver would divide
265 0617 by 9 and see whether the remainder was 2.
266 </pre>
267
268 <pre><strong><big>4. Polynomical Arithmetic
269 </big></strong>
270 While the division scheme described in the previous section is very
271 very similar to the checksumming schemes called CRC schemes, the CRC
272 schemes are in fact a bit weirder, and we need to delve into some
273 strange number systems to understand them.</pre>
274
275 <pre>The word you will hear all the time when dealing with CRC algorithms
276 is the word &quot;polynomial&quot;. A given CRC algorithm will be said to be
277 using a particular polynomial, and CRC algorithms in general are said
278 to be operating using polynomial arithmetic. What does this mean?</pre>
279
280 <pre>Instead of the divisor, dividend (message), quotient, and remainder
281 (as described in the previous section) being viewed as positive
282 integers, they are viewed as polynomials with binary coefficients.
283 This is done by treating each number as a bit-string whose bits are
284 the coefficients of a polynomial. For example, the ordinary number 23
285 (decimal) is 17 (hex) and 10111 binary and so it corresponds to the
286 polynomial:</pre>
287
288 <pre> 1*x^4 + 0*x^3 + 1*x^2 + 1*x^1 + 1*x^0</pre>
289
290 <pre>or, more simply:</pre>
291
292 <pre> x^4 + x^2 + x^1 + x^0</pre>
293
294 <pre>Using this technique, the message, and the divisor can be represented
295 as polynomials and we can do all our arithmetic just as before, except
296 that now it's all cluttered up with Xs. For example, suppose we wanted
297 to multiply 1101 by 1011. We can do this simply by multiplying the
298 polynomials:</pre>
299
300 <pre>(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
301 = (x^6 + x^4 + x^3
302 + x^5 + x^3 + x^2
303 + x^3 + x^1 + x^0) = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0</pre>
304
305 <pre>At this point, to get the right answer, we have to pretend that x is 2
306 and propagate binary carries from the 3*x^3 yielding</pre>
307
308 <pre> x^7 + x^3 + x^2 + x^1 + x^0</pre>
309
310 <pre>It's just like ordinary arithmetic except that the base is abstracted
311 and brought into all the calculations explicitly instead of being
312 there implicitly. So what's the point?</pre>
313
314 <pre>The point is that IF we pretend that we DON'T know what x is, we CAN'T
315 perform the carries. We don't know that 3*x^3 is the same as x^4 + x^3
316 because we don't know that x is 2. In this true polynomial arithmetic
317 the relationship between all the coefficients is unknown and so the
318 coefficients of each power effectively become strongly typed;
319 coefficients of x^2 are effectively of a different type to
320 coefficients of x^3.</pre>
321
322 <pre>With the coefficients of each power nicely isolated, mathematicians
323 came up with all sorts of different kinds of polynomial arithmetics
324 simply by changing the rules about how coefficients work. Of these
325 schemes, one in particular is relevant here, and that is a polynomial
326 arithmetic where the coefficients are calculated MOD 2 and there is no
327 carry; all coefficients must be either 0 or 1 and no carries are
328 calculated. This is called &quot;polynomial arithmetic mod 2&quot;. Thus,
329 returning to the earlier example:</pre>
330
331 <pre>(x^3 + x^2 + x^0)(x^3 + x^1 + x^0)
332 = (x^6 + x^4 + x^3
333 + x^5 + x^3 + x^2
334 + x^3 + x^1 + x^0)
335 = x^6 + x^5 + x^4 + 3*x^3 + x^2 + x^1 + x^0</pre>
336
337 <pre>Under the other arithmetic, the 3*x^3 term was propagated using the
338 carry mechanism using the knowledge that x=2. Under &quot;polynomial
339 arithmetic mod 2&quot;, we don't know what x is, there are no carries, and
340 all coefficients have to be calculated mod 2. Thus, the result
341 becomes:</pre>
342
343 <pre>= x^6 + x^5 + x^4 + x^3 + x^2 + x^1 + x^0</pre>
344
345 <pre>As Knuth [Knuth81] says (p.400):</pre>
346
347 <pre> &quot;The reader should note the similarity between polynomial
348 arithmetic and multiple-precision arithmetic (Section 4.3.1), where
349 the radix b is substituted for x. The chief difference is that the
350 coefficient u_k of x^k in polynomial arithmetic bears little or no
351 relation to its neighboring coefficients x^{k-1} [and x^{k+1}], so
352 the idea of &quot;carrying&quot; from one place to another is absent. In fact
353 polynomial arithmetic modulo b is essentially identical to multiple
354 precision arithmetic with radix b, except that all carries are
355 suppressed.&quot;</pre>
356
357 <pre>Thus polynomical arithmetic mod 2 is just binary arithmetic mod 2 with
358 no carries. While polynomials provide useful mathematical machinery in
359 more analytical approaches to CRC and error-correction algorithms, for
360 the purposes of exposition they provide no extra insight and some
361 encumbrance and have been discarded in the remainder of this document
362 in favour of direct manipulation of the arithmetical system with which
363 they are isomorphic: binary arithmetic with no carry.
364 </pre>
365
366 <pre><strong><big>5. Binary Arithmetic with No Carries
367 </big></strong>
368 Having dispensed with polynomials, we can focus on the real arithmetic
369 issue, which is that all the arithmetic performed during CRC
370 calculations is performed in binary with no carries. Often this is
371 called polynomial arithmetic, but as I have declared the rest of this
372 document a polynomial free zone, we'll have to call it CRC arithmetic
373 instead. As this arithmetic is a key part of CRC calculations, we'd
374 better get used to it. Here we go:</pre>
375
376 <pre>Adding two numbers in CRC arithmetic is the same as adding numbers in
377 ordinary binary arithmetic except there is no carry. This means that
378 each pair of corresponding bits determine the corresponding output bit
379 without reference to any other bit positions. For example:</pre>
380
381 <pre> 10011011
382 +11001010
383 --------
384 01010001
385 --------</pre>
386
387 <pre>There are only four cases for each bit position:</pre>
388
389 <pre> 0+0=0
390 0+1=1
391 1+0=1
392 1+1=0 (no carry)</pre>
393
394 <pre>Subtraction is identical:</pre>
395
396 <pre> 10011011
397 -11001010
398 --------
399 01010001
400 --------</pre>
401
402 <pre>with</pre>
403
404 <pre> 0-0=0
405 0-1=1 (wraparound)
406 1-0=1
407 1-1=0</pre>
408
409 <pre>In fact, both addition and subtraction in CRC arithmetic is equivalent
410 to the XOR operation, and the XOR operation is its own inverse. This
411 effectively reduces the operations of the first level of power
412 (addition, subtraction) to a single operation that is its own inverse.
413 This is a very convenient property of the arithmetic.</pre>
414
415 <pre>By collapsing of addition and subtraction, the arithmetic discards any
416 notion of magnitude beyond the power of its highest one bit. While it
417 seems clear that 1010 is greater than 10, it is no longer the case
418 that 1010 can be considered to be greater than 1001. To see this, note
419 that you can get from 1010 to 1001 by both adding and subtracting the
420 same quantity:</pre>
421
422 <pre> 1010 = 1010 + 0011
423 1010 = 1010 - 0011</pre>
424
425 <pre>This makes nonsense of any notion of order.</pre>
426
427 <pre>Having defined addition, we can move to multiplication and division.
428 Multiplication is absolutely straightforward, being the sum of the
429 first number, shifted in accordance with the second number.</pre>
430
431 <pre> 1101
432 x 1011
433 ----
434 1101
435 1101.
436 0000..
437 1101...
438 -------
439 1111111 Note: The sum uses CRC addition
440 -------</pre>
441
442 <pre>Division is a little messier as we need to know when &quot;a number goes
443 into another number&quot;. To do this, we invoke the weak definition of
444 magnitude defined earlier: that X is greater than or equal to Y iff
445 the position of the highest 1 bit of X is the same or greater than the
446 position of the highest 1 bit of Y. Here's a fully worked division
447 (nicked from [Tanenbaum81]).</pre>
448
449 <pre> 1100001010
450 _______________
451 10011 ) 11010110110000
452 10011,,.,,....
453 -----,,.,,....
454 10011,.,,....
455 10011,.,,....
456 -----,.,,....
457 00001.,,....
458 00000.,,....
459 -----.,,....
460 00010,,....
461 00000,,....
462 -----,,....
463 00101,....
464 00000,....
465 -----,....
466 01011....
467 00000....
468 -----....
469 10110...
470 10011...
471 -----...
472 01010..
473 00000..
474 -----..
475 10100.
476 10011.
477 -----.
478 01110
479 00000
480 -----
481 1110 = Remainder</pre>
482
483 <pre>That's really it. Before proceeding further, however, it's worth our
484 while playing with this arithmetic a bit to get used to it.</pre>
485
486 <pre>We've already played with addition and subtraction, noticing that they
487 are the same thing. Here, though, we should note that in this
488 arithmetic A+0=A and A-0=A. This obvious property is very useful
489 later.</pre>
490
491 <pre>In dealing with CRC multiplication and division, it's worth getting a
492 feel for the concepts of MULTIPLE and DIVISIBLE.</pre>
493
494 <pre>If a number A is a multiple of B then what this means in CRC
495 arithmetic is that it is possible to construct A from zero by XORing
496 in various shifts of B. For example, if A was 0111010110 and B was 11,
497 we could construct A from B as follows:</pre>
498
499 <pre> 0111010110
500 = .......11.
501 + ....11....
502 + ...11.....
503 .11.......</pre>
504
505 <pre>However, if A is 0111010111, it is not possible to construct it out of
506 various shifts of B (can you see why? - see later) so it is said to be
507 not divisible by B in CRC arithmetic.</pre>
508
509 <pre>Thus we see that CRC arithmetic is primarily about XORing particular
510 values at various shifting offsets.
511 </pre>
512
513 <pre><big><strong>6. A Fully Worked Example
514 </strong></big>
515 Having defined CRC arithmetic, we can now frame a CRC calculation as
516 simply a division, because that's all it is! This section fills in the
517 details and gives an example.</pre>
518
519 <pre>To perform a CRC calculation, we need to choose a divisor. In maths
520 marketing speak the divisor is called the &quot;generator polynomial&quot; or
521 simply the &quot;polynomial&quot;, and is a key parameter of any CRC algorithm.
522 It would probably be more friendly to call the divisor something else,
523 but the poly talk is so deeply ingrained in the field that it would
524 now be confusing to avoid it. As a compromise, we will refer to the
525 CRC polynomial as the &quot;poly&quot;. Just think of this number as a sort of
526 parrot. &quot;Hello poly!&quot;</pre>
527
528 <pre>You can choose any poly and come up with a CRC algorithm. However,
529 some polys are better than others, and so it is wise to stick with the
530 tried an tested ones. A later section addresses this issue.</pre>
531
532 <pre>The width (position of the highest 1 bit) of the poly is very
533 important as it dominates the whole calculation. Typically, widths of
534 16 or 32 are chosen so as to simplify implementation on modern
535 computers. The width of a poly is the actual bit position of the
536 highest bit. For example, the width of 10011 is 4, not 5. For the
537 purposes of example, we will chose a poly of 10011 (of width W of 4).</pre>
538
539 <pre>Having chosen a poly, we can proceed with the calculation. This is
540 simply a division (in CRC arithmetic) of the message by the poly. The
541 only trick is that W zero bits are appended to the message before the
542 CRC is calculated. Thus we have:</pre>
543
544 <pre> Original message : 1101011011
545 Poly : 10011
546 Message after appending W zeros : 11010110110000</pre>
547
548 <pre>Now we simply divide the augmented message by the poly using CRC
549 arithmetic. This is the same division as before:</pre>
550
551 <pre> 1100001010 = Quotient (nobody cares about the quotient)
552 _______________
553 10011 ) 11010110110000 = Augmented message (1101011011 + 0000)
554 =Poly 10011,,.,,....
555 -----,,.,,....
556 10011,.,,....
557 10011,.,,....
558 -----,.,,....
559 00001.,,....
560 00000.,,....
561 -----.,,....
562 00010,,....
563 00000,,....
564 -----,,....
565 00101,....
566 00000,....
567 -----,....
568 01011....
569 00000....
570 -----....
571 10110...
572 10011...
573 -----...
574 01010..
575 00000..
576 -----..
577 10100.
578 10011.
579 -----.
580 01110
581 00000
582 -----
583 1110 = Remainder = THE CHECKSUM!!!!</pre>
584
585 <pre>The division yields a quotient, which we throw away, and a remainder,
586 which is the calculated checksum. This ends the calculation.</pre>
587
588 <pre>Usually, the checksum is then appended to the message and the result
589 transmitted. In this case the transmission would be: 11010110111110.</pre>
590
591 <pre>At the other end, the receiver can do one of two things:</pre>
592
593 <pre> a. Separate the message and checksum. Calculate the checksum for
594 the message (after appending W zeros) and compare the two
595 checksums.</pre>
596
597 <pre> b. Checksum the whole lot (without appending zeros) and see if it
598 comes out as zero!</pre>
599
600 <pre>These two options are equivalent. However, in the next section, we
601 will be assuming option b because it is marginally mathematically
602 cleaner.</pre>
603
604 <pre>A summary of the operation of the class of CRC algorithms:</pre>
605
606 <pre> 1. Choose a width W, and a poly G (of width W).
607 2. Append W zero bits to the message. Call this M'.
608 3. Divide M' by G using CRC arithmetic. The remainder is the checksum.</pre>
609
610 <pre>That's all there is to it.</pre>
611
612 <pre><strong><big>7. Choosing A Poly
613 </big></strong>
614 Choosing a poly is somewhat of a black art and the reader is referred
615 to [Tanenbaum81] (p.130-132) which has a very clear discussion of this
616 issue. This section merely aims to put the fear of death into anyone
617 who so much as toys with the idea of making up their own poly. If you
618 don't care about why one poly might be better than another and just
619 want to find out about high-speed implementations, choose one of the
620 arithmetically sound polys listed at the end of this section and skip
621 to the next section.</pre>
622
623 <pre>First note that the transmitted message T is a multiple of the poly.
624 To see this, note that 1) the last W bits of T is the remainder after
625 dividing the augmented (by zeros remember) message by the poly, and 2)
626 addition is the same as subtraction so adding the remainder pushes the
627 value up to the next multiple. Now note that if the transmitted
628 message is corrupted in transmission that we will receive T+E where E
629 is an error vector (and + is CRC addition (i.e. XOR)). Upon receipt of
630 this message, the receiver divides T+E by G. As T mod G is 0, (T+E)
631 mod G = E mod G. Thus, the capacity of the poly we choose to catch
632 particular kinds of errors will be determined by the set of multiples
633 of G, for any corruption E that is a multiple of G will be undetected.
634 Our task then is to find classes of G whose multiples look as little
635 like the kind of line noise (that will be creating the corruptions) as
636 possible. So let's examine the kinds of line noise we can expect.</pre>
637
638 <pre><strong>SINGLE BIT ERRORS:</strong> A single bit error means E=1000...0000. We can
639 ensure that this class of error is always detected by making sure that
640 G has at least two bits set to 1. Any multiple of G will be
641 constructed using shifting and adding and it is impossible to
642 construct a value with a single bit by shifting an adding a single
643 value with more than one bit set, as the two end bits will always
644 persist.</pre>
645
646 <pre><strong>TWO-BIT ERRORS:</strong> To detect all errors of the form 100...000100...000
647 (i.e. E contains two 1 bits) choose a G that does not have multiples
648 that are 11, 101, 1001, 10001, 100001, etc. It is not clear to me how
649 one goes about doing this (I don't have the pure maths background),
650 but Tanenbaum assures us that such G do exist, and cites G with 1 bits
651 (15,14,1) turned on as an example of one G that won't divide anything
652 less than 1...1 where ... is 32767 zeros.</pre>
653
654 <pre><strong>ERRORS WITH AN ODD NUMBER OF BITS:</strong> We can catch all corruptions where
655 E has an odd number of bits by choosing a G that has an even number of
656 bits. To see this, note that 1) CRC multiplication is simply XORing a
657 constant value into a register at various offsets, 2) XORing is simply
658 a bit-flip operation, and 3) if you XOR a value with an even number of
659 bits into a register, the oddness of the number of 1 bits in the
660 register remains invariant. Example: Starting with E=111, attempt to
661 flip all three bits to zero by the repeated application of XORing in
662 11 at one of the two offsets (i.e. &quot;E=E XOR 011&quot; and &quot;E=E XOR 110&quot;)
663 This is nearly isomorphic to the &quot;glass tumblers&quot; party puzzle where
664 you challenge someone to flip three tumblers by the repeated
665 application of the operation of flipping any two. Most of the popular
666 CRC polys contain an even number of 1 bits. (Note: Tanenbaum states
667 more specifically that all errors with an odd number of bits can be
668 caught by making G a multiple of 11).</pre>
669
670 <pre><strong>BURST ERRORS:</strong> A burst error looks like E=000...000111...11110000...00.
671 That is, E consists of all zeros except for a run of 1s somewhere
672 inside. This can be recast as E=(10000...00)(1111111...111) where
673 there are z zeros in the LEFT part and n ones in the RIGHT part. To
674 catch errors of this kind, we simply set the lowest bit of G to 1.
675 Doing this ensures that LEFT cannot be a factor of G. Then, so long as
676 G is wider than RIGHT, the error will be detected. See Tanenbaum for a
677 clearer explanation of this; I'm a little fuzzy on this one. Note:
678 Tanenbaum asserts that the probability of a burst of length greater
679 than W getting through is (0.5)^W.</pre>
680
681 <pre>That concludes the section on the fine art of selecting polys.</pre>
682
683 <pre>Some popular polys are:
684 16 bits: (16,12,5,0) [X25 standard]
685 (16,15,2,0) [&quot;CRC-16&quot;]
686 32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
687 </pre>
688
689 <pre><big><strong>8. A Straightforward CRC Implementation
690 </strong></big>
691 That's the end of the theory; now we turn to implementations. To start
692 with, we examine an absolutely straight-down-the-middle boring
693 straightforward low-speed implementation that doesn't use any speed
694 tricks at all. We'll then transform that program progessively until we
695 end up with the compact table-driven code we all know and love and
696 which some of us would like to understand.</pre>
697
698 <pre>To implement a CRC algorithm all we have to do is implement CRC
699 division. There are two reasons why we cannot simply use the divide
700 instruction of whatever machine we are on. The first is that we have
701 to do the divide in CRC arithmetic. The second is that the dividend
702 might be ten megabytes long, and todays processors do not have
703 registers that big.</pre>
704
705 <pre>So to implement CRC division, we have to feed the message through a
706 division register. At this point, we have to be absolutely precise
707 about the message data. In all the following examples the message will
708 be considered to be a stream of bytes (each of 8 bits) with bit 7 of
709 each byte being considered to be the most significant bit (MSB). The
710 bit stream formed from these bytes will be the bit stream with the MSB
711 (bit 7) of the first byte first, going down to bit 0 of the first
712 byte, and then the MSB of the second byte and so on.</pre>
713
714 <pre>With this in mind, we can sketch an implementation of the CRC
715 division. For the purposes of example, consider a poly with W=4 and
716 the poly=10111. Then, the perform the division, we need to use a 4-bit
717 register:</pre>
718
719 <pre> 3 2 1 0 Bits
720 +---+---+---+---+
721 Pop! &lt;-- | | | | | &lt;----- Augmented message
722 +---+---+---+---+</pre>
723
724 <pre> 1 0 1 1 1 = The Poly</pre>
725
726 <pre>(Reminder: The augmented message is the message followed by W zero bits.)</pre>
727
728 <pre>To perform the division perform the following:</pre>
729
730 <pre> Load the register with zero bits.
731 Augment the message by appending W zero bits to the end of it.
732 While (more message bits)
733 Begin
734 Shift the register left by one bit, reading the next bit of the
735 augmented message into register bit position 0.
736 If (a 1 bit popped out of the register during step 3)
737 Register = Register XOR Poly.
738 End
739 The register now contains the remainder.</pre>
740
741 <pre>(Note: In practice, the IF condition can be tested by testing the top
742 bit of R before performing the shift.)</pre>
743
744 <pre>We will call this algorithm &quot;SIMPLE&quot;.</pre>
745
746 <pre>This might look a bit messy, but all we are really doing is
747 &quot;subtracting&quot; various powers (i.e. shiftings) of the poly from the
748 message until there is nothing left but the remainder. Study the
749 manual examples of long division if you don't understand this.</pre>
750
751 <pre>It should be clear that the above algorithm will work for any width W.
752 </pre>
753
754 <pre><big><strong>9. A Table-Driven Implementation
755 </strong></big>
756 The SIMPLE algorithm above is a good starting point because it
757 corresponds directly to the theory presented so far, and because it is
758 so SIMPLE. However, because it operates at the bit level, it is rather
759 awkward to code (even in C), and inefficient to execute (it has to
760 loop once for each bit). To speed it up, we need to find a way to
761 enable the algorithm to process the message in units larger than one
762 bit. Candidate quantities are nibbles (4 bits), bytes (8 bits), words
763 (16 bits) and longwords (32 bits) and higher if we can achieve it. Of
764 these, 4 bits is best avoided because it does not correspond to a byte
765 boundary. At the very least, any speedup should allow us to operate at
766 byte boundaries, and in fact most of the table driven algorithms
767 operate a byte at a time.</pre>
768
769 <pre>For the purposes of discussion, let us switch from a 4-bit poly to a
770 32-bit one. Our register looks much the same, except the boxes
771 represent bytes instead of bits, and the Poly is 33 bits (one implicit
772 1 bit at the top and 32 &quot;active&quot; bits) (W=32).</pre>
773
774 <pre> 3 2 1 0 Bytes
775 +----+----+----+----+
776 Pop! &lt;-- | | | | | &lt;----- Augmented message
777 +----+----+----+----+</pre>
778
779 <pre> 1&lt;------32 bits------&gt;</pre>
780
781 <pre>The SIMPLE algorithm is still applicable. Let us examine what it does.
782 Imagine that the SIMPLE algorithm is in full swing and consider the
783 top 8 bits of the 32-bit register (byte 3) to have the values:</pre>
784
785 <pre> t7 t6 t5 t4 t3 t2 t1 t0</pre>
786
787 <pre>In the next iteration of SIMPLE, t7 will determine whether the Poly
788 will be XORed into the entire register. If t7=1, this will happen,
789 otherwise it will not. Suppose that the top 8 bits of the poly are g7
790 g6.. g0, then after the next iteration, the top byte will be:</pre>
791
792 <pre> t6 t5 t4 t3 t2 t1 t0 ??
793 + t7 * (g7 g6 g5 g4 g3 g2 g1 g0) [Reminder: + is XOR]</pre>
794
795 <pre>The NEW top bit (that will control what happens in the next iteration)
796 now has the value t6 + t7*g7. The important thing to notice here is
797 that from an informational point of view, all the information required
798 to calculate the NEW top bit was present in the top TWO bits of the
799 original top byte. Similarly, the NEXT top bit can be calculated in
800 advance SOLELY from the top THREE bits t7, t6, and t5. In fact, in
801 general, the value of the top bit in the register in k iterations can
802 be calculated from the top k bits of the register. Let us take this
803 for granted for a moment.</pre>
804
805 <pre>Consider for a moment that we use the top 8 bits of the register to
806 calculate the value of the top bit of the register during the next 8
807 iterations. Suppose that we drive the next 8 iterations using the
808 calculated values (which we could perhaps store in a single byte
809 register and shift out to pick off each bit). Then we note three
810 things:</pre>
811
812 <pre> * The top byte of the register now doesn't matter. No matter how
813 many times and at what offset the poly is XORed to the top 8
814 bits, they will all be shifted out the right hand side during the
815 next 8 iterations anyway.
816 </pre>
817
818 <pre> * The remaining bits will be shifted left one position and the
819 rightmost byte of the register will be shifted in the next byte</pre>
820
821 <pre> AND</pre>
822
823 <pre> * While all this is going on, the register will be subjected to a
824 series of XOR's in accordance with the bits of the pre-calculated
825 control byte.</pre>
826
827 <pre>Now consider the effect of XORing in a constant value at various
828 offsets to a register. For example:</pre>
829
830 <pre> 0100010 Register
831 ...0110 XOR this
832 ..0110. XOR this
833 0110... XOR this
834 -------
835 0011000
836 -------</pre>
837
838 <pre>The point of this is that you can XOR constant values into a register
839 to your heart's delight, and in the end, there will exist a value
840 which when XORed in with the original register will have the same
841 effect as all the other XORs.</pre>
842
843 <pre>Perhaps you can see the solution now. Putting all the pieces together
844 we have an algorithm that goes like this:</pre>
845
846 <pre><em> While (augmented message is not exhausted)
847 Begin
848 Examine the top byte of the register
849 Calculate the control byte from the top byte of the register
850 Sum all the Polys at various offsets that are to be XORed into
851 the register in accordance with the control byte
852 Shift the register left by one byte, reading a new message byte
853 into the rightmost byte of the register
854 XOR the summed polys to the register
855 End</em></pre>
856
857 <pre>As it stands this is not much better than the SIMPLE algorithm.
858 However, it turns out that most of the calculation can be precomputed
859 and assembled into a table. As a result, the above algorithm can be
860 reduced to:</pre>
861
862 <pre><em> While (augmented message is not exhaused)
863 Begin
864 Top = top_byte(Register);
865 Register = (Register &lt;&lt; 24) | next_augmessage_byte;
866 Register = Register XOR precomputed_table[Top];
867 End</em></pre>
868
869 <pre>There! If you understand this, you've grasped the main idea of
870 table-driven CRC algorithms. The above is a very efficient algorithm
871 requiring just a shift, and OR, an XOR, and a table lookup per byte.
872 Graphically, it looks like this:</pre>
873
874 <pre> 3 2 1 0 Bytes
875 +----+----+----+----+
876 +-----&lt;| | | | | &lt;----- Augmented message
877 | +----+----+----+----+
878 | ^
879 | |
880 | XOR
881 | |
882 | 0+----+----+----+----+ Algorithm
883 v +----+----+----+----+ ---------
884 | +----+----+----+----+ 1. Shift the register left by
885 | +----+----+----+----+ one byte, reading in a new
886 | +----+----+----+----+ message byte.
887 | +----+----+----+----+ 2. Use the top byte just rotated
888 | +----+----+----+----+ out of the register to index
889 +-----&gt;+----+----+----+----+ the table of 256 32-bit values.
890 +----+----+----+----+ 3. XOR the table value into the
891 +----+----+----+----+ register.
892 +----+----+----+----+ 4. Goto 1 iff more augmented
893 +----+----+----+----+ message bytes.
894 255+----+----+----+----+
895 </pre>
896
897 <pre>In C, the algorithm main loop looks like this:</pre>
898
899 <pre> <em> r=0;
900 while (len--)
901 {
902 byte t = (r &gt;&gt; 24) &amp; 0xFF;
903 r = (r &lt;&lt; 8) | *p++;
904 r^=table[t];
905 }</em></pre>
906
907 <pre>where len is the length of the augmented message in bytes, p points to
908 the augmented message, r is the register, t is a temporary, and table
909 is the computed table. This code can be made even more unreadable as
910 follows:</pre>
911
912 <pre><em> r=0; while (len--) r = ((r &lt;&lt; 8) | *p++) ^ t[(r &gt;&gt; 24) &amp; 0xFF];</em></pre>
913
914 <pre>This is a very clean, efficient loop, although not a very obvious one
915 to the casual observer not versed in CRC theory. We will call this the
916 TABLE algorithm.
917 </pre>
918
919 <pre><strong><big>10. A Slightly Mangled Table-Driven Implementation
920 </big></strong>
921 Despite the terse beauty of the line</pre>
922
923 <pre><em> r=0; while (len--) r = ((r &lt;&lt; 8) | *p++) ^ t[(r &gt;&gt; 24) &amp; 0xFF];</em></pre>
924
925 <pre>those optimizing hackers couldn't leave it alone. The trouble, you
926 see, is that this loop operates upon the AUGMENTED message and in
927 order to use this code, you have to append W/8 zero bytes to the end
928 of the message before pointing p at it. Depending on the run-time
929 environment, this may or may not be a problem; if the block of data
930 was handed to us by some other code, it could be a BIG problem. One
931 alternative is simply to append the following line after the above
932 loop, once for each zero byte:</pre>
933
934 <pre> for (i=0; i&lt;W/4; i++) r = (r &lt;&lt; 8) ^ t[(r &gt;&gt; 24) &amp; 0xFF];</pre>
935
936 <pre>This looks like a sane enough solution to me. However, at the further
937 expense of clarity (which, you must admit, is already a pretty scare
938 commodity in this code) we can reorganize this small loop further so
939 as to avoid the need to either augment the message with zero bytes, or
940 to explicitly process zero bytes at the end as above. To explain the
941 optimization, we return to the processing diagram given earlier.</pre>
942
943 <pre> 3 2 1 0 Bytes
944 +----+----+----+----+
945 +-----&lt;| | | | | &lt;----- Augmented message
946 | +----+----+----+----+
947 | ^
948 | |
949 | XOR
950 | |
951 | 0+----+----+----+----+ Algorithm
952 v +----+----+----+----+ ---------
953 | +----+----+----+----+ 1. Shift the register left by
954 | +----+----+----+----+ one byte, reading in a new
955 | +----+----+----+----+ message byte.
956 | +----+----+----+----+ 2. Use the top byte just rotated
957 | +----+----+----+----+ out of the register to index
958 +-----&gt;+----+----+----+----+ the table of 256 32-bit values.
959 +----+----+----+----+ 3. XOR the table value into the
960 +----+----+----+----+ register.
961 +----+----+----+----+ 4. Goto 1 iff more augmented
962 +----+----+----+----+ message bytes.
963 255+----+----+----+----+</pre>
964
965 <pre>Now, note the following facts:</pre>
966
967 <pre><strong>TAIL:</strong> The W/4 augmented zero bytes that appear at the end of the
968 message will be pushed into the register from the right as all
969 the other bytes are, but their values (0) will have no effect
970 whatsoever on the register because 1) XORing with zero does not
971 change the target byte, and 2) the four bytes are never
972 propagated out the left side of the register where their
973 zeroness might have some sort of influence. Thus, the sole
974 function of the W/4 augmented zero bytes is to drive the
975 calculation for another W/4 byte cycles so that the end of the
976 REAL data passes all the way through the register.</pre>
977
978 <pre><strong>HEAD:</strong> If the initial value of the register is zero, the first four
979 iterations of the loop will have the sole effect of shifting in
980 the first four bytes of the message from the right. This is
981 because the first 32 control bits are all zero and so nothing is
982 XORed into the register. Even if the initial value is not zero,
983 the first 4 byte iterations of the algorithm will have the sole
984 effect of shifting the first 4 bytes of the message into the
985 register and then XORing them with some constant value (that is
986 a function of the initial value of the register).</pre>
987
988 <pre>These facts, combined with the XOR property</pre>
989
990 <pre> (A xor B) xor C = A xor (B xor C)</pre>
991
992 <pre>mean that message bytes need not actually travel through the W/4 bytes
993 of the register. Instead, they can be XORed into the top byte just
994 before it is used to index the lookup table. This leads to the
995 following modified version of the algorithm.
996 </pre>
997
998 <pre> +-----&lt;Message (non augmented)
999 |
1000 v 3 2 1 0 Bytes
1001 | +----+----+----+----+
1002 XOR----&lt;| | | | |
1003 | +----+----+----+----+
1004 | ^
1005 | |
1006 | XOR
1007 | |
1008 | 0+----+----+----+----+ Algorithm
1009 v +----+----+----+----+ ---------
1010 | +----+----+----+----+ 1. Shift the register left by
1011 | +----+----+----+----+ one byte, reading in a new
1012 | +----+----+----+----+ message byte.
1013 | +----+----+----+----+ 2. XOR the top byte just rotated
1014 | +----+----+----+----+ out of the register with the
1015 +-----&gt;+----+----+----+----+ next message byte to yield an
1016 +----+----+----+----+ index into the table ([0,255]).
1017 +----+----+----+----+ 3. XOR the table value into the
1018 +----+----+----+----+ register.
1019 +----+----+----+----+ 4. Goto 1 iff more augmented
1020 255+----+----+----+----+ message bytes.
1021 </pre>
1022
1023 <pre>Note: The initial register value for this algorithm must be the
1024 initial value of the register for the previous algorithm fed through
1025 the table four times. Note: The table is such that if the previous
1026 algorithm used 0, the new algorithm will too.</pre>
1027
1028 <pre>This is an IDENTICAL algorithm and will yield IDENTICAL results. The C
1029 code looks something like this:</pre>
1030
1031 <pre> r=0; while (len--) r = (r&lt;&lt;8) ^ t[(r &gt;&gt; 24) ^ *p++];</pre>
1032
1033 <pre>and THIS is the code that you are likely to find inside current
1034 table-driven CRC implementations. Some FF masks might have to be ANDed
1035 in here and there for portability's sake, but basically, the above
1036 loop is IT. We will call this the DIRECT TABLE ALGORITHM.</pre>
1037
1038 <pre>During the process of trying to understand all this stuff, I managed
1039 to derive the SIMPLE algorithm and the table-driven version derived
1040 from that. However, when I compared my code with the code found in
1041 real-implementations, I was totally bamboozled as to why the bytes
1042 were being XORed in at the wrong end of the register! It took quite a
1043 while before I figured out that theirs and my algorithms were actually
1044 the same. Part of why I am writing this document is that, while the
1045 link between division and my earlier table-driven code is vaguely
1046 apparent, any such link is fairly well erased when you start pumping
1047 bytes in at the &quot;wrong end&quot; of the register. It looks all wrong!</pre>
1048
1049 <pre>If you've got this far, you not only understand the theory, the
1050 practice, the optimized practice, but you also understand the real
1051 code you are likely to run into. Could get any more complicated? Yes
1052 it can.
1053 </pre>
1054
1055 <pre><big><strong>11. &quot;Reflected&quot; Table-Driven Implementations
1056 </strong></big>
1057 Despite the fact that the above code is probably optimized about as
1058 much as it could be, this did not stop some enterprising individuals
1059 from making things even more complicated. To understand how this
1060 happened, we have to enter the world of hardware.</pre>
1061
1062 <pre><strong>DEFINITION:</strong> A value/register is reflected if it's bits are swapped
1063 around its centre. For example: 0101 is the 4-bit reflection of 1010.
1064 0011 is the reflection of 1100.
1065 0111-0101-1010-1111-0010-0101-1011-1100 is the reflection of
1066 0011-1101-1010-0100-1111-0101-1010-1110.</pre>
1067
1068 <pre>Turns out that UARTs (those handy little chips that perform serial IO)
1069 are in the habit of transmitting each byte with the least significant
1070 bit (bit 0) first and the most significant bit (bit 7) last (i.e.
1071 reflected). An effect of this convention is that hardware engineers
1072 constructing hardware CRC calculators that operate at the bit level
1073 took to calculating CRCs of bytes streams with each of the bytes
1074 reflected within itself. The bytes are processed in the same order,
1075 but the bits in each byte are swapped; bit 0 is now bit 7, bit 1 is
1076 now bit 6, and so on. Now this wouldn't matter much if this convention
1077 was restricted to hardware land. However it seems that at some stage
1078 some of these CRC values were presented at the software level and
1079 someone had to write some code that would interoperate with the
1080 hardware CRC calculation.</pre>
1081
1082 <pre>In this situation, a normal sane software engineer would simply
1083 reflect each byte before processing it. However, it would seem that
1084 normal sane software engineers were thin on the ground when this early
1085 ground was being broken, because instead of reflecting the bytes,
1086 whoever was responsible held down the byte and reflected the world,
1087 leading to the following &quot;reflected&quot; algorithm which is identical to
1088 the previous one except that everything is reflected except the input
1089 bytes.
1090 </pre>
1091
1092 <pre> Message (non augmented) &gt;-----+
1093 |
1094 Bytes 0 1 2 3 v
1095 +----+----+----+----+ |
1096 | | | | |&gt;----XOR
1097 +----+----+----+----+ |
1098 ^ |
1099 | |
1100 XOR |
1101 | |
1102 +----+----+----+----+0 |
1103 +----+----+----+----+ v
1104 +----+----+----+----+ |
1105 +----+----+----+----+ |
1106 +----+----+----+----+ |
1107 +----+----+----+----+ |
1108 +----+----+----+----+ |
1109 +----+----+----+----+&lt;-----+
1110 +----+----+----+----+
1111 +----+----+----+----+
1112 +----+----+----+----+
1113 +----+----+----+----+
1114 +----+----+----+----+255</pre>
1115
1116 <pre>Notes:</pre>
1117
1118 <pre> * The table is identical to the one in the previous algorithm
1119 except that each entry has been reflected.</pre>
1120
1121 <pre> * The initial value of the register is the same as in the previous
1122 algorithm except that it has been reflected.</pre>
1123
1124 <pre> * The bytes of the message are processed in the same order as
1125 before (i.e. the message itself is not reflected).</pre>
1126
1127 <pre> * The message bytes themselves don't need to be explicitly
1128 reflected, because everything else has been!</pre>
1129
1130 <pre>At the end of execution, the register contains the reflection of the
1131 final CRC value (remainder). Actually, I'm being rather hard on
1132 whoever cooked this up because it seems that hardware implementations
1133 of the CRC algorithm used the reflected checksum value and so
1134 producing a reflected CRC was just right. In fact reflecting the world
1135 was probably a good engineering solution - if a confusing one.</pre>
1136
1137 <pre>We will call this the REFLECTED algorithm.</pre>
1138
1139 <pre>Whether or not it made sense at the time, the effect of having
1140 reflected algorithms kicking around the world's FTP sites is that
1141 about half the CRC implementations one runs into are reflected and the
1142 other half not. It's really terribly confusing. In particular, it
1143 would seem to me that the casual reader who runs into a reflected,
1144 table-driven implementation with the bytes &quot;fed in the wrong end&quot;
1145 would have Buckley's chance of ever connecting the code to the concept
1146 of binary mod 2 division.</pre>
1147
1148 <pre>It couldn't get any more confusing could it? Yes it could.
1149 </pre>
1150
1151 <pre><big><strong>12. &quot;Reversed&quot; Polys
1152 </strong></big>
1153 As if reflected implementations weren't enough, there is another
1154 concept kicking around which makes the situation bizaarly confusing.
1155 The concept is reversed Polys.</pre>
1156
1157 <pre>It turns out that the reflection of good polys tend to be good polys
1158 too! That is, if G=11101 is a good poly value, then 10111 will be as
1159 well. As a consequence, it seems that every time an organization (such
1160 as CCITT) standardizes on a particularly good poly (&quot;polynomial&quot;),
1161 those in the real world can't leave the poly's reflection alone
1162 either. They just HAVE to use it. As a result, the set of &quot;standard&quot;
1163 poly's has a corresponding set of reflections, which are also in use.
1164 To avoid confusion, we will call these the &quot;reversed&quot; polys.</pre>
1165
1166 <pre> X25 standard: 1-0001-0000-0010-0001
1167 X25 reversed: 1-0000-1000-0001-0001</pre>
1168
1169 <pre> CRC16 standard: 1-1000-0000-0000-0101
1170 CRC16 reversed: 1-0100-0000-0000-0011</pre>
1171
1172 <pre>Note that here it is the entire poly that is being reflected/reversed,
1173 not just the bottom W bits. This is an important distinction. In the
1174 reflected algorithm described in the previous section, the poly used
1175 in the reflected algorithm was actually identical to that used in the
1176 non-reflected algorithm; all that had happened is that the bytes had
1177 effectively been reflected. As such, all the 16-bit/32-bit numbers in
1178 the algorithm had to be reflected. In contrast, the ENTIRE poly
1179 includes the implicit one bit at the top, and so reversing a poly is
1180 not the same as reflecting its bottom 16 or 32 bits.</pre>
1181
1182 <pre>The upshot of all this is that a reflected algorithm is not equivalent
1183 to the original algorithm with the poly reflected. Actually, this is
1184 probably less confusing than if they were duals.</pre>
1185
1186 <pre>If all this seems a bit unclear, don't worry, because we're going to
1187 sort it all out &quot;real soon now&quot;. Just one more section to go before
1188 that.
1189 </pre>
1190
1191 <pre><strong><big>13. Initial and Final Values
1192 </big></strong>
1193 In addition to the complexity already seen, CRC algorithms differ from
1194 each other in two other regards:</pre>
1195
1196 <pre> * The initial value of the register.</pre>
1197
1198 <pre> * The value to be XORed with the final register value.</pre>
1199
1200 <pre>For example, the &quot;CRC32&quot; algorithm initializes its register to
1201 FFFFFFFF and XORs the final register value with FFFFFFFF.</pre>
1202
1203 <pre>Most CRC algorithms initialize their register to zero. However, some
1204 initialize it to a non-zero value. In theory (i.e. with no assumptions
1205 about the message), the initial value has no affect on the strength of
1206 the CRC algorithm, the initial value merely providing a fixed starting
1207 point from which the register value can progress. However, in
1208 practice, some messages are more likely than others, and it is wise to
1209 initialize the CRC algorithm register to a value that does not have
1210 &quot;blind spots&quot; that are likely to occur in practice. By &quot;blind spot&quot; is
1211 meant a sequence of message bytes that do not result in the register
1212 changing its value. In particular, any CRC algorithm that initializes
1213 its register to zero will have a blind spot of zero when it starts up
1214 and will be unable to &quot;count&quot; a leading run of zero bytes. As a
1215 leading run of zero bytes is quite common in real messages, it is wise
1216 to initialize the algorithm register to a non-zero value.
1217 </pre>
1218
1219 <pre><big><strong>14. Defining Algorithms Absolutely
1220 </strong></big>
1221 At this point we have covered all the different aspects of
1222 table-driven CRC algorithms. As there are so many variations on these
1223 algorithms, it is worth trying to establish a nomenclature for them.
1224 This section attempts to do that.</pre>
1225
1226 <pre>We have seen that CRC algorithms vary in:</pre>
1227
1228 <pre> * Width of the poly (polynomial).
1229 * Value of the poly.
1230 * Initial value for the register.
1231 * Whether the bits of each byte are reflected before being processed.
1232 * Whether the algorithm feeds input bytes through the register or
1233 xors them with a byte from one end and then straight into the table.
1234 * Whether the final register value should be reversed (as in reflected
1235 versions).
1236 * Value to XOR with the final register value.</pre>
1237
1238 <pre>In order to be able to talk about particular CRC algorithms, we need
1239 to able to define them more precisely than this. For this reason, the
1240 next section attempts to provide a well-defined parameterized model
1241 for CRC algorithms. To refer to a particular algorithm, we need then
1242 simply specify the algorithm in terms of parameters to the model.
1243 </pre>
1244
1245 <pre><big><strong>15. A Parameterized Model For CRC Algorithms
1246 </strong></big>
1247 In this section we define a precise parameterized model CRC algorithm
1248 which, for want of a better name, we will call the &quot;Rocksoft^tm Model
1249 CRC Algorithm&quot; (and why not? Rocksoft^tm could do with some free
1250 advertising :-).</pre>
1251
1252 <pre>The most important aspect of the model algorithm is that it focusses
1253 exclusively on functionality, ignoring all implementation details. The
1254 aim of the exercise is to construct a way of referring precisely to
1255 particular CRC algorithms, regardless of how confusingly they are
1256 implemented. To this end, the model must be as simple and precise as
1257 possible, with as little confusion as possible.</pre>
1258
1259 <pre>The Rocksoft^tm Model CRC Algorithm is based essentially on the DIRECT
1260 TABLE ALGORITHM specified earlier. However, the algorithm has to be
1261 further parameterized to enable it to behave in the same way as some
1262 of the messier algorithms out in the real world.</pre>
1263
1264 <pre>To enable the algorithm to behave like reflected algorithms, we
1265 provide a boolean option to reflect the input bytes, and a boolean
1266 option to specify whether to reflect the output checksum value. By
1267 framing reflection as an input/output transformation, we avoid the
1268 confusion of having to mentally map the parameters of reflected and
1269 non-reflected algorithms.</pre>
1270
1271 <pre>An extra parameter allows the algorithm's register to be initialized
1272 to a particular value. A further parameter is XORed with the final
1273 value before it is returned.</pre>
1274
1275 <pre>By putting all these pieces together we end up with the parameters of
1276 the algorithm:</pre>
1277
1278 <pre> <strong>NAME: </strong>This is a name given to the algorithm. A string value.</pre>
1279
1280 <pre> <strong>WIDTH:</strong> This is the width of the algorithm expressed in bits. This
1281 is one less than the width of the Poly.</pre>
1282
1283 <pre> <strong>POLY:</strong> This parameter is the poly. This is a binary value that
1284 should be specified as a hexadecimal number. The top bit of the
1285 poly should be omitted. For example, if the poly is 10110, you
1286 should specify 06. An important aspect of this parameter is that it
1287 represents the unreflected poly; the bottom bit of this parameter
1288 is always the LSB of the divisor during the division regardless of
1289 whether the algorithm being modelled is reflected.</pre>
1290
1291 <pre> <strong>INIT:</strong> This parameter specifies the initial value of the register
1292 when the algorithm starts. This is the value that is to be assigned
1293 to the register in the direct table algorithm. In the table
1294 algorithm, we may think of the register always commencing with the
1295 value zero, and this value being XORed into the register after the
1296 N'th bit iteration. This parameter should be specified as a
1297 hexadecimal number.</pre>
1298
1299 <pre> <strong>REFIN:</strong> This is a boolean parameter. If it is FALSE, input bytes are
1300 processed with bit 7 being treated as the most significant bit
1301 (MSB) and bit 0 being treated as the least significant bit. If this
1302 parameter is FALSE, each byte is reflected before being processed.</pre>
1303
1304 <pre> <strong>REFOUT:</strong> This is a boolean parameter. If it is set to FALSE, the
1305 final value in the register is fed into the XOROUT stage directly,
1306 otherwise, if this parameter is TRUE, the final register value is
1307 reflected first.</pre>
1308
1309 <pre> <strong>XOROUT:</strong> This is an W-bit value that should be specified as a
1310 hexadecimal number. It is XORed to the final register value (after
1311 the REFOUT) stage before the value is returned as the official
1312 checksum.</pre>
1313
1314 <pre> <strong>CHECK</strong>: This field is not strictly part of the definition, and, in
1315 the event of an inconsistency between this field and the other
1316 field, the other fields take precedence. This field is a check
1317 value that can be used as a weak validator of implementations of
1318 the algorithm. The field contains the checksum obtained when the
1319 ASCII string &quot;123456789&quot; is fed through the specified algorithm
1320 (i.e. 313233... (hexadecimal)).</pre>
1321
1322 <pre>With these parameters defined, the model can now be used to specify a
1323 particular CRC algorithm exactly. Here is an example specification for
1324 a popular form of the CRC-16 algorithm.</pre>
1325
1326 <pre> Name : &quot;CRC-16&quot;
1327 Width : 16
1328 Poly : 8005
1329 Init : 0000
1330 RefIn : True
1331 RefOut : True
1332 XorOut : 0000
1333 Check : BB3D
1334 </pre>
1335
1336 <pre><big><strong>16. A Catalog of Parameter Sets for Standards
1337 </strong></big>
1338 At this point, I would like to give a list of the specifications for
1339 commonly used CRC algorithms. However, most of the algorithms that I
1340 have come into contact with so far are specified in such a vague way
1341 that this has not been possible. What I can provide is a list of polys
1342 for various CRC standards I have heard of:</pre>
1343
1344 <pre> X25 standard : 1021 [CRC-CCITT, ADCCP, SDLC/HDLC]
1345 X25 reversed : 0811</pre>
1346
1347 <pre> CRC16 standard : 8005
1348 CRC16 reversed : 4003 [LHA]</pre>
1349
1350 <pre> CRC32 : 04C11DB7 [PKZIP, AUTODIN II, Ethernet, FDDI]</pre>
1351
1352 <pre>I would be interested in hearing from anyone out there who can tie
1353 down the complete set of model parameters for any of these standards.</pre>
1354
1355 <pre>However, a program that was kicking around seemed to imply the
1356 following specifications. Can anyone confirm or deny them (or provide
1357 the check values (which I couldn't be bothered coding up and
1358 calculating)).</pre>
1359
1360 <pre> Name : &quot;CRC-16/CITT&quot;
1361 Width : 16
1362 Poly : 1021
1363 Init : FFFF
1364 RefIn : False
1365 RefOut : False
1366 XorOut : 0000
1367 Check : ?
1368 </pre>
1369
1370 <pre> Name : &quot;XMODEM&quot;
1371 Width : 16
1372 Poly : 8408
1373 Init : 0000
1374 RefIn : True
1375 RefOut : True
1376 XorOut : 0000
1377 Check : ?
1378 </pre>
1379
1380 <pre> Name : &quot;ARC&quot;
1381 Width : 16
1382 Poly : 8005
1383 Init : 0000
1384 RefIn : True
1385 RefOut : True
1386 XorOut : 0000
1387 Check : ?</pre>
1388
1389 <pre>Here is the specification for the CRC-32 algorithm which is reportedly
1390 used in PKZip, AUTODIN II, Ethernet, and FDDI.</pre>
1391
1392 <pre> Name : &quot;CRC-32&quot;
1393 Width : 32
1394 Poly : 04C11DB7
1395 Init : FFFFFFFF
1396 RefIn : True
1397 RefOut : True
1398 XorOut : FFFFFFFF
1399 Check : CBF43926
1400 </pre>
1401
1402 <pre><big><strong>17. An Implementation of the Model Algorithm
1403 </strong></big>
1404 Here is an implementation of the model algorithm in the C programming
1405 language. The implementation consists of a header file (.h) and an
1406 implementation file (.c). If you're reading this document in a
1407 sequential scroller, you can skip this code by searching for the
1408 string &quot;Roll Your Own&quot;.</pre>
1409
1410 <pre>To ensure that the following code is working, configure it for the
1411 CRC-16 and CRC-32 algorithms given above and ensure that they produce
1412 the specified &quot;check&quot; checksum when fed the test string &quot;123456789&quot;
1413 (see earlier).</pre>
1414
1415 <p>&nbsp;</p>
1416
1417 <p>&nbsp;</p>
1418
1419 <pre>/******************************************************************************/
1420 /* Start of crcmodel.h */
1421 /******************************************************************************/
1422 /* */
1423 /* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
1424 /* Date : 3 June 1993. */
1425 /* Status : Public domain. */
1426 /* */
1427 /* Description : This is the header (.h) file for the reference */
1428 /* implementation of the Rocksoft^tm Model CRC Algorithm. For more */
1429 /* information on the Rocksoft^tm Model CRC Algorithm, see the document */
1430 /* titled &quot;A Painless Guide to CRC Error Detection Algorithms&quot; by Ross */
1431 /* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */
1432 /* &quot;ftp.adelaide.edu.au/pub/rocksoft&quot;. */
1433 /* */
1434 /* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
1435 /* */
1436 /******************************************************************************/
1437 /* */
1438 /* How to Use This Package */
1439 /* ----------------------- */
1440 /* Step 1: Declare a variable of type cm_t. Declare another variable */
1441 /* (p_cm say) of type p_cm_t and initialize it to point to the first */
1442 /* variable (e.g. p_cm_t p_cm = &amp;cm_t). */
1443 /* */
1444 /* Step 2: Assign values to the parameter fields of the structure. */
1445 /* If you don't know what to assign, see the document cited earlier. */
1446 /* For example: */
1447 /* p_cm-&gt;cm_width = 16; */
1448 /* p_cm-&gt;cm_poly = 0x8005L; */
1449 /* p_cm-&gt;cm_init = 0L; */
1450 /* p_cm-&gt;cm_refin = TRUE; */
1451 /* p_cm-&gt;cm_refot = TRUE; */
1452 /* p_cm-&gt;cm_xorot = 0L; */
1453 /* Note: Poly is specified without its top bit (18005 becomes 8005). */
1454 /* Note: Width is one bit less than the raw poly width. */
1455 /* */
1456 /* Step 3: Initialize the instance with a call cm_ini(p_cm); */
1457 /* */
1458 /* Step 4: Process zero or more message bytes by placing zero or more */
1459 /* successive calls to cm_nxt. Example: cm_nxt(p_cm,ch); */
1460 /* */
1461 /* Step 5: Extract the CRC value at any time by calling crc = cm_crc(p_cm); */
1462 /* If the CRC is a 16-bit value, it will be in the bottom 16 bits. */
1463 /* */
1464 /******************************************************************************/
1465 /* */
1466 /* Design Notes */
1467 /* ------------ */
1468 /* PORTABILITY: This package has been coded very conservatively so that */
1469 /* it will run on as many machines as possible. For example, all external */
1470 /* identifiers have been restricted to 6 characters and all internal ones to */
1471 /* 8 characters. The prefix cm (for Crc Model) is used as an attempt to avoid */
1472 /* namespace collisions. This package is endian independent. */
1473 /* */
1474 /* EFFICIENCY: This package (and its interface) is not designed for */
1475 /* speed. The purpose of this package is to act as a well-defined reference */
1476 /* model for the specification of CRC algorithms. If you want speed, cook up */
1477 /* a specific table-driven implementation as described in the document cited */
1478 /* above. This package is designed for validation only; if you have found or */
1479 /* implemented a CRC algorithm and wish to describe it as a set of parameters */
1480 /* to the Rocksoft^tm Model CRC Algorithm, your CRC algorithm implementation */
1481 /* should behave identically to this package under those parameters. */
1482 /* */
1483 /******************************************************************************/</pre>
1484
1485 <pre>/* The following #ifndef encloses this entire */
1486 /* header file, rendering it indempotent. */
1487 #ifndef CM_DONE
1488 #define CM_DONE</pre>
1489
1490 <pre>/******************************************************************************/</pre>
1491
1492 <pre>/* The following definitions are extracted from my style header file which */
1493 /* would be cumbersome to distribute with this package. The DONE_STYLE is the */
1494 /* idempotence symbol used in my style header file. */</pre>
1495
1496 <pre>#ifndef DONE_STYLE</pre>
1497
1498 <pre>typedef unsigned long ulong;
1499 typedef unsigned bool;
1500 typedef unsigned char * p_ubyte_;</pre>
1501
1502 <pre>#ifndef TRUE
1503 #define FALSE 0
1504 #define TRUE 1
1505 #endif</pre>
1506
1507 <pre>/* Change to the second definition if you don't have prototypes. */
1508 #define P_(A) A
1509 /* #define P_(A) () */</pre>
1510
1511 <pre>/* Uncomment this definition if you don't have void. */
1512 /* typedef int void; */</pre>
1513
1514 <pre>#endif</pre>
1515
1516 <pre>/******************************************************************************/</pre>
1517
1518 <pre>/* CRC Model Abstract Type */
1519 /* ----------------------- */
1520 /* The following type stores the context of an executing instance of the */
1521 /* model algorithm. Most of the fields are model parameters which must be */
1522 /* set before the first initializing call to cm_ini. */
1523 typedef struct
1524 {
1525 int cm_width; /* Parameter: Width in bits [8,32]. */
1526 ulong cm_poly; /* Parameter: The algorithm's polynomial. */
1527 ulong cm_init; /* Parameter: Initial register value. */
1528 bool cm_refin; /* Parameter: Reflect input bytes? */
1529 bool cm_refot; /* Parameter: Reflect output CRC? */
1530 ulong cm_xorot; /* Parameter: XOR this to output CRC. */</pre>
1531
1532 <pre> ulong cm_reg; /* Context: Context during execution. */
1533 } cm_t;
1534 typedef cm_t *p_cm_t;</pre>
1535
1536 <pre>/******************************************************************************/</pre>
1537
1538 <pre>/* Functions That Implement The Model */
1539 /* ---------------------------------- */
1540 /* The following functions animate the cm_t abstraction. */</pre>
1541
1542 <pre>void cm_ini P_((p_cm_t p_cm));
1543 /* Initializes the argument CRC model instance. */
1544 /* All parameter fields must be set before calling this. */</pre>
1545
1546 <pre>void cm_nxt P_((p_cm_t p_cm,int ch));
1547 /* Processes a single message byte [0,255]. */</pre>
1548
1549 <pre>void cm_blk P_((p_cm_t p_cm,p_ubyte_ blk_adr,ulong blk_len));
1550 /* Processes a block of message bytes. */</pre>
1551
1552 <pre>ulong cm_crc P_((p_cm_t p_cm));
1553 /* Returns the CRC value for the message bytes processed so far. */</pre>
1554
1555 <pre>/******************************************************************************/</pre>
1556
1557 <pre>/* Functions For Table Calculation */
1558 /* ------------------------------- */
1559 /* The following function can be used to calculate a CRC lookup table. */
1560 /* It can also be used at run-time to create or check static tables. */</pre>
1561
1562 <pre>ulong cm_tab P_((p_cm_t p_cm,int index));
1563 /* Returns the i'th entry for the lookup table for the specified algorithm. */
1564 /* The function examines the fields cm_width, cm_poly, cm_refin, and the */
1565 /* argument table index in the range [0,255] and returns the table entry in */
1566 /* the bottom cm_width bytes of the return value. */</pre>
1567
1568 <pre>/******************************************************************************/</pre>
1569
1570 <pre>/* End of the header file idempotence #ifndef */
1571 #endif</pre>
1572
1573 <pre>/******************************************************************************/
1574 /* End of crcmodel.h */
1575 /******************************************************************************/
1576 </pre>
1577
1578 <pre>/******************************************************************************/
1579 /* Start of crcmodel.c */
1580 /******************************************************************************/
1581 /* */
1582 /* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
1583 /* Date : 3 June 1993. */
1584 /* Status : Public domain. */
1585 /* */
1586 /* Description : This is the implementation (.c) file for the reference */
1587 /* implementation of the Rocksoft^tm Model CRC Algorithm. For more */
1588 /* information on the Rocksoft^tm Model CRC Algorithm, see the document */
1589 /* titled &quot;A Painless Guide to CRC Error Detection Algorithms&quot; by Ross */
1590 /* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */
1591 /* &quot;ftp.adelaide.edu.au/pub/rocksoft&quot;. */
1592 /* */
1593 /* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
1594 /* */
1595 /******************************************************************************/
1596 /* */
1597 /* Implementation Notes */
1598 /* -------------------- */
1599 /* To avoid inconsistencies, the specification of each function is not echoed */
1600 /* here. See the header file for a description of these functions. */
1601 /* This package is light on checking because I want to keep it short and */
1602 /* simple and portable (i.e. it would be too messy to distribute my entire */
1603 /* C culture (e.g. assertions package) with this package. */
1604 /* */
1605 /******************************************************************************/</pre>
1606
1607 <pre>#include &quot;crcmodel.h&quot;</pre>
1608
1609 <pre>/******************************************************************************/</pre>
1610
1611 <pre>/* The following definitions make the code more readable. */</pre>
1612
1613 <pre>#define BITMASK(X) (1L &lt;&lt; (X))
1614 #define MASK32 0xFFFFFFFFL
1615 #define LOCAL static</pre>
1616
1617 <pre>/******************************************************************************/</pre>
1618
1619 <pre>LOCAL ulong reflect P_((ulong v,int b));
1620 LOCAL ulong reflect (v,b)
1621 /* Returns the value v with the bottom b [0,32] bits reflected. */
1622 /* Example: reflect(0x3e23L,3) == 0x3e26 */
1623 ulong v;
1624 int b;
1625 {
1626 int i;
1627 ulong t = v;
1628 for (i=0; i&lt;b; i++)
1629 {
1630 if (t &amp; 1L)
1631 v|= BITMASK((b-1)-i);
1632 else
1633 v&amp;= ~BITMASK((b-1)-i);
1634 t&gt;&gt;=1;
1635 }
1636 return v;
1637 }</pre>
1638
1639 <pre>/******************************************************************************/</pre>
1640
1641 <pre>LOCAL ulong widmask P_((p_cm_t));
1642 LOCAL ulong widmask (p_cm)
1643 /* Returns a longword whose value is (2^p_cm-&gt;cm_width)-1. */
1644 /* The trick is to do this portably (e.g. without doing &lt;&lt;32). */
1645 p_cm_t p_cm;
1646 {
1647 return (((1L&lt;&lt;(p_cm-&gt;cm_width-1))-1L)&lt;&lt;1)|1L;
1648 }</pre>
1649
1650 <pre>/******************************************************************************/</pre>
1651
1652 <pre>void cm_ini (p_cm)
1653 p_cm_t p_cm;
1654 {
1655 p_cm-&gt;cm_reg = p_cm-&gt;cm_init;
1656 }</pre>
1657
1658 <pre>/******************************************************************************/</pre>
1659
1660 <pre>void cm_nxt (p_cm,ch)
1661 p_cm_t p_cm;
1662 int ch;
1663 {
1664 int i;
1665 ulong uch = (ulong) ch;
1666 ulong topbit = BITMASK(p_cm-&gt;cm_width-1);</pre>
1667
1668 <pre> if (p_cm-&gt;cm_refin) uch = reflect(uch,8);
1669 p_cm-&gt;cm_reg ^= (uch &lt;&lt; (p_cm-&gt;cm_width-8));
1670 for (i=0; i&lt;8; i++)
1671 {
1672 if (p_cm-&gt;cm_reg &amp; topbit)
1673 p_cm-&gt;cm_reg = (p_cm-&gt;cm_reg &lt;&lt; 1) ^ p_cm-&gt;cm_poly;
1674 else
1675 p_cm-&gt;cm_reg &lt;&lt;= 1;
1676 p_cm-&gt;cm_reg &amp;= widmask(p_cm);
1677 }
1678 }</pre>
1679
1680 <pre>/******************************************************************************/</pre>
1681
1682 <pre>void cm_blk (p_cm,blk_adr,blk_len)
1683 p_cm_t p_cm;
1684 p_ubyte_ blk_adr;
1685 ulong blk_len;
1686 {
1687 while (blk_len--) cm_nxt(p_cm,*blk_adr++);
1688 }</pre>
1689
1690 <pre>/******************************************************************************/</pre>
1691
1692 <pre>ulong cm_crc (p_cm)
1693 p_cm_t p_cm;
1694 {
1695 if (p_cm-&gt;cm_refot)
1696 return p_cm-&gt;cm_xorot ^ reflect(p_cm-&gt;cm_reg,p_cm-&gt;cm_width);
1697 else
1698 return p_cm-&gt;cm_xorot ^ p_cm-&gt;cm_reg;
1699 }</pre>
1700
1701 <pre>/******************************************************************************/</pre>
1702
1703 <pre>ulong cm_tab (p_cm,index)
1704 p_cm_t p_cm;
1705 int index;
1706 {
1707 int i;
1708 ulong r;
1709 ulong topbit = BITMASK(p_cm-&gt;cm_width-1);
1710 ulong inbyte = (ulong) index;</pre>
1711
1712 <pre> if (p_cm-&gt;cm_refin) inbyte = reflect(inbyte,8);
1713 r = inbyte &lt;&lt; (p_cm-&gt;cm_width-8);
1714 for (i=0; i&lt;8; i++)
1715 if (r &amp; topbit)
1716 r = (r &lt;&lt; 1) ^ p_cm-&gt;cm_poly;
1717 else
1718 r&lt;&lt;=1;
1719 if (p_cm-&gt;cm_refin) r = reflect(r,p_cm-&gt;cm_width);
1720 return r &amp; widmask(p_cm);
1721 }</pre>
1722
1723 <pre>/******************************************************************************/
1724 /* End of crcmodel.c */
1725 /******************************************************************************/
1726 </pre>
1727
1728 <pre><big><strong>18. Roll Your Own Table-Driven Implementation
1729 </strong></big>
1730 Despite all the fuss I've made about understanding and defining CRC
1731 algorithms, the mechanics of their high-speed implementation remains
1732 trivial. There are really only two forms: normal and reflected. Normal
1733 shifts to the left and covers the case of algorithms with Refin=FALSE
1734 and Refot=FALSE. Reflected shifts to the right and covers algorithms
1735 with both those parameters true. (If you want one parameter true and
1736 the other false, you'll have to figure it out for yourself!) The
1737 polynomial is embedded in the lookup table (to be discussed). The
1738 other parameters, Init and XorOt can be coded as macros. Here is the
1739 32-bit normal form (the 16-bit form is similar).</pre>
1740
1741 <pre> unsigned long crc_normal ();
1742 unsigned long crc_normal (blk_adr,blk_len)
1743 unsigned char *blk_adr;
1744 unsigned long blk_len;
1745 {
1746 unsigned long crc = INIT;
1747 while (blk_len--)
1748 crc = crctable[((crc&gt;&gt;24) ^ *blk_adr++) &amp; 0xFFL] ^ (crc &lt;&lt; 8);
1749 return crc ^ XOROT;
1750 }</pre>
1751
1752 <pre>Here is the reflected form:</pre>
1753
1754 <pre> unsigned long crc_reflected ();
1755 unsigned long crc_reflected (blk_adr,blk_len)
1756 unsigned char *blk_adr;
1757 unsigned long blk_len;
1758 {
1759 unsigned long crc = INIT_REFLECTED;
1760 while (blk_len--)
1761 crc = crctable[(crc ^ *blk_adr++) &amp; 0xFFL] ^ (crc &gt;&gt; 8));
1762 return crc ^ XOROT;
1763 }</pre>
1764
1765 <pre>Note: I have carefully checked the above two code fragments, but I
1766 haven't actually compiled or tested them. This shouldn't matter to
1767 you, as, no matter WHAT you code, you will always be able to tell if
1768 you have got it right by running whatever you have created against the
1769 reference model given earlier. The code fragments above are really
1770 just a rough guide. The reference model is the definitive guide.</pre>
1771
1772 <pre>Note: If you don't care much about speed, just use the reference model
1773 code!
1774 </pre>
1775
1776 <pre><big><strong>19. Generating A Lookup Table
1777 </strong></big>
1778 The only component missing from the normal and reversed code fragments
1779 in the previous section is the lookup table. The lookup table can be
1780 computed at run time using the cm_tab function of the model package
1781 given earlier, or can be pre-computed and inserted into the C program.
1782 In either case, it should be noted that the lookup table depends only
1783 on the POLY and RefIn (and RefOt) parameters. Basically, the
1784 polynomial determines the table, but you can generate a reflected
1785 table too if you want to use the reflected form above.</pre>
1786
1787 <pre>The following program generates any desired 16-bit or 32-bit lookup
1788 table. Skip to the word &quot;Summary&quot; if you want to skip over this code.
1789
1790 </pre>
1791
1792 <pre>/******************************************************************************/
1793 /* Start of crctable.c */
1794 /******************************************************************************/
1795 /* */
1796 /* Author : Ross Williams (ross@guest.adelaide.edu.au.). */
1797 /* Date : 3 June 1993. */
1798 /* Version : 1.0. */
1799 /* Status : Public domain. */
1800 /* */
1801 /* Description : This program writes a CRC lookup table (suitable for */
1802 /* inclusion in a C program) to a designated output file. The program can be */
1803 /* statically configured to produce any table covered by the Rocksoft^tm */
1804 /* Model CRC Algorithm. For more information on the Rocksoft^tm Model CRC */
1805 /* Algorithm, see the document titled &quot;A Painless Guide to CRC Error */
1806 /* Detection Algorithms&quot; by Ross Williams (ross@guest.adelaide.edu.au.). This */
1807 /* document is likely to be in &quot;ftp.adelaide.edu.au/pub/rocksoft&quot;. */
1808 /* */
1809 /* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */
1810 /* */
1811 /******************************************************************************/</pre>
1812
1813 <pre>#include &lt;stdio.h&gt;
1814 #include &lt;stdlib.h&gt;
1815 #include &quot;crcmodel.h&quot;</pre>
1816
1817 <pre>/******************************************************************************/</pre>
1818
1819 <pre>/* TABLE PARAMETERS */
1820 /* ================ */
1821 /* The following parameters entirely determine the table to be generated. You */
1822 /* should need to modify only the definitions in this section before running */
1823 /* this program. */
1824 /* */
1825 /* TB_FILE is the name of the output file. */
1826 /* TB_WIDTH is the table width in bytes (either 2 or 4). */
1827 /* TB_POLY is the &quot;polynomial&quot;, which must be TB_WIDTH bytes wide. */
1828 /* TB_REVER indicates whether the table is to be reversed (reflected). */
1829 /* */
1830 /* Example: */
1831 /* */
1832 /* #define TB_FILE &quot;crctable.out&quot; */
1833 /* #define TB_WIDTH 2 */
1834 /* #define TB_POLY 0x8005L */
1835 /* #define TB_REVER TRUE */</pre>
1836
1837 <pre>#define TB_FILE &quot;crctable.out&quot;
1838 #define TB_WIDTH 4
1839 #define TB_POLY 0x04C11DB7L
1840 #define TB_REVER TRUE</pre>
1841
1842 <pre>/******************************************************************************/</pre>
1843
1844 <pre>/* Miscellaneous definitions. */</pre>
1845
1846 <pre>#define LOCAL static
1847 FILE *outfile;
1848 #define WR(X) fprintf(outfile,(X))
1849 #define WP(X,Y) fprintf(outfile,(X),(Y))</pre>
1850
1851 <pre>/******************************************************************************/</pre>
1852
1853 <pre>LOCAL void chk_err P_((char *));
1854 LOCAL void chk_err (mess)
1855 /* If mess is non-empty, write it out and abort. Otherwise, check the error */
1856 /* status of outfile and abort if an error has occurred. */
1857 char *mess;
1858 {
1859 if (mess[0] != 0 ) {printf(&quot;%s\n&quot;,mess); exit(EXIT_FAILURE);}
1860 if (ferror(outfile)) {perror(&quot;chk_err&quot;); exit(EXIT_FAILURE);}
1861 }</pre>
1862
1863 <pre>/******************************************************************************/</pre>
1864
1865 <pre>LOCAL void chkparam P_((void));
1866 LOCAL void chkparam ()
1867 {
1868 if ((TB_WIDTH != 2) &amp;&amp; (TB_WIDTH != 4))
1869 chk_err(&quot;chkparam: Width parameter is illegal.&quot;);
1870 if ((TB_WIDTH == 2) &amp;&amp; (TB_POLY &amp; 0xFFFF0000L))
1871 chk_err(&quot;chkparam: Poly parameter is too wide.&quot;);
1872 if ((TB_REVER != FALSE) &amp;&amp; (TB_REVER != TRUE))
1873 chk_err(&quot;chkparam: Reverse parameter is not boolean.&quot;);
1874 }</pre>
1875
1876 <pre>/******************************************************************************/</pre>
1877
1878 <pre>LOCAL void gentable P_((void));
1879 LOCAL void gentable ()
1880 {
1881 WR(&quot;/*****************************************************************/\n&quot;);
1882 WR(&quot;/* */\n&quot;);
1883 WR(&quot;/* CRC LOOKUP TABLE */\n&quot;);
1884 WR(&quot;/* ================ */\n&quot;);
1885 WR(&quot;/* The following CRC lookup table was generated automagically */\n&quot;);
1886 WR(&quot;/* by the Rocksoft^tm Model CRC Algorithm Table Generation */\n&quot;);
1887 WR(&quot;/* Program V1.0 using the following model parameters: */\n&quot;);
1888 WR(&quot;/* */\n&quot;);
1889 WP(&quot;/* Width : %1lu bytes. */\n&quot;,
1890 (ulong) TB_WIDTH);
1891 if (TB_WIDTH == 2)
1892 WP(&quot;/* Poly : 0x%04lX */\n&quot;,
1893 (ulong) TB_POLY);
1894 else
1895 WP(&quot;/* Poly : 0x%08lXL */\n&quot;,
1896 (ulong) TB_POLY);
1897 if (TB_REVER)
1898 WR(&quot;/* Reverse : TRUE. */\n&quot;);
1899 else
1900 WR(&quot;/* Reverse : FALSE. */\n&quot;);
1901 WR(&quot;/* */\n&quot;);
1902 WR(&quot;/* For more information on the Rocksoft^tm Model CRC Algorithm, */\n&quot;);
1903 WR(&quot;/* see the document titled \&quot;A Painless Guide to CRC Error */\n&quot;);
1904 WR(&quot;/* Detection Algorithms\&quot; by Ross Williams */\n&quot;);
1905 WR(&quot;/* (ross@guest.adelaide.edu.au.). This document is likely to be */\n&quot;);
1906 WR(&quot;/* in the FTP archive \&quot;ftp.adelaide.edu.au/pub/rocksoft\&quot;. */\n&quot;);
1907 WR(&quot;/* */\n&quot;);
1908 WR(&quot;/*****************************************************************/\n&quot;);
1909 WR(&quot;\n&quot;);
1910 switch (TB_WIDTH)
1911 {
1912 case 2: WR(&quot;unsigned short crctable[256] =\n{\n&quot;); break;
1913 case 4: WR(&quot;unsigned long crctable[256] =\n{\n&quot;); break;
1914 default: chk_err(&quot;gentable: TB_WIDTH is invalid.&quot;);
1915 }
1916 chk_err(&quot;&quot;);</pre>
1917
1918 <pre> {
1919 int i;
1920 cm_t cm;
1921 char *form = (TB_WIDTH==2) ? &quot;0x%04lX&quot; : &quot;0x%08lXL&quot;;
1922 int perline = (TB_WIDTH==2) ? 8 : 4;</pre>
1923
1924 <pre> cm.cm_width = TB_WIDTH*8;
1925 cm.cm_poly = TB_POLY;
1926 cm.cm_refin = TB_REVER;</pre>
1927
1928 <pre> for (i=0; i&lt;256; i++)
1929 {
1930 WR(&quot; &quot;);
1931 WP(form,(ulong) cm_tab(&amp;cm,i));
1932 if (i != 255) WR(&quot;,&quot;);
1933 if (((i+1) % perline) == 0) WR(&quot;\n&quot;);
1934 chk_err(&quot;&quot;);
1935 }</pre>
1936
1937 <pre> WR(&quot;};\n&quot;);
1938 WR(&quot;\n&quot;);
1939 WR(&quot;/*****************************************************************/\n&quot;);
1940 WR(&quot;/* End of CRC Lookup Table */\n&quot;);
1941 WR(&quot;/*****************************************************************/\n&quot;);
1942 WR(&quot;&quot;);
1943 chk_err(&quot;&quot;);
1944 }
1945 }</pre>
1946
1947 <pre>/******************************************************************************/</pre>
1948
1949 <pre>main ()
1950 {
1951 printf(&quot;\n&quot;);
1952 printf(&quot;Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0\n&quot;);
1953 printf(&quot;-------------------------------------------------------------\n&quot;);
1954 printf(&quot;Output file is \&quot;%s\&quot;.\n&quot;,TB_FILE);
1955 chkparam();
1956 outfile = fopen(TB_FILE,&quot;w&quot;); chk_err(&quot;&quot;);
1957 gentable();
1958 if (fclose(outfile) != 0)
1959 chk_err(&quot;main: Couldn't close output file.&quot;);
1960 printf(&quot;\nSUCCESS: The table has been successfully written.\n&quot;);
1961 }</pre>
1962
1963 <pre>/******************************************************************************/
1964 /* End of crctable.c */
1965 /******************************************************************************/</pre>
1966
1967 <pre><big><strong>20. Summary
1968 </strong></big>
1969 This document has provided a detailed explanation of CRC algorithms
1970 explaining their theory and stepping through increasingly
1971 sophisticated implementations ranging from simple bit shifting through
1972 to byte-at-a-time table-driven implementations. The various
1973 implementations of different CRC algorithms that make them confusing
1974 to deal with have been explained. A parameterized model algorithm has
1975 been described that can be used to precisely define a particular CRC
1976 algorithm, and a reference implementation provided. Finally, a program
1977 to generate CRC tables has been provided.</pre>
1978
1979 <pre><big><strong>21. Corrections
1980 </strong></big>
1981 If you think that any part of this document is unclear or incorrect,
1982 or have any other information, or suggestions on how this document
1983 could be improved, please context the author. In particular, I would
1984 like to hear from anyone who can provide Rocksoft^tm Model CRC
1985 Algorithm parameters for standard algorithms out there.</pre>
1986
1987 <p>&nbsp;</p>
1988
1989 <pre><big><strong>A. Glossary
1990 </strong></big>
1991 CHECKSUM - A number that has been calculated as a function of some
1992 message. The literal interpretation of this word &quot;Check-Sum&quot; indicates
1993 that the function should involve simply adding up the bytes in the
1994 message. Perhaps this was what early checksums were. Today, however,
1995 although more sophisticated formulae are used, the term &quot;checksum&quot; is
1996 still used.</pre>
1997
1998 <pre>CRC - This stands for &quot;Cyclic Redundancy Code&quot;. Whereas the term
1999 &quot;checksum&quot; seems to be used to refer to any non-cryptographic checking
2000 information unit, the term &quot;CRC&quot; seems to be reserved only for
2001 algorithms that are based on the &quot;polynomial&quot; division idea.</pre>
2002
2003 <pre>G - This symbol is used in this document to represent the Poly.</pre>
2004
2005 <pre>MESSAGE - The input data being checksummed. This is usually structured
2006 as a sequence of bytes. Whether the top bit or the bottom bit of each
2007 byte is treated as the most significant or least significant is a
2008 parameter of CRC algorithms.</pre>
2009
2010 <pre>POLY - This is my friendly term for the polynomial of a CRC.</pre>
2011
2012 <pre>POLYNOMIAL - The &quot;polynomial&quot; of a CRC algorithm is simply the divisor
2013 in the division implementing the CRC algorithm.</pre>
2014
2015 <pre>REFLECT - A binary number is reflected by swapping all of its bits
2016 around the central point. For example, 1101 is the reflection of 1011.</pre>
2017
2018 <pre>ROCKSOFT^TM MODEL CRC ALGORITHM - A parameterized algorithm whose
2019 purpose is to act as a solid reference for describing CRC algorithms.
2020 Typically CRC algorithms are specified by quoting a polynomial.
2021 However, in order to construct a precise implementation, one also
2022 needs to know initialization values and so on.</pre>
2023
2024 <pre>WIDTH - The width of a CRC algorithm is the width of its polynomical
2025 minus one. For example, if the polynomial is 11010, the width would be
2026 4 bits. The width is usually set to be a multiple of 8 bits.</pre>
2027
2028 <p>&nbsp;</p>
2029
2030 <pre><big><strong>B. References
2031 </strong></big>
2032 [Griffiths87] Griffiths, G., Carlyle Stones, G., &quot;The Tea-Leaf Reader
2033 Algorithm: An Efficient Implementation of CRC-16 and CRC-32&quot;,
2034 Communications of the ACM, 30(7), pp.617-620. Comment: This paper
2035 describes a high-speed table-driven implementation of CRC algorithms.
2036 The technique seems to be a touch messy, and is superceded by the
2037 Sarwete algorithm.</pre>
2038
2039 <pre>[Knuth81] Knuth, D.E., &quot;The Art of Computer Programming&quot;, Volume 2:
2040 Seminumerical Algorithms, Section 4.6.</pre>
2041
2042 <pre>[Nelson 91] Nelson, M., &quot;The Data Compression Book&quot;, M&amp;T Books, (501
2043 Galveston Drive, Redwood City, CA 94063), 1991, ISBN: 1-55851-214-4.
2044 Comment: If you want to see a real implementation of a real 32-bit
2045 checksum algorithm, look on pages 440, and 446-448.</pre>
2046
2047 <pre>[Sarwate88] Sarwate, D.V., &quot;Computation of Cyclic Redundancy Checks
2048 via Table Look-Up&quot;, Communications of the ACM, 31(8), pp.1008-1013.
2049 Comment: This paper describes a high-speed table-driven implementation
2050 for CRC algorithms that is superior to the tea-leaf algorithm.
2051 Although this paper describes the technique used by most modern CRC
2052 implementations, I found the appendix of this paper (where all the
2053 good stuff is) difficult to understand.</pre>
2054
2055 <pre>[Tanenbaum81] Tanenbaum, A.S., &quot;Computer Networks&quot;, Prentice Hall,
2056 1981, ISBN: 0-13-164699-0. Comment: Section 3.5.3 on pages 128 to 132
2057 provides a very clear description of CRC codes. However, it does not
2058 describe table-driven implementation techniques.
2059 </pre>
2060
2061 <p>&nbsp;</p>
2062
2063 <pre><strong><big>C. References I Have Detected But Haven't Yet Sighted
2064 </big></strong>
2065 Boudreau, Steen, &quot;Cyclic Redundancy Checking by Program,&quot; AFIPS
2066 Proceedings, Vol. 39, 1971.</pre>
2067
2068 <pre>Davies, Barber, &quot;Computer Networks and Their Protocols,&quot; J. Wiley &amp;
2069 Sons, 1979.</pre>
2070
2071 <pre>Higginson, Kirstein, &quot;On the Computation of Cyclic Redundancy Checks
2072 by Program,&quot; The Computer Journal (British), Vol. 16, No. 1, Feb 1973.</pre>
2073
2074 <pre>McNamara, J. E., &quot;Technical Aspects of Data Communication,&quot; 2nd
2075 Edition, Digital Press, Bedford, Massachusetts, 1982.</pre>
2076
2077 <pre>Marton and Frambs, &quot;A Cyclic Redundancy Checking (CRC) Algorithm,&quot;
2078 Honeywell Computer Journal, Vol. 5, No. 3, 1971.</pre>
2079
2080 <pre>Nelson M., &quot;File verification using CRC&quot;, Dr Dobbs Journal, May 1992,
2081 pp.64-67.</pre>
2082
2083 <pre>Ramabadran T.V., Gaitonde S.S., &quot;A tutorial on CRC computations&quot;, IEEE
2084 Micro, Aug 1988.</pre>
2085
2086 <pre>Schwaderer W.D., &quot;CRC Calculation&quot;, April 85 PC Tech Journal,
2087 pp.118-133.</pre>
2088
2089 <pre>Ward R.K, Tabandeh M., &quot;Error Correction and Detection, A Geometric
2090 Approach&quot; The Computer Journal, Vol. 27, No. 3, 1984, pp.246-253.</pre>
2091
2092 <pre>Wecker, S., &quot;A Table-Lookup Algorithm for Software Computation of
2093 Cyclic Redundancy Check (CRC),&quot; Digital Equipment Corporation
2094 memorandum, 1974.</pre>
2095
2096 <hr>
2097 </html>

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25