Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Calculating CRC Checksums in C++


June 1999/Calculating CRC Checksums in C++

Calculating CRC Checksums in C++

Colin Mahoney

Here's a handy template that computes a variety of CRC checksums.


A while back I was asked to produce some C++ code to calculate CRC (cyclic redundancy code) checksums. I was given a copy of Ross Williams' article, "A Painless Guide to CRC Error Detection Algorithms" [1], which includes a detailed description of the basic CRC algorithm, its optimization using tables and other means, and information about various CRC protocols. The article describes a parameterized model for CRC algorithms called the "Rocksoft™ Model CRC Algorithm." The article includes C source code for an implementation of the model. The model seemed to be made to measure for an implementation in C++ using templates. In this article I describe CRCGenerator, a C++ class which I produced based on Ross's original C code. Readers who want a detailed description of CRC algorithms should refer to Ross's original article.

CRCs — The Basics

CRCs create hash values for a block of data. These values can be used to check for file integrity and transmission errors in streams. They should not be used to check for malicious tampering with data, as it is quite easy to change the original data in a way that conserves the original CRC value.

A CRC checksum is obtained by treating the input data as a very long binary number, and dividing it by a shorter number — usually 16 or 32 bits. The remainder of this division is the CRC value. The quotient is not used and thus does not have to be recorded. The division is carried out modulo two without carries, and can be calculated efficiently using shifts and XORs (exclusive ORs). The divisor is known as the "polynomial," for reasons related to the mathematical theory underlying such calculations. CRC checksums have a useful property: if the checksum is appended to the original data, the new checksum for <data + original checksum> is zero. This makes testing for transmission errors very easy; the checksum can be transmitted after the data, and the receiver has only to check that the checksum for all the data received is zero.

The CRCGenerator Implementation

CRCGenerator (Figure 1 a partial listing of crc.h) uses a nested table class, CRCTable, to do most of the work of calculating the checksum. CRCTable has one data member, Table, and three member functions — a constructor, a subscripting operator, and CalcTableEntry. The latter calculates the values for the elements of the table, and is called repeatedly from the constructor to fill the table. CRCGenerator has a static data member Table, of type CRCTable. The unsigned long member Register holds the current value of the CRC calculation. It is initialized to the value of the template parameter Init. The code uses template parameters in conditional expressions to select the appropriate element of Table when processing data. This will produce a lot of "conditional expression is constant" style messages on compilation. You may want to disable this warning when compiling crc.h.

CRCGenerator is defined in the namespace cdm_crc. Also defined in this namespace are CRCMaxBits, which defines the maximum number of bits that can be held in an unsigned long, and an insertion operator to write the CRC value to an ostream.

The Rocksoft Model

The Rocksoft model uses seven parameters to describe each CRC protocol. Six of these make natural template parameters in C++, while the seventh is a check value used to validate implementations of the algorithm. I wrote the CRCGenerator class to use just five of the Rocksoft parameters as well as one additional parameter. The declaration of the CRCGenerator class is:

template
   <
   int Width,
   unsigned long Poly,
   unsigned long Init,
   unsigned long XOrOut,
   bool Ref,
   bool Direct=true
   >
   class CRCGenerator;

If you want to calculate CRC-16 checksums, you can typedef the type:

typedef CRCGenerator
   <
   16,
   0x8005,
   0,
   0,
   true
   > CRC16;

The template parameters are as follows.

Width

This parameter describes the width of the polynomial used to calculate the checksum. It is equal to the highest exponent of x used in the polynomial representation of the divisor. CRCGenerator works with polynomials of widths from 8 to 32 bits.

Poly

This parameter is the value representing the polynomial used to calculate the CRC, but not including the most significant bit. This value should have Width bits. The ability of a CRC algorithm to detect errors depends to a large part on the mathematical properties of the polynomial chosen. For this reason it is not really a good idea to "invent" your own polynomial — unless you really know what you're doing you should use one that has been tried and tested.

Init

This is the value used to initialize the CRC value, as given by the CRC protocol in question. Common values are 0, as in CRC-16, and 0xFFFFFFFF, as in CRC-32.

XOrOut

This is the value to be XORed with the final result of the CRC calculation to obtain the CRC value for the data. If XOrOut is non-zero, the CRCGenerator function GetNormalCRC will not return zero after processing <data+ original checksum>.

Ref

Some CRC protocols process bytes least-significant bit first — the bytes are reflected. Ref controls whether the input bytes should be reflected before being processed, and whether the final CRC value should be reflected before it is read. The Rocksoft model uses separate parameters for input and output, but my implementation uses a single value for both.

Direct

When Direct is true (the default value) each byte processed is passed immediately through Register — that is, there are no bytes sitting in Register waiting to be propagated out by the following data. The effect is as if each byte processed had been pushed through Register by Width zero bits. Any actual data that follows is superimposed on top of these zero bits and then processed in the same way.

The value that has been fed into Register by the end of the calculation is equal to the total input data augmented by Width zero bits. This is the required behavior for most CRC alorithms. For some algorithms, however, the bytes processed should be placed at the bottom of the register then pushed through it by the following data. You can get this behavior by setting the Direct parameter to false. If you have Direct set to false and you want to force all the data through the register, you can combine calls to Process and ProcessBits to pass Width zero bits through the register after processing all your data.

The "Check" parameter in the Rocksoft Model is the value that should be obtained when the string "123456789" is processed.

The CRCGenerator Interface

The public interface for CRCGenerator is shown below:

CRCGenerator();
unsigned long GetCRC() const;
unsigned long GetNormalCRC() const;
bool GetDirect() const;
bool GetReflect() const;
bool GetWidth() const;
void LoadRegister
   (
   unsigned long value
   );
void Process(unsigned char byte);
void Process
   (
   unsigned char* block,
   int block_size
   );
template<class InIter> void
Process(InIter first, InIter last);
void ProcessBits
   (
   unsigned char bits,
   int count
   );
void Reset();
void Write(ostream& os) const;

A synopsis of these functions follows.

CRCGenerator

Only a default constructor is required since all the necessary information is given in the template parameters.

GetCRC

This function returns the value in the CRC register after XORing with XOrOut. If the Ref parameter is true this value is bitwise reflected. If you want to feed this value into the CRC calculation, you should do so least significant byte first — you don't need to worry about the bits, as the calculation takes care of reflecting them. If Ref is false the bytes are correctly ordered. The value is returned in the bottom Width bits of the return value.

GetNormalCRC

This function reflects the bytes in the CRC register if Ref is true, and returns the CRC value in the most significant bytes of the return value. The value returned from GetNormalCRC can be fed into the calculation most-significant byte first, irrespective of whether Ref is true or false.

GetDirect, GetReflect, GetWidth

These functions return the values of the Direct, Ref, and Width parameters respectively. These may be useful for shifting or formatting the value returned by GetCRC or GetNormalCRC.

LoadRegister

This function can be called to XOR a value into the register. The value is reflected as necessary. This function should not be required for most calculations.

Process

The three Process functions allow data to be fed into the calculation either one byte at a time or in blocks. An alternative to the version using member templates is provided; it is commented out and can be used if your compiler doesn't support member templates.

ProcessBits

Processes count bits from bits. If Ref is false they are read in least-significant bit first; if Ref is true, most-significant bit first. Unless you want to do something unusual with CRCs having widths that are not integral numbers of bytes you probably won't need to use this function.

Reset

This function sets the CRC register value to the value of the Init parameter.

Write

Writes the CRC value to a stream, taking Ref into account. Write can be used to append the CRC value to a file stream. The file will then produce a CRC value of zero if read in and processed through CRCGenerator.

An Example: CRC-16

I have already shown the typedef used by the standard CRC-16 protocol. The following code runs the test case for the Rocksoft model:

typedef CRCGenerator
   < 16,
     0x8005UL,
     0UL,
     0UL,
     true > CRC16;
unsigned char data[] =
   {'1','2','3', '4','5','6','7', '8','9'};
CRC16 crc16;
crc16.Process(data, 9);
unsigned long crc_val;
crc_val=crc16.GetNormalCRC();

Figure 2 shows complete code to calculate and print CRC-16 checksums for a list of files specified on the command line. Note the call to infile.unsetf(ios_base::skipws), which is necessary because istream_iterator<> skips whitespace by default.

Conclusion

The above examples demonstrate the convenience offered by C++ template classes. The template mechanism takes care of the creation and initialization of the static look-up table, allowing the class user to write code uncluttered by global variables or calls to initialization functions. My intention in writing the CRCGenerator class was to provide efficiency, ease of use, and flexiblity. In as much as this has been achieved, it is because C++ has made these often conflicting goals easily attainable.

Note

[1] Available online at Ross's web site at http://www.ross.net/crc/.

Colin Mahoney teaches English and is an independent developer of software for language learners in Sabadell, Spain. He can be contacted at [email protected].


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.