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