diff options
author | robot-contrib <robot-contrib@yandex-team.com> | 2023-01-19 03:17:24 +0300 |
---|---|---|
committer | robot-contrib <robot-contrib@yandex-team.com> | 2023-01-19 03:17:24 +0300 |
commit | f82da47be274e1ae3f9d755e9a9983f317d77582 (patch) | |
tree | 81e79ee21b1288934b04774a8058b822e52be6e1 | |
parent | 41ca552f4ada50d9f2b11383dc79d066afbd8bf2 (diff) | |
download | ydb-f82da47be274e1ae3f9d755e9a9983f317d77582.tar.gz |
Update contrib/restricted/boost/crc to 1.79.0
4 files changed, 1710 insertions, 511 deletions
diff --git a/contrib/restricted/boost/crc/CMakeLists.darwin.txt b/contrib/restricted/boost/crc/CMakeLists.darwin.txt index 06b5073397..2730ce7c01 100644 --- a/contrib/restricted/boost/crc/CMakeLists.darwin.txt +++ b/contrib/restricted/boost/crc/CMakeLists.darwin.txt @@ -13,7 +13,8 @@ target_include_directories(restricted-boost-crc INTERFACE ) target_link_libraries(restricted-boost-crc INTERFACE contrib-libs-cxxsupp - yutil + restricted-boost-array restricted-boost-config restricted-boost-integer + restricted-boost-type_traits ) diff --git a/contrib/restricted/boost/crc/CMakeLists.linux-aarch64.txt b/contrib/restricted/boost/crc/CMakeLists.linux-aarch64.txt index 60e4b683df..6473832eb1 100644 --- a/contrib/restricted/boost/crc/CMakeLists.linux-aarch64.txt +++ b/contrib/restricted/boost/crc/CMakeLists.linux-aarch64.txt @@ -14,7 +14,8 @@ target_include_directories(restricted-boost-crc INTERFACE target_link_libraries(restricted-boost-crc INTERFACE contrib-libs-linux-headers contrib-libs-cxxsupp - yutil + restricted-boost-array restricted-boost-config restricted-boost-integer + restricted-boost-type_traits ) diff --git a/contrib/restricted/boost/crc/CMakeLists.linux.txt b/contrib/restricted/boost/crc/CMakeLists.linux.txt index 60e4b683df..6473832eb1 100644 --- a/contrib/restricted/boost/crc/CMakeLists.linux.txt +++ b/contrib/restricted/boost/crc/CMakeLists.linux.txt @@ -14,7 +14,8 @@ target_include_directories(restricted-boost-crc INTERFACE target_link_libraries(restricted-boost-crc INTERFACE contrib-libs-linux-headers contrib-libs-cxxsupp - yutil + restricted-boost-array restricted-boost-config restricted-boost-integer + restricted-boost-type_traits ) diff --git a/contrib/restricted/boost/crc/include/boost/crc.hpp b/contrib/restricted/boost/crc/include/boost/crc.hpp index 6be5aa1d8b..c39d615a6f 100644 --- a/contrib/restricted/boost/crc/include/boost/crc.hpp +++ b/contrib/restricted/boost/crc/include/boost/crc.hpp @@ -1,16 +1,47 @@ // Boost CRC library crc.hpp header file -----------------------------------// -// Copyright 2001, 2004 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>.) +// Copyright 2001, 2004, 2011 Daryle Walker. +// Distributed under the Boost Software License, Version 1.0. (See the +// accompanying file LICENSE_1_0.txt or a copy at +// <http://www.boost.org/LICENSE_1_0.txt>.) // See <http://www.boost.org/libs/crc/> for the library's home page. +/** \file + \brief A collection of function templates and class templates that compute + various forms of Cyclic Redundancy Codes (CRCs). + + \author Daryle Walker + + \version 1.5 + + \copyright Boost Software License, version 1.0 + + Contains the declarations (and definitions) of various kinds of CRC + computation functions, function object types, and encapsulated policy types. + + \warning The sample CRC-computer types were just checked against the + <a href="http://regregex.bbcmicro.net/crc-catalogue.htm">Catalogue of + parametrised CRC algorithms</a>. New type aliases were added where I got + a standard wrong. However, the mistaken <code>typedef</code>s are still + there for backwards compatibility. + \note There are references to the <i>Rocksoft™ Model CRC + Algorithm</i>, as described within \"A Painless Guide to CRC Error + Detection Algorithms,\" linked from \"<a + href="http://www.ross.net/crc/crcpaper.html">CRC: A Paper On CRCs</a>\" by + Ross Williams. It will be abbreviated \"RMCA\" in other documentation + blocks. + */ + #ifndef BOOST_CRC_HPP #define BOOST_CRC_HPP -#include <boost/config.hpp> // for BOOST_STATIC_CONSTANT, etc. -#include <boost/integer.hpp> // for boost::uint_t +#include <boost/array.hpp> // for boost::array +#include <boost/config.hpp> // for BOOST_STATIC_CONSTANT, etc. +#include <boost/cstdint.hpp> // for UINTMAX_C, boost::uintmax_t +#include <boost/integer.hpp> // for boost::uint_t +#include <boost/type_traits/conditional.hpp> +#include <boost/type_traits/integral_constant.hpp> #include <climits> // for CHAR_BIT, etc. #include <cstddef> // for std::size_t @@ -22,78 +53,58 @@ // on the CRC's bit count. This macro expresses that type in a compact // form, but also allows an alternate type for compilers that don't support // dependent types (in template value-parameters). -#if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS) || (defined(BOOST_MSVC) && (BOOST_MSVC <= 1300))) +#if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS)) #define BOOST_CRC_PARM_TYPE typename ::boost::uint_t<Bits>::fast #else #define BOOST_CRC_PARM_TYPE unsigned long #endif -// Some compilers [MS VC++ 6] cannot correctly set up several versions of a -// function template unless every template argument can be unambiguously -// deduced from the function arguments. (The bug is hidden if only one version -// is needed.) Since all of the CRC function templates have this problem, the -// workaround is to make up a dummy function argument that encodes the template -// arguments. Calls to such template functions need all their template -// arguments explicitly specified. At least one compiler that needs this -// workaround also needs the default value for the dummy argument to be -// specified in the definition. -#if defined(__GNUC__) || !defined(BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS) -#define BOOST_CRC_DUMMY_PARM_TYPE -#define BOOST_CRC_DUMMY_INIT -#define BOOST_ACRC_DUMMY_PARM_TYPE -#define BOOST_ACRC_DUMMY_INIT -#else -namespace boost { namespace detail { - template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, - BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, - bool ReflectIn, bool ReflectRem > - struct dummy_crc_argument { }; -} } -#define BOOST_CRC_DUMMY_PARM_TYPE , detail::dummy_crc_argument<Bits, \ - TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem> *p_ -#define BOOST_CRC_DUMMY_INIT BOOST_CRC_DUMMY_PARM_TYPE = 0 -#define BOOST_ACRC_DUMMY_PARM_TYPE , detail::dummy_crc_argument<Bits, \ - TruncPoly, 0, 0, false, false> *p_ -#define BOOST_ACRC_DUMMY_INIT BOOST_ACRC_DUMMY_PARM_TYPE = 0 -#endif - - namespace boost { // Forward declarations ----------------------------------------------------// +//! Bit-wise CRC computer template < std::size_t Bits > class crc_basic; +//! Table-driven CRC computer, usable as a function object template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u, BOOST_CRC_PARM_TYPE InitRem = 0u, BOOST_CRC_PARM_TYPE FinalXor = 0u, bool ReflectIn = false, bool ReflectRem = false > class crc_optimal; +//! Compute the (unaugmented) CRC of a memory block template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > typename uint_t<Bits>::fast crc( void const *buffer, - std::size_t byte_count - BOOST_CRC_DUMMY_PARM_TYPE ); + std::size_t byte_count); +//! Compute the CRC of a memory block, with any augmentation provided by user template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly > typename uint_t<Bits>::fast augmented_crc( void const *buffer, - std::size_t byte_count, typename uint_t<Bits>::fast initial_remainder - BOOST_ACRC_DUMMY_PARM_TYPE ); - -template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly > - typename uint_t<Bits>::fast augmented_crc( void const *buffer, - std::size_t byte_count - BOOST_ACRC_DUMMY_PARM_TYPE ); + std::size_t byte_count, + typename uint_t<Bits>::fast initial_remainder = 0u); +//! Computation type for ARC|CRC-16|CRC-IBM|CRC-16/ARC|CRC-16/LHA standard typedef crc_optimal<16, 0x8005, 0, 0, true, true> crc_16_type; -typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_type; +//! Computation type for CRC-16/CCITT-FALSE standard +typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false> crc_ccitt_false_t; +//! Computation type for the CRC mistakenly called the CCITT standard +typedef crc_ccitt_false_t crc_ccitt_type; +//! Computation type for the actual +//! KERMIT|CRC-16/CCITT|CRC-16/CCITT-TRUE|CRC-CCITT standard +typedef crc_optimal<16, 0x1021, 0, 0, true, true> crc_ccitt_true_t; +//! Computation type that I mistakenly called the XMODEM standard; it inverts +//! both reflection parameters and reflects the truncated divisor (Don't use?!) typedef crc_optimal<16, 0x8408, 0, 0, true, true> crc_xmodem_type; +//! Computation type for the actual XMODEM|ZMODEM|CRC-16/ACORN standard +typedef crc_optimal<16, 0x1021, 0, 0, false, false> crc_xmodem_t; +//! Computation type for CRC-32|CRC-32/ADCCP|PKZIP standard typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> crc_32_type; @@ -101,81 +112,90 @@ typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true> // Forward declarations for implementation detail stuff --------------------// // (Just for the stuff that will be needed for the next two sections) +//! \cond namespace detail { - template < std::size_t Bits > - struct mask_uint_t; - - template < > - struct mask_uint_t< std::numeric_limits<unsigned char>::digits >; - - #if USHRT_MAX > UCHAR_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned short>::digits >; - #endif + //! Mix-in class to add a possibly-reflecting member function + template < int BitLength, bool DoIt, int Id = 0 > + class possible_reflector; - #if UINT_MAX > USHRT_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned int>::digits >; - #endif - - #if ULONG_MAX > UINT_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned long>::digits >; - #endif - - template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect > - struct crc_table_t; - - template < std::size_t Bits, bool DoReflect > - class crc_helper; - - #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - template < std::size_t Bits > - class crc_helper< Bits, false >; - #endif + //! Mix-in class for byte-fed, table-driven CRC algorithms + template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect, + int Id = 0 > + class crc_driver; } // namespace detail +//! \endcond // Simple cyclic redundancy code (CRC) class declaration -------------------// +/** Objects of this type compute the CRC checksum of submitted data, where said + data can be entered piecemeal through several different kinds of groupings. + Modulo-2 polynomial division steps are always performed bit-wise, without + the use of pre-computation tables. Said division uses the altered + algorithm, so any data has to be unaugmented. + + \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from + the RMCA) + */ template < std::size_t Bits > class crc_basic { - // Implementation type - typedef detail::mask_uint_t<Bits> masking_type; - public: // Type - typedef typename masking_type::least value_type; + /** \brief The register type used for computations + + This type is used for CRC calculations and is the type for any returned + checksums and returned or submitted remainders, (truncated) divisors, or + XOR masks. It is a built-in unsigned integer type. + */ + typedef typename boost::uint_t<Bits>::fast value_type; // Constant for the template parameter + //! A copy of \a Bits provided for meta-programming purposes BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits ); - // Constructor - explicit crc_basic( value_type truncated_polynominal, + // Constructor (use the automatic copy-ctr, move-ctr, and dtr) + //! Create a computer, separately listing each needed parameter + explicit crc_basic( value_type truncated_polynomial, value_type initial_remainder = 0, value_type final_xor_value = 0, bool reflect_input = false, bool reflect_remainder = false ); // Internal Operations + //! Return the (truncated) polynomial divisor value_type get_truncated_polynominal() const; + //! Return what the polynomial remainder was set to during construction value_type get_initial_remainder() const; + //! Return the XOR-mask used during output processing value_type get_final_xor_value() const; + //! Check if input-bytes will be reflected before processing bool get_reflect_input() const; + //! Check if the remainder will be reflected during output processing bool get_reflect_remainder() const; + //! Return the remainder based from already-processed bits value_type get_interim_remainder() const; + //! Change the interim remainder to a new value void reset( value_type new_rem ); + //! Change the interim remainder back to the initial value void reset(); // External Operations + //! Submit a single bit for input processing void process_bit( bool bit ); - void process_bits( unsigned char bits, std::size_t bit_count ); + //! Submit the lowest \a bit_length bits of a byte for input processing + void process_bits( unsigned char bits, std::size_t bit_length ); + //! Submit a single byte for input processing void process_byte( unsigned char byte ); + //! Submit a memory block for input processing, iterator-pair style void process_block( void const *bytes_begin, void const *bytes_end ); + //! Submit a memory block for input processing, pointer-and-size style void process_bytes( void const *buffer, std::size_t byte_count ); + //! Return the checksum of the already-processed bits value_type checksum() const; private: @@ -189,67 +209,106 @@ private: // Optimized cyclic redundancy code (CRC) class declaration ----------------// +/** Objects of this type compute the CRC checksum of submitted data, where said + data can be entered piecemeal through several different kinds of groupings. + Modulo-2 polynomial division steps are performed byte-wise, aided by the use + of pre-computation tables. Said division uses the altered algorithm, so any + data has to be unaugmented. + + \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from + the RMCA) + \tparam TruncPoly The lowest coefficients of the divisor polynomial. The + highest-order coefficient is omitted and always assumed to be 1. Defaults + to \c 0, i.e. the only non-zero term is the implicit one for + x<sup><var>Bits</var></sup>. (\e Poly from the RMCA) + \tparam InitRem The (unaugmented) initial state of the polynomial + remainder. Defaults to \c 0 if omitted. (\e Init from the RMCA) + \tparam FinalXor The (XOR) bit-mask to be applied to the output remainder, + after possible reflection but before returning. Defaults to \c 0 (i.e. no + bit changes) if omitted. (\e XorOut from the RMCA) + \tparam ReflectIn If \c true, input bytes are read lowest-order bit first, + otherwise highest-order bit first. Defaults to \c false if omitted. + (\e RefIn from the RMCA) + \tparam ReflectRem If \c true, the output remainder is reflected before the + XOR-mask. Defaults to \c false if omitted. (\e RefOut from the RMCA) + + \todo Get rid of the default value for \a TruncPoly. Choosing a divisor is + an important decision with many factors, so a default is never useful, + especially a bad one. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > class crc_optimal { - // Implementation type - typedef detail::mask_uint_t<Bits> masking_type; - public: // Type - typedef typename masking_type::fast value_type; + //! \copydoc boost::crc_basic::value_type + typedef typename boost::uint_t<Bits>::fast value_type; // Constants for the template parameters + //! \copydoc boost::crc_basic::bit_count BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits ); + //! A copy of \a TruncPoly provided for meta-programming purposes BOOST_STATIC_CONSTANT( value_type, truncated_polynominal = TruncPoly ); + //! A copy of \a InitRem provided for meta-programming purposes BOOST_STATIC_CONSTANT( value_type, initial_remainder = InitRem ); + //! A copy of \a FinalXor provided for meta-programming purposes BOOST_STATIC_CONSTANT( value_type, final_xor_value = FinalXor ); + //! A copy of \a ReflectIn provided for meta-programming purposes BOOST_STATIC_CONSTANT( bool, reflect_input = ReflectIn ); + //! A copy of \a ReflectRem provided for meta-programming purposes BOOST_STATIC_CONSTANT( bool, reflect_remainder = ReflectRem ); - // Constructor - explicit crc_optimal( value_type init_rem = InitRem ); + // Constructor (use the automatic copy-ctr, move-ctr, and dtr) + //! Create a computer, giving an initial remainder if desired + explicit crc_optimal( value_type init_rem = initial_remainder ); // Internal Operations + //! \copybrief boost::crc_basic::get_truncated_polynominal value_type get_truncated_polynominal() const; + //! \copybrief boost::crc_basic::get_initial_remainder value_type get_initial_remainder() const; + //! \copybrief boost::crc_basic::get_final_xor_value value_type get_final_xor_value() const; + //! \copybrief boost::crc_basic::get_reflect_input bool get_reflect_input() const; + //! \copybrief boost::crc_basic::get_reflect_remainder bool get_reflect_remainder() const; + //! \copybrief boost::crc_basic::get_interim_remainder value_type get_interim_remainder() const; - void reset( value_type new_rem = InitRem ); + //! Change the interim remainder to either a given value or the initial one + void reset( value_type new_rem = initial_remainder ); // External Operations + //! \copybrief boost::crc_basic::process_byte void process_byte( unsigned char byte ); + //! \copybrief boost::crc_basic::process_block void process_block( void const *bytes_begin, void const *bytes_end ); + //! \copybrief boost::crc_basic::process_bytes void process_bytes( void const *buffer, std::size_t byte_count ); + //! \copybrief boost::crc_basic::checksum value_type checksum() const; // Operators + //! Submit a single byte for input processing, suitable for the STL void operator ()( unsigned char byte ); + //! Return the checksum of the already-processed bits, suitable for the STL value_type operator ()() const; private: - // The implementation of output reflection depends on both reflect states. - BOOST_STATIC_CONSTANT( bool, reflect_output = (ReflectRem != ReflectIn) ); - - #ifndef __BORLANDC__ - #define BOOST_CRC_REF_OUT_VAL reflect_output - #else - typedef crc_optimal self_type; - #define BOOST_CRC_REF_OUT_VAL (self_type::reflect_output) - #endif - - // More implementation types - typedef detail::crc_table_t<Bits, TruncPoly, ReflectIn> crc_table_type; - typedef detail::crc_helper<Bits, ReflectIn> helper_type; - typedef detail::crc_helper<Bits, BOOST_CRC_REF_OUT_VAL> reflect_out_type; - - #undef BOOST_CRC_REF_OUT_VAL + // Implementation types + // (Processing for reflected input gives reflected remainders, so you only + // have to apply output-reflection if Reflect-Remainder doesn't match + // Reflect-Input.) + typedef detail::possible_reflector<Bits, ReflectIn> reflect_i_type; + typedef detail::crc_driver<Bits, TruncPoly, ReflectIn> crc_table_type; + typedef detail::possible_reflector<Bits, ReflectRem != ReflectIn> + reflect_o_type; // Member data value_type rem_; @@ -259,390 +318,1264 @@ private: // Implementation detail stuff ---------------------------------------------// +//! \cond namespace detail { - // Forward declarations for more implementation details - template < std::size_t Bits > - struct high_uint_t; + /** \brief Meta-programming integral constant for a single-bit bit-mask + + Generates a compile-time constant for a bit-mask that affects a single + bit. The \c value will be 2<sup><var>BitIndex</var></sup>. The \c type + will be the smallest built-in unsigned integer type that can contain the + value, unless there's a built-in type that the system can handle easier, + then the \c type will be smallest fast-handled unsigned integer type. + + \pre 0 \<= BitIndex \< \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam BitIndex The place of the sole set bit. + */ + template < int BitIndex > + struct high_bit_mask_c + : boost::integral_constant<typename boost::uint_t< BitIndex + 1 >::fast, + ( UINTMAX_C(1) << BitIndex )> + {}; + + /** \brief Meta-programming integral constant for a lowest-bits bit-mask + + Generates a compile-time constant for a bit-mask that affects the lowest + bits. The \c value will be 2<sup><var>BitCount</var></sup> - 1. The + \c type will be the smallest built-in unsigned integer type that can + contain the value, unless there's a built-in type that the system can + handle easier, then the \c type will be smallest fast-handled unsigned + integer type. + + \pre 0 \<= BitCount \<= \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam BitCount The number of lowest-placed bits set. + */ + template < int BitCount > + struct low_bits_mask_c + : boost::integral_constant<typename boost::uint_t< BitCount >::fast, ( + BitCount ? (( (( UINTMAX_C(1) << (BitCount - 1) ) - 1u) << 1 ) | + UINTMAX_C( 1 )) : 0u )> + {}; + + /** \brief Reflects the bits of a number + + Reverses the order of the given number of bits within a value. For + instance, if the given reflect count is 5, then the bit values for the + 16- and 1-place will switch and the 8- and 2-place will switch, leaving + the other bits alone. (The 4-place bit is in the middle, so it wouldn't + change.) + + \pre \a Unsigned is a built-in unsigned integer type + \pre 0 \< word_length \<= \c std\::numeric_limits\<Unsigned\>\::digits + + \tparam Unsigned The type of \a x. + + \param x The value to be (partially) reflected. + \param word_length The number of low-order bits to reflect. Defaults + to the total number of value bits in \a Unsigned. + + \return The (partially) reflected value. + + \todo Check if this is the fastest way. + */ + template < typename Unsigned > + Unsigned reflect_unsigned( Unsigned x, int word_length + = std::numeric_limits<Unsigned>::digits ) + { + for ( Unsigned l = 1u, h = l << (word_length - 1) ; h > l ; h >>= 1, l + <<= 1 ) + { + Unsigned const m = h | l, t = x & m; + + if ( (t == h) || (t == l) ) + x ^= m; + } + + return x; + } - template < std::size_t Bits > - struct reflector; + /** \brief Make a byte-to-byte-reflection map + Creates a mapping array so the results can be cached. Uses + #reflect_unsigned to generate the element values. - // Traits class for mask; given the bit number - // (1-based), get the mask for that bit by itself. - template < std::size_t Bits > - struct high_uint_t - : boost::uint_t< Bits > + \return An array <var>a</var> such that, for a given byte value + <var>i</var>, <code><var>a</var>[ <var>i</var> ]</code> resolves to + the reflected value of <var>i</var>. + */ + boost::array< unsigned char, (UINTMAX_C( 1 ) << CHAR_BIT) > + inline make_byte_reflection_table() { - typedef boost::uint_t<Bits> base_type; - typedef typename base_type::least least; - typedef typename base_type::fast fast; + boost::array<unsigned char, ( UINTMAX_C(1) << CHAR_BIT )> result; + unsigned char i = 0u; -#if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243 - static const least high_bit = 1ul << ( Bits - 1u ); - static const fast high_bit_fast = 1ul << ( Bits - 1u ); -#else - BOOST_STATIC_CONSTANT( least, high_bit = (least( 1u ) << ( Bits - - 1u )) ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = (fast( 1u ) << ( Bits - - 1u )) ); -#endif + do + result[ i ] = reflect_unsigned( i ); + while ( ++i ); + return result; + } - }; // boost::detail::high_uint_t + /** \brief Reflects the bits of a single byte + Reverses the order of all the bits within a value. For instance, the + bit values for the 2<sup><code>CHAR_BIT</code> - 1</sup>- and 1-place + will switch and the 2<sup><code>CHAR_BIT</code> - 2</sup>- and 2-place + will switch, etc. - // Reflection routine class wrapper - // (since MS VC++ 6 couldn't handle the unwrapped version) - template < std::size_t Bits > - struct reflector - { - typedef typename boost::uint_t<Bits>::fast value_type; + \param x The byte value to be reflected. - static value_type reflect( value_type x ); + \return The reflected value. - }; // boost::detail::reflector + \note Since this could be the most common type of reflection, and the + number of states is relatively small, the implementation pre-computes + and uses a table of all the results. + */ + inline unsigned char reflect_byte( unsigned char x ) + { + static boost::array<unsigned char, ( UINTMAX_C(1) << CHAR_BIT )> const + table = make_byte_reflection_table(); + + return table[ x ]; + } - // Function that reflects its argument - template < std::size_t Bits > - typename reflector<Bits>::value_type - reflector<Bits>::reflect - ( - typename reflector<Bits>::value_type x - ) + /** \brief Reflects some bits within a single byte + + Like #reflect_unsigned, except it takes advantage of any (long-term) + speed gains #reflect_byte may bring. + + \pre 0 \< \a word_length \<= \c CHAR_BIT + + \param x The value to be (partially) reflected. + \param word_length The number of low-order bits to reflect. + + \return The (partially) reflected value. + */ + inline unsigned char reflect_sub_byte( unsigned char x, int word_length ) + { return reflect_byte(x) >> (CHAR_BIT - word_length); } + + /** \brief Possibly reflects the bits of a number + + Reverses the order of the given number of bits within a value. For + instance, if the given reflect count is 5, then the bit values for the + 16- and 1-place will switch and the 8- and 2-place will switch, leaving + the other bits alone. (The 4-place bit is in the middle, so it wouldn't + change.) This variant function allows the reflection be controlled by + an extra parameter, in case the decision to use reflection is made at + run-time. + + \pre \a Unsigned is a built-in unsigned integer type + \pre 0 \< word_length \<= \c std\::numeric_limits\<Unsigned\>\::digits + + \tparam Unsigned The type of \a x. + + \param x The value to be (partially) reflected. + \param reflect Controls whether \a x is actually reflected (\c true) or + left alone (\c false). + \param word_length The number of low-order bits to reflect. Defaults + to the total number of value bits in \a Unsigned. + + \return The possibly (partially) reflected value. + */ + template < typename Unsigned > + inline + Unsigned reflect_optionally( Unsigned x, bool reflect, int word_length + = std::numeric_limits<Unsigned>::digits ) + { return reflect ? reflect_unsigned(x, word_length) : x; } + + /** \brief Possibly reflects the bits of a single byte + + Uses #reflect_byte (if \a reflect is \c true). + + \param x The byte value to be (possibly) reflected. + \param reflect Whether (\c true) or not (\c false) \a x is reflected. + + \return <code><var>reflect</var> ? reflect_byte(<var>x</var>) : + <var>x</var></code> + */ + inline + unsigned char reflect_byte_optionally( unsigned char x, bool reflect ) + { return reflect ? reflect_byte(x) : x; } + + /** \brief Update a CRC remainder by several bits, assuming a non-augmented + message + + Performs several steps of division required by the CRC algorithm, giving + a new remainder polynomial based on the divisor polynomial and the + synthesized dividend polynomial (from the old remainder and the + newly-provided input). The computations assume that the CRC is directly + exposed from the remainder, without any zero-valued bits augmented to + the message bits. + + \pre \a Register and \a Word are both built-in unsigned integer types + \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\> + \::digits + \pre 0 \< \a word_length \<= std\::numeric_limits\<\a Word\>\::digits + + \tparam Register The type used for representing the remainder and + divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i>. + \tparam Word The type used for storing the incoming terms of the + dividend modulo-2 polynomial. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i> when \a reflect is + \c false, and the coefficient of <i>x<sup><var>word_length</var> - 1 - + i</sup></i> otherwise. + + \param[in] register_length The number of significant low-order bits + to be used from \a Register values. It is the order of the modulo-2 + polynomial remainder and one less than the divisor's order. + \param[in,out] remainder The upper part of the dividend polynomial + before division, and the remainder polynomial after. + \param[in] new_dividend_bits The coefficients for the next + \a word_length lowest terms of the dividend polynomial. + \param[in] truncated_divisor The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \param[in] word_length The number of lowest-order bits to read from + \a new_dividend_bits. + \param[in] reflect If \c false, read from the highest-order marked + bit from \a new_dividend_bits and go down, as normal. Otherwise, + proceed from the lowest-order bit and go up. + + \note This routine performs a modulo-2 polynomial division variant. + The exclusive-or operations are applied in a different order, since + that kind of operation is commutative and associative. It also + assumes that the zero-valued augment string was applied before this + step, which means that the updated remainder can be directly used as + the final CRC. + */ + template < typename Register, typename Word > + void crc_modulo_word_update( int register_length, Register &remainder, Word + new_dividend_bits, Register truncated_divisor, int word_length, bool + reflect ) { - value_type reflection = 0; - value_type const one = 1; + // Create this masking constant outside the loop. + Register const high_bit_mask = UINTMAX_C(1) << (register_length - 1); + + // The natural reading order for division is highest digit/bit first. + // The "reflect" parameter switches this. However, building a bit mask + // for the lowest bit is the easiest.... + new_dividend_bits = reflect_optionally( new_dividend_bits, !reflect, + word_length ); - for ( std::size_t i = 0 ; i < Bits ; ++i, x >>= 1 ) + // Perform modulo-2 division for each new dividend input bit + for ( int i = word_length ; i ; --i, new_dividend_bits >>= 1 ) { - if ( x & one ) - { - reflection |= ( one << (Bits - 1u - i) ); - } + // compare the new bit with the remainder's highest + remainder ^= ( new_dividend_bits & 1u ) ? high_bit_mask : 0u; + + // perform modulo-2 division + bool const quotient = remainder & high_bit_mask; + + remainder <<= 1; + remainder ^= quotient ? truncated_divisor : 0u; + + // The quotient isn't used for anything, so don't keep it. } + } - return reflection; + /** \brief Update a CRC remainder by a single bit, assuming a non-augmented + message + + Performs the next step of division required by the CRC algorithm, giving + a new remainder polynomial based on the divisor polynomial and the + synthesized dividend polynomial (from the old remainder and the + newly-provided input). The computations assume that the CRC is directly + exposed from the remainder, without any zero-valued bits augmented to + the message bits. + + \pre \a Register is a built-in unsigned integer type + \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\> + \::digits + + \tparam Register The type used for representing the remainder and + divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i>. + + \param[in] register_length The number of significant low-order bits + to be used from \a Register values. It is the order of the modulo-2 + polynomial remainder and one less than the divisor's order. + \param[in,out] remainder The upper part of the dividend polynomial + before division, and the remainder polynomial after. + \param[in] new_dividend_bit The coefficient for the constant term + of the dividend polynomial. + \param[in] truncated_divisor The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + + \note This routine performs a modulo-2 polynomial division variant. + The exclusive-or operations are applied in a different order, since + that kind of operation is commutative and associative. It also + assumes that the zero-valued augment string was applied before this + step, which means that the updated remainder can be directly used as + the final CRC. + */ + template < typename Register > + inline void crc_modulo_update( int register_length, Register &remainder, + bool new_dividend_bit, Register truncated_divisor ) + { + crc_modulo_word_update( register_length, remainder, + static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false ); } + /** \brief Update a CRC remainder by several bits, assuming an augmented + message + + Performs several steps of division required by the CRC algorithm, giving + a new remainder polynomial based on the divisor polynomial and the + synthesized dividend polynomial (from the old remainder and the + newly-provided input). The computations assume that a zero-valued + string of bits will be appended to the message before extracting the + CRC. + + \pre \a Register and \a Word are both built-in unsigned integer types + \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\> + \::digits + \pre 0 \< \a word_length \<= std\::numeric_limits\<\a Word\>\::digits + + \tparam Register The type used for representing the remainder and + divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i>. + \tparam Word The type used for storing the incoming terms of the + dividend modulo-2 polynomial. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i> when \a reflect is + \c false, and the coefficient of <i>x<sup><var>word_length</var> - 1 - + i</sup></i> otherwise. + + \param[in] register_length The number of significant low-order bits + to be used from \a Register values. It is the order of the modulo-2 + polynomial remainder and one less than the divisor's order. + \param[in,out] remainder The upper part of the dividend polynomial + before division, and the remainder polynomial after. + \param[in] new_dividend_bits The coefficients for the next + \a word_length lowest terms of the dividend polynomial. + \param[in] truncated_divisor The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \param[in] word_length The number of lowest-order bits to read from + \a new_dividend_bits. + \param[in] reflect If \c false, read from the highest-order marked + bit from \a new_dividend_bits and go down, as normal. Otherwise, + proceed from the lowest-order bit and go up. + + \note This routine performs straight-forward modulo-2 polynomial + division. It assumes that an augment string will be processed at the + end of the message bits before doing CRC analysis. + \todo Use this function somewhere so I can test it. + */ + template < typename Register, typename Word > + void augmented_crc_modulo_word_update( int register_length, Register + &remainder, Word new_dividend_bits, Register truncated_divisor, int + word_length, bool reflect ) + { + // Create this masking constant outside the loop. + Register const high_bit_mask = UINTMAX_C(1) << (register_length - 1); + + // The natural reading order for division is highest digit/bit first. + // The "reflect" parameter switches this. However, building a bit mask + // for the lowest bit is the easiest.... + new_dividend_bits = reflect_optionally( new_dividend_bits, not reflect, + word_length ); + + // Perform modulo-2 division for each new dividend input bit + for ( int i = word_length ; i ; --i, new_dividend_bits >>= 1 ) + { + bool const quotient = remainder & high_bit_mask; - // Traits class for masks; given the bit number (1-based), - // get the mask for that bit and its lower bits. - template < std::size_t Bits > - struct mask_uint_t - : high_uint_t< Bits > + remainder <<= 1; + remainder |= new_dividend_bits & 1u; + remainder ^= quotient ? truncated_divisor : 0u; + + // The quotient isn't used for anything, so don't keep it. + } + } + + /** \brief Update a CRC remainder by a single bit, assuming an augmented + message + + Performs the next step of division required by the CRC algorithm, giving + a new remainder polynomial based on the divisor polynomial and the + synthesized dividend polynomial (from the old remainder and the + newly-provided input). The computations assume that a zero-valued + string of bits will be appended to the message before extracting the + CRC. + + \pre \a Register is a built-in unsigned integer type + \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\> + \::digits + + \tparam Register The type used for representing the remainder and + divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i>. + + \param[in] register_length The number of significant low-order bits + to be used from \a Register values. It is the order of the modulo-2 + polynomial remainder and one less than the divisor's order. + \param[in,out] remainder The upper part of the dividend polynomial + before division, and the remainder polynomial after. + \param[in] new_dividend_bit The coefficient for the constant term + of the dividend polynomial. + \param[in] truncated_divisor The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + + \note This routine performs straight-forward modulo-2 polynomial + division. It assumes that an augment string will be processed at the + end of the message bits before doing CRC analysis. + \todo Use this function somewhere so I can test it. + */ + template < typename Register > + inline void augmented_crc_modulo_update( int register_length, Register + &remainder, bool new_dividend_bit, Register truncated_divisor ) { - typedef high_uint_t<Bits> base_type; - typedef typename base_type::least least; - typedef typename base_type::fast fast; - - #ifndef __BORLANDC__ - using base_type::high_bit; - using base_type::high_bit_fast; - #else - BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast ); - #endif - -#if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243 - static const least sig_bits = (~( ~( 0ul ) << Bits )) ; -#else - BOOST_STATIC_CONSTANT( least, sig_bits = (~( ~(least( 0u )) << Bits )) ); -#endif -#if defined(__GNUC__) && __GNUC__ == 4 && __GNUC_MINOR__ == 0 && __GNUC_PATCHLEVEL__ == 2 - // Work around a weird bug that ICEs the compiler in build_c_cast - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = static_cast<fast>(sig_bits) ); -#else - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); -#endif - }; // boost::detail::mask_uint_t + augmented_crc_modulo_word_update( register_length, remainder, + static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false ); + } + + /** \brief A mix-in class that returns its argument + + This class template makes a function object that returns its argument + as-is. It's one case for #possible_reflector. - template < > - struct mask_uint_t< std::numeric_limits<unsigned char>::digits > - : high_uint_t< std::numeric_limits<unsigned char>::digits > + \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam BitLength How many significant bits arguments have. + */ + template < int BitLength > + class non_reflector { - typedef high_uint_t<std::numeric_limits<unsigned char>::digits> - base_type; - typedef base_type::least least; - typedef base_type::fast fast; - - #ifndef __BORLANDC__ - using base_type::high_bit; - using base_type::high_bit_fast; - #else - BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast ); - #endif - - BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) ); - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); - - }; // boost::detail::mask_uint_t - - #if USHRT_MAX > UCHAR_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned short>::digits > - : high_uint_t< std::numeric_limits<unsigned short>::digits > + public: + /** \brief The type to check for specialization + + This is a Boost integral constant indicating that this class + does not reflect its input values. + */ + typedef boost::false_type is_reflecting_type; + /** \brief The type to check for register bit length + + This is a Boost integral constant indicating how many + significant bits won't actually be reflected. + */ + typedef boost::integral_constant< int, BitLength > width_c; + /** \brief The type of (not-)reflected values + + This type is the input and output type for the (possible-) + reflection function, which does nothing here. + */ + typedef typename boost::uint_t< BitLength >::fast value_type; + + /** \brief Does nothing + + Returns the given value, not reflecting any part of it. + + \param x The value to not be reflected. + + \return \a x + */ + inline static value_type reflect_q( value_type x ) + { return x; } + }; + + /** \brief A mix-in class that reflects (the lower part of) its argument, + generally for types larger than a byte + + This class template makes a function object that returns its argument + after reflecting its lower-order bits. It's one sub-case for + #possible_reflector. + + \pre \c CHAR_BIT \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t + \>\::digits + + \tparam BitLength How many significant bits arguments have. + */ + template < int BitLength > + class super_byte_reflector { - typedef high_uint_t<std::numeric_limits<unsigned short>::digits> - base_type; - typedef base_type::least least; - typedef base_type::fast fast; - - #ifndef __BORLANDC__ - using base_type::high_bit; - using base_type::high_bit_fast; - #else - BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast ); - #endif - - BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) ); - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); - - }; // boost::detail::mask_uint_t - #endif - - #if UINT_MAX > USHRT_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned int>::digits > - : high_uint_t< std::numeric_limits<unsigned int>::digits > + public: + /** \brief The type to check for specialization + + This is a Boost integral constant indicating that this class + does reflect its input values. + */ + typedef boost::true_type is_reflecting_type; + /** \brief The type to check for register bit length + + This is a Boost integral constant indicating how many + significant bits will be reflected. + */ + typedef boost::integral_constant< int, BitLength > width_c; + /** \brief The type of reflected values + + This is both the input and output type for the reflection function. + */ + typedef typename boost::uint_t< BitLength >::fast value_type; + + /** \brief Reflect (part of) the given value + + Reverses the order of the given number of bits within a value, + using #reflect_unsigned. + + \param x The value to be (partially) reflected. + + \return ( <var>x</var> & + ~(2<sup><var>width_c</var>\::value</sup> - 1) ) | REFLECT( + <var>x</var> & (2<sup><var>width_c</var>\::value</sup> - + 1) ) + */ + inline static value_type reflect_q( value_type x ) + { return reflect_unsigned(x, width_c::value); } + }; + + /** \brief A mix-in class that reflects (the lower part of) its argument, + generally for bytes + + This class template makes a function object that returns its argument + after reflecting its lower-order bits. It's one sub-case for + #possible_reflector. + + \pre 0 \< \a BitLength \<= \c CHAR_BIT + + \tparam BitLength How many significant bits arguments have. + */ + template < int BitLength > + class sub_type_reflector { - typedef high_uint_t<std::numeric_limits<unsigned int>::digits> - base_type; - typedef base_type::least least; - typedef base_type::fast fast; - - #ifndef __BORLANDC__ - using base_type::high_bit; - using base_type::high_bit_fast; - #else - BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast ); - #endif - - BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) ); - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); - - }; // boost::detail::mask_uint_t - #endif - - #if ULONG_MAX > UINT_MAX - template < > - struct mask_uint_t< std::numeric_limits<unsigned long>::digits > - : high_uint_t< std::numeric_limits<unsigned long>::digits > + public: + /** \brief The type to check for specialization + + This is a Boost integral constant indicating that this class + does reflect its input values. + */ + typedef boost::true_type is_reflecting_type; + /** \brief The type to check for register bit length + + This is a Boost integral constant indicating how many + significant bits will be reflected. + */ + typedef boost::integral_constant< int, BitLength > width_c; + /** \brief The type of reflected values + + This is both the input and output type for the reflection function. + */ + typedef unsigned char value_type; + + /** \brief Reflect (part of) the given value + + Reverses the order of the given number of bits within a value, + using #reflect_sub_byte. + + \param x The value to be (partially) reflected. + + \return ( <var>x</var> & + ~(2<sup><var>width_c</var>\::value</sup> - 1) ) | REFLECT( + <var>x</var> & (2<sup><var>width_c</var>\::value</sup> - + 1) ) + */ + inline static value_type reflect_q( value_type x ) + { return reflect_sub_byte(x, width_c::value); } + }; + + /** \brief A mix-in class that reflects (the lower part of) its argument + + This class template makes a function object that returns its argument + after reflecting its lower-order bits. It's one case for + #possible_reflector. + + \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam BitLength How many significant bits arguments have. + */ + template < int BitLength > + class reflector + : public boost::conditional< (BitLength > CHAR_BIT), + super_byte_reflector<BitLength>, sub_type_reflector<BitLength> >::type + { }; + + /** This class template adds a member function #reflect_q that will + conditionally reflect its first argument, controlled by a compile-time + parameter. + + \pre 0 \< \a BitLength \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam BitLength How many significant bits arguments have. + \tparam DoIt \c true if #reflect_q will reflect, \c false if it should + return its argument unchanged. + \tparam Id An extra differentiator if multiple copies of this class + template are mixed-in as base classes. Defaults to 0 if omitted. + */ + template < int BitLength, bool DoIt, int Id > + class possible_reflector + : public boost::conditional< DoIt, reflector<BitLength>, + non_reflector<BitLength> >::type { - typedef high_uint_t<std::numeric_limits<unsigned long>::digits> - base_type; - typedef base_type::least least; - typedef base_type::fast fast; + public: + /** \brief The type to check for ID - #ifndef __BORLANDC__ - using base_type::high_bit; - using base_type::high_bit_fast; - #else - BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit ); - BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast ); - #endif + This is a Boost integral constant indicating what ID number this + instantiation used. + */ + typedef boost::integral_constant<int, Id> id_type; + }; - BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) ); - BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) ); + /** \brief Find the composite remainder update effect from a fixed bit + sequence, for each potential sequence combination. + + For each value between 0 and 2<sup><var>SubOrder</var></sup> - 1, + computes the XOR mask corresponding to the composite effect they update + the incoming remainder, which is the upper part of the dividend that + gets (partially) pushed out of its register by the incoming value's + bits. The composite value merges the \"partial products\" from each bit + of the value being updated individually. + + \pre \a Register is a built-in unsigned integer type + \pre 0 \< \a SubOrder \<= \a register_length \<= + std\::numeric_limits\<\a Register\>\::digits + + \tparam SubOrder The number of low-order significant bits of the trial + new dividends. + \tparam Register The type used for representing the remainder and + divisor modulo-2 polynomials. The bit at <code>2<sup>i</sup></code> + is used as the coefficient of <i>x<sup>i</sup></i>. + + \param[in] register_length The number of significant low-order bits + to be used from \a Register values. It is the order of the modulo-2 + polynomial remainder and one less than the divisor's order. + \param[in] truncated_divisor The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \param[in] reflect If \c false, read from the highest-order marked + bit from a new dividend's bits and go down, as normal. Otherwise, + proceed from the lowest-order bit and go up. + + \return An array such that the element at index <var>i</var> is the + composite effect XOR mask for value <var>i</var>. + + \note This routine performs a modulo-2 polynomial division variant. + The exclusive-or operations are applied in a different order, since + that kind of operation is commutative and associative. It also + assumes that the zero-valued augment string was applied before this + step, which means that the updated remainder can be directly used as + the final CRC. + \todo Check that using the unaugmented-CRC division routines give the + same composite mask table as using augmented-CRC routines. + */ + template < int SubOrder, typename Register > + boost::array< Register, (UINTMAX_C( 1 ) << SubOrder) > + make_partial_xor_products_table( int register_length, Register + truncated_divisor, bool reflect ) + { + boost::array<Register, ( UINTMAX_C(1) << SubOrder )> result; - }; // boost::detail::mask_uint_t - #endif + // Loop over every possible dividend value + for ( typename boost::uint_t<SubOrder + 1>::fast dividend = 0u; + dividend < result.size() ; ++dividend ) + { + Register remainder = 0u; + crc_modulo_word_update( register_length, remainder, dividend, + truncated_divisor, SubOrder, false ); + result[ reflect_optionally(dividend, reflect, SubOrder) ] = + reflect_optionally( remainder, reflect, register_length ); + } + return result; + } - // CRC table generator - template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect > - struct crc_table_t + /** \brief A mix-in class for the table of table-driven CRC algorithms + + Encapsulates the parameters need to make a global (technically, + class-static) table usuable in CRC algorithms, and generates said + table. + + \pre 0 \< \a SubOrder \<= Order \<= + std\::numeric_limits\<uintmax_t\>\::digits + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam SubOrder The number of low-order significant bits of the trial + new dividends. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \tparam Reflect If \c false, read from the highest-order marked + bit from a new dividend's bits and go down, as normal. Otherwise, + proceed from the lowest-order bit and go up. + */ + template < int Order, int SubOrder, boost::uintmax_t TruncatedPolynomial, + bool Reflect > + class crc_table_t { - BOOST_STATIC_CONSTANT( std::size_t, byte_combos = (1ul << CHAR_BIT) ); - - typedef mask_uint_t<Bits> masking_type; - typedef typename masking_type::fast value_type; -#if defined(__BORLANDC__) && defined(_M_IX86) && (__BORLANDC__ == 0x560) - // for some reason Borland's command line compiler (version 0x560) - // chokes over this unless we do the calculation for it: - typedef value_type table_type[ 0x100 ]; -#elif defined(__GNUC__) - // old versions of GCC (before 4.0.2) choke on using byte_combos - // as a constant expression when compiling with -pedantic. - typedef value_type table_type[1ul << CHAR_BIT]; -#else - typedef value_type table_type[ byte_combos ]; -#endif + public: + /** \brief The type to check for register bit length + + This is a Boost integral constant indicating how many + significant bits are in the remainder and (truncated) divisor. + */ + typedef boost::integral_constant< int, Order > width_c; + /** \brief The type to check for index-unit bit length + + This is a Boost integral constant indicating how many + significant bits are in the trial new dividends. + */ + typedef boost::integral_constant< int, SubOrder > unit_width_c; + /** \brief The type of registers + + This is the output type for the partial-product map. + */ + typedef typename boost::uint_t< Order >::fast value_type; + /** \brief The type to check the divisor + + This is a Boost integral constant representing the (truncated) + divisor. + */ + typedef boost::integral_constant< value_type, TruncatedPolynomial > + poly_c; + /** \brief The type to check for reflection + + This is a Boost integral constant representing whether input + units should be read in reverse order. + */ + typedef boost::integral_constant< bool, Reflect > refin_c; + /** \brief The type to check for map size + + This is a Boost integral constant representing the number of + elements in the partial-product map, based on the unit size. + */ + typedef high_bit_mask_c< SubOrder > table_size_c; + /** \brief The type of the unit TO partial-product map + + This is the array type that takes units as the index and said unit's + composite partial-product mask as the element. + */ + typedef boost::array<value_type, table_size_c::value> array_type; + /** \brief Create a global array for the mapping table + + Creates an instance of a partial-product array with this class's + parameters. + + \return A reference to a immutable array giving the partial-product + update XOR map for each potential sub-unit value. + */ + static array_type const & get_table() + { + static array_type const table = + make_partial_xor_products_table<unit_width_c::value>( + width_c::value, poly_c::value, refin_c::value ); - static void init_table(); + return table; + } + }; - static table_type table_; + /** \brief A mix-in class that handles direct (i.e. non-reflected) byte-fed + table-driven CRC algorithms + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes aren't + reflected before processing. + + \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial > + class direct_byte_table_driven_crcs + : public crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, false> + { + typedef crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, false> + base_type; - }; // boost::detail::crc_table_t + public: + typedef typename base_type::value_type value_type; + typedef typename base_type::array_type array_type; - // CRC table generator static data member definition - // (Some compilers [Borland C++] require the initializer to be present.) - template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect > - typename crc_table_t<Bits, TruncPoly, Reflect>::table_type - crc_table_t<Bits, TruncPoly, Reflect>::table_ - = { 0 }; + /** \brief Compute the updated remainder after reading some bytes - // Populate CRC lookup table - template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect > - void - crc_table_t<Bits, TruncPoly, Reflect>::init_table - ( - ) - { - // compute table only on the first run - static bool did_init = false; - if ( did_init ) return; + The implementation reads from a table to speed-up applying + augmented-CRC updates byte-wise. - // factor-out constants to avoid recalculation - value_type const fast_hi_bit = masking_type::high_bit_fast; - unsigned char const byte_hi_bit = 1u << (CHAR_BIT - 1u); + \param remainder The pre-update remainder + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read - // loop over every possible dividend value - unsigned char dividend = 0; - do + \return The updated remainder + */ + static value_type augmented_crc_update( value_type remainder, unsigned + char const *new_dividend_bytes, std::size_t new_dividend_byte_count) { - value_type remainder = 0; + static array_type const & table = base_type::get_table(); - // go through all the dividend's bits - for ( unsigned char mask = byte_hi_bit ; mask ; mask >>= 1 ) + while ( new_dividend_byte_count-- ) { - // check if divisor fits - if ( dividend & mask ) - { - remainder ^= fast_hi_bit; - } - - // do polynominal division - if ( remainder & fast_hi_bit ) - { - remainder <<= 1; - remainder ^= TruncPoly; - } - else - { - remainder <<= 1; - } + // Locates the merged partial product based on the leading byte + unsigned char const index = ( remainder >> (Order - CHAR_BIT) ) + & UCHAR_MAX; + + // Complete the multi-bit modulo-2 polynomial division + remainder <<= CHAR_BIT; + remainder |= *new_dividend_bytes++; + remainder ^= table.elems[ index ]; } - table_[ crc_helper<CHAR_BIT, Reflect>::reflect(dividend) ] - = crc_helper<Bits, Reflect>::reflect( remainder ); + return remainder; } - while ( ++dividend ); - did_init = true; - } + /** \brief Compute the updated remainder after reading some bytes - #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - // Align the msb of the remainder to a byte - template < std::size_t Bits, bool RightShift > - class remainder - { - public: - typedef typename uint_t<Bits>::fast value_type; + The implementation reads from a table to speed-up applying + unaugmented-CRC updates byte-wise. - static unsigned char align_msb( value_type rem ) - { return rem >> (Bits - CHAR_BIT); } + \param remainder The pre-update remainder + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated remainder + */ + static value_type crc_update( value_type remainder, unsigned char + const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + static array_type const & table = base_type::get_table(); + + while ( new_dividend_byte_count-- ) + { + // Locates the merged partial product based on comparing the + // leading and incoming bytes + unsigned char const index = ( (remainder >> ( Order - CHAR_BIT + )) & UCHAR_MAX ) ^ *new_dividend_bytes++; + + // Complete the multi-bit altered modulo-2 polynomial division + remainder = (remainder << CHAR_BIT); + remainder ^= table.elems[ index ]; + } + + return remainder; + } }; - // Specialization for the case that the remainder has less - // bits than a byte: align the remainder msb to the byte msb - template < std::size_t Bits > - class remainder< Bits, false > + /** \brief A mix-in class that handles reflected byte-fed, table-driven CRC + algorithms + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes are + reflected before processing. + + \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial > + class reflected_byte_table_driven_crcs + : public crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, true> { + typedef crc_table_t<Order, CHAR_BIT, TruncatedPolynomial, true> + base_type; + public: - typedef typename uint_t<Bits>::fast value_type; + typedef typename base_type::value_type value_type; + typedef typename base_type::array_type array_type; - static unsigned char align_msb( value_type rem ) - { return rem << (CHAR_BIT - Bits); } + /** \brief Compute the updated remainder after reading some bytes + + The implementation reads from a table to speed-up applying + reflecting augmented-CRC updates byte-wise. + + \param remainder The pre-update remainder; since the bytes are + being reflected, this remainder also has to be reflected + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated, reflected remainder + */ + static value_type augmented_crc_update( value_type remainder, unsigned + char const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + static array_type const & table = base_type::get_table(); + + while ( new_dividend_byte_count-- ) + { + // Locates the merged partial product based on the leading byte + // (which is at the low-order end for reflected remainders) + unsigned char const index = remainder & UCHAR_MAX; + + // Complete the multi-bit reflected modulo-2 polynomial division + remainder >>= CHAR_BIT; + remainder |= static_cast<value_type>( *new_dividend_bytes++ ) + << ( Order - CHAR_BIT ); + remainder ^= table.elems[ index ]; + } + + return remainder; + } + + /** \brief Compute the updated remainder after reading some bytes + + The implementation reads from a table to speed-up applying + reflected unaugmented-CRC updates byte-wise. + + \param remainder The pre-update remainder; since the bytes are + being reflected, this remainder also has to be reflected + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated, reflected remainder + */ + static value_type crc_update( value_type remainder, unsigned char + const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + static array_type const & table = base_type::get_table(); + + while ( new_dividend_byte_count-- ) + { + // Locates the merged partial product based on comparing the + // leading and incoming bytes + unsigned char const index = ( remainder & UCHAR_MAX ) ^ + *new_dividend_bytes++; + + // Complete the multi-bit reflected altered modulo-2 polynomial + // division + remainder >>= CHAR_BIT; + remainder ^= table.elems[ index ]; + } + + return remainder; + } }; - #endif - // CRC helper routines - template < std::size_t Bits, bool DoReflect > - class crc_helper + /** \brief Mix-in class for byte-fed, table-driven CRC algorithms with + parameter values at least a byte in width + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes may be + reflected before processing, controlled by a compile-time parameter. + + \pre \c CHAR_BIT \<= \a Order \<= \c std\::numeric_limits\<uintmax_t\> + \::digits + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \tparam Reflect If \c false, read from the highest-order bit from a new + input byte and go down, as normal. Otherwise, proceed from the + lowest-order bit and go up. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect > + class byte_table_driven_crcs + : public boost::conditional< Reflect, + reflected_byte_table_driven_crcs<Order, TruncatedPolynomial>, + direct_byte_table_driven_crcs<Order, TruncatedPolynomial> >::type + { }; + + /** \brief A mix-in class that handles direct (i.e. non-reflected) byte-fed + CRC algorithms for sub-byte parameters + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes aren't + reflected before processing. + + \pre 0 \< \a Order \< \c CHAR_BIT + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial > + class direct_sub_byte_crcs + : public crc_table_t<Order, Order, TruncatedPolynomial, false> { + typedef crc_table_t<Order, Order, TruncatedPolynomial, false> + base_type; + public: - // Type - typedef typename uint_t<Bits>::fast value_type; - - #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - // Possibly reflect a remainder - static value_type reflect( value_type x ) - { return detail::reflector<Bits>::reflect( x ); } - - // Compare a byte to the remainder's highest byte - static unsigned char index( value_type rem, unsigned char x ) - { return x ^ rem; } - - // Shift out the remainder's highest byte - static value_type shift( value_type rem ) - { return rem >> CHAR_BIT; } - #else - // Possibly reflect a remainder - static value_type reflect( value_type x ) - { return DoReflect ? detail::reflector<Bits>::reflect( x ) : x; } - - // Compare a byte to the remainder's highest byte - static unsigned char index( value_type rem, unsigned char x ) - { return x ^ ( DoReflect ? rem : - ((Bits>CHAR_BIT)?( rem >> (Bits - CHAR_BIT) ) : - ( rem << (CHAR_BIT - Bits) ))); } - - // Shift out the remainder's highest byte - static value_type shift( value_type rem ) - { return DoReflect ? rem >> CHAR_BIT : rem << CHAR_BIT; } - #endif - - }; // boost::detail::crc_helper - - #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION - template < std::size_t Bits > - class crc_helper<Bits, false> + typedef typename base_type::width_c width_c; + typedef typename base_type::value_type value_type; + typedef typename base_type::poly_c poly_c; + typedef typename base_type::array_type array_type; + + /** \brief Compute the updated remainder after reading some bytes + + The implementation reads from a table to speed-up applying + augmented-CRC updates byte-wise. + + \param remainder The pre-update remainder + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated remainder + + \todo Use this function somewhere so I can test it. + */ + static value_type augmented_crc_update( value_type remainder, unsigned + char const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + //static array_type const & table = base_type::get_table(); + + while ( new_dividend_byte_count-- ) + { + // Without a table, process each byte explicitly + augmented_crc_modulo_word_update( width_c::value, remainder, + *new_dividend_bytes++, poly_c::value, CHAR_BIT, false ); + } + + return remainder; + } + + /** \brief Compute the updated remainder after reading some bytes + + The implementation reads from a table to speed-up applying + unaugmented-CRC updates byte-wise. + + \param remainder The pre-update remainder + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated remainder + */ + static value_type crc_update( value_type remainder, unsigned char + const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + //static array_type const & table = base_type::get_table(); + + while ( new_dividend_byte_count-- ) + { + // Without a table, process each byte explicitly + crc_modulo_word_update( width_c::value, remainder, + *new_dividend_bytes++, poly_c::value, CHAR_BIT, false ); + } + + return remainder; + } + }; + + /** \brief A mix-in class that handles reflected byte-fed, CRC algorithms + for sub-byte parameters + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes are + reflected before processing. + + \pre 0 \< \a Order \< \c CHAR_BIT + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial > + class reflected_sub_byte_crcs + : public crc_table_t<Order, Order, TruncatedPolynomial, true> { + typedef crc_table_t<Order, Order, TruncatedPolynomial, true> + base_type; + public: - // Type - typedef typename uint_t<Bits>::fast value_type; + typedef typename base_type::width_c width_c; + typedef typename base_type::value_type value_type; + typedef typename base_type::poly_c poly_c; + typedef typename base_type::array_type array_type; + + /** \brief Compute the updated remainder after reading some bytes + + The implementation reads from a table to speed-up applying + reflecting augmented-CRC updates byte-wise. + + \param remainder The pre-update remainder; since the bytes are + being reflected, this remainder also has to be reflected + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read + + \return The updated, reflected remainder + + \todo Use this function somewhere so I can test it. + */ + static value_type augmented_crc_update( value_type remainder, unsigned + char const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + //static array_type const & table = base_type::get_table(); + + remainder = reflect_sub_byte( remainder, width_c::value ); + while ( new_dividend_byte_count-- ) + { + // Without a table, process each byte explicitly + augmented_crc_modulo_word_update( width_c::value, remainder, + *new_dividend_bytes++, poly_c::value, CHAR_BIT, true ); + } + remainder = reflect_sub_byte( remainder, width_c::value ); + + return remainder; + } - // Possibly reflect a remainder - static value_type reflect( value_type x ) - { return x; } + /** \brief Compute the updated remainder after reading some bytes - // Compare a byte to the remainder's highest byte - static unsigned char index( value_type rem, unsigned char x ) - { return x ^ remainder<Bits,(Bits>CHAR_BIT)>::align_msb( rem ); } + The implementation reads from a table to speed-up applying + reflected unaugmented-CRC updates byte-wise. - // Shift out the remainder's highest byte - static value_type shift( value_type rem ) - { return rem << CHAR_BIT; } + \param remainder The pre-update remainder; since the bytes are + being reflected, this remainder also has to be reflected + \param new_dividend_bytes The address where the new bytes start + \param new_dividend_byte_count The number of new bytes to read - }; // boost::detail::crc_helper - #endif + \return The updated, reflected remainder + */ + static value_type crc_update( value_type remainder, unsigned char + const *new_dividend_bytes, std::size_t new_dividend_byte_count) + { + //static array_type const & table = base_type::get_table(); + + remainder = reflect_sub_byte( remainder, width_c::value ); + while ( new_dividend_byte_count-- ) + { + // Without a table, process each byte explicitly + crc_modulo_word_update( width_c::value, remainder, + *new_dividend_bytes++, poly_c::value, CHAR_BIT, true ); + } + remainder = reflect_sub_byte( remainder, width_c::value ); + + return remainder; + } + }; + + /** \brief Mix-in class for byte-fed, table-driven CRC algorithms with + sub-byte parameters + + This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes may be + reflected before processing, controlled by a compile-time parameter. + + \pre 0 \< \a Order \< \c CHAR_BIT + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \tparam Reflect If \c false, read from the highest-order bit from a new + input byte and go down, as normal. Otherwise, proceed from the + lowest-order bit and go up. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect > + class sub_byte_crcs + : public boost::conditional< Reflect, + reflected_sub_byte_crcs<Order, TruncatedPolynomial>, + direct_sub_byte_crcs<Order, TruncatedPolynomial> >::type + { }; + + /** This class template adds member functions #augmented_crc_update and + #crc_update to update remainders from new input bytes. The bytes may be + reflected before processing, controlled by a compile-time parameter. + + \pre 0 \< \a Order \<= \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam Order The order of the modulo-2 polynomial remainder and one + less than the divisor's order. + \tparam TruncatedPolynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always + assumed to be 1. + \tparam Reflect If \c false, read from the highest-order bit from a new + input byte and go down, as normal. Otherwise, proceed from the + lowest-order bit and go up. + \tparam Id An extra differentiator if multiple copies of this class + template are mixed-in as base classes. Defaults to 0 if omitted. + */ + template < int Order, boost::uintmax_t TruncatedPolynomial, bool Reflect, + int Id > + class crc_driver + : public boost::conditional< (Order < CHAR_BIT), sub_byte_crcs<Order, + TruncatedPolynomial, Reflect>, byte_table_driven_crcs<Order, + TruncatedPolynomial, Reflect> >::type + { + public: + /** \brief The type to check for ID + + This is a Boost integral constant indicating what ID number this + instantiation used. + */ + typedef boost::integral_constant<int, Id> id_type; + }; } // namespace detail +//! \endcond // Simple CRC class function definitions -----------------------------------// +/** Constructs a \c crc_basic object with at least the required parameters to a + particular CRC formula to be processed upon receiving input. + + \param[in] truncated_polynomial The lowest coefficients of the divisor + polynomial. The highest-order coefficient is omitted and always assumed + to be 1. (\e Poly from the RMCA) + \param[in] initial_remainder The (unaugmented) initial state of the + polynomial remainder. Defaults to \c 0 if omitted. (\e Init from the + RMCA) + \param[in] final_xor_value The (XOR) bit-mask to be applied to the output + remainder, after possible reflection but before returning. Defaults to + \c 0 (i.e. no bit changes) if omitted. (\e XorOut from the RMCA) + \param[in] reflect_input If \c true, input bytes are read lowest-order bit + first, otherwise highest-order bit first. Defaults to \c false if + omitted. (\e RefIn from the RMCA) + \param[in] reflect_remainder If \c true, the output remainder is reflected + before the XOR-mask. Defaults to \c false if omitted. (\e RefOut from + the RMCA) + + \post <code><var>truncated_polynomial</var> == + this->get_truncated_polynominal()</code> + \post <code><var>initial_remainder</var> == + this->get_initial_remainder()</code> + \post <code><var>final_xor_value</var> == + this->get_final_xor_value()</code> + \post <code><var>reflect_input</var> == + this->get_reflect_input()</code> + \post <code><var>reflect_remainder</var> == + this->get_reflect_remainder()</code> + \post <code><var>initial_remainder</var> == + this->get_interim_remainder()</code> + \post <code>(<var>reflect_remainder</var> ? + REFLECT(<var>initial_remainder</var>) : <var>initial_remainder</var>) ^ + <var>final_xor_value</var> == this->checksum()</code> + */ template < std::size_t Bits > inline crc_basic<Bits>::crc_basic ( - typename crc_basic<Bits>::value_type truncated_polynominal, - typename crc_basic<Bits>::value_type initial_remainder, // = 0 - typename crc_basic<Bits>::value_type final_xor_value, // = 0 - bool reflect_input, // = false - bool reflect_remainder // = false + value_type truncated_polynomial, + value_type initial_remainder, // = 0 + value_type final_xor_value, // = 0 + bool reflect_input, // = false + bool reflect_remainder // = false ) - : rem_( initial_remainder ), poly_( truncated_polynominal ) + : rem_( initial_remainder ), poly_( truncated_polynomial ) , init_( initial_remainder ), final_( final_xor_value ) , rft_in_( reflect_input ), rft_out_( reflect_remainder ) { } +/** Returns a representation of the polynomial divisor. The value of the + 2<sup>i</sup> bit is the value of the coefficient of the polynomial's + x<sup>i</sup> term. The omitted bit for x<sup>(#bit_count)</sup> term is + always 1. + + \return The bit-packed list of coefficients. If the bit-length of + #value_type exceeds #bit_count, the values of higher-placed bits should be + ignored (even any for x<sup>(#bit_count)</sup>) since they're unregulated. + */ template < std::size_t Bits > inline typename crc_basic<Bits>::value_type @@ -653,6 +1586,14 @@ crc_basic<Bits>::get_truncated_polynominal return poly_; } +/** Returns a representation of the polynomial remainder before any input has + been submitted. The value of the 2<sup>i</sup> bit is the value of the + coefficient of the polynomial's x<sup>i</sup> term. + + \return The bit-packed list of coefficients. If the bit-length of + #value_type exceeds #bit_count, the values of higher-placed bits should be + ignored since they're unregulated. + */ template < std::size_t Bits > inline typename crc_basic<Bits>::value_type @@ -663,6 +1604,15 @@ crc_basic<Bits>::get_initial_remainder return init_; } +/** Returns the mask to be used during creation of a checksum. The mask is used + for an exclusive-or (XOR) operation applied bit-wise to the interim + remainder representation (after any reflection, if #get_reflect_remainder() + returns \c true). + + \return The bit-mask. If the bit-length of #value_type exceeds #bit_count, + the values of higher-placed bits should be ignored since they're + unregulated. + */ template < std::size_t Bits > inline typename crc_basic<Bits>::value_type @@ -673,6 +1623,13 @@ crc_basic<Bits>::get_final_xor_value return final_; } +/** Returns a whether or not a submitted byte will be \"reflected\" before it is + used to update the interim remainder. Only the byte-wise operations + #process_byte, #process_block, and #process_bytes are affected. + + \retval true Input bytes will be read starting from the lowest-order bit. + \retval false Input bytes will be read starting from the highest-order bit. + */ template < std::size_t Bits > inline bool @@ -683,6 +1640,12 @@ crc_basic<Bits>::get_reflect_input return rft_in_; } +/** Indicates if the interim remainder will be \"reflected\" before it is passed + to the XOR-mask stage when returning a checksum. + + \retval true The interim remainder is reflected before further work. + \retval false The interim remainder is applied to the XOR-mask as-is. + */ template < std::size_t Bits > inline bool @@ -693,6 +1656,19 @@ crc_basic<Bits>::get_reflect_remainder return rft_out_; } +/** Returns a representation of the polynomial remainder after all the input + submissions since construction or the last #reset call. The value of the + 2<sup>i</sup> bit is the value of the coefficient of the polynomial's + x<sup>i</sup> term. If CRC processing gets interrupted here, retain the + value returned, and use it to start up the next CRC computer where you left + off (with #reset(value_type) or construction). The next computer has to + have its other parameters compatible with this computer. + + \return The bit-packed list of coefficients. If the bit-length of + #value_type exceeds #bit_count, the values of higher-placed bits should be + ignored since they're unregulated. No output processing (reflection or + XOR mask) has been applied to the value. + */ template < std::size_t Bits > inline typename crc_basic<Bits>::value_type @@ -700,20 +1676,45 @@ crc_basic<Bits>::get_interim_remainder ( ) const { - return rem_ & masking_type::sig_bits; + return rem_ & detail::low_bits_mask_c<bit_count>::value; } +/** Changes the interim polynomial remainder to \a new_rem, purging any + influence previously submitted input has had. The value of the + 2<sup>i</sup> bit is the value of the coefficient of the polynomial's + x<sup>i</sup> term. + + \param[in] new_rem The (unaugmented) state of the polynomial remainder + starting from this point, with no output processing applied. + + \post <code><var>new_rem</var> == this->get_interim_remainder()</code> + \post <code>((this->get_reflect_remainder() ? + REFLECT(<var>new_rem</var>) : <var>new_rem</var>) ^ + this->get_final_xor_value()) == this->checksum()</code> + */ template < std::size_t Bits > inline void crc_basic<Bits>::reset ( - typename crc_basic<Bits>::value_type new_rem + value_type new_rem ) { rem_ = new_rem; } +/** Changes the interim polynomial remainder to the initial remainder given + during construction, purging any influence previously submitted input has + had. The value of the 2<sup>i</sup> bit is the value of the coefficient of + the polynomial's x<sup>i</sup> term. + + \post <code>this->get_initial_remainder() == + this->get_interim_remainder()</code> + \post <code>((this->get_reflect_remainder() ? + REFLECT(this->get_initial_remainder()) : + this->get_initial_remainder()) ^ this->get_final_xor_value()) + == this->checksum()</code> + */ template < std::size_t Bits > inline void @@ -724,6 +1725,13 @@ crc_basic<Bits>::reset this->reset( this->get_initial_remainder() ); } +/** Updates the interim remainder with a single altered-CRC-division step. + + \param[in] bit The new input bit. + + \post The interim remainder is updated though a modulo-2 polynomial + division, where the division steps are altered for unaugmented CRCs. + */ template < std::size_t Bits > inline void @@ -732,43 +1740,54 @@ crc_basic<Bits>::process_bit bool bit ) { - value_type const high_bit_mask = masking_type::high_bit; + detail::crc_modulo_update( bit_count, rem_, bit, poly_ ); +} - // compare the new bit with the remainder's highest - rem_ ^= ( bit ? high_bit_mask : 0u ); +/** Updates the interim remainder with several altered-CRC-division steps. Each + bit is processed separately, starting from the one at the + 2<sup><var>bit_length</var> - 1</sup> place, then proceeding down to the + lowest-placed bit. Any order imposed by + <code>this->get_reflect_input()</code> is ignored. - // a full polynominal division step is done when the highest bit is one - bool const do_poly_div = static_cast<bool>( rem_ & high_bit_mask ); + \pre 0 \< \a bit_length \<= \c CHAR_BIT - // shift out the highest bit - rem_ <<= 1; - - // carry out the division, if needed - if ( do_poly_div ) - { - rem_ ^= poly_; - } -} + \param[in] bits The byte containing the new input bits. + \param[in] bit_length The number of bits in the byte to be read. + \post The interim remainder is updated though \a bit_length modulo-2 + polynomial divisions, where the division steps are altered for unaugmented + CRCs. + */ template < std::size_t Bits > void crc_basic<Bits>::process_bits ( unsigned char bits, - std::size_t bit_count + std::size_t bit_length ) { // ignore the bits above the ones we want - bits <<= CHAR_BIT - bit_count; + bits <<= CHAR_BIT - bit_length; // compute the CRC for each bit, starting with the upper ones unsigned char const high_bit_mask = 1u << ( CHAR_BIT - 1u ); - for ( std::size_t i = bit_count ; i > 0u ; --i, bits <<= 1u ) + for ( std::size_t i = bit_length ; i > 0u ; --i, bits <<= 1u ) { process_bit( static_cast<bool>(bits & high_bit_mask) ); } } +/** Updates the interim remainder with a byte's worth of altered-CRC-division + steps. The bits within the byte are processed from the highest place down + if <code>this->get_reflect_input()</code> is \c false, and lowest place + up otherwise. + + \param[in] byte The new input byte. + + \post The interim remainder is updated though \c CHAR_BIT modulo-2 + polynomial divisions, where the division steps are altered for unaugmented + CRCs. + */ template < std::size_t Bits > inline void @@ -777,10 +1796,33 @@ crc_basic<Bits>::process_byte unsigned char byte ) { - process_bits( (rft_in_ ? detail::reflector<CHAR_BIT>::reflect(byte) - : byte), CHAR_BIT ); + process_bits( (rft_in_ ? detail::reflect_byte( byte ) : byte), CHAR_BIT ); } +/** Updates the interim remainder with several bytes' worth of + altered-CRC-division steps. The bits within each byte are processed from + the highest place down if <code>this->get_reflect_input()</code> is + \c false, and lowest place up otherwise. The bytes themselves are processed + starting from the one pointed by \a bytes_begin until \a bytes_end is + reached through forward iteration, treating the two pointers as if they + point to <code>unsigned char</code> objects. + + \pre \a bytes_end has to equal \a bytes_begin if the latter is \c NULL or + otherwise doesn't point to a valid buffer. + \pre \a bytes_end, if not equal to \a bytes_begin, has to point within or + one-byte-past the same buffer \a bytes_begin points into. + \pre \a bytes_end has to be reachable from \a bytes_begin through a finite + number of forward byte-pointer increments. + + \param[in] bytes_begin The address where the memory block begins. + \param[in] bytes_end Points to one-byte past the address of the memory + block's last byte, or \a bytes_begin if no bytes are to be read. + + \post The interim remainder is updated though <code>CHAR_BIT * (((unsigned + char const *) bytes_end) - ((unsigned char const *) bytes_begin))</code> + modulo-2 polynomial divisions, where the division steps are altered for + unaugmented CRCs. + */ template < std::size_t Bits > void crc_basic<Bits>::process_block @@ -796,6 +1838,26 @@ crc_basic<Bits>::process_block } } +/** Updates the interim remainder with several bytes' worth of + altered-CRC-division steps. The bits within each byte are processed from + the highest place down if <code>this->get_reflect_input()</code> is + \c false, and lowest place up otherwise. The bytes themselves are processed + starting from the one pointed by \a buffer, forward-iterated (as if the + pointed-to objects were of <code>unsigned char</code>) until \a byte_count + bytes are read. + + \pre \a byte_count has to equal 0 if \a buffer is \c NULL or otherwise + doesn't point to valid memory. + \pre If \a buffer points within valid memory, then that block has to have + at least \a byte_count more valid bytes allocated from that point. + + \param[in] buffer The address where the memory block begins. + \param[in] byte_count The number of bytes in the memory block. + + \post The interim remainder is updated though <code>CHAR_BIT * + <var>byte_count</var></code> modulo-2 polynomial divisions, where the + division steps are altered for unaugmented CRCs. + */ template < std::size_t Bits > inline void @@ -811,6 +1873,18 @@ crc_basic<Bits>::process_bytes process_block( b, b + byte_count ); } +/** Computes the checksum of all the submitted bits since construction or the + last call to #reset. The checksum will be the raw checksum, i.e. the + (interim) remainder after all the modulo-2 polynomial division, plus any + output processing. + + \return <code>(this->get_reflect_remainder() ? + REFLECT(this->get_interim_remainder()) : + this->get_interim_remainder()) ^ this->get_final_xor_value()</code> + + \note Since checksums are meant to be compared, any higher-placed bits + (when the bit-length of #value_type exceeds #bit_count) will be set to 0. + */ template < std::size_t Bits > inline typename crc_basic<Bits>::value_type @@ -818,8 +1892,8 @@ crc_basic<Bits>::checksum ( ) const { - return ( (rft_out_ ? detail::reflector<Bits>::reflect( rem_ ) : rem_) - ^ final_ ) & masking_type::sig_bits; + return ( (rft_out_ ? detail::reflect_unsigned( rem_, bit_count ) : + rem_) ^ final_ ) & detail::low_bits_mask_c<bit_count>::value; } @@ -829,19 +1903,35 @@ crc_basic<Bits>::checksum #define BOOST_CRC_OPTIMAL_NAME crc_optimal<Bits, TruncPoly, InitRem, \ FinalXor, ReflectIn, ReflectRem> +/** Constructs a \c crc_optimal object with a particular CRC formula to be + processed upon receiving input. The initial remainder may be overridden. + + \param[in] init_rem The (unaugmented) initial state of the polynomial + remainder. Defaults to #initial_remainder if omitted. + + \post <code>#truncated_polynominal == + this->get_truncated_polynominal()</code> + \post <code>#initial_remainder == this->get_initial_remainder()</code> + \post <code>#final_xor_value == this->get_final_xor_value()</code> + \post <code>#reflect_input == this->get_reflect_input()</code> + \post <code>#reflect_remainder == this->get_reflect_remainder()</code> + \post <code><var>init_rem</var> == this->get_interim_remainder()</code> + \post <code>(#reflect_remainder ? REFLECT(<var>init_rem</var>) : + <var>init_rem</var>) ^ #final_xor_value == this->checksum()</code> + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > inline BOOST_CRC_OPTIMAL_NAME::crc_optimal ( - typename BOOST_CRC_OPTIMAL_NAME::value_type init_rem // = InitRem + value_type init_rem // = initial_remainder ) - : rem_( helper_type::reflect(init_rem) ) + : rem_( reflect_i_type::reflect_q(init_rem) ) { - crc_table_type::init_table(); } +//! \copydetails boost::crc_basic::get_truncated_polynominal template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -851,9 +1941,10 @@ BOOST_CRC_OPTIMAL_NAME::get_truncated_polynominal ( ) const { - return TruncPoly; + return truncated_polynominal; } +//! \copydetails boost::crc_basic::get_initial_remainder template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -863,9 +1954,10 @@ BOOST_CRC_OPTIMAL_NAME::get_initial_remainder ( ) const { - return InitRem; + return initial_remainder; } +//! \copydetails boost::crc_basic::get_final_xor_value template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -875,9 +1967,10 @@ BOOST_CRC_OPTIMAL_NAME::get_final_xor_value ( ) const { - return FinalXor; + return final_xor_value; } +//! \copydetails boost::crc_basic::get_reflect_input template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -887,9 +1980,10 @@ BOOST_CRC_OPTIMAL_NAME::get_reflect_input ( ) const { - return ReflectIn; + return reflect_input; } +//! \copydetails boost::crc_basic::get_reflect_remainder template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -899,9 +1993,10 @@ BOOST_CRC_OPTIMAL_NAME::get_reflect_remainder ( ) const { - return ReflectRem; + return reflect_remainder; } +//! \copydetails boost::crc_basic::get_interim_remainder template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -912,9 +2007,24 @@ BOOST_CRC_OPTIMAL_NAME::get_interim_remainder ) const { // Interim remainder should be _un_-reflected, so we have to undo it. - return helper_type::reflect( rem_ ) & masking_type::sig_bits_fast; + return reflect_i_type::reflect_q( rem_ ) & + detail::low_bits_mask_c<bit_count>::value; } +/** Changes the interim polynomial remainder to \a new_rem, purging any + influence previously submitted input has had. The value of the + 2<sup>i</sup> bit is the value of the coefficient of the polynomial's + x<sup>i</sup> term. + + \param[in] new_rem The (unaugmented) state of the polynomial remainder + starting from this point, with no output processing applied. Defaults to + <code>this->get_initial_remainder()</code> if omitted. + + \post <code><var>new_rem</var> == this->get_interim_remainder()</code> + \post <code>((this->get_reflect_remainder() ? + REFLECT(<var>new_rem</var>) : <var>new_rem</var>) ^ + this->get_final_xor_value()) == this->checksum()</code> + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -922,12 +2032,18 @@ inline void BOOST_CRC_OPTIMAL_NAME::reset ( - typename BOOST_CRC_OPTIMAL_NAME::value_type new_rem // = InitRem + value_type new_rem // = initial_remainder ) { - rem_ = helper_type::reflect( new_rem ); + rem_ = reflect_i_type::reflect_q( new_rem ); } +/** \copydetails boost::crc_basic::process_byte + + \note Any modulo-2 polynomial divisions may use a table of pre-computed + remainder changes (as XOR masks) to speed computation when reading data + byte-wise. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -941,9 +2057,16 @@ BOOST_CRC_OPTIMAL_NAME::process_byte process_bytes( &byte, sizeof(byte) ); } +/** \copydetails boost::crc_basic::process_block + + \note Any modulo-2 polynomial divisions may use a table of pre-computed + remainder changes (as XOR masks) to speed computation when reading data + byte-wise. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > +inline void BOOST_CRC_OPTIMAL_NAME::process_block ( @@ -951,20 +2074,16 @@ BOOST_CRC_OPTIMAL_NAME::process_block void const * bytes_end ) { - // Recompute the CRC for each byte passed - for ( unsigned char const * p - = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p ) - { - // Compare the new byte with the remainder's higher bits to - // get the new bits, shift out the remainder's current higher - // bits, and update the remainder with the polynominal division - // of the new bits. - unsigned char const byte_index = helper_type::index( rem_, *p ); - rem_ = helper_type::shift( rem_ ); - rem_ ^= crc_table_type::table_[ byte_index ]; - } + process_bytes( bytes_begin, static_cast<unsigned char const *>(bytes_end) - + static_cast<unsigned char const *>(bytes_begin) ); } +/** \copydetails boost::crc_basic::process_bytes + + \note Any modulo-2 polynomial divisions may use a table of pre-computed + remainder changes (as XOR masks) to speed computation when reading data + byte-wise. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -976,11 +2095,11 @@ BOOST_CRC_OPTIMAL_NAME::process_bytes std::size_t byte_count ) { - unsigned char const * const b = static_cast<unsigned char const *>( - buffer ); - process_block( b, b + byte_count ); + rem_ = crc_table_type::crc_update( rem_, static_cast<unsigned char const + *>(buffer), byte_count ); } +//! \copydetails boost::crc_basic::checksum template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -990,10 +2109,29 @@ BOOST_CRC_OPTIMAL_NAME::checksum ( ) const { - return ( reflect_out_type::reflect(rem_) ^ get_final_xor_value() ) - & masking_type::sig_bits_fast; + return ( reflect_o_type::reflect_q(rem_) ^ get_final_xor_value() ) + & detail::low_bits_mask_c<bit_count>::value; } +/** Updates the interim remainder with a byte's worth of altered-CRC-division + steps. The bits within the byte are processed from the highest place down + if <code>this->get_reflect_input()</code> is \c false, and lowest place + up otherwise. This function is meant to present a function-object interface + to code that wants to process a stream of bytes with + <code>std::for_each</code> or similar range-processing algorithms. Since + some of these algorithms takes their function object by value, make sure to + copy back the result to this object so the updates can be remembered. + + \param[in] byte The new input byte. + + \post The interim remainder is updated though \c CHAR_BIT modulo-2 + polynomial divisions, where the division steps are altered for unaugmented + CRCs. + + \note Any modulo-2 polynomial divisions may use a table of pre-computed + remainder changes (as XOR masks) to speed computation when reading data + byte-wise. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -1007,6 +2145,22 @@ BOOST_CRC_OPTIMAL_NAME::operator () process_byte( byte ); } +/** Computes the checksum of all the submitted bits since construction or the + last call to #reset. The checksum will be the raw checksum, i.e. the + (interim) remainder after all the modulo-2 polynomial division, plus any + output processing. This function is meant to present a function-object + interface to code that wants to receive data like + <code>std::generate_n</code> or similar data-processing algorithms. Note + that if this object is used as a generator multiple times without an + intervening mutating operation, the same value will always be returned. + + \return <code>(this->get_reflect_remainder() ? + REFLECT(this->get_interim_remainder()) : + this->get_interim_remainder()) ^ this->get_final_xor_value()</code> + + \note Since checksums are meant to be compared, any higher-placed bits + (when the bit-length of #value_type exceeds #bit_count) will be set to 0. + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -1022,6 +2176,43 @@ BOOST_CRC_OPTIMAL_NAME::operator () // CRC computation function definition -------------------------------------// +/** Computes the polynomial remainder of a CRC run, assuming that \a buffer and + \a byte_count describe a memory block representing the polynomial dividend. + The division steps are altered so the result directly gives a checksum, + without need to augment the memory block with scratch-space bytes. The + first byte is considered the highest order, going down for subsequent bytes. + + \pre 0 \< \a Bits \<= \c std\::numeric_limits\<uintmax_t\>\::digits + + \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from + the RMCA) + \tparam TruncPoly The lowest coefficients of the divisor polynomial. The + highest-order coefficient is omitted and always assumed to be 1. + (\e Poly from the RMCA) + \tparam InitRem The (unaugmented) initial state of the polynomial + remainder. (\e Init from the RMCA) + \tparam FinalXor The (XOR) bit-mask to be applied to the output remainder, + after possible reflection but before returning. (\e XorOut from the RMCA) + \tparam ReflectIn If \c True, input bytes are read lowest-order bit first, + otherwise highest-order bit first. (\e RefIn from the RMCA) + \tparam ReflectRem If \c True, the output remainder is reflected before the + XOR-mask. (\e RefOut from the RMCA) + + \param[in] buffer The address where the memory block begins. + \param[in] byte_count The number of bytes in the memory block. + + \return The checksum, which is the last (interim) remainder plus any output + processing. + + \note Unaugmented-style CRC runs perform modulo-2 polynomial division in + an altered order. The trailing \a Bits number of zero-valued bits needed + to extracted an (unprocessed) checksum is virtually moved to near the + beginning of the message. This is OK since the XOR operation is + commutative and associative. It also means that you can get a checksum + anytime. Since data is being read byte-wise, a table of pre-computed + remainder changes (as XOR masks) can be used to speed computation. + + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor, bool ReflectIn, bool ReflectRem > @@ -1031,7 +2222,6 @@ crc ( void const * buffer, std::size_t byte_count - BOOST_CRC_DUMMY_INIT ) { BOOST_CRC_OPTIMAL_NAME computer; @@ -1040,57 +2230,67 @@ crc } -// Augmented-message CRC computation function definitions ------------------// - +// Augmented-message CRC computation function definition -------------------// + +/** Computes the polynomial remainder of a CRC run, assuming that \a buffer and + \a byte_count describe a memory block representing the polynomial dividend. + The first byte is considered the highest order, going down for subsequent + bytes. Within a byte, the highest-order bit is read first (corresponding to + \e RefIn = \c False in the RMCA). Check the other parts of this function's + documentation to see how a checksum can be gained and/or used. + + \pre 0 \< \a Bits \<= \c std\::numeric_limit\<uintmax_t\>\::digits + + \tparam Bits The order of the modulo-2 polynomial divisor. (\e Width from + the RMCA) + \tparam TruncPoly The lowest coefficients of the divisor polynomial. The + highest-order coefficient is omitted and always assumed to be 1. + (\e Poly from the RMCA) + + \param[in] buffer The address where the memory block begins. + \param[in] byte_count The number of bytes in the memory block. + \param[in] initial_remainder The initial state of the polynomial + remainder, defaulting to zero if omitted. If you are reading a memory + block in multiple runs, put the return value of the previous run here. + (Note that initial-remainders given by RMCA parameter lists, as + \e Init, assume that the initial remainder is in its \b unaugmented state, + so you would need to convert the value to make it suitable for this + function. I currently don't provide a conversion routine.) + + \return The interim remainder, if no augmentation is used. A special value + if augmentation is used (see the notes). No output processing is done on + the value. (In RMCA terms, \e RefOut is \c False and \e XorOut is \c 0.) + + \note Augmented-style CRC runs use straight-up modulo-2 polynomial + division. Since data is being read byte-wise, a table of pre-computed + remainder changes (as XOR masks) can be used to speed computation. + \note Reading just a memory block will yield an interim remainder, and not + the final checksum. To get that checksum, allocate \a Bits / \c CHAR_BIT + bytes directly after the block and fill them with zero values, then extend + \a byte_count to include those extra bytes. A data block is corrupt if + the return value doesn't equal your separately given checksum. + \note Another way to perform a check is use the zero-byte extension method, + but replace the zero values with your separately-given checksum. The + checksum must be loaded in big-endian order. Here corruption, in either + the data block or the given checksum, is confirmed if the return value is + not zero. + \note The two checksum techniques assume the CRC-run is performed bit-wise, + while this function works byte-wise. That means that the techniques can + be used only if \c CHAR_BIT divides \a Bits evenly! + */ template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly > typename uint_t<Bits>::fast augmented_crc ( void const * buffer, std::size_t byte_count, - typename uint_t<Bits>::fast initial_remainder - BOOST_ACRC_DUMMY_INIT -) -{ - typedef unsigned char byte_type; - typedef detail::mask_uint_t<Bits> masking_type; - typedef detail::crc_table_t<Bits, TruncPoly, false> crc_table_type; - - typename masking_type::fast rem = initial_remainder; - byte_type const * const b = static_cast<byte_type const *>( buffer ); - byte_type const * const e = b + byte_count; - - crc_table_type::init_table(); - for ( byte_type const * p = b ; p < e ; ++p ) - { - // Use the current top byte as the table index to the next - // "partial product." Shift out that top byte, shifting in - // the next augmented-message byte. Complete the division. - byte_type const byte_index = rem >> ( Bits - CHAR_BIT ); - rem <<= CHAR_BIT; - rem |= *p; - rem ^= crc_table_type::table_[ byte_index ]; - } - - return rem & masking_type::sig_bits_fast; -} - -template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly > -inline -typename uint_t<Bits>::fast -augmented_crc -( - void const * buffer, - std::size_t byte_count - BOOST_ACRC_DUMMY_INIT + typename uint_t<Bits>::fast initial_remainder // = 0u ) { - // The last function argument has its type specified so the other version of - // augmented_crc will be called. If the cast wasn't in place, and the - // BOOST_ACRC_DUMMY_INIT added a third argument (for a workaround), the "0" - // would match as that third argument, leading to infinite recursion. - return augmented_crc<Bits, TruncPoly>( buffer, byte_count, - static_cast<typename uint_t<Bits>::fast>(0) ); + return detail::low_bits_mask_c<Bits>::value & + detail::byte_table_driven_crcs<Bits, TruncPoly, false>:: + augmented_crc_update( initial_remainder, static_cast<unsigned char const + *>(buffer), byte_count ); } @@ -1099,10 +2299,6 @@ augmented_crc // Undo header-private macros #undef BOOST_CRC_OPTIMAL_NAME -#undef BOOST_ACRC_DUMMY_INIT -#undef BOOST_ACRC_DUMMY_PARM_TYPE -#undef BOOST_CRC_DUMMY_INIT -#undef BOOST_CRC_DUMMY_PARM_TYPE #undef BOOST_CRC_PARM_TYPE |