Header <boost/crc.hpp>The header <boost/crc.hpp> supplies two
class templates in namespace Contents
Header Synopsis#include <boost/integer.hpp> // for boost::uint_t #include <cstddef> // for std::size_t namespace boost { template < std::size_t Bits > class crc_basic; template < std::size_t Bits, impl_def TruncPoly = 0u, impl_def InitRem = 0u, impl_def FinalXor = 0u, bool ReflectIn = false, bool ReflectRem = false > class crc_optimal; template < std::size_t Bits, impl_def TruncPoly, impl_def InitRem, impl_def FinalXor, bool ReflectIn, bool ReflectRem > typename uint_t<Bits>::fast crc( void const *buffer, std::size_t byte_count ); template < std::size_t Bits, impl_def TruncPoly > typename uint_t<Bits>::fast augmented_crc( void const *buffer, std::size_t byte_count, typename uint_t<Bits>::fast initial_remainder ); template < std::size_t Bits, impl_def TruncPoly > typename uint_t<Bits>::fast augmented_crc( void const *buffer, std::size_t byte_count ); typedef crc_optimal<16, 0x8005, 0, 0, true, true> crc_16_type; typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_type; typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type; typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> crc_32_type; } The implementation-defined type impl_def stands for the quickest-to-manipulate built-in unsigned integral type that can represent at least Bits bits. RationaleA common error detection technique, especially with electronic communications, is an appended checksum. The transmitter sends its data bits, followed by the bits of the checksum. The checksum is based on operations done on the data bit stream. The receiver applies the same operations on the bits it gets, and then gets the checksum. If the computed checksum doesn't match the received checksum, then an error ocurred in the transmission. There is the slight chance that the error is only in the checksum, and an actually-correct data stream is rejected. There is also the chance of an error occurring that does not change the checksum, making that error invisible. CRC is a common checksum type, used for error detection for hardware interfaces and encoding formats. BackgroundCRCs work by computing the remainder of a modulo-2 polynominal division. The message is treated as the (binary) coefficents of a long polynominal for the dividend, with the earlier bits of the message fed first as the polynominal's highest coefficents. A particular CRC algorithm has another polynominal associated with it to be used as the divisor. The quotient is ignored. The remainder of the division considered the checksum. However, the division uses modulo-2 rules (no carries) for the coefficents. See A Painless Guide to CRC Error Detection Algorithms for complete information. A clearer guide is at the Easier Said Than Done web page. CRC Parameters
Theoretical CRC Computertemplate < std::size_t Bits > class boost::crc_basic { public: // Type typedef implementation_defined value_type; // Constant reflecting template parameter static std::size_t const bit_count = Bits; // Constructor explicit crc_basic( value_type truncated_polynominal, value_type initial_remainder = 0, value_type final_xor_value = 0, bool reflect_input = false, bool reflect_remainder = false ); // Internal Operations value_type get_truncated_polynominal() const; value_type get_initial_remainder() const; value_type get_final_xor_value() const; bool get_reflect_input() const; bool get_reflect_remainder() const; value_type get_interim_remainder() const; void reset( value_type new_rem ); void reset(); // External Operations void process_bit( bool bit ); void process_bits( unsigned char bits, std::size_t bit_count ); void process_byte( unsigned char byte ); void process_block( void const *bytes_begin, void const *bytes_end ); void process_bytes( void const *buffer, std::size_t byte_count ); value_type checksum() const; }; The This implementation is slow since it computes its CRC the same way as in theory, bit by bit. No optimizations are performed. It wastes space since most of the CRC parameters are specified at run-time as constructor parameters. Optimized CRC Computertemplate < std::size_t Bits, impl_def TruncPoly, impl_def InitRem, impl_def FinalXor, bool ReflectIn, bool ReflectRem > class boost::crc_optimal { public: // Type typedef implementation_defined value_type; // Constants reflecting template parameters static std::size_t const bit_count = Bits; static value_type const truncated_polynominal = TruncPoly; static value_type const initial_remainder = InitRem; static value_type const final_xor_value = FinalXor; static bool const reflect_input = ReflectIn; static bool const reflect_remainder = ReflectRem; // Constructor explicit crc_optimal( value_type init_rem = InitRem ); // Internal Operations value_type get_truncated_polynominal() const; value_type get_initial_remainder() const; value_type get_final_xor_value() const; bool get_reflect_input() const; bool get_reflect_remainder() const; value_type get_interim_remainder() const; void reset( value_type new_rem = InitRem ); // External Operations void process_byte( unsigned char byte ); void process_block( void const *bytes_begin, void const *bytes_end ); void process_bytes( void const *buffer, std::size_t byte_count ); value_type checksum() const; // Operators void operator ()( unsigned char byte ); value_type operator ()() const; }; The This implementation is fast since it uses as many optimizations as practical. All of the CRC parameters are specified at compile-time as template parameters. No individual bits are considered; only whole bytes are passed. A table of interim CRC values versus byte values is pre-computed when the first object using a particular bit size, truncated polynominal, and input reflection state is processed. Computer UsageThe two class templates have different policies on where the CRC's parameters go. Both class templates use the number of bits in the CRC as the first template parameter. The theoretical computer class template has the bit count as its only template parameter, all the other CRC parameters are entered through the constructor. The optimized computer class template obtains all its CRC parameters as template parameters, and instantiated objects are usually default-constructed. The CRC parameters can be inspected at run-time with the following
member functions: The The After any construction, both CRC computers work the same way. Feeding new data to a computer is in a seperate operation(s) from extracting the current CRC value from the computer. The following table lists the feeding and extracting operations.
You can use them like this: #include <boost/crc.hpp> // for boost::crc_basic, boost::crc_optimal #include <boost/cstdint.hpp> // for boost::uint16_t #include <algorithm> // for std::for_each #include <cassert> // for assert #include <cstddef> // for std::size_t #include <iostream> // for std::cout #include <ostream> // for std::endl // Main function int main () { // This is "123456789" in ASCII unsigned char const data[] = { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 }; std::size_t const data_len = sizeof( data ) / sizeof( data[0] ); // The expected CRC for the given data boost::uint16_t const expected = 0x29B1; // Simulate CRC-CCITT boost::crc_basic<16> crc_ccitt1( 0x1021, 0xFFFF, 0, false, false ); crc_ccitt1.process_bytes( data, data_len ); assert( crc_ccitt1.checksum() == expected ); // Repeat with the optimal version (assuming a 16-bit type exists) boost::crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt2; crc_ccitt2 = std::for_each( data, data + data_len, crc_ccitt2 ); assert( crc_ccitt2() == expected ); std::cout << "All tests passed." << std::endl; return 0; } CRC Functiontemplate < std::size_t Bits, impl_def TruncPoly, impl_def InitRem, impl_def FinalXor, bool ReflectIn, bool ReflectRem > typename boost::uint_t<Bits>::fast boost::crc( void const *buffer, std::size_t byte_count ); The Augmented-CRC Functionstemplate < std::size_t Bits, impl_def TruncPoly > typename boost::uint_t<Bits>::fast boost::augmented_crc( void const *buffer, std::size_t byte_count, typename boost::uint_t<Bits>::fast initial_remainder ); template < std::size_t Bits, impl_def TruncPoly > typename boost::uint_t<Bits>::fast boost::augmented_crc( void const *buffer, std::size_t byte_count ); All the other CRC-computing function or class templates work assuming
that the division steps start immediately on the first message bits.
The two The template parameters of both versions of the function template are
the CRC's bit size ( These function templates are useful if the bytes of the CRC directly
follow the message's bytes. First, set the bytes of where the CRC will
go to zero. Then use Interruptions in the CRC data can be handled by feeding the result of
Note that for the same CRC system, the initial remainder for augmented message method will be different than for the unaugmented message method. The main exception is zero; if the augmented-CRC algorithm uses a zero initial remainder, the equivalent unaugmented-CRC algorithm will also use a zero initial remainder. Given an initial remainder for a augmented-CRC algorithm, the result from processing just zero-valued CRC bytes without any message bytes is the equivalent inital remainder for the unaugmented-CRC algorithm. An example follows: #include <boost/crc.hpp> // for boost::crc_basic, boost::augmented_crc #include <boost/cstdint.hpp> // for boost::uint16_t #include <cassert> // for assert #include <iostream> // for std::cout #include <ostream> // for std::endl // Main function int main () { using boost::uint16_t; using boost::augmented_crc; uint16_t data[6] = { 2, 4, 31, 67, 98, 0 }; uint16_t const init_rem = 0x123; uint16_t crc1 = augmented_crc<16, 0x8005>( data, sizeof(data), init_rem ); uint16_t const zero = 0; uint16_t const new_init_rem = augmented_crc<16, 0x8005>( &zero, sizeof(zero) ); boost::crc_basic<16> crc2( 0x8005, new_init_rem ); crc2.process_block( data, &data[5] ); // don't include CRC assert( crc2.checksum() == crc1 ); std::cout << "All tests passed." << std::endl; return 0; } Pre-Defined CRC SamplesFour sample CRC types are given, representing several common CRC
algorithms. For example, computations from
References
CreditsContributors
AcknowledgementsFor giving advice on compiler/C++ compliance, implementation, interface, algorithms, and bug reports:
History
Revised: 15 June 2003 Copyright 2001, 2003 Daryle Walker. Use, modification, and distribution are subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.) |