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