08b5643372ec3e8a73d13665544e91229cc4ce5a
[folly.git] / folly / Checksum.cpp
1 /*
2  * Copyright 2014 Facebook, Inc.
3  *
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
7  *
8  *   http://www.apache.org/licenses/LICENSE-2.0
9  *
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.
15  */
16
17 #include <folly/Checksum.h>
18 #include <algorithm>
19 #include <stdexcept>
20 #include <boost/crc.hpp>
21 #include <folly/CpuId.h>
22
23 namespace folly {
24
25 namespace detail {
26
27 #ifndef __has_builtin
28   /* nolint */
29   #define __has_builtin(x) 0
30 #endif
31
32 #if (__has_builtin(__builtin_ia32_crc32qi) && \
33      __has_builtin(__builtin_ia32_crc32di)) || \
34     (FOLLY_X64 && defined(__GNUC__) && defined(__GNUC_MINOR__) && \
35      (((__GNUC__ * 100) + __GNUC_MINOR__) >= 407))
36
37 // Fast SIMD implementation of CRC-32C for x86 with SSE 4.2
38 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
39     uint32_t startingChecksum) {
40   uint32_t sum = startingChecksum;
41   size_t offset = 0;
42
43   // Process bytes one at a time until we reach an 8-byte boundary and can
44   // start doing aligned 64-bit reads.
45   static uintptr_t ALIGN_MASK = sizeof(uint64_t) - 1;
46   size_t mask = (size_t)((uintptr_t)data & ALIGN_MASK);
47   if (mask != 0) {
48     size_t limit = std::min(nbytes, sizeof(uint64_t) - mask);
49     while (offset < limit) {
50       sum = (uint32_t)__builtin_ia32_crc32qi(sum, data[offset]);
51       offset++;
52     }
53   }
54
55   // Process 8 bytes at a time until we have fewer than 8 bytes left.
56   while (offset + sizeof(uint64_t) <= nbytes) {
57     const uint64_t* src = (const uint64_t*)(data + offset);
58     sum = __builtin_ia32_crc32di(sum, *src);
59     offset += sizeof(uint64_t);
60   }
61
62   // Process any bytes remaining after the last aligned 8-byte block.
63   while (offset < nbytes) {
64     sum = (uint32_t)__builtin_ia32_crc32qi(sum, data[offset]);
65     offset++;
66   }
67   return sum;
68 }
69
70 bool crc32c_hw_supported() {
71   static folly::CpuId id;
72   return id.sse42();
73 }
74
75 #else
76
77 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
78     uint32_t startingChecksum) {
79   throw std::runtime_error("crc32_hw is not implemented on this platform");
80 }
81
82 bool crc32c_hw_supported() {
83   return false;
84 }
85
86 #endif
87
88 uint32_t crc32c_sw(const uint8_t *data, size_t nbytes,
89     uint32_t startingChecksum) {
90
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);
105
106   static const uint32_t CRC32C_POLYNOMIAL = 0x1EDC6F41;
107   boost::crc_optimal<32, CRC32C_POLYNOMIAL, ~0U, 0, true, true> sum(
108       startingChecksum);
109   sum.process_bytes(data, nbytes);
110   return sum.checksum();
111 }
112
113 } // folly::detail
114
115 uint32_t crc32c(const uint8_t *data, size_t nbytes,
116     uint32_t startingChecksum) {
117   if (detail::crc32c_hw_supported()) {
118     return detail::crc32c_hw(data, nbytes, startingChecksum);
119   } else {
120     return detail::crc32c_sw(data, nbytes, startingChecksum);
121   }
122 }
123
124 } // folly