2 * Copyright 2016 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>
20 #include <boost/crc.hpp>
21 #include <folly/CpuId.h>
23 #if FOLLY_X64 && (__SSE4_2__ || defined(__clang__) || __GNUC_PREREQ(4, 9))
24 #include <nmmintrin.h>
31 #if FOLLY_X64 && (__SSE4_2__ || defined(__clang__) || __GNUC_PREREQ(4, 9))
33 // Fast SIMD implementation of CRC-32C for x86 with SSE 4.2
34 FOLLY_TARGET_ATTRIBUTE("sse4.2")
35 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
36 uint32_t startingChecksum) {
37 uint32_t sum = startingChecksum;
40 // Process bytes one at a time until we reach an 8-byte boundary and can
41 // start doing aligned 64-bit reads.
42 static uintptr_t ALIGN_MASK = sizeof(uint64_t) - 1;
43 size_t mask = (size_t)((uintptr_t)data & ALIGN_MASK);
45 size_t limit = std::min(nbytes, sizeof(uint64_t) - mask);
46 while (offset < limit) {
47 sum = (uint32_t)_mm_crc32_u8(sum, data[offset]);
52 // Process 8 bytes at a time until we have fewer than 8 bytes left.
53 while (offset + sizeof(uint64_t) <= nbytes) {
54 const uint64_t* src = (const uint64_t*)(data + offset);
55 sum = _mm_crc32_u64(sum, *src);
56 offset += sizeof(uint64_t);
59 // Process any bytes remaining after the last aligned 8-byte block.
60 while (offset < nbytes) {
61 sum = (uint32_t)_mm_crc32_u8(sum, data[offset]);
67 bool crc32c_hw_supported() {
68 static folly::CpuId id;
74 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
75 uint32_t startingChecksum) {
76 throw std::runtime_error("crc32_hw is not implemented on this platform");
79 bool crc32c_hw_supported() {
85 uint32_t crc32c_sw(const uint8_t *data, size_t nbytes,
86 uint32_t startingChecksum) {
88 // Reverse the bits in the starting checksum so they'll be in the
89 // right internal format for Boost's CRC engine.
90 // O(1)-time, branchless bit reversal algorithm from
91 // http://graphics.stanford.edu/~seander/bithacks.html
92 startingChecksum = ((startingChecksum >> 1) & 0x55555555) |
93 ((startingChecksum & 0x55555555) << 1);
94 startingChecksum = ((startingChecksum >> 2) & 0x33333333) |
95 ((startingChecksum & 0x33333333) << 2);
96 startingChecksum = ((startingChecksum >> 4) & 0x0f0f0f0f) |
97 ((startingChecksum & 0x0f0f0f0f) << 4);
98 startingChecksum = ((startingChecksum >> 8) & 0x00ff00ff) |
99 ((startingChecksum & 0x00ff00ff) << 8);
100 startingChecksum = (startingChecksum >> 16) |
101 (startingChecksum << 16);
103 static const uint32_t CRC32C_POLYNOMIAL = 0x1EDC6F41;
104 boost::crc_optimal<32, CRC32C_POLYNOMIAL, ~0U, 0, true, true> sum(
106 sum.process_bytes(data, nbytes);
107 return sum.checksum();
112 uint32_t crc32c(const uint8_t *data, size_t nbytes,
113 uint32_t startingChecksum) {
114 if (detail::crc32c_hw_supported()) {
115 return detail::crc32c_hw(data, nbytes, startingChecksum);
117 return detail::crc32c_sw(data, nbytes, startingChecksum);