crc32.c@ 96424

最後變更在這個檔案從96424是 95239,由 vboxsync 提交於 3 年前
libs/zlib: Upgrade to 1.2.12, bugref:8515
屬性 svn:eol-style 設為 `native`
檔案大小: 31.2 KB

行
1	/* crc32.c -- compute the CRC-32 of a data stream
2	* Copyright (C) 1995-2022 Mark Adler
3	* For conditions of distribution and use, see copyright notice in zlib.h
4	*
5	* This interleaved implementation of a CRC makes use of pipelined multiple
6	* arithmetic-logic units, commonly found in modern CPU cores. It is due to
7	* Kadatch and Jenkins (2010). See doc/crc-doc.1.0.pdf in this distribution.
8	*/
9
10	/* @(#) $Id$ */
11
12	/*
13	Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
14	protection on the static variables used to control the first-use generation
15	of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
16	first call get_crc_table() to initialize the tables before allowing more than
17	one thread to use crc32().
18
19	MAKECRCH can be #defined to write out crc32.h. A main() routine is also
20	produced, so that this one source file can be compiled to an executable.
21	*/
22
23	#ifdef MAKECRCH
24	# include <stdio.h>
25	# ifndef DYNAMIC_CRC_TABLE
26	# define DYNAMIC_CRC_TABLE
27	# endif /* !DYNAMIC_CRC_TABLE */
28	#endif /* MAKECRCH */
29
30	#include "zutil.h" /* for Z_U4, Z_U8, z_crc_t, and FAR definitions */
31
32	/*
33	A CRC of a message is computed on N braids of words in the message, where
34	each word consists of W bytes (4 or 8). If N is 3, for example, then three
35	running sparse CRCs are calculated respectively on each braid, at these
36	indices in the array of words: 0, 3, 6, ..., 1, 4, 7, ..., and 2, 5, 8, ...
37	This is done starting at a word boundary, and continues until as many blocks
38	of N * W bytes as are available have been processed. The results are combined
39	into a single CRC at the end. For this code, N must be in the range 1..6 and
40	W must be 4 or 8. The upper limit on N can be increased if desired by adding
41	more #if blocks, extending the patterns apparent in the code. In addition,
42	crc32.h would need to be regenerated, if the maximum N value is increased.
43
44	N and W are chosen empirically by benchmarking the execution time on a given
45	processor. The choices for N and W below were based on testing on Intel Kaby
46	Lake i7, AMD Ryzen 7, ARM Cortex-A57, Sparc64-VII, PowerPC POWER9, and MIPS64
47	Octeon II processors. The Intel, AMD, and ARM processors were all fastest
48	with N=5, W=8. The Sparc, PowerPC, and MIPS64 were all fastest at N=5, W=4.
49	They were all tested with either gcc or clang, all using the -O3 optimization
50	level. Your mileage may vary.
51	*/
52
53	/* Define N */
54	#ifdef Z_TESTN
55	# define N Z_TESTN
56	#else
57	# define N 5
58	#endif
59	#if N < 1 \|\| N > 6
60	# error N must be in 1..6
61	#endif
62
63	/*
64	z_crc_t must be at least 32 bits. z_word_t must be at least as long as
65	z_crc_t. It is assumed here that z_word_t is either 32 bits or 64 bits, and
66	that bytes are eight bits.
67	*/
68
69	/*
70	Define W and the associated z_word_t type. If W is not defined, then a
71	braided calculation is not used, and the associated tables and code are not
72	compiled.
73	*/
74	#ifdef Z_TESTW
75	# if Z_TESTW-1 != -1
76	# define W Z_TESTW
77	# endif
78	#else
79	# ifdef MAKECRCH
80	# define W 8 /* required for MAKECRCH */
81	# else
82	# if defined(__x86_64__) \|\| defined(__aarch64__)
83	# define W 8
84	# else
85	# define W 4
86	# endif
87	# endif
88	#endif
89	#ifdef W
90	# if W == 8 && defined(Z_U8)
91	typedef Z_U8 z_word_t;
92	# elif defined(Z_U4)
93	# undef W
94	# define W 4
95	typedef Z_U4 z_word_t;
96	# else
97	# undef W
98	# endif
99	#endif
100
101	/* Local functions. */
102	local z_crc_t multmodp OF((z_crc_t a, z_crc_t b));
103	local z_crc_t x2nmodp OF((z_off64_t n, unsigned k));
104
105	/* If available, use the ARM processor CRC32 instruction. */
106	#if defined(__aarch64__) && defined(__ARM_FEATURE_CRC32) && W == 8
107	# define ARMCRC32
108	#endif
109
110	#if defined(W) && (!defined(ARMCRC32) \|\| defined(DYNAMIC_CRC_TABLE))
111	/*
112	Swap the bytes in a z_word_t to convert between little and big endian. Any
113	self-respecting compiler will optimize this to a single machine byte-swap
114	instruction, if one is available. This assumes that word_t is either 32 bits
115	or 64 bits.
116	*/
117	local z_word_t byte_swap(word)
118	z_word_t word;
119	{
120	# if W == 8
121	return
122	(word & 0xff00000000000000) >> 56 \|
123	(word & 0xff000000000000) >> 40 \|
124	(word & 0xff0000000000) >> 24 \|
125	(word & 0xff00000000) >> 8 \|
126	(word & 0xff000000) << 8 \|
127	(word & 0xff0000) << 24 \|
128	(word & 0xff00) << 40 \|
129	(word & 0xff) << 56;
130	# else /* W == 4 */
131	return
132	(word & 0xff000000) >> 24 \|
133	(word & 0xff0000) >> 8 \|
134	(word & 0xff00) << 8 \|
135	(word & 0xff) << 24;
136	# endif
137	}
138	#endif
139
140	/* CRC polynomial. */
141	#define POLY 0xedb88320 /* p(x) reflected, with x^32 implied */
142
143	#ifdef DYNAMIC_CRC_TABLE
144
145	local z_crc_t FAR crc_table[256];
146	local z_crc_t FAR x2n_table[32];
147	local void make_crc_table OF((void));
148	#ifdef W
149	local z_word_t FAR crc_big_table[256];
150	local z_crc_t FAR crc_braid_table[W][256];
151	local z_word_t FAR crc_braid_big_table[W][256];
152	local void braid OF((z_crc_t [][256], z_word_t [][256], int, int));
153	#endif
154	#ifdef MAKECRCH
155	local void write_table OF((FILE , const z_crc_t FAR , int));
156	local void write_table32hi OF((FILE , const z_word_t FAR , int));
157	local void write_table64 OF((FILE , const z_word_t FAR , int));
158	#endif /* MAKECRCH */
159
160	/*
161	Define a once() function depending on the availability of atomics. If this is
162	compiled with DYNAMIC_CRC_TABLE defined, and if CRCs will be computed in
163	multiple threads, and if atomics are not available, then get_crc_table() must
164	be called to initialize the tables and must return before any threads are
165	allowed to compute or combine CRCs.
166	*/
167
168	/* Definition of once functionality. */
169	typedef struct once_s once_t;
170	local void once OF((once_t , void ()(void)));
171
172	/* Check for the availability of atomics. */
173	#if defined(__STDC__) && __STDC_VERSION__ >= 201112L && \
174	!defined(__STDC_NO_ATOMICS__)
175
176	#include <stdatomic.h>
177
178	/* Structure for once(), which must be initialized with ONCE_INIT. */
179	struct once_s {
180	atomic_flag begun;
181	atomic_int done;
182	};
183	#define ONCE_INIT {ATOMIC_FLAG_INIT, 0}
184
185	/*
186	Run the provided init() function exactly once, even if multiple threads
187	invoke once() at the same time. The state must be a once_t initialized with
188	ONCE_INIT.
189	*/
190	local void once(state, init)
191	once_t *state;
192	void (*init)(void);
193	{
194	if (!atomic_load(&state->done)) {
195	if (atomic_flag_test_and_set(&state->begun))
196	while (!atomic_load(&state->done))
197	;
198	else {
199	init();
200	atomic_store(&state->done, 1);
201	}
202	}
203	}
204
205	#else /* no atomics */
206
207	/* Structure for once(), which must be initialized with ONCE_INIT. */
208	struct once_s {
209	volatile int begun;
210	volatile int done;
211	};
212	#define ONCE_INIT {0, 0}
213
214	/* Test and set. Alas, not atomic, but tries to minimize the period of
215	vulnerability. */
216	local int test_and_set OF((int volatile *));
217	local int test_and_set(flag)
218	int volatile *flag;
219	{
220	int was;
221
222	was = *flag;
223	*flag = 1;
224	return was;
225	}
226
227	/* Run the provided init() function once. This is not thread-safe. */
228	local void once(state, init)
229	once_t *state;
230	void (*init)(void);
231	{
232	if (!state->done) {
233	if (test_and_set(&state->begun))
234	while (!state->done)
235	;
236	else {
237	init();
238	state->done = 1;
239	}
240	}
241	}
242
243	#endif
244
245	/* State for once(). */
246	local once_t made = ONCE_INIT;
247
248	/*
249	Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
250	x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.
251
252	Polynomials over GF(2) are represented in binary, one bit per coefficient,
253	with the lowest powers in the most significant bit. Then adding polynomials
254	is just exclusive-or, and multiplying a polynomial by x is a right shift by
255	one. If we call the above polynomial p, and represent a byte as the
256	polynomial q, also with the lowest power in the most significant bit (so the
257	byte 0xb1 is the polynomial x^7+x^3+x^2+1), then the CRC is (q*x^32) mod p,
258	where a mod b means the remainder after dividing a by b.
259
260	This calculation is done using the shift-register method of multiplying and
261	taking the remainder. The register is initialized to zero, and for each
262	incoming bit, x^32 is added mod p to the register if the bit is a one (where
263	x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x
264	(which is shifting right by one and adding x^32 mod p if the bit shifted out
265	is a one). We start with the highest power (least significant bit) of q and
266	repeat for all eight bits of q.
267
268	The table is simply the CRC of all possible eight bit values. This is all the
269	information needed to generate CRCs on data a byte at a time for all
270	combinations of CRC register values and incoming bytes.
271	*/
272
273	local void make_crc_table()
274	{
275	unsigned i, j, n;
276	z_crc_t p;
277
278	/* initialize the CRC of bytes tables */
279	for (i = 0; i < 256; i++) {
280	p = i;
281	for (j = 0; j < 8; j++)
282	p = p & 1 ? (p >> 1) ^ POLY : p >> 1;
283	crc_table[i] = p;
284	#ifdef W
285	crc_big_table[i] = byte_swap(p);
286	#endif
287	}
288
289	/* initialize the x^2^n mod p(x) table */
290	p = (z_crc_t)1 << 30; /* x^1 */
291	x2n_table[0] = p;
292	for (n = 1; n < 32; n++)
293	x2n_table[n] = p = multmodp(p, p);
294
295	#ifdef W
296	/* initialize the braiding tables -- needs x2n_table[] */
297	braid(crc_braid_table, crc_braid_big_table, N, W);
298	#endif
299
300	#ifdef MAKECRCH
301	{
302	/*
303	The crc32.h header file contains tables for both 32-bit and 64-bit
304	z_word_t's, and so requires a 64-bit type be available. In that case,
305	z_word_t must be defined to be 64-bits. This code then also generates
306	and writes out the tables for the case that z_word_t is 32 bits.
307	*/
308	#if !defined(W) \|\| W != 8
309	# error Need a 64-bit integer type in order to generate crc32.h.
310	#endif
311	FILE *out;
312	int k, n;
313	z_crc_t ltl[8][256];
314	z_word_t big[8][256];
315
316	out = fopen("crc32.h", "w");
317	if (out == NULL) return;
318
319	/* write out little-endian CRC table to crc32.h */
320	fprintf(out,
321	"/* crc32.h -- tables for rapid CRC calculation\n"
322	" * Generated automatically by crc32.c\n */\n"
323	"\n"
324	"local const z_crc_t FAR crc_table[] = {\n"
325	" ");
326	write_table(out, crc_table, 256);
327	fprintf(out,
328	"};\n");
329
330	/* write out big-endian CRC table for 64-bit z_word_t to crc32.h */
331	fprintf(out,
332	"\n"
333	"#ifdef W\n"
334	"\n"
335	"#if W == 8\n"
336	"\n"
337	"local const z_word_t FAR crc_big_table[] = {\n"
338	" ");
339	write_table64(out, crc_big_table, 256);
340	fprintf(out,
341	"};\n");
342
343	/* write out big-endian CRC table for 32-bit z_word_t to crc32.h */
344	fprintf(out,
345	"\n"
346	"#else /* W == 4 */\n"
347	"\n"
348	"local const z_word_t FAR crc_big_table[] = {\n"
349	" ");
350	write_table32hi(out, crc_big_table, 256);
351	fprintf(out,
352	"};\n"
353	"\n"
354	"#endif\n");
355
356	/* write out braid tables for each value of N */
357	for (n = 1; n <= 6; n++) {
358	fprintf(out,
359	"\n"
360	"#if N == %d\n", n);
361
362	/* compute braid tables for this N and 64-bit word_t */
363	braid(ltl, big, n, 8);
364
365	/* write out braid tables for 64-bit z_word_t to crc32.h */
366	fprintf(out,
367	"\n"
368	"#if W == 8\n"
369	"\n"
370	"local const z_crc_t FAR crc_braid_table[][256] = {\n");
371	for (k = 0; k < 8; k++) {
372	fprintf(out, " {");
373	write_table(out, ltl[k], 256);
374	fprintf(out, "}%s", k < 7 ? ",\n" : "");
375	}
376	fprintf(out,
377	"};\n"
378	"\n"
379	"local const z_word_t FAR crc_braid_big_table[][256] = {\n");
380	for (k = 0; k < 8; k++) {
381	fprintf(out, " {");
382	write_table64(out, big[k], 256);
383	fprintf(out, "}%s", k < 7 ? ",\n" : "");
384	}
385	fprintf(out,
386	"};\n");
387
388	/* compute braid tables for this N and 32-bit word_t */
389	braid(ltl, big, n, 4);
390
391	/* write out braid tables for 32-bit z_word_t to crc32.h */
392	fprintf(out,
393	"\n"
394	"#else /* W == 4 */\n"
395	"\n"
396	"local const z_crc_t FAR crc_braid_table[][256] = {\n");
397	for (k = 0; k < 4; k++) {
398	fprintf(out, " {");
399	write_table(out, ltl[k], 256);
400	fprintf(out, "}%s", k < 3 ? ",\n" : "");
401	}
402	fprintf(out,
403	"};\n"
404	"\n"
405	"local const z_word_t FAR crc_braid_big_table[][256] = {\n");
406	for (k = 0; k < 4; k++) {
407	fprintf(out, " {");
408	write_table32hi(out, big[k], 256);
409	fprintf(out, "}%s", k < 3 ? ",\n" : "");
410	}
411	fprintf(out,
412	"};\n"
413	"\n"
414	"#endif\n"
415	"\n"
416	"#endif\n");
417	}
418	fprintf(out,
419	"\n"
420	"#endif\n");
421
422	/* write out zeros operator table to crc32.h */
423	fprintf(out,
424	"\n"
425	"local const z_crc_t FAR x2n_table[] = {\n"
426	" ");
427	write_table(out, x2n_table, 32);
428	fprintf(out,
429	"};\n");
430	fclose(out);
431	}
432	#endif /* MAKECRCH */
433	}
434
435	#ifdef MAKECRCH
436
437	/*
438	Write the 32-bit values in table[0..k-1] to out, five per line in
439	hexadecimal separated by commas.
440	*/
441	local void write_table(out, table, k)
442	FILE *out;
443	const z_crc_t FAR *table;
444	int k;
445	{
446	int n;
447
448	for (n = 0; n < k; n++)
449	fprintf(out, "%s0x%08lx%s", n == 0 \|\| n % 5 ? "" : " ",
450	(unsigned long)(table[n]),
451	n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
452	}
453
454	/*
455	Write the high 32-bits of each value in table[0..k-1] to out, five per line
456	in hexadecimal separated by commas.
457	*/
458	local void write_table32hi(out, table, k)
459	FILE *out;
460	const z_word_t FAR *table;
461	int k;
462	{
463	int n;
464
465	for (n = 0; n < k; n++)
466	fprintf(out, "%s0x%08lx%s", n == 0 \|\| n % 5 ? "" : " ",
467	(unsigned long)(table[n] >> 32),
468	n == k - 1 ? "" : (n % 5 == 4 ? ",\n" : ", "));
469	}
470
471	/*
472	Write the 64-bit values in table[0..k-1] to out, three per line in
473	hexadecimal separated by commas. This assumes that if there is a 64-bit
474	type, then there is also a long long integer type, and it is at least 64
475	bits. If not, then the type cast and format string can be adjusted
476	accordingly.
477	*/
478	local void write_table64(out, table, k)
479	FILE *out;
480	const z_word_t FAR *table;
481	int k;
482	{
483	int n;
484
485	for (n = 0; n < k; n++)
486	fprintf(out, "%s0x%016llx%s", n == 0 \|\| n % 3 ? "" : " ",
487	(unsigned long long)(table[n]),
488	n == k - 1 ? "" : (n % 3 == 2 ? ",\n" : ", "));
489	}
490
491	/* Actually do the deed. */
492	int main()
493	{
494	make_crc_table();
495	return 0;
496	}
497
498	#endif /* MAKECRCH */
499
500	#ifdef W
501	/*
502	Generate the little and big-endian braid tables for the given n and z_word_t
503	size w. Each array must have room for w blocks of 256 elements.
504	*/
505	local void braid(ltl, big, n, w)
506	z_crc_t ltl[][256];
507	z_word_t big[][256];
508	int n;
509	int w;
510	{
511	int k;
512	z_crc_t i, p, q;
513	for (k = 0; k < w; k++) {
514	p = x2nmodp((n * w + 3 - k) << 3, 0);
515	ltl[k][0] = 0;
516	big[w - 1 - k][0] = 0;
517	for (i = 1; i < 256; i++) {
518	ltl[k][i] = q = multmodp(i << 24, p);
519	big[w - 1 - k][i] = byte_swap(q);
520	}
521	}
522	}
523	#endif
524
525	#else /* !DYNAMIC_CRC_TABLE */
526	/* ========================================================================
527	* Tables for byte-wise and braided CRC-32 calculations, and a table of powers
528	* of x for combining CRC-32s, all made by make_crc_table().
529	*/
530	#include "crc32.h"
531	#endif /* DYNAMIC_CRC_TABLE */
532
533	/* ========================================================================
534	* Routines used for CRC calculation. Some are also required for the table
535	* generation above.
536	*/
537
538	/*
539	Return a(x) multiplied by b(x) modulo p(x), where p(x) is the CRC polynomial,
540	reflected. For speed, this requires that a not be zero.
541	*/
542	local z_crc_t multmodp(a, b)
543	z_crc_t a;
544	z_crc_t b;
545	{
546	z_crc_t m, p;
547
548	m = (z_crc_t)1 << 31;
549	p = 0;
550	for (;;) {
551	if (a & m) {
552	p ^= b;
553	if ((a & (m - 1)) == 0)
554	break;
555	}
556	m >>= 1;
557	b = b & 1 ? (b >> 1) ^ POLY : b >> 1;
558	}
559	return p;
560	}
561
562	/*
563	Return x^(n * 2^k) modulo p(x). Requires that x2n_table[] has been
564	initialized.
565	*/
566	local z_crc_t x2nmodp(n, k)
567	z_off64_t n;
568	unsigned k;
569	{
570	z_crc_t p;
571
572	p = (z_crc_t)1 << 31; /* x^0 == 1 */
573	while (n) {
574	if (n & 1)
575	p = multmodp(x2n_table[k & 31], p);
576	n >>= 1;
577	k++;
578	}
579	return p;
580	}
581
582	/* =========================================================================
583	* This function can be used by asm versions of crc32(), and to force the
584	* generation of the CRC tables in a threaded application.
585	*/
586	const z_crc_t FAR * ZEXPORT get_crc_table()
587	{
588	#ifdef DYNAMIC_CRC_TABLE
589	once(&made, make_crc_table);
590	#endif /* DYNAMIC_CRC_TABLE */
591	return (const z_crc_t FAR *)crc_table;
592	}
593
594	/* =========================================================================
595	* Use ARM machine instructions if available. This will compute the CRC about
596	* ten times faster than the braided calculation. This code does not check for
597	* the presence of the CRC instruction at run time. __ARM_FEATURE_CRC32 will
598	* only be defined if the compilation specifies an ARM processor architecture
599	* that has the instructions. For example, compiling with -march=armv8.1-a or
600	* -march=armv8-a+crc, or -march=native if the compile machine has the crc32
601	* instructions.
602	*/
603	#ifdef ARMCRC32
604
605	/*
606	Constants empirically determined to maximize speed. These values are from
607	measurements on a Cortex-A57. Your mileage may vary.
608	*/
609	#define Z_BATCH 3990 /* number of words in a batch */
610	#define Z_BATCH_ZEROS 0xa10d3d0c /* computed from Z_BATCH = 3990 */
611	#define Z_BATCH_MIN 800 /* fewest words in a final batch */
612
613	unsigned long ZEXPORT crc32_z(crc, buf, len)
614	unsigned long crc;
615	const unsigned char FAR *buf;
616	z_size_t len;
617	{
618	z_crc_t val;
619	z_word_t crc1, crc2;
620	const z_word_t *word;
621	z_word_t val0, val1, val2;
622	z_size_t last, last2, i;
623	z_size_t num;
624
625	/* Return initial CRC, if requested. */
626	if (buf == Z_NULL) return 0;
627
628	#ifdef DYNAMIC_CRC_TABLE
629	once(&made, make_crc_table);
630	#endif /* DYNAMIC_CRC_TABLE */
631
632	/* Pre-condition the CRC */
633	crc ^= 0xffffffff;
634
635	/* Compute the CRC up to a word boundary. */
636	while (len && ((z_size_t)buf & 7) != 0) {
637	len--;
638	val = *buf++;
639	__asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val));
640	}
641
642	/* Prepare to compute the CRC on full 64-bit words word[0..num-1]. */
643	word = (z_word_t const *)buf;
644	num = len >> 3;
645	len &= 7;
646
647	/* Do three interleaved CRCs to realize the throughput of one crc32x
648	instruction per cycle. Each CRC is calcuated on Z_BATCH words. The three
649	CRCs are combined into a single CRC after each set of batches. */
650	while (num >= 3 * Z_BATCH) {
651	crc1 = 0;
652	crc2 = 0;
653	for (i = 0; i < Z_BATCH; i++) {
654	val0 = word[i];
655	val1 = word[i + Z_BATCH];
656	val2 = word[i + 2 * Z_BATCH];
657	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
658	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1));
659	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2));
660	}
661	word += 3 * Z_BATCH;
662	num -= 3 * Z_BATCH;
663	crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc1;
664	crc = multmodp(Z_BATCH_ZEROS, crc) ^ crc2;
665	}
666
667	/* Do one last smaller batch with the remaining words, if there are enough
668	to pay for the combination of CRCs. */
669	last = num / 3;
670	if (last >= Z_BATCH_MIN) {
671	last2 = last << 1;
672	crc1 = 0;
673	crc2 = 0;
674	for (i = 0; i < last; i++) {
675	val0 = word[i];
676	val1 = word[i + last];
677	val2 = word[i + last2];
678	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
679	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc1) : "r"(val1));
680	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc2) : "r"(val2));
681	}
682	word += 3 * last;
683	num -= 3 * last;
684	val = x2nmodp(last, 6);
685	crc = multmodp(val, crc) ^ crc1;
686	crc = multmodp(val, crc) ^ crc2;
687	}
688
689	/* Compute the CRC on any remaining words. */
690	for (i = 0; i < num; i++) {
691	val0 = word[i];
692	__asm__ volatile("crc32x %w0, %w0, %x1" : "+r"(crc) : "r"(val0));
693	}
694	word += num;
695
696	/* Complete the CRC on any remaining bytes. */
697	buf = (const unsigned char FAR *)word;
698	while (len) {
699	len--;
700	val = *buf++;
701	__asm__ volatile("crc32b %w0, %w0, %w1" : "+r"(crc) : "r"(val));
702	}
703
704	/* Return the CRC, post-conditioned. */
705	return crc ^ 0xffffffff;
706	}
707
708	#else
709
710	#ifdef W
711
712	/*
713	Return the CRC of the W bytes in the word_t data, taking the
714	least-significant byte of the word as the first byte of data, without any pre
715	or post conditioning. This is used to combine the CRCs of each braid.
716	*/
717	local z_crc_t crc_word(data)
718	z_word_t data;
719	{
720	int k;
721	for (k = 0; k < W; k++)
722	data = (data >> 8) ^ crc_table[data & 0xff];
723	return (z_crc_t)data;
724	}
725
726	local z_word_t crc_word_big(data)
727	z_word_t data;
728	{
729	int k;
730	for (k = 0; k < W; k++)
731	data = (data << 8) ^
732	crc_big_table[(data >> ((W - 1) << 3)) & 0xff];
733	return data;
734	}
735
736	#endif
737
738	/* ========================================================================= */
739	unsigned long ZEXPORT crc32_z(crc, buf, len)
740	unsigned long crc;
741	const unsigned char FAR *buf;
742	z_size_t len;
743	{
744	/* Return initial CRC, if requested. */
745	if (buf == Z_NULL) return 0;
746
747	#ifdef DYNAMIC_CRC_TABLE
748	once(&made, make_crc_table);
749	#endif /* DYNAMIC_CRC_TABLE */
750
751	/* Pre-condition the CRC */
752	crc ^= 0xffffffff;
753
754	#ifdef W
755
756	/* If provided enough bytes, do a braided CRC calculation. */
757	if (len >= N * W + W - 1) {
758	z_size_t blks;
759	z_word_t const *words;
760	unsigned endian;
761	int k;
762
763	/* Compute the CRC up to a z_word_t boundary. */
764	while (len && ((z_size_t)buf & (W - 1)) != 0) {
765	len--;
766	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
767	}
768
769	/* Compute the CRC on as many N z_word_t blocks as are available. */
770	blks = len / (N * W);
771	len -= blks * N * W;
772	words = (z_word_t const *)buf;
773
774	/* Do endian check at execution time instead of compile time, since ARM
775	processors can change the endianess at execution time. If the
776	compiler knows what the endianess will be, it can optimize out the
777	check and the unused branch. */
778	endian = 1;
779	if ((unsigned char )&endian) {
780	/* Little endian. */
781
782	z_crc_t crc0;
783	z_word_t word0;
784	#if N > 1
785	z_crc_t crc1;
786	z_word_t word1;
787	#if N > 2
788	z_crc_t crc2;
789	z_word_t word2;
790	#if N > 3
791	z_crc_t crc3;
792	z_word_t word3;
793	#if N > 4
794	z_crc_t crc4;
795	z_word_t word4;
796	#if N > 5
797	z_crc_t crc5;
798	z_word_t word5;
799	#endif
800	#endif
801	#endif
802	#endif
803	#endif
804
805	/* Initialize the CRC for each braid. */
806	crc0 = crc;
807	#if N > 1
808	crc1 = 0;
809	#if N > 2
810	crc2 = 0;
811	#if N > 3
812	crc3 = 0;
813	#if N > 4
814	crc4 = 0;
815	#if N > 5
816	crc5 = 0;
817	#endif
818	#endif
819	#endif
820	#endif
821	#endif
822
823	/*
824	Process the first blks-1 blocks, computing the CRCs on each braid
825	independently.
826	*/
827	while (--blks) {
828	/* Load the word for each braid into registers. */
829	word0 = crc0 ^ words[0];
830	#if N > 1
831	word1 = crc1 ^ words[1];
832	#if N > 2
833	word2 = crc2 ^ words[2];
834	#if N > 3
835	word3 = crc3 ^ words[3];
836	#if N > 4
837	word4 = crc4 ^ words[4];
838	#if N > 5
839	word5 = crc5 ^ words[5];
840	#endif
841	#endif
842	#endif
843	#endif
844	#endif
845	words += N;
846
847	/* Compute and update the CRC for each word. The loop should
848	get unrolled. */
849	crc0 = crc_braid_table[0][word0 & 0xff];
850	#if N > 1
851	crc1 = crc_braid_table[0][word1 & 0xff];
852	#if N > 2
853	crc2 = crc_braid_table[0][word2 & 0xff];
854	#if N > 3
855	crc3 = crc_braid_table[0][word3 & 0xff];
856	#if N > 4
857	crc4 = crc_braid_table[0][word4 & 0xff];
858	#if N > 5
859	crc5 = crc_braid_table[0][word5 & 0xff];
860	#endif
861	#endif
862	#endif
863	#endif
864	#endif
865	for (k = 1; k < W; k++) {
866	crc0 ^= crc_braid_table[k][(word0 >> (k << 3)) & 0xff];
867	#if N > 1
868	crc1 ^= crc_braid_table[k][(word1 >> (k << 3)) & 0xff];
869	#if N > 2
870	crc2 ^= crc_braid_table[k][(word2 >> (k << 3)) & 0xff];
871	#if N > 3
872	crc3 ^= crc_braid_table[k][(word3 >> (k << 3)) & 0xff];
873	#if N > 4
874	crc4 ^= crc_braid_table[k][(word4 >> (k << 3)) & 0xff];
875	#if N > 5
876	crc5 ^= crc_braid_table[k][(word5 >> (k << 3)) & 0xff];
877	#endif
878	#endif
879	#endif
880	#endif
881	#endif
882	}
883	}
884
885	/*
886	Process the last block, combining the CRCs of the N braids at the
887	same time.
888	*/
889	crc = crc_word(crc0 ^ words[0]);
890	#if N > 1
891	crc = crc_word(crc1 ^ words[1] ^ crc);
892	#if N > 2
893	crc = crc_word(crc2 ^ words[2] ^ crc);
894	#if N > 3
895	crc = crc_word(crc3 ^ words[3] ^ crc);
896	#if N > 4
897	crc = crc_word(crc4 ^ words[4] ^ crc);
898	#if N > 5
899	crc = crc_word(crc5 ^ words[5] ^ crc);
900	#endif
901	#endif
902	#endif
903	#endif
904	#endif
905	words += N;
906	}
907	else {
908	/* Big endian. */
909
910	z_word_t crc0, word0, comb;
911	#if N > 1
912	z_word_t crc1, word1;
913	#if N > 2
914	z_word_t crc2, word2;
915	#if N > 3
916	z_word_t crc3, word3;
917	#if N > 4
918	z_word_t crc4, word4;
919	#if N > 5
920	z_word_t crc5, word5;
921	#endif
922	#endif
923	#endif
924	#endif
925	#endif
926
927	/* Initialize the CRC for each braid. */
928	crc0 = byte_swap(crc);
929	#if N > 1
930	crc1 = 0;
931	#if N > 2
932	crc2 = 0;
933	#if N > 3
934	crc3 = 0;
935	#if N > 4
936	crc4 = 0;
937	#if N > 5
938	crc5 = 0;
939	#endif
940	#endif
941	#endif
942	#endif
943	#endif
944
945	/*
946	Process the first blks-1 blocks, computing the CRCs on each braid
947	independently.
948	*/
949	while (--blks) {
950	/* Load the word for each braid into registers. */
951	word0 = crc0 ^ words[0];
952	#if N > 1
953	word1 = crc1 ^ words[1];
954	#if N > 2
955	word2 = crc2 ^ words[2];
956	#if N > 3
957	word3 = crc3 ^ words[3];
958	#if N > 4
959	word4 = crc4 ^ words[4];
960	#if N > 5
961	word5 = crc5 ^ words[5];
962	#endif
963	#endif
964	#endif
965	#endif
966	#endif
967	words += N;
968
969	/* Compute and update the CRC for each word. The loop should
970	get unrolled. */
971	crc0 = crc_braid_big_table[0][word0 & 0xff];
972	#if N > 1
973	crc1 = crc_braid_big_table[0][word1 & 0xff];
974	#if N > 2
975	crc2 = crc_braid_big_table[0][word2 & 0xff];
976	#if N > 3
977	crc3 = crc_braid_big_table[0][word3 & 0xff];
978	#if N > 4
979	crc4 = crc_braid_big_table[0][word4 & 0xff];
980	#if N > 5
981	crc5 = crc_braid_big_table[0][word5 & 0xff];
982	#endif
983	#endif
984	#endif
985	#endif
986	#endif
987	for (k = 1; k < W; k++) {
988	crc0 ^= crc_braid_big_table[k][(word0 >> (k << 3)) & 0xff];
989	#if N > 1
990	crc1 ^= crc_braid_big_table[k][(word1 >> (k << 3)) & 0xff];
991	#if N > 2
992	crc2 ^= crc_braid_big_table[k][(word2 >> (k << 3)) & 0xff];
993	#if N > 3
994	crc3 ^= crc_braid_big_table[k][(word3 >> (k << 3)) & 0xff];
995	#if N > 4
996	crc4 ^= crc_braid_big_table[k][(word4 >> (k << 3)) & 0xff];
997	#if N > 5
998	crc5 ^= crc_braid_big_table[k][(word5 >> (k << 3)) & 0xff];
999	#endif
1000	#endif
1001	#endif
1002	#endif
1003	#endif
1004	}
1005	}
1006
1007	/*
1008	Process the last block, combining the CRCs of the N braids at the
1009	same time.
1010	*/
1011	comb = crc_word_big(crc0 ^ words[0]);
1012	#if N > 1
1013	comb = crc_word_big(crc1 ^ words[1] ^ comb);
1014	#if N > 2
1015	comb = crc_word_big(crc2 ^ words[2] ^ comb);
1016	#if N > 3
1017	comb = crc_word_big(crc3 ^ words[3] ^ comb);
1018	#if N > 4
1019	comb = crc_word_big(crc4 ^ words[4] ^ comb);
1020	#if N > 5
1021	comb = crc_word_big(crc5 ^ words[5] ^ comb);
1022	#endif
1023	#endif
1024	#endif
1025	#endif
1026	#endif
1027	words += N;
1028	crc = byte_swap(comb);
1029	}
1030
1031	/*
1032	Update the pointer to the remaining bytes to process.
1033	*/
1034	buf = (unsigned char const *)words;
1035	}
1036
1037	#endif /* W */
1038
1039	/* Complete the computation of the CRC on any remaining bytes. */
1040	while (len >= 8) {
1041	len -= 8;
1042	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1043	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1044	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1045	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1046	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1047	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1048	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1049	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1050	}
1051	while (len) {
1052	len--;
1053	crc = (crc >> 8) ^ crc_table[(crc ^ *buf++) & 0xff];
1054	}
1055
1056	/* Return the CRC, post-conditioned. */
1057	return crc ^ 0xffffffff;
1058	}
1059
1060	#endif
1061
1062	/* ========================================================================= */
1063	unsigned long ZEXPORT crc32(crc, buf, len)
1064	unsigned long crc;
1065	const unsigned char FAR *buf;
1066	uInt len;
1067	{
1068	return crc32_z(crc, buf, len);
1069	}
1070
1071	/* ========================================================================= */
1072	uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
1073	uLong crc1;
1074	uLong crc2;
1075	z_off64_t len2;
1076	{
1077	#ifdef DYNAMIC_CRC_TABLE
1078	once(&made, make_crc_table);
1079	#endif /* DYNAMIC_CRC_TABLE */
1080	return multmodp(x2nmodp(len2, 3), crc1) ^ crc2;
1081	}
1082
1083	/* ========================================================================= */
1084	uLong ZEXPORT crc32_combine(crc1, crc2, len2)
1085	uLong crc1;
1086	uLong crc2;
1087	z_off_t len2;
1088	{
1089	return crc32_combine64(crc1, crc2, len2);
1090	}
1091
1092	/* ========================================================================= */
1093	uLong ZEXPORT crc32_combine_gen64(len2)
1094	z_off64_t len2;
1095	{
1096	#ifdef DYNAMIC_CRC_TABLE
1097	once(&made, make_crc_table);
1098	#endif /* DYNAMIC_CRC_TABLE */
1099	return x2nmodp(len2, 3);
1100	}
1101
1102	/* ========================================================================= */
1103	uLong ZEXPORT crc32_combine_gen(len2)
1104	z_off_t len2;
1105	{
1106	return crc32_combine_gen64(len2);
1107	}
1108
1109	/* ========================================================================= */
1110	uLong crc32_combine_op(crc1, crc2, op)
1111	uLong crc1;
1112	uLong crc2;
1113	uLong op;
1114	{
1115	return multmodp(op, crc1) ^ crc2;
1116	}

注意: 瀏覽 TracBrowser 來幫助您使用儲存庫瀏覽器

source: vbox/trunk/src/libs/zlib-1.2.12/crc32.c@ 96424

以其他格式下載: