openMSX
CRC16.hh
Go to the documentation of this file.
1 #ifndef CRC16_HH
2 #define CRC16_HH
3 
4 #include <cstddef>
5 #include <cstdint>
6 
7 namespace openmsx {
8 
13 class CRC16
14 {
15 public:
18  explicit CRC16(uint16_t initialCRC = 0xFFFF)
19  {
20  init(initialCRC);
21  }
22 
25  void init(uint16_t initialCRC)
26  {
27  crc = initialCRC;
28  }
29 
33  template<uint8_t V1> void init()
34  {
35  static const uint16_t T0 = 0xffff;
36  static const uint16_t T1 = CT_CRC16<T0, V1>::value;
37  init(T1);
38  }
39  template<uint8_t V1, uint8_t V2> void init()
40  {
41  static const uint16_t T0 = 0xffff;
42  static const uint16_t T1 = CT_CRC16<T0, V1>::value;
43  static const uint16_t T2 = CT_CRC16<T1, V2>::value;
44  init(T2);
45  }
46  template<uint8_t V1, uint8_t V2, uint8_t V3> void init()
47  {
48  static const uint16_t T0 = 0xffff;
49  static const uint16_t T1 = CT_CRC16<T0, V1>::value;
50  static const uint16_t T2 = CT_CRC16<T1, V2>::value;
51  static const uint16_t T3 = CT_CRC16<T2, V3>::value;
52  init(T3);
53  }
54  template<uint8_t V1, uint8_t V2, uint8_t V3, uint8_t V4> void init()
55  {
56  static const uint16_t T0 = 0xffff;
57  static const uint16_t T1 = CT_CRC16<T0, V1>::value;
58  static const uint16_t T2 = CT_CRC16<T1, V2>::value;
59  static const uint16_t T3 = CT_CRC16<T2, V3>::value;
60  static const uint16_t T4 = CT_CRC16<T3, V4>::value;
61  init(T4);
62  }
63 
66  void update(uint8_t value)
67  {
68  // Classical byte-at-a-time algorithm by Dilip V. Sarwate
69  crc = (crc << 8) ^ tab[0][(crc >> 8) ^ value];
70  }
71 
75  void update(const uint8_t* data, size_t size)
76  {
77  // Based on:
78  // Slicing-by-4 and slicing-by-8 algorithms by Michael E.
79  // Kounavis and Frank L. Berry from Intel Corp.
80  // http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf
81  // and the implementation by Peter Kankowski found on:
82  // http://www.strchr.com/crc32_popcnt
83  // I transformed the code from CRC32 to CRC16 (this was not
84  // trivial because both CRCs use a different convention about
85  // bit order). I also made the code work on bigendian hosts.
86 
87  unsigned c = crc; // 32-bit are faster than 16-bit calculations
88  // on x86 and many other modern architectures
89  // calculate the bulk of the data 8 bytes at a time
90  for (auto n = size / 8; n; --n) {
91  c = tab[7][data[0] ^ (c >> 8)] ^
92  tab[6][data[1] ^ (c & 255)] ^
93  tab[5][data[2]] ^
94  tab[4][data[3]] ^
95  tab[3][data[4]] ^
96  tab[2][data[5]] ^
97  tab[1][data[6]] ^
98  tab[0][data[7]];
99  data += 8;
100  }
101  // calculate the remaining bytes in the usual way
102  for (size &= 7; size; --size) {
103  c = uint16_t(c << 8) ^ tab[0][(c >> 8) ^ *data++];
104  }
105  crc = c; // store back in a 16-bit result
106  }
107 
110  uint16_t getValue() const
111  {
112  return crc;
113  }
114 
115 private:
116  uint16_t crc;
117  static const uint16_t tab[8][256];
118 
119  // The Stuff below is template magic to perform the following
120  // computation at compile-time:
121  // for (int i = 8; i < 16; ++i) {
122  // crc = (crc << 1) ^ ((((crc ^ (data << i)) & 0x8000) ? 0x1021 : 0));
123  // }
124  template<uint16_t C, uint16_t V, int B> struct CT_H {
125  static const uint16_t D = uint16_t(C << 1) ^ (((C ^ V) & 0x8000) ? 0x1021 : 0);
126  static const uint16_t value = CT_H<D, uint16_t(V << 1), B - 1>::value;
127  };
128  template<uint16_t C, uint16_t V> struct CT_H<C, V, 0> {
129  static const uint16_t value = C;
130  };
131  template<uint16_t IN, uint8_t VAL> struct CT_CRC16 : CT_H<IN, VAL << 8, 8> {};
132 };
133 
134 } // namespace openmsx
135 
136 #endif
void init()
Definition: CRC16.hh:46
void init(uint16_t initialCRC)
(Re)initialize the current value
Definition: CRC16.hh:25
uint16_t getValue() const
Get current CRC value.
Definition: CRC16.hh:110
void init()
(Re)initialize with a short initial sequence.
Definition: CRC16.hh:33
void init()
Definition: CRC16.hh:39
void init()
Definition: CRC16.hh:54
This class calculates CRC numbers for the polygon x^16 + x^12 + x^5 + 1.
Definition: CRC16.hh:13
void update(const uint8_t *data, size_t size)
For large blocks (e.g.
Definition: CRC16.hh:75
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:7
CRC16(uint16_t initialCRC=0xFFFF)
Create CRC16 with an optional initial value.
Definition: CRC16.hh:18
void update(uint8_t value)
Update CRC with one byte.
Definition: CRC16.hh:66
size_t size(string_ref utf8)