Home Libraries Author Links

stm::crc< RemPolT > Class Template Reference
[GenCRC: Generic CRC Generation]

List of all members.


Detailed Description

template<typename RemPolT>
class stm::crc< RemPolT >

Class template crc provides a means to generate cyclic redundancy check (CRC) remainder polynomials of type RemPolT over buffers of byte-like objects.

The CRC algorithm works by computing the remainder of a modulo-2 polynominal division. The buffer to check is treated as the (binary) coefficents of a long polynominal for the dividend, with the higher order bits of the buffer fed first as the polynominal's highest coefficents. A particular CRC algorithm has another polynominal, the so called generator polynomial, associated with it to be used as the divisor. The quotient is ignored. The remainder of the division is considered as checksum. However, the division uses modulo-2 rules (no carries) for the coefficents.

RemPolT shall be an unsigned integer type as e.g. unsigned short, unsigned int, unsigned long, unsigned long long or maybe even unsigned char. The implementation uses a RemPolT table of dimension 2**sizeof(char) = 256. Because of the size and initialization time needed for this lookup table, it is proposed to generate one const crc<RemPolT> object for each generator polynomial needed as globally as possible and reusing it everywhere CRC check remainder polynomials are needed. Also pointers or references to such const crc<RemPolT> objects may freely be passed around.

Examples:

gencrctest.cpp.

Definition at line 130 of file gencrc.hpp.


Public Types

typedef RemPolT rempol_type
 The type rempol_type represents CRC remainder polynomials.

Public Member Functions

 crc (rempol_type generatorPolynomial, rempol_type initialRemainderPolynomial=0, bool reflectInput=false)
 Constructs a crc object usable to generate CRC remainder polynomials using the generator polynomial generatorPolynomial.
template<typename InputIterator>
rempol_type operator() (InputIterator first, InputIterator last, bool reflectRemainder=false, rempol_type finalXorPolynomial=0) const
 Return the CRC remainder polynomial over the value type buffer consisting of the half open interval [*first, *last) of value type objects.
template<typename InputIterator>
rempol_type operator() (rempol_type initialRemainderPolynomial, InputIterator first, InputIterator last, bool reflectRemainder=false, rempol_type finalXorPolynomial=0) const
 Return the CRC remainder polynomial over the value type buffer consisting of the half open interval [*first, *last) of value type objects.
template<typename InputIterator>
rempol_type operator() (InputIterator first, size_t size, bool reflectRemainder=false, rempol_type finalXorPolynomial=0) const
 Return the CRC remainder polynomial over the value type buffer consisting of size value type objects beginning at *first.
template<typename InputIterator>
rempol_type operator() (rempol_type initialRemainderPolynomial, InputIterator first, size_t size, bool reflectRemainder=false, rempol_type finalXorPolynomial=0) const
 Return the CRC remainder polynomial over the value type buffer consisting of size value type objects beginning at *first.
bool inputReflection () const
 Return true, if this object performs input reflection, else false.
rempol_type generatorPolynomial () const
 Return this object's generator polynomial without the implicit leading coefficient.
rempol_type defaultInitialRemainderPolynomial () const
 Return this object's default initial remainer polynomial.

Member Typedef Documentation

template<typename RemPolT>
typedef RemPolT stm::crc< RemPolT >::rempol_type

The type rempol_type represents CRC remainder polynomials.

CRC remainder polynomials are the sum ci*x**i (0 <= i <= deg) of monomials of the indeterminate x with binary coefficients ci computed modulo-2 and the polynomial degree deg.

If s is the number of binary digits of rempol_type (this is 8 * sizeof (rempol_type)), then the maximal possible polynomial degree is deg = s - 1. Such a polynomial is represented in a rempol_type object by representing the binary coefficient of its order i monomial as bit i of the rempol_type object.

Thus for example, for s = 16 rempol_type may be chosen as unsigned short and the CRC remainder polynomial

                   x**15 + x**12 + x**5 + x**0
is expressed as 0x9021.

Definition at line 153 of file gencrc.hpp.


Constructor & Destructor Documentation

template<typename RemPolT>
stm::crc< RemPolT >::crc ( rempol_type  generatorPolynomial,
rempol_type  initialRemainderPolynomial = 0,
bool  reflectInput = false 
) [explicit]

Constructs a crc object usable to generate CRC remainder polynomials using the generator polynomial generatorPolynomial.

The generator polynomial is always assumed to be of degree s = 8 * sizeof (rempol_type) and thus the corresponding binary coefficient at the imaginary binary digit s is always assumed to be 1 and is not represented explicitly.

So for example, for s = 16 the generator polynomial of degree 16

                   x**16 + x**12 + x**5 + x**0
is expressed as unsigned short 0x1021.

By means of the optional parameter initialRemainderPolynomial a remainder polynomial serving as initial value for the check algorithm may be supplied. If this parameter is missing, 0 is assumed.

Normally the the input bits are fed a byte at a time, with the highest bits of a byte treated as the higher bits of the dividend polynominal. Some CRC algorithms require to reflect the bits (about the byte's center, so the first and last bits are switched, etc.) before feeding.

With the optional parameter reflectInput set to true this behaviour may be chosen. If this parameter is missing, false is assumed.


Member Function Documentation

template<typename RemPolT>
template<typename InputIterator>
rempol_type stm::crc< RemPolT >::operator() ( InputIterator  first,
InputIterator  last,
bool  reflectRemainder = false,
rempol_type  finalXorPolynomial = 0 
) const

Return the CRC remainder polynomial over the value type buffer consisting of the half open interval [*first, *last) of value type objects.

The template parameter InputIterator shall conform to the inpuit iterator requirements (24.1.1). It may be a constant iterator and shall have a byte-like value type value_type with sizeof (value_type) == 1 and be convertible to rempol_type. Thus e.g. for value_type char, signed char or unsigned char may be used and as InputIterator e.g. pointers or const pointers to one of these value types may be chosen.

As initial remainder polynomial defaultInitialRemainderPolynomial() specified by the constructor is used. If reflectRemainder is true (default: false), the computed remainder polynomial is reflected.

Just before return the result is xored with finalXorPolynomial, which is 0 by default.

template<typename RemPolT>
template<typename InputIterator>
rempol_type stm::crc< RemPolT >::operator() ( rempol_type  initialRemainderPolynomial,
InputIterator  first,
InputIterator  last,
bool  reflectRemainder = false,
rempol_type  finalXorPolynomial = 0 
) const

Return the CRC remainder polynomial over the value type buffer consisting of the half open interval [*first, *last) of value type objects.

The template parameter InputIterator shall conform to the inpuit iterator requirements (24.1.1). It may be a constant iterator and shall have a byte-like value type value_type with sizeof (value_type) == 1 and be convertible to rempol_type. Thus e.g. for value_type char, signed char or unsigned char may be used and as InputIterator e.g. pointers or const pointers to one of these value types may be chosen.

As initial remainder polynomial the argument initialRemainderPolynomial is used.

If reflectRemainder is true (default: false), the computed remainder polynomial is reflected.

Just before return the result is xored with finalXorPolynomial, which is 0 by default.

template<typename RemPolT>
template<typename InputIterator>
rempol_type stm::crc< RemPolT >::operator() ( InputIterator  first,
size_t  size,
bool  reflectRemainder = false,
rempol_type  finalXorPolynomial = 0 
) const

Return the CRC remainder polynomial over the value type buffer consisting of size value type objects beginning at *first.

The template parameter InputIterator shall conform to the inpuit iterator requirements (24.1.1). It may be a constant iterator and shall have a byte-like value type value_type with sizeof (value_type) == 1 and be convertible to rempol_type. Thus e.g. for value_type char, signed char or unsigned char may be used and as InputIterator e.g. pointers or const pointers to one of these value types may be chosen.

As initial remainder polynomial defaultInitialRemainderPolynomial() specified by the constructor is used.

If reflectRemainder is true (default: false), the computed remainder polynomial is reflected.

Just before return the result is xored with finalXorPolynomial, which is 0 by default.

template<typename RemPolT>
template<typename InputIterator>
rempol_type stm::crc< RemPolT >::operator() ( rempol_type  initialRemainderPolynomial,
InputIterator  first,
size_t  size,
bool  reflectRemainder = false,
rempol_type  finalXorPolynomial = 0 
) const

Return the CRC remainder polynomial over the value type buffer consisting of size value type objects beginning at *first.

The template parameter InputIterator shall conform to the inpuit iterator requirements (24.1.1). It may be a constant iterator and shall have a byte-like value type value_type with sizeof (value_type) == 1 and be convertible to rempol_type. Thus e.g. for value_type char, signed char or unsigned char may be used and as InputIterator e.g. pointers or const pointers to one of these value types may be chosen.

As initial remainder polynomial the argument initialRemainderPolynomial is used.

If reflectRemainder is true (default: false), the computed remainder polynomial is reflected.

Just before return the result is xored with finalXorPolynomial, which is 0 by default.

template<typename RemPolT>
bool stm::crc< RemPolT >::inputReflection (  )  const

Return true, if this object performs input reflection, else false.

template<typename RemPolT>
rempol_type stm::crc< RemPolT >::generatorPolynomial (  )  const

Return this object's generator polynomial without the implicit leading coefficient.

template<typename RemPolT>
rempol_type stm::crc< RemPolT >::defaultInitialRemainderPolynomial (  )  const

Return this object's default initial remainer polynomial.


© Copyright Tom Michaelis 2002-2007

Distributed under the SysToMath Software License (See the accompanying file license.txt or a copy at www.SysToMath.com).