1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include "pw_checksum/crc32.h"
16
17 #include <array>
18
19 namespace pw::checksum {
20 namespace {
21
22 // Calculates the partial CRC32 of the low order kBits of value using
23 // the reversed polynomial kPolynomial. This is a building block for
24 // both implementing a tableless CRC32 implementation as well as generating
25 // look up tables for tables based implementations.
26 //
27 // Information on CRC32 can be found at:
28 // https://en.wikipedia.org/wiki/Cyclic_redundancy_check
29 template <std::size_t kBits, uint32_t kPolynomial>
Crc32ProcessDataChunk(uint32_t value)30 constexpr uint32_t Crc32ProcessDataChunk(uint32_t value) {
31 for (uint32_t j = 0; j < kBits; j++) {
32 value = (value >> 1u) ^
33 (static_cast<uint32_t>(-static_cast<int32_t>(value & 1u)) &
34 kPolynomial);
35 }
36 return value;
37 }
38
39 // Generates a lookup table for a table based CRC32 implementation.
40 // The table pre-computes the CRC for every value representable by
41 // kBits of data. kPolynomial is used as the reversed polynomial
42 // for the computation. The returned table will have 2^kBits entries.
43 template <std::size_t kBits, uint32_t kPolynomial>
GenerateCrc32Table()44 constexpr std::array<uint32_t, (1 << kBits)> GenerateCrc32Table() {
45 std::array<uint32_t, (1 << kBits)> table{};
46 for (uint32_t i = 0; i < (1 << kBits); i++) {
47 table[i] = Crc32ProcessDataChunk<kBits, kPolynomial>(i);
48 }
49 return table;
50 }
51
52 // Reversed polynomial for the commonly used CRC32 variant. See:
53 // https://en.wikipedia.org/wiki/Cyclic_redundancy_check#Polynomial_representations_of_cyclic_redundancy_checks
54 constexpr uint32_t kCrc32Polynomial = 0xEDB88320;
55
56 } // namespace
57
_pw_checksum_InternalCrc32EightBit(const void * data,size_t size_bytes,uint32_t state)58 extern "C" uint32_t _pw_checksum_InternalCrc32EightBit(const void* data,
59 size_t size_bytes,
60 uint32_t state) {
61 static constexpr std::array<uint32_t, 256> kCrc32Table =
62 GenerateCrc32Table<8, kCrc32Polynomial>();
63 const uint8_t* data_bytes = static_cast<const uint8_t*>(data);
64
65 for (size_t i = 0; i < size_bytes; ++i) {
66 state = kCrc32Table[(state ^ data_bytes[i]) & 0xFFu] ^ (state >> 8);
67 }
68
69 return state;
70 }
71
_pw_checksum_InternalCrc32FourBit(const void * data,size_t size_bytes,uint32_t state)72 extern "C" uint32_t _pw_checksum_InternalCrc32FourBit(const void* data,
73 size_t size_bytes,
74 uint32_t state) {
75 static constexpr std::array<uint32_t, 16> kCrc32Table =
76 GenerateCrc32Table<4, kCrc32Polynomial>();
77 const uint8_t* data_bytes = static_cast<const uint8_t*>(data);
78
79 for (size_t i = 0; i < size_bytes; ++i) {
80 state ^= data_bytes[i];
81 state = kCrc32Table[state & 0x0f] ^ (state >> 4);
82 state = kCrc32Table[state & 0x0f] ^ (state >> 4);
83 }
84
85 return state;
86 }
87
_pw_checksum_InternalCrc32OneBit(const void * data,size_t size_bytes,uint32_t state)88 extern "C" uint32_t _pw_checksum_InternalCrc32OneBit(const void* data,
89 size_t size_bytes,
90 uint32_t state) {
91 const uint8_t* data_bytes = static_cast<const uint8_t*>(data);
92
93 for (size_t i = 0; i < size_bytes; ++i) {
94 state = Crc32ProcessDataChunk<8, kCrc32Polynomial>(state ^ data_bytes[i]);
95 }
96
97 return state;
98 }
99
100 } // namespace pw::checksum
101