1 // SPDX-License-Identifier: 0BSD
2
3 ///////////////////////////////////////////////////////////////////////////////
4 //
5 /// \file crc_x86_clmul.h
6 /// \brief CRC32 and CRC64 implementations using CLMUL instructions.
7 ///
8 /// The CRC32 and CRC64 implementations use 32/64-bit x86 SSSE3, SSE4.1, and
9 /// CLMUL instructions. This is compatible with Elbrus 2000 (E2K) too.
10 ///
11 /// See the Intel white paper "Fast CRC Computation for Generic Polynomials
12 /// Using PCLMULQDQ Instruction" from 2009. The original file seems to be
13 /// gone from Intel's website but a version is available here:
14 /// https://www.researchgate.net/publication/263424619_Fast_CRC_computation
15 /// (The link was checked on 2024-06-11.)
16 ///
17 /// While this file has both CRC32 and CRC64 implementations, only one
18 /// can be built at a time. The version to build is selected by defining
19 /// BUILDING_CRC_CLMUL to 32 or 64 before including this file.
20 ///
21 /// NOTE: The x86 CLMUL CRC implementation was rewritten for XZ Utils 5.8.0.
22 //
23 // Authors: Lasse Collin
24 // Ilya Kurdyukov
25 //
26 ///////////////////////////////////////////////////////////////////////////////
27
28 // This file must not be included more than once.
29 #ifdef LZMA_CRC_X86_CLMUL_H
30 # error crc_x86_clmul.h was included twice.
31 #endif
32 #define LZMA_CRC_X86_CLMUL_H
33
34 #if BUILDING_CRC_CLMUL != 32 && BUILDING_CRC_CLMUL != 64
35 # error BUILDING_CRC_CLMUL is undefined or has an invalid value
36 #endif
37
38 #include <immintrin.h>
39
40 #if defined(_MSC_VER)
41 # include <intrin.h>
42 #elif defined(HAVE_CPUID_H)
43 # include <cpuid.h>
44 #endif
45
46
47 // EDG-based compilers (Intel's classic compiler and compiler for E2K) can
48 // define __GNUC__ but the attribute must not be used with them.
49 // The new Clang-based ICX needs the attribute.
50 //
51 // NOTE: Build systems check for this too, keep them in sync with this.
52 #if (defined(__GNUC__) || defined(__clang__)) && !defined(__EDG__)
53 # define crc_attr_target \
54 __attribute__((__target__("ssse3,sse4.1,pclmul")))
55 #else
56 # define crc_attr_target
57 #endif
58
59
60 // GCC and Clang would produce good code with _mm_set_epi64x
61 // but MSVC needs _mm_cvtsi64_si128 on x86-64.
62 #if defined(__i386__) || defined(_M_IX86)
63 # define my_set_low64(a) _mm_set_epi64x(0, (a))
64 #else
65 # define my_set_low64(a) _mm_cvtsi64_si128(a)
66 #endif
67
68
69 // Align it so that the whole array is within the same cache line.
70 // More than one unaligned load can be done from this during the
71 // same CRC function call.
72 //
73 // The bytes [0] to [31] are used with AND to clear the low bytes. (With ANDN
74 // those could be used to clear the high bytes too but it's not needed here.)
75 //
76 // The bytes [16] to [47] are for left shifts.
77 // The bytes [32] to [63] are for right shifts.
78 alignas(64)
79 static uint8_t vmasks[64] = {
80 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
81 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
82 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
83 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
84 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
85 0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F,
86 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
87 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
88 };
89
90
91 // *Unaligned* 128-bit load
92 crc_attr_target
93 static inline __m128i
my_load128(const uint8_t * p)94 my_load128(const uint8_t *p)
95 {
96 return _mm_loadu_si128((const __m128i *)p);
97 }
98
99
100 // Keep the highest "count" bytes as is and clear the remaining low bytes.
101 crc_attr_target
102 static inline __m128i
keep_high_bytes(__m128i v,size_t count)103 keep_high_bytes(__m128i v, size_t count)
104 {
105 return _mm_and_si128(my_load128((vmasks + count)), v);
106 }
107
108
109 // Shift the 128-bit value left by "amount" bytes (not bits).
110 crc_attr_target
111 static inline __m128i
shift_left(__m128i v,size_t amount)112 shift_left(__m128i v, size_t amount)
113 {
114 return _mm_shuffle_epi8(v, my_load128((vmasks + 32 - amount)));
115 }
116
117
118 // Shift the 128-bit value right by "amount" bytes (not bits).
119 crc_attr_target
120 static inline __m128i
shift_right(__m128i v,size_t amount)121 shift_right(__m128i v, size_t amount)
122 {
123 return _mm_shuffle_epi8(v, my_load128((vmasks + 32 + amount)));
124 }
125
126
127 crc_attr_target
128 static inline __m128i
fold(__m128i v,__m128i k)129 fold(__m128i v, __m128i k)
130 {
131 __m128i a = _mm_clmulepi64_si128(v, k, 0x00);
132 __m128i b = _mm_clmulepi64_si128(v, k, 0x11);
133 return _mm_xor_si128(a, b);
134 }
135
136
137 crc_attr_target
138 static inline __m128i
fold_xor(__m128i v,__m128i k,const uint8_t * buf)139 fold_xor(__m128i v, __m128i k, const uint8_t *buf)
140 {
141 return _mm_xor_si128(my_load128(buf), fold(v, k));
142 }
143
144
145 #if BUILDING_CRC_CLMUL == 32
146 crc_attr_target
147 static uint32_t
crc32_arch_optimized(const uint8_t * buf,size_t size,uint32_t crc)148 crc32_arch_optimized(const uint8_t *buf, size_t size, uint32_t crc)
149 #else
150 crc_attr_target
151 static uint64_t
152 crc64_arch_optimized(const uint8_t *buf, size_t size, uint64_t crc)
153 #endif
154 {
155 // We will assume that there is at least one byte of input.
156 if (size == 0)
157 return crc;
158
159 // See crc_clmul_consts_gen.c.
160 #if BUILDING_CRC_CLMUL == 32
161 const __m128i fold512 = _mm_set_epi64x(0x1d9513d7, 0x8f352d95);
162 const __m128i fold128 = _mm_set_epi64x(0xccaa009e, 0xae689191);
163 const __m128i mu_p = _mm_set_epi64x(
164 (int64_t)0xb4e5b025f7011641, 0x1db710640);
165 #else
166 const __m128i fold512 = _mm_set_epi64x(
167 (int64_t)0x081f6054a7842df4, (int64_t)0x6ae3efbb9dd441f3);
168
169 const __m128i fold128 = _mm_set_epi64x(
170 (int64_t)0xdabe95afc7875f40, (int64_t)0xe05dd497ca393ae4);
171
172 const __m128i mu_p = _mm_set_epi64x(
173 (int64_t)0x9c3e466c172963d5, (int64_t)0x92d8af2baf0e1e84);
174 #endif
175
176 __m128i v0, v1, v2, v3;
177
178 crc = ~crc;
179
180 if (size < 8) {
181 uint64_t x = crc;
182 size_t i = 0;
183
184 // Checking the bit instead of comparing the size means
185 // that we don't need to update the size between the steps.
186 if (size & 4) {
187 x ^= read32le(buf);
188 buf += 4;
189 i = 32;
190 }
191
192 if (size & 2) {
193 x ^= (uint64_t)read16le(buf) << i;
194 buf += 2;
195 i += 16;
196 }
197
198 if (size & 1)
199 x ^= (uint64_t)*buf << i;
200
201 v0 = my_set_low64((int64_t)x);
202 v0 = shift_left(v0, 8 - size);
203
204 } else if (size < 16) {
205 v0 = my_set_low64((int64_t)(crc ^ read64le(buf)));
206
207 // NOTE: buf is intentionally left 8 bytes behind so that
208 // we can read the last 1-7 bytes with read64le(buf + size).
209 size -= 8;
210
211 // Handling 8-byte input specially is a speed optimization
212 // as the clmul can be skipped. A branch is also needed to
213 // avoid a too high shift amount.
214 if (size > 0) {
215 const size_t padding = 8 - size;
216 uint64_t high = read64le(buf + size) >> (padding * 8);
217
218 #if defined(__i386__) || defined(_M_IX86)
219 // Simple but likely not the best code for 32-bit x86.
220 v0 = _mm_insert_epi32(v0, (int32_t)high, 2);
221 v0 = _mm_insert_epi32(v0, (int32_t)(high >> 32), 3);
222 #else
223 v0 = _mm_insert_epi64(v0, (int64_t)high, 1);
224 #endif
225
226 v0 = shift_left(v0, padding);
227
228 v1 = _mm_srli_si128(v0, 8);
229 v0 = _mm_clmulepi64_si128(v0, fold128, 0x10);
230 v0 = _mm_xor_si128(v0, v1);
231 }
232 } else {
233 v0 = my_set_low64((int64_t)crc);
234
235 // To align or not to align the buf pointer? If the end of
236 // the buffer isn't aligned, aligning the pointer here would
237 // make us do an extra folding step with the associated byte
238 // shuffling overhead. The cost of that would need to be
239 // lower than the benefit of aligned reads. Testing on an old
240 // Intel Ivy Bridge processor suggested that aligning isn't
241 // worth the cost but it likely depends on the processor and
242 // buffer size. Unaligned loads (MOVDQU) should be fast on
243 // x86 processors that support PCLMULQDQ, so we don't align
244 // the buf pointer here.
245
246 // Read the first (and possibly the only) full 16 bytes.
247 v0 = _mm_xor_si128(v0, my_load128(buf));
248 buf += 16;
249 size -= 16;
250
251 if (size >= 48) {
252 v1 = my_load128(buf);
253 v2 = my_load128(buf + 16);
254 v3 = my_load128(buf + 32);
255 buf += 48;
256 size -= 48;
257
258 while (size >= 64) {
259 v0 = fold_xor(v0, fold512, buf);
260 v1 = fold_xor(v1, fold512, buf + 16);
261 v2 = fold_xor(v2, fold512, buf + 32);
262 v3 = fold_xor(v3, fold512, buf + 48);
263 buf += 64;
264 size -= 64;
265 }
266
267 v0 = _mm_xor_si128(v1, fold(v0, fold128));
268 v0 = _mm_xor_si128(v2, fold(v0, fold128));
269 v0 = _mm_xor_si128(v3, fold(v0, fold128));
270 }
271
272 while (size >= 16) {
273 v0 = fold_xor(v0, fold128, buf);
274 buf += 16;
275 size -= 16;
276 }
277
278 if (size > 0) {
279 // We want the last "size" number of input bytes to
280 // be at the high bits of v1. First do a full 16-byte
281 // load and then mask the low bytes to zeros.
282 v1 = my_load128(buf + size - 16);
283 v1 = keep_high_bytes(v1, size);
284
285 // Shift high bytes from v0 to the low bytes of v1.
286 //
287 // Alternatively we could replace the combination
288 // keep_high_bytes + shift_right + _mm_or_si128 with
289 // _mm_shuffle_epi8 + _mm_blendv_epi8 but that would
290 // require larger tables for the masks. Now there are
291 // three loads (instead of two) from the mask tables
292 // but they all are from the same cache line.
293 v1 = _mm_or_si128(v1, shift_right(v0, size));
294
295 // Shift high bytes of v0 away, padding the
296 // low bytes with zeros.
297 v0 = shift_left(v0, 16 - size);
298
299 v0 = _mm_xor_si128(v1, fold(v0, fold128));
300 }
301
302 v1 = _mm_srli_si128(v0, 8);
303 v0 = _mm_clmulepi64_si128(v0, fold128, 0x10);
304 v0 = _mm_xor_si128(v0, v1);
305 }
306
307 // Barrett reduction
308
309 #if BUILDING_CRC_CLMUL == 32
310 v1 = _mm_clmulepi64_si128(v0, mu_p, 0x10); // v0 * mu
311 v1 = _mm_clmulepi64_si128(v1, mu_p, 0x00); // v1 * p
312 v0 = _mm_xor_si128(v0, v1);
313 return ~(uint32_t)_mm_extract_epi32(v0, 2);
314 #else
315 // Because p is 65 bits but one bit doesn't fit into the 64-bit
316 // half of __m128i, finish the second clmul by shifting v1 left
317 // by 64 bits and xorring it to the final result.
318 v1 = _mm_clmulepi64_si128(v0, mu_p, 0x10); // v0 * mu
319 v2 = _mm_slli_si128(v1, 8);
320 v1 = _mm_clmulepi64_si128(v1, mu_p, 0x00); // v1 * p
321 v0 = _mm_xor_si128(v0, v2);
322 v0 = _mm_xor_si128(v0, v1);
323 #if defined(__i386__) || defined(_M_IX86)
324 return ~(((uint64_t)(uint32_t)_mm_extract_epi32(v0, 3) << 32) |
325 (uint64_t)(uint32_t)_mm_extract_epi32(v0, 2));
326 #else
327 return ~(uint64_t)_mm_extract_epi64(v0, 1);
328 #endif
329 #endif
330 }
331
332
333 // Even though this is an inline function, compile it only when needed.
334 // This way it won't appear in E2K builds at all.
335 #if defined(CRC32_GENERIC) || defined(CRC64_GENERIC)
336 // Inlining this function duplicates the function body in crc32_resolve() and
337 // crc64_resolve(), but this is acceptable because this is a tiny function.
338 static inline bool
is_arch_extension_supported(void)339 is_arch_extension_supported(void)
340 {
341 int success = 1;
342 uint32_t r[4]; // eax, ebx, ecx, edx
343
344 #if defined(_MSC_VER)
345 // This needs <intrin.h> with MSVC. ICC has it as a built-in
346 // on all platforms.
347 __cpuid(r, 1);
348 #elif defined(HAVE_CPUID_H)
349 // Compared to just using __asm__ to run CPUID, this also checks
350 // that CPUID is supported and saves and restores ebx as that is
351 // needed with GCC < 5 with position-independent code (PIC).
352 success = __get_cpuid(1, &r[0], &r[1], &r[2], &r[3]);
353 #else
354 // Just a fallback that shouldn't be needed.
355 __asm__("cpuid\n\t"
356 : "=a"(r[0]), "=b"(r[1]), "=c"(r[2]), "=d"(r[3])
357 : "a"(1), "c"(0));
358 #endif
359
360 // Returns true if these are supported:
361 // CLMUL (bit 1 in ecx)
362 // SSSE3 (bit 9 in ecx)
363 // SSE4.1 (bit 19 in ecx)
364 const uint32_t ecx_mask = (1 << 1) | (1 << 9) | (1 << 19);
365 return success && (r[2] & ecx_mask) == ecx_mask;
366
367 // Alternative methods that weren't used:
368 // - ICC's _may_i_use_cpu_feature: the other methods should work too.
369 // - GCC >= 6 / Clang / ICX __builtin_cpu_supports("pclmul")
370 //
371 // CPUID decoding is needed with MSVC anyway and older GCC. This keeps
372 // the feature checks in the build system simpler too. The nice thing
373 // about __builtin_cpu_supports would be that it generates very short
374 // code as is it only reads a variable set at startup but a few bytes
375 // doesn't matter here.
376 }
377 #endif
378