folly/detail/Crc32cDetail.cpp

   1 /*
   2  * Copyright 2016 Ferry Toth, Exalon Delft BV, The Netherlands
   3  *  This software is provided 'as-is', without any express or implied
   4  * warranty.  In no event will the author be held liable for any damages
   5  * arising from the use of this software.
   6  *  Permission is granted to anyone to use this software for any purpose,
   7  * including commercial applications, and to alter it and redistribute it
   8  * freely, subject to the following restrictions:
   9  *  1. The origin of this software must not be misrepresented; you must not
  10  *   claim that you wrote the original software. If you use this software
  11  *   in a product, an acknowledgment in the product documentation would be
  12  *   appreciated but is not required.
  13  * 2. Altered source versions must be plainly marked as such, and must not be
  14  *   misrepresented as being the original software.
  15  * 3. This notice may not be removed or altered from any source distribution.
  16  *  Ferry Toth
  17  * ftoth@exalondelft.nl
  18  *
  19  * https://github.com/htot/crc32c
  20  *
  21  * Modified by Facebook
  22  *
  23  * Original intel whitepaper:
  24  * "Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction"
  25  * https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf
  26  *
  27  * 32-bit support dropped
  28  * use intrinsics instead of inline asm
  29  * other code cleanup
  30  */
  31
  32 #include <stdexcept>
  33
  34 #include <folly/detail/ChecksumDetail.h>
  35
  36 #include <folly/CppAttributes.h>
  37
  38 #include <boost/preprocessor/arithmetic/add.hpp>
  39 #include <boost/preprocessor/arithmetic/sub.hpp>
  40 #include <boost/preprocessor/repetition/repeat_from_to.hpp>
  41
  42 namespace folly {
  43 namespace detail {
  44
  45 #if FOLLY_SSE_PREREQ(4, 2)
  46
  47 namespace crc32_detail {
  48
  49 #define CRCtriplet(crc, buf, offset)                  \
  50   crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
  51   crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset)); \
  52   crc##2 = _mm_crc32_u64(crc##2, *(buf##2 + offset)); \
  53   FOLLY_FALLTHROUGH;
  54
  55 #define CRCduplet(crc, buf, offset)                   \
  56   crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
  57   crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset));
  58
  59 #define CRCsinglet(crc, buf, offset)                    \
  60   crc = _mm_crc32_u64(crc, *(uint64_t*)(buf + offset)); \
  61   FOLLY_FALLTHROUGH;
  62
  63 #define CASEREPEAT_TRIPLET(unused, count, total)    \
  64   case BOOST_PP_ADD(1, BOOST_PP_SUB(total, count)): \
  65     CRCtriplet(crc, next, -BOOST_PP_ADD(1, BOOST_PP_SUB(total, count)));
  66
  67 #define CASEREPEAT_SINGLET(unused, count, total) \
  68   case BOOST_PP_SUB(total, count):               \
  69     CRCsinglet(crc0, next, -BOOST_PP_SUB(total, count) * 8);
  70
  71 // Numbers taken directly from intel whitepaper.
  72 const __m128i clmul_constants[] = {
  73     {0x14cd00bd6, 0x105ec76f0}, {0x0ba4fc28e, 0x14cd00bd6},
  74     {0x1d82c63da, 0x0f20c0dfe}, {0x09e4addf8, 0x0ba4fc28e},
  75     {0x039d3b296, 0x1384aa63a}, {0x102f9b8a2, 0x1d82c63da},
  76     {0x14237f5e6, 0x01c291d04}, {0x00d3b6092, 0x09e4addf8},
  77     {0x0c96cfdc0, 0x0740eef02}, {0x18266e456, 0x039d3b296},
  78     {0x0daece73e, 0x0083a6eec}, {0x0ab7aff2a, 0x102f9b8a2},
  79     {0x1248ea574, 0x1c1733996}, {0x083348832, 0x14237f5e6},
  80     {0x12c743124, 0x02ad91c30}, {0x0b9e02b86, 0x00d3b6092},
  81     {0x018b33a4e, 0x06992cea2}, {0x1b331e26a, 0x0c96cfdc0},
  82     {0x17d35ba46, 0x07e908048}, {0x1bf2e8b8a, 0x18266e456},
  83     {0x1a3e0968a, 0x11ed1f9d8}, {0x0ce7f39f4, 0x0daece73e},
  84     {0x061d82e56, 0x0f1d0f55e}, {0x0d270f1a2, 0x0ab7aff2a},
  85     {0x1c3f5f66c, 0x0a87ab8a8}, {0x12ed0daac, 0x1248ea574},
  86     {0x065863b64, 0x08462d800}, {0x11eef4f8e, 0x083348832},
  87     {0x1ee54f54c, 0x071d111a8}, {0x0b3e32c28, 0x12c743124},
  88     {0x0064f7f26, 0x0ffd852c6}, {0x0dd7e3b0c, 0x0b9e02b86},
  89     {0x0f285651c, 0x0dcb17aa4}, {0x010746f3c, 0x018b33a4e},
  90     {0x1c24afea4, 0x0f37c5aee}, {0x0271d9844, 0x1b331e26a},
  91     {0x08e766a0c, 0x06051d5a2}, {0x093a5f730, 0x17d35ba46},
  92     {0x06cb08e5c, 0x11d5ca20e}, {0x06b749fb2, 0x1bf2e8b8a},
  93     {0x1167f94f2, 0x021f3d99c}, {0x0cec3662e, 0x1a3e0968a},
  94     {0x19329634a, 0x08f158014}, {0x0e6fc4e6a, 0x0ce7f39f4},
  95     {0x08227bb8a, 0x1a5e82106}, {0x0b0cd4768, 0x061d82e56},
  96     {0x13c2b89c4, 0x188815ab2}, {0x0d7a4825c, 0x0d270f1a2},
  97     {0x10f5ff2ba, 0x105405f3e}, {0x00167d312, 0x1c3f5f66c},
  98     {0x0f6076544, 0x0e9adf796}, {0x026f6a60a, 0x12ed0daac},
  99     {0x1a2adb74e, 0x096638b34}, {0x19d34af3a, 0x065863b64},
 100     {0x049c3cc9c, 0x1e50585a0}, {0x068bce87a, 0x11eef4f8e},
 101     {0x1524fa6c6, 0x19f1c69dc}, {0x16cba8aca, 0x1ee54f54c},
 102     {0x042d98888, 0x12913343e}, {0x1329d9f7e, 0x0b3e32c28},
 103     {0x1b1c69528, 0x088f25a3a}, {0x02178513a, 0x0064f7f26},
 104     {0x0e0ac139e, 0x04e36f0b0}, {0x0170076fa, 0x0dd7e3b0c},
 105     {0x141a1a2e2, 0x0bd6f81f8}, {0x16ad828b4, 0x0f285651c},
 106     {0x041d17b64, 0x19425cbba}, {0x1fae1cc66, 0x010746f3c},
 107     {0x1a75b4b00, 0x18db37e8a}, {0x0f872e54c, 0x1c24afea4},
 108     {0x01e41e9fc, 0x04c144932}, {0x086d8e4d2, 0x0271d9844},
 109     {0x160f7af7a, 0x052148f02}, {0x05bb8f1bc, 0x08e766a0c},
 110     {0x0a90fd27a, 0x0a3c6f37a}, {0x0b3af077a, 0x093a5f730},
 111     {0x04984d782, 0x1d22c238e}, {0x0ca6ef3ac, 0x06cb08e5c},
 112     {0x0234e0b26, 0x063ded06a}, {0x1d88abd4a, 0x06b749fb2},
 113     {0x04597456a, 0x04d56973c}, {0x0e9e28eb4, 0x1167f94f2},
 114     {0x07b3ff57a, 0x19385bf2e}, {0x0c9c8b782, 0x0cec3662e},
 115     {0x13a9cba9e, 0x0e417f38a}, {0x093e106a4, 0x19329634a},
 116     {0x167001a9c, 0x14e727980}, {0x1ddffc5d4, 0x0e6fc4e6a},
 117     {0x00df04680, 0x0d104b8fc}, {0x02342001e, 0x08227bb8a},
 118     {0x00a2a8d7e, 0x05b397730}, {0x168763fa6, 0x0b0cd4768},
 119     {0x1ed5a407a, 0x0e78eb416}, {0x0d2c3ed1a, 0x13c2b89c4},
 120     {0x0995a5724, 0x1641378f0}, {0x19b1afbc4, 0x0d7a4825c},
 121     {0x109ffedc0, 0x08d96551c}, {0x0f2271e60, 0x10f5ff2ba},
 122     {0x00b0bf8ca, 0x00bf80dd2}, {0x123888b7a, 0x00167d312},
 123     {0x1e888f7dc, 0x18dcddd1c}, {0x002ee03b2, 0x0f6076544},
 124     {0x183e8d8fe, 0x06a45d2b2}, {0x133d7a042, 0x026f6a60a},
 125     {0x116b0f50c, 0x1dd3e10e8}, {0x05fabe670, 0x1a2adb74e},
 126     {0x130004488, 0x0de87806c}, {0x000bcf5f6, 0x19d34af3a},
 127     {0x18f0c7078, 0x014338754}, {0x017f27698, 0x049c3cc9c},
 128     {0x058ca5f00, 0x15e3e77ee}, {0x1af900c24, 0x068bce87a},
 129     {0x0b5cfca28, 0x0dd07448e}, {0x0ded288f8, 0x1524fa6c6},
 130     {0x059f229bc, 0x1d8048348}, {0x06d390dec, 0x16cba8aca},
 131     {0x037170390, 0x0a3e3e02c}, {0x06353c1cc, 0x042d98888},
 132     {0x0c4584f5c, 0x0d73c7bea}, {0x1f16a3418, 0x1329d9f7e},
 133     {0x0531377e2, 0x185137662}, {0x1d8d9ca7c, 0x1b1c69528},
 134     {0x0b25b29f2, 0x18a08b5bc}, {0x19fb2a8b0, 0x02178513a},
 135     {0x1a08fe6ac, 0x1da758ae0}, {0x045cddf4e, 0x0e0ac139e},
 136     {0x1a91647f2, 0x169cf9eb0}, {0x1a0f717c4, 0x0170076fa},
 137 };
 138
 139 /*
 140  * CombineCRC performs pclmulqdq multiplication of 2 partial CRC's and a well
 141  * chosen constant and xor's these with the remaining CRC.
 142  */
 143 uint64_t CombineCRC(
 144     unsigned long block_size,
 145     uint64_t crc0,
 146     uint64_t crc1,
 147     uint64_t crc2,
 148     const uint64_t* next2) {
 149   const auto multiplier = *(clmul_constants + block_size - 1);
 150   const auto crc0_xmm = _mm_set_epi64x(0, crc0);
 151   const auto res0 = _mm_clmulepi64_si128(crc0_xmm, multiplier, 0x00);
 152   const auto crc1_xmm = _mm_set_epi64x(0, crc1);
 153   const auto res1 = _mm_clmulepi64_si128(crc1_xmm, multiplier, 0x10);
 154   const auto res = _mm_xor_si128(res0, res1);
 155   crc0 = _mm_cvtsi128_si64(res);
 156   crc0 = crc0 ^ *((uint64_t*)next2 - 1);
 157   crc2 = _mm_crc32_u64(crc2, crc0);
 158   return crc2;
 159 }
 160
 161 // Generates a block that will crc up to 7 bytes of unaligned data.
 162 // Always inline to avoid overhead on small crc sizes.
 163 FOLLY_ALWAYS_INLINE void align_to_8(
 164     unsigned long align,
 165     uint64_t& crc0, // crc so far, updated on return
 166     const unsigned char*& next) { // next data pointer, updated on return
 167   uint32_t crc32bit = crc0;
 168   if (align & 0x04) {
 169     crc32bit = _mm_crc32_u32(crc32bit, *(uint32_t*)next);
 170     next += sizeof(uint32_t);
 171   }
 172   if (align & 0x02) {
 173     crc32bit = _mm_crc32_u16(crc32bit, *(uint16_t*)next);
 174     next += sizeof(uint16_t);
 175   }
 176   if (align & 0x01) {
 177     crc32bit = _mm_crc32_u8(crc32bit, *(next));
 178     next++;
 179   }
 180   crc0 = crc32bit;
 181 }
 182
 183 // The main loop for large crc sizes. Generates three crc32c
 184 // streams, of varying block sizes, using a duff's device.
 185 void triplet_loop(
 186     unsigned long block_size,
 187     uint64_t& crc0, // crc so far, updated on return
 188     const unsigned char*& next, // next data pointer, updated on return
 189     unsigned long n) { // block count
 190   uint64_t crc1 = 0, crc2 = 0;
 191   // points to the first byte of the next block
 192   const uint64_t* next0 = (uint64_t*)next + block_size;
 193   const uint64_t* next1 = next0 + block_size;
 194   const uint64_t* next2 = next1 + block_size;
 195
 196   // Use Duff's device, a for() loop inside a switch()
 197   // statement. This needs to execute at least once, round len
 198   // down to nearest triplet multiple
 199   switch (block_size) {
 200     case 128:
 201       do {
 202         // jumps here for a full block of len 128
 203         CRCtriplet(crc, next, -128);
 204
 205         // Generates case statements from 127 to 2 of form:
 206         // case 127:
 207         //    CRCtriplet(crc, next, -127);
 208         BOOST_PP_REPEAT_FROM_TO(0, 126, CASEREPEAT_TRIPLET, 126);
 209
 210         // For the last byte, the three crc32c streams must be combined
 211         // using carry-less multiplication.
 212         case 1:
 213           CRCduplet(crc, next, -1); // the final triplet is actually only 2
 214           crc0 = CombineCRC(block_size, crc0, crc1, crc2, next2);
 215           if (--n > 0) {
 216             crc1 = crc2 = 0;
 217             block_size = 128;
 218             // points to the first byte of the next block
 219             next0 = next2 + 128;
 220             next1 = next0 + 128; // from here on all blocks are 128 long
 221             next2 = next1 + 128;
 222           }
 223           FOLLY_FALLTHROUGH;
 224         case 0:;
 225       } while (n > 0);
 226   }
 227
 228   next = (const unsigned char*)next2;
 229 }
 230
 231 } // namespace crc32c_detail
 232
 233 /* Compute CRC-32C using the Intel hardware instruction. */
 234 FOLLY_TARGET_ATTRIBUTE("sse4.2")
 235 uint32_t crc32c_hw(const uint8_t* buf, size_t len, uint32_t crc) {
 236   const unsigned char* next = (const unsigned char*)buf;
 237   unsigned long count;
 238   uint64_t crc0;
 239   crc0 = crc;
 240
 241   if (len >= 8) {
 242     // if len > 216 then align and use triplets
 243     if (len > 216) {
 244       unsigned long align = (8 - (uintptr_t)next) & 7;
 245       crc32_detail::align_to_8(align, crc0, next);
 246       len -= align;
 247
 248       count = len / 24; // number of triplets
 249       len %= 24; // bytes remaining
 250       unsigned long n = count >> 7; // #blocks = first block + full blocks
 251       unsigned long block_size = count & 127;
 252       if (block_size == 0) {
 253         block_size = 128;
 254       } else {
 255         n++;
 256       }
 257
 258       // This is a separate function call mainly to stop
 259       // clang from spilling registers.
 260       crc32_detail::triplet_loop(block_size, crc0, next, n);
 261     }
 262
 263     unsigned count2 = len >> 3;
 264     len = len & 7;
 265     next += (count2 * 8);
 266
 267     // Generates a duff device for the last 128 bytes of aligned data.
 268     switch (count2) {
 269       // Generates case statements of the form:
 270       // case 27:
 271       //   CRCsinglet(crc0, next, -27 * 8);
 272       BOOST_PP_REPEAT_FROM_TO(0, 27, CASEREPEAT_SINGLET, 27);
 273       case 0:;
 274     }
 275   }
 276
 277   // compute the crc for up to seven trailing bytes
 278   crc32_detail::align_to_8(len, crc0, next);
 279   return (uint32_t)crc0;
 280 }
 281
 282 #else
 283
 284 uint32_t crc32c_hw(const uint8_t* buf, size_t len, uint32_t crc) {
 285   throw std::runtime_error("crc32_hw is not implemented on this platform");
 286 }
 287
 288 #endif
 289
 290 } // namespace detail
 291 } // namespace folly