
BoostCommit : 
Subject: [Boostcommit] svn:boost r76160  trunk/boost
From: dwalker07_at_[hidden]
Date: 20111225 16:11:07
Author: dlwalker
Date: 20111225 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 singlebit version call the bitgroup version instead of the reverse, switched the appearance of the two routines in their file, moved the register bitlength from a compiletime parameter to runtime, made the singlebit 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 20111225 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 nonaugmented
+ /** \brief Update a CRC remainder by several bits, assuming a nonaugmented
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
newlyprovided input). The computations assume that the CRC is directly
exposed from the remainder, without any zerovalued bits augmented to
the message bits.
 \pre \a Register is a builtin unsigned integer type
 \pre 0 \< \a Bits \<= std\::numeric_limits\<\a Register\>\::digits
+ \pre \a Register and \Word are both builtin 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 modulo2 polynomial divisor
\tparam Register The type used for representing the remainder and
divisor modulo2 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 modulo2 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 loworder bits
+ to be used from \a Register values. It is the order of the modulo2
+ 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 highestorder coefficient is omitted and always
assumed to be 1.

 \return The quotient of the division (usually useless).
+ \param[in] word_length The number of lowestorder bits to read from
+ \a new_dividend_bits.
+ \param[in] reflect If \c false, read from the highestorder marked
+ bit from \a new_dividend_bits and go down, as normal. Otherwise,
+ proceed from the lowestorder bit and go up.
\note This routine performs a modulo2 polynomial division variant.
The exclusiveor 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 modulo2 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 modulo2 division
 bool const quotient = remainder & high_bit_mask_c<Bits  1>::value;
+ // perform modulo2 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 nonaugmented
+ /** \brief Update a CRC remainder by a single bit, assuming a nonaugmented
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
newlyprovided input). The computations assume that the CRC is directly
exposed from the remainder, without any zerovalued bits augmented to
the message bits.
 \pre \a Register and \Word are both builtin 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 builtin unsigned integer type
+ \pre 0 \< \a register_length \<= std\::numeric_limits\<\a Register\>
+ \::digits
 \tparam Bits The order of the modulo2 polynomial divisor
\tparam Register The type used for representing the remainder and
divisor modulo2 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 modulo2 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 loworder bits
+ to be used from \a Register values. It is the order of the modulo2
+ 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 highestorder coefficient is omitted and always
assumed to be 1.
 \param[in] word_length The number of lowestorder bits to read from
 \a new_dividend_bits.
 \param[in] reflect If \c false, read from the highestorder marked
 bit from \a new_dividend_bits and go down, as normal. Otherwise,
 proceed from the lowestorder bit and go up.
\note This routine performs a modulo2 polynomial division variant.
The exclusiveor 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 modulo2 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 alteredCRCdivision steps. Each
BoostCommit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk