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