File Coverage

cpan/Compress-Raw-Zlib/crc32.c
Criterion Covered Total %
statement 10 43 23.3
branch n/a
condition n/a
subroutine n/a
total 10 43 23.3


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