ACloudViewer  3.9.4
A Modern Library for 3D Data Processing
CRC.h
Go to the documentation of this file.
1 
38 /*
39  CRC++ can be configured by setting various #defines before #including this header file:
40 
41  #define crcpp_uint8 - Specifies the type used to store CRCs that have a width of 8
42  bits or less. This type is not used in CRC calculations. Defaults to ::std::uint8_t. #define crcpp_uint16 - Specifies
43  the type used to store CRCs that have a width between 9 and 16 bits (inclusive). This type is not used in CRC
44  calculations. Defaults to ::std::uint16_t. #define crcpp_uint32 - Specifies the type used
45  to store CRCs that have a width between 17 and 32 bits (inclusive). This type is not used in CRC calculations.
46  Defaults to ::std::uint32_t. #define crcpp_uint64 - Specifies the type used to store CRCs
47  that have a width between 33 and 64 bits (inclusive). This type is not used in CRC calculations. Defaults to
48  ::std::uint64_t. #define crcpp_size - This type is used for loop iteration and function
49  signatures only. Defaults to ::std::size_t. #define CRCPP_USE_NAMESPACE - Define to place all
50  CRC++ code within the ::CRCPP namespace. #define CRCPP_BRANCHLESS - Define to enable a
51  branchless CRC implementation. The branchless implementation uses a single integer multiplication in the bit-by-bit
52  calculation instead of a small conditional. The branchless implementation may be faster on processor architectures
53  which support single-instruction integer multiplication. #define CRCPP_USE_CPP11 - Define to
54  enables C++11 features (move semantics, constexpr, static_assert, etc.). #define
55  CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS - Define to include definitions for little-used CRCs.
56 */
57 
58 #ifndef CRCPP_CRC_H_
59 #define CRCPP_CRC_H_
60 
61 #include <climits> // Includes CHAR_BIT
62 #ifdef CRCPP_USE_CPP11
63 #include <cstddef> // Includes ::std::size_t
64 #include <cstdint> // Includes ::std::uint8_t, ::std::uint16_t, ::std::uint32_t, ::std::uint64_t
65 #else
66 #include <stddef.h> // Includes size_t
67 #include <stdint.h> // Includes uint8_t, uint16_t, uint32_t, uint64_t
68 #endif
69 #include <limits> // Includes ::std::numeric_limits
70 #include <utility> // Includes ::std::move
71 
72 #ifndef crcpp_uint8
73 #ifdef CRCPP_USE_CPP11
75 #define crcpp_uint8 ::std::uint8_t
76 #else
78 #define crcpp_uint8 uint8_t
79 #endif
80 #endif
81 
82 #ifndef crcpp_uint16
83 #ifdef CRCPP_USE_CPP11
85 #define crcpp_uint16 ::std::uint16_t
86 #else
88 #define crcpp_uint16 uint16_t
89 #endif
90 #endif
91 
92 #ifndef crcpp_uint32
93 #ifdef CRCPP_USE_CPP11
95 #define crcpp_uint32 ::std::uint32_t
96 #else
98 #define crcpp_uint32 uint32_t
99 #endif
100 #endif
101 
102 #ifndef crcpp_uint64
103 #ifdef CRCPP_USE_CPP11
105 #define crcpp_uint64 ::std::uint64_t
106 #else
108 #define crcpp_uint64 uint64_t
109 #endif
110 #endif
111 
112 #ifndef crcpp_size
113 #ifdef CRCPP_USE_CPP11
115 #define crcpp_size ::std::size_t
116 #else
118 #define crcpp_size size_t
119 #endif
120 #endif
121 
122 #ifdef CRCPP_USE_CPP11
124 #define crcpp_constexpr constexpr
125 #else
127 #define crcpp_constexpr const
128 #endif
129 
130 #ifdef CRCPP_USE_NAMESPACE
131 namespace CRCPP
132 {
133 #endif
134 
142  class CRC
143  {
144  public:
145  // Forward declaration
146  template <typename CRCType, crcpp_uint16 CRCWidth> struct Table;
147 
151  template <typename CRCType, crcpp_uint16 CRCWidth> struct Parameters
152  {
153  CRCType polynomial;
154  CRCType initialValue;
155  CRCType finalXOR;
156  bool reflectInput;
157  bool reflectOutput;
158 
159  Table<CRCType, CRCWidth> MakeTable() const;
160  };
161 
166  template <typename CRCType, crcpp_uint16 CRCWidth> struct Table
167  {
168  // Constructors are intentionally NOT marked explicit.
169  Table( const Parameters<CRCType, CRCWidth> &parameters );
170 
171 #ifdef CRCPP_USE_CPP11
172  Table( Parameters<CRCType, CRCWidth> &&parameters );
173 #endif
174 
175  const Parameters<CRCType, CRCWidth> &GetParameters() const;
176 
177  const CRCType *GetTable() const;
178 
179  CRCType operator[]( unsigned char index ) const;
180 
181  private:
182  void InitTable();
183 
184  Parameters<CRCType, CRCWidth> parameters;
185  CRCType table[1 << CHAR_BIT];
186  };
187 
188  // The number of bits in CRCType must be at least as large as CRCWidth.
189  // CRCType must be an unsigned integer type or a custom type with operator overloads.
190  template <typename CRCType, crcpp_uint16 CRCWidth>
191  static CRCType Calculate( const void *data, crcpp_size size, const Parameters<CRCType, CRCWidth> &parameters );
192 
193  template <typename CRCType, crcpp_uint16 CRCWidth>
194  static CRCType Calculate( const void *data, crcpp_size size, const Parameters<CRCType, CRCWidth> &parameters,
195  CRCType crc );
196 
197  template <typename CRCType, crcpp_uint16 CRCWidth>
198  static CRCType Calculate( const void *data, crcpp_size size, const Table<CRCType, CRCWidth> &lookupTable );
199 
200  template <typename CRCType, crcpp_uint16 CRCWidth>
201  static CRCType Calculate( const void *data, crcpp_size size, const Table<CRCType, CRCWidth> &lookupTable,
202  CRCType crc );
203 
204  // Common CRCs up to 64 bits.
205  // Note: Check values are the computed CRCs when given an ASCII input of "123456789" (without null terminator)
206 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
207  static const Parameters<crcpp_uint8, 4> &CRC_4_ITU();
208  static const Parameters<crcpp_uint8, 5> &CRC_5_EPC();
209  static const Parameters<crcpp_uint8, 5> &CRC_5_ITU();
210  static const Parameters<crcpp_uint8, 5> &CRC_5_USB();
211  static const Parameters<crcpp_uint8, 6> &CRC_6_CDMA2000A();
212  static const Parameters<crcpp_uint8, 6> &CRC_6_CDMA2000B();
213  static const Parameters<crcpp_uint8, 6> &CRC_6_ITU();
214  static const Parameters<crcpp_uint8, 7> &CRC_7();
215 #endif
216  static const Parameters<crcpp_uint8, 8> &CRC_8();
217 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
218  static const Parameters<crcpp_uint8, 8> &CRC_8_EBU();
219  static const Parameters<crcpp_uint8, 8> &CRC_8_MAXIM();
220  static const Parameters<crcpp_uint8, 8> &CRC_8_WCDMA();
221  static const Parameters<crcpp_uint16, 10> &CRC_10();
222  static const Parameters<crcpp_uint16, 10> &CRC_10_CDMA2000();
223  static const Parameters<crcpp_uint16, 11> &CRC_11();
224  static const Parameters<crcpp_uint16, 12> &CRC_12_CDMA2000();
225  static const Parameters<crcpp_uint16, 12> &CRC_12_DECT();
226  static const Parameters<crcpp_uint16, 12> &CRC_12_UMTS();
227  static const Parameters<crcpp_uint16, 13> &CRC_13_BBC();
228  static const Parameters<crcpp_uint16, 15> &CRC_15();
229  static const Parameters<crcpp_uint16, 15> &CRC_15_MPT1327();
230 #endif
231  static const Parameters<crcpp_uint16, 16> &CRC_16_ARC();
232  static const Parameters<crcpp_uint16, 16> &CRC_16_BUYPASS();
233  static const Parameters<crcpp_uint16, 16> &CRC_16_CCITTFALSE();
234 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
235  static const Parameters<crcpp_uint16, 16> &CRC_16_CDMA2000();
236  static const Parameters<crcpp_uint16, 16> &CRC_16_DECTR();
237  static const Parameters<crcpp_uint16, 16> &CRC_16_DECTX();
238  static const Parameters<crcpp_uint16, 16> &CRC_16_DNP();
239 #endif
240  static const Parameters<crcpp_uint16, 16> &CRC_16_GENIBUS();
241  static const Parameters<crcpp_uint16, 16> &CRC_16_KERMIT();
242 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
243  static const Parameters<crcpp_uint16, 16> &CRC_16_MAXIM();
244  static const Parameters<crcpp_uint16, 16> &CRC_16_MODBUS();
245  static const Parameters<crcpp_uint16, 16> &CRC_16_T10DIF();
246  static const Parameters<crcpp_uint16, 16> &CRC_16_USB();
247 #endif
248  static const Parameters<crcpp_uint16, 16> &CRC_16_X25();
249  static const Parameters<crcpp_uint16, 16> &CRC_16_XMODEM();
250 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
251  static const Parameters<crcpp_uint32, 17> &CRC_17_CAN();
252  static const Parameters<crcpp_uint32, 21> &CRC_21_CAN();
253  static const Parameters<crcpp_uint32, 24> &CRC_24();
254  static const Parameters<crcpp_uint32, 24> &CRC_24_FLEXRAYA();
255  static const Parameters<crcpp_uint32, 24> &CRC_24_FLEXRAYB();
256  static const Parameters<crcpp_uint32, 30> &CRC_30();
257 #endif
258  static const Parameters<crcpp_uint32, 32> &CRC_32();
259  static const Parameters<crcpp_uint32, 32> &CRC_32_BZIP2();
260 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
261  static const Parameters<crcpp_uint32, 32> &CRC_32_C();
262 #endif
263  static const Parameters<crcpp_uint32, 32> &CRC_32_MPEG2();
264  static const Parameters<crcpp_uint32, 32> &CRC_32_POSIX();
265 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
266  static const Parameters<crcpp_uint32, 32> &CRC_32_Q();
267  static const Parameters<crcpp_uint64, 40> &CRC_40_GSM();
268  static const Parameters<crcpp_uint64, 64> &CRC_64();
269 #endif
270 
271 #ifdef CRCPP_USE_CPP11
272  CRC() = delete;
273  CRC( const CRC &other ) = delete;
274  CRC &operator=( const CRC &other ) = delete;
275  CRC( CRC &&other ) = delete;
276  CRC &operator=( CRC &&other ) = delete;
277 #endif
278 
279  private:
280 #ifndef CRCPP_USE_CPP11
281  CRC();
282  CRC( const CRC &other );
283  CRC &operator=( const CRC &other );
284 #endif
285 
286  template <typename IntegerType> static IntegerType Reflect( IntegerType value, crcpp_uint16 numBits );
287 
288  template <typename CRCType, crcpp_uint16 CRCWidth>
289  static CRCType Finalize( CRCType remainder, CRCType finalXOR, bool reflectOutput );
290 
291  template <typename CRCType, crcpp_uint16 CRCWidth>
292  static CRCType UndoFinalize( CRCType remainder, CRCType finalXOR, bool reflectOutput );
293 
294  template <typename CRCType, crcpp_uint16 CRCWidth>
295  static CRCType CalculateRemainder( const void *data, crcpp_size size,
296  const Parameters<CRCType, CRCWidth> &parameters, CRCType remainder );
297 
298  template <typename CRCType, crcpp_uint16 CRCWidth>
299  static CRCType CalculateRemainder( const void *data, crcpp_size size, const Table<CRCType, CRCWidth> &lookupTable,
300  CRCType remainder );
301 
302  template <typename IntegerType> static crcpp_constexpr IntegerType BoundedConstexprValue( IntegerType x );
303  };
304 
313  template <typename CRCType, crcpp_uint16 CRCWidth>
314  inline CRC::Table<CRCType, CRCWidth> CRC::Parameters<CRCType, CRCWidth>::MakeTable() const
315  {
316  // This should take advantage of RVO and optimize out the copy.
317  return CRC::Table<CRCType, CRCWidth>( *this );
318  }
319 
326  template <typename CRCType, crcpp_uint16 CRCWidth>
327  inline CRC::Table<CRCType, CRCWidth>::Table( const Parameters<CRCType, CRCWidth> &parameters ) :
328  parameters( parameters )
329  {
330  InitTable();
331  }
332 
333 #ifdef CRCPP_USE_CPP11
340  template <typename CRCType, crcpp_uint16 CRCWidth>
341  inline CRC::Table<CRCType, CRCWidth>::Table( Parameters<CRCType, CRCWidth> &&parameters ) :
342  parameters( ::std::move( parameters ) )
343  {
344  InitTable();
345  }
346 #endif
347 
354  template <typename CRCType, crcpp_uint16 CRCWidth>
355  inline const CRC::Parameters<CRCType, CRCWidth> &CRC::Table<CRCType, CRCWidth>::GetParameters() const
356  {
357  return parameters;
358  }
359 
366  template <typename CRCType, crcpp_uint16 CRCWidth>
367  inline const CRCType *CRC::Table<CRCType, CRCWidth>::GetTable() const
368  {
369  return table;
370  }
371 
379  template <typename CRCType, crcpp_uint16 CRCWidth>
380  inline CRCType CRC::Table<CRCType, CRCWidth>::operator[]( unsigned char index ) const
381  {
382  return table[index];
383  }
384 
390  template <typename CRCType, crcpp_uint16 CRCWidth> inline void CRC::Table<CRCType, CRCWidth>::InitTable()
391  {
392  // For masking off the bits for the CRC (in the event that the number of bits in CRCType is larger than CRCWidth)
393  static crcpp_constexpr CRCType BIT_MASK( ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) |
394  ( ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) - CRCType( 1 ) ) );
395 
396  static crcpp_constexpr CRCType SHIFT( CRC::BoundedConstexprValue( CHAR_BIT - CRCWidth ) );
397 
398  CRCType crc;
399  unsigned char byte = 0;
400 
401  // Loop over each dividend (each possible number storable in an unsigned char)
402  do
403  {
404  crc = CRC::CalculateRemainder<CRCType, CRCWidth>( &byte, sizeof( byte ), parameters, CRCType( 0 ) );
405 
406  // This mask might not be necessary; all unit tests pass with this line commented out,
407  // but that might just be a coincidence based on the CRC parameters used for testing.
408  // In any case, this is harmless to leave in and only adds a single machine instruction per loop iteration.
409  crc &= BIT_MASK;
410 
411  if ( !parameters.reflectInput && CRCWidth < CHAR_BIT )
412  {
413  // Undo the special operation at the end of the CalculateRemainder()
414  // function for non-reflected CRCs < CHAR_BIT.
415  crc <<= SHIFT;
416  }
417 
418  table[byte] = crc;
419  } while ( ++byte );
420  }
421 
431  template <typename CRCType, crcpp_uint16 CRCWidth>
432  inline CRCType CRC::Calculate( const void *data, crcpp_size size, const Parameters<CRCType, CRCWidth> &parameters )
433  {
434  CRCType remainder = CalculateRemainder( data, size, parameters, parameters.initialValue );
435 
436  // No need to mask the remainder here; the mask will be applied in the Finalize() function.
437 
438  return Finalize<CRCType, CRCWidth>( remainder, parameters.finalXOR,
439  parameters.reflectInput != parameters.reflectOutput );
440  }
452  template <typename CRCType, crcpp_uint16 CRCWidth>
453  inline CRCType CRC::Calculate( const void *data, crcpp_size size, const Parameters<CRCType, CRCWidth> &parameters,
454  CRCType crc )
455  {
456  CRCType remainder = UndoFinalize<CRCType, CRCWidth>( crc, parameters.finalXOR,
457  parameters.reflectInput != parameters.reflectOutput );
458 
459  remainder = CalculateRemainder( data, size, parameters, remainder );
460 
461  // No need to mask the remainder here; the mask will be applied in the Finalize() function.
462 
463  return Finalize<CRCType, CRCWidth>( remainder, parameters.finalXOR,
464  parameters.reflectInput != parameters.reflectOutput );
465  }
466 
476  template <typename CRCType, crcpp_uint16 CRCWidth>
477  inline CRCType CRC::Calculate( const void *data, crcpp_size size, const Table<CRCType, CRCWidth> &lookupTable )
478  {
479  const Parameters<CRCType, CRCWidth> &parameters = lookupTable.GetParameters();
480 
481  CRCType remainder = CalculateRemainder( data, size, lookupTable, parameters.initialValue );
482 
483  // No need to mask the remainder here; the mask will be applied in the Finalize() function.
484 
485  return Finalize<CRCType, CRCWidth>( remainder, parameters.finalXOR,
486  parameters.reflectInput != parameters.reflectOutput );
487  }
488 
500  template <typename CRCType, crcpp_uint16 CRCWidth>
501  inline CRCType CRC::Calculate( const void *data, crcpp_size size, const Table<CRCType, CRCWidth> &lookupTable,
502  CRCType crc )
503  {
504  const Parameters<CRCType, CRCWidth> &parameters = lookupTable.GetParameters();
505 
506  CRCType remainder = UndoFinalize<CRCType, CRCWidth>( crc, parameters.finalXOR,
507  parameters.reflectInput != parameters.reflectOutput );
508 
509  remainder = CalculateRemainder( data, size, lookupTable, remainder );
510 
511  // No need to mask the remainder here; the mask will be applied in the Finalize() function.
512 
513  return Finalize<CRCType, CRCWidth>( remainder, parameters.finalXOR,
514  parameters.reflectInput != parameters.reflectOutput );
515  }
516 
524  template <typename IntegerType> inline IntegerType CRC::Reflect( IntegerType value, crcpp_uint16 numBits )
525  {
526  IntegerType reversedValue( 0 );
527 
528  for ( crcpp_uint16 i = 0; i < numBits; ++i )
529  {
530  reversedValue = ( reversedValue << 1 ) | ( value & 1 );
531  value >>= 1;
532  }
533 
534  return reversedValue;
535  }
536 
546  template <typename CRCType, crcpp_uint16 CRCWidth>
547  inline CRCType CRC::Finalize( CRCType remainder, CRCType finalXOR, bool reflectOutput )
548  {
549  // For masking off the bits for the CRC (in the event that the number of bits in CRCType is larger than CRCWidth)
550  static crcpp_constexpr CRCType BIT_MASK = ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) |
551  ( ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) - CRCType( 1 ) );
552 
553  if ( reflectOutput )
554  {
555  remainder = Reflect( remainder, CRCWidth );
556  }
557 
558  return ( remainder ^ finalXOR ) & BIT_MASK;
559  }
560 
579  template <typename CRCType, crcpp_uint16 CRCWidth>
580  inline CRCType CRC::UndoFinalize( CRCType crc, CRCType finalXOR, bool reflectOutput )
581  {
582  // For masking off the bits for the CRC (in the event that the number of bits in CRCType is larger than CRCWidth)
583  static crcpp_constexpr CRCType BIT_MASK = ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) |
584  ( ( CRCType( 1 ) << ( CRCWidth - CRCType( 1 ) ) ) - CRCType( 1 ) );
585 
586  crc = ( crc & BIT_MASK ) ^ finalXOR;
587 
588  if ( reflectOutput )
589  {
590  crc = Reflect( crc, CRCWidth );
591  }
592 
593  return crc;
594  }
595 
607  template <typename CRCType, crcpp_uint16 CRCWidth>
608  inline CRCType CRC::CalculateRemainder( const void *data, crcpp_size size,
609  const Parameters<CRCType, CRCWidth> &parameters, CRCType remainder )
610  {
611 #ifdef CRCPP_USE_CPP11
612  // This static_assert is put here because this function will always be compiled in no matter what
613  // the template parameters are and whether or not a table lookup or bit-by-bit algorithm is used.
614  static_assert( ::std::numeric_limits<CRCType>::digits >= CRCWidth,
615  "CRCType is too small to contain a CRC of width CRCWidth." );
616 #else
617  // Catching this compile-time error is very important. Sadly, the compiler error will be very cryptic, but it's
618  // better than nothing.
619  enum
620  {
621  static_assert_failed_CRCType_is_too_small_to_contain_a_CRC_of_width_CRCWidth =
622  1 / ( ::std::numeric_limits<CRCType>::digits >= CRCWidth ? 1 : 0 )
623  };
624 #endif
625 
626  const unsigned char *current = reinterpret_cast<const unsigned char *>( data );
627 
628  // Slightly different implementations based on the parameters. The current implementations try to eliminate as
629  // much computation from the inner loop (looping over each bit) as possible.
630  if ( parameters.reflectInput )
631  {
632  CRCType polynomial = CRC::Reflect( parameters.polynomial, CRCWidth );
633  while ( size-- )
634  {
635  remainder ^= *current++;
636 
637  // An optimizing compiler might choose to unroll this loop.
638  for ( crcpp_size i = 0; i < CHAR_BIT; ++i )
639  {
640 #ifdef CRCPP_BRANCHLESS
641  // Clever way to avoid a branch at the expense of a multiplication. This code is equivalent to the
642  // following: if (remainder & 1)
643  // remainder = (remainder >> 1) ^ polynomial;
644  // else
645  // remainder >>= 1;
646  remainder = ( remainder >> 1 ) ^ ( ( remainder & 1 ) * polynomial );
647 #else
648  remainder = ( remainder & 1 ) ? ( ( remainder >> 1 ) ^ polynomial ) : ( remainder >> 1 );
649 #endif
650  }
651  }
652  }
653  else if ( CRCWidth >= CHAR_BIT )
654  {
655  static crcpp_constexpr CRCType CRC_WIDTH_MINUS_ONE( CRCWidth - CRCType( 1 ) );
656 #ifndef CRCPP_BRANCHLESS
657  static crcpp_constexpr CRCType CRC_HIGHEST_BIT_MASK( CRCType( 1 ) << CRC_WIDTH_MINUS_ONE );
658 #endif
659  static crcpp_constexpr CRCType SHIFT( BoundedConstexprValue( CRCWidth - CHAR_BIT ) );
660 
661  while ( size-- )
662  {
663  remainder ^= ( static_cast<CRCType>( *current++ ) << SHIFT );
664 
665  // An optimizing compiler might choose to unroll this loop.
666  for ( crcpp_size i = 0; i < CHAR_BIT; ++i )
667  {
668 #ifdef CRCPP_BRANCHLESS
669  // Clever way to avoid a branch at the expense of a multiplication. This code is equivalent to the
670  // following: if (remainder & CRC_HIGHEST_BIT_MASK)
671  // remainder = (remainder << 1) ^ parameters.polynomial;
672  // else
673  // remainder <<= 1;
674  remainder =
675  ( remainder << 1 ) ^ ( ( ( remainder >> CRC_WIDTH_MINUS_ONE ) & 1 ) * parameters.polynomial );
676 #else
677  remainder = ( remainder & CRC_HIGHEST_BIT_MASK ) ? ( ( remainder << 1 ) ^ parameters.polynomial )
678  : ( remainder << 1 );
679 #endif
680  }
681  }
682  }
683  else
684  {
685  static crcpp_constexpr CRCType CHAR_BIT_MINUS_ONE( CHAR_BIT - 1 );
686 #ifndef CRCPP_BRANCHLESS
687  static crcpp_constexpr CRCType CHAR_BIT_HIGHEST_BIT_MASK( CRCType( 1 ) << CHAR_BIT_MINUS_ONE );
688 #endif
689  static crcpp_constexpr CRCType SHIFT( BoundedConstexprValue( CHAR_BIT - CRCWidth ) );
690 
691  CRCType polynomial = parameters.polynomial << SHIFT;
692  remainder <<= SHIFT;
693 
694  while ( size-- )
695  {
696  remainder ^= *current++;
697 
698  // An optimizing compiler might choose to unroll this loop.
699  for ( crcpp_size i = 0; i < CHAR_BIT; ++i )
700  {
701 #ifdef CRCPP_BRANCHLESS
702  // Clever way to avoid a branch at the expense of a multiplication. This code is equivalent to the
703  // following: if (remainder & CHAR_BIT_HIGHEST_BIT_MASK)
704  // remainder = (remainder << 1) ^ polynomial;
705  // else
706  // remainder <<= 1;
707  remainder = ( remainder << 1 ) ^ ( ( ( remainder >> CHAR_BIT_MINUS_ONE ) & 1 ) * polynomial );
708 #else
709  remainder =
710  ( remainder & CHAR_BIT_HIGHEST_BIT_MASK ) ? ( ( remainder << 1 ) ^ polynomial ) : ( remainder << 1 );
711 #endif
712  }
713  }
714 
715  remainder >>= SHIFT;
716  }
717 
718  return remainder;
719  }
720 
732  template <typename CRCType, crcpp_uint16 CRCWidth>
733  inline CRCType CRC::CalculateRemainder( const void *data, crcpp_size size,
734  const Table<CRCType, CRCWidth> &lookupTable, CRCType remainder )
735  {
736  const unsigned char *current = reinterpret_cast<const unsigned char *>( data );
737 
738  if ( lookupTable.GetParameters().reflectInput )
739  {
740  while ( size-- )
741  {
742 #if defined( WIN32 ) || defined( _WIN32 ) || defined( WINCE )
743  // Disable warning about data loss when doing (remainder >> CHAR_BIT) when
744  // remainder is one byte long. The algorithm is still correct in this case,
745  // though it's possible that one additional machine instruction will be executed.
746 #pragma warning( push )
747 #pragma warning( disable : 4333 )
748 #endif
749  remainder = ( remainder >> CHAR_BIT ) ^ lookupTable[static_cast<unsigned char>( remainder ^ *current++ )];
750 #if defined( WIN32 ) || defined( _WIN32 ) || defined( WINCE )
751 #pragma warning( pop )
752 #endif
753  }
754  }
755  else if ( CRCWidth >= CHAR_BIT )
756  {
757  static crcpp_constexpr CRCType SHIFT( BoundedConstexprValue( CRCWidth - CHAR_BIT ) );
758 
759  while ( size-- )
760  {
761  remainder = ( remainder << CHAR_BIT ) ^
762  lookupTable[static_cast<unsigned char>( ( remainder >> SHIFT ) ^ *current++ )];
763  }
764  }
765  else
766  {
767  static crcpp_constexpr CRCType SHIFT( BoundedConstexprValue( CHAR_BIT - CRCWidth ) );
768 
769  remainder <<= SHIFT;
770 
771  while ( size-- )
772  {
773  // Note: no need to mask here since remainder is guaranteed to fit in a single byte.
774  remainder = lookupTable[static_cast<unsigned char>( remainder ^ *current++ )];
775  }
776 
777  remainder >>= SHIFT;
778  }
779 
780  return remainder;
781  }
782 
793  template <typename IntegerType> inline crcpp_constexpr IntegerType CRC::BoundedConstexprValue( IntegerType x )
794  {
795  return ( x < IntegerType( 0 ) ) ? IntegerType( 0 ) : x;
796  }
797 
798 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
811  inline const CRC::Parameters<crcpp_uint8, 4> &CRC::CRC_4_ITU()
812  {
813  static const Parameters<crcpp_uint8, 4> parameters = { 0x3, 0x0, 0x0, true, true };
814  return parameters;
815  }
816 
829  inline const CRC::Parameters<crcpp_uint8, 5> &CRC::CRC_5_EPC()
830  {
831  static const Parameters<crcpp_uint8, 5> parameters = { 0x09, 0x09, 0x00, false, false };
832  return parameters;
833  }
834 
847  inline const CRC::Parameters<crcpp_uint8, 5> &CRC::CRC_5_ITU()
848  {
849  static const Parameters<crcpp_uint8, 5> parameters = { 0x15, 0x00, 0x00, true, true };
850  return parameters;
851  }
852 
865  inline const CRC::Parameters<crcpp_uint8, 5> &CRC::CRC_5_USB()
866  {
867  static const Parameters<crcpp_uint8, 5> parameters = { 0x05, 0x1F, 0x1F, true, true };
868  return parameters;
869  }
870 
883  inline const CRC::Parameters<crcpp_uint8, 6> &CRC::CRC_6_CDMA2000A()
884  {
885  static const Parameters<crcpp_uint8, 6> parameters = { 0x27, 0x3F, 0x00, false, false };
886  return parameters;
887  }
888 
901  inline const CRC::Parameters<crcpp_uint8, 6> &CRC::CRC_6_CDMA2000B()
902  {
903  static const Parameters<crcpp_uint8, 6> parameters = { 0x07, 0x3F, 0x00, false, false };
904  return parameters;
905  }
906 
919  inline const CRC::Parameters<crcpp_uint8, 6> &CRC::CRC_6_ITU()
920  {
921  static const Parameters<crcpp_uint8, 6> parameters = { 0x03, 0x00, 0x00, true, true };
922  return parameters;
923  }
924 
937  inline const CRC::Parameters<crcpp_uint8, 7> &CRC::CRC_7()
938  {
939  static const Parameters<crcpp_uint8, 7> parameters = { 0x09, 0x00, 0x00, false, false };
940  return parameters;
941  }
942 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
943 
956  inline const CRC::Parameters<crcpp_uint8, 8> &CRC::CRC_8()
957  {
958  static const Parameters<crcpp_uint8, 8> parameters = { 0x07, 0x00, 0x00, false, false };
959  return parameters;
960  }
961 
962 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
975  inline const CRC::Parameters<crcpp_uint8, 8> &CRC::CRC_8_EBU()
976  {
977  static const Parameters<crcpp_uint8, 8> parameters = { 0x1D, 0xFF, 0x00, true, true };
978  return parameters;
979  }
980 
993  inline const CRC::Parameters<crcpp_uint8, 8> &CRC::CRC_8_MAXIM()
994  {
995  static const Parameters<crcpp_uint8, 8> parameters = { 0x31, 0x00, 0x00, true, true };
996  return parameters;
997  }
998 
1011  inline const CRC::Parameters<crcpp_uint8, 8> &CRC::CRC_8_WCDMA()
1012  {
1013  static const Parameters<crcpp_uint8, 8> parameters = { 0x9B, 0x00, 0x00, true, true };
1014  return parameters;
1015  }
1016 
1029  inline const CRC::Parameters<crcpp_uint16, 10> &CRC::CRC_10()
1030  {
1031  static const Parameters<crcpp_uint16, 10> parameters = { 0x233, 0x000, 0x000, false, false };
1032  return parameters;
1033  }
1034 
1047  inline const CRC::Parameters<crcpp_uint16, 10> &CRC::CRC_10_CDMA2000()
1048  {
1049  static const Parameters<crcpp_uint16, 10> parameters = { 0x3D9, 0x3FF, 0x000, false, false };
1050  return parameters;
1051  }
1052 
1065  inline const CRC::Parameters<crcpp_uint16, 11> &CRC::CRC_11()
1066  {
1067  static const Parameters<crcpp_uint16, 11> parameters = { 0x385, 0x01A, 0x000, false, false };
1068  return parameters;
1069  }
1070 
1083  inline const CRC::Parameters<crcpp_uint16, 12> &CRC::CRC_12_CDMA2000()
1084  {
1085  static const Parameters<crcpp_uint16, 12> parameters = { 0xF13, 0xFFF, 0x000, false, false };
1086  return parameters;
1087  }
1088 
1101  inline const CRC::Parameters<crcpp_uint16, 12> &CRC::CRC_12_DECT()
1102  {
1103  static const Parameters<crcpp_uint16, 12> parameters = { 0x80F, 0x000, 0x000, false, false };
1104  return parameters;
1105  }
1106 
1119  inline const CRC::Parameters<crcpp_uint16, 12> &CRC::CRC_12_UMTS()
1120  {
1121  static const Parameters<crcpp_uint16, 12> parameters = { 0x80F, 0x000, 0x000, false, true };
1122  return parameters;
1123  }
1124 
1137  inline const CRC::Parameters<crcpp_uint16, 13> &CRC::CRC_13_BBC()
1138  {
1139  static const Parameters<crcpp_uint16, 13> parameters = { 0x1CF5, 0x0000, 0x0000, false, false };
1140  return parameters;
1141  }
1142 
1155  inline const CRC::Parameters<crcpp_uint16, 15> &CRC::CRC_15()
1156  {
1157  static const Parameters<crcpp_uint16, 15> parameters = { 0x4599, 0x0000, 0x0000, false, false };
1158  return parameters;
1159  }
1160 
1173  inline const CRC::Parameters<crcpp_uint16, 15> &CRC::CRC_15_MPT1327()
1174  {
1175  static const Parameters<crcpp_uint16, 15> parameters = { 0x6815, 0x0000, 0x0001, false, false };
1176  return parameters;
1177  }
1178 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1179 
1192  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_ARC()
1193  {
1194  static const Parameters<crcpp_uint16, 16> parameters = { 0x8005, 0x0000, 0x0000, true, true };
1195  return parameters;
1196  }
1197 
1210  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_BUYPASS()
1211  {
1212  static const Parameters<crcpp_uint16, 16> parameters = { 0x8005, 0x0000, 0x0000, false, false };
1213  return parameters;
1214  }
1215 
1228  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_CCITTFALSE()
1229  {
1230  static const Parameters<crcpp_uint16, 16> parameters = { 0x1021, 0xFFFF, 0x0000, false, false };
1231  return parameters;
1232  }
1233 
1234 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1247  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_CDMA2000()
1248  {
1249  static const Parameters<crcpp_uint16, 16> parameters = { 0xC867, 0xFFFF, 0x0000, false, false };
1250  return parameters;
1251  }
1252 
1265  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_DECTR()
1266  {
1267  static const Parameters<crcpp_uint16, 16> parameters = { 0x0589, 0x0000, 0x0001, false, false };
1268  return parameters;
1269  }
1270 
1283  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_DECTX()
1284  {
1285  static const Parameters<crcpp_uint16, 16> parameters = { 0x0589, 0x0000, 0x0000, false, false };
1286  return parameters;
1287  }
1288 
1301  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_DNP()
1302  {
1303  static const Parameters<crcpp_uint16, 16> parameters = { 0x3D65, 0x0000, 0xFFFF, true, true };
1304  return parameters;
1305  }
1306 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1307 
1320  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_GENIBUS()
1321  {
1322  static const Parameters<crcpp_uint16, 16> parameters = { 0x1021, 0xFFFF, 0xFFFF, false, false };
1323  return parameters;
1324  }
1325 
1338  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_KERMIT()
1339  {
1340  static const Parameters<crcpp_uint16, 16> parameters = { 0x1021, 0x0000, 0x0000, true, true };
1341  return parameters;
1342  }
1343 
1344 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1357  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_MAXIM()
1358  {
1359  static const Parameters<crcpp_uint16, 16> parameters = { 0x8005, 0x0000, 0xFFFF, true, true };
1360  return parameters;
1361  }
1362 
1375  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_MODBUS()
1376  {
1377  static const Parameters<crcpp_uint16, 16> parameters = { 0x8005, 0xFFFF, 0x0000, true, true };
1378  return parameters;
1379  }
1380 
1393  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_T10DIF()
1394  {
1395  static const Parameters<crcpp_uint16, 16> parameters = { 0x8BB7, 0x0000, 0x0000, false, false };
1396  return parameters;
1397  }
1398 
1411  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_USB()
1412  {
1413  static const Parameters<crcpp_uint16, 16> parameters = { 0x8005, 0xFFFF, 0xFFFF, true, true };
1414  return parameters;
1415  }
1416 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1417 
1430  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_X25()
1431  {
1432  static const Parameters<crcpp_uint16, 16> parameters = { 0x1021, 0xFFFF, 0xFFFF, true, true };
1433  return parameters;
1434  }
1435 
1448  inline const CRC::Parameters<crcpp_uint16, 16> &CRC::CRC_16_XMODEM()
1449  {
1450  static const Parameters<crcpp_uint16, 16> parameters = { 0x1021, 0x0000, 0x0000, false, false };
1451  return parameters;
1452  }
1453 
1454 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1467  inline const CRC::Parameters<crcpp_uint32, 17> &CRC::CRC_17_CAN()
1468  {
1469  static const Parameters<crcpp_uint32, 17> parameters = { 0x1685B, 0x00000, 0x00000, false, false };
1470  return parameters;
1471  }
1472 
1485  inline const CRC::Parameters<crcpp_uint32, 21> &CRC::CRC_21_CAN()
1486  {
1487  static const Parameters<crcpp_uint32, 21> parameters = { 0x102899, 0x000000, 0x000000, false, false };
1488  return parameters;
1489  }
1490 
1503  inline const CRC::Parameters<crcpp_uint32, 24> &CRC::CRC_24()
1504  {
1505  static const Parameters<crcpp_uint32, 24> parameters = { 0x864CFB, 0xB704CE, 0x000000, false, false };
1506  return parameters;
1507  }
1508 
1521  inline const CRC::Parameters<crcpp_uint32, 24> &CRC::CRC_24_FLEXRAYA()
1522  {
1523  static const Parameters<crcpp_uint32, 24> parameters = { 0x5D6DCB, 0xFEDCBA, 0x000000, false, false };
1524  return parameters;
1525  }
1526 
1539  inline const CRC::Parameters<crcpp_uint32, 24> &CRC::CRC_24_FLEXRAYB()
1540  {
1541  static const Parameters<crcpp_uint32, 24> parameters = { 0x5D6DCB, 0xABCDEF, 0x000000, false, false };
1542  return parameters;
1543  }
1544 
1557  inline const CRC::Parameters<crcpp_uint32, 30> &CRC::CRC_30()
1558  {
1559  static const Parameters<crcpp_uint32, 30> parameters = { 0x2030B9C7, 0x3FFFFFFF, 0x00000000, false, false };
1560  return parameters;
1561  }
1562 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1563 
1576  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32()
1577  {
1578  static const Parameters<crcpp_uint32, 32> parameters = { 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, true, true };
1579  return parameters;
1580  }
1581 
1594  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32_BZIP2()
1595  {
1596  static const Parameters<crcpp_uint32, 32> parameters = { 0x04C11DB7, 0xFFFFFFFF, 0xFFFFFFFF, false, false };
1597  return parameters;
1598  }
1599 
1600 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1613  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32_C()
1614  {
1615  static const Parameters<crcpp_uint32, 32> parameters = { 0x1EDC6F41, 0xFFFFFFFF, 0xFFFFFFFF, true, true };
1616  return parameters;
1617  }
1618 #endif
1619 
1632  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32_MPEG2()
1633  {
1634  static const Parameters<crcpp_uint32, 32> parameters = { 0x04C11DB7, 0xFFFFFFFF, 0x00000000, false, false };
1635  return parameters;
1636  }
1637 
1650  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32_POSIX()
1651  {
1652  static const Parameters<crcpp_uint32, 32> parameters = { 0x04C11DB7, 0x00000000, 0xFFFFFFFF, false, false };
1653  return parameters;
1654  }
1655 
1656 #ifdef CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1669  inline const CRC::Parameters<crcpp_uint32, 32> &CRC::CRC_32_Q()
1670  {
1671  static const Parameters<crcpp_uint32, 32> parameters = { 0x814141AB, 0x00000000, 0x00000000, false, false };
1672  return parameters;
1673  }
1674 
1687  inline const CRC::Parameters<crcpp_uint64, 40> &CRC::CRC_40_GSM()
1688  {
1689  static const Parameters<crcpp_uint64, 40> parameters = { 0x0004820009, 0x0000000000, 0xFFFFFFFFFF, false, false };
1690  return parameters;
1691  }
1692 
1705  inline const CRC::Parameters<crcpp_uint64, 64> &CRC::CRC_64()
1706  {
1707  static const Parameters<crcpp_uint64, 64> parameters = { 0x42F0E1EBA9EA3693, 0x0000000000000000,
1708  0x0000000000000000, false, false };
1709  return parameters;
1710  }
1711 #endif // CRCPP_INCLUDE_ESOTERIC_CRC_DEFINITIONS
1712 
1713 #ifdef CRCPP_USE_NAMESPACE
1714 }
1715 #endif
1716 
1717 #endif // CRCPP_CRC_H_
crcpp_constexpr
#define crcpp_constexpr
Compile-time expression definition.
Definition: CRC.h:127
crcpp_uint16
#define crcpp_uint16
Unsigned 16-bit integer definition, used primarily for parameter definitions.
Definition: CRC.h:88
crcpp_size
#define crcpp_size
Unsigned size definition, used for specifying data sizes.
Definition: CRC.h:118
size
int size
Definition: FileIOFactory.cpp:130
CRC
Static class for computing CRCs.
Definition: CRC.h:143
CRC::Calculate
static CRCType Calculate(const void *data, size_t size, const Parameters< CRCType, CRCWidth > &parameters)
Computes a CRC.
Definition: CRC.h:432
CRC::CRC_8
static const Parameters< uint8_t, 8 > & CRC_8()
Returns a set of parameters for CRC-8 SMBus.
Definition: CRC.h:956
CRC::CRC_16_KERMIT
static const Parameters< uint16_t, 16 > & CRC_16_KERMIT()
Returns a set of parameters for CRC-16 KERMIT (aka CRC-16 CCITT, CRC-16 CCITT-TRUE).
Definition: CRC.h:1338
CRC::CRC_32_POSIX
static const Parameters< uint32_t, 32 > & CRC_32_POSIX()
Returns a set of parameters for CRC-32 POSIX.
Definition: CRC.h:1650
CRC::CRC_32_BZIP2
static const Parameters< uint32_t, 32 > & CRC_32_BZIP2()
Returns a set of parameters for CRC-32 BZIP2 (aka CRC-32 AAL5, CRC-32 DECT-B, CRC-32 B-CRC).
Definition: CRC.h:1594
CRC::CRC_16_BUYPASS
static const Parameters< uint16_t, 16 > & CRC_16_BUYPASS()
Returns a set of parameters for CRC-16 BUYPASS (aka CRC-16 VERIFONE, CRC-16 UMTS).
Definition: CRC.h:1210
CRC::CRC_32
static const Parameters< uint32_t, 32 > & CRC_32()
Returns a set of parameters for CRC-32 (aka CRC-32 ADCCP, CRC-32 PKZip).
Definition: CRC.h:1576
CRC::CRC_16_X25
static const Parameters< uint16_t, 16 > & CRC_16_X25()
Returns a set of parameters for CRC-16 X-25 (aka CRC-16 IBM-SDLC, CRC-16 ISO-HDLC,...
Definition: CRC.h:1430
CRC::CRC_16_GENIBUS
static const Parameters< uint16_t, 16 > & CRC_16_GENIBUS()
Returns a set of parameters for CRC-16 GENIBUS (aka CRC-16 EPC, CRC-16 I-CODE, CRC-16 DARC).
Definition: CRC.h:1320
CRC::CRC_16_CCITTFALSE
static const Parameters< uint16_t, 16 > & CRC_16_CCITTFALSE()
Returns a set of parameters for CRC-16 CCITT FALSE.
Definition: CRC.h:1228
CRC::CRC_32_MPEG2
static const Parameters< uint32_t, 32 > & CRC_32_MPEG2()
Returns a set of parameters for CRC-32 MPEG-2.
Definition: CRC.h:1632
CRC::CRC_16_XMODEM
static const Parameters< uint16_t, 16 > & CRC_16_XMODEM()
Returns a set of parameters for CRC-16 XMODEM (aka CRC-16 ZMODEM, CRC-16 ACORN, CRC-16 LTE).
Definition: CRC.h:1448
CRC::CRC_16_ARC
static const Parameters< uint16_t, 16 > & CRC_16_ARC()
Returns a set of parameters for CRC-16 ARC (aka CRC-16 IBM, CRC-16 LHA).
Definition: CRC.h:1192
std
Definition: Eigen.h:85
Table
struct Table Table
Definition: sqlite3.c:14665
CRC::Parameters
CRC parameters.
Definition: CRC.h:152
CRC::Parameters::MakeTable
Table< CRCType, CRCWidth > MakeTable() const
Returns a CRC lookup table construct using these CRC parameters.
Definition: CRC.h:314
CRC::Parameters::initialValue
CRCType initialValue
Initial CRC value.
Definition: CRC.h:154
CRC::Parameters::polynomial
CRCType polynomial
CRC polynomial.
Definition: CRC.h:153
CRC::Parameters::finalXOR
CRCType finalXOR
Value to XOR with the final CRC.
Definition: CRC.h:155
CRC::Parameters::reflectInput
bool reflectInput
true to reflect all input bytes
Definition: CRC.h:156
CRC::Parameters::reflectOutput
bool reflectOutput
true to reflect the output CRC (reflection occurs before the final XOR)
Definition: CRC.h:157
CRC::Table
CRC lookup table. After construction, the CRC parameters are fixed.
Definition: CRC.h:167
CRC::Table::GetTable
const CRCType * GetTable() const
Gets the CRC table.
Definition: CRC.h:367
CRC::Table::GetParameters
const Parameters< CRCType, CRCWidth > & GetParameters() const
Gets the CRC parameters used to construct the CRC table.
Definition: CRC.h:355
CRC::Table::operator[]
CRCType operator[](unsigned char index) const
Gets an entry in the CRC table.
Definition: CRC.h:380
CRC::Table::Table
Table(const Parameters< CRCType, CRCWidth > &parameters)
Constructs a CRC table from a set of CRC parameters.
Definition: CRC.h:327
Parameters
Algorithm parameters.
Definition: ecvPoissonReconDlg.cpp:43