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

[sur-behoffski <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     : 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.