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