|
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 |