CRC Model - Release Notes
Copyright 2017 by The Software Samurai.
On the web: http://www.SoftwareSam.us/
Software released under GNU GPL3, and documentation released under FDL1.3
Original algorithm and notes (1993) were written and placed in the
public domain by:
Ross Williams: www.ross.net
This package contains source code and basic documentation for the 'crcmodel' application.
You will need to build the application binary for your target system (see README file).
The 'crcmodel' utility is a GNU/Linux console (command-line) utility which provides
a reference model for implementing CRC (Cyclic Redundancy Check) “checksum”
generation.
This is not a commercial-quality product. The user interface is quite basic and the documentation
is useful but simple.
- This application is intended as a reference for students and others who are implementing CRC checksums
in their own work.
- 'crcmodel' provides a simple, accurate model for CRC generation based on a set of flexible setup
parameters. If, for a given source data stream and setup parameters, your CRC implementation generates the
same CRC value as 'crcmodel' then you can be relatively certain that your implementation is correct.
The reference model checksum generator does not use a table lookup. Instead it directly calculates the CRC
byte-by-byte. This is a simple and reliable model for algorithm verification tests, but it is comparatively slow.
- For high-speed commercial-grade applications such as assembling Ethernet packets, the CRC algorithm
can be enhanced by using a pre-generated lookup table to reduce the number of necessary runtime calculations.
The 'crcmodel' application is able to flexibly generate such a lookup table to match your exact specifications.
However, as Ross says in his notes: “If you don't care much about
speed, just use the reference model code!”
- We have enhanced Ross's original code to include an example implementation of the table-lookup speed
enhancement. For this example we dynamically build a lookup table according to the setup parameters provided and
then process the input stream using that table.
Note that to properly evaluate the difference in processing performance between the direct calculation method and
the table lookup method, we would need a much larger data set than our simple test data provides. We leave that
evaluation as an exercise.
While our simple lookup-table implementation is certainly faster, it is also potentially less robust. However, for all
the likely combinations of setup parameters, the faster algorithm produces exactly the same results as the reference model.
(See the GenRamTable() and FileChecksumT() functions for details
of the lookup-table implementation.) We hope that your hot implementation will be even faster,
and every bit as stable. Good luck!
- 'crcmodel' supports both 16-bit and 32-bit CRC generation using the following parameters:
- width of the CRC register (and table entries)
- “polynomial” value, i.e. the hexidecimal value which is the divisor for CRC division.
- initial register value
- reflection of the input, that is reversing the bits of each byte of the input stream.
- reflection of the final CRC value, that is reversing the bits of the final register value before
returning from the algorithm.
- XOR value to be applied to the final CRC value.
- User Interface and command-line options. There are three operating mode options.
One of these options must be the first option specified.
- ––test
Perform an internal test of the algorithm using a known parameter setup and a simple input stream: “123456789”.
- ––file
Specify a source binary file as the input stream and apply the reference model code to it.
- ––table
Generate and export a lookup table based on the optional parameters described below.
Optional Parameters
These options allow optional specification of all setup parameters for CRC checksum and table generation.
All CRC processing parameters have default values that correspond to a generic 32-bit algorithm.
(All optional parameters are ignored for the internal
algorithm-validation test. '––test')
- ––poly=POLY
This is the so-called “generator polynomial” or hexadecimal XOR value.
Default: 04C11DB7h This is the value used in many popular algorithms including the one
of particular interest to us, which is the CRC checksum used by OGG/Vorbis audio tag data.
Any hexadecimal value will work, so long as it is the same width as the register; however,
some values work better than others.
Register width is specified by the '––regbits' option below.
-
––reflect=[true | false]
Direction of bit processing for input bytes.
'true' for algorithms which shift bits right (default)
'false' for algorithms which shift bits left
-
––reflout=[true | false]
Reverse the order of bits for the final CRC checksum value before returning it.
'true' Reverse the bit order. (default)
'false' Do not reverse the bit order.
-
––regbits=[16 | 32]
Number of bits in the accumulator register.
16 == 16-bit calculations
32 == 32-bit calculations (default)
-
––regfinal=HEXVALUE
Post-calculation XOR value (in hexadecimal). default: FFFFFFFFh
Perform an XOR operation on the final CRC checksum value before returning it.
-
––reginit=HEXVALUE
Initial register value (in hexadecimal). This will be the register value when
processing begins. default: FFFFFFFFh
-
––oggvorbis
Special Case: Set up processing parameters for OGG/Vorbis metadata (tag data)
checksum generation.
-
––help
Display a list of command-line options (this list)
- There is no formal documentation for this application because this is a reference algorithm and not a
commercial product. Ross's original article describing the theory and the practical mathematics of CRC generation
can be found at:
“A Painless Guide To CRC Error Detection Algorithms,”
http://www.ross.net/crc/download/crc_v3.txt
For the current release, at least, in addition to our own implementation notes in the source code, most of
Ross's explanations and source-code notes have been retained.
Application usage is described by the list of command-line options: crcmodel --help (see above)
- Since this package was originally posted, we have completed an implementation of the CRC model in C++.
We believe it to be a much cleaner implementation with enhanced source code readability and easy portability for
integration into other applications. Please see the crcPlus package, available as a separate download.
- As a final note, in the classroom, we live by Abelson & Sussman's postulate that
“Programs must be written for people to read, and only incidentally for
machines to execute.” In that spirit, we have made some rather unkind remarks in the source code about
Ross Williams' coding style. Sorry about that, but keep in mind that Ross is a pioneer in algorithms, and that pioneers
are messy by nature in ways that software designers cannot afford to be.
The files included in this release.
crcmodel/ // Source code directory
crcmodel.c // Startup code, user interface and basic functionality
crcmodel.h // Definitions and constant data
crctable.c // Code for generating a CRC lookup table
Makefile // Build the 'crcmodel' application
README // Package description, release notes (this file)
Notes on the current release of 'crcmodel'
- This application was designed under Fedora Linux and is built using the GNU C compiler, version 4.8.3.
(Note for users of Microsoft Windows(tm), we strongly recommend that you immediately wipe your system and
install Ubuntu 16 LTS.) http://releases.ubuntu.com/
- The -std=gnu11 switch is required for a successful build. See the Makefile for details.
- Original Release v:1.0 was written by Ross Williams and is in the public domain.
- Current Release v:1.5.02
- Based on Ross Williams' original work and enhanced for student use.
- Convert most hard-coded #define's to variables and implement command-line switches for dynamic configuration
of the algorithm.
- Implementation of a very basic
user interface.
- Additions to and/or modification of source code notes.
- Mea culpa: This application was written in four(4) days, most of which time was spent in research.
It has not yet been seen by our beta-test volunteers. Although programmers always believe that our work is
totally bug-free, we are always wrong. Please report all bugs or suspected bugs via the website. We apologize
for any errors, all of which are entirely our own responsibility.
— Software Sam
These notes are adapted from the “README” file included with the application
archive.
Thank you and have fun with CRC! — Software Sam
|