boost/boost/crc.hpp

   1 //  Boost CRC library crc.hpp header file  -----------------------------------//
   2
   3 //  Copyright 2001 Daryle Walker.  Use, modification, and distribution are
   4 //  subject to the Boost Software License, Version 1.0.  (See accompanying file
   5 //  LICENSE_1_0.txt or a copy at <http://www.boost.org/LICENSE_1_0.txt>.)
   6
   7 //  See <http://www.boost.org/libs/crc/> for the library's home page.
   8
   9 #ifndef BOOST_CRC_HPP
  10 #define BOOST_CRC_HPP
  11
  12 #include <boost/config.hpp>   // for BOOST_STATIC_CONSTANT, etc.
  13 #include <boost/integer.hpp>  // for boost::uint_t
  14
  15 #include <climits>  // for CHAR_BIT, etc.
  16 #include <cstddef>  // for std::size_t
  17
  18 #include <boost/limits.hpp>  // for std::numeric_limits
  19
  20
  21 // The type of CRC parameters that can go in a template should be related
  22 // on the CRC's bit count.  This macro expresses that type in a compact
  23 // form, but also allows an alternate type for compilers that don't support
  24 // dependent types (in template value-parameters).
  25 #if !(defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS) || (defined(BOOST_MSVC) && (BOOST_MSVC <= 1300)))
  26 #define BOOST_CRC_PARM_TYPE  typename ::boost::uint_t<Bits>::fast
  27 #else
  28 #define BOOST_CRC_PARM_TYPE  unsigned long
  29 #endif
  30
  31 // Some compilers [MS VC++ 6] cannot correctly set up several versions of a
  32 // function template unless every template argument can be unambiguously
  33 // deduced from the function arguments.  (The bug is hidden if only one version
  34 // is needed.)  Since all of the CRC function templates have this problem, the
  35 // workaround is to make up a dummy function argument that encodes the template
  36 // arguments.  Calls to such template functions need all their template
  37 // arguments explicitly specified.  At least one compiler that needs this
  38 // workaround also needs the default value for the dummy argument to be
  39 // specified in the definition.
  40 #if defined(__GNUC__) || !defined(BOOST_NO_EXPLICIT_FUNCTION_TEMPLATE_ARGUMENTS)
  41 #define BOOST_CRC_DUMMY_PARM_TYPE
  42 #define BOOST_CRC_DUMMY_INIT
  43 #define BOOST_ACRC_DUMMY_PARM_TYPE
  44 #define BOOST_ACRC_DUMMY_INIT
  45 #else
  46 namespace boost { namespace detail {
  47     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  48      BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  49      bool ReflectIn, bool ReflectRem >
  50     struct dummy_crc_argument  { };
  51 } }
  52 #define BOOST_CRC_DUMMY_PARM_TYPE   , detail::dummy_crc_argument<Bits, \
  53  TruncPoly, InitRem, FinalXor, ReflectIn, ReflectRem> *p_
  54 #define BOOST_CRC_DUMMY_INIT        BOOST_CRC_DUMMY_PARM_TYPE = 0
  55 #define BOOST_ACRC_DUMMY_PARM_TYPE  , detail::dummy_crc_argument<Bits, \
  56  TruncPoly, 0, 0, false, false> *p_
  57 #define BOOST_ACRC_DUMMY_INIT       BOOST_ACRC_DUMMY_PARM_TYPE = 0
  58 #endif
  59
  60
  61 namespace boost
  62 {
  63
  64
  65 //  Forward declarations  ----------------------------------------------------//
  66
  67 template < std::size_t Bits >
  68     class crc_basic;
  69
  70 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly = 0u,
  71            BOOST_CRC_PARM_TYPE InitRem = 0u,
  72            BOOST_CRC_PARM_TYPE FinalXor = 0u, bool ReflectIn = false,
  73            bool ReflectRem = false >
  74     class crc_optimal;
  75
  76 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
  77            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
  78            bool ReflectIn, bool ReflectRem >
  79     typename uint_t<Bits>::fast  crc( void const *buffer,
  80      std::size_t byte_count
  81      BOOST_CRC_DUMMY_PARM_TYPE );
  82
  83 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
  84     typename uint_t<Bits>::fast  augmented_crc( void const *buffer,
  85      std::size_t byte_count, typename uint_t<Bits>::fast initial_remainder
  86      BOOST_ACRC_DUMMY_PARM_TYPE );
  87
  88 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
  89     typename uint_t<Bits>::fast  augmented_crc( void const *buffer,
  90      std::size_t byte_count
  91      BOOST_ACRC_DUMMY_PARM_TYPE );
  92
  93 typedef crc_optimal<16, 0x8005, 0, 0, true, true>         crc_16_type;
  94 typedef crc_optimal<16, 0x1021, 0xFFFF, 0, false, false>  crc_ccitt_type;
  95 typedef crc_optimal<16, 0x8408, 0, 0, true, true>         crc_xmodem_type;
  96
  97 typedef crc_optimal<32, 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true>
  98   crc_32_type;
  99
 100
 101 //  Forward declarations for implementation detail stuff  --------------------//
 102 //  (Just for the stuff that will be needed for the next two sections)
 103
 104 namespace detail
 105 {
 106     template < std::size_t Bits >
 107         struct mask_uint_t;
 108
 109     template <  >
 110         struct mask_uint_t< std::numeric_limits<unsigned char>::digits >;
 111
 112     #if USHRT_MAX > UCHAR_MAX
 113     template <  >
 114         struct mask_uint_t< std::numeric_limits<unsigned short>::digits >;
 115     #endif
 116
 117     #if UINT_MAX > USHRT_MAX
 118     template <  >
 119         struct mask_uint_t< std::numeric_limits<unsigned int>::digits >;
 120     #endif
 121
 122     #if ULONG_MAX > UINT_MAX
 123     template <  >
 124         struct mask_uint_t< std::numeric_limits<unsigned long>::digits >;
 125     #endif
 126
 127     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 128         struct crc_table_t;
 129
 130     template < std::size_t Bits, bool DoReflect >
 131         class crc_helper;
 132
 133     #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 134     template < std::size_t Bits >
 135         class crc_helper< Bits, false >;
 136     #endif
 137
 138 }  // namespace detail
 139
 140
 141 //  Simple cyclic redundancy code (CRC) class declaration  -------------------//
 142
 143 template < std::size_t Bits >
 144 class crc_basic
 145 {
 146     // Implementation type
 147     typedef detail::mask_uint_t<Bits>  masking_type;
 148
 149 public:
 150     // Type
 151     typedef typename masking_type::least  value_type;
 152
 153     // Constant for the template parameter
 154     BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );
 155
 156     // Constructor
 157     explicit  crc_basic( value_type truncated_polynominal,
 158                value_type initial_remainder = 0, value_type final_xor_value = 0,
 159                bool reflect_input = false, bool reflect_remainder = false );
 160
 161     // Internal Operations
 162     value_type  get_truncated_polynominal() const;
 163     value_type  get_initial_remainder() const;
 164     value_type  get_final_xor_value() const;
 165     bool        get_reflect_input() const;
 166     bool        get_reflect_remainder() const;
 167
 168     value_type  get_interim_remainder() const;
 169     void        reset( value_type new_rem );
 170     void        reset();
 171
 172     // External Operations
 173     void  process_bit( bool bit );
 174     void  process_bits( unsigned char bits, std::size_t bit_count );
 175     void  process_byte( unsigned char byte );
 176     void  process_block( void const *bytes_begin, void const *bytes_end );
 177     void  process_bytes( void const *buffer, std::size_t byte_count );
 178
 179     value_type  checksum() const;
 180
 181 private:
 182     // Member data
 183     value_type  rem_;
 184     value_type  poly_, init_, final_;  // non-const to allow assignability
 185     bool        rft_in_, rft_out_;     // non-const to allow assignability
 186
 187 };  // boost::crc_basic
 188
 189
 190 //  Optimized cyclic redundancy code (CRC) class declaration  ----------------//
 191
 192 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 193            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 194            bool ReflectIn, bool ReflectRem >
 195 class crc_optimal
 196 {
 197     // Implementation type
 198     typedef detail::mask_uint_t<Bits>  masking_type;
 199
 200 public:
 201     // Type
 202     typedef typename masking_type::fast  value_type;
 203
 204     // Constants for the template parameters
 205     BOOST_STATIC_CONSTANT( std::size_t, bit_count = Bits );
 206     BOOST_STATIC_CONSTANT( value_type, truncated_polynominal = TruncPoly );
 207     BOOST_STATIC_CONSTANT( value_type, initial_remainder = InitRem );
 208     BOOST_STATIC_CONSTANT( value_type, final_xor_value = FinalXor );
 209     BOOST_STATIC_CONSTANT( bool, reflect_input = ReflectIn );
 210     BOOST_STATIC_CONSTANT( bool, reflect_remainder = ReflectRem );
 211
 212     // Constructor
 213     explicit  crc_optimal( value_type init_rem = InitRem );
 214
 215     // Internal Operations
 216     value_type  get_truncated_polynominal() const;
 217     value_type  get_initial_remainder() const;
 218     value_type  get_final_xor_value() const;
 219     bool        get_reflect_input() const;
 220     bool        get_reflect_remainder() const;
 221
 222     value_type  get_interim_remainder() const;
 223     void        reset( value_type new_rem = InitRem );
 224
 225     // External Operations
 226     void  process_byte( unsigned char byte );
 227     void  process_block( void const *bytes_begin, void const *bytes_end );
 228     void  process_bytes( void const *buffer, std::size_t byte_count );
 229
 230     value_type  checksum() const;
 231
 232     // Operators
 233     void        operator ()( unsigned char byte );
 234     value_type  operator ()() const;
 235
 236 private:
 237     // The implementation of output reflection depends on both reflect states.
 238     BOOST_STATIC_CONSTANT( bool, reflect_output = (ReflectRem != ReflectIn) );
 239
 240     #ifndef __BORLANDC__
 241     #define BOOST_CRC_REF_OUT_VAL  reflect_output
 242     #else
 243     typedef crc_optimal  self_type;
 244     #define BOOST_CRC_REF_OUT_VAL  (self_type::reflect_output)
 245     #endif
 246
 247     // More implementation types
 248     typedef detail::crc_table_t<Bits, TruncPoly, ReflectIn>  crc_table_type;
 249     typedef detail::crc_helper<Bits, ReflectIn>              helper_type;
 250     typedef detail::crc_helper<Bits, BOOST_CRC_REF_OUT_VAL>  reflect_out_type;
 251
 252     #undef BOOST_CRC_REF_OUT_VAL
 253
 254     // Member data
 255     value_type  rem_;
 256
 257 };  // boost::crc_optimal
 258
 259
 260 //  Implementation detail stuff  ---------------------------------------------//
 261
 262 namespace detail
 263 {
 264     // Forward declarations for more implementation details
 265     template < std::size_t Bits >
 266         struct high_uint_t;
 267
 268     template < std::size_t Bits >
 269         struct reflector;
 270
 271
 272     // Traits class for mask; given the bit number
 273     // (1-based), get the mask for that bit by itself.
 274     template < std::size_t Bits >
 275     struct high_uint_t
 276         : boost::uint_t< Bits >
 277     {
 278         typedef boost::uint_t<Bits>        base_type;
 279         typedef typename base_type::least  least;
 280         typedef typename base_type::fast   fast;
 281
 282 #if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243
 283         static const least high_bit = 1ul << ( Bits - 1u );
 284         static const fast high_bit_fast = 1ul << ( Bits - 1u );
 285 #else
 286         BOOST_STATIC_CONSTANT( least, high_bit = (least( 1u ) << ( Bits
 287          - 1u )) );
 288         BOOST_STATIC_CONSTANT( fast, high_bit_fast = (fast( 1u ) << ( Bits
 289          - 1u )) );
 290 #endif
 291
 292     };  // boost::detail::high_uint_t
 293
 294
 295     // Reflection routine class wrapper
 296     // (since MS VC++ 6 couldn't handle the unwrapped version)
 297     template < std::size_t Bits >
 298     struct reflector
 299     {
 300         typedef typename boost::uint_t<Bits>::fast  value_type;
 301
 302         static  value_type  reflect( value_type x );
 303
 304     };  // boost::detail::reflector
 305
 306     // Function that reflects its argument
 307     template < std::size_t Bits >
 308     typename reflector<Bits>::value_type
 309     reflector<Bits>::reflect
 310     (
 311         typename reflector<Bits>::value_type  x
 312     )
 313     {
 314         value_type        reflection = 0;
 315         value_type const  one = 1;
 316
 317         for ( std::size_t i = 0 ; i < Bits ; ++i, x >>= 1 )
 318         {
 319             if ( x & one )
 320             {
 321                 reflection |= ( one << (Bits - 1u - i) );
 322             }
 323         }
 324
 325         return reflection;
 326     }
 327
 328
 329     // Traits class for masks; given the bit number (1-based),
 330     // get the mask for that bit and its lower bits.
 331     template < std::size_t Bits >
 332     struct mask_uint_t
 333         : high_uint_t< Bits >
 334     {
 335         typedef high_uint_t<Bits>          base_type;
 336         typedef typename base_type::least  least;
 337         typedef typename base_type::fast   fast;
 338
 339         #ifndef __BORLANDC__
 340         using base_type::high_bit;
 341         using base_type::high_bit_fast;
 342         #else
 343         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 344         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 345         #endif
 346
 347 #if defined(__EDG_VERSION__) && __EDG_VERSION__ <= 243
 348         static const least sig_bits = (~( ~( 0ul ) << Bits )) ;
 349 #else
 350         BOOST_STATIC_CONSTANT( least, sig_bits = (~( ~(least( 0u )) << Bits )) );
 351 #endif
 352         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 353
 354     };  // boost::detail::mask_uint_t
 355
 356     template <  >
 357     struct mask_uint_t< std::numeric_limits<unsigned char>::digits >
 358         : high_uint_t< std::numeric_limits<unsigned char>::digits >
 359     {
 360         typedef high_uint_t<std::numeric_limits<unsigned char>::digits>
 361           base_type;
 362         typedef base_type::least  least;
 363         typedef base_type::fast   fast;
 364
 365         #ifndef __BORLANDC__
 366         using base_type::high_bit;
 367         using base_type::high_bit_fast;
 368         #else
 369         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 370         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 371         #endif
 372
 373         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 374         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 375
 376     };  // boost::detail::mask_uint_t
 377
 378     #if USHRT_MAX > UCHAR_MAX
 379     template <  >
 380     struct mask_uint_t< std::numeric_limits<unsigned short>::digits >
 381         : high_uint_t< std::numeric_limits<unsigned short>::digits >
 382     {
 383         typedef high_uint_t<std::numeric_limits<unsigned short>::digits>
 384           base_type;
 385         typedef base_type::least  least;
 386         typedef base_type::fast   fast;
 387
 388         #ifndef __BORLANDC__
 389         using base_type::high_bit;
 390         using base_type::high_bit_fast;
 391         #else
 392         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 393         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 394         #endif
 395
 396         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 397         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 398
 399     };  // boost::detail::mask_uint_t
 400     #endif
 401
 402     #if UINT_MAX > USHRT_MAX
 403     template <  >
 404     struct mask_uint_t< std::numeric_limits<unsigned int>::digits >
 405         : high_uint_t< std::numeric_limits<unsigned int>::digits >
 406     {
 407         typedef high_uint_t<std::numeric_limits<unsigned int>::digits>
 408           base_type;
 409         typedef base_type::least  least;
 410         typedef base_type::fast   fast;
 411
 412         #ifndef __BORLANDC__
 413         using base_type::high_bit;
 414         using base_type::high_bit_fast;
 415         #else
 416         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 417         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 418         #endif
 419
 420         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 421         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 422
 423     };  // boost::detail::mask_uint_t
 424     #endif
 425
 426     #if ULONG_MAX > UINT_MAX
 427     template <  >
 428     struct mask_uint_t< std::numeric_limits<unsigned long>::digits >
 429         : high_uint_t< std::numeric_limits<unsigned long>::digits >
 430     {
 431         typedef high_uint_t<std::numeric_limits<unsigned long>::digits>
 432           base_type;
 433         typedef base_type::least  least;
 434         typedef base_type::fast   fast;
 435
 436         #ifndef __BORLANDC__
 437         using base_type::high_bit;
 438         using base_type::high_bit_fast;
 439         #else
 440         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 441         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 442         #endif
 443
 444         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 445         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 446
 447     };  // boost::detail::mask_uint_t
 448     #endif
 449
 450
 451     // CRC table generator
 452     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 453     struct crc_table_t
 454     {
 455         BOOST_STATIC_CONSTANT( std::size_t, byte_combos = (1ul << CHAR_BIT) );
 456
 457         typedef mask_uint_t<Bits>            masking_type;
 458         typedef typename masking_type::fast  value_type;
 459 #if defined(__BORLANDC__) && defined(_M_IX86) && (__BORLANDC__ == 0x560)
 460         // for some reason Borland's command line compiler (version 0x560)
 461         // chokes over this unless we do the calculation for it:
 462         typedef value_type                   table_type[ 0x100 ];
 463 #else
 464         typedef value_type                   table_type[ byte_combos ];
 465 #endif
 466
 467         static  void  init_table();
 468
 469         static  table_type  table_;
 470
 471     };  // boost::detail::crc_table_t
 472
 473     // CRC table generator static data member definition
 474     // (Some compilers [Borland C++] require the initializer to be present.)
 475     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 476     typename crc_table_t<Bits, TruncPoly, Reflect>::table_type
 477     crc_table_t<Bits, TruncPoly, Reflect>::table_
 478      = { 0 };
 479
 480     // Populate CRC lookup table
 481     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 482     void
 483     crc_table_t<Bits, TruncPoly, Reflect>::init_table
 484     (
 485     )
 486     {
 487         // compute table only on the first run
 488         static  bool  did_init = false;
 489         if ( did_init )  return;
 490
 491         // factor-out constants to avoid recalculation
 492         value_type const     fast_hi_bit = masking_type::high_bit_fast;
 493         unsigned char const  byte_hi_bit = 1u << (CHAR_BIT - 1u);
 494
 495         // loop over every possible dividend value
 496         unsigned char  dividend = 0;
 497         do
 498         {
 499             value_type  remainder = 0;
 500
 501             // go through all the dividend's bits
 502             for ( unsigned char mask = byte_hi_bit ; mask ; mask >>= 1 )
 503             {
 504                 // check if divisor fits
 505                 if ( dividend & mask )
 506                 {
 507                     remainder ^= fast_hi_bit;
 508                 }
 509
 510                 // do polynominal division
 511                 if ( remainder & fast_hi_bit )
 512                 {
 513                     remainder <<= 1;
 514                     remainder ^= TruncPoly;
 515                 }
 516                 else
 517                 {
 518                     remainder <<= 1;
 519                 }
 520             }
 521
 522             table_[ crc_helper<CHAR_BIT, Reflect>::reflect(dividend) ]
 523              = crc_helper<Bits, Reflect>::reflect( remainder );
 524         }
 525         while ( ++dividend );
 526
 527         did_init = true;
 528     }
 529
 530
 531     // CRC helper routines
 532     template < std::size_t Bits, bool DoReflect >
 533     class crc_helper
 534     {
 535     public:
 536         // Type
 537         typedef typename uint_t<Bits>::fast  value_type;
 538
 539     #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 540         // Possibly reflect a remainder
 541         static  value_type  reflect( value_type x )
 542             { return detail::reflector<Bits>::reflect( x ); }
 543
 544         // Compare a byte to the remainder's highest byte
 545         static  unsigned char  index( value_type rem, unsigned char x )
 546             { return x ^ rem; }
 547
 548         // Shift out the remainder's highest byte
 549         static  value_type  shift( value_type rem )
 550             { return rem >> CHAR_BIT; }
 551     #else
 552         // Possibly reflect a remainder
 553         static  value_type  reflect( value_type x )
 554             { return DoReflect ? detail::reflector<Bits>::reflect( x ) : x; }
 555
 556         // Compare a byte to the remainder's highest byte
 557         static  unsigned char  index( value_type rem, unsigned char x )
 558             { return x ^ ( rem >> (DoReflect ? 0u : Bits - CHAR_BIT) ); }
 559
 560         // Shift out the remainder's highest byte
 561         static  value_type  shift( value_type rem )
 562             { return DoReflect ? rem >> CHAR_BIT : rem << CHAR_BIT; }
 563     #endif
 564
 565     };  // boost::detail::crc_helper
 566
 567     #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 568     template < std::size_t Bits >
 569     class crc_helper<Bits, false>
 570     {
 571     public:
 572         // Type
 573         typedef typename uint_t<Bits>::fast  value_type;
 574
 575         // Possibly reflect a remainder
 576         static  value_type  reflect( value_type x )
 577             { return x; }
 578
 579         // Compare a byte to the remainder's highest byte
 580         static  unsigned char  index( value_type rem, unsigned char x )
 581             { return x ^ ( rem >> (Bits - CHAR_BIT) ); }
 582
 583         // Shift out the remainder's highest byte
 584         static  value_type  shift( value_type rem )
 585             { return rem << CHAR_BIT; }
 586
 587     };  // boost::detail::crc_helper
 588     #endif
 589
 590
 591 }  // namespace detail
 592
 593
 594 //  Simple CRC class function definitions  -----------------------------------//
 595
 596 template < std::size_t Bits >
 597 inline
 598 crc_basic<Bits>::crc_basic
 599 (
 600     typename crc_basic<Bits>::value_type  truncated_polynominal,
 601     typename crc_basic<Bits>::value_type  initial_remainder,      // = 0
 602     typename crc_basic<Bits>::value_type  final_xor_value,        // = 0
 603     bool                                  reflect_input,          // = false
 604     bool                                  reflect_remainder       // = false
 605 )
 606     : rem_( initial_remainder ), poly_( truncated_polynominal )
 607     , init_( initial_remainder ), final_( final_xor_value )
 608     , rft_in_( reflect_input ), rft_out_( reflect_remainder )
 609 {
 610 }
 611
 612 template < std::size_t Bits >
 613 inline
 614 typename crc_basic<Bits>::value_type
 615 crc_basic<Bits>::get_truncated_polynominal
 616 (
 617 ) const
 618 {
 619     return poly_;
 620 }
 621
 622 template < std::size_t Bits >
 623 inline
 624 typename crc_basic<Bits>::value_type
 625 crc_basic<Bits>::get_initial_remainder
 626 (
 627 ) const
 628 {
 629     return init_;
 630 }
 631
 632 template < std::size_t Bits >
 633 inline
 634 typename crc_basic<Bits>::value_type
 635 crc_basic<Bits>::get_final_xor_value
 636 (
 637 ) const
 638 {
 639     return final_;
 640 }
 641
 642 template < std::size_t Bits >
 643 inline
 644 bool
 645 crc_basic<Bits>::get_reflect_input
 646 (
 647 ) const
 648 {
 649     return rft_in_;
 650 }
 651
 652 template < std::size_t Bits >
 653 inline
 654 bool
 655 crc_basic<Bits>::get_reflect_remainder
 656 (
 657 ) const
 658 {
 659     return rft_out_;
 660 }
 661
 662 template < std::size_t Bits >
 663 inline
 664 typename crc_basic<Bits>::value_type
 665 crc_basic<Bits>::get_interim_remainder
 666 (
 667 ) const
 668 {
 669     return rem_ & masking_type::sig_bits;
 670 }
 671
 672 template < std::size_t Bits >
 673 inline
 674 void
 675 crc_basic<Bits>::reset
 676 (
 677     typename crc_basic<Bits>::value_type  new_rem
 678 )
 679 {
 680     rem_ = new_rem;
 681 }
 682
 683 template < std::size_t Bits >
 684 inline
 685 void
 686 crc_basic<Bits>::reset
 687 (
 688 )
 689 {
 690     this->reset( this->get_initial_remainder() );
 691 }
 692
 693 template < std::size_t Bits >
 694 inline
 695 void
 696 crc_basic<Bits>::process_bit
 697 (
 698     bool  bit
 699 )
 700 {
 701     value_type const  high_bit_mask = masking_type::high_bit;
 702
 703     // compare the new bit with the remainder's highest
 704     rem_ ^= ( bit ? high_bit_mask : 0u );
 705
 706     // a full polynominal division step is done when the highest bit is one
 707     bool const  do_poly_div = static_cast<bool>( rem_ & high_bit_mask );
 708
 709     // shift out the highest bit
 710     rem_ <<= 1;
 711
 712     // carry out the division, if needed
 713     if ( do_poly_div )
 714     {
 715         rem_ ^= poly_;
 716     }
 717 }
 718
 719 template < std::size_t Bits >
 720 void
 721 crc_basic<Bits>::process_bits
 722 (
 723     unsigned char  bits,
 724     std::size_t    bit_count
 725 )
 726 {
 727     // ignore the bits above the ones we want
 728     bits <<= CHAR_BIT - bit_count;
 729
 730     // compute the CRC for each bit, starting with the upper ones
 731     unsigned char const  high_bit_mask = 1u << ( CHAR_BIT - 1u );
 732     for ( std::size_t i = bit_count ; i > 0u ; --i, bits <<= 1u )
 733     {
 734         process_bit( static_cast<bool>(bits & high_bit_mask) );
 735     }
 736 }
 737
 738 template < std::size_t Bits >
 739 inline
 740 void
 741 crc_basic<Bits>::process_byte
 742 (
 743     unsigned char  byte
 744 )
 745 {
 746     process_bits( (rft_in_ ? detail::reflector<CHAR_BIT>::reflect(byte)
 747      : byte), CHAR_BIT );
 748 }
 749
 750 template < std::size_t Bits >
 751 void
 752 crc_basic<Bits>::process_block
 753 (
 754     void const *  bytes_begin,
 755     void const *  bytes_end
 756 )
 757 {
 758     for ( unsigned char const * p
 759      = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p )
 760     {
 761         process_byte( *p );
 762     }
 763 }
 764
 765 template < std::size_t Bits >
 766 inline
 767 void
 768 crc_basic<Bits>::process_bytes
 769 (
 770     void const *  buffer,
 771     std::size_t   byte_count
 772 )
 773 {
 774     unsigned char const * const  b = static_cast<unsigned char const *>(
 775      buffer );
 776
 777     process_block( b, b + byte_count );
 778 }
 779
 780 template < std::size_t Bits >
 781 inline
 782 typename crc_basic<Bits>::value_type
 783 crc_basic<Bits>::checksum
 784 (
 785 ) const
 786 {
 787     return ( (rft_out_ ? detail::reflector<Bits>::reflect( rem_ ) : rem_)
 788      ^ final_ ) & masking_type::sig_bits;
 789 }
 790
 791
 792 //  Optimized CRC class function definitions  --------------------------------//
 793
 794 // Macro to compact code
 795 #define BOOST_CRC_OPTIMAL_NAME  crc_optimal<Bits, TruncPoly, InitRem, \
 796  FinalXor, ReflectIn, ReflectRem>
 797
 798 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 799            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 800            bool ReflectIn, bool ReflectRem >
 801 inline
 802 BOOST_CRC_OPTIMAL_NAME::crc_optimal
 803 (
 804     typename BOOST_CRC_OPTIMAL_NAME::value_type  init_rem  // = InitRem
 805 )
 806     : rem_( helper_type::reflect(init_rem) )
 807 {
 808     crc_table_type::init_table();
 809 }
 810
 811 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 812            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 813            bool ReflectIn, bool ReflectRem >
 814 inline
 815 typename BOOST_CRC_OPTIMAL_NAME::value_type
 816 BOOST_CRC_OPTIMAL_NAME::get_truncated_polynominal
 817 (
 818 ) const
 819 {
 820     return TruncPoly;
 821 }
 822
 823 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 824            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 825            bool ReflectIn, bool ReflectRem >
 826 inline
 827 typename BOOST_CRC_OPTIMAL_NAME::value_type
 828 BOOST_CRC_OPTIMAL_NAME::get_initial_remainder
 829 (
 830 ) const
 831 {
 832     return InitRem;
 833 }
 834
 835 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 836            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 837            bool ReflectIn, bool ReflectRem >
 838 inline
 839 typename BOOST_CRC_OPTIMAL_NAME::value_type
 840 BOOST_CRC_OPTIMAL_NAME::get_final_xor_value
 841 (
 842 ) const
 843 {
 844     return FinalXor;
 845 }
 846
 847 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 848            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 849            bool ReflectIn, bool ReflectRem >
 850 inline
 851 bool
 852 BOOST_CRC_OPTIMAL_NAME::get_reflect_input
 853 (
 854 ) const
 855 {
 856     return ReflectIn;
 857 }
 858
 859 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 860            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 861            bool ReflectIn, bool ReflectRem >
 862 inline
 863 bool
 864 BOOST_CRC_OPTIMAL_NAME::get_reflect_remainder
 865 (
 866 ) const
 867 {
 868     return ReflectRem;
 869 }
 870
 871 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 872            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 873            bool ReflectIn, bool ReflectRem >
 874 inline
 875 typename BOOST_CRC_OPTIMAL_NAME::value_type
 876 BOOST_CRC_OPTIMAL_NAME::get_interim_remainder
 877 (
 878 ) const
 879 {
 880     // Interim remainder should be _un_-reflected, so we have to undo it.
 881     return helper_type::reflect( rem_ ) & masking_type::sig_bits_fast;
 882 }
 883
 884 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 885            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 886            bool ReflectIn, bool ReflectRem >
 887 inline
 888 void
 889 BOOST_CRC_OPTIMAL_NAME::reset
 890 (
 891     typename BOOST_CRC_OPTIMAL_NAME::value_type  new_rem  // = InitRem
 892 )
 893 {
 894     rem_ = helper_type::reflect( new_rem );
 895 }
 896
 897 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 898            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 899            bool ReflectIn, bool ReflectRem >
 900 inline
 901 void
 902 BOOST_CRC_OPTIMAL_NAME::process_byte
 903 (
 904     unsigned char  byte
 905 )
 906 {
 907     process_bytes( &byte, sizeof(byte) );
 908 }
 909
 910 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 911            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 912            bool ReflectIn, bool ReflectRem >
 913 void
 914 BOOST_CRC_OPTIMAL_NAME::process_block
 915 (
 916     void const *  bytes_begin,
 917     void const *  bytes_end
 918 )
 919 {
 920     // Recompute the CRC for each byte passed
 921     for ( unsigned char const * p
 922      = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p )
 923     {
 924         // Compare the new byte with the remainder's higher bits to
 925         // get the new bits, shift out the remainder's current higher
 926         // bits, and update the remainder with the polynominal division
 927         // of the new bits.
 928         unsigned char const  byte_index = helper_type::index( rem_, *p );
 929         rem_ = helper_type::shift( rem_ );
 930         rem_ ^= crc_table_type::table_[ byte_index ];
 931     }
 932 }
 933
 934 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 935            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 936            bool ReflectIn, bool ReflectRem >
 937 inline
 938 void
 939 BOOST_CRC_OPTIMAL_NAME::process_bytes
 940 (
 941     void const *   buffer,
 942     std::size_t  byte_count
 943 )
 944 {
 945     unsigned char const * const  b = static_cast<unsigned char const *>(
 946      buffer );
 947     process_block( b, b + byte_count );
 948 }
 949
 950 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 951            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 952            bool ReflectIn, bool ReflectRem >
 953 inline
 954 typename BOOST_CRC_OPTIMAL_NAME::value_type
 955 BOOST_CRC_OPTIMAL_NAME::checksum
 956 (
 957 ) const
 958 {
 959     return ( reflect_out_type::reflect(rem_) ^ get_final_xor_value() )
 960      & masking_type::sig_bits_fast;
 961 }
 962
 963 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 964            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 965            bool ReflectIn, bool ReflectRem >
 966 inline
 967 void
 968 BOOST_CRC_OPTIMAL_NAME::operator ()
 969 (
 970     unsigned char  byte
 971 )
 972 {
 973     process_byte( byte );
 974 }
 975
 976 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 977            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 978            bool ReflectIn, bool ReflectRem >
 979 inline
 980 typename BOOST_CRC_OPTIMAL_NAME::value_type
 981 BOOST_CRC_OPTIMAL_NAME::operator ()
 982 (
 983 ) const
 984 {
 985     return checksum();
 986 }
 987
 988
 989 //  CRC computation function definition  -------------------------------------//
 990
 991 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 992            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 993            bool ReflectIn, bool ReflectRem >
 994 inline
 995 typename uint_t<Bits>::fast
 996 crc
 997 (
 998     void const *  buffer,
 999     std::size_t   byte_count
1000     BOOST_CRC_DUMMY_INIT
1001 )
1002 {
1003     BOOST_CRC_OPTIMAL_NAME  computer;
1004     computer.process_bytes( buffer, byte_count );
1005     return computer.checksum();
1006 }
1007
1008
1009 //  Augmented-message CRC computation function definitions  ------------------//
1010
1011 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
1012 typename uint_t<Bits>::fast
1013 augmented_crc
1014 (
1015     void const *                 buffer,
1016     std::size_t                  byte_count,
1017     typename uint_t<Bits>::fast  initial_remainder
1018     BOOST_ACRC_DUMMY_INIT
1019 )
1020 {
1021     typedef unsigned char                                byte_type;
1022     typedef detail::mask_uint_t<Bits>                    masking_type;
1023     typedef detail::crc_table_t<Bits, TruncPoly, false>  crc_table_type;
1024
1025     typename masking_type::fast  rem = initial_remainder;
1026     byte_type const * const      b = static_cast<byte_type const *>( buffer );
1027     byte_type const * const      e = b + byte_count;
1028
1029     crc_table_type::init_table();
1030     for ( byte_type const * p = b ; p < e ; ++p )
1031     {
1032         // Use the current top byte as the table index to the next
1033         // "partial product."  Shift out that top byte, shifting in
1034         // the next augmented-message byte.  Complete the division.
1035         byte_type const  byte_index = rem >> ( Bits - CHAR_BIT );
1036         rem <<= CHAR_BIT;
1037         rem |= *p;
1038         rem ^= crc_table_type::table_[ byte_index ];
1039     }
1040
1041     return rem & masking_type::sig_bits_fast;
1042 }
1043
1044 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
1045 inline
1046 typename uint_t<Bits>::fast
1047 augmented_crc
1048 (
1049     void const *  buffer,
1050     std::size_t   byte_count
1051     BOOST_ACRC_DUMMY_INIT
1052 )
1053 {
1054    // The last function argument has its type specified so the other version of
1055    // augmented_crc will be called.  If the cast wasn't in place, and the
1056    // BOOST_ACRC_DUMMY_INIT added a third argument (for a workaround), the "0"
1057    // would match as that third argument, leading to infinite recursion.
1058    return augmented_crc<Bits, TruncPoly>( buffer, byte_count,
1059     static_cast<typename uint_t<Bits>::fast>(0) );
1060 }
1061
1062
1063 }  // namespace boost
1064
1065
1066 // Undo header-private macros
1067 #undef BOOST_CRC_OPTIMAL_NAME
1068 #undef BOOST_ACRC_DUMMY_INIT
1069 #undef BOOST_ACRC_DUMMY_PARM_TYPE
1070 #undef BOOST_CRC_DUMMY_INIT
1071 #undef BOOST_CRC_DUMMY_PARM_TYPE
1072 #undef BOOST_CRC_PARM_TYPE
1073
1074
1075 #endif  // BOOST_CRC_HPP
1076