]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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( 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( (rft_in_ ? detail::reflector<CHAR_BIT>::reflect(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( *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( b, 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( &byte, 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( b, 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 |