Skip to content

Instantly share code, notes, and snippets.

@kugland

kugland/crc32.cpp

Last active September 3, 2019 05:07
Show Gist options
  • Save kugland/881c6cb82a8af8dc43aaba275bce2a25 to your computer and use it in GitHub Desktop.
Save kugland/881c6cb82a8af8dc43aaba275bce2a25 to your computer and use it in GitHub Desktop.
Download ZIP
Primitives for a header-only CRC-32 implementation for MCUs.
Raw
crc32.cpp
#include <stdint.h>
#include <stdio.h>
#include "helper.hpp"
#include "reflect.hpp"
using crc32::impl::bit_sizeof;
using crc32::impl::and_mask;
using crc32::impl::shift;
using crc32::impl::reflect_u8;
using crc32::impl::reflect_u32;
template <
unsigned Order,
uintmax_t Polynomial,
bool RefIn,
bool RefOut,
uintmax_t Init,
uintmax_t XorOut
>
struct
{
using type = uint32_t;
static constexpr unsigned order = Order;
static constexpr type polynomial = static_cast<type>(Polynomial);
static constexpr bool ref_in = RefIn;
static constexpr bool ref_out = RefOut;
static constexpr type init = static_cast<type>(Init);
static constexpr type xor_out = static_cast<type>(XorOut);
static constexpr bool reverse = reflect_input() ^ reflect_output();
static constexpr type shift_input(uint8_t byte)
{ return shift<type>(byte, reverse() ? 0 : order() - 8); }
static constexpr uint8_t reflect_input(uint8_t byte)
{ return ref_in ? reflect_u8(byte) : byte; }
};
template <typename Variant>
constexpr uint32_t crc32_bit(unsigned i, uint32_t rem)
{
return i == 0
? rem
: crc32_bit<Variant>(i - 1,
rem & shift<uint32_t>(1, Variant::reverse ? 0 : bit_sizeof<uint32_t>() - 1)
? shift(rem, Variant::reverse ? -1 : 1) ^ Variant::polynomial
: shift(rem, Variant::reverse ? -1 : 1));
}
template <typename Variant>
constexpr uint32_t crc32_byte(uint32_t rem, uint8_t byte)
{
return crc32_bit<Variant>(8, rem ^ shift<Variant::type>(byte, Variant::byte_shift));
}
int main(void) {
uint32_t rem = ~0;
for (int i = '0'; i <= '9'; i++) {
printf("%c\n", i);
rem = crc32_byte<0xEDB88320, true>(rem, i);
//printf("%08x\n", rem);
}
printf("%08x\n", ~rem);
/*for (int i = 0; i < 256; i++) {
rem = crc32_byte<0xEDB88320, true>(rem, i);
printf("%08x\n", rem);
}*/
}
Raw
crccalc.com.txt
https://crccalc.com/
Raw
helper.hpp
#ifndef DOXYGEN_SHOULD_SKIP_THIS
#ifndef CRC32_HELPER_HPP_08E038424EC66F1A702D50895BE77DAE35B1EC08
#define CRC32_HELPER_HPP_08E038424EC66F1A702D50895BE77DAE35B1EC08
#include <limits.h>
namespace crc32 {
namespace impl {
// Return the bit-width of a type.
template <typename Type>
constexpr unsigned bit_sizeof()
{ return sizeof(Type) * CHAR_BIT; }
// Return the sign of a value (1 for positives and 0, and -1 for negatives).
template <typename Type>
constexpr Type signof(Type value)
{ return value >= 0 ? 1 : -1; }
// Bit shift function. Allows positive (<<) and negative (>>) shifts,
// as well as zero shifts (NOP).
template <typename Type>
constexpr Type shift(Type value, int count)
{
return count == 0
? value
: count > 0
? value << static_cast<Type>(+count)
: value >> static_cast<Type>(-count);
}
// Creates an AND-mask, starting at given bit and measuring a given width.
template <typename Type>
constexpr Type and_mask(unsigned start, unsigned width)
{ return width == 0 ? 0 : shift(1, start) | and_mask<Type>(start, width - 1); }
// End recursive template-expansion of function select below.
template <typename Type>
static inline constexpr Type select(unsigned index)
{ return Type(); }
// Select one of the items passed to it.
// e.g. select(0, a, b, c) = a; select(1, a, b, c) = b; etc.
template <typename Type, typename... Params>
static inline constexpr Type select(unsigned index, Type value, Params... values)
{ return index == 0 ? value : select<Type>(index - 1, values...); }
// ***************************************************************************************** //
// BACKPORT OF C++14 STD::INDEX_SEQUENCE //
// ***************************************************************************************** //
// Under C++14, we could use std::index_sequence and std::make_index_sequence.
// cf. https://en.cppreference.com/w/cpp/utility/integer_sequence
template <unsigned... Is>
struct index_sequence { };
template <unsigned N, unsigned... Is>
struct make_index_sequence: make_index_sequence<N - 1, N - 1, Is...> { };
template <unsigned... Is>
struct make_index_sequence<0, Is...>: index_sequence<Is...> { };
}
}
#endif /* CRC32_HELPER_HPP_08E038424EC66F1A702D50895BE77DAE35B1EC08 */
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
Raw
lookup_table.hpp
#ifndef DOXYGEN_SHOULD_SKIP_THIS
#ifndef CRC32_MCU_LOOKUP_TABLE_HPP_A361AB2BCB119D5492F108CBC0D550A023E9E54E
#define CRC32_MCU_LOOKUP_TABLE_HPP_A361AB2BCB119D5492F108CBC0D550A023E9E54E
#include <stdint.h>
#include "helper.hpp"
namespace crc32 {
namespace impl {
struct lookup_table { uint32_t values[256]; };
template <typename Func, unsigned... Is>
constexpr lookup_table make_lookup_table(index_sequence<Is...>, Func func)
{ return {{ func(Is)... }}; }
template <typename Func>
constexpr lookup_table make_lookup_table(Func func)
{ return make_lookup_table(make_index_sequence<256>(), func); }
}
}
#endif /* CRC32_MCU_LOOKUP_TABLE_HPP_A361AB2BCB119D5492F108CBC0D550A023E9E54E */
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
Raw
nr
00000000
04c11db7
09823b6e
0d4326d9
130476dc
17c56b6b
1a864db2
1e475005
2608edb8
22c9f00f
2f8ad6d6
2b4bcb61
350c9b64
31cd86d3
3c8ea00a
384fbdbd
4c11db70
48d0c6c7
4593e01e
4152fda9
5f15adac
5bd4b01b
569796c2
52568b75
6a1936c8
6ed82b7f
639b0da6
675a1011
791d4014
7ddc5da3
709f7b7a
745e66cd
9823b6e0
9ce2ab57
91a18d8e
95609039
8b27c03c
8fe6dd8b
82a5fb52
8664e6e5
be2b5b58
baea46ef
b7a96036
b3687d81
ad2f2d84
a9ee3033
a4ad16ea
a06c0b5d
d4326d90
d0f37027
ddb056fe
d9714b49
c7361b4c
c3f706fb
ceb42022
ca753d95
f23a8028
f6fb9d9f
fbb8bb46
ff79a6f1
e13ef6f4
e5ffeb43
e8bccd9a
ec7dd02d
34867077
30476dc0
3d044b19
39c556ae
278206ab
23431b1c
2e003dc5
2ac12072
128e9dcf
164f8078
1b0ca6a1
1fcdbb16
018aeb13
054bf6a4
0808d07d
0cc9cdca
7897ab07
7c56b6b0
71159069
75d48dde
6b93dddb
6f52c06c
6211e6b5
66d0fb02
5e9f46bf
5a5e5b08
571d7dd1
53dc6066
4d9b3063
495a2dd4
44190b0d
40d816ba
aca5c697
a864db20
a527fdf9
a1e6e04e
bfa1b04b
bb60adfc
b6238b25
b2e29692
8aad2b2f
8e6c3698
832f1041
87ee0df6
99a95df3
9d684044
902b669d
94ea7b2a
e0b41de7
e4750050
e9362689
edf73b3e
f3b06b3b
f771768c
fa325055
fef34de2
c6bcf05f
c27dede8
cf3ecb31
cbffd686
d5b88683
d1799b34
dc3abded
d8fba05a
690ce0ee
6dcdfd59
608edb80
644fc637
7a089632
7ec98b85
738aad5c
774bb0eb
4f040d56
4bc510e1
46863638
42472b8f
5c007b8a
58c1663d
558240e4
51435d53
251d3b9e
21dc2629
2c9f00f0
285e1d47
36194d42
32d850f5
3f9b762c
3b5a6b9b
0315d626
07d4cb91
0a97ed48
0e56f0ff
1011a0fa
14d0bd4d
19939b94
1d528623
f12f560e
f5ee4bb9
f8ad6d60
fc6c70d7
e22b20d2
e6ea3d65
eba91bbc
ef68060b
d727bbb6
d3e6a601
dea580d8
da649d6f
c423cd6a
c0e2d0dd
cda1f604
c960ebb3
bd3e8d7e
b9ff90c9
b4bcb610
b07daba7
ae3afba2
aafbe615
a7b8c0cc
a379dd7b
9b3660c6
9ff77d71
92b45ba8
9675461f
8832161a
8cf30bad
81b02d74
857130c3
5d8a9099
594b8d2e
5408abf7
50c9b640
4e8ee645
4a4ffbf2
470cdd2b
43cdc09c
7b827d21
7f436096
7200464f
76c15bf8
68860bfd
6c47164a
61043093
65c52d24
119b4be9
155a565e
18197087
1cd86d30
029f3d35
065e2082
0b1d065b
0fdc1bec
3793a651
3352bbe6
3e119d3f
3ad08088
2497d08d
2056cd3a
2d15ebe3
29d4f654
c5a92679
c1683bce
cc2b1d17
c8ea00a0
d6ad50a5
d26c4d12
df2f6bcb
dbee767c
e3a1cbc1
e760d676
ea23f0af
eee2ed18
f0a5bd1d
f464a0aa
f9278673
fde69bc4
89b8fd09
8d79e0be
803ac667
84fbdbd0
9abc8bd5
9e7d9662
933eb0bb
97ffad0c
afb010b1
ab710d06
a6322bdf
a2f33668
bcb4666d
b8757bda
b5365d03
b1f740b4
00000000
77073096
ee0e612c
990951ba
076dc419
706af48f
e963a535
9e6495a3
0edb8832
79dcb8a4
e0d5e91e
97d2d988
09b64c2b
7eb17cbd
e7b82d07
90bf1d91
1db71064
6ab020f2
f3b97148
84be41de
1adad47d
6ddde4eb
f4d4b551
83d385c7
136c9856
646ba8c0
fd62f97a
8a65c9ec
14015c4f
63066cd9
fa0f3d63
8d080df5
3b6e20c8
4c69105e
d56041e4
a2677172
3c03e4d1
4b04d447
d20d85fd
a50ab56b
35b5a8fa
42b2986c
dbbbc9d6
acbcf940
32d86ce3
45df5c75
dcd60dcf
abd13d59
26d930ac
51de003a
c8d75180
bfd06116
21b4f4b5
56b3c423
cfba9599
b8bda50f
2802b89e
5f058808
c60cd9b2
b10be924
2f6f7c87
58684c11
c1611dab
b6662d3d
76dc4190
01db7106
98d220bc
efd5102a
71b18589
06b6b51f
9fbfe4a5
e8b8d433
7807c9a2
0f00f934
9609a88e
e10e9818
7f6a0dbb
086d3d2d
91646c97
e6635c01
6b6b51f4
1c6c6162
856530d8
f262004e
6c0695ed
1b01a57b
8208f4c1
f50fc457
65b0d9c6
12b7e950
8bbeb8ea
fcb9887c
62dd1ddf
15da2d49
8cd37cf3
fbd44c65
4db26158
3ab551ce
a3bc0074
d4bb30e2
4adfa541
3dd895d7
a4d1c46d
d3d6f4fb
4369e96a
346ed9fc
ad678846
da60b8d0
44042d73
33031de5
aa0a4c5f
dd0d7cc9
5005713c
270241aa
be0b1010
c90c2086
5768b525
206f85b3
b966d409
ce61e49f
5edef90e
29d9c998
b0d09822
c7d7a8b4
59b33d17
2eb40d81
b7bd5c3b
c0ba6cad
edb88320
9abfb3b6
03b6e20c
74b1d29a
ead54739
9dd277af
04db2615
73dc1683
e3630b12
94643b84
0d6d6a3e
7a6a5aa8
e40ecf0b
9309ff9d
0a00ae27
7d079eb1
f00f9344
8708a3d2
1e01f268
6906c2fe
f762575d
806567cb
196c3671
6e6b06e7
fed41b76
89d32be0
10da7a5a
67dd4acc
f9b9df6f
8ebeeff9
17b7be43
60b08ed5
d6d6a3e8
a1d1937e
38d8c2c4
4fdff252
d1bb67f1
a6bc5767
3fb506dd
48b2364b
d80d2bda
af0a1b4c
36034af6
41047a60
df60efc3
a867df55
316e8eef
4669be79
cb61b38c
bc66831a
256fd2a0
5268e236
cc0c7795
bb0b4703
220216b9
5505262f
c5ba3bbe
b2bd0b28
2bb45a92
5cb36a04
c2d7ffa7
b5d0cf31
2cd99e8b
5bdeae1d
9b64c2b0
ec63f226
756aa39c
026d930a
9c0906a9
eb0e363f
72076785
05005713
95bf4a82
e2b87a14
7bb12bae
0cb61b38
92d28e9b
e5d5be0d
7cdcefb7
0bdbdf21
86d3d2d4
f1d4e242
68ddb3f8
1fda836e
81be16cd
f6b9265b
6fb077e1
18b74777
88085ae6
ff0f6a70
66063bca
11010b5c
8f659eff
f862ae69
616bffd3
166ccf45
a00ae278
d70dd2ee
4e048354
3903b3c2
a7672661
d06016f7
4969474d
3e6e77db
aed16a4a
d9d65adc
40df0b66
37d83bf0
a9bcae53
debb9ec5
47b2cf7f
30b5ffe9
bdbdf21c
cabac28a
53b39330
24b4a3a6
bad03605
cdd70693
54de5729
23d967bf
b3667a2e
c4614ab8
5d681b02
2a6f2b94
b40bbe37
c30c8ea1
5a05df1b
2d02ef8d
Raw
reflect.hpp
#ifndef DOXYGEN_SHOULD_SKIP_THIS
#ifndef CRC32_MCU_REFLECT_HPP_CB5E2B215BCF4DFDF54BB109A712DF6395D316C6
#define CRC32_MCU_REFLECT_HPP_CB5E2B215BCF4DFDF54BB109A712DF6395D316C6
#include <stdint.h>
#include "helper.hpp"
namespace crc32 {
namespace impl {
// This implementation is ugly, I admit, but it works with C++11 single-statement
// constexpr functions, and produces consistently small code for many different
// architectures when using gcc.
// ***************************************************************************************** //
// REFLECT USING AND MASKS AND SHIFTS //
// ***************************************************************************************** //
template <typename Type>
static inline constexpr Type reflect_mask_helper_1(Type mask, Type shift, Type value)
{ return ((value & mask) >> shift) | ((value << shift) & mask); }
template <typename Type>
static inline constexpr Type reflect_mask_helper_0(unsigned i, Type value)
{
return i == 0
? value
: reflect_mask_helper_0(
i - 1,
reflect_mask_helper_1<Type>(
select(i - 1, 0xaaaaaaaaaaaaaaaa, 0xcccccccccccccccc, 0xf0f0f0f0f0f0f0f0,
0xff00ff00ff00ff00, 0xffff0000ffff0000, 0xffffffff00000000),
1 << (i - 1),
value));
}
template <typename Type>
static inline constexpr Type reflect_mask(Type value)
{ return reflect_mask_helper_0(__builtin_ctz(bit_sizeof<Type>()), value); }
// ***************************************************************************************** //
// REFLECT USING UNION TYPE //
// ***************************************************************************************** //
template <typename Type, typename PartType>
union reflect_parts_union
{
PartType parts[sizeof(Type) / sizeof(PartType)];
Type whole;
};
template <typename Type, typename PartType, unsigned... Is>
[[gnu::always_inline]]
constexpr reflect_parts_union<Type, PartType>
make_reflect_parts_union(index_sequence<Is...>, Type value)
{
return {
reflect_mask<PartType>(reflect_parts_union<Type, PartType>{
.whole = value
}.parts[sizeof(Type) / sizeof(PartType) - 1 - Is])...
};
}
template <typename Type, typename PartType>
static inline constexpr Type reflect_parts(Type value)
{
return make_reflect_parts_union<Type, PartType>(
make_index_sequence<sizeof(Type) / sizeof(PartType)>(), value
).whole;
}
// #if defined(__AVR__)
// union reflect_u16_union { uint8_t u8[2]; uint16_t u16; };
// static inline constexpr uint16_t reflect_u16(uint16_t value)
// {
// return reflect_u16_union{ .u8 = {
// reflect_u8(reflect_u16_union{ .u16 = value }.u8[1]),
// reflect_u8(reflect_u16_union{ .u16 = value }.u8[0])
// } }.u16;
// }
// #else
// static inline constexpr uint16_t reflect_u16(uint16_t value)
// {
// return reflect_helper<uint16_t>(0xaaaa, 1,
// reflect_helper<uint16_t>(0xcccc, 2,
// reflect_helper<uint16_t>(0xf0f0, 4,
// reflect_helper<uint16_t>(0xff00, 8, value))));
// }
// #endif
// #if defined(__AVR__)
// union reflect_u32_union { uint8_t u8[4]; uint32_t u32; };
// static inline constexpr uint32_t reflect_u32(uint32_t value)
// {
// return reflect_u32_union{ .u8 = {
// reflect_u8(reflect_u32_union{ .u32 = value }.u8[3]),
// reflect_u8(reflect_u32_union{ .u32 = value }.u8[2]),
// reflect_u8(reflect_u32_union{ .u32 = value }.u8[1]),
// reflect_u8(reflect_u32_union{ .u32 = value }.u8[0])
// } }.u32;
// }
// #elif defined(__MSP430__)
// union reflect_u32_union { uint16_t u16[2]; uint32_t u32; };
// static inline constexpr uint32_t reflect_u32(uint32_t value)
// {
// return reflect_u32_union{ .u16 = {
// reflect_u16(reflect_u32_union{ .u32 = value }.u16[1]),
// reflect_u16(reflect_u32_union{ .u32 = value }.u16[0])
// } }.u32;
// }
// #else
// static inline constexpr uint32_t reflect_u32(uint32_t value)
// {
// return reflect_helper<uint32_t>(0xaaaaaaaa, 1,
// reflect_helper<uint32_t>(0xcccccccc, 2,
// reflect_helper<uint32_t>(0xf0f0f0f0, 4,
// reflect_helper<uint32_t>(0xff00ff00, 8,
// reflect_helper<uint32_t>(0xffff0000, 16, value)))));
// }
// #endif
// #if defined(__AVR__)
// union reflect_u64_union { uint8_t u8[8]; uint64_t u64; };
// static inline constexpr uint64_t reflect_u64(uint64_t value)
// {
// return reflect_u64_union{ .u8 = {
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[7]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[6]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[5]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[4]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[3]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[2]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[1]),
// reflect_u8(reflect_u64_union{ .u64 = value }.u8[0])
// } }.u64;
// }
// #elif (defined(__arm__) && !defined(__aarch64__)) || defined(__i386__) \
// || (defined(__mips) && !defined(__mips64)) || defined(__MSP430__) \
// || (defined(__PPC__) && !defined(__PPC64__)) || defined(__riscv_xlen) \
// || defined(__xtensa__)
// union reflect_u64_union { uint32_t u32[2]; uint64_t u64; };
// static inline constexpr uint64_t reflect_u64(uint64_t value)
// {
// return reflect_u64_union{ .u32 = {
// reflect_u32(reflect_u64_union{ .u64 = value }.u32[1]),
// reflect_u32(reflect_u64_union{ .u64 = value }.u32[0])
// } }.u64;
// }
// #else
// static inline constexpr uint64_t reflect_u64(uint64_t value)
// {
// return reflect_helper<uint64_t>(0xaaaaaaaaaaaaaaaa, 1,
// reflect_helper<uint64_t>(0xcccccccccccccccc, 2,
// reflect_helper<uint64_t>(0xf0f0f0f0f0f0f0f0, 4,
// reflect_helper<uint64_t>(0xff00ff00ff00ff00, 8,
// reflect_helper<uint64_t>(0xffff0000ffff0000, 16,
// reflect_helper<uint64_t>(0xffffffff00000000, 32, value))))));
// }
// #endif
}
}
#endif /* CRC32_MCU_REFLECT_HPP_CB5E2B215BCF4DFDF54BB109A712DF6395D316C6 */
#endif /* DOXYGEN_SHOULD_SKIP_THIS */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment