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 #include <initializer_list>
7 
8 namespace openmsx {
9 
10 struct CRC16Lut { // replace with std::array in c++17
11  uint16_t a[8][0x100];
12 };
13 inline constexpr CRC16Lut calcTable()
14 {
15  CRC16Lut result = {};
16  for (unsigned i = 0; i < 0x100; ++i) {
17  uint16_t x = i << 8;
18  for (int j = 0; j < 8; ++j) {
19  x = (x << 1) ^ ((x & 0x8000) ? 0x1021 : 0);
20  }
21  result.a[0][i] = x;
22  }
23  for (unsigned i = 0; i < 0x100; ++i) {
24  uint16_t c = result.a[0][i];
25  for (unsigned j = 1; j < 8; ++j) {
26  c = result.a[0][c >> 8] ^ (c << 8);
27  result.a[j][i] = c;
28  }
29  }
30  return result;
31 }
32 
37 class CRC16
38 {
39 public:
42  explicit constexpr CRC16(uint16_t initialCRC = 0xffff)
43  : crc(initialCRC)
44  {
45  }
46 
49  constexpr void init(uint16_t initialCRC)
50  {
51  crc = initialCRC;
52  }
53 
54  constexpr void init(std::initializer_list<uint8_t> list)
55  {
56  crc = 0xffff;
57  for (auto& val : list) {
58  update(val);
59  }
60  }
61 
64  constexpr void update(uint8_t value)
65  {
66  // Classical byte-at-a-time algorithm by Dilip V. Sarwate
67  crc = (crc << 8) ^ tab.a[0][(crc >> 8) ^ value];
68  }
69 
73  constexpr void update(const uint8_t* data, size_t size)
74  {
75  // Based on:
76  // Slicing-by-4 and slicing-by-8 algorithms by Michael E.
77  // Kounavis and Frank L. Berry from Intel Corp.
78  // http://www.intel.com/technology/comms/perfnet/download/CRC_generators.pdf
79  // and the implementation by Peter Kankowski found on:
80  // http://www.strchr.com/crc32_popcnt
81  // I transformed the code from CRC32 to CRC16 (this was not
82  // trivial because both CRCs use a different convention about
83  // bit order). I also made the code work on bigendian hosts.
84 
85  unsigned c = crc; // 32-bit are faster than 16-bit calculations
86  // on x86 and many other modern architectures
87  // calculate the bulk of the data 8 bytes at a time
88  for (auto n = size / 8; n; --n) {
89  c = tab.a[7][data[0] ^ (c >> 8)] ^
90  tab.a[6][data[1] ^ (c & 255)] ^
91  tab.a[5][data[2]] ^
92  tab.a[4][data[3]] ^
93  tab.a[3][data[4]] ^
94  tab.a[2][data[5]] ^
95  tab.a[1][data[6]] ^
96  tab.a[0][data[7]];
97  data += 8;
98  }
99  // calculate the remaining bytes in the usual way
100  for (size &= 7; size; --size) {
101  c = uint16_t(c << 8) ^ tab.a[0][(c >> 8) ^ *data++];
102  }
103  crc = c; // store back in a 16-bit result
104  }
105 
108  constexpr uint16_t getValue() const
109  {
110  return crc;
111  }
112 
113 private:
114  static constexpr CRC16Lut tab = calcTable();
115 
116  uint16_t crc;
117 };
118 
119 } // namespace openmsx
120 
121 #endif
constexpr uint16_t getValue() const
Get current CRC value.
Definition: CRC16.hh:108
constexpr void update(const uint8_t *data, size_t size)
For large blocks (e.g.
Definition: CRC16.hh:73
constexpr void init(std::initializer_list< uint8_t > list)
Definition: CRC16.hh:54
constexpr CRC16(uint16_t initialCRC=0xffff)
Create CRC16 with an optional initial value.
Definition: CRC16.hh:42
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.hh:69
This class calculates CRC numbers for the polygon x^16 + x^12 + x^5 + 1.
Definition: CRC16.hh:37
constexpr void init(uint16_t initialCRC)
(Re)initialize the current value
Definition: CRC16.hh:49
Thanks to enen for testing this on a real cartridge:
Definition: Autofire.cc:5
constexpr CRC16Lut calcTable()
Definition: CRC16.hh:13
uint16_t a[8][0x100]
Definition: CRC16.hh:11
constexpr void update(uint8_t value)
Update CRC with one byte.
Definition: CRC16.hh:64
constexpr auto size(const C &c) -> decltype(c.size())
Definition: span.hh:62