Branch data Line data Source code
1 : : /* crc32c.c -- compute CRC-32C using software table or available hardware instructions
2 : : * Copyright (C) 2013 Mark Adler
3 : : * Version 1.1 1 Aug 2013 Mark Adler
4 : : *
5 : : * Code retrieved in August 2016 from August 2013 post by Mark Adler on
6 : : * http://stackoverflow.com/questions/17645167/implementing-sse-4-2s-crc32c-in-software
7 : : * Modified for use in libjulia:
8 : : * - exported function renamed to jl_crc32c, DLL exports added.
9 : : * - removed main() function
10 : : * - architecture and compiler detection
11 : : * - precompute crc32c tables and store in a generated .c file
12 : : * - ARMv8 support
13 : : */
14 : :
15 : : /*
16 : : This software is provided 'as-is', without any express or implied
17 : : warranty. In no event will the author be held liable for any damages
18 : : arising from the use of this software.
19 : :
20 : : Permission is granted to anyone to use this software for any purpose,
21 : : including commercial applications, and to alter it and redistribute it
22 : : freely, subject to the following restrictions:
23 : :
24 : : 1. The origin of this software must not be misrepresented; you must not
25 : : claim that you wrote the original software. If you use this software
26 : : in a product, an acknowledgment in the product documentation would be
27 : : appreciated but is not required.
28 : : 2. Altered source versions must be plainly marked as such, and must not be
29 : : misrepresented as being the original software.
30 : : 3. This notice may not be removed or altered from any source distribution.
31 : :
32 : : Mark Adler
33 : : madler@alumni.caltech.edu
34 : : */
35 : :
36 : : /* This computes a CRC-32C, *not* the CRC-32 used by Ethernet and zip, gzip, etc.
37 : : * A software version is provided as a fall-back, as well as for speed comparisons. */
38 : :
39 : : /* Version history:
40 : : 1.0 10 Feb 2013 First version
41 : : 1.1 1 Aug 2013 Correct comments on why three crc instructions in parallel
42 : : */
43 : :
44 : : #include "julia.h"
45 : : #include "julia_internal.h"
46 : : #include "processor.h"
47 : :
48 : : #if defined(_CPU_AARCH64_) && defined(_OS_LINUX_)
49 : : # include <sys/auxv.h>
50 : : #endif
51 : :
52 : : /* CRC-32C (iSCSI) polynomial in reversed bit order. */
53 : : #define POLY 0x82f63b78
54 : :
55 : : /* Block sizes for three-way parallel crc computation. LONG and SHORT must
56 : : both be powers of two. The associated string constants must be set
57 : : accordingly, for use in constructing the assembler instructions. */
58 : : #define LONG 8192
59 : : #define LONGx1 "8192"
60 : : #define LONGx2 "16384"
61 : : #define SHORT 256
62 : : #define SHORTx1 "256"
63 : : #define SHORTx2 "512"
64 : :
65 : : #ifndef GEN_CRC32C_TABLES
66 : : #include "crc32c-tables.c"
67 : :
68 : : #if JL_USE_IFUNC
69 : : // Archs that can't use ifunc to do feature detection (e.g. ARM) should undef this below.
70 : : # define JL_CRC32C_USE_IFUNC
71 : : #endif
72 : :
73 : : JL_DLLEXPORT uint32_t jl_crc32c_sw(uint32_t crci, const char *buf, size_t len);
74 : : typedef uint32_t (*crc32c_func_t)(uint32_t crc, const char *buf, size_t len);
75 : :
76 : : /* Apply the zeros operator table to crc. */
77 : 112 : JL_UNUSED static inline uint32_t crc32c_shift(const uint32_t zeros[][256], uint32_t crc)
78 : : {
79 : 112 : return zeros[0][crc & 0xff] ^ zeros[1][(crc >> 8) & 0xff] ^
80 : 112 : zeros[2][(crc >> 16) & 0xff] ^ zeros[3][crc >> 24];
81 : : }
82 : :
83 : : #if defined(_CPU_X86_64_) || defined(_CPU_X86_)
84 : : # ifdef _CPU_X86_64_
85 : : # define CRC32_PTR "crc32q"
86 : : # else
87 : : # define CRC32_PTR "crc32l"
88 : : # endif
89 : :
90 : : /* Compute CRC-32C using the SSE4.2 hardware instruction. */
91 : 578 : static uint32_t crc32c_sse42(uint32_t crc, const char *buf, size_t len)
92 : : {
93 : : /* need to be 64 bits for crc32q */
94 : : /* pre-process the crc */
95 : 578 : uintptr_t crc0 = crc ^ 0xffffffff;
96 : :
97 : : /* compute the crc for up to seven leading bytes to bring the data pointer
98 : : to an eight-byte boundary */
99 [ + + - + ]: 578 : while (len && ((uintptr_t)buf & 7) != 0) {
100 : 0 : __asm__("crc32b\t" "(%1), %0"
101 : : : "=r"(crc0)
102 : : : "r"(buf), "0"(crc0));
103 : 0 : buf++;
104 : 0 : len--;
105 : : }
106 : :
107 : : /* compute the crc on sets of LONG*3 bytes, executing three independent crc
108 : : instructions, each on LONG bytes -- this is optimized for the Nehalem,
109 : : Westmere, Sandy Bridge, and Ivy Bridge architectures, which have a
110 : : throughput of one crc per cycle, but a latency of three cycles */
111 [ - + ]: 578 : while (len >= LONG * 3) {
112 : 0 : uintptr_t crc1 = 0;
113 : 0 : uintptr_t crc2 = 0;
114 : 0 : const char *end = buf + LONG;
115 : : do {
116 : 0 : __asm__(CRC32_PTR "\t" "(%3), %0\n\t"
117 : : CRC32_PTR "\t" LONGx1 "(%3), %1\n\t"
118 : : CRC32_PTR "\t" LONGx2 "(%3), %2"
119 : : : "=r"(crc0), "=r"(crc1), "=r"(crc2)
120 : : : "r"(buf), "0"(crc0), "1"(crc1), "2"(crc2));
121 : 0 : buf += sizeof(void*);
122 [ # # ]: 0 : } while (buf < end);
123 : 0 : crc0 = crc32c_shift(crc32c_long, crc0) ^ crc1;
124 : 0 : crc0 = crc32c_shift(crc32c_long, crc0) ^ crc2;
125 : 0 : buf += LONG * 2;
126 : 0 : len -= LONG * 3;
127 : : }
128 : :
129 : : /* do the same thing, but now on SHORT*3 blocks for the remaining data less
130 : : than a LONG*3 block */
131 [ + + ]: 634 : while (len >= SHORT * 3) {
132 : 56 : uintptr_t crc1 = 0;
133 : 56 : uintptr_t crc2 = 0;
134 : 56 : const char *end = buf + SHORT;
135 : : do {
136 : 1792 : __asm__(CRC32_PTR "\t" "(%3), %0\n\t"
137 : : CRC32_PTR "\t" SHORTx1 "(%3), %1\n\t"
138 : : CRC32_PTR "\t" SHORTx2 "(%3), %2"
139 : : : "=r"(crc0), "=r"(crc1), "=r"(crc2)
140 : : : "r"(buf), "0"(crc0), "1"(crc1), "2"(crc2));
141 : 1792 : buf += sizeof(void*);
142 [ + + ]: 1792 : } while (buf < end);
143 : 56 : crc0 = crc32c_shift(crc32c_short, crc0) ^ crc1;
144 : 56 : crc0 = crc32c_shift(crc32c_short, crc0) ^ crc2;
145 : 56 : buf += SHORT * 2;
146 : 56 : len -= SHORT * 3;
147 : : }
148 : :
149 : : /* compute the crc on the remaining eight-byte units less than a SHORT*3
150 : : block */
151 : 578 : const char *end = buf + (len - (len & 7));
152 [ + + ]: 13552 : while (buf < end) {
153 : 12974 : __asm__(CRC32_PTR "\t" "(%1), %0"
154 : : : "=r"(crc0)
155 : : : "r"(buf), "0"(crc0));
156 : 12974 : buf += sizeof(void*);
157 : : }
158 : 578 : len &= 7;
159 : :
160 : : /* compute the crc for up to seven trailing bytes */
161 [ + + ]: 2126 : while (len) {
162 : 1548 : __asm__("crc32b\t" "(%1), %0"
163 : : : "=r"(crc0)
164 : : : "r"(buf), "0"(crc0));
165 : 1548 : buf++;
166 : 1548 : len--;
167 : : }
168 : :
169 : : /* return a post-processed crc */
170 : 578 : return (uint32_t)crc0 ^ 0xffffffff;
171 : : }
172 : :
173 : : // HW feature detection
174 : : # ifdef __SSE4_2__
175 : : // The C code is compiled with SSE42 being required. Skip runtime dispatch.
176 : : JL_DLLEXPORT uint32_t jl_crc32c(uint32_t crc, const char *buf, size_t len)
177 : : {
178 : : return crc32c_sse42(crc, buf, len);
179 : : }
180 : : # else
181 : 90 : static crc32c_func_t crc32c_dispatch(void)
182 : : {
183 : : // When used in ifunc, we cannot call external functions (i.e. jl_cpuid)
184 : 90 : uint32_t eax = 1, ebx, ecx, edx;
185 : 90 : asm (
186 : : #if defined(__i386__) && defined(__PIC__)
187 : : "xchg %%ebx, %%esi;"
188 : : "cpuid;"
189 : : "xchg %%esi, %%ebx;":
190 : : "=S" (ebx) ,
191 : : #else
192 : : "cpuid":
193 : : "=b" (ebx),
194 : : #endif
195 : : "+a" (eax),
196 : : "=c" (ecx),
197 : : "=d" (edx));
198 [ + - ]: 90 : if ((ecx >> 20) & 1)
199 : 90 : return crc32c_sse42;
200 : 0 : return jl_crc32c_sw;
201 : : }
202 : : // For ifdef detection below
203 : : # define crc32c_dispatch crc32c_dispatch
204 : : # define crc32c_dispatch_ifunc "crc32c_dispatch"
205 : : # endif
206 : : #elif defined(_CPU_AARCH64_)
207 : : #ifdef _COMPILER_CLANG_
208 : : #define CRC_TARGET __attribute__((target("crc")))
209 : : #else
210 : : #define CRC_TARGET __attribute__((target("+crc")))
211 : : #endif
212 : : /* Compute CRC-32C using the ARMv8 CRC32 extension. */
213 : : CRC_TARGET static inline uint32_t crc32cx(uint32_t crc, uint64_t val)
214 : : {
215 : : uint32_t res;
216 : : asm("crc32cx %w0, %w1, %2" : "=r"(res) : "r"(crc), "r"(val));
217 : : return res;
218 : : }
219 : : CRC_TARGET static inline uint32_t crc32cw(uint32_t crc, uint32_t val)
220 : : {
221 : : uint32_t res;
222 : : asm("crc32cw %w0, %w1, %w2" : "=r"(res) : "r"(crc), "r"(val));
223 : : return res;
224 : : }
225 : : CRC_TARGET static inline uint32_t crc32ch(uint32_t crc, uint32_t val)
226 : : {
227 : : uint32_t res;
228 : : asm("crc32ch %w0, %w1, %w2" : "=r"(res) : "r"(crc), "r"(val));
229 : : return res;
230 : : }
231 : : CRC_TARGET static inline uint32_t crc32cb(uint32_t crc, uint32_t val)
232 : : {
233 : : uint32_t res;
234 : : asm("crc32cb %w0, %w1, %w2" : "=r"(res) : "r"(crc), "r"(val));
235 : : return res;
236 : : }
237 : :
238 : : // Modified from the SSE4.2 version.
239 : : CRC_TARGET static uint32_t crc32c_armv8(uint32_t crc, const char *buf, size_t len)
240 : : {
241 : : /* pre-process the crc */
242 : : crc = ~crc;
243 : :
244 : : // Misaligned access doesn't seem to have any measurable performance overhead
245 : : // on Cortex-A57
246 : :
247 : : // crc32c has a latency of 3 and throughput of 1 on Cortex-A57
248 : : // The latency and throughput are 2 and 1 on Cortex-A72
249 : : // In either case, the 3 wide parallel processing shouldn't hurt since the block size
250 : : // should be big enough.
251 : : /* compute the crc on sets of LONG*3 bytes, executing three independent crc
252 : : * instructions, each on LONG bytes. */
253 : : while (len >= LONG * 3) {
254 : : uint32_t crc1 = 0;
255 : : uint32_t crc2 = 0;
256 : : const char *end = buf + LONG;
257 : : const char *buf2 = end;
258 : : const char *buf3 = end + LONG;
259 : : do {
260 : : crc = crc32cx(crc, jl_load_unaligned_i64(buf));
261 : : buf += 8;
262 : : crc1 = crc32cx(crc1, jl_load_unaligned_i64(buf2));
263 : : buf2 += 8;
264 : : crc2 = crc32cx(crc2, jl_load_unaligned_i64(buf3));
265 : : buf3 += 8;
266 : : } while (buf < end);
267 : : crc = crc32c_shift(crc32c_long, crc) ^ crc1;
268 : : crc = crc32c_shift(crc32c_long, crc) ^ crc2;
269 : : buf += LONG * 2;
270 : : len -= LONG * 3;
271 : : }
272 : :
273 : : /* do the same thing, but now on SHORT*3 blocks for the remaining data less
274 : : * than a LONG*3 block */
275 : : while (len >= SHORT * 3) {
276 : : uint32_t crc1 = 0;
277 : : uint32_t crc2 = 0;
278 : : const char *end = buf + SHORT;
279 : : const char *buf2 = end;
280 : : const char *buf3 = end + SHORT;
281 : : do {
282 : : crc = crc32cx(crc, jl_load_unaligned_i64(buf));
283 : : buf += 8;
284 : : crc1 = crc32cx(crc1, jl_load_unaligned_i64(buf2));
285 : : buf2 += 8;
286 : : crc2 = crc32cx(crc2, jl_load_unaligned_i64(buf3));
287 : : buf3 += 8;
288 : : } while (buf < end);
289 : : crc = crc32c_shift(crc32c_short, crc) ^ crc1;
290 : : crc = crc32c_shift(crc32c_short, crc) ^ crc2;
291 : : buf += SHORT * 2;
292 : : len -= SHORT * 3;
293 : : }
294 : : // The same shift table can be used to compute two SHORT blocks simultaneously
295 : : if (len >= SHORT * 2) {
296 : : uint32_t crc1 = 0;
297 : : const char *end = buf + SHORT;
298 : : const char *buf2 = end;
299 : : do {
300 : : crc = crc32cx(crc, jl_load_unaligned_i64(buf));
301 : : buf += 8;
302 : : crc1 = crc32cx(crc1, jl_load_unaligned_i64(buf2));
303 : : buf2 += 8;
304 : : } while (buf < end);
305 : : crc = crc32c_shift(crc32c_short, crc) ^ crc1;
306 : : buf += SHORT;
307 : : len -= SHORT * 2;
308 : : }
309 : :
310 : : /* compute the crc on the remaining eight-byte units less than a SHORT*2
311 : : block */
312 : : const char *end = buf + len - 8;
313 : : while (buf <= end) {
314 : : crc = crc32cx(crc, jl_load_unaligned_i64(buf));
315 : : buf += 8;
316 : : }
317 : : if (len & 4) {
318 : : crc = crc32cw(crc, jl_load_unaligned_i32(buf));
319 : : buf += 4;
320 : : }
321 : : if (len & 2) {
322 : : crc = crc32ch(crc, jl_load_unaligned_i16(buf));
323 : : buf += 2;
324 : : }
325 : : if (len & 1)
326 : : crc = crc32cb(crc, *buf);
327 : : /* return a post-processed crc */
328 : : return ~crc;
329 : : }
330 : :
331 : : // HW feature detection
332 : : # ifdef __ARM_FEATURE_CRC32
333 : : // The C code is compiled with CRC32 being required. Skip runtime dispatch.
334 : : JL_DLLEXPORT uint32_t jl_crc32c(uint32_t crc, const char *buf, size_t len)
335 : : {
336 : : return crc32c_armv8(crc, buf, len);
337 : : }
338 : : # elif defined(_OS_DARWIN_)
339 : : // All Apple chips that run Darwin should have crc32 support.
340 : : // If that ever changes for some reason, this could be detected via the hw.optional.crc32 sysctl
341 : : # error Darwin/ARM64, but no CRC32 support?
342 : : # elif defined(_OS_LINUX_)
343 : : static crc32c_func_t crc32c_dispatch(unsigned long hwcap)
344 : : {
345 : : if (hwcap & (1 << JL_AArch64_crc))
346 : : return crc32c_armv8;
347 : : return jl_crc32c_sw;
348 : : }
349 : : // For ifdef detection below
350 : : # define crc32c_dispatch() crc32c_dispatch(getauxval(AT_HWCAP))
351 : : # define crc32c_dispatch_ifunc "crc32c_dispatch"
352 : : # else
353 : : # pragma message("CRC32 feature detection not implemented for this OS. Falling back to software version.")
354 : : # endif
355 : : #else
356 : : // If we don't have any accelerated version to define, just make the _sw version define
357 : : // the real version and then define a _sw version as test wrapper.
358 : : JL_DLLEXPORT uint32_t jl_crc32c(uint32_t crc, const char *buf, size_t len);
359 : : JL_DLLEXPORT uint32_t jl_crc32c_sw(uint32_t crc, const char *buf, size_t len)
360 : : {
361 : : return jl_crc32c(crc, buf, len);
362 : : }
363 : : #define jl_crc32c_sw jl_crc32c
364 : : #endif
365 : :
366 : : #ifdef crc32c_dispatch
367 : : # ifdef JL_CRC32C_USE_IFUNC
368 : : // ifunc dispatch
369 : : JL_DLLEXPORT uint32_t jl_crc32c(uint32_t crc, const char *buf, size_t len)
370 : : __attribute__((ifunc (crc32c_dispatch_ifunc)));
371 : : # else
372 : : // lazy wrapper dispatch
373 : : static uint32_t crc32c_lazy(uint32_t crc, const char *buf, size_t len);
374 : : static crc32c_func_t crc32c_func = crc32c_lazy;
375 : :
376 : : static uint32_t crc32c_lazy(uint32_t crc, const char *buf, size_t len)
377 : : {
378 : : crc32c_func = crc32c_dispatch();
379 : : return crc32c_func(crc, buf, len);
380 : : }
381 : :
382 : : /* Compute a CRC-32C. Do a lazy dispatch based on hardware features */
383 : : JL_DLLEXPORT uint32_t jl_crc32c(uint32_t crc, const char *buf, size_t len)
384 : : {
385 : : return crc32c_func(crc, buf, len);
386 : : }
387 : : # endif
388 : : #endif
389 : :
390 : : /* Table-driven software version as a fall-back. This is about 15 times slower
391 : : than using the hardware instructions. This computes a little-endian
392 : : CRC32c, equivalent to the little-endian CRC of the SSE4.2 or ARMv8 instructions,
393 : : regardless of the endianness of the machine this is running on. */
394 : 0 : JL_DLLEXPORT uint32_t jl_crc32c_sw(uint32_t crci, const char *buf, size_t len)
395 : : {
396 : 0 : uintptr_t crc = crci ^ 0xffffffff;
397 [ # # # # ]: 0 : while (len && ((uintptr_t)buf & 7) != 0) {
398 : 0 : crc = crc32c_table[0][(crc ^ *buf++) & 0xff] ^ (crc >> 8);
399 : 0 : len--;
400 : : }
401 [ # # ]: 0 : while (len >= 8) {
402 : : #ifdef _P64
403 : 0 : crc ^= *(uint64_t*)buf;
404 : 0 : crc = crc32c_table[7][crc & 0xff] ^
405 : 0 : crc32c_table[6][(crc >> 8) & 0xff] ^
406 : 0 : crc32c_table[5][(crc >> 16) & 0xff] ^
407 : 0 : crc32c_table[4][(crc >> 24) & 0xff] ^
408 : 0 : crc32c_table[3][(crc >> 32) & 0xff] ^
409 : 0 : crc32c_table[2][(crc >> 40) & 0xff] ^
410 : 0 : crc32c_table[1][(crc >> 48) & 0xff] ^
411 : 0 : crc32c_table[0][crc >> 56];
412 : : #else
413 : : uint32_t *p = (uint32_t*)buf;
414 : : crc ^= p[0];
415 : : uint32_t hi = p[1];
416 : : crc = crc32c_table[7][crc & 0xff] ^
417 : : crc32c_table[6][(crc >> 8) & 0xff] ^
418 : : crc32c_table[5][(crc >> 16) & 0xff] ^
419 : : crc32c_table[4][(crc >> 24) & 0xff] ^
420 : : crc32c_table[3][hi & 0xff] ^
421 : : crc32c_table[2][(hi >> 8) & 0xff] ^
422 : : crc32c_table[1][(hi >> 16) & 0xff] ^
423 : : crc32c_table[0][hi >> 24];
424 : : #endif
425 : 0 : buf += 8;
426 : 0 : len -= 8;
427 : : }
428 [ # # ]: 0 : while (len) {
429 : 0 : crc = crc32c_table[0][(crc ^ *buf++) & 0xff] ^ (crc >> 8);
430 : 0 : len--;
431 : : }
432 : 0 : return (uint32_t)crc ^ 0xffffffff;
433 : : }
434 : :
435 : : /*****************************************************************************/
436 : : /*****************************************************************************/
437 : : /*****************************************************************************/
438 : :
439 : : /* Compile with -DGEN_CRC32C_TABLES to generate header file containing
440 : : precomputed hardware and software tables */
441 : : // Example command line, run from top level directory:
442 : : // $ gcc src/crc32c.c -o main -DGEN_CRC32C_TABLES -I src -I src/support
443 : : // $ ./main > src/crc32c-tables.c
444 : :
445 : : #else /* ifdef GEN_CRC32C_TABLES */
446 : :
447 : : /* Table for a quadword-at-a-time software crc. */
448 : : static uint32_t crc32c_table[8][256];
449 : :
450 : : /* Construct table for software CRC-32C calculation. */
451 : : static void crc32c_init_sw(void)
452 : : {
453 : : uint32_t n, crc, k;
454 : :
455 : : for (n = 0; n < 256; n++) {
456 : : crc = n;
457 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
458 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
459 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
460 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
461 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
462 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
463 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
464 : : crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
465 : : crc32c_table[0][n] = crc;
466 : : }
467 : : for (n = 0; n < 256; n++) {
468 : : crc = crc32c_table[0][n];
469 : : for (k = 1; k < 8; k++) {
470 : : crc = crc32c_table[0][crc & 0xff] ^ (crc >> 8);
471 : : crc32c_table[k][n] = crc;
472 : : }
473 : : }
474 : : }
475 : :
476 : : /* Tables for hardware crc that shift a crc by LONG and SHORT zeros. */
477 : : static uint32_t crc32c_long[4][256];
478 : : static uint32_t crc32c_short[4][256];
479 : :
480 : : /* Multiply a matrix times a vector over the Galois field of two elements,
481 : : GF(2). Each element is a bit in an unsigned integer. mat must have at
482 : : least as many entries as the power of two for most significant one bit in
483 : : vec. */
484 : : static inline uint32_t gf2_matrix_times(uint32_t *mat, uint32_t vec)
485 : : {
486 : : uint32_t sum;
487 : :
488 : : sum = 0;
489 : : while (vec) {
490 : : if (vec & 1)
491 : : sum ^= *mat;
492 : : vec >>= 1;
493 : : mat++;
494 : : }
495 : : return sum;
496 : : }
497 : :
498 : : /* Multiply a matrix by itself over GF(2). Both mat and square must have 32
499 : : rows. */
500 : : static inline void gf2_matrix_square(uint32_t *square, uint32_t *mat)
501 : : {
502 : : int n;
503 : :
504 : : for (n = 0; n < 32; n++)
505 : : square[n] = gf2_matrix_times(mat, mat[n]);
506 : : }
507 : :
508 : : /* Construct an operator to apply len zeros to a crc. len must be a power of
509 : : two. If len is not a power of two, then the result is the same as for the
510 : : largest power of two less than len. The result for len == 0 is the same as
511 : : for len == 1. A version of this routine could be easily written for any
512 : : len, but that is not needed for this application. */
513 : : static void crc32c_zeros_op(uint32_t *even, size_t len)
514 : : {
515 : : int n;
516 : : uint32_t row;
517 : : uint32_t odd[32]; /* odd-power-of-two zeros operator */
518 : :
519 : : /* put operator for one zero bit in odd */
520 : : odd[0] = POLY; /* CRC-32C polynomial */
521 : : row = 1;
522 : : for (n = 1; n < 32; n++) {
523 : : odd[n] = row;
524 : : row <<= 1;
525 : : }
526 : :
527 : : /* put operator for two zero bits in even */
528 : : gf2_matrix_square(even, odd);
529 : :
530 : : /* put operator for four zero bits in odd */
531 : : gf2_matrix_square(odd, even);
532 : :
533 : : /* first square will put the operator for one zero byte (eight zero bits),
534 : : in even -- next square puts operator for two zero bytes in odd, and so
535 : : on, until len has been rotated down to zero */
536 : : do {
537 : : gf2_matrix_square(even, odd);
538 : : len >>= 1;
539 : : if (len == 0)
540 : : return;
541 : : gf2_matrix_square(odd, even);
542 : : len >>= 1;
543 : : } while (len);
544 : :
545 : : /* answer ended up in odd -- copy to even */
546 : : for (n = 0; n < 32; n++)
547 : : even[n] = odd[n];
548 : : }
549 : :
550 : : /* Take a length and build four lookup tables for applying the zeros operator
551 : : for that length, byte-by-byte on the operand. */
552 : : static void crc32c_zeros(uint32_t zeros[][256], size_t len)
553 : : {
554 : : uint32_t n;
555 : : uint32_t op[32];
556 : :
557 : : crc32c_zeros_op(op, len);
558 : : for (n = 0; n < 256; n++) {
559 : : zeros[0][n] = gf2_matrix_times(op, n);
560 : : zeros[1][n] = gf2_matrix_times(op, n << 8);
561 : : zeros[2][n] = gf2_matrix_times(op, n << 16);
562 : : zeros[3][n] = gf2_matrix_times(op, n << 24);
563 : : }
564 : : }
565 : :
566 : : /* Initialize tables for shifting crcs. */
567 : : static void crc32c_init_hw(void)
568 : : {
569 : : crc32c_zeros(crc32c_long, LONG);
570 : : crc32c_zeros(crc32c_short, SHORT);
571 : : }
572 : :
573 : : #include <stdio.h>
574 : :
575 : : static void print_array(const char *name, int m, int n, const uint32_t *a)
576 : : {
577 : : int i, j;
578 : : printf("JL_UNUSED static const uint32_t %s[%d][%d] = {\n", name, m, n);
579 : : for (i = 0; i < m; ++i) {
580 : : printf(" { %u", a[i*n+0]);
581 : : for (j = 1; j < n; ++j) printf(",%u", a[i*n+j]);
582 : : printf(" }%s", i == m-1 ? "\n" : ",\n");
583 : : }
584 : : printf("};\n");
585 : : }
586 : :
587 : : int main(void)
588 : : {
589 : : printf("// This file is a part of Julia. License is MIT: https://julialang.org/license\n\n");
590 : : printf("/* Pregenerated tables for crc32c.c, produced by compiling with -DGEN_CRC32C_TABLES. */\n"
591 : : "#if POLY != 0x%x\n# error \"tables generated for different polynomial\"\n#endif\n\n", POLY);
592 : : crc32c_init_sw();
593 : : print_array("crc32c_table", 8, 256, &crc32c_table[0][0]);
594 : : crc32c_init_hw();
595 : : printf("\n");
596 : : print_array("crc32c_long", 4, 256, &crc32c_long[0][0]);
597 : : print_array("crc32c_short", 4, 256, &crc32c_short[0][0]);
598 : : return 0;
599 : : }
600 : :
601 : : #endif /* GEN_CRC32C_TABLES */
602 : :
603 : : /*****************************************************************************/
604 : : /*****************************************************************************/
605 : : /*****************************************************************************/
|
