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