boost/boost/crc.hpp

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