[boost] problem with small width CRCs

From: Bert Klaps (bertk_at_[hidden])
Date: 2004-08-10 10:32:40

Hi,

I ran into a problem using the CRC library for SDH LCAS control words
(3-bit CRC) and SDH Trail Trace Identifier messages (7-bit CRC).

For CRC widths smaller than character width the theoretical and
optimized CRC computers produce different results for non-reflected
input. Gcc produces this warning:

/usr/local/boost/boost_1_31_0/boost/crc.hpp:581: warning: right shift 
count >= width of type

The problem is that for the table based computer the msb of
the remainder needs to be compared to the msb of the input byte.
For most popular CRC parameters that's a right shift, but for CRC
widths smaller than a character this should be a left shift...

Reflected input requires comparing lsb's which doesn't involve any
shifting.

I've attached a patch that solved the problem for me.

Regards,
Bert Klaps


/usr/local/boost/boost_1_31_0/boost/crc.hpp: In static member function `static 
   unsigned char boost::detail::crc_helper<Bits, false>::index(typename 
   boost::uint_t<Bits>::fast, unsigned char) [with unsigned int Bits = 3]':
/usr/local/boost/boost_1_31_0/boost/crc.hpp:928:   instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_block(const void*, const void*) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]'
/usr/local/boost/boost_1_31_0/boost/crc.hpp:947:   instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_bytes(const void*, unsigned int) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]'
/usr/local/boost/boost_1_31_0/boost/crc.hpp:907:   instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::process_byte(unsigned char) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]'
/usr/local/boost/boost_1_31_0/boost/crc.hpp:973:   instantiated from `void boost::crc_optimal<Bits, TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem>::operator()(unsigned char) [with unsigned int Bits = 3, typename boost::uint_t<Bits>::fast TruncPoly = 3, typename boost::uint_t<Bits>::fast InitRem = 0, typename boost::uint_t<Bits>::fast FinalXor = 0, bool ReflectIn = false, bool ReflectRem = false]'
/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.3/include/g++-v3/bits/stl_algo.h:157:   instantiated from `_Function std::for_each(_InputIter, _InputIter, _Function) [with _InputIter = __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >, _Function = boost::crc_optimal<3, 3, 0, 0, false, false>]'
lcas.cpp:44:   instantiated from here
/usr/local/boost/boost_1_31_0/boost/crc.hpp:581: warning: right shift count >= 
   width of type


*** crc.hpp.orig	Tue Aug 10 14:10:34 2004
--- crc.hpp	Tue Aug 10 14:57:06 2004
***************
*** 527,532 ****
--- 527,556 ----
          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;
+ 
+         static unsigned char align_msb( value_type rem )
+             { return rem >> (Bits - CHAR_BIT); }
+     };
+ 
+     // 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;
+ 
+         static unsigned char align_msb( value_type rem )
+             { return rem << (CHAR_BIT - Bits); }
+     };
+     #endif
  
      // CRC helper routines
      template < std::size_t Bits, bool DoReflect >
***************
*** 555,561 ****
  
          // Compare a byte to the remainder's highest byte
          static  unsigned char  index( value_type rem, unsigned char x )
!             { return x ^ ( rem >> (DoReflect ? 0u : Bits - CHAR_BIT) ); }
  
          // Shift out the remainder's highest byte
          static  value_type  shift( value_type rem )
--- 579,587 ----
  
          // 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 )
***************
*** 578,584 ****
  
          // Compare a byte to the remainder's highest byte
          static  unsigned char  index( value_type rem, unsigned char x )
!             { return x ^ ( rem >> (Bits - CHAR_BIT) ); }
  
          // Shift out the remainder's highest byte
          static  value_type  shift( value_type rem )
--- 604,610 ----
  
          // 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 )