Embedded Template Library 1.0
Loading...
Searching...
No Matches
crc_implementation.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2021 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_CRC_IMPLEMENTATION_INCLUDED
32#define ETL_CRC_IMPLEMENTATION_INCLUDED
33
34#include "../platform.h"
35#include "../binary.h"
37#include "../static_assert.h"
38#include "../type_traits.h"
39
40#include "stdint.h"
41
42#include "crc_parameters.h"
43
44#if defined(ETL_COMPILER_KEIL)
45 #pragma diag_suppress 1300
46#endif
47
48namespace etl
49{
50 namespace private_crc
51 {
52 //*****************************************************************************
54 //*****************************************************************************
55 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, TAccumulator Entry>
57 {
58 private:
59
60 static ETL_CONSTANT bool Do_Poly = Reflect ? (Entry & TAccumulator(1U)) != 0U : (Entry & (TAccumulator(1U) << (Accumulator_Bits - 1U))) != 0U;
61
62 public:
63
64 static ETL_CONSTANT TAccumulator value =
65 Reflect ? TAccumulator(Do_Poly ? (Entry >> 1U) ^ etl::reverse_bits_const<TAccumulator, Polynomial>::value : (Entry >> 1U))
66 : TAccumulator(Do_Poly ? (Entry << 1U) ^ Polynomial : (Entry << 1U));
67 };
68
69 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, TAccumulator Entry>
70 ETL_CONSTANT TAccumulator crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect, Entry>::value;
71
72 //*****************************************************************************
74 //*****************************************************************************
75 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index, uint8_t Chunk_Bits>
77 {
78 ETL_STATIC_ASSERT((Chunk_Bits == 2U) || (Chunk_Bits == 4U) || (Chunk_Bits == 8U), "Chunk bits must be 2, 4 or 8");
79 };
80
81 //*********************************
82 // Chunk bit size of 2.
83 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
84 class crc_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Index, 2U>
85 {
86 public:
87
88 static ETL_CONSTANT size_t Shift_Bits = size_t(Accumulator_Bits - 2U);
89 static ETL_CONSTANT TAccumulator Entry = Reflect ? TAccumulator(Index) : TAccumulator(TAccumulator(Index) << Shift_Bits);
90
91 static ETL_CONSTANT TAccumulator value =
92 crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect,
93 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Entry>::value>::value;
94 };
95
96 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
98
99 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
101
102 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
104
105 //*********************************
106 // Chunk bit size of 4.
107 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
108 class crc_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Index, 4U>
109 {
110 public:
111
112 static ETL_CONSTANT size_t Shift_Bits = size_t(Accumulator_Bits - 4U);
113 static ETL_CONSTANT TAccumulator Entry = Reflect ? TAccumulator(Index) : TAccumulator(TAccumulator(Index) << Shift_Bits);
114
115 static ETL_CONSTANT TAccumulator value = crc_partial_table_entry<
116 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
118 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
119 crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect,
120 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Entry>::value>::value>::value>::value;
121 };
122
123 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
125
126 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
128
129 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
131
132 //*********************************
133 // Chunk bit size of 8.
134 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
135 class crc_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Index, 8U>
136 {
137 public:
138
139 static ETL_CONSTANT size_t Shift_Bits = size_t(Accumulator_Bits - 8U);
140 static ETL_CONSTANT TAccumulator Entry = Reflect ? TAccumulator(Index) : TAccumulator(TAccumulator(Index) << Shift_Bits);
141
142 static ETL_CONSTANT TAccumulator value = crc_partial_table_entry<
143 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
145 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
147 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
149 TAccumulator, Accumulator_Bits, Polynomial, Reflect,
150 crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect,
151 crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect,
152 crc_partial_table_entry< TAccumulator, Accumulator_Bits, Polynomial, Reflect,
153 crc_partial_table_entry<TAccumulator, Accumulator_Bits,
154 Polynomial, Reflect, Entry>::value>::
155 value>::value>::value>::value>::value>::value>::value;
156 };
157
158 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
160
161 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
163
164 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
166
167 //*****************************************************************************
169 //*****************************************************************************
170
171 //*********************************
172 // Accumulator_Bits > Chunk_Bits
173 // Not Reflected
174 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
175 static ETL_CONSTEXPR14 typename etl::enable_if<(Accumulator_Bits > Chunk_Bits) && !Reflect, TAccumulator>::type
176 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
177 {
178 value &= Chunk_Mask;
179
180 uint8_t index = (crc >> (Accumulator_Bits - Chunk_Bits)) ^ value;
181
182 crc <<= Chunk_Bits;
183 crc ^= table[index];
184
185 return crc;
186 }
187
188 //*********************************
189 // Accumulator_Bits > Chunk_Bits
190 // Reflected
191 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
192 static ETL_CONSTEXPR14 typename etl::enable_if<(Accumulator_Bits > Chunk_Bits) && Reflect, TAccumulator>::type
193 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
194 {
195 value &= Chunk_Mask;
196
197 uint8_t index = (crc & Chunk_Mask) ^ value;
198
199 crc >>= Chunk_Bits;
200 crc ^= table[index];
201
202 return crc;
203 }
204
205 //*********************************
206 // Accumulator_Bits == Chunk_Bits
207 // Not Reflected
208 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
209 static ETL_CONSTEXPR14 typename etl::enable_if<(Accumulator_Bits == Chunk_Bits) && !Reflect, TAccumulator>::type
210 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
211 {
212 value &= Chunk_Mask;
213
214 uint8_t index = (crc >> (Accumulator_Bits - Chunk_Bits)) ^ value;
215
216 crc = table[index];
217
218 return crc;
219 }
220
221 //*********************************
222 // Accumulator_Bits == Chunk_Bits
223 // Reflected
224 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
225 static ETL_CONSTEXPR14 typename etl::enable_if<(Accumulator_Bits == Chunk_Bits) && Reflect, TAccumulator>::type
226 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
227 {
228 value &= Chunk_Mask;
229
230 uint8_t index = (crc & Chunk_Mask) ^ value;
231
232 crc = table[index];
233
234 return crc;
235 }
236
237 //*****************************************************************************
238 // CRC Tables.
239 //*****************************************************************************
240 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect,
241 size_t Table_Size>
242 struct crc_table;
243
244 //*********************************
245 // Table size of 4.
246 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
247 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 4U>
248 {
249 //*************************************************************************
250#if !ETL_USING_CPP11
251 TAccumulator add(TAccumulator crc, uint8_t value) const
252 {
253#endif
258#if ETL_USING_CPP11
259 ETL_CONSTEXPR14 TAccumulator add(TAccumulator crc, uint8_t value) const
260 {
261#endif
262 if ETL_IF_CONSTEXPR (Reflect)
263 {
264 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
265 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 1U)), table);
266 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 2U)), table);
267 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 3U)), table);
268 }
269 else
270 {
271 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 3U)), table);
272 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 2U)), table);
273 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 1U)), table);
274 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
275 }
276
277 return crc;
278 }
279 };
280#if ETL_USING_CPP11
281 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
283#endif
284
285 //*********************************
286 // Table size of 16.
287 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
288 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 16U>
289 {
290 //*************************************************************************
291#if !ETL_USING_CPP11
292 TAccumulator add(TAccumulator crc, uint8_t value) const
293 {
294#endif
295 static
312#if ETL_USING_CPP11
313 ETL_CONSTEXPR14 TAccumulator add(TAccumulator crc, uint8_t value) const
314 {
315#endif
316 if ETL_IF_CONSTEXPR (Reflect)
317 {
318 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
319 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value >> Chunk_Bits, table);
320 }
321 else
322 {
323 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value >> Chunk_Bits, table);
324 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
325 }
326
327 return crc;
328 }
329 };
330#if ETL_USING_CPP11
331 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
333#endif
334
335 //*********************************
336 // Table size of 256.
337 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
338 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 256U>
339 {
340 //*************************************************************************
341#if !ETL_USING_CPP11
342 TAccumulator add(TAccumulator crc, uint8_t value) const
343 {
344#endif
345 static
602#if ETL_USING_CPP11
603 ETL_CONSTEXPR14 TAccumulator add(TAccumulator crc, uint8_t value) const
604 {
605#endif
606
607 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
608
609 return crc;
610 }
611 };
612#if ETL_USING_CPP11
613 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
615#endif
616 //*****************************************************************************
617 // CRC Policies.
618 //*****************************************************************************
619 template <typename TCrcParameters, size_t Table_Size>
621
622 //*********************************
623 // Policy for 256 entry table.
624 template <typename TCrcParameters>
625 struct crc_policy<TCrcParameters, 256U>
626 : public crc_table<typename TCrcParameters::accumulator_type, TCrcParameters::Accumulator_Bits, 8U, 0xFFU, TCrcParameters::Polynomial,
627 TCrcParameters::Reflect, 256U>
628 {
629 typedef typename TCrcParameters::accumulator_type accumulator_type;
630 typedef accumulator_type value_type;
631
632 //*************************************************************************
633 ETL_CONSTEXPR accumulator_type initial() const
634 {
635 return TCrcParameters::Reflect ? etl::reverse_bits_const<accumulator_type, TCrcParameters::Initial>::value : TCrcParameters::Initial;
636 }
637
638 //*************************************************************************
639 ETL_CONSTEXPR accumulator_type final(accumulator_type crc) const
640 {
641 return crc ^ TCrcParameters::Xor_Out;
642 }
643 };
644
645 //*********************************
646 // Policy for 16 entry table.
647 template <typename TCrcParameters>
648 struct crc_policy<TCrcParameters, 16U>
649 : public crc_table<typename TCrcParameters::accumulator_type, TCrcParameters::Accumulator_Bits, 4U, 0x0FU, TCrcParameters::Polynomial,
650 TCrcParameters::Reflect, 16U>
651 {
652 typedef typename TCrcParameters::accumulator_type accumulator_type;
653 typedef accumulator_type value_type;
654
655 //*************************************************************************
656 ETL_CONSTEXPR accumulator_type initial() const
657 {
658 return TCrcParameters::Reflect ? etl::reverse_bits_const<accumulator_type, TCrcParameters::Initial>::value : TCrcParameters::Initial;
659 }
660
661 //*************************************************************************
662 ETL_CONSTEXPR accumulator_type final(accumulator_type crc) const
663 {
664 return crc ^ TCrcParameters::Xor_Out;
665 }
666 };
667
668 //*********************************
669 // Policy for 4 entry table.
670 template <typename TCrcParameters>
671 struct crc_policy<TCrcParameters, 4U>
672 : public crc_table<typename TCrcParameters::accumulator_type, TCrcParameters::Accumulator_Bits, 2U, 0x03U, TCrcParameters::Polynomial,
673 TCrcParameters::Reflect, 4U>
674 {
675 typedef typename TCrcParameters::accumulator_type accumulator_type;
676 typedef accumulator_type value_type;
677
678 //*************************************************************************
679 ETL_CONSTEXPR accumulator_type initial() const
680 {
681 return TCrcParameters::Reflect ? etl::reverse_bits_const<accumulator_type, TCrcParameters::Initial>::value : TCrcParameters::Initial;
682 }
683
684 //*************************************************************************
685 ETL_CONSTEXPR accumulator_type final(accumulator_type crc) const
686 {
687 return crc ^ TCrcParameters::Xor_Out;
688 }
689 };
690 }
691
692 //*****************************************************************************
694 //*****************************************************************************
695 template <typename TCrcParameters, size_t Table_Size>
696 class crc_type : public etl::frame_check_sequence< private_crc::crc_policy<TCrcParameters, Table_Size> >
697 {
698 public:
699
700 ETL_STATIC_ASSERT((Table_Size == 4U) || (Table_Size == 16U) || (Table_Size == 256U), "Table size must be 4, 16 or 256");
701
702 //*************************************************************************
704 //*************************************************************************
705 ETL_CONSTEXPR14 crc_type()
706 {
707 this->reset();
708 }
709
710 //*************************************************************************
714 //*************************************************************************
715 template <typename TIterator>
716 ETL_CONSTEXPR14 crc_type(TIterator begin, const TIterator end)
717 {
718 this->reset();
719 this->add(begin, end);
720 }
721 };
722 }
723
724#endif
ETL_CONSTEXPR14 crc_type(TIterator begin, const TIterator end)
Definition crc_implementation.h:716
ETL_CONSTEXPR14 crc_type()
Default constructor.
Definition crc_implementation.h:705
CRC Partial Table Entry.
Definition crc_implementation.h:57
CRC Table Entry.
Definition crc_implementation.h:77
Definition binary.h:483
ETL_CONSTEXPR14 void add(TIterator begin, const TIterator end)
Definition frame_check_sequence.h:145
ETL_CONSTEXPR14 void reset()
Definition frame_check_sequence.h:134
Definition frame_check_sequence.h:98
bitset_ext
Definition absolute.h:40
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition iterator.h:967
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition iterator.h:997
Definition crc_implementation.h:620
Definition crc_implementation.h:242