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 for updates, documentation, and revision history.
   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 #ifndef BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS
  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 #ifndef 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 #ifdef __DECCXX
 284             static const least high_bit = 1ul << (Bits - 1u);
 285             static const fast high_bit_fast = 1ul << (Bits - 1u);
 286 #else
 287         BOOST_STATIC_CONSTANT( least, high_bit = (least( 1u ) << ( Bits
 288          - 1u )) );
 289         BOOST_STATIC_CONSTANT( fast, high_bit_fast = (fast( 1u ) << ( Bits
 290          - 1u )) );
 291 #endif
 292
 293     };  // boost::detail::high_uint_t
 294
 295
 296     // Reflection routine class wrapper
 297     // (since MS VC++ 6 couldn't handle the unwrapped version)
 298     template < std::size_t Bits >
 299     struct reflector
 300     {
 301         typedef typename boost::uint_t<Bits>::fast  value_type;
 302
 303         static  value_type  reflect( value_type x );
 304
 305     };  // boost::detail::reflector
 306
 307     // Function that reflects its argument
 308     template < std::size_t Bits >
 309     typename reflector<Bits>::value_type
 310     reflector<Bits>::reflect
 311     (
 312         typename reflector<Bits>::value_type  x
 313     )
 314     {
 315         value_type        reflection = 0;
 316         value_type const  one = 1;
 317
 318         for ( std::size_t i = 0 ; i < Bits ; ++i, x >>= 1 )
 319         {
 320             if ( x & one )
 321             {
 322                 reflection |= ( one << (Bits - 1u - i) );
 323             }
 324         }
 325
 326         return reflection;
 327     }
 328
 329
 330     // Traits class for masks; given the bit number (1-based),
 331     // get the mask for that bit and its lower bits.
 332     template < std::size_t Bits >
 333     struct mask_uint_t
 334         : high_uint_t< Bits >
 335     {
 336         typedef high_uint_t<Bits>          base_type;
 337         typedef typename base_type::least  least;
 338         typedef typename base_type::fast   fast;
 339
 340         #ifndef __BORLANDC__
 341         using base_type::high_bit;
 342         using base_type::high_bit_fast;
 343         #else
 344         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 345         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 346         #endif
 347
 348 #ifdef __DECCXX
 349             static const least sig_bits = (~( ~(0ul) << Bits));
 350 #else
 351         BOOST_STATIC_CONSTANT( least, sig_bits = (~( ~(least( 0u )) << Bits )) );
 352 #endif
 353         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 354
 355     };  // boost::detail::mask_uint_t
 356
 357     template <  >
 358     struct mask_uint_t< std::numeric_limits<unsigned char>::digits >
 359         : high_uint_t< std::numeric_limits<unsigned char>::digits >
 360     {
 361         typedef high_uint_t<std::numeric_limits<unsigned char>::digits>
 362           base_type;
 363         typedef base_type::least  least;
 364         typedef base_type::fast   fast;
 365
 366         #ifndef __BORLANDC__
 367         using base_type::high_bit;
 368         using base_type::high_bit_fast;
 369         #else
 370         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 371         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 372         #endif
 373
 374         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 375         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 376
 377     };  // boost::detail::mask_uint_t
 378
 379     #if USHRT_MAX > UCHAR_MAX
 380     template <  >
 381     struct mask_uint_t< std::numeric_limits<unsigned short>::digits >
 382         : high_uint_t< std::numeric_limits<unsigned short>::digits >
 383     {
 384         typedef high_uint_t<std::numeric_limits<unsigned short>::digits>
 385           base_type;
 386         typedef base_type::least  least;
 387         typedef base_type::fast   fast;
 388
 389         #ifndef __BORLANDC__
 390         using base_type::high_bit;
 391         using base_type::high_bit_fast;
 392         #else
 393         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 394         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 395         #endif
 396
 397         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 398         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 399
 400     };  // boost::detail::mask_uint_t
 401     #endif
 402
 403     #if UINT_MAX > USHRT_MAX
 404     template <  >
 405     struct mask_uint_t< std::numeric_limits<unsigned int>::digits >
 406         : high_uint_t< std::numeric_limits<unsigned int>::digits >
 407     {
 408         typedef high_uint_t<std::numeric_limits<unsigned int>::digits>
 409           base_type;
 410         typedef base_type::least  least;
 411         typedef base_type::fast   fast;
 412
 413         #ifndef __BORLANDC__
 414         using base_type::high_bit;
 415         using base_type::high_bit_fast;
 416         #else
 417         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 418         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 419         #endif
 420
 421         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 422         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 423
 424     };  // boost::detail::mask_uint_t
 425     #endif
 426
 427     #if ULONG_MAX > UINT_MAX
 428     template <  >
 429     struct mask_uint_t< std::numeric_limits<unsigned long>::digits >
 430         : high_uint_t< std::numeric_limits<unsigned long>::digits >
 431     {
 432         typedef high_uint_t<std::numeric_limits<unsigned long>::digits>
 433           base_type;
 434         typedef base_type::least  least;
 435         typedef base_type::fast   fast;
 436
 437         #ifndef __BORLANDC__
 438         using base_type::high_bit;
 439         using base_type::high_bit_fast;
 440         #else
 441         BOOST_STATIC_CONSTANT( least, high_bit = base_type::high_bit );
 442         BOOST_STATIC_CONSTANT( fast, high_bit_fast = base_type::high_bit_fast );
 443         #endif
 444
 445         BOOST_STATIC_CONSTANT( least, sig_bits = (~( least(0u) )) );
 446         BOOST_STATIC_CONSTANT( fast, sig_bits_fast = fast(sig_bits) );
 447
 448     };  // boost::detail::mask_uint_t
 449     #endif
 450
 451
 452     // CRC table generator
 453     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 454     struct crc_table_t
 455     {
 456         BOOST_STATIC_CONSTANT( std::size_t, byte_combos = (1ul << CHAR_BIT) );
 457
 458         typedef mask_uint_t<Bits>            masking_type;
 459         typedef typename masking_type::fast  value_type;
 460         typedef value_type                   table_type[ byte_combos ];
 461
 462         static  void  init_table();
 463
 464         static  table_type  table_;
 465
 466     };  // boost::detail::crc_table_t
 467
 468     // CRC table generator static data member definition
 469     // (Some compilers [Borland C++] require the initializer to be present.)
 470     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 471     typename crc_table_t<Bits, TruncPoly, Reflect>::table_type
 472     crc_table_t<Bits, TruncPoly, Reflect>::table_
 473      = { 0 };
 474
 475     // Populate CRC lookup table
 476     template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly, bool Reflect >
 477     void
 478     crc_table_t<Bits, TruncPoly, Reflect>::init_table
 479     (
 480     )
 481     {
 482         // compute table only on the first run
 483         static  bool  did_init = false;
 484         if ( did_init )  return;
 485
 486         // factor-out constants to avoid recalculation
 487         value_type const     fast_hi_bit = masking_type::high_bit_fast;
 488         unsigned char const  byte_hi_bit = 1u << (CHAR_BIT - 1u);
 489
 490         // loop over every possible dividend value
 491         unsigned char  dividend = 0;
 492         do
 493         {
 494             value_type  remainder = 0;
 495
 496             // go through all the dividend's bits
 497             for ( unsigned char mask = byte_hi_bit ; mask ; mask >>= 1 )
 498             {
 499                 // check if divisor fits
 500                 if ( dividend & mask )
 501                 {
 502                     remainder ^= fast_hi_bit;
 503                 }
 504
 505                 // do polynominal division
 506                 if ( remainder & fast_hi_bit )
 507                 {
 508                     remainder <<= 1;
 509                     remainder ^= TruncPoly;
 510                 }
 511                 else
 512                 {
 513                     remainder <<= 1;
 514                 }
 515             }
 516
 517             table_[ crc_helper<CHAR_BIT, Reflect>::reflect(dividend) ]
 518              = crc_helper<Bits, Reflect>::reflect( remainder );
 519         }
 520         while ( ++dividend );
 521
 522         did_init = true;
 523     }
 524
 525
 526     // CRC helper routines
 527     template < std::size_t Bits, bool DoReflect >
 528     class crc_helper
 529     {
 530     public:
 531         // Type
 532         typedef typename uint_t<Bits>::fast  value_type;
 533
 534     #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 535         // Possibly reflect a remainder
 536         static  value_type  reflect( value_type x )
 537             { return detail::reflector<Bits>::reflect( x ); }
 538
 539         // Compare a byte to the remainder's highest byte
 540         static  unsigned char  index( value_type rem, unsigned char x )
 541             { return x ^ rem; }
 542
 543         // Shift out the remainder's highest byte
 544         static  value_type  shift( value_type rem )
 545             { return rem >> CHAR_BIT; }
 546     #else
 547         // Possibly reflect a remainder
 548         static  value_type  reflect( value_type x )
 549             { return DoReflect ? detail::reflector<Bits>::reflect( x ) : x; }
 550
 551         // Compare a byte to the remainder's highest byte
 552         static  unsigned char  index( value_type rem, unsigned char x )
 553             { return x ^ ( rem >> (DoReflect ? 0u : Bits - CHAR_BIT) ); }
 554
 555         // Shift out the remainder's highest byte
 556         static  value_type  shift( value_type rem )
 557             { return DoReflect ? rem >> CHAR_BIT : rem << CHAR_BIT; }
 558     #endif
 559
 560     };  // boost::detail::crc_helper
 561
 562     #ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
 563     template < std::size_t Bits >
 564     class crc_helper<Bits, false>
 565     {
 566     public:
 567         // Type
 568         typedef typename uint_t<Bits>::fast  value_type;
 569
 570         // Possibly reflect a remainder
 571         static  value_type  reflect( value_type x )
 572             { return x; }
 573
 574         // Compare a byte to the remainder's highest byte
 575         static  unsigned char  index( value_type rem, unsigned char x )
 576             { return x ^ ( rem >> (Bits - CHAR_BIT) ); }
 577
 578         // Shift out the remainder's highest byte
 579         static  value_type  shift( value_type rem )
 580             { return rem << CHAR_BIT; }
 581
 582     };  // boost::detail::crc_helper
 583     #endif
 584
 585
 586 }  // namespace detail
 587
 588
 589 //  Simple CRC class function definitions  -----------------------------------//
 590
 591 template < std::size_t Bits >
 592 inline
 593 crc_basic<Bits>::crc_basic
 594 (
 595     typename crc_basic<Bits>::value_type  truncated_polynominal,
 596     typename crc_basic<Bits>::value_type  initial_remainder,      // = 0
 597     typename crc_basic<Bits>::value_type  final_xor_value,        // = 0
 598     bool                                  reflect_input,          // = false
 599     bool                                  reflect_remainder       // = false
 600 )
 601     : rem_( initial_remainder ), poly_( truncated_polynominal )
 602     , init_( initial_remainder ), final_( final_xor_value )
 603     , rft_in_( reflect_input ), rft_out_( reflect_remainder )
 604 {
 605 }
 606
 607 template < std::size_t Bits >
 608 inline
 609 typename crc_basic<Bits>::value_type
 610 crc_basic<Bits>::get_truncated_polynominal
 611 (
 612 ) const
 613 {
 614     return poly_;
 615 }
 616
 617 template < std::size_t Bits >
 618 inline
 619 typename crc_basic<Bits>::value_type
 620 crc_basic<Bits>::get_initial_remainder
 621 (
 622 ) const
 623 {
 624     return init_;
 625 }
 626
 627 template < std::size_t Bits >
 628 inline
 629 typename crc_basic<Bits>::value_type
 630 crc_basic<Bits>::get_final_xor_value
 631 (
 632 ) const
 633 {
 634     return final_;
 635 }
 636
 637 template < std::size_t Bits >
 638 inline
 639 bool
 640 crc_basic<Bits>::get_reflect_input
 641 (
 642 ) const
 643 {
 644     return rft_in_;
 645 }
 646
 647 template < std::size_t Bits >
 648 inline
 649 bool
 650 crc_basic<Bits>::get_reflect_remainder
 651 (
 652 ) const
 653 {
 654     return rft_out_;
 655 }
 656
 657 template < std::size_t Bits >
 658 inline
 659 typename crc_basic<Bits>::value_type
 660 crc_basic<Bits>::get_interim_remainder
 661 (
 662 ) const
 663 {
 664     return rem_ & masking_type::sig_bits;
 665 }
 666
 667 template < std::size_t Bits >
 668 inline
 669 void
 670 crc_basic<Bits>::reset
 671 (
 672     typename crc_basic<Bits>::value_type  new_rem
 673 )
 674 {
 675     rem_ = new_rem;
 676 }
 677
 678 template < std::size_t Bits >
 679 inline
 680 void
 681 crc_basic<Bits>::reset
 682 (
 683 )
 684 {
 685     this->reset( this->get_initial_remainder() );
 686 }
 687
 688 template < std::size_t Bits >
 689 inline
 690 void
 691 crc_basic<Bits>::process_bit
 692 (
 693     bool  bit
 694 )
 695 {
 696     value_type const  high_bit_mask = masking_type::high_bit;
 697
 698     // compare the new bit with the remainder's highest
 699     rem_ ^= ( bit ? high_bit_mask : 0u );
 700
 701     // a full polynominal division step is done when the highest bit is one
 702     bool const  do_poly_div = static_cast<bool>( rem_ & high_bit_mask );
 703
 704     // shift out the highest bit
 705     rem_ <<= 1;
 706
 707     // carry out the division, if needed
 708     if ( do_poly_div )
 709     {
 710         rem_ ^= poly_;
 711     }
 712 }
 713
 714 template < std::size_t Bits >
 715 void
 716 crc_basic<Bits>::process_bits
 717 (
 718     unsigned char  bits,
 719     std::size_t    bit_count
 720 )
 721 {
 722     // ignore the bits above the ones we want
 723     bits <<= CHAR_BIT - bit_count;
 724
 725     // compute the CRC for each bit, starting with the upper ones
 726     unsigned char const  high_bit_mask = 1u << ( CHAR_BIT - 1u );
 727     for ( std::size_t i = bit_count ; i > 0u ; --i, bits <<= 1u )
 728     {
 729         process_bit( static_cast<bool>(bits & high_bit_mask) );
 730     }
 731 }
 732
 733 template < std::size_t Bits >
 734 inline
 735 void
 736 crc_basic<Bits>::process_byte
 737 (
 738     unsigned char  byte
 739 )
 740 {
 741     process_bits( (rft_in_ ? detail::reflector<CHAR_BIT>::reflect(byte)
 742      : byte), CHAR_BIT );
 743 }
 744
 745 template < std::size_t Bits >
 746 void
 747 crc_basic<Bits>::process_block
 748 (
 749     void const *  bytes_begin,
 750     void const *  bytes_end
 751 )
 752 {
 753     for ( unsigned char const * p
 754      = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p )
 755     {
 756         process_byte( *p );
 757     }
 758 }
 759
 760 template < std::size_t Bits >
 761 inline
 762 void
 763 crc_basic<Bits>::process_bytes
 764 (
 765     void const *  buffer,
 766     std::size_t   byte_count
 767 )
 768 {
 769     unsigned char const * const  b = static_cast<unsigned char const *>(
 770      buffer );
 771
 772     process_block( b, b + byte_count );
 773 }
 774
 775 template < std::size_t Bits >
 776 inline
 777 typename crc_basic<Bits>::value_type
 778 crc_basic<Bits>::checksum
 779 (
 780 ) const
 781 {
 782     return ( (rft_out_ ? detail::reflector<Bits>::reflect( rem_ ) : rem_)
 783      ^ final_ ) & masking_type::sig_bits;
 784 }
 785
 786
 787 //  Optimized CRC class function definitions  --------------------------------//
 788
 789 // Macro to compact code
 790 #define BOOST_CRC_OPTIMAL_NAME  crc_optimal<Bits, TruncPoly, InitRem, \
 791  FinalXor, ReflectIn, ReflectRem>
 792
 793 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 794            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 795            bool ReflectIn, bool ReflectRem >
 796 inline
 797 BOOST_CRC_OPTIMAL_NAME::crc_optimal
 798 (
 799     typename BOOST_CRC_OPTIMAL_NAME::value_type  init_rem  // = InitRem
 800 )
 801     : rem_( helper_type::reflect(init_rem) )
 802 {
 803     crc_table_type::init_table();
 804 }
 805
 806 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 807            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 808            bool ReflectIn, bool ReflectRem >
 809 inline
 810 typename BOOST_CRC_OPTIMAL_NAME::value_type
 811 BOOST_CRC_OPTIMAL_NAME::get_truncated_polynominal
 812 (
 813 ) const
 814 {
 815     return TruncPoly;
 816 }
 817
 818 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 819            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 820            bool ReflectIn, bool ReflectRem >
 821 inline
 822 typename BOOST_CRC_OPTIMAL_NAME::value_type
 823 BOOST_CRC_OPTIMAL_NAME::get_initial_remainder
 824 (
 825 ) const
 826 {
 827     return InitRem;
 828 }
 829
 830 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 831            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 832            bool ReflectIn, bool ReflectRem >
 833 inline
 834 typename BOOST_CRC_OPTIMAL_NAME::value_type
 835 BOOST_CRC_OPTIMAL_NAME::get_final_xor_value
 836 (
 837 ) const
 838 {
 839     return FinalXor;
 840 }
 841
 842 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 843            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 844            bool ReflectIn, bool ReflectRem >
 845 inline
 846 bool
 847 BOOST_CRC_OPTIMAL_NAME::get_reflect_input
 848 (
 849 ) const
 850 {
 851     return ReflectIn;
 852 }
 853
 854 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 855            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 856            bool ReflectIn, bool ReflectRem >
 857 inline
 858 bool
 859 BOOST_CRC_OPTIMAL_NAME::get_reflect_remainder
 860 (
 861 ) const
 862 {
 863     return ReflectRem;
 864 }
 865
 866 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 867            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 868            bool ReflectIn, bool ReflectRem >
 869 inline
 870 typename BOOST_CRC_OPTIMAL_NAME::value_type
 871 BOOST_CRC_OPTIMAL_NAME::get_interim_remainder
 872 (
 873 ) const
 874 {
 875     // Interim remainder should be _un_-reflected, so we have to undo it.
 876     return helper_type::reflect( rem_ ) & masking_type::sig_bits_fast;
 877 }
 878
 879 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 880            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 881            bool ReflectIn, bool ReflectRem >
 882 inline
 883 void
 884 BOOST_CRC_OPTIMAL_NAME::reset
 885 (
 886     typename BOOST_CRC_OPTIMAL_NAME::value_type  new_rem  // = InitRem
 887 )
 888 {
 889     rem_ = helper_type::reflect( new_rem );
 890 }
 891
 892 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 893            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 894            bool ReflectIn, bool ReflectRem >
 895 inline
 896 void
 897 BOOST_CRC_OPTIMAL_NAME::process_byte
 898 (
 899     unsigned char  byte
 900 )
 901 {
 902     process_bytes( &byte, sizeof(byte) );
 903 }
 904
 905 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 906            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 907            bool ReflectIn, bool ReflectRem >
 908 void
 909 BOOST_CRC_OPTIMAL_NAME::process_block
 910 (
 911     void const *  bytes_begin,
 912     void const *  bytes_end
 913 )
 914 {
 915     // Recompute the CRC for each byte passed
 916     for ( unsigned char const * p
 917      = static_cast<unsigned char const *>(bytes_begin) ; p < bytes_end ; ++p )
 918     {
 919         // Compare the new byte with the remainder's higher bits to
 920         // get the new bits, shift out the remainder's current higher
 921         // bits, and update the remainder with the polynominal division
 922         // of the new bits.
 923         unsigned char const  byte_index = helper_type::index( rem_, *p );
 924         rem_ = helper_type::shift( rem_ );
 925         rem_ ^= crc_table_type::table_[ byte_index ];
 926     }
 927 }
 928
 929 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 930            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 931            bool ReflectIn, bool ReflectRem >
 932 inline
 933 void
 934 BOOST_CRC_OPTIMAL_NAME::process_bytes
 935 (
 936     void const *   buffer,
 937     std::size_t  byte_count
 938 )
 939 {
 940     unsigned char const * const  b = static_cast<unsigned char const *>(
 941      buffer );
 942     process_block( b, b + byte_count );
 943 }
 944
 945 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 946            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 947            bool ReflectIn, bool ReflectRem >
 948 inline
 949 typename BOOST_CRC_OPTIMAL_NAME::value_type
 950 BOOST_CRC_OPTIMAL_NAME::checksum
 951 (
 952 ) const
 953 {
 954     return ( reflect_out_type::reflect(rem_) ^ get_final_xor_value() )
 955      & masking_type::sig_bits_fast;
 956 }
 957
 958 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 959            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 960            bool ReflectIn, bool ReflectRem >
 961 inline
 962 void
 963 BOOST_CRC_OPTIMAL_NAME::operator ()
 964 (
 965     unsigned char  byte
 966 )
 967 {
 968     process_byte( byte );
 969 }
 970
 971 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 972            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 973            bool ReflectIn, bool ReflectRem >
 974 inline
 975 typename BOOST_CRC_OPTIMAL_NAME::value_type
 976 BOOST_CRC_OPTIMAL_NAME::operator ()
 977 (
 978 ) const
 979 {
 980     return checksum();
 981 }
 982
 983
 984 //  CRC computation function definition  -------------------------------------//
 985
 986 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly,
 987            BOOST_CRC_PARM_TYPE InitRem, BOOST_CRC_PARM_TYPE FinalXor,
 988            bool ReflectIn, bool ReflectRem >
 989 inline
 990 typename uint_t<Bits>::fast
 991 crc
 992 (
 993     void const *  buffer,
 994     std::size_t   byte_count
 995     BOOST_CRC_DUMMY_INIT
 996 )
 997 {
 998     BOOST_CRC_OPTIMAL_NAME  computer;
 999     computer.process_bytes( buffer, byte_count );
1000     return computer.checksum();
1001 }
1002
1003
1004 //  Augmented-message CRC computation function definitions  ------------------//
1005
1006 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
1007 typename uint_t<Bits>::fast
1008 augmented_crc
1009 (
1010     void const *                 buffer,
1011     std::size_t                  byte_count,
1012     typename uint_t<Bits>::fast  initial_remainder
1013     BOOST_ACRC_DUMMY_INIT
1014 )
1015 {
1016     typedef unsigned char                                byte_type;
1017     typedef detail::mask_uint_t<Bits>                    masking_type;
1018     typedef detail::crc_table_t<Bits, TruncPoly, false>  crc_table_type;
1019
1020     typename masking_type::fast  rem = initial_remainder;
1021     byte_type const * const      b = static_cast<byte_type const *>( buffer );
1022     byte_type const * const      e = b + byte_count;
1023
1024     crc_table_type::init_table();
1025     for ( byte_type const * p = b ; p < e ; ++p )
1026     {
1027         // Use the current top byte as the table index to the next
1028         // "partial product."  Shift out that top byte, shifting in
1029         // the next augmented-message byte.  Complete the division.
1030         byte_type const  byte_index = rem >> ( Bits - CHAR_BIT );
1031         rem <<= CHAR_BIT;
1032         rem |= *p;
1033         rem ^= crc_table_type::table_[ byte_index ];
1034     }
1035
1036     return rem & masking_type::sig_bits_fast;
1037 }
1038
1039 template < std::size_t Bits, BOOST_CRC_PARM_TYPE TruncPoly >
1040 inline
1041 typename uint_t<Bits>::fast
1042 augmented_crc
1043 (
1044     void const *  buffer,
1045     std::size_t   byte_count
1046     BOOST_ACRC_DUMMY_INIT
1047 )
1048 {
1049    // The last function argument has its type specified so the other version of
1050    // augmented_crc will be called.  If the cast wasn't in place, and the
1051    // BOOST_ACRC_DUMMY_INIT added a third argument (for a workaround), the "0"
1052    // would match as that third argument, leading to infinite recursion.
1053    return augmented_crc<Bits, TruncPoly>( buffer, byte_count,
1054     static_cast<typename uint_t<Bits>::fast>(0) );
1055 }
1056
1057
1058 }  // namespace boost
1059
1060
1061 // Undo header-private macros
1062 #undef BOOST_CRC_OPTIMAL_NAME
1063 #undef BOOST_ACRC_DUMMY_INIT
1064 #undef BOOST_ACRC_DUMMY_PARM_TYPE
1065 #undef BOOST_CRC_DUMMY_INIT
1066 #undef BOOST_CRC_DUMMY_PARM_TYPE
1067 #undef BOOST_CRC_PARM_TYPE
1068
1069
1070 #endif  // BOOST_CRC_HPP