folly/Checksum.cpp

   1 /*
   2  * Copyright 2015 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 __SSE4_2__ && \
  33     ((__has_builtin(__builtin_ia32_crc32qi) && \
  34      __has_builtin(__builtin_ia32_crc32di)) || \
  35     (FOLLY_X64 && defined(__GNUC__) && defined(__GNUC_MINOR__) && \
  36      (((__GNUC__ * 100) + __GNUC_MINOR__) >= 407)))
  37
  38 // Fast SIMD implementation of CRC-32C for x86 with SSE 4.2
  39 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
  40     uint32_t startingChecksum) {
  41   uint32_t sum = startingChecksum;
  42   size_t offset = 0;
  43
  44   // Process bytes one at a time until we reach an 8-byte boundary and can
  45   // start doing aligned 64-bit reads.
  46   static uintptr_t ALIGN_MASK = sizeof(uint64_t) - 1;
  47   size_t mask = (size_t)((uintptr_t)data & ALIGN_MASK);
  48   if (mask != 0) {
  49     size_t limit = std::min(nbytes, sizeof(uint64_t) - mask);
  50     while (offset < limit) {
  51       sum = (uint32_t)__builtin_ia32_crc32qi(sum, data[offset]);
  52       offset++;
  53     }
  54   }
  55
  56   // Process 8 bytes at a time until we have fewer than 8 bytes left.
  57   while (offset + sizeof(uint64_t) <= nbytes) {
  58     const uint64_t* src = (const uint64_t*)(data + offset);
  59     sum = __builtin_ia32_crc32di(sum, *src);
  60     offset += sizeof(uint64_t);
  61   }
  62
  63   // Process any bytes remaining after the last aligned 8-byte block.
  64   while (offset < nbytes) {
  65     sum = (uint32_t)__builtin_ia32_crc32qi(sum, data[offset]);
  66     offset++;
  67   }
  68   return sum;
  69 }
  70
  71 bool crc32c_hw_supported() {
  72   static folly::CpuId id;
  73   return id.sse42();
  74 }
  75
  76 #else
  77
  78 uint32_t crc32c_hw(const uint8_t *data, size_t nbytes,
  79     uint32_t startingChecksum) {
  80   throw std::runtime_error("crc32_hw is not implemented on this platform");
  81 }
  82
  83 bool crc32c_hw_supported() {
  84   return false;
  85 }
  86
  87 #endif
  88
  89 uint32_t crc32c_sw(const uint8_t *data, size_t nbytes,
  90     uint32_t startingChecksum) {
  91
  92   // Reverse the bits in the starting checksum so they'll be in the
  93   // right internal format for Boost's CRC engine.
  94   //     O(1)-time, branchless bit reversal algorithm from
  95   //     http://graphics.stanford.edu/~seander/bithacks.html
  96   startingChecksum = ((startingChecksum >> 1) & 0x55555555) |
  97       ((startingChecksum & 0x55555555) << 1);
  98   startingChecksum = ((startingChecksum >> 2) & 0x33333333) |
  99       ((startingChecksum & 0x33333333) << 2);
 100   startingChecksum = ((startingChecksum >> 4) & 0x0f0f0f0f) |
 101       ((startingChecksum & 0x0f0f0f0f) << 4);
 102   startingChecksum = ((startingChecksum >> 8) & 0x00ff00ff) |
 103       ((startingChecksum & 0x00ff00ff) << 8);
 104   startingChecksum = (startingChecksum >> 16) |
 105       (startingChecksum << 16);
 106
 107   static const uint32_t CRC32C_POLYNOMIAL = 0x1EDC6F41;
 108   boost::crc_optimal<32, CRC32C_POLYNOMIAL, ~0U, 0, true, true> sum(
 109       startingChecksum);
 110   sum.process_bytes(data, nbytes);
 111   return sum.checksum();
 112 }
 113
 114 } // folly::detail
 115
 116 uint32_t crc32c(const uint8_t *data, size_t nbytes,
 117     uint32_t startingChecksum) {
 118   if (detail::crc32c_hw_supported()) {
 119     return detail::crc32c_hw(data, nbytes, startingChecksum);
 120   } else {
 121     return detail::crc32c_sw(data, nbytes, startingChecksum);
 122   }
 123 }
 124
 125 } // folly