Class crc

Synopsis

#include "breeze/checksum/crc.hpp"

template< typename Traits >
class crc

Description

A generic CRC calculator.

This template is instantiated over a traits class which provides the characterizing parameters of the CRC to calculate. To the best of my knowledge, these parameters were first identified by Ross N. Williams in his paper "A painless guide to CRC error detection algorithms", available online (a copy of the version available on <ross.net> at the time of this writing—October 7, 2020—is in the source tree; the file name is crc_v3.txt).

crc.hpp also provides traits classes for common CRC types (of course, other such classes can be defined by the user).

Warning
I haven't thought out the case CHAR_BIT > 8, so expect little changes to be done for unusual machines. Also, CRCs with a width less than 8 are not supported.
Each traits class must declare the following public members:
value_type:
A typedef to an unsigned type (e.g. std::uint32_t) for holding the CRC value. The width of this type can be larger than width if e.g. an exactly-sized type is not available on your implementation or you want to see the effect on performance of using a different type (e.g. uint_fast16_t for CRC-16).
width:
The number of bits in the CRC. This is also the degree of the polynomial used for the divisions. The polynomial can have at most width + 1 terms, but since the highest degree term has always the coefficient 1 (otherwise the degree wouldn't be width), that coefficient will be implied. The type of this constant is int const.
poly:
The unreflected divisor polynomial, with the top-most bit omitted; we emphasize that this is unreflected, regardless of reflect_in and reflect_out. The type is value_type const.
init:
An initial value for the computation. Type value_type const.
reflect_in:
true if and only if each input byte must be considerered reflected (UART); note that, as an optimization, this implementation will not actually reflect the input bytes, but the resulting CRCs will be as if it did. The type is bool const.
reflect_out:
true if and only if the final calculated value (before the XOR) must be reflected; usually equal to reflect_in, but at least one CRC exists (CRC-12/UMTS) for which these two values are different. The type is bool const .
xor_out:
The final value to XOR with. The type is value_type const.
check:
The CRC of the sequence "123456789", encoded as ASCII (nine characters, without any terminator); used to verify the implementation and the traits class.

Constructors

crc overloadInitializes the CRC calculator.
crc overloadCalculates the CRC of the range [first, last).

Functions to process input

accumulate overloadProcesses the values in [first, last), updating the calculated CRC.
accumulate overloadProcesses the character c, updating the calculated CRC.

Functions to read the result

valueReturns the calculated CRC

Source

Lines 110-182 in breeze/checksum/crc.hpp.

template< typename Traits >
class crc
{
public:
    //!     The same as \c Traits::value_type.
    // -----------------------------------------------------------------------
    typedef typename Traits::value_type
                        value_type ;

    //!\name Constructors
    //!\{
    //
    //!     Initializes the CRC calculator.
    // -----------------------------------------------------------------------
    constexpr           crc() noexcept ;

    //!     Calculates the CRC of the range <tt>[first, last)</tt>.
    // -----------------------------------------------------------------------
    template< typename InputIter >
    constexpr           crc( InputIter first, InputIter last ) ;
    //!\}

    //!\name Functions to process input
    //!\{
    //
    //!     Processes the values in <tt>[first, last)</tt>, updating the
    //!     calculated CRC.
    // -----------------------------------------------------------------------
    template< typename InputIter >
    constexpr void      accumulate( InputIter first, InputIter last ) ;

    //!     Processes the character \c c, updating the calculated CRC.
    // -----------------------------------------------------------------------
    constexpr void      accumulate( char c ) noexcept ;
    //!\}

    //!\name Functions to read the result
    //!\{
    //
    //!     Returns the calculated CRC. This read may occur at any time,
    //!     and doesn't disturb the running sum.
    // -----------------------------------------------------------------------
    constexpr value_type
                        value() const noexcept ;
    //!\}

private:
    //      A repetition of some of the names in Traits, to make code
    //      less verbose (inherit privately from Traits, instead?).
    // -----------------------------------------------------------------------
    static int        const width       = Traits::width       ;
    static value_type const init        = Traits::init        ;
    static bool       const reflect_in  = Traits::reflect_in  ;
    static bool       const reflect_out = Traits::reflect_out ;
    static value_type const xor_out     = Traits::xor_out     ;


    value_type          m_current ;
    static constexpr crc_private::crc_cache< Traits >
                        s_cache{} ;

    //      A few sanity checks on the traits class. These use
    //      "Traits::" to make things clearer for the user if an assert
    //      fails.
    // -----------------------------------------------------------------------
    static_assert( ! meta::has_sign< typename Traits::value_type >::value, "") ;
    static_assert( Traits::width > 0, "" ) ;
    static_assert( Traits::width <=
                       meta::width< typename Traits::value_type >::value,
                   "value_type does not have at least width value bits") ;
    static_assert( ( Traits::poly & 1 ) != 0,
                   "the constant term of the polynomial must be 1") ;
} ;