Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / 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