[Boost-commit] svn:boost r76197 - in trunk: boost libs/crc/test

Subject: [Boost-commit] svn:boost r76197 - in trunk: boost libs/crc/test
From: dwalker07_at_[hidden]
Date: 2011-12-26 19:39:27

Author: dlwalker
Date: 2011-12-26 19:39:25 EST (Mon, 26 Dec 2011)
New Revision: 76197
URL: http://svn.boost.org/trac/boost/changeset/76197

Log:
Re-did the compile-time reflection and CRC-table systems, making CRC configurations with mixed-reflection parameters and sub-byte width work, and doubling the speed\!
Text files modified: 
   trunk/boost/crc.hpp               |   866 ++++++++++++++++++++++++++++++++------- 
   trunk/libs/crc/test/crc_test2.cpp |     2                                         
   2 files changed, 700 insertions(+), 168 deletions(-)

Modified: trunk/boost/crc.hpp
==============================================================================
--- trunk/boost/crc.hpp	(original)
+++ trunk/boost/crc.hpp	2011-12-26 19:39:25 EST (Mon, 26 Dec 2011)
@@ -38,7 +38,7 @@
 
 #include <boost/array.hpp>           // for boost::array
 #include <boost/config.hpp>          // for BOOST_STATIC_CONSTANT, etc.
-#include <boost/cstdint.hpp>         // for UINTMAX_C
+#include <boost/cstdint.hpp>         // for UINTMAX_C, boost::uintmax_t
 #include <boost/integer.hpp>         // for boost::uint_t
 #include <boost/mpl/bool.hpp>        // for boost::mpl::true_, ...false_
 #include <boost/mpl/if.hpp>          // for boost::mpl::if_c
@@ -147,21 +147,15 @@
 //! \cond
 namespace detail
 {
-    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 to add a possibly-reflecting member function
     template < int BitLength, bool DoIt, int Id = 0 >
         class possible_reflector;
 
+    //! 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
 
@@ -343,11 +337,10 @@
     // (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::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;
-    typedef detail::crc_table_t<Bits, TruncPoly, ReflectIn>  crc_table_type;
-    typedef detail::crc_helper<Bits, ReflectIn>              helper_type;
 
     // Member data
     value_type  rem_;
@@ -658,141 +651,119 @@
          static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false );
     }
 
+    /** \brief  Update a CRC remainder by several bits, assuming an augmented
+          message
 
-    // CRC table generator
-    template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
-    struct crc_table_t
-    {
-        BOOST_STATIC_CONSTANT( std::size_t, byte_combos = (1ul << CHAR_BIT) );
-
-        typedef typename boost::uint_t<Bits>::fast  value_type;
-
-        BOOST_STATIC_CONSTANT( value_type, truncated_polynomial = TruncPoly );
-#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
+        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.
 
-        static  void  init_table();
+        \pre  \a Register and \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
 
-        static  table_type  table_;
+        \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.
 
-    };  // boost::detail::crc_table_t
+        \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.
 
-    // 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 };
-
-    // 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
-    (
-    )
+        \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 )
     {
-        // compute table only on the first run
-        static  bool  did_init = false;
-        if ( did_init )  return;
+        // Create this masking constant outside the loop.
+        Register const  high_bit_mask = UINTMAX_C(1) << (register_length - 1);
 
-        // Loop over every possible dividend value
-        for ( boost::uint_t<CHAR_BIT + 1>::fast  dividend = 0u ; dividend <=
-         UCHAR_MAX ; ++dividend )
+        // 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 )
         {
-            value_type  remainder = 0u;
+            bool const  quotient = remainder & high_bit_mask;
 
-            crc_modulo_word_update( Bits, remainder, dividend,
-             truncated_polynomial, CHAR_BIT, false );
+            remainder <<= 1;
+            remainder |= new_dividend_bits & 1u;
+            remainder ^= quotient ? truncated_divisor : 0u;
 
-            table_[ reflect_byte_optionally(dividend, Reflect) ]
-             = reflect_optionally( remainder, Reflect, Bits );
+            // The quotient isn't used for anything, so don't keep it.
         }
-
-        did_init = true;
     }
 
-    #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;
+    /** \brief  Update a CRC remainder by a single bit, assuming an augmented
+          message
 
-        static unsigned char align_msb( value_type rem )
-            { return rem >> (Bits - CHAR_BIT); }
-    };
+        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.
 
-    // 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 >
-    {
-    public:
-        typedef typename uint_t<Bits>::fast  value_type;
+        \pre  \a Register is a built-in unsigned integer type
+        \pre  0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
+          \::digits
 
-        static unsigned char align_msb( value_type rem )
-            { return rem << (CHAR_BIT - Bits); }
-    };
-    #endif
+        \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>.
 
-    // CRC helper routines
-    template < std::size_t Bits, bool DoReflect >
-    class crc_helper
-    {
-    public:
-        // Type
-        typedef typename uint_t<Bits>::fast  value_type;
+        \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.
 
-    #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
-        // 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
-        // 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>
+        \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 )
     {
-    public:
-        // Type
-        typedef typename uint_t<Bits>::fast  value_type;
-
-        // 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 ); }
-
-        // Shift out the remainder's highest byte
-        static  value_type  shift( value_type rem )
-            { return rem << CHAR_BIT; }
-
-    };  // boost::detail::crc_helper
-    #endif
+        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
 
@@ -982,6 +953,594 @@
         typedef boost::mpl::integral_c<int, Id>  id_type;
     };
 
+    /** \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;
+
+        // 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;
+    }
+
+    /** \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
+    {
+    public:
+        /** \brief  The type to check for register bit length
+
+            This is a Boost.MPL integral constant indicating how many
+            significant bits are in the remainder and (truncated) divisor.
+         */
+        typedef boost::mpl::integral_c< int, Order >              width_c;
+        /** \brief  The type to check for index-unit bit length
+
+            This is a Boost.MPL integral constant indicating how many
+            significant bits are in the trial new dividends.
+         */
+        typedef boost::mpl::integral_c< 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.MPL integral constant representing the (truncated)
+            divisor.
+         */
+        typedef boost::mpl::integral_c< value_type, TruncatedPolynomial >
+          poly_c;
+        /** \brief  The type to check for reflection
+
+            This is a Boost.MPL integral constant representing whether input
+            units should be read in reverse order.
+         */
+        typedef boost::mpl::integral_c< bool, Reflect >           refin_c;
+        /** \brief  The type to check for map size
+
+            This is a Boost.MPL 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 );
+
+            return 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;
+
+    public:
+        typedef typename base_type::value_type  value_type;
+        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
+         */
+        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
+                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 ];
+            }
+
+            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-- )
+            {
+                // 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 <<= CHAR_BIT;
+                remainder ^= table.elems[ index ];
+            }
+
+            return remainder;
+        }
+    };
+
+    /** \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 base_type::value_type  value_type;
+        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
+         */
+        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;
+        }
+    };
+
+    /** \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::mpl::if_c< 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:
+        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:
+        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;
+        }
+
+        /** \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();
+
+            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::mpl::if_c< 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::mpl::if_c< (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.MPL integral constant indicating what ID number this
+            instantiation used.
+         */
+        typedef boost::mpl::integral_c<int, Id>  id_type;
+    };
+
 
 }  // namespace detail
 //! \endcond
@@ -1401,7 +1960,6 @@
 )
     : rem_( reflect_i_type::reflect_q(init_rem) )
 {
-    crc_table_type::init_table();
 }
 
 //! \copydetails  boost::crc_basic::get_truncated_polynominal
@@ -1539,6 +2097,7 @@
 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
 (
@@ -1546,18 +2105,8 @@
     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
@@ -1577,9 +2126,8 @@
     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
@@ -1772,26 +2320,10 @@
     BOOST_ACRC_DUMMY_INIT
 )
 {
-    typedef unsigned char                                byte_type;
-    typedef detail::crc_table_t<Bits, TruncPoly, false>  crc_table_type;
-
-    typename uint_t<Bits>::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 & detail::low_bits_mask_c<Bits>::value;
+    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 );
 }
 
 

Modified: trunk/libs/crc/test/crc_test2.cpp
==============================================================================
--- trunk/libs/crc/test/crc_test2.cpp	(original)
+++ trunk/libs/crc/test/crc_test2.cpp	2011-12-26 19:39:25 EST (Mon, 26 Dec 2011)
@@ -33,7 +33,7 @@
 
 // Control tests at compile-time
 #ifndef CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST
-#define CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST  0
+#define CONTROL_SUB_BYTE_MISMATCHED_REFLECTION_TEST  1
 #endif