Embedded Template Library 1.0
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 "../frame_check_sequence.h"
36#include "../static_assert.h"
37#include "../binary.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
61 : (Entry & (TAccumulator(1U) << (Accumulator_Bits - 1U))) != 0U;
62
63 public:
64
65 static ETL_CONSTANT TAccumulator value = 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>
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 = crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
93 };
94
95 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
97
98 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
100
101 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
103
104 //*********************************
105 // Chunk bit size of 4.
106 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
107 class crc_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Index, 4U>
108 {
109 public:
110
111 static ETL_CONSTANT size_t Shift_Bits = size_t(Accumulator_Bits - 4U);
112 static ETL_CONSTANT TAccumulator Entry = Reflect ? TAccumulator(Index) : TAccumulator(TAccumulator(Index) << Shift_Bits);
113
114 static ETL_CONSTANT TAccumulator value = crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
115 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
116 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
118 };
119
120 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
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 //*********************************
130 // Chunk bit size of 8.
131 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
132 class crc_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Index, 8U>
133 {
134 public:
135
136 static ETL_CONSTANT size_t Shift_Bits = size_t(Accumulator_Bits - 8U);
137 static ETL_CONSTANT TAccumulator Entry = Reflect ? TAccumulator(Index) : TAccumulator(TAccumulator(Index) << Shift_Bits);
138
139 static ETL_CONSTANT TAccumulator value = crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
140 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
141 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
142 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
143 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
144 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
145 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect,
146 crc_partial_table_entry<TAccumulator, Accumulator_Bits, Polynomial, Reflect, Entry>::value>::value>::value>::value>::value>::value>::value>::value;
147 };
148
149 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
151
152 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
154
155 template <typename TAccumulator, size_t Accumulator_Bits, TAccumulator Polynomial, bool Reflect, size_t Index>
157
158 //*****************************************************************************
160 //*****************************************************************************
161
162 //*********************************
163 // Accumulator_Bits > Chunk_Bits
164 // Not Reflected
165 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
166 static
167 typename etl::enable_if<(Accumulator_Bits > Chunk_Bits) && !Reflect, TAccumulator>::type
168 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
169 {
170 value &= Chunk_Mask;
171
172 uint8_t index = (crc >> (Accumulator_Bits - Chunk_Bits)) ^ value;
173
174 crc <<= Chunk_Bits;
175 crc ^= table[index];
176
177 return crc;
178 }
179
180 //*********************************
181 // Accumulator_Bits > Chunk_Bits
182 // Reflected
183 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
184 static
185 typename etl::enable_if<(Accumulator_Bits > Chunk_Bits) && Reflect, TAccumulator>::type
186 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
187 {
188 value &= Chunk_Mask;
189
190 uint8_t index = (crc & Chunk_Mask) ^ value;
191
192 crc >>= Chunk_Bits;
193 crc ^= table[index];
194
195 return crc;
196 }
197
198 //*********************************
199 // Accumulator_Bits == Chunk_Bits
200 // Not Reflected
201 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
202 static
203 typename etl::enable_if<(Accumulator_Bits == Chunk_Bits) && !Reflect, TAccumulator>::type
204 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
205 {
206 value &= Chunk_Mask;
207
208 uint8_t index = (crc >> (Accumulator_Bits - Chunk_Bits)) ^ value;
209
210 crc = table[index];
211
212 return crc;
213 }
214
215 //*********************************
216 // Accumulator_Bits == Chunk_Bits
217 // Reflected
218 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, bool Reflect>
219 static
220 typename etl::enable_if<(Accumulator_Bits == Chunk_Bits) && Reflect, TAccumulator>::type
221 crc_update_chunk(TAccumulator crc, uint8_t value, const TAccumulator table[])
222 {
223 value &= Chunk_Mask;
224
225 uint8_t index = (crc & Chunk_Mask) ^ value;
226
227 crc = table[index];
228
229 return crc;
230 }
231
232 //*****************************************************************************
233 // CRC Tables.
234 //*****************************************************************************
235 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect, size_t Table_Size>
236 struct crc_table;
237
238 //*********************************
239 // Table size of 4.
240 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
241 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 4U>
242 {
243 //*************************************************************************
244 TAccumulator add(TAccumulator crc, uint8_t value) const
245 {
246 static ETL_CONSTANT TAccumulator table[4U] =
247 {
252 };
253
254 if ETL_IF_CONSTEXPR(Reflect)
255 {
256 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
257 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 1U)), table);
258 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 2U)), table);
259 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 3U)), table);
260 }
261 else
262 {
263 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 3U)), table);
264 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, (value >> (Chunk_Bits * 2U)), 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, table);
267 }
268
269 return crc;
270 }
271 };
272
273 //*********************************
274 // Table size of 16.
275 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
276 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 16U>
277 {
278 //*************************************************************************
279 TAccumulator add(TAccumulator crc, uint8_t value) const
280 {
281 static ETL_CONSTANT TAccumulator table[16U] =
282 {
299 };
300
301 if ETL_IF_CONSTEXPR(Reflect)
302 {
303 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
304 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value >> Chunk_Bits, table);
305 }
306 else
307 {
308 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value >> Chunk_Bits, table);
309 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
310 }
311
312 return crc;
313 }
314 };
315
316 //*********************************
317 // Table size of 256.
318 template <typename TAccumulator, size_t Accumulator_Bits, size_t Chunk_Bits, uint8_t Chunk_Mask, TAccumulator Polynomial, bool Reflect>
319 struct crc_table<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Polynomial, Reflect, 256U>
320 {
321 //*************************************************************************
322 TAccumulator add(TAccumulator crc, uint8_t value) const
323 {
324 static ETL_CONSTANT TAccumulator table[256U] =
325 {
582 };
583
584 crc = crc_update_chunk<TAccumulator, Accumulator_Bits, Chunk_Bits, Chunk_Mask, Reflect>(crc, value, table);
585
586 return crc;
587 }
588 };
589
590 //*****************************************************************************
591 // CRC Policies.
592 //*****************************************************************************
593 template <typename TCrcParameters, size_t Table_Size>
595
596 //*********************************
597 // Policy for 256 entry table.
598 template <typename TCrcParameters>
599 struct crc_policy<TCrcParameters, 256U> : public crc_table<typename TCrcParameters::accumulator_type,
600 TCrcParameters::Accumulator_Bits,
601 8U,
602 0xFFU,
603 TCrcParameters::Polynomial,
604 TCrcParameters::Reflect,
605 256U>
606 {
607 typedef typename TCrcParameters::accumulator_type accumulator_type;
608 typedef accumulator_type value_type;
609
610 //*************************************************************************
611 ETL_CONSTEXPR accumulator_type initial() const
612 {
614 : TCrcParameters::Initial;
615 }
616
617 //*************************************************************************
618 accumulator_type final(accumulator_type crc) const
619 {
620 return crc ^ TCrcParameters::Xor_Out;
621 }
622 };
623
624 //*********************************
625 // Policy for 16 entry table.
626 template <typename TCrcParameters>
627 struct crc_policy<TCrcParameters, 16U> : public crc_table<typename TCrcParameters::accumulator_type,
628 TCrcParameters::Accumulator_Bits,
629 4U,
630 0x0FU,
631 TCrcParameters::Polynomial,
632 TCrcParameters::Reflect,
633 16U>
634 {
635 typedef typename TCrcParameters::accumulator_type accumulator_type;
636 typedef accumulator_type value_type;
637
638 //*************************************************************************
639 ETL_CONSTEXPR accumulator_type initial() const
640 {
642 : TCrcParameters::Initial;
643 }
644
645 //*************************************************************************
646 accumulator_type final(accumulator_type crc) const
647 {
648 return crc ^ TCrcParameters::Xor_Out;
649 }
650 };
651
652 //*********************************
653 // Policy for 4 entry table.
654 template <typename TCrcParameters>
655 struct crc_policy<TCrcParameters, 4U> : public crc_table<typename TCrcParameters::accumulator_type,
656 TCrcParameters::Accumulator_Bits,
657 2U,
658 0x03U,
659 TCrcParameters::Polynomial,
660 TCrcParameters::Reflect,
661 4U>
662 {
663 typedef typename TCrcParameters::accumulator_type accumulator_type;
664 typedef accumulator_type value_type;
665
666 //*************************************************************************
667 ETL_CONSTEXPR accumulator_type initial() const
668 {
670 : TCrcParameters::Initial;
671 }
672
673 //*************************************************************************
674 accumulator_type final(accumulator_type crc) const
675 {
676 return crc ^ TCrcParameters::Xor_Out;
677 }
678 };
679 }
680
681 //*****************************************************************************
683 //*****************************************************************************
684 template <typename TCrcParameters, size_t Table_Size>
685 class crc_type : public etl::frame_check_sequence<private_crc::crc_policy<TCrcParameters, Table_Size> >
686 {
687 public:
688
689 ETL_STATIC_ASSERT((Table_Size == 4U) || (Table_Size == 16U) || (Table_Size == 256U), "Table size must be 4, 16 or 256");
690
691 //*************************************************************************
693 //*************************************************************************
695 {
696 this->reset();
697 }
698
699 //*************************************************************************
703 //*************************************************************************
704 template<typename TIterator>
705 crc_type(TIterator begin, const TIterator end)
706 {
707 this->reset();
708 this->add(begin, end);
709 }
710 };
711}
712
713#endif
Basic parameterised CRC type.
Definition: crc_implementation.h:686
crc_type(TIterator begin, const TIterator end)
Definition: crc_implementation.h:705
crc_type()
Default constructor.
Definition: crc_implementation.h:694
CRC Partial Table Entry.
Definition: crc_implementation.h:57
CRC Table Entry.
Definition: crc_implementation.h:77
Definition: binary.h:514
void reset()
Resets the FCS to the initial state.
Definition: frame_check_sequence.h:134
void add(TIterator begin, const TIterator end)
Definition: frame_check_sequence.h:145
Definition: frame_check_sequence.h:100
enable_if
Definition: type_traits_generator.h:1191
bitset_ext
Definition: absolute.h:38
ETL_CONSTEXPR TContainer::iterator begin(TContainer &container)
Definition: iterator.h:931
ETL_CONSTEXPR TContainer::iterator end(TContainer &container)
Definition: iterator.h:961
Definition: crc_implementation.h:594
Definition: crc_implementation.h:236