ยปCore Development>Code coverage>Modules/zlib/crc32.c

Python code coverage for Modules/zlib/crc32.c

#countcontent
1n/a/* crc32.c -- compute the CRC-32 of a data stream
2n/a * Copyright (C) 1995-2006, 2010, 2011, 2012, 2016 Mark Adler
3n/a * For conditions of distribution and use, see copyright notice in zlib.h
4n/a *
5n/a * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
6n/a * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
7n/a * tables for updating the shift register in one step with three exclusive-ors
8n/a * instead of four steps with four exclusive-ors. This results in about a
9n/a * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
10n/a */
11n/a
12n/a/* @(#) $Id$ */
13n/a
14n/a/*
15n/a Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
16n/a protection on the static variables used to control the first-use generation
17n/a of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
18n/a first call get_crc_table() to initialize the tables before allowing more than
19n/a one thread to use crc32().
20n/a
21n/a DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.
22n/a */
23n/a
24n/a#ifdef MAKECRCH
25n/a# include <stdio.h>
26n/a# ifndef DYNAMIC_CRC_TABLE
27n/a# define DYNAMIC_CRC_TABLE
28n/a# endif /* !DYNAMIC_CRC_TABLE */
29n/a#endif /* MAKECRCH */
30n/a
31n/a#include "zutil.h" /* for STDC and FAR definitions */
32n/a
33n/a/* Definitions for doing the crc four data bytes at a time. */
34n/a#if !defined(NOBYFOUR) && defined(Z_U4)
35n/a# define BYFOUR
36n/a#endif
37n/a#ifdef BYFOUR
38n/a local unsigned long crc32_little OF((unsigned long,
39n/a const unsigned char FAR *, z_size_t));
40n/a local unsigned long crc32_big OF((unsigned long,
41n/a const unsigned char FAR *, z_size_t));
42n/a# define TBLS 8
43n/a#else
44n/a# define TBLS 1
45n/a#endif /* BYFOUR */
46n/a
47n/a/* Local functions for crc concatenation */
48n/alocal unsigned long gf2_matrix_times OF((unsigned long *mat,
49n/a unsigned long vec));
50n/alocal void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
51n/alocal uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
52n/a
53n/a
54n/a#ifdef DYNAMIC_CRC_TABLE
55n/a
56n/alocal volatile int crc_table_empty = 1;
57n/alocal z_crc_t FAR crc_table[TBLS][256];
58n/alocal void make_crc_table OF((void));
59n/a#ifdef MAKECRCH
60n/a local void write_table OF((FILE *, const z_crc_t FAR *));
61n/a#endif /* MAKECRCH */
62n/a/*
63n/a Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
64n/a 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.
65n/a
66n/a Polynomials over GF(2) are represented in binary, one bit per coefficient,
67n/a with the lowest powers in the most significant bit. Then adding polynomials
68n/a is just exclusive-or, and multiplying a polynomial by x is a right shift by
69n/a one. If we call the above polynomial p, and represent a byte as the
70n/a polynomial q, also with the lowest power in the most significant bit (so the
71n/a byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
72n/a where a mod b means the remainder after dividing a by b.
73n/a
74n/a This calculation is done using the shift-register method of multiplying and
75n/a taking the remainder. The register is initialized to zero, and for each
76n/a incoming bit, x^32 is added mod p to the register if the bit is a one (where
77n/a x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
78n/a x (which is shifting right by one and adding x^32 mod p if the bit shifted
79n/a out is a one). We start with the highest power (least significant bit) of
80n/a q and repeat for all eight bits of q.
81n/a
82n/a The first table is simply the CRC of all possible eight bit values. This is
83n/a all the information needed to generate CRCs on data a byte at a time for all
84n/a combinations of CRC register values and incoming bytes. The remaining tables
85n/a allow for word-at-a-time CRC calculation for both big-endian and little-
86n/a endian machines, where a word is four bytes.
87n/a*/
88n/alocal void make_crc_table()
89n/a{
90n/a z_crc_t c;
91n/a int n, k;
92n/a z_crc_t poly; /* polynomial exclusive-or pattern */
93n/a /* terms of polynomial defining this crc (except x^32): */
94n/a static volatile int first = 1; /* flag to limit concurrent making */
95n/a static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
96n/a
97n/a /* See if another task is already doing this (not thread-safe, but better
98n/a than nothing -- significantly reduces duration of vulnerability in
99n/a case the advice about DYNAMIC_CRC_TABLE is ignored) */
100n/a if (first) {
101n/a first = 0;
102n/a
103n/a /* make exclusive-or pattern from polynomial (0xedb88320UL) */
104n/a poly = 0;
105n/a for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
106n/a poly |= (z_crc_t)1 << (31 - p[n]);
107n/a
108n/a /* generate a crc for every 8-bit value */
109n/a for (n = 0; n < 256; n++) {
110n/a c = (z_crc_t)n;
111n/a for (k = 0; k < 8; k++)
112n/a c = c & 1 ? poly ^ (c >> 1) : c >> 1;
113n/a crc_table[0][n] = c;
114n/a }
115n/a
116n/a#ifdef BYFOUR
117n/a /* generate crc for each value followed by one, two, and three zeros,
118n/a and then the byte reversal of those as well as the first table */
119n/a for (n = 0; n < 256; n++) {
120n/a c = crc_table[0][n];
121n/a crc_table[4][n] = ZSWAP32(c);
122n/a for (k = 1; k < 4; k++) {
123n/a c = crc_table[0][c & 0xff] ^ (c >> 8);
124n/a crc_table[k][n] = c;
125n/a crc_table[k + 4][n] = ZSWAP32(c);
126n/a }
127n/a }
128n/a#endif /* BYFOUR */
129n/a
130n/a crc_table_empty = 0;
131n/a }
132n/a else { /* not first */
133n/a /* wait for the other guy to finish (not efficient, but rare) */
134n/a while (crc_table_empty)
135n/a ;
136n/a }
137n/a
138n/a#ifdef MAKECRCH
139n/a /* write out CRC tables to crc32.h */
140n/a {
141n/a FILE *out;
142n/a
143n/a out = fopen("crc32.h", "w");
144n/a if (out == NULL) return;
145n/a fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
146n/a fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
147n/a fprintf(out, "local const z_crc_t FAR ");
148n/a fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
149n/a write_table(out, crc_table[0]);
150n/a# ifdef BYFOUR
151n/a fprintf(out, "#ifdef BYFOUR\n");
152n/a for (k = 1; k < 8; k++) {
153n/a fprintf(out, " },\n {\n");
154n/a write_table(out, crc_table[k]);
155n/a }
156n/a fprintf(out, "#endif\n");
157n/a# endif /* BYFOUR */
158n/a fprintf(out, " }\n};\n");
159n/a fclose(out);
160n/a }
161n/a#endif /* MAKECRCH */
162n/a}
163n/a
164n/a#ifdef MAKECRCH
165n/alocal void write_table(out, table)
166n/a FILE *out;
167n/a const z_crc_t FAR *table;
168n/a{
169n/a int n;
170n/a
171n/a for (n = 0; n < 256; n++)
172n/a fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ",
173n/a (unsigned long)(table[n]),
174n/a n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
175n/a}
176n/a#endif /* MAKECRCH */
177n/a
178n/a#else /* !DYNAMIC_CRC_TABLE */
179n/a/* ========================================================================
180n/a * Tables of CRC-32s of all single-byte values, made by make_crc_table().
181n/a */
182n/a#include "crc32.h"
183n/a#endif /* DYNAMIC_CRC_TABLE */
184n/a
185n/a/* =========================================================================
186n/a * This function can be used by asm versions of crc32()
187n/a */
188n/aconst z_crc_t FAR * ZEXPORT get_crc_table()
189n/a{
190n/a#ifdef DYNAMIC_CRC_TABLE
191n/a if (crc_table_empty)
192n/a make_crc_table();
193n/a#endif /* DYNAMIC_CRC_TABLE */
194n/a return (const z_crc_t FAR *)crc_table;
195n/a}
196n/a
197n/a/* ========================================================================= */
198n/a#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
199n/a#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
200n/a
201n/a/* ========================================================================= */
202n/aunsigned long ZEXPORT crc32_z(crc, buf, len)
203n/a unsigned long crc;
204n/a const unsigned char FAR *buf;
205n/a z_size_t len;
206n/a{
207n/a if (buf == Z_NULL) return 0UL;
208n/a
209n/a#ifdef DYNAMIC_CRC_TABLE
210n/a if (crc_table_empty)
211n/a make_crc_table();
212n/a#endif /* DYNAMIC_CRC_TABLE */
213n/a
214n/a#ifdef BYFOUR
215n/a if (sizeof(void *) == sizeof(ptrdiff_t)) {
216n/a z_crc_t endian;
217n/a
218n/a endian = 1;
219n/a if (*((unsigned char *)(&endian)))
220n/a return crc32_little(crc, buf, len);
221n/a else
222n/a return crc32_big(crc, buf, len);
223n/a }
224n/a#endif /* BYFOUR */
225n/a crc = crc ^ 0xffffffffUL;
226n/a while (len >= 8) {
227n/a DO8;
228n/a len -= 8;
229n/a }
230n/a if (len) do {
231n/a DO1;
232n/a } while (--len);
233n/a return crc ^ 0xffffffffUL;
234n/a}
235n/a
236n/a/* ========================================================================= */
237n/aunsigned long ZEXPORT crc32(crc, buf, len)
238n/a unsigned long crc;
239n/a const unsigned char FAR *buf;
240n/a uInt len;
241n/a{
242n/a return crc32_z(crc, buf, len);
243n/a}
244n/a
245n/a#ifdef BYFOUR
246n/a
247n/a/*
248n/a This BYFOUR code accesses the passed unsigned char * buffer with a 32-bit
249n/a integer pointer type. This violates the strict aliasing rule, where a
250n/a compiler can assume, for optimization purposes, that two pointers to
251n/a fundamentally different types won't ever point to the same memory. This can
252n/a manifest as a problem only if one of the pointers is written to. This code
253n/a only reads from those pointers. So long as this code remains isolated in
254n/a this compilation unit, there won't be a problem. For this reason, this code
255n/a should not be copied and pasted into a compilation unit in which other code
256n/a writes to the buffer that is passed to these routines.
257n/a */
258n/a
259n/a/* ========================================================================= */
260n/a#define DOLIT4 c ^= *buf4++; \
261n/a c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
262n/a crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
263n/a#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
264n/a
265n/a/* ========================================================================= */
266n/alocal unsigned long crc32_little(crc, buf, len)
267n/a unsigned long crc;
268n/a const unsigned char FAR *buf;
269n/a z_size_t len;
270n/a{
271n/a register z_crc_t c;
272n/a register const z_crc_t FAR *buf4;
273n/a
274n/a c = (z_crc_t)crc;
275n/a c = ~c;
276n/a while (len && ((ptrdiff_t)buf & 3)) {
277n/a c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
278n/a len--;
279n/a }
280n/a
281n/a buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
282n/a while (len >= 32) {
283n/a DOLIT32;
284n/a len -= 32;
285n/a }
286n/a while (len >= 4) {
287n/a DOLIT4;
288n/a len -= 4;
289n/a }
290n/a buf = (const unsigned char FAR *)buf4;
291n/a
292n/a if (len) do {
293n/a c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
294n/a } while (--len);
295n/a c = ~c;
296n/a return (unsigned long)c;
297n/a}
298n/a
299n/a/* ========================================================================= */
300n/a#define DOBIG4 c ^= *buf4++; \
301n/a c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
302n/a crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
303n/a#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
304n/a
305n/a/* ========================================================================= */
306n/alocal unsigned long crc32_big(crc, buf, len)
307n/a unsigned long crc;
308n/a const unsigned char FAR *buf;
309n/a z_size_t len;
310n/a{
311n/a register z_crc_t c;
312n/a register const z_crc_t FAR *buf4;
313n/a
314n/a c = ZSWAP32((z_crc_t)crc);
315n/a c = ~c;
316n/a while (len && ((ptrdiff_t)buf & 3)) {
317n/a c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
318n/a len--;
319n/a }
320n/a
321n/a buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
322n/a while (len >= 32) {
323n/a DOBIG32;
324n/a len -= 32;
325n/a }
326n/a while (len >= 4) {
327n/a DOBIG4;
328n/a len -= 4;
329n/a }
330n/a buf = (const unsigned char FAR *)buf4;
331n/a
332n/a if (len) do {
333n/a c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
334n/a } while (--len);
335n/a c = ~c;
336n/a return (unsigned long)(ZSWAP32(c));
337n/a}
338n/a
339n/a#endif /* BYFOUR */
340n/a
341n/a#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
342n/a
343n/a/* ========================================================================= */
344n/alocal unsigned long gf2_matrix_times(mat, vec)
345n/a unsigned long *mat;
346n/a unsigned long vec;
347n/a{
348n/a unsigned long sum;
349n/a
350n/a sum = 0;
351n/a while (vec) {
352n/a if (vec & 1)
353n/a sum ^= *mat;
354n/a vec >>= 1;
355n/a mat++;
356n/a }
357n/a return sum;
358n/a}
359n/a
360n/a/* ========================================================================= */
361n/alocal void gf2_matrix_square(square, mat)
362n/a unsigned long *square;
363n/a unsigned long *mat;
364n/a{
365n/a int n;
366n/a
367n/a for (n = 0; n < GF2_DIM; n++)
368n/a square[n] = gf2_matrix_times(mat, mat[n]);
369n/a}
370n/a
371n/a/* ========================================================================= */
372n/alocal uLong crc32_combine_(crc1, crc2, len2)
373n/a uLong crc1;
374n/a uLong crc2;
375n/a z_off64_t len2;
376n/a{
377n/a int n;
378n/a unsigned long row;
379n/a unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
380n/a unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
381n/a
382n/a /* degenerate case (also disallow negative lengths) */
383n/a if (len2 <= 0)
384n/a return crc1;
385n/a
386n/a /* put operator for one zero bit in odd */
387n/a odd[0] = 0xedb88320UL; /* CRC-32 polynomial */
388n/a row = 1;
389n/a for (n = 1; n < GF2_DIM; n++) {
390n/a odd[n] = row;
391n/a row <<= 1;
392n/a }
393n/a
394n/a /* put operator for two zero bits in even */
395n/a gf2_matrix_square(even, odd);
396n/a
397n/a /* put operator for four zero bits in odd */
398n/a gf2_matrix_square(odd, even);
399n/a
400n/a /* apply len2 zeros to crc1 (first square will put the operator for one
401n/a zero byte, eight zero bits, in even) */
402n/a do {
403n/a /* apply zeros operator for this bit of len2 */
404n/a gf2_matrix_square(even, odd);
405n/a if (len2 & 1)
406n/a crc1 = gf2_matrix_times(even, crc1);
407n/a len2 >>= 1;
408n/a
409n/a /* if no more bits set, then done */
410n/a if (len2 == 0)
411n/a break;
412n/a
413n/a /* another iteration of the loop with odd and even swapped */
414n/a gf2_matrix_square(odd, even);
415n/a if (len2 & 1)
416n/a crc1 = gf2_matrix_times(odd, crc1);
417n/a len2 >>= 1;
418n/a
419n/a /* if no more bits set, then done */
420n/a } while (len2 != 0);
421n/a
422n/a /* return combined crc */
423n/a crc1 ^= crc2;
424n/a return crc1;
425n/a}
426n/a
427n/a/* ========================================================================= */
428n/auLong ZEXPORT crc32_combine(crc1, crc2, len2)
429n/a uLong crc1;
430n/a uLong crc2;
431n/a z_off_t len2;
432n/a{
433n/a return crc32_combine_(crc1, crc2, len2);
434n/a}
435n/a
436n/auLong ZEXPORT crc32_combine64(crc1, crc2, len2)
437n/a uLong crc1;
438n/a uLong crc2;
439n/a z_off64_t len2;
440n/a{
441n/a return crc32_combine_(crc1, crc2, len2);
442n/a}