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