Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C

sur-behoffski
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     : [hidden email].
         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 ([hidden email]) and Mark Adler
                   ([hidden email]) 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.

Reply | Threaded
Open this post in threaded view
|

Re: Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C

Enrico Colombini
On 25-Oct-19 08:51, sur-behoffski wrote:
> 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/

Thanks for the pointer, looks very interesting.

--
   Enrico

Reply | Threaded
Open this post in threaded view
|

Re: Ross Williams' "CRC Pitstop" page... gives lots of background, in pseudocode/C

Gé Weijers
If you REALLY want to know why CRC is the way it is from a mathematical point of view:

"The iSCSI CRC32C Digest and the Simultaneous Multiply and Divide Algorithm"
https://pdfs.semanticscholar.org/21b8/c594566f8ad0dba7b8e071705b8f865d5fff.pdf

To find the best CRC polynomial for your specific range of message lengths:



--