[Boost-commit] svn:boost r76160 - trunk/boost

Subject: [Boost-commit] svn:boost r76160 - trunk/boost
From: dwalker07_at_[hidden]
Date: 2011-12-25 16:11:07

Author: dlwalker
Date: 2011-12-25 16:11:07 EST (Sun, 25 Dec 2011)
New Revision: 76160
URL: http://svn.boost.org/trac/boost/changeset/76160

Log:
Changed the two internal core CRC routines: made the single-bit version call the bit-group version instead of the reverse, switched the appearance of the two routines in their file, moved the register bit-length from a compile-time parameter to run-time, made the single-bit version inline and no longer return any quotient.
Text files modified: 
   trunk/boost/crc.hpp |   120 +++++++++++++++++++++-------------------
   1 files changed, 63 insertions(+), 57 deletions(-)

Modified: trunk/boost/crc.hpp
==============================================================================
--- trunk/boost/crc.hpp	(original)
+++ trunk/boost/crc.hpp	2011-12-25 16:11:07 EST (Sun, 25 Dec 2011)
@@ -537,33 +537,45 @@
     unsigned char  reflect_byte_optionally( unsigned char x, bool reflect )
     { return reflect ? reflect_byte(x) : x; }
 
-    /** \brief  Update a CRC remainder by a single bit, assuming a non-augmented
+    /** \brief  Update a CRC remainder by several bits, assuming a non-augmented
           message
 
-        Performs the next step of division required by the CRC algorithm, giving
+        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 is a built-in unsigned integer type
-        \pre  0 \< \a Bits \<= std\::numeric_limits\<\a Register\>\::digits
+        \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
 
-        \tparam Bits  The order of the modulo-2 polynomial divisor
         \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_bit  The coefficient for the constant term
-          of the dividend polynomial.
+        \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.
-
-        \return  The quotient of the division (usually useless).
+        \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
@@ -572,57 +584,64 @@
           step, which means that the updated remainder can be directly used as
           the final CRC.
      */
-    template < int Bits, typename Register >
-    bool  crc_modulo_update( Register &remainder, bool new_dividend_bit,
-     Register truncated_divisor )
+    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 )
     {
-        // compare the new bit with the remainder's highest
-        remainder ^= new_dividend_bit ? high_bit_mask_c<Bits - 1>::value : 0u;
+        // 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 )
+        {
+            // 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_c<Bits - 1>::value;
+            // perform modulo-2 division
+            bool const  quotient = remainder & high_bit_mask;
 
-        remainder <<= 1;
-        remainder ^= quotient ? truncated_divisor : 0u;
-        return quotient;
+            remainder <<= 1;
+            remainder ^= quotient ? truncated_divisor : 0u;
+
+            // The quotient isn't used for anything, so don't keep it.
+        }
     }
 
-    /** \brief  Update a CRC remainder by several bits, assuming a non-augmented
+    /** \brief  Update a CRC remainder by a single bit, assuming a non-augmented
           message
 
-        Performs several steps of division required by the CRC algorithm, giving
+        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 and \Word are both built-in unsigned integer types
-        \pre  0 \< \a Bits \<= std\::numeric_limits\<\a Register\>\::digits
-        \pre  0 \< \a word_length \<= std\::numeric_limits\<\a Word\>\::digits
+        \pre  \a Register is a built-in unsigned integer type
+        \pre  0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
+          \::digits
 
-        \tparam Bits  The order of the modulo-2 polynomial divisor
         \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]     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.
-        \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
@@ -631,25 +650,12 @@
           step, which means that the updated remainder can be directly used as
           the final CRC.
      */
-    template < int Bits, typename Register, typename Word >
-    void  crc_modulo_word_update( Register &remainder, Word new_dividend_bits,
-     Register truncated_divisor, int word_length, bool reflect )
+    template < typename Register >
+    inline  void  crc_modulo_update( int register_length, Register &remainder,
+     bool new_dividend_bit, Register truncated_divisor )
     {
-        // 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 ( int  i = word_length ; i ; --i, new_dividend_bits >>= 1 )
-            crc_modulo_update<Bits>( remainder, new_dividend_bits & 1u,
-             truncated_divisor );
-
-        // Note that the quotient isn't stored, since you usually won't need it,
-        // and calculating it slows you down.  If you want it, just do this loop
-        // manually.  Start with Word: Quotient := 0, then for each step do:
-        //   Quotient <- (Quotient << 1) | crc_modulo_update(...)
+        crc_modulo_word_update( register_length, remainder,
+         static_cast<unsigned>(new_dividend_bit), truncated_divisor, 1, false );
     }
 
 
@@ -704,7 +710,7 @@
         {
             value_type  remainder = 0u;
 
-            crc_modulo_word_update<Bits>( remainder, dividend,
+            crc_modulo_word_update( Bits, remainder, dividend,
              truncated_polynomial, CHAR_BIT, false );
 
             table_[ reflect_byte_optionally(dividend, Reflect) ]
@@ -1206,7 +1212,7 @@
     bool  bit
 )
 {
-    detail::crc_modulo_update<bit_count>( rem_, bit, poly_ );
+    detail::crc_modulo_update( bit_count, rem_, bit, poly_ );
 }
 
 /** Updates the interim remainder with several altered-CRC-division steps.  Each