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