CppSerdes  1.0
A serialization/deserialization library designed with embedded systems in mind
cppcrc.h
Go to the documentation of this file.
1 
9 #ifndef CPPCRC_H_
10 #define CPPCRC_H_
11 
12 #include <stddef.h>
13 #include <stdint.h>
14 #include <utility>
15 
16 //
17 // Backend implementation:
18 //
19 
20 namespace crc_utils
21 {
22  inline constexpr uint8_t reverse_bits(uint8_t x)
23  {
24  constexpr uint8_t lookup[16] = {0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf};
25  return (lookup[x & 0x0F] << 4) | lookup[x >> 4];
26  }
27  inline constexpr uint16_t reverse_bits(uint16_t x)
28  {
29  return uint16_t(reverse_bits(uint8_t(x))) << 8 | uint16_t(reverse_bits(uint8_t(x >> 8)));
30  }
31  inline constexpr uint32_t reverse_bits(uint32_t x)
32  {
33  return uint32_t(reverse_bits(uint16_t(x))) << 16 | uint32_t(reverse_bits(uint16_t(x >> 16)));
34  }
35  inline constexpr uint64_t reverse_bits(uint64_t x)
36  {
37  return uint64_t(reverse_bits(uint32_t(x))) << 32 | uint64_t(reverse_bits(uint32_t(x >> 32)));
38  }
39  template <typename out_t, out_t poly, bool refl_in, bool refl_out, size_t index>
40  constexpr out_t get_crc_table_value_at_index()
41  {
42  constexpr size_t bit_width = sizeof(out_t) * 8;
43  out_t remainder = refl_in ? reverse_bits(static_cast<out_t>(index)) >> (bit_width - 8u) : static_cast<out_t>(index);
44  constexpr out_t mask = static_cast<out_t>(1) << (bit_width - 1u);
45  for (size_t i = 0; i < bit_width; i++)
46  {
47  if (remainder & mask)
48  remainder = (remainder << 1) ^ poly;
49  else
50  remainder <<= 1;
51  }
52  return refl_in ? reverse_bits(remainder) : remainder;
53  }
54 
55  template <typename out_t, out_t poly, bool refl_in, bool refl_out, size_t size = 256, typename = std::make_index_sequence<size>>
56  struct crc_lookup_table;
57 
58  template <typename out_t, out_t poly, bool refl_in, bool refl_out, size_t size, size_t... indexes>
59  struct crc_lookup_table<out_t, poly, refl_in, refl_out, size, std::index_sequence<indexes...>>
60  {
61  static constexpr out_t value[size] = {get_crc_table_value_at_index<out_t, poly, refl_in, refl_out, indexes>()...};
62  };
63 
64 #if ((defined(_MSVC_LANG) && _MSVC_LANG < 201703L) || (defined(__cplusplus) && __cplusplus < 201703L)) // redeclaration is only needed before C++17
65  template <typename out_t, out_t poly, bool refl_in, bool refl_out, size_t size, size_t... indexes>
66  constexpr out_t crc_lookup_table<out_t, poly, refl_in, refl_out, size, std::index_sequence<indexes...>>::value[size];
67 #endif
68 
69  template <typename out_t, out_t poly, bool refl_in, bool refl_out, out_t x_or_out, typename std::enable_if<refl_in, int *>::type = nullptr>
70  constexpr out_t calculate_crc(const uint8_t *bytes, size_t n, out_t crc)
71  {
72  constexpr auto &lookup = crc_lookup_table<out_t, poly, refl_in, refl_out>().value;
73  crc = reverse_bits(crc);
74  while (n--)
75  crc = lookup[static_cast<uint8_t>(*bytes++ ^ crc)] ^ (crc >> 8);
76  return (refl_out != refl_in ? reverse_bits(crc) : crc) ^ x_or_out; // needed since the reflections are baked into the table for speed
77  }
78 
79  template <typename out_t, out_t poly, bool refl_in, bool refl_out, out_t x_or_out, typename std::enable_if<!refl_in, int *>::type = nullptr>
80  constexpr out_t calculate_crc(const uint8_t *bytes, size_t n, out_t crc)
81  {
82  constexpr auto &lookup = crc_lookup_table<out_t, poly, refl_in, refl_out>().value;
83  constexpr size_t bit_width_minus_8 = sizeof(out_t) * 8 - 8U;
84  while (n--)
85  crc = lookup[static_cast<uint8_t>(*bytes++ ^ (crc >> bit_width_minus_8))] ^ (crc << 8);
86  return (refl_out ? reverse_bits(crc) : crc) ^ x_or_out;
87  }
88 
89  template <typename out_t, out_t poly_arg, out_t init_arg, bool refl_in_arg, bool refl_out_arg, out_t x_or_out_arg>
90  struct crc
91  {
92  using type = out_t; // base type of the crc algorithm
93  static constexpr out_t poly = poly_arg; // polynomial of the crc algorithm
94  static constexpr out_t init = init_arg; // initial CRC internal state, WARNING: may be different from "null_crc"
95  static constexpr bool refl_in = refl_in_arg; // true if the bits of the crc should be reflected/reversed on input
96  static constexpr bool refl_out = refl_out_arg; // true if the bits of the crc should be reflected/reversed on output
97  static constexpr out_t x_or_out = x_or_out_arg; // the value to X-OR the output with
98  static constexpr out_t null_crc = (refl_out ? reverse_bits(init) : init) ^ x_or_out; // CRC value of no/null data
99 
101  static constexpr out_t calc(const uint8_t *bytes = nullptr, size_t num_bytes = 0u, out_t prior_crc_value = null_crc)
102  {
103  prior_crc_value = x_or_out ? prior_crc_value ^ x_or_out : prior_crc_value;
104  prior_crc_value = refl_out ? reverse_bits(prior_crc_value) : prior_crc_value;
105  return calculate_crc<out_t, poly, refl_in, refl_out, x_or_out>(bytes, num_bytes, prior_crc_value);
106  }
108  static constexpr auto &table()
109  {
110  return crc_lookup_table<out_t, poly, refl_in, refl_out>().value;
111  }
112  };
113 } // namespace crc_utils
114 
115 //
116 // Default CRC Configurations: <type, poly, init, refl_in, refl_out, x_or_out>
117 //
118 
119 namespace CRC8
120 {
121  using CRC8 = crc_utils::crc<uint8_t, 0x07, 0x00, false, false, 0x00>;
122  using CDMA2000 = crc_utils::crc<uint8_t, 0x9B, 0xFF, false, false, 0x00>;
123  using DARC = crc_utils::crc<uint8_t, 0x39, 0x00, true, true, 0x00>;
124  using DVB_S2 = crc_utils::crc<uint8_t, 0xD5, 0x00, false, false, 0x00>;
125  using EBU = crc_utils::crc<uint8_t, 0x1D, 0xFF, true, true, 0x00>;
126  using I_CODE = crc_utils::crc<uint8_t, 0x1D, 0xFD, false, false, 0x00>;
127  using ITU = crc_utils::crc<uint8_t, 0x07, 0x00, false, false, 0x55>;
128  using MAXIM = crc_utils::crc<uint8_t, 0x31, 0x00, true, true, 0x00>;
129  using ROHC = crc_utils::crc<uint8_t, 0x07, 0xFF, true, true, 0x00>;
130  using WCDMA = crc_utils::crc<uint8_t, 0x9B, 0x00, true, true, 0x00>;
131 } // namespace CRC8
132 namespace CRC16
133 {
134  using ARC = crc_utils::crc<uint16_t, 0x8005, 0x0000, true, true, 0x0000>;
135  using AUG_CCITT = crc_utils::crc<uint16_t, 0x1021, 0x1D0F, false, false, 0x0000>;
136  using BUYPASS = crc_utils::crc<uint16_t, 0x8005, 0x0000, false, false, 0x0000>;
137  using CCITT_FALSE = crc_utils::crc<uint16_t, 0x1021, 0xFFFF, false, false, 0x0000>;
138  using CDMA2000 = crc_utils::crc<uint16_t, 0xC867, 0xFFFF, false, false, 0x0000>;
139  using DDS_110 = crc_utils::crc<uint16_t, 0x8005, 0x800D, false, false, 0x0000>;
140  using DECT_R = crc_utils::crc<uint16_t, 0x0589, 0x0000, false, false, 0x0001>;
141  using DECT_X = crc_utils::crc<uint16_t, 0x0589, 0x0000, false, false, 0x0000>;
142  using DNP = crc_utils::crc<uint16_t, 0x3D65, 0x0000, true, true, 0xFFFF>;
143  using EN_13757 = crc_utils::crc<uint16_t, 0x3D65, 0x0000, false, false, 0xFFFF>;
144  using GENIBUS = crc_utils::crc<uint16_t, 0x1021, 0xFFFF, false, false, 0xFFFF>;
145  using KERMIT = crc_utils::crc<uint16_t, 0x1021, 0x0000, true, true, 0x0000>;
146  using MAXIM = crc_utils::crc<uint16_t, 0x8005, 0x0000, true, true, 0xFFFF>;
147  using MCRF4XX = crc_utils::crc<uint16_t, 0x1021, 0xFFFF, true, true, 0x0000>;
148  using MODBUS = crc_utils::crc<uint16_t, 0x8005, 0xFFFF, true, true, 0x0000>;
149  using RIELLO = crc_utils::crc<uint16_t, 0x1021, 0xB2AA, true, true, 0x0000>;
150  using T10_DIF = crc_utils::crc<uint16_t, 0x8BB7, 0x0000, false, false, 0x0000>;
151  using TELEDISK = crc_utils::crc<uint16_t, 0xA097, 0x0000, false, false, 0x0000>;
152  using TMS37157 = crc_utils::crc<uint16_t, 0x1021, 0x89EC, true, true, 0x0000>;
153  using USB = crc_utils::crc<uint16_t, 0x8005, 0xFFFF, true, true, 0xFFFF>;
154  using X_25 = crc_utils::crc<uint16_t, 0x1021, 0xFFFF, true, true, 0xFFFF>;
155  using XMODEM = crc_utils::crc<uint16_t, 0x1021, 0x0000, false, false, 0x0000>;
156  using A = crc_utils::crc<uint16_t, 0x1021, 0xC6C6, true, true, 0x0000>;
157 } // namespace CRC16
158 namespace CRC32
159 {
160  using CRC32 = crc_utils::crc<uint32_t, 0x04C11DB7, 0xFFFFFFFF, true, true, 0xFFFFFFFF>;
161  using BZIP2 = crc_utils::crc<uint32_t, 0x04C11DB7, 0xFFFFFFFF, false, false, 0xFFFFFFFF>;
162  using JAMCRC = crc_utils::crc<uint32_t, 0x04C11DB7, 0xFFFFFFFF, true, true, 0x00000000>;
163  using MPEG_2 = crc_utils::crc<uint32_t, 0x04C11DB7, 0xFFFFFFFF, false, false, 0x00000000>;
164  using POSIX = crc_utils::crc<uint32_t, 0x04C11DB7, 0x00000000, false, false, 0xFFFFFFFF>;
165  using SATA = crc_utils::crc<uint32_t, 0x04C11DB7, 0x52325032, false, false, 0x00000000>;
166  using XFER = crc_utils::crc<uint32_t, 0x000000AF, 0x00000000, false, false, 0x00000000>;
167  using C = crc_utils::crc<uint32_t, 0x1EDC6F41, 0xFFFFFFFF, true, true, 0xFFFFFFFF>;
168  using D = crc_utils::crc<uint32_t, 0xA833982B, 0xFFFFFFFF, true, true, 0xFFFFFFFF>;
169  using Q = crc_utils::crc<uint32_t, 0x814141AB, 0x00000000, false, false, 0x00000000>;
170 } // namespace CRC32
171 namespace CRC64
172 {
173  using ECMA = crc_utils::crc<uint64_t, 0x42F0E1EBA9EA3693, 0x0000000000000000, false, false, 0x0000000000000000>;
174  using GO_ISO = crc_utils::crc<uint64_t, 0x000000000000001B, 0xFFFFFFFFFFFFFFFF, true, true, 0xFFFFFFFFFFFFFFFF>;
175  using WE = crc_utils::crc<uint64_t, 0x42F0E1EBA9EA3693, 0xFFFFFFFFFFFFFFFF, false, false, 0xFFFFFFFFFFFFFFFF>;
176  using XY = crc_utils::crc<uint64_t, 0x42F0E1EBA9EA3693, 0xFFFFFFFFFFFFFFFF, true, true, 0xFFFFFFFFFFFFFFFF>;
177 } // namespace CRC64
178 
179 #endif // CPPCRC_H_
crc_utils::crc::table
static constexpr auto & table()
the underlying pre-computed CRC table used for fast lookup-table-based calculations
Definition: cppcrc.h:108
crc_utils::crc_lookup_table
Definition: cppcrc.h:56
crc_utils::crc::calc
static constexpr out_t calc(const uint8_t *bytes=nullptr, size_t num_bytes=0u, out_t prior_crc_value=null_crc)
Calculate the checksum of some bytes, or continue an existing calculation by passing in the prior crc...
Definition: cppcrc.h:101
crc_utils::crc
Definition: cppcrc.h:90