Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C
- From: sur-behoffski <sur_behoffski@...>
- Date: 2019年10月25日 17:21:10 +1030
G'day,
I've been fortunate to know Dr. Ross Williams, who has been involved in all sorts
of interesting software.
He has a "CRC Pitstop" page at:
http://ross.net/crc/
It contains a lot of information... In particular the 1993 paper,
"A Painless Guide to CRC Error Detection Algorithms", is a classic. Here is
the header, and the table of contents, in glorious ASCII:
-------------------
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS
==================================================
"Everything you wanted to know about CRC algorithms, but were afraid
to ask for fear that errors in your understanding might be detected."
Version : 3.
Date : 19 August 1993.
Author : Ross N. Williams.
Net : ross@guest.adelaide.edu.au.
FTP : ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt
Company : Rocksoft^tm Pty Ltd.
Snail : 16 Lerwick Avenue, Hazelwood Park 5066, Australia.
Fax : +61 8 373-4911 (c/- Internode Systems Pty Ltd).
Phone : +61 8 379-9217 (10am to 10pm Adelaide Australia time).
Note : "Rocksoft" is a trademark of Rocksoft Pty Ltd, Australia.
Status : Copyright (C) Ross Williams, 1993. However, permission is
granted to make and distribute verbatim copies of this
document provided that this information block and copyright
notice is included. Also, the C code modules included
in this document are fully public domain.
Thanks : Thanks to Jean-loup Gailly (jloup@chorus.fr) and Mark Adler
(me@quest.jpl.nasa.gov) who both proof read this document
and picked out lots of nits as well as some big fat bugs.
Table of Contents
-----------------
Abstract
1. Introduction: Error Detection
2. The Need For Complexity
3. The Basic Idea Behind CRC Algorithms
4. Polynomical Arithmetic
5. Binary Arithmetic with No Carries
6. A Fully Worked Example
7. Choosing A Poly
8. A Straightforward CRC Implementation
9. A Table-Driven Implementation
10. A Slightly Mangled Table-Driven Implementation
11. "Reflected" Table-Driven Implementations
12. "Reversed" Polys
13. Initial and Final Values
14. Defining Algorithms Absolutely
15. A Parameterized Model For CRC Algorithms
16. A Catalog of Parameter Sets for Standards
17. An Implementation of the Model Algorithm
18. Roll Your Own Table-Driven Implementation
19. Generating A Lookup Table
20. Summary
21. Corrections
A. Glossary
B. References
C. References I Have Detected But Haven't Yet Sighted
-------------------
The "established" CRCs from the 1950s-1980s have been widely copied; however,
I note that the "Castagnoli" CRC family(s), published in 1993 (e.g. CRC323C),
are gaining traction as they do a better job of finding errors in some
situations. See the second paragraph in the section "Standards and common use"
in the Wikipedia CRC page:
https://en.m.wikipedia.org/wiki/Cyclic_redundancy_check
cheers,
s-b etc.