2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 #include <folly/Checksum.h>
18 #include <boost/crc.hpp>
19 #include <folly/CpuId.h>
20 #include <folly/detail/ChecksumDetail.h>
24 #if FOLLY_SSE_PREREQ(4, 2)
25 #include <nmmintrin.h>
33 crc32c_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum);
34 #if FOLLY_SSE_PREREQ(4, 2)
37 crc32_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum);
39 // Fast SIMD implementation of CRC-32 for x86 with pclmul
41 crc32_hw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
42 uint32_t sum = startingChecksum;
45 // Process unaligned bytes
46 if ((uintptr_t)data & 15) {
47 size_t limit = std::min(nbytes, -(uintptr_t)data & 15);
48 sum = crc32_sw(data, limit, sum);
54 sum = crc32_hw_aligned(sum, (const __m128i*)(data + offset), nbytes / 16);
55 offset += nbytes & ~15;
59 // Remaining unaligned bytes
60 return crc32_sw(data + offset, nbytes, sum);
63 bool crc32c_hw_supported() {
64 static folly::CpuId id;
68 bool crc32_hw_supported() {
69 static folly::CpuId id;
75 uint32_t crc32_hw(const uint8_t *data, size_t nbytes,
76 uint32_t startingChecksum) {
77 throw std::runtime_error("crc32_hw is not implemented on this platform");
80 bool crc32c_hw_supported() {
84 bool crc32_hw_supported() {
89 template <uint32_t CRC_POLYNOMIAL>
90 uint32_t crc_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
91 // Reverse the bits in the starting checksum so they'll be in the
92 // right internal format for Boost's CRC engine.
93 // O(1)-time, branchless bit reversal algorithm from
94 // http://graphics.stanford.edu/~seander/bithacks.html
95 startingChecksum = ((startingChecksum >> 1) & 0x55555555) |
96 ((startingChecksum & 0x55555555) << 1);
97 startingChecksum = ((startingChecksum >> 2) & 0x33333333) |
98 ((startingChecksum & 0x33333333) << 2);
99 startingChecksum = ((startingChecksum >> 4) & 0x0f0f0f0f) |
100 ((startingChecksum & 0x0f0f0f0f) << 4);
101 startingChecksum = ((startingChecksum >> 8) & 0x00ff00ff) |
102 ((startingChecksum & 0x00ff00ff) << 8);
103 startingChecksum = (startingChecksum >> 16) |
104 (startingChecksum << 16);
106 boost::crc_optimal<32, CRC_POLYNOMIAL, ~0U, 0, true, true> sum(
108 sum.process_bytes(data, nbytes);
109 return sum.checksum();
113 crc32c_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
114 constexpr uint32_t CRC32C_POLYNOMIAL = 0x1EDC6F41;
115 return crc_sw<CRC32C_POLYNOMIAL>(data, nbytes, startingChecksum);
119 crc32_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
120 constexpr uint32_t CRC32_POLYNOMIAL = 0x04C11DB7;
121 return crc_sw<CRC32_POLYNOMIAL>(data, nbytes, startingChecksum);
124 } // namespace detail
126 uint32_t crc32c(const uint8_t *data, size_t nbytes,
127 uint32_t startingChecksum) {
128 if (detail::crc32c_hw_supported()) {
129 return detail::crc32c_hw(data, nbytes, startingChecksum);
131 return detail::crc32c_sw(data, nbytes, startingChecksum);
135 uint32_t crc32(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
136 if (detail::crc32_hw_supported()) {
137 return detail::crc32_hw(data, nbytes, startingChecksum);
139 return detail::crc32_sw(data, nbytes, startingChecksum);
144 crc32_type(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
145 return ~crc32(data, nbytes, startingChecksum);