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
LE_LOAD32(const uint8_t * p)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))
LE_LOAD64(const uint8_t * p)322 static inline uint64_t LE_LOAD64(const uint8_t *p) {
323 return DecodeFixed64(reinterpret_cast<const char*>(p));
324 }
325 #endif
326
Slow_CRC32(uint64_t * l,uint8_t const ** p)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
Fast_CRC32(uint64_t * l,uint8_t const ** p)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**)>
ExtendImpl(uint32_t crc,const char * buf,size_t size)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
isSSE42()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
isPCLMULQDQ()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)
ExtendPPCImpl(uint32_t crc,const char * buf,size_t size)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__
arch_ppc_probe(void)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
isAltiVec()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)
ExtendARMImpl(uint32_t crc,const char * buf,size_t size)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
IsFastCrc32Supported()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
align_to_8(size_t len,uint64_t & crc0,const unsigned char * & next)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 //
CombineCRC(size_t block_size,uint64_t crc0,uint64_t crc1,uint64_t crc2,const uint64_t * next2)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
crc32c_3way(uint32_t crc,const char * buf,size_t len)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
Choose_Extend()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();
Extend(uint32_t crc,const char * buf,size_t size)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
1256