What is CRC?
The Cyclic Redundancy Check, short CRC, is a common technique for the calculation of checksums in order to provide an error-detection on data transfers in digital networks and storage devices. The basic principle of CRC calculations was invented by W. Wesley Peterson in 1961, while many of today’s standard implementations were published later on by several other researchers and mathematicians.
CRCs are deemed cyclic and redundant as they utilize cyclic block codes to calculate checksums, which themselves contain no information that was not already included in the raw data for which the CRC was calculated. The usefulness of CRC checksums instead originates from their inherent capacity to detect erroneous data in communication channels and storage devices; including any uneven number of bit errors and most two-bit errors, as well as any burst error of certain length.In order to do so, CRC algorithms require a generator polynomial that is used as a divisor in a polynomial division of the raw data for which to calculate the CRC. The remainder of this division is then considered the result.In hardware, CRC checksum calculations may be easily implemented using linear feedback shift-registers. The following example diagram illustrates the basic principle of these hardware implementations:
Usage of different generator polynomials results in different error-detection properties, thus the selection of the proper generator polynomial is a question of vital importance. Some of the factors in this selection process are the length of the data for which to calculate the CRC, the desired error-detection properties, and the desired performance of the calculation.
Various CRC calculation algorithms have been incorporated into industrial standards that do not only define the generator polynomial to be used in the polynomial division, but also require compliance to further specifications such as initialization vectors.
Using emLib CRC
The emLib CRC module has a simple yet powerful API that can be easily integrated into an existing application. The code is completely written in ANSI-C.
emLib CRC does not offer API functions that are fully conformant to a specific standard implementation, but delivers generic CRC routines instead. This allows their usage in more than one standard implementation at a time, but requires the user to make sure desired initialization vectors and further specifications are performed from within the application
To simply calculate a CRC for contiguous raw data, the application would only need to call one function. If two or more distinct data areas need to be processed into the same CRC, subsequent calls to the function may be used for incremental calculations over each of these areas. All functionality can be verified with standard test patterns using the validation API functions. The functions for generating the lookup tables that are used for specific polynomials are also included for full transparency.
Performance and Memory Footprint
The following table contains performance values for an emLib CRC release build as tested on a Cortex-M7 at 200 MHz, using the 32-bit polynomials 0xEDB88320 (LSB) and 0x04C11DB7 (MSB):
for 1 MB of data
|Bitwise, arbitrary polynomial (LSB)||–||124||1.53||650.12 ms||56 byte|
|Table-driven, arbitrary polynomial (LSB)||784||17||11.21||89.13 ms||92 byte|
|Table-driven, specified polynomial (LSB)||–||13||14.67||68.16 ms||1060 byte|
|Bitwise, arbitrary polynomial (MSB)||148||134||1.42||702.45 ms||168 byte|
|Table-driven, arbitrary polynomial (MSB)||878||20||9.53||104.86 ms||234 byte|
|Table-driven, specified polynomial (MSB)||–||11||17.33||57.67 ms||1056 byte|
Using the 32-bit polynomial 0x04C11DB7 to verify the integrity of a message
This sample shows how to calculate a 32-bit CRC for a given message. Subsequently, it verifies the message’s integrity by calculating the 32-bit CRC for the augmented message.
emLib includes sample applications to demonstrate its functionality and to provide an easy to use starting point for your application. The applications’ source code is included in the shipment. The following applications are delivered with emLib CRC:
|Application name||Target platform||Description|
|CRCAugmentFile.exe||Windows||Command line tool to augment a file with its calculated CRC. Uses the 32-bit polynomial 0x04C11DB7.|
|CRCCalc.exe||Windows||Command line tool to calculate the CRC for a given file using the bitwise API functions for arbitrary polynomials. Calculation parameters are user-configurable.|
|CRCValidate.exe||Windows||Command line tool to validate the emLib CRC API using standard test patterns.|
|CRCVerifyAugmentedFile.exe||Windows||Command line tool to verify the integrity of an augmented file. Uses the 32-bit polynomial 0x04C11DB7.|
CRCAugmentFile is a Windows command line tool to augment a file with its calculated CRC. Typically, this is done by a sender before sending the file towards its recipient. CRCAugmentFile uses the 32-bit polynomial 0x04C11DB7 (MSB-first notation) and requires the file to not be write-protected. The application CRCVerifyAugmentedFile may be used to verify the augmented file’s integrity.
|<sourcefile>||Path to the file for which to calculate the CRC. Must not be write-protected.|
CRCCalc is a Windows command line tool to calculate the CRC for a given file using the bitwise emLib CRC API functions for arbitrary polynomials. Further calculation parameters are configurable by the user, including the polynomial to use and an initial value for the calculation. CRCCalc may be used to easily calculate CRC checksums for arbitrary files.
|<sourcefile>||Path to the file for which to calculate the CRC.|
|[-MSB [<SizeOfPoly>]||(Optional) Used to indicate MSB-first notation. If not set, calculation is performed LSB-first. If set and Polynomial is given, SizeOfPoly must indicate that polynomial’s size. If set and Polynomial is not given, a default polynomial of known size is used, hence SizeOfPoly is ignored and may be omitted.|
|[-poly <Polynomial>]||(Optional) Defines the polynomial to be used, which must not exceed a polynomial degree of 32. Expects hexadecimal notation. If not set, the 16-bit polynomial 0x8408 is used for LSB-first calculations and the 16-bit polynomial 0x1021 is used for MSB-first calculations.|
|[-init <InitialCRC>]||(Optional) Initial value for incremental calculations. Expects hexadecimal notation. If not set, 0x0 is used as initial value.|
CRCValidate is a Windows console application to validate the emLib CRC API using standard test patterns. It uses the emLib CRC validation API to validate the implementation of the emLib CRC API functions. CRCValidate will display an error code if any validation fails, omitting further validation steps.
CRCVerifyAugmentedFile is a Windows command line tool to verify the integrity of an augmented file. Typically, this is done by the file’s recipient. CRCVerifyAugmentedFile uses the 32-bit polynomial 0x04C11DB7 (MSB-first notation). The application CRCAugmentFile may be used to augment a file with its calculated CRC.
|<sourcefile>||Path to the file for which to calculate the CRC.|