OXYGENHUB
◆ main openmsx / src / utils / CRC16.hh
2.8 KiB · C++ · last changed chore(): initial commit 1 month ago source blame history raw
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
12 
namespace openmsx {
13
14 
/**
15 
 * This class calculates CRC numbers for the polygon
16 
 *   x^16 + x^12 + x^5 + 1
17 
 */
18 
class CRC16
19 
{
20 
public:
21 
	/** Create CRC16 with an optional initial value
22 
	 */
23 
	explicit constexpr CRC16(uint16_t initialCRC = 0xffff)
24 
		: crc(initialCRC)
25 
	{
26 
	}
27
28 
	/** (Re)initialize the current value
29 
	 */
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
43 
	/** Update CRC with one byte
44 
	 */
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
51 
	/** For large blocks (e.g. 512 bytes) this routine is approx 5x faster
52 
	  * than calling the method above in a loop.
53 
	  */
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
87 
	/** Get current CRC value
88 
	 */
89 
	[[nodiscard]] constexpr uint16_t getValue() const
90 
	{
91 
		return crc;
92 
	}
93
94 
private:
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