folly/hash/Checksum.cpp

   1 /*
   2  * Copyright 2013-present 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/hash/Checksum.h>
  18 #include <boost/crc.hpp>
  19 #include <folly/CpuId.h>
  20 #include <folly/hash/detail/ChecksumDetail.h>
  21 #include <algorithm>
  22 #include <stdexcept>
  23
  24 #if FOLLY_SSE_PREREQ(4, 2)
  25 #include <nmmintrin.h>
  26 #endif
  27
  28 namespace folly {
  29
  30 namespace detail {
  31
  32 uint32_t
  33 crc32c_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum);
  34 #if FOLLY_SSE_PREREQ(4, 2)
  35
  36 uint32_t
  37 crc32_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum);
  38
  39 // Fast SIMD implementation of CRC-32 for x86 with pclmul
  40 uint32_t
  41 crc32_hw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
  42   uint32_t sum = startingChecksum;
  43   size_t offset = 0;
  44
  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);
  49     offset += limit;
  50     nbytes -= limit;
  51   }
  52
  53   if (nbytes >= 16) {
  54     sum = crc32_hw_aligned(sum, (const __m128i*)(data + offset), nbytes / 16);
  55     offset += nbytes & ~15;
  56     nbytes &= 15;
  57   }
  58
  59   // Remaining unaligned bytes
  60   return crc32_sw(data + offset, nbytes, sum);
  61 }
  62
  63 bool crc32c_hw_supported() {
  64   static folly::CpuId id;
  65   return id.sse42();
  66 }
  67
  68 bool crc32_hw_supported() {
  69   static folly::CpuId id;
  70   return id.sse42();
  71 }
  72
  73 #else
  74
  75 uint32_t crc32_hw(
  76     const uint8_t* /* data */,
  77     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 bool crc32_hw_supported() {
  87   return false;
  88 }
  89 #endif
  90
  91 template <uint32_t CRC_POLYNOMIAL>
  92 uint32_t crc_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
  93   // Reverse the bits in the starting checksum so they'll be in the
  94   // right internal format for Boost's CRC engine.
  95   //     O(1)-time, branchless bit reversal algorithm from
  96   //     http://graphics.stanford.edu/~seander/bithacks.html
  97   startingChecksum = ((startingChecksum >> 1) & 0x55555555) |
  98       ((startingChecksum & 0x55555555) << 1);
  99   startingChecksum = ((startingChecksum >> 2) & 0x33333333) |
 100       ((startingChecksum & 0x33333333) << 2);
 101   startingChecksum = ((startingChecksum >> 4) & 0x0f0f0f0f) |
 102       ((startingChecksum & 0x0f0f0f0f) << 4);
 103   startingChecksum = ((startingChecksum >> 8) & 0x00ff00ff) |
 104       ((startingChecksum & 0x00ff00ff) << 8);
 105   startingChecksum = (startingChecksum >> 16) |
 106       (startingChecksum << 16);
 107
 108   boost::crc_optimal<32, CRC_POLYNOMIAL, ~0U, 0, true, true> sum(
 109       startingChecksum);
 110   sum.process_bytes(data, nbytes);
 111   return sum.checksum();
 112 }
 113
 114 uint32_t
 115 crc32c_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
 116   constexpr uint32_t CRC32C_POLYNOMIAL = 0x1EDC6F41;
 117   return crc_sw<CRC32C_POLYNOMIAL>(data, nbytes, startingChecksum);
 118 }
 119
 120 uint32_t
 121 crc32_sw(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
 122   constexpr uint32_t CRC32_POLYNOMIAL = 0x04C11DB7;
 123   return crc_sw<CRC32_POLYNOMIAL>(data, nbytes, startingChecksum);
 124 }
 125
 126 } // namespace detail
 127
 128 uint32_t crc32c(const uint8_t *data, size_t nbytes,
 129     uint32_t startingChecksum) {
 130   if (detail::crc32c_hw_supported()) {
 131     return detail::crc32c_hw(data, nbytes, startingChecksum);
 132   } else {
 133     return detail::crc32c_sw(data, nbytes, startingChecksum);
 134   }
 135 }
 136
 137 uint32_t crc32(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
 138   if (detail::crc32_hw_supported()) {
 139     return detail::crc32_hw(data, nbytes, startingChecksum);
 140   } else {
 141     return detail::crc32_sw(data, nbytes, startingChecksum);
 142   }
 143 }
 144
 145 uint32_t
 146 crc32_type(const uint8_t* data, size_t nbytes, uint32_t startingChecksum) {
 147   return ~crc32(data, nbytes, startingChecksum);
 148 }
 149
 150 } // namespace folly