ceph/src/rocksdb/util/crc32c.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9 //
  10 // A portable implementation of crc32c, optimized to handle
  11 // four bytes at a time.
  12 #include "util/crc32c.h"
  13 #include <stdint.h>
  14 #ifdef HAVE_SSE42
  15 #include <nmmintrin.h>
  16 #include <wmmintrin.h>
  17 #endif
  18 #include "util/coding.h"
  19 #include "util/util.h"
  20
  21 #include "util/crc32c_arm64.h"
  22
  23 #ifdef __powerpc64__
  24 #include "util/crc32c_ppc.h"
  25 #include "util/crc32c_ppc_constants.h"
  26
  27 #if __linux__
  28 #include <sys/auxv.h>
  29
  30 #ifndef PPC_FEATURE2_VEC_CRYPTO
  31 #define PPC_FEATURE2_VEC_CRYPTO 0x02000000
  32 #endif
  33
  34 #ifndef AT_HWCAP2
  35 #define AT_HWCAP2 26
  36 #endif
  37
  38 #endif /* __linux__ */
  39
  40 #endif
  41
  42 namespace ROCKSDB_NAMESPACE {
  43 namespace crc32c {
  44
  45 #if defined(HAVE_POWER8) && defined(HAS_ALTIVEC)
  46 #ifdef __powerpc64__
  47 static int arch_ppc_crc32 = 0;
  48 #endif /* __powerpc64__ */
  49 #endif
  50
  51 static const uint32_t table0_[256] = {
  52   0x00000000, 0xf26b8303, 0xe13b70f7, 0x1350f3f4,
  53   0xc79a971f, 0x35f1141c, 0x26a1e7e8, 0xd4ca64eb,
  54   0x8ad958cf, 0x78b2dbcc, 0x6be22838, 0x9989ab3b,
  55   0x4d43cfd0, 0xbf284cd3, 0xac78bf27, 0x5e133c24,
  56   0x105ec76f, 0xe235446c, 0xf165b798, 0x030e349b,
  57   0xd7c45070, 0x25afd373, 0x36ff2087, 0xc494a384,
  58   0x9a879fa0, 0x68ec1ca3, 0x7bbcef57, 0x89d76c54,
  59   0x5d1d08bf, 0xaf768bbc, 0xbc267848, 0x4e4dfb4b,
  60   0x20bd8ede, 0xd2d60ddd, 0xc186fe29, 0x33ed7d2a,
  61   0xe72719c1, 0x154c9ac2, 0x061c6936, 0xf477ea35,
  62   0xaa64d611, 0x580f5512, 0x4b5fa6e6, 0xb93425e5,
  63   0x6dfe410e, 0x9f95c20d, 0x8cc531f9, 0x7eaeb2fa,
  64   0x30e349b1, 0xc288cab2, 0xd1d83946, 0x23b3ba45,
  65   0xf779deae, 0x05125dad, 0x1642ae59, 0xe4292d5a,
  66   0xba3a117e, 0x4851927d, 0x5b016189, 0xa96ae28a,
  67   0x7da08661, 0x8fcb0562, 0x9c9bf696, 0x6ef07595,
  68   0x417b1dbc, 0xb3109ebf, 0xa0406d4b, 0x522bee48,
  69   0x86e18aa3, 0x748a09a0, 0x67dafa54, 0x95b17957,
  70   0xcba24573, 0x39c9c670, 0x2a993584, 0xd8f2b687,
  71   0x0c38d26c, 0xfe53516f, 0xed03a29b, 0x1f682198,
  72   0x5125dad3, 0xa34e59d0, 0xb01eaa24, 0x42752927,
  73   0x96bf4dcc, 0x64d4cecf, 0x77843d3b, 0x85efbe38,
  74   0xdbfc821c, 0x2997011f, 0x3ac7f2eb, 0xc8ac71e8,
  75   0x1c661503, 0xee0d9600, 0xfd5d65f4, 0x0f36e6f7,
  76   0x61c69362, 0x93ad1061, 0x80fde395, 0x72966096,
  77   0xa65c047d, 0x5437877e, 0x4767748a, 0xb50cf789,
  78   0xeb1fcbad, 0x197448ae, 0x0a24bb5a, 0xf84f3859,
  79   0x2c855cb2, 0xdeeedfb1, 0xcdbe2c45, 0x3fd5af46,
  80   0x7198540d, 0x83f3d70e, 0x90a324fa, 0x62c8a7f9,
  81   0xb602c312, 0x44694011, 0x5739b3e5, 0xa55230e6,
  82   0xfb410cc2, 0x092a8fc1, 0x1a7a7c35, 0xe811ff36,
  83   0x3cdb9bdd, 0xceb018de, 0xdde0eb2a, 0x2f8b6829,
  84   0x82f63b78, 0x709db87b, 0x63cd4b8f, 0x91a6c88c,
  85   0x456cac67, 0xb7072f64, 0xa457dc90, 0x563c5f93,
  86   0x082f63b7, 0xfa44e0b4, 0xe9141340, 0x1b7f9043,
  87   0xcfb5f4a8, 0x3dde77ab, 0x2e8e845f, 0xdce5075c,
  88   0x92a8fc17, 0x60c37f14, 0x73938ce0, 0x81f80fe3,
  89   0x55326b08, 0xa759e80b, 0xb4091bff, 0x466298fc,
  90   0x1871a4d8, 0xea1a27db, 0xf94ad42f, 0x0b21572c,
  91   0xdfeb33c7, 0x2d80b0c4, 0x3ed04330, 0xccbbc033,
  92   0xa24bb5a6, 0x502036a5, 0x4370c551, 0xb11b4652,
  93   0x65d122b9, 0x97baa1ba, 0x84ea524e, 0x7681d14d,
  94   0x2892ed69, 0xdaf96e6a, 0xc9a99d9e, 0x3bc21e9d,
  95   0xef087a76, 0x1d63f975, 0x0e330a81, 0xfc588982,
  96   0xb21572c9, 0x407ef1ca, 0x532e023e, 0xa145813d,
  97   0x758fe5d6, 0x87e466d5, 0x94b49521, 0x66df1622,
  98   0x38cc2a06, 0xcaa7a905, 0xd9f75af1, 0x2b9cd9f2,
  99   0xff56bd19, 0x0d3d3e1a, 0x1e6dcdee, 0xec064eed,
 100   0xc38d26c4, 0x31e6a5c7, 0x22b65633, 0xd0ddd530,
 101   0x0417b1db, 0xf67c32d8, 0xe52cc12c, 0x1747422f,
 102   0x49547e0b, 0xbb3ffd08, 0xa86f0efc, 0x5a048dff,
 103   0x8ecee914, 0x7ca56a17, 0x6ff599e3, 0x9d9e1ae0,
 104   0xd3d3e1ab, 0x21b862a8, 0x32e8915c, 0xc083125f,
 105   0x144976b4, 0xe622f5b7, 0xf5720643, 0x07198540,
 106   0x590ab964, 0xab613a67, 0xb831c993, 0x4a5a4a90,
 107   0x9e902e7b, 0x6cfbad78, 0x7fab5e8c, 0x8dc0dd8f,
 108   0xe330a81a, 0x115b2b19, 0x020bd8ed, 0xf0605bee,
 109   0x24aa3f05, 0xd6c1bc06, 0xc5914ff2, 0x37faccf1,
 110   0x69e9f0d5, 0x9b8273d6, 0x88d28022, 0x7ab90321,
 111   0xae7367ca, 0x5c18e4c9, 0x4f48173d, 0xbd23943e,
 112   0xf36e6f75, 0x0105ec76, 0x12551f82, 0xe03e9c81,
 113   0x34f4f86a, 0xc69f7b69, 0xd5cf889d, 0x27a40b9e,
 114   0x79b737ba, 0x8bdcb4b9, 0x988c474d, 0x6ae7c44e,
 115   0xbe2da0a5, 0x4c4623a6, 0x5f16d052, 0xad7d5351
 116 };
 117 static const uint32_t table1_[256] = {
 118   0x00000000, 0x13a29877, 0x274530ee, 0x34e7a899,
 119   0x4e8a61dc, 0x5d28f9ab, 0x69cf5132, 0x7a6dc945,
 120   0x9d14c3b8, 0x8eb65bcf, 0xba51f356, 0xa9f36b21,
 121   0xd39ea264, 0xc03c3a13, 0xf4db928a, 0xe7790afd,
 122   0x3fc5f181, 0x2c6769f6, 0x1880c16f, 0x0b225918,
 123   0x714f905d, 0x62ed082a, 0x560aa0b3, 0x45a838c4,
 124   0xa2d13239, 0xb173aa4e, 0x859402d7, 0x96369aa0,
 125   0xec5b53e5, 0xfff9cb92, 0xcb1e630b, 0xd8bcfb7c,
 126   0x7f8be302, 0x6c297b75, 0x58ced3ec, 0x4b6c4b9b,
 127   0x310182de, 0x22a31aa9, 0x1644b230, 0x05e62a47,
 128   0xe29f20ba, 0xf13db8cd, 0xc5da1054, 0xd6788823,
 129   0xac154166, 0xbfb7d911, 0x8b507188, 0x98f2e9ff,
 130   0x404e1283, 0x53ec8af4, 0x670b226d, 0x74a9ba1a,
 131   0x0ec4735f, 0x1d66eb28, 0x298143b1, 0x3a23dbc6,
 132   0xdd5ad13b, 0xcef8494c, 0xfa1fe1d5, 0xe9bd79a2,
 133   0x93d0b0e7, 0x80722890, 0xb4958009, 0xa737187e,
 134   0xff17c604, 0xecb55e73, 0xd852f6ea, 0xcbf06e9d,
 135   0xb19da7d8, 0xa23f3faf, 0x96d89736, 0x857a0f41,
 136   0x620305bc, 0x71a19dcb, 0x45463552, 0x56e4ad25,
 137   0x2c896460, 0x3f2bfc17, 0x0bcc548e, 0x186eccf9,
 138   0xc0d23785, 0xd370aff2, 0xe797076b, 0xf4359f1c,
 139   0x8e585659, 0x9dface2e, 0xa91d66b7, 0xbabffec0,
 140   0x5dc6f43d, 0x4e646c4a, 0x7a83c4d3, 0x69215ca4,
 141   0x134c95e1, 0x00ee0d96, 0x3409a50f, 0x27ab3d78,
 142   0x809c2506, 0x933ebd71, 0xa7d915e8, 0xb47b8d9f,
 143   0xce1644da, 0xddb4dcad, 0xe9537434, 0xfaf1ec43,
 144   0x1d88e6be, 0x0e2a7ec9, 0x3acdd650, 0x296f4e27,
 145   0x53028762, 0x40a01f15, 0x7447b78c, 0x67e52ffb,
 146   0xbf59d487, 0xacfb4cf0, 0x981ce469, 0x8bbe7c1e,
 147   0xf1d3b55b, 0xe2712d2c, 0xd69685b5, 0xc5341dc2,
 148   0x224d173f, 0x31ef8f48, 0x050827d1, 0x16aabfa6,
 149   0x6cc776e3, 0x7f65ee94, 0x4b82460d, 0x5820de7a,
 150   0xfbc3faf9, 0xe861628e, 0xdc86ca17, 0xcf245260,
 151   0xb5499b25, 0xa6eb0352, 0x920cabcb, 0x81ae33bc,
 152   0x66d73941, 0x7575a136, 0x419209af, 0x523091d8,
 153   0x285d589d, 0x3bffc0ea, 0x0f186873, 0x1cbaf004,
 154   0xc4060b78, 0xd7a4930f, 0xe3433b96, 0xf0e1a3e1,
 155   0x8a8c6aa4, 0x992ef2d3, 0xadc95a4a, 0xbe6bc23d,
 156   0x5912c8c0, 0x4ab050b7, 0x7e57f82e, 0x6df56059,
 157   0x1798a91c, 0x043a316b, 0x30dd99f2, 0x237f0185,
 158   0x844819fb, 0x97ea818c, 0xa30d2915, 0xb0afb162,
 159   0xcac27827, 0xd960e050, 0xed8748c9, 0xfe25d0be,
 160   0x195cda43, 0x0afe4234, 0x3e19eaad, 0x2dbb72da,
 161   0x57d6bb9f, 0x447423e8, 0x70938b71, 0x63311306,
 162   0xbb8de87a, 0xa82f700d, 0x9cc8d894, 0x8f6a40e3,
 163   0xf50789a6, 0xe6a511d1, 0xd242b948, 0xc1e0213f,
 164   0x26992bc2, 0x353bb3b5, 0x01dc1b2c, 0x127e835b,
 165   0x68134a1e, 0x7bb1d269, 0x4f567af0, 0x5cf4e287,
 166   0x04d43cfd, 0x1776a48a, 0x23910c13, 0x30339464,
 167   0x4a5e5d21, 0x59fcc556, 0x6d1b6dcf, 0x7eb9f5b8,
 168   0x99c0ff45, 0x8a626732, 0xbe85cfab, 0xad2757dc,
 169   0xd74a9e99, 0xc4e806ee, 0xf00fae77, 0xe3ad3600,
 170   0x3b11cd7c, 0x28b3550b, 0x1c54fd92, 0x0ff665e5,
 171   0x759baca0, 0x663934d7, 0x52de9c4e, 0x417c0439,
 172   0xa6050ec4, 0xb5a796b3, 0x81403e2a, 0x92e2a65d,
 173   0xe88f6f18, 0xfb2df76f, 0xcfca5ff6, 0xdc68c781,
 174   0x7b5fdfff, 0x68fd4788, 0x5c1aef11, 0x4fb87766,
 175   0x35d5be23, 0x26772654, 0x12908ecd, 0x013216ba,
 176   0xe64b1c47, 0xf5e98430, 0xc10e2ca9, 0xd2acb4de,
 177   0xa8c17d9b, 0xbb63e5ec, 0x8f844d75, 0x9c26d502,
 178   0x449a2e7e, 0x5738b609, 0x63df1e90, 0x707d86e7,
 179   0x0a104fa2, 0x19b2d7d5, 0x2d557f4c, 0x3ef7e73b,
 180   0xd98eedc6, 0xca2c75b1, 0xfecbdd28, 0xed69455f,
 181   0x97048c1a, 0x84a6146d, 0xb041bcf4, 0xa3e32483
 182 };
 183 static const uint32_t table2_[256] = {
 184   0x00000000, 0xa541927e, 0x4f6f520d, 0xea2ec073,
 185   0x9edea41a, 0x3b9f3664, 0xd1b1f617, 0x74f06469,
 186   0x38513ec5, 0x9d10acbb, 0x773e6cc8, 0xd27ffeb6,
 187   0xa68f9adf, 0x03ce08a1, 0xe9e0c8d2, 0x4ca15aac,
 188   0x70a27d8a, 0xd5e3eff4, 0x3fcd2f87, 0x9a8cbdf9,
 189   0xee7cd990, 0x4b3d4bee, 0xa1138b9d, 0x045219e3,
 190   0x48f3434f, 0xedb2d131, 0x079c1142, 0xa2dd833c,
 191   0xd62de755, 0x736c752b, 0x9942b558, 0x3c032726,
 192   0xe144fb14, 0x4405696a, 0xae2ba919, 0x0b6a3b67,
 193   0x7f9a5f0e, 0xdadbcd70, 0x30f50d03, 0x95b49f7d,
 194   0xd915c5d1, 0x7c5457af, 0x967a97dc, 0x333b05a2,
 195   0x47cb61cb, 0xe28af3b5, 0x08a433c6, 0xade5a1b8,
 196   0x91e6869e, 0x34a714e0, 0xde89d493, 0x7bc846ed,
 197   0x0f382284, 0xaa79b0fa, 0x40577089, 0xe516e2f7,
 198   0xa9b7b85b, 0x0cf62a25, 0xe6d8ea56, 0x43997828,
 199   0x37691c41, 0x92288e3f, 0x78064e4c, 0xdd47dc32,
 200   0xc76580d9, 0x622412a7, 0x880ad2d4, 0x2d4b40aa,
 201   0x59bb24c3, 0xfcfab6bd, 0x16d476ce, 0xb395e4b0,
 202   0xff34be1c, 0x5a752c62, 0xb05bec11, 0x151a7e6f,
 203   0x61ea1a06, 0xc4ab8878, 0x2e85480b, 0x8bc4da75,
 204   0xb7c7fd53, 0x12866f2d, 0xf8a8af5e, 0x5de93d20,
 205   0x29195949, 0x8c58cb37, 0x66760b44, 0xc337993a,
 206   0x8f96c396, 0x2ad751e8, 0xc0f9919b, 0x65b803e5,
 207   0x1148678c, 0xb409f5f2, 0x5e273581, 0xfb66a7ff,
 208   0x26217bcd, 0x8360e9b3, 0x694e29c0, 0xcc0fbbbe,
 209   0xb8ffdfd7, 0x1dbe4da9, 0xf7908dda, 0x52d11fa4,
 210   0x1e704508, 0xbb31d776, 0x511f1705, 0xf45e857b,
 211   0x80aee112, 0x25ef736c, 0xcfc1b31f, 0x6a802161,
 212   0x56830647, 0xf3c29439, 0x19ec544a, 0xbcadc634,
 213   0xc85da25d, 0x6d1c3023, 0x8732f050, 0x2273622e,
 214   0x6ed23882, 0xcb93aafc, 0x21bd6a8f, 0x84fcf8f1,
 215   0xf00c9c98, 0x554d0ee6, 0xbf63ce95, 0x1a225ceb,
 216   0x8b277743, 0x2e66e53d, 0xc448254e, 0x6109b730,
 217   0x15f9d359, 0xb0b84127, 0x5a968154, 0xffd7132a,
 218   0xb3764986, 0x1637dbf8, 0xfc191b8b, 0x595889f5,
 219   0x2da8ed9c, 0x88e97fe2, 0x62c7bf91, 0xc7862def,
 220   0xfb850ac9, 0x5ec498b7, 0xb4ea58c4, 0x11abcaba,
 221   0x655baed3, 0xc01a3cad, 0x2a34fcde, 0x8f756ea0,
 222   0xc3d4340c, 0x6695a672, 0x8cbb6601, 0x29faf47f,
 223   0x5d0a9016, 0xf84b0268, 0x1265c21b, 0xb7245065,
 224   0x6a638c57, 0xcf221e29, 0x250cde5a, 0x804d4c24,
 225   0xf4bd284d, 0x51fcba33, 0xbbd27a40, 0x1e93e83e,
 226   0x5232b292, 0xf77320ec, 0x1d5de09f, 0xb81c72e1,
 227   0xccec1688, 0x69ad84f6, 0x83834485, 0x26c2d6fb,
 228   0x1ac1f1dd, 0xbf8063a3, 0x55aea3d0, 0xf0ef31ae,
 229   0x841f55c7, 0x215ec7b9, 0xcb7007ca, 0x6e3195b4,
 230   0x2290cf18, 0x87d15d66, 0x6dff9d15, 0xc8be0f6b,
 231   0xbc4e6b02, 0x190ff97c, 0xf321390f, 0x5660ab71,
 232   0x4c42f79a, 0xe90365e4, 0x032da597, 0xa66c37e9,
 233   0xd29c5380, 0x77ddc1fe, 0x9df3018d, 0x38b293f3,
 234   0x7413c95f, 0xd1525b21, 0x3b7c9b52, 0x9e3d092c,
 235   0xeacd6d45, 0x4f8cff3b, 0xa5a23f48, 0x00e3ad36,
 236   0x3ce08a10, 0x99a1186e, 0x738fd81d, 0xd6ce4a63,
 237   0xa23e2e0a, 0x077fbc74, 0xed517c07, 0x4810ee79,
 238   0x04b1b4d5, 0xa1f026ab, 0x4bdee6d8, 0xee9f74a6,
 239   0x9a6f10cf, 0x3f2e82b1, 0xd50042c2, 0x7041d0bc,
 240   0xad060c8e, 0x08479ef0, 0xe2695e83, 0x4728ccfd,
 241   0x33d8a894, 0x96993aea, 0x7cb7fa99, 0xd9f668e7,
 242   0x9557324b, 0x3016a035, 0xda386046, 0x7f79f238,
 243   0x0b899651, 0xaec8042f, 0x44e6c45c, 0xe1a75622,
 244   0xdda47104, 0x78e5e37a, 0x92cb2309, 0x378ab177,
 245   0x437ad51e, 0xe63b4760, 0x0c158713, 0xa954156d,
 246   0xe5f54fc1, 0x40b4ddbf, 0xaa9a1dcc, 0x0fdb8fb2,
 247   0x7b2bebdb, 0xde6a79a5, 0x3444b9d6, 0x91052ba8
 248 };
 249 static const uint32_t table3_[256] = {
 250   0x00000000, 0xdd45aab8, 0xbf672381, 0x62228939,
 251   0x7b2231f3, 0xa6679b4b, 0xc4451272, 0x1900b8ca,
 252   0xf64463e6, 0x2b01c95e, 0x49234067, 0x9466eadf,
 253   0x8d665215, 0x5023f8ad, 0x32017194, 0xef44db2c,
 254   0xe964b13d, 0x34211b85, 0x560392bc, 0x8b463804,
 255   0x924680ce, 0x4f032a76, 0x2d21a34f, 0xf06409f7,
 256   0x1f20d2db, 0xc2657863, 0xa047f15a, 0x7d025be2,
 257   0x6402e328, 0xb9474990, 0xdb65c0a9, 0x06206a11,
 258   0xd725148b, 0x0a60be33, 0x6842370a, 0xb5079db2,
 259   0xac072578, 0x71428fc0, 0x136006f9, 0xce25ac41,
 260   0x2161776d, 0xfc24ddd5, 0x9e0654ec, 0x4343fe54,
 261   0x5a43469e, 0x8706ec26, 0xe524651f, 0x3861cfa7,
 262   0x3e41a5b6, 0xe3040f0e, 0x81268637, 0x5c632c8f,
 263   0x45639445, 0x98263efd, 0xfa04b7c4, 0x27411d7c,
 264   0xc805c650, 0x15406ce8, 0x7762e5d1, 0xaa274f69,
 265   0xb327f7a3, 0x6e625d1b, 0x0c40d422, 0xd1057e9a,
 266   0xaba65fe7, 0x76e3f55f, 0x14c17c66, 0xc984d6de,
 267   0xd0846e14, 0x0dc1c4ac, 0x6fe34d95, 0xb2a6e72d,
 268   0x5de23c01, 0x80a796b9, 0xe2851f80, 0x3fc0b538,
 269   0x26c00df2, 0xfb85a74a, 0x99a72e73, 0x44e284cb,
 270   0x42c2eeda, 0x9f874462, 0xfda5cd5b, 0x20e067e3,
 271   0x39e0df29, 0xe4a57591, 0x8687fca8, 0x5bc25610,
 272   0xb4868d3c, 0x69c32784, 0x0be1aebd, 0xd6a40405,
 273   0xcfa4bccf, 0x12e11677, 0x70c39f4e, 0xad8635f6,
 274   0x7c834b6c, 0xa1c6e1d4, 0xc3e468ed, 0x1ea1c255,
 275   0x07a17a9f, 0xdae4d027, 0xb8c6591e, 0x6583f3a6,
 276   0x8ac7288a, 0x57828232, 0x35a00b0b, 0xe8e5a1b3,
 277   0xf1e51979, 0x2ca0b3c1, 0x4e823af8, 0x93c79040,
 278   0x95e7fa51, 0x48a250e9, 0x2a80d9d0, 0xf7c57368,
 279   0xeec5cba2, 0x3380611a, 0x51a2e823, 0x8ce7429b,
 280   0x63a399b7, 0xbee6330f, 0xdcc4ba36, 0x0181108e,
 281   0x1881a844, 0xc5c402fc, 0xa7e68bc5, 0x7aa3217d,
 282   0x52a0c93f, 0x8fe56387, 0xedc7eabe, 0x30824006,
 283   0x2982f8cc, 0xf4c75274, 0x96e5db4d, 0x4ba071f5,
 284   0xa4e4aad9, 0x79a10061, 0x1b838958, 0xc6c623e0,
 285   0xdfc69b2a, 0x02833192, 0x60a1b8ab, 0xbde41213,
 286   0xbbc47802, 0x6681d2ba, 0x04a35b83, 0xd9e6f13b,
 287   0xc0e649f1, 0x1da3e349, 0x7f816a70, 0xa2c4c0c8,
 288   0x4d801be4, 0x90c5b15c, 0xf2e73865, 0x2fa292dd,
 289   0x36a22a17, 0xebe780af, 0x89c50996, 0x5480a32e,
 290   0x8585ddb4, 0x58c0770c, 0x3ae2fe35, 0xe7a7548d,
 291   0xfea7ec47, 0x23e246ff, 0x41c0cfc6, 0x9c85657e,
 292   0x73c1be52, 0xae8414ea, 0xcca69dd3, 0x11e3376b,
 293   0x08e38fa1, 0xd5a62519, 0xb784ac20, 0x6ac10698,
 294   0x6ce16c89, 0xb1a4c631, 0xd3864f08, 0x0ec3e5b0,
 295   0x17c35d7a, 0xca86f7c2, 0xa8a47efb, 0x75e1d443,
 296   0x9aa50f6f, 0x47e0a5d7, 0x25c22cee, 0xf8878656,
 297   0xe1873e9c, 0x3cc29424, 0x5ee01d1d, 0x83a5b7a5,
 298   0xf90696d8, 0x24433c60, 0x4661b559, 0x9b241fe1,
 299   0x8224a72b, 0x5f610d93, 0x3d4384aa, 0xe0062e12,
 300   0x0f42f53e, 0xd2075f86, 0xb025d6bf, 0x6d607c07,
 301   0x7460c4cd, 0xa9256e75, 0xcb07e74c, 0x16424df4,
 302   0x106227e5, 0xcd278d5d, 0xaf050464, 0x7240aedc,
 303   0x6b401616, 0xb605bcae, 0xd4273597, 0x09629f2f,
 304   0xe6264403, 0x3b63eebb, 0x59416782, 0x8404cd3a,
 305   0x9d0475f0, 0x4041df48, 0x22635671, 0xff26fcc9,
 306   0x2e238253, 0xf36628eb, 0x9144a1d2, 0x4c010b6a,
 307   0x5501b3a0, 0x88441918, 0xea669021, 0x37233a99,
 308   0xd867e1b5, 0x05224b0d, 0x6700c234, 0xba45688c,
 309   0xa345d046, 0x7e007afe, 0x1c22f3c7, 0xc167597f,
 310   0xc747336e, 0x1a0299d6, 0x782010ef, 0xa565ba57,
 311   0xbc65029d, 0x6120a825, 0x0302211c, 0xde478ba4,
 312   0x31035088, 0xec46fa30, 0x8e647309, 0x5321d9b1,
 313   0x4a21617b, 0x9764cbc3, 0xf54642fa, 0x2803e842
 314 };
 315
 316 // Used to fetch a naturally-aligned 32-bit word in little endian byte-order
 317 static inline uint32_t LE_LOAD32(const uint8_t *p) {
 318   return DecodeFixed32(reinterpret_cast<const char*>(p));
 319 }
 320
 321 #if defined(HAVE_SSE42) && (defined(__LP64__) || defined(_WIN64))
 322 static inline uint64_t LE_LOAD64(const uint8_t *p) {
 323   return DecodeFixed64(reinterpret_cast<const char*>(p));
 324 }
 325 #endif
 326
 327 static inline void Slow_CRC32(uint64_t* l, uint8_t const **p) {
 328   uint32_t c = static_cast<uint32_t>(*l ^ LE_LOAD32(*p));
 329   *p += 4;
 330   *l = table3_[c & 0xff] ^
 331   table2_[(c >> 8) & 0xff] ^
 332   table1_[(c >> 16) & 0xff] ^
 333   table0_[c >> 24];
 334   // DO it twice.
 335   c = static_cast<uint32_t>(*l ^ LE_LOAD32(*p));
 336   *p += 4;
 337   *l = table3_[c & 0xff] ^
 338   table2_[(c >> 8) & 0xff] ^
 339   table1_[(c >> 16) & 0xff] ^
 340   table0_[c >> 24];
 341 }
 342
 343 static inline void Fast_CRC32(uint64_t* l, uint8_t const **p) {
 344 #ifndef HAVE_SSE42
 345   Slow_CRC32(l, p);
 346 #elif defined(__LP64__) || defined(_WIN64)
 347   *l = _mm_crc32_u64(*l, LE_LOAD64(*p));
 348   *p += 8;
 349 #else
 350   *l = _mm_crc32_u32(static_cast<unsigned int>(*l), LE_LOAD32(*p));
 351   *p += 4;
 352   *l = _mm_crc32_u32(static_cast<unsigned int>(*l), LE_LOAD32(*p));
 353   *p += 4;
 354 #endif
 355 }
 356
 357 template<void (*CRC32)(uint64_t*, uint8_t const**)>
 358 uint32_t ExtendImpl(uint32_t crc, const char* buf, size_t size) {
 359
 360   const uint8_t *p = reinterpret_cast<const uint8_t *>(buf);
 361   const uint8_t *e = p + size;
 362   uint64_t l = crc ^ 0xffffffffu;
 363
 364 // Align n to (1 << m) byte boundary
 365 #define ALIGN(n, m)     ((n + ((1 << m) - 1)) & ~((1 << m) - 1))
 366
 367 #define STEP1 do {                              \
 368     int c = (l & 0xff) ^ *p++;                  \
 369     l = table0_[c] ^ (l >> 8);                  \
 370 } while (0)
 371
 372
 373   // Point x at first 16-byte aligned byte in string.  This might be
 374   // just past the end of the string.
 375   const uintptr_t pval = reinterpret_cast<uintptr_t>(p);
 376   const uint8_t* x = reinterpret_cast<const uint8_t*>(ALIGN(pval, 4));
 377   if (x <= e) {
 378     // Process bytes until finished or p is 16-byte aligned
 379     while (p != x) {
 380       STEP1;
 381     }
 382   }
 383   // Process bytes 16 at a time
 384   while ((e-p) >= 16) {
 385     CRC32(&l, &p);
 386     CRC32(&l, &p);
 387   }
 388   // Process bytes 8 at a time
 389   while ((e-p) >= 8) {
 390     CRC32(&l, &p);
 391   }
 392   // Process the last few bytes
 393   while (p != e) {
 394     STEP1;
 395   }
 396 #undef STEP1
 397 #undef ALIGN
 398   return static_cast<uint32_t>(l ^ 0xffffffffu);
 399 }
 400
 401 // Detect if ARM64 CRC or not.
 402 #ifndef HAVE_ARM64_CRC
 403 // Detect if SS42 or not.
 404 #ifndef HAVE_POWER8
 405
 406 static bool isSSE42() {
 407 #ifndef HAVE_SSE42
 408   return false;
 409 #elif defined(__GNUC__) && defined(__x86_64__) && !defined(IOS_CROSS_COMPILE)
 410   uint32_t c_;
 411   __asm__("cpuid" : "=c"(c_) : "a"(1) : "ebx", "edx");
 412   return c_ & (1U << 20);  // copied from CpuId.h in Folly. Test SSE42
 413 #elif defined(_WIN64)
 414   int info[4];
 415   __cpuidex(info, 0x00000001, 0);
 416   return (info[2] & ((int)1 << 20)) != 0;
 417 #else
 418   return false;
 419 #endif
 420 }
 421
 422 static bool isPCLMULQDQ() {
 423 #ifndef HAVE_SSE42
 424 // in build_detect_platform we set this macro when both SSE42 and PCLMULQDQ are
 425 // supported by compiler
 426   return false;
 427 #elif defined(__GNUC__) && defined(__x86_64__) && !defined(IOS_CROSS_COMPILE)
 428   uint32_t c_;
 429   __asm__("cpuid" : "=c"(c_) : "a"(1) : "ebx", "edx");
 430   return c_ & (1U << 1);  // PCLMULQDQ is in bit 1 (not bit 0)
 431 #elif defined(_WIN64)
 432   int info[4];
 433   __cpuidex(info, 0x00000001, 0);
 434   return (info[2] & ((int)1 << 1)) != 0;
 435 #else
 436   return false;
 437 #endif
 438 }
 439
 440 #endif  // HAVE_POWER8
 441 #endif  // HAVE_ARM64_CRC
 442
 443 typedef uint32_t (*Function)(uint32_t, const char*, size_t);
 444
 445 #if defined(HAVE_POWER8) && defined(HAS_ALTIVEC)
 446 uint32_t ExtendPPCImpl(uint32_t crc, const char *buf, size_t size) {
 447   return crc32c_ppc(crc, (const unsigned char *)buf, size);
 448 }
 449
 450 #if __linux__
 451 static int arch_ppc_probe(void) {
 452   arch_ppc_crc32 = 0;
 453
 454 #if defined(__powerpc64__)
 455   if (getauxval(AT_HWCAP2) & PPC_FEATURE2_VEC_CRYPTO) arch_ppc_crc32 = 1;
 456 #endif /* __powerpc64__ */
 457
 458   return arch_ppc_crc32;
 459 }
 460 #endif  // __linux__
 461
 462 static bool isAltiVec() {
 463   if (arch_ppc_probe()) {
 464     return true;
 465   } else {
 466     return false;
 467   }
 468 }
 469 #endif
 470
 471 #if defined(__linux__) && defined(HAVE_ARM64_CRC)
 472 uint32_t ExtendARMImpl(uint32_t crc, const char *buf, size_t size) {
 473   return crc32c_arm64(crc, (const unsigned char *)buf, size);
 474 }
 475 #endif
 476
 477 std::string IsFastCrc32Supported() {
 478   bool has_fast_crc = false;
 479   std::string fast_zero_msg;
 480   std::string arch;
 481 #ifdef HAVE_POWER8
 482 #ifdef HAS_ALTIVEC
 483   if (arch_ppc_probe()) {
 484     has_fast_crc = true;
 485     arch = "PPC";
 486   }
 487 #else
 488   has_fast_crc = false;
 489   arch = "PPC";
 490 #endif
 491 #elif defined(__linux__) && defined(HAVE_ARM64_CRC)
 492   if (crc32c_runtime_check()) {
 493     has_fast_crc = true;
 494     arch = "Arm64";
 495   } else {
 496     has_fast_crc = false;
 497     arch = "Arm64";
 498   }
 499 #else
 500   has_fast_crc = isSSE42();
 501   arch = "x86";
 502 #endif
 503   if (has_fast_crc) {
 504     fast_zero_msg.append("Supported on " + arch);
 505   }
 506   else {
 507     fast_zero_msg.append("Not supported on " + arch);
 508   }
 509   return fast_zero_msg;
 510 }
 511
 512
 513 /*
 514  * Copyright 2016 Ferry Toth, Exalon Delft BV, The Netherlands
 515  *  This software is provided 'as-is', without any express or implied
 516  * warranty.  In no event will the author be held liable for any damages
 517  * arising from the use of this software.
 518  *  Permission is granted to anyone to use this software for any purpose,
 519  * including commercial applications, and to alter it and redistribute it
 520  * freely, subject to the following restrictions:
 521  *  1. The origin of this software must not be misrepresented; you must not
 522  *   claim that you wrote the original software. If you use this software
 523  *   in a product, an acknowledgment in the product documentation would be
 524  *   appreciated but is not required.
 525  * 2. Altered source versions must be plainly marked as such, and must not be
 526  *   misrepresented as being the original software.
 527  * 3. This notice may not be removed or altered from any source distribution.
 528  *  Ferry Toth
 529  * ftoth@exalondelft.nl
 530  *
 531  * https://github.com/htot/crc32c
 532  *
 533  * Modified by Facebook
 534  *
 535  * Original intel whitepaper:
 536  * "Fast CRC Computation for iSCSI Polynomial Using CRC32 Instruction"
 537  * https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf
 538  *
 539  * This version is from the folly library, created by Dave Watson <davejwatson@fb.com>
 540  *
 541 */
 542 #if defined HAVE_SSE42 && defined HAVE_PCLMUL
 543
 544 #define CRCtriplet(crc, buf, offset)                  \
 545   crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
 546   crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset)); \
 547   crc##2 = _mm_crc32_u64(crc##2, *(buf##2 + offset));
 548
 549 #define CRCduplet(crc, buf, offset)                   \
 550   crc##0 = _mm_crc32_u64(crc##0, *(buf##0 + offset)); \
 551   crc##1 = _mm_crc32_u64(crc##1, *(buf##1 + offset));
 552
 553 #define CRCsinglet(crc, buf, offset)                    \
 554   crc = _mm_crc32_u64(crc, *(uint64_t*)(buf + offset));
 555
 556
 557 // Numbers taken directly from intel whitepaper.
 558 // clang-format off
 559 const uint64_t clmul_constants[] = {
 560     0x14cd00bd6, 0x105ec76f0, 0x0ba4fc28e, 0x14cd00bd6,
 561     0x1d82c63da, 0x0f20c0dfe, 0x09e4addf8, 0x0ba4fc28e,
 562     0x039d3b296, 0x1384aa63a, 0x102f9b8a2, 0x1d82c63da,
 563     0x14237f5e6, 0x01c291d04, 0x00d3b6092, 0x09e4addf8,
 564     0x0c96cfdc0, 0x0740eef02, 0x18266e456, 0x039d3b296,
 565     0x0daece73e, 0x0083a6eec, 0x0ab7aff2a, 0x102f9b8a2,
 566     0x1248ea574, 0x1c1733996, 0x083348832, 0x14237f5e6,
 567     0x12c743124, 0x02ad91c30, 0x0b9e02b86, 0x00d3b6092,
 568     0x018b33a4e, 0x06992cea2, 0x1b331e26a, 0x0c96cfdc0,
 569     0x17d35ba46, 0x07e908048, 0x1bf2e8b8a, 0x18266e456,
 570     0x1a3e0968a, 0x11ed1f9d8, 0x0ce7f39f4, 0x0daece73e,
 571     0x061d82e56, 0x0f1d0f55e, 0x0d270f1a2, 0x0ab7aff2a,
 572     0x1c3f5f66c, 0x0a87ab8a8, 0x12ed0daac, 0x1248ea574,
 573     0x065863b64, 0x08462d800, 0x11eef4f8e, 0x083348832,
 574     0x1ee54f54c, 0x071d111a8, 0x0b3e32c28, 0x12c743124,
 575     0x0064f7f26, 0x0ffd852c6, 0x0dd7e3b0c, 0x0b9e02b86,
 576     0x0f285651c, 0x0dcb17aa4, 0x010746f3c, 0x018b33a4e,
 577     0x1c24afea4, 0x0f37c5aee, 0x0271d9844, 0x1b331e26a,
 578     0x08e766a0c, 0x06051d5a2, 0x093a5f730, 0x17d35ba46,
 579     0x06cb08e5c, 0x11d5ca20e, 0x06b749fb2, 0x1bf2e8b8a,
 580     0x1167f94f2, 0x021f3d99c, 0x0cec3662e, 0x1a3e0968a,
 581     0x19329634a, 0x08f158014, 0x0e6fc4e6a, 0x0ce7f39f4,
 582     0x08227bb8a, 0x1a5e82106, 0x0b0cd4768, 0x061d82e56,
 583     0x13c2b89c4, 0x188815ab2, 0x0d7a4825c, 0x0d270f1a2,
 584     0x10f5ff2ba, 0x105405f3e, 0x00167d312, 0x1c3f5f66c,
 585     0x0f6076544, 0x0e9adf796, 0x026f6a60a, 0x12ed0daac,
 586     0x1a2adb74e, 0x096638b34, 0x19d34af3a, 0x065863b64,
 587     0x049c3cc9c, 0x1e50585a0, 0x068bce87a, 0x11eef4f8e,
 588     0x1524fa6c6, 0x19f1c69dc, 0x16cba8aca, 0x1ee54f54c,
 589     0x042d98888, 0x12913343e, 0x1329d9f7e, 0x0b3e32c28,
 590     0x1b1c69528, 0x088f25a3a, 0x02178513a, 0x0064f7f26,
 591     0x0e0ac139e, 0x04e36f0b0, 0x0170076fa, 0x0dd7e3b0c,
 592     0x141a1a2e2, 0x0bd6f81f8, 0x16ad828b4, 0x0f285651c,
 593     0x041d17b64, 0x19425cbba, 0x1fae1cc66, 0x010746f3c,
 594     0x1a75b4b00, 0x18db37e8a, 0x0f872e54c, 0x1c24afea4,
 595     0x01e41e9fc, 0x04c144932, 0x086d8e4d2, 0x0271d9844,
 596     0x160f7af7a, 0x052148f02, 0x05bb8f1bc, 0x08e766a0c,
 597     0x0a90fd27a, 0x0a3c6f37a, 0x0b3af077a, 0x093a5f730,
 598     0x04984d782, 0x1d22c238e, 0x0ca6ef3ac, 0x06cb08e5c,
 599     0x0234e0b26, 0x063ded06a, 0x1d88abd4a, 0x06b749fb2,
 600     0x04597456a, 0x04d56973c, 0x0e9e28eb4, 0x1167f94f2,
 601     0x07b3ff57a, 0x19385bf2e, 0x0c9c8b782, 0x0cec3662e,
 602     0x13a9cba9e, 0x0e417f38a, 0x093e106a4, 0x19329634a,
 603     0x167001a9c, 0x14e727980, 0x1ddffc5d4, 0x0e6fc4e6a,
 604     0x00df04680, 0x0d104b8fc, 0x02342001e, 0x08227bb8a,
 605     0x00a2a8d7e, 0x05b397730, 0x168763fa6, 0x0b0cd4768,
 606     0x1ed5a407a, 0x0e78eb416, 0x0d2c3ed1a, 0x13c2b89c4,
 607     0x0995a5724, 0x1641378f0, 0x19b1afbc4, 0x0d7a4825c,
 608     0x109ffedc0, 0x08d96551c, 0x0f2271e60, 0x10f5ff2ba,
 609     0x00b0bf8ca, 0x00bf80dd2, 0x123888b7a, 0x00167d312,
 610     0x1e888f7dc, 0x18dcddd1c, 0x002ee03b2, 0x0f6076544,
 611     0x183e8d8fe, 0x06a45d2b2, 0x133d7a042, 0x026f6a60a,
 612     0x116b0f50c, 0x1dd3e10e8, 0x05fabe670, 0x1a2adb74e,
 613     0x130004488, 0x0de87806c, 0x000bcf5f6, 0x19d34af3a,
 614     0x18f0c7078, 0x014338754, 0x017f27698, 0x049c3cc9c,
 615     0x058ca5f00, 0x15e3e77ee, 0x1af900c24, 0x068bce87a,
 616     0x0b5cfca28, 0x0dd07448e, 0x0ded288f8, 0x1524fa6c6,
 617     0x059f229bc, 0x1d8048348, 0x06d390dec, 0x16cba8aca,
 618     0x037170390, 0x0a3e3e02c, 0x06353c1cc, 0x042d98888,
 619     0x0c4584f5c, 0x0d73c7bea, 0x1f16a3418, 0x1329d9f7e,
 620     0x0531377e2, 0x185137662, 0x1d8d9ca7c, 0x1b1c69528,
 621     0x0b25b29f2, 0x18a08b5bc, 0x19fb2a8b0, 0x02178513a,
 622     0x1a08fe6ac, 0x1da758ae0, 0x045cddf4e, 0x0e0ac139e,
 623     0x1a91647f2, 0x169cf9eb0, 0x1a0f717c4, 0x0170076fa,
 624 };
 625
 626 // Compute the crc32c value for buffer smaller than 8
 627 #ifdef ROCKSDB_UBSAN_RUN
 628 #if defined(__clang__)
 629 __attribute__((__no_sanitize__("alignment")))
 630 #elif defined(__GNUC__)
 631 __attribute__((__no_sanitize_undefined__))
 632 #endif
 633 #endif
 634 inline void align_to_8(
 635     size_t len,
 636     uint64_t& crc0, // crc so far, updated on return
 637     const unsigned char*& next) { // next data pointer, updated on return
 638   uint32_t crc32bit = static_cast<uint32_t>(crc0);
 639   if (len & 0x04) {
 640     crc32bit = _mm_crc32_u32(crc32bit, *(uint32_t*)next);
 641     next += sizeof(uint32_t);
 642   }
 643   if (len & 0x02) {
 644     crc32bit = _mm_crc32_u16(crc32bit, *(uint16_t*)next);
 645     next += sizeof(uint16_t);
 646   }
 647   if (len & 0x01) {
 648     crc32bit = _mm_crc32_u8(crc32bit, *(next));
 649     next++;
 650   }
 651   crc0 = crc32bit;
 652 }
 653
 654 //
 655 // CombineCRC performs pclmulqdq multiplication of 2 partial CRC's and a well
 656 // chosen constant and xor's these with the remaining CRC.
 657 //
 658 inline uint64_t CombineCRC(
 659     size_t block_size,
 660     uint64_t crc0,
 661     uint64_t crc1,
 662     uint64_t crc2,
 663     const uint64_t* next2) {
 664   const auto multiplier =
 665       *(reinterpret_cast<const __m128i*>(clmul_constants) + block_size - 1);
 666   const auto crc0_xmm = _mm_set_epi64x(0, crc0);
 667   const auto res0 = _mm_clmulepi64_si128(crc0_xmm, multiplier, 0x00);
 668   const auto crc1_xmm = _mm_set_epi64x(0, crc1);
 669   const auto res1 = _mm_clmulepi64_si128(crc1_xmm, multiplier, 0x10);
 670   const auto res = _mm_xor_si128(res0, res1);
 671   crc0 = _mm_cvtsi128_si64(res);
 672   crc0 = crc0 ^ *((uint64_t*)next2 - 1);
 673   crc2 = _mm_crc32_u64(crc2, crc0);
 674   return crc2;
 675 }
 676
 677 // Compute CRC-32C using the Intel hardware instruction.
 678 #ifdef ROCKSDB_UBSAN_RUN
 679 #if defined(__clang__)
 680 __attribute__((__no_sanitize__("alignment")))
 681 #elif defined(__GNUC__)
 682 __attribute__((__no_sanitize_undefined__))
 683 #endif
 684 #endif
 685 uint32_t crc32c_3way(uint32_t crc, const char* buf, size_t len) {
 686   const unsigned char* next = (const unsigned char*)buf;
 687   uint64_t count;
 688   uint64_t crc0, crc1, crc2;
 689   crc0 = crc ^ 0xffffffffu;
 690
 691
 692   if (len >= 8) {
 693     // if len > 216 then align and use triplets
 694     if (len > 216) {
 695       {
 696         // Work on the bytes (< 8) before the first 8-byte alignment addr starts
 697         uint64_t align_bytes = (8 - (uintptr_t)next) & 7;
 698         len -= align_bytes;
 699         align_to_8(align_bytes, crc0, next);
 700       }
 701
 702       // Now work on the remaining blocks
 703       count = len / 24; // number of triplets
 704       len %= 24; // bytes remaining
 705       uint64_t n = count >> 7; // #blocks = first block + full blocks
 706       uint64_t block_size = count & 127;
 707       if (block_size == 0) {
 708         block_size = 128;
 709       } else {
 710         n++;
 711       }
 712       // points to the first byte of the next block
 713       const uint64_t* next0 = (uint64_t*)next + block_size;
 714       const uint64_t* next1 = next0 + block_size;
 715       const uint64_t* next2 = next1 + block_size;
 716
 717       crc1 = crc2 = 0;
 718       // Use Duff's device, a for() loop inside a switch()
 719       // statement. This needs to execute at least once, round len
 720       // down to nearest triplet multiple
 721       switch (block_size) {
 722         case 128:
 723           do {
 724             // jumps here for a full block of len 128
 725             CRCtriplet(crc, next, -128);
 726             FALLTHROUGH_INTENDED;
 727             case 127:
 728               // jumps here or below for the first block smaller
 729               CRCtriplet(crc, next, -127);
 730               FALLTHROUGH_INTENDED;
 731             case 126:
 732               CRCtriplet(crc, next, -126); // than 128
 733               FALLTHROUGH_INTENDED;
 734             case 125:
 735               CRCtriplet(crc, next, -125);
 736               FALLTHROUGH_INTENDED;
 737             case 124:
 738               CRCtriplet(crc, next, -124);
 739               FALLTHROUGH_INTENDED;
 740             case 123:
 741               CRCtriplet(crc, next, -123);
 742               FALLTHROUGH_INTENDED;
 743             case 122:
 744               CRCtriplet(crc, next, -122);
 745               FALLTHROUGH_INTENDED;
 746             case 121:
 747               CRCtriplet(crc, next, -121);
 748               FALLTHROUGH_INTENDED;
 749             case 120:
 750               CRCtriplet(crc, next, -120);
 751               FALLTHROUGH_INTENDED;
 752             case 119:
 753               CRCtriplet(crc, next, -119);
 754               FALLTHROUGH_INTENDED;
 755             case 118:
 756               CRCtriplet(crc, next, -118);
 757               FALLTHROUGH_INTENDED;
 758             case 117:
 759               CRCtriplet(crc, next, -117);
 760               FALLTHROUGH_INTENDED;
 761             case 116:
 762               CRCtriplet(crc, next, -116);
 763               FALLTHROUGH_INTENDED;
 764             case 115:
 765               CRCtriplet(crc, next, -115);
 766               FALLTHROUGH_INTENDED;
 767             case 114:
 768               CRCtriplet(crc, next, -114);
 769               FALLTHROUGH_INTENDED;
 770             case 113:
 771               CRCtriplet(crc, next, -113);
 772               FALLTHROUGH_INTENDED;
 773             case 112:
 774               CRCtriplet(crc, next, -112);
 775               FALLTHROUGH_INTENDED;
 776             case 111:
 777               CRCtriplet(crc, next, -111);
 778               FALLTHROUGH_INTENDED;
 779             case 110:
 780               CRCtriplet(crc, next, -110);
 781               FALLTHROUGH_INTENDED;
 782             case 109:
 783               CRCtriplet(crc, next, -109);
 784               FALLTHROUGH_INTENDED;
 785             case 108:
 786               CRCtriplet(crc, next, -108);
 787               FALLTHROUGH_INTENDED;
 788             case 107:
 789               CRCtriplet(crc, next, -107);
 790               FALLTHROUGH_INTENDED;
 791             case 106:
 792               CRCtriplet(crc, next, -106);
 793               FALLTHROUGH_INTENDED;
 794             case 105:
 795               CRCtriplet(crc, next, -105);
 796               FALLTHROUGH_INTENDED;
 797             case 104:
 798               CRCtriplet(crc, next, -104);
 799               FALLTHROUGH_INTENDED;
 800             case 103:
 801               CRCtriplet(crc, next, -103);
 802               FALLTHROUGH_INTENDED;
 803             case 102:
 804               CRCtriplet(crc, next, -102);
 805               FALLTHROUGH_INTENDED;
 806             case 101:
 807               CRCtriplet(crc, next, -101);
 808               FALLTHROUGH_INTENDED;
 809             case 100:
 810               CRCtriplet(crc, next, -100);
 811               FALLTHROUGH_INTENDED;
 812             case 99:
 813               CRCtriplet(crc, next, -99);
 814               FALLTHROUGH_INTENDED;
 815             case 98:
 816               CRCtriplet(crc, next, -98);
 817               FALLTHROUGH_INTENDED;
 818             case 97:
 819               CRCtriplet(crc, next, -97);
 820               FALLTHROUGH_INTENDED;
 821             case 96:
 822               CRCtriplet(crc, next, -96);
 823               FALLTHROUGH_INTENDED;
 824             case 95:
 825               CRCtriplet(crc, next, -95);
 826               FALLTHROUGH_INTENDED;
 827             case 94:
 828               CRCtriplet(crc, next, -94);
 829               FALLTHROUGH_INTENDED;
 830             case 93:
 831               CRCtriplet(crc, next, -93);
 832               FALLTHROUGH_INTENDED;
 833             case 92:
 834               CRCtriplet(crc, next, -92);
 835               FALLTHROUGH_INTENDED;
 836             case 91:
 837               CRCtriplet(crc, next, -91);
 838               FALLTHROUGH_INTENDED;
 839             case 90:
 840               CRCtriplet(crc, next, -90);
 841               FALLTHROUGH_INTENDED;
 842             case 89:
 843               CRCtriplet(crc, next, -89);
 844               FALLTHROUGH_INTENDED;
 845             case 88:
 846               CRCtriplet(crc, next, -88);
 847               FALLTHROUGH_INTENDED;
 848             case 87:
 849               CRCtriplet(crc, next, -87);
 850               FALLTHROUGH_INTENDED;
 851             case 86:
 852               CRCtriplet(crc, next, -86);
 853               FALLTHROUGH_INTENDED;
 854             case 85:
 855               CRCtriplet(crc, next, -85);
 856               FALLTHROUGH_INTENDED;
 857             case 84:
 858               CRCtriplet(crc, next, -84);
 859               FALLTHROUGH_INTENDED;
 860             case 83:
 861               CRCtriplet(crc, next, -83);
 862               FALLTHROUGH_INTENDED;
 863             case 82:
 864               CRCtriplet(crc, next, -82);
 865               FALLTHROUGH_INTENDED;
 866             case 81:
 867               CRCtriplet(crc, next, -81);
 868               FALLTHROUGH_INTENDED;
 869             case 80:
 870               CRCtriplet(crc, next, -80);
 871               FALLTHROUGH_INTENDED;
 872             case 79:
 873               CRCtriplet(crc, next, -79);
 874               FALLTHROUGH_INTENDED;
 875             case 78:
 876               CRCtriplet(crc, next, -78);
 877               FALLTHROUGH_INTENDED;
 878             case 77:
 879               CRCtriplet(crc, next, -77);
 880               FALLTHROUGH_INTENDED;
 881             case 76:
 882               CRCtriplet(crc, next, -76);
 883               FALLTHROUGH_INTENDED;
 884             case 75:
 885               CRCtriplet(crc, next, -75);
 886               FALLTHROUGH_INTENDED;
 887             case 74:
 888               CRCtriplet(crc, next, -74);
 889               FALLTHROUGH_INTENDED;
 890             case 73:
 891               CRCtriplet(crc, next, -73);
 892               FALLTHROUGH_INTENDED;
 893             case 72:
 894               CRCtriplet(crc, next, -72);
 895               FALLTHROUGH_INTENDED;
 896             case 71:
 897               CRCtriplet(crc, next, -71);
 898               FALLTHROUGH_INTENDED;
 899             case 70:
 900               CRCtriplet(crc, next, -70);
 901               FALLTHROUGH_INTENDED;
 902             case 69:
 903               CRCtriplet(crc, next, -69);
 904               FALLTHROUGH_INTENDED;
 905             case 68:
 906               CRCtriplet(crc, next, -68);
 907               FALLTHROUGH_INTENDED;
 908             case 67:
 909               CRCtriplet(crc, next, -67);
 910               FALLTHROUGH_INTENDED;
 911             case 66:
 912               CRCtriplet(crc, next, -66);
 913               FALLTHROUGH_INTENDED;
 914             case 65:
 915               CRCtriplet(crc, next, -65);
 916               FALLTHROUGH_INTENDED;
 917             case 64:
 918               CRCtriplet(crc, next, -64);
 919               FALLTHROUGH_INTENDED;
 920             case 63:
 921               CRCtriplet(crc, next, -63);
 922               FALLTHROUGH_INTENDED;
 923             case 62:
 924               CRCtriplet(crc, next, -62);
 925               FALLTHROUGH_INTENDED;
 926             case 61:
 927               CRCtriplet(crc, next, -61);
 928               FALLTHROUGH_INTENDED;
 929             case 60:
 930               CRCtriplet(crc, next, -60);
 931               FALLTHROUGH_INTENDED;
 932             case 59:
 933               CRCtriplet(crc, next, -59);
 934               FALLTHROUGH_INTENDED;
 935             case 58:
 936               CRCtriplet(crc, next, -58);
 937               FALLTHROUGH_INTENDED;
 938             case 57:
 939               CRCtriplet(crc, next, -57);
 940               FALLTHROUGH_INTENDED;
 941             case 56:
 942               CRCtriplet(crc, next, -56);
 943               FALLTHROUGH_INTENDED;
 944             case 55:
 945               CRCtriplet(crc, next, -55);
 946               FALLTHROUGH_INTENDED;
 947             case 54:
 948               CRCtriplet(crc, next, -54);
 949               FALLTHROUGH_INTENDED;
 950             case 53:
 951               CRCtriplet(crc, next, -53);
 952               FALLTHROUGH_INTENDED;
 953             case 52:
 954               CRCtriplet(crc, next, -52);
 955               FALLTHROUGH_INTENDED;
 956             case 51:
 957               CRCtriplet(crc, next, -51);
 958               FALLTHROUGH_INTENDED;
 959             case 50:
 960               CRCtriplet(crc, next, -50);
 961               FALLTHROUGH_INTENDED;
 962             case 49:
 963               CRCtriplet(crc, next, -49);
 964               FALLTHROUGH_INTENDED;
 965             case 48:
 966               CRCtriplet(crc, next, -48);
 967               FALLTHROUGH_INTENDED;
 968             case 47:
 969               CRCtriplet(crc, next, -47);
 970               FALLTHROUGH_INTENDED;
 971             case 46:
 972               CRCtriplet(crc, next, -46);
 973               FALLTHROUGH_INTENDED;
 974             case 45:
 975               CRCtriplet(crc, next, -45);
 976               FALLTHROUGH_INTENDED;
 977             case 44:
 978               CRCtriplet(crc, next, -44);
 979               FALLTHROUGH_INTENDED;
 980             case 43:
 981               CRCtriplet(crc, next, -43);
 982               FALLTHROUGH_INTENDED;
 983             case 42:
 984               CRCtriplet(crc, next, -42);
 985               FALLTHROUGH_INTENDED;
 986             case 41:
 987               CRCtriplet(crc, next, -41);
 988               FALLTHROUGH_INTENDED;
 989             case 40:
 990               CRCtriplet(crc, next, -40);
 991               FALLTHROUGH_INTENDED;
 992             case 39:
 993               CRCtriplet(crc, next, -39);
 994               FALLTHROUGH_INTENDED;
 995             case 38:
 996               CRCtriplet(crc, next, -38);
 997               FALLTHROUGH_INTENDED;
 998             case 37:
 999               CRCtriplet(crc, next, -37);
1000               FALLTHROUGH_INTENDED;
1001             case 36:
1002               CRCtriplet(crc, next, -36);
1003               FALLTHROUGH_INTENDED;
1004             case 35:
1005               CRCtriplet(crc, next, -35);
1006               FALLTHROUGH_INTENDED;
1007             case 34:
1008               CRCtriplet(crc, next, -34);
1009               FALLTHROUGH_INTENDED;
1010             case 33:
1011               CRCtriplet(crc, next, -33);
1012               FALLTHROUGH_INTENDED;
1013             case 32:
1014               CRCtriplet(crc, next, -32);
1015               FALLTHROUGH_INTENDED;
1016             case 31:
1017               CRCtriplet(crc, next, -31);
1018               FALLTHROUGH_INTENDED;
1019             case 30:
1020               CRCtriplet(crc, next, -30);
1021               FALLTHROUGH_INTENDED;
1022             case 29:
1023               CRCtriplet(crc, next, -29);
1024               FALLTHROUGH_INTENDED;
1025             case 28:
1026               CRCtriplet(crc, next, -28);
1027               FALLTHROUGH_INTENDED;
1028             case 27:
1029               CRCtriplet(crc, next, -27);
1030               FALLTHROUGH_INTENDED;
1031             case 26:
1032               CRCtriplet(crc, next, -26);
1033               FALLTHROUGH_INTENDED;
1034             case 25:
1035               CRCtriplet(crc, next, -25);
1036               FALLTHROUGH_INTENDED;
1037             case 24:
1038               CRCtriplet(crc, next, -24);
1039               FALLTHROUGH_INTENDED;
1040             case 23:
1041               CRCtriplet(crc, next, -23);
1042               FALLTHROUGH_INTENDED;
1043             case 22:
1044               CRCtriplet(crc, next, -22);
1045               FALLTHROUGH_INTENDED;
1046             case 21:
1047               CRCtriplet(crc, next, -21);
1048               FALLTHROUGH_INTENDED;
1049             case 20:
1050               CRCtriplet(crc, next, -20);
1051               FALLTHROUGH_INTENDED;
1052             case 19:
1053               CRCtriplet(crc, next, -19);
1054               FALLTHROUGH_INTENDED;
1055             case 18:
1056               CRCtriplet(crc, next, -18);
1057               FALLTHROUGH_INTENDED;
1058             case 17:
1059               CRCtriplet(crc, next, -17);
1060               FALLTHROUGH_INTENDED;
1061             case 16:
1062               CRCtriplet(crc, next, -16);
1063               FALLTHROUGH_INTENDED;
1064             case 15:
1065               CRCtriplet(crc, next, -15);
1066               FALLTHROUGH_INTENDED;
1067             case 14:
1068               CRCtriplet(crc, next, -14);
1069               FALLTHROUGH_INTENDED;
1070             case 13:
1071               CRCtriplet(crc, next, -13);
1072               FALLTHROUGH_INTENDED;
1073             case 12:
1074               CRCtriplet(crc, next, -12);
1075               FALLTHROUGH_INTENDED;
1076             case 11:
1077               CRCtriplet(crc, next, -11);
1078               FALLTHROUGH_INTENDED;
1079             case 10:
1080               CRCtriplet(crc, next, -10);
1081               FALLTHROUGH_INTENDED;
1082             case 9:
1083               CRCtriplet(crc, next, -9);
1084               FALLTHROUGH_INTENDED;
1085             case 8:
1086               CRCtriplet(crc, next, -8);
1087               FALLTHROUGH_INTENDED;
1088             case 7:
1089               CRCtriplet(crc, next, -7);
1090               FALLTHROUGH_INTENDED;
1091             case 6:
1092               CRCtriplet(crc, next, -6);
1093               FALLTHROUGH_INTENDED;
1094             case 5:
1095               CRCtriplet(crc, next, -5);
1096               FALLTHROUGH_INTENDED;
1097             case 4:
1098               CRCtriplet(crc, next, -4);
1099               FALLTHROUGH_INTENDED;
1100             case 3:
1101               CRCtriplet(crc, next, -3);
1102               FALLTHROUGH_INTENDED;
1103             case 2:
1104               CRCtriplet(crc, next, -2);
1105               FALLTHROUGH_INTENDED;
1106             case 1:
1107               CRCduplet(crc, next, -1); // the final triplet is actually only 2
1108               //{ CombineCRC(); }
1109               crc0 = CombineCRC(block_size, crc0, crc1, crc2, next2);
1110               if (--n > 0) {
1111                 crc1 = crc2 = 0;
1112                 block_size = 128;
1113                 // points to the first byte of the next block
1114                 next0 = next2 + 128;
1115                 next1 = next0 + 128; // from here on all blocks are 128 long
1116                 next2 = next1 + 128;
1117               }
1118               FALLTHROUGH_INTENDED;
1119             case 0:;
1120           } while (n > 0);
1121       }
1122       next = (const unsigned char*)next2;
1123     }
1124     uint64_t count2 = len >> 3; // 216 of less bytes is 27 or less singlets
1125     len = len & 7;
1126     next += (count2 * 8);
1127     switch (count2) {
1128       case 27:
1129         CRCsinglet(crc0, next, -27 * 8);
1130         FALLTHROUGH_INTENDED;
1131       case 26:
1132         CRCsinglet(crc0, next, -26 * 8);
1133         FALLTHROUGH_INTENDED;
1134       case 25:
1135         CRCsinglet(crc0, next, -25 * 8);
1136         FALLTHROUGH_INTENDED;
1137       case 24:
1138         CRCsinglet(crc0, next, -24 * 8);
1139         FALLTHROUGH_INTENDED;
1140       case 23:
1141         CRCsinglet(crc0, next, -23 * 8);
1142         FALLTHROUGH_INTENDED;
1143       case 22:
1144         CRCsinglet(crc0, next, -22 * 8);
1145         FALLTHROUGH_INTENDED;
1146       case 21:
1147         CRCsinglet(crc0, next, -21 * 8);
1148         FALLTHROUGH_INTENDED;
1149       case 20:
1150         CRCsinglet(crc0, next, -20 * 8);
1151         FALLTHROUGH_INTENDED;
1152       case 19:
1153         CRCsinglet(crc0, next, -19 * 8);
1154         FALLTHROUGH_INTENDED;
1155       case 18:
1156         CRCsinglet(crc0, next, -18 * 8);
1157         FALLTHROUGH_INTENDED;
1158       case 17:
1159         CRCsinglet(crc0, next, -17 * 8);
1160         FALLTHROUGH_INTENDED;
1161       case 16:
1162         CRCsinglet(crc0, next, -16 * 8);
1163         FALLTHROUGH_INTENDED;
1164       case 15:
1165         CRCsinglet(crc0, next, -15 * 8);
1166         FALLTHROUGH_INTENDED;
1167       case 14:
1168         CRCsinglet(crc0, next, -14 * 8);
1169         FALLTHROUGH_INTENDED;
1170       case 13:
1171         CRCsinglet(crc0, next, -13 * 8);
1172         FALLTHROUGH_INTENDED;
1173       case 12:
1174         CRCsinglet(crc0, next, -12 * 8);
1175         FALLTHROUGH_INTENDED;
1176       case 11:
1177         CRCsinglet(crc0, next, -11 * 8);
1178         FALLTHROUGH_INTENDED;
1179       case 10:
1180         CRCsinglet(crc0, next, -10 * 8);
1181         FALLTHROUGH_INTENDED;
1182       case 9:
1183         CRCsinglet(crc0, next, -9 * 8);
1184         FALLTHROUGH_INTENDED;
1185       case 8:
1186         CRCsinglet(crc0, next, -8 * 8);
1187         FALLTHROUGH_INTENDED;
1188       case 7:
1189         CRCsinglet(crc0, next, -7 * 8);
1190         FALLTHROUGH_INTENDED;
1191       case 6:
1192         CRCsinglet(crc0, next, -6 * 8);
1193         FALLTHROUGH_INTENDED;
1194       case 5:
1195         CRCsinglet(crc0, next, -5 * 8);
1196         FALLTHROUGH_INTENDED;
1197       case 4:
1198         CRCsinglet(crc0, next, -4 * 8);
1199         FALLTHROUGH_INTENDED;
1200       case 3:
1201         CRCsinglet(crc0, next, -3 * 8);
1202         FALLTHROUGH_INTENDED;
1203       case 2:
1204         CRCsinglet(crc0, next, -2 * 8);
1205         FALLTHROUGH_INTENDED;
1206       case 1:
1207         CRCsinglet(crc0, next, -1 * 8);
1208         FALLTHROUGH_INTENDED;
1209       case 0:;
1210     }
1211   }
1212   {
1213     align_to_8(len, crc0, next);
1214     return (uint32_t)crc0 ^ 0xffffffffu;
1215   }
1216 }
1217
1218 #endif //HAVE_SSE42 && HAVE_PCLMUL
1219
1220 static inline Function Choose_Extend() {
1221 #ifdef HAVE_POWER8
1222   return isAltiVec() ? ExtendPPCImpl : ExtendImpl<Slow_CRC32>;
1223 #elif defined(__linux__) && defined(HAVE_ARM64_CRC)
1224   if(crc32c_runtime_check()) {
1225     return ExtendARMImpl;
1226   } else {
1227     return ExtendImpl<Slow_CRC32>;
1228   }
1229 #else
1230   if (isSSE42()) {
1231     if (isPCLMULQDQ()) {
1232 #if defined HAVE_SSE42  && defined HAVE_PCLMUL && !defined NO_THREEWAY_CRC32C
1233       return crc32c_3way;
1234 #else
1235     return ExtendImpl<Fast_CRC32>; // Fast_CRC32 will check HAVE_SSE42 itself
1236 #endif
1237     }
1238     else {  // no runtime PCLMULQDQ support but has SSE42 support
1239       return ExtendImpl<Fast_CRC32>;
1240     }
1241   } // end of isSSE42()
1242   else {
1243     return ExtendImpl<Slow_CRC32>;
1244   }
1245 #endif
1246 }
1247
1248 static Function ChosenExtend = Choose_Extend();
1249 uint32_t Extend(uint32_t crc, const char* buf, size_t size) {
1250   return ChosenExtend(crc, buf, size);
1251 }
1252
1253
1254 }  // namespace crc32c
1255 }  // namespace ROCKSDB_NAMESPACE