ceph/src/boost/boost/crc.hpp

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