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
10namespace openmsx {
11
16class CRC16
17{
18public:
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
92private:
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
This class calculates CRC numbers for the polygon x^16 + x^12 + x^5 + 1.
Definition: CRC16.hh:17
constexpr void update(uint8_t value)
Update CRC with one byte.
Definition: CRC16.hh:43
constexpr void update(const uint8_t *data, size_t size)
For large blocks (e.g.
Definition: CRC16.hh:52
constexpr uint16_t getValue() const
Get current CRC value.
Definition: CRC16.hh:87
constexpr void init(std::initializer_list< uint8_t > list)
Definition: CRC16.hh:33
constexpr CRC16(uint16_t initialCRC=0xffff)
Create CRC16 with an optional initial value.
Definition: CRC16.hh:21
constexpr void init(uint16_t initialCRC)
(Re)initialize the current value
Definition: CRC16.hh:28
This file implemented 3 utility functions:
Definition: Autofire.cc:9
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:127
size_t size(std::string_view utf8)
constexpr void repeat(T n, Op op)
Repeat the given operation 'op' 'n' times.
Definition: xrange.hh:148
constexpr auto xrange(T e)
Definition: xrange.hh:133