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

Parent Directory | 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)

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>"Everything you wanted to know about CRC algorithms, but were afraid |

19 | to ask for fear that errors in your understanding might be detected."</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 : "Rocksoft" 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. "Reflected" Table-Driven Implementations |

57 | 12. "Reversed" 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 | "Rocksoft^tm Model CRC Algorithm". 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> <original intact message> <checksum> |

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 "random"; 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 "checksum" 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 "checksum" (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 "1559 divided by 9 is 173 with a remainder of 2".</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 "polynomial". 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 "polynomial arithmetic mod 2". 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 "polynomial |

339 | arithmetic mod 2", 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> "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 "carrying" 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."</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 "a number goes |

443 | into another number". 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 "generator polynomial" or |

521 | simply the "polynomial", 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 "poly". Just think of this number as a sort of |

526 | parrot. "Hello poly!"</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. "E=E XOR 011" and "E=E XOR 110") |

663 | This is nearly isomorphic to the "glass tumblers" 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) ["CRC-16"] |

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! <-- | | | | | <----- 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 "SIMPLE".</pre> |

745 | |

746 | <pre>This might look a bit messy, but all we are really doing is |

747 | "subtracting" 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 "active" bits) (W=32).</pre> |

773 | |

774 | <pre> 3 2 1 0 Bytes |

775 | +----+----+----+----+ |

776 | Pop! <-- | | | | | <----- Augmented message |

777 | +----+----+----+----+</pre> |

778 | |

779 | <pre> 1<------32 bits------></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 << 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 | +-----<| | | | | <----- 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 | +----->+----+----+----+----+ 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 >> 24) & 0xFF; |

903 | r = (r << 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 << 8) | *p++) ^ t[(r >> 24) & 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 << 8) | *p++) ^ t[(r >> 24) & 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<W/4; i++) r = (r << 8) ^ t[(r >> 24) & 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 | +-----<| | | | | <----- 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 | +----->+----+----+----+----+ 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> +-----<Message (non augmented) |

999 | | |

1000 | v 3 2 1 0 Bytes |

1001 | | +----+----+----+----+ |

1002 | XOR----<| | | | | |

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 | +----->+----+----+----+----+ 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<<8) ^ t[(r >> 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 "wrong end" 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. "Reflected" 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 "reflected" 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) >-----+ |

1093 | | |

1094 | Bytes 0 1 2 3 v |

1095 | +----+----+----+----+ | |

1096 | | | | | |>----XOR |

1097 | +----+----+----+----+ | |

1098 | ^ | |

1099 | | | |

1100 | XOR | |

1101 | | | |

1102 | +----+----+----+----+0 | |

1103 | +----+----+----+----+ v |

1104 | +----+----+----+----+ | |

1105 | +----+----+----+----+ | |

1106 | +----+----+----+----+ | |

1107 | +----+----+----+----+ | |

1108 | +----+----+----+----+ | |

1109 | +----+----+----+----+<-----+ |

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 "fed in the wrong end" |

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. "Reversed" 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 ("polynomial"), |

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 "standard" |

1163 | poly's has a corresponding set of reflections, which are also in use. |

1164 | To avoid confusion, we will call these the "reversed" 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 "real soon now". 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 "CRC32" 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 | "blind spots" that are likely to occur in practice. By "blind spot" 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 "count" 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 "Rocksoft^tm Model |

1249 | CRC Algorithm" (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 "123456789" 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 : "CRC-16" |

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 : "CRC-16/CITT" |

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 : "XMODEM" |

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 : "ARC" |

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 : "CRC-32" |

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 "Roll Your Own".</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 "check" checksum when fed the test string "123456789" |

1413 | (see earlier).</pre> |

1414 | |

1415 | <p> </p> |

1416 | |

1417 | <p> </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 "A Painless Guide to CRC Error Detection Algorithms" by Ross */ |

1431 | /* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */ |

1432 | /* "ftp.adelaide.edu.au/pub/rocksoft". */ |

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 = &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->cm_width = 16; */ |

1448 | /* p_cm->cm_poly = 0x8005L; */ |

1449 | /* p_cm->cm_init = 0L; */ |

1450 | /* p_cm->cm_refin = TRUE; */ |

1451 | /* p_cm->cm_refot = TRUE; */ |

1452 | /* p_cm->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 "A Painless Guide to CRC Error Detection Algorithms" by Ross */ |

1590 | /* Williams (ross@guest.adelaide.edu.au.). This document is likely to be in */ |

1591 | /* "ftp.adelaide.edu.au/pub/rocksoft". */ |

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 "crcmodel.h"</pre> |

1608 | |

1609 | <pre>/******************************************************************************/</pre> |

1610 | |

1611 | <pre>/* The following definitions make the code more readable. */</pre> |

1612 | |

1613 | <pre>#define BITMASK(X) (1L << (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<b; i++) |

1629 | { |

1630 | if (t & 1L) |

1631 | v|= BITMASK((b-1)-i); |

1632 | else |

1633 | v&= ~BITMASK((b-1)-i); |

1634 | t>>=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->cm_width)-1. */ |

1644 | /* The trick is to do this portably (e.g. without doing <<32). */ |

1645 | p_cm_t p_cm; |

1646 | { |

1647 | return (((1L<<(p_cm->cm_width-1))-1L)<<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->cm_reg = p_cm->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->cm_width-1);</pre> |

1667 | |

1668 | <pre> if (p_cm->cm_refin) uch = reflect(uch,8); |

1669 | p_cm->cm_reg ^= (uch << (p_cm->cm_width-8)); |

1670 | for (i=0; i<8; i++) |

1671 | { |

1672 | if (p_cm->cm_reg & topbit) |

1673 | p_cm->cm_reg = (p_cm->cm_reg << 1) ^ p_cm->cm_poly; |

1674 | else |

1675 | p_cm->cm_reg <<= 1; |

1676 | p_cm->cm_reg &= 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->cm_refot) |

1696 | return p_cm->cm_xorot ^ reflect(p_cm->cm_reg,p_cm->cm_width); |

1697 | else |

1698 | return p_cm->cm_xorot ^ p_cm->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->cm_width-1); |

1710 | ulong inbyte = (ulong) index;</pre> |

1711 | |

1712 | <pre> if (p_cm->cm_refin) inbyte = reflect(inbyte,8); |

1713 | r = inbyte << (p_cm->cm_width-8); |

1714 | for (i=0; i<8; i++) |

1715 | if (r & topbit) |

1716 | r = (r << 1) ^ p_cm->cm_poly; |

1717 | else |

1718 | r<<=1; |

1719 | if (p_cm->cm_refin) r = reflect(r,p_cm->cm_width); |

1720 | return r & 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>>24) ^ *blk_adr++) & 0xFFL] ^ (crc << 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++) & 0xFFL] ^ (crc >> 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 "Summary" 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 "A Painless Guide to CRC Error */ |

1806 | /* Detection Algorithms" by Ross Williams (ross@guest.adelaide.edu.au.). This */ |

1807 | /* document is likely to be in "ftp.adelaide.edu.au/pub/rocksoft". */ |

1808 | /* */ |

1809 | /* Note: Rocksoft is a trademark of Rocksoft Pty Ltd, Adelaide, Australia. */ |

1810 | /* */ |

1811 | /******************************************************************************/</pre> |

1812 | |

1813 | <pre>#include <stdio.h> |

1814 | #include <stdlib.h> |

1815 | #include "crcmodel.h"</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 "polynomial", 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 "crctable.out" */ |

1833 | /* #define TB_WIDTH 2 */ |

1834 | /* #define TB_POLY 0x8005L */ |

1835 | /* #define TB_REVER TRUE */</pre> |

1836 | |

1837 | <pre>#define TB_FILE "crctable.out" |

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("%s\n",mess); exit(EXIT_FAILURE);} |

1860 | if (ferror(outfile)) {perror("chk_err"); 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) && (TB_WIDTH != 4)) |

1869 | chk_err("chkparam: Width parameter is illegal."); |

1870 | if ((TB_WIDTH == 2) && (TB_POLY & 0xFFFF0000L)) |

1871 | chk_err("chkparam: Poly parameter is too wide."); |

1872 | if ((TB_REVER != FALSE) && (TB_REVER != TRUE)) |

1873 | chk_err("chkparam: Reverse parameter is not boolean."); |

1874 | }</pre> |

1875 | |

1876 | <pre>/******************************************************************************/</pre> |

1877 | |

1878 | <pre>LOCAL void gentable P_((void)); |

1879 | LOCAL void gentable () |

1880 | { |

1881 | WR("/*****************************************************************/\n"); |

1882 | WR("/* */\n"); |

1883 | WR("/* CRC LOOKUP TABLE */\n"); |

1884 | WR("/* ================ */\n"); |

1885 | WR("/* The following CRC lookup table was generated automagically */\n"); |

1886 | WR("/* by the Rocksoft^tm Model CRC Algorithm Table Generation */\n"); |

1887 | WR("/* Program V1.0 using the following model parameters: */\n"); |

1888 | WR("/* */\n"); |

1889 | WP("/* Width : %1lu bytes. */\n", |

1890 | (ulong) TB_WIDTH); |

1891 | if (TB_WIDTH == 2) |

1892 | WP("/* Poly : 0x%04lX */\n", |

1893 | (ulong) TB_POLY); |

1894 | else |

1895 | WP("/* Poly : 0x%08lXL */\n", |

1896 | (ulong) TB_POLY); |

1897 | if (TB_REVER) |

1898 | WR("/* Reverse : TRUE. */\n"); |

1899 | else |

1900 | WR("/* Reverse : FALSE. */\n"); |

1901 | WR("/* */\n"); |

1902 | WR("/* For more information on the Rocksoft^tm Model CRC Algorithm, */\n"); |

1903 | WR("/* see the document titled \"A Painless Guide to CRC Error */\n"); |

1904 | WR("/* Detection Algorithms\" by Ross Williams */\n"); |

1905 | WR("/* (ross@guest.adelaide.edu.au.). This document is likely to be */\n"); |

1906 | WR("/* in the FTP archive \"ftp.adelaide.edu.au/pub/rocksoft\". */\n"); |

1907 | WR("/* */\n"); |

1908 | WR("/*****************************************************************/\n"); |

1909 | WR("\n"); |

1910 | switch (TB_WIDTH) |

1911 | { |

1912 | case 2: WR("unsigned short crctable[256] =\n{\n"); break; |

1913 | case 4: WR("unsigned long crctable[256] =\n{\n"); break; |

1914 | default: chk_err("gentable: TB_WIDTH is invalid."); |

1915 | } |

1916 | chk_err("");</pre> |

1917 | |

1918 | <pre> { |

1919 | int i; |

1920 | cm_t cm; |

1921 | char *form = (TB_WIDTH==2) ? "0x%04lX" : "0x%08lXL"; |

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<256; i++) |

1929 | { |

1930 | WR(" "); |

1931 | WP(form,(ulong) cm_tab(&cm,i)); |

1932 | if (i != 255) WR(","); |

1933 | if (((i+1) % perline) == 0) WR("\n"); |

1934 | chk_err(""); |

1935 | }</pre> |

1936 | |

1937 | <pre> WR("};\n"); |

1938 | WR("\n"); |

1939 | WR("/*****************************************************************/\n"); |

1940 | WR("/* End of CRC Lookup Table */\n"); |

1941 | WR("/*****************************************************************/\n"); |

1942 | WR(""); |

1943 | chk_err(""); |

1944 | } |

1945 | }</pre> |

1946 | |

1947 | <pre>/******************************************************************************/</pre> |

1948 | |

1949 | <pre>main () |

1950 | { |

1951 | printf("\n"); |

1952 | printf("Rocksoft^tm Model CRC Algorithm Table Generation Program V1.0\n"); |

1953 | printf("-------------------------------------------------------------\n"); |

1954 | printf("Output file is \"%s\".\n",TB_FILE); |

1955 | chkparam(); |

1956 | outfile = fopen(TB_FILE,"w"); chk_err(""); |

1957 | gentable(); |

1958 | if (fclose(outfile) != 0) |

1959 | chk_err("main: Couldn't close output file."); |

1960 | printf("\nSUCCESS: The table has been successfully written.\n"); |

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> </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 "Check-Sum" 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 "checksum" is |

1996 | still used.</pre> |

1997 | |

1998 | <pre>CRC - This stands for "Cyclic Redundancy Code". Whereas the term |

1999 | "checksum" seems to be used to refer to any non-cryptographic checking |

2000 | information unit, the term "CRC" seems to be reserved only for |

2001 | algorithms that are based on the "polynomial" 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 "polynomial" 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> </p> |

2029 | |

2030 | <pre><big><strong>B. References |

2031 | </strong></big> |

2032 | [Griffiths87] Griffiths, G., Carlyle Stones, G., "The Tea-Leaf Reader |

2033 | Algorithm: An Efficient Implementation of CRC-16 and CRC-32", |

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., "The Art of Computer Programming", Volume 2: |

2040 | Seminumerical Algorithms, Section 4.6.</pre> |

2041 | |

2042 | <pre>[Nelson 91] Nelson, M., "The Data Compression Book", M&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., "Computation of Cyclic Redundancy Checks |

2048 | via Table Look-Up", 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., "Computer Networks", 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> </p> |

2062 | |

2063 | <pre><strong><big>C. References I Have Detected But Haven't Yet Sighted |

2064 | </big></strong> |

2065 | Boudreau, Steen, "Cyclic Redundancy Checking by Program," AFIPS |

2066 | Proceedings, Vol. 39, 1971.</pre> |

2067 | |

2068 | <pre>Davies, Barber, "Computer Networks and Their Protocols," J. Wiley & |

2069 | Sons, 1979.</pre> |

2070 | |

2071 | <pre>Higginson, Kirstein, "On the Computation of Cyclic Redundancy Checks |

2072 | by Program," The Computer Journal (British), Vol. 16, No. 1, Feb 1973.</pre> |

2073 | |

2074 | <pre>McNamara, J. E., "Technical Aspects of Data Communication," 2nd |

2075 | Edition, Digital Press, Bedford, Massachusetts, 1982.</pre> |

2076 | |

2077 | <pre>Marton and Frambs, "A Cyclic Redundancy Checking (CRC) Algorithm," |

2078 | Honeywell Computer Journal, Vol. 5, No. 3, 1971.</pre> |

2079 | |

2080 | <pre>Nelson M., "File verification using CRC", Dr Dobbs Journal, May 1992, |

2081 | pp.64-67.</pre> |

2082 | |

2083 | <pre>Ramabadran T.V., Gaitonde S.S., "A tutorial on CRC computations", IEEE |

2084 | Micro, Aug 1988.</pre> |

2085 | |

2086 | <pre>Schwaderer W.D., "CRC Calculation", April 85 PC Tech Journal, |

2087 | pp.118-133.</pre> |

2088 | |

2089 | <pre>Ward R.K, Tabandeh M., "Error Correction and Detection, A Geometric |

2090 | Approach" The Computer Journal, Vol. 27, No. 3, 1984, pp.246-253.</pre> |

2091 | |

2092 | <pre>Wecker, S., "A Table-Lookup Algorithm for Software Computation of |

2093 | Cyclic Redundancy Check (CRC)," Digital Equipment Corporation |

2094 | memorandum, 1974.</pre> |

2095 | |

2096 | <hr> |

2097 | </html> |

dashley@gmail.com | ViewVC Help |

Powered by ViewVC 1.1.25 |