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