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