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