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