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 <rbrown64@csc.com.au> 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 <stdio.h>
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 *, z_size_t));
42 local unsigned long crc32_big OF((unsigned long,
43 const unsigned char FAR *, z_size_t));
44# define TBLS 8
45#else
46# define TBLS 1
47#endif /* BYFOUR */
48
49/* Local functions for crc concatenation */
50local unsigned long gf2_matrix_times OF((unsigned long *mat,
51 unsigned long vec));
52local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
53local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
54
55
56#ifdef DYNAMIC_CRC_TABLE
57
58local volatile int crc_table_empty = 1;
59local z_crc_t FAR crc_table[TBLS][256];
60local 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*/
90local 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
167local void write_table(out, 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 */
190const 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 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/* ========================================================================= */
204unsigned long ZEXPORT crc32_z(crc, buf, len)
205 unsigned long crc;
206 const unsigned char FAR *buf;
207 z_size_t len;
208{
209 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 crc = crc ^ 0xffffffffUL;
228 while (len >= 8) {
229 DO8;
230 len -= 8;
231 }
232 if (len) do {
233 DO1;
234 } while (--len);
235 return crc ^ 0xffffffffUL;
236}
237
238/* ========================================================================= */
239unsigned long ZEXPORT crc32(crc, buf, len)
240 unsigned long crc;
241 const unsigned char FAR *buf;
242 uInt len;
243{
244 return crc32_z(crc, buf, len);
245}
246
247#ifdef BYFOUR
248
249/*
250 This BYFOUR code accesses the passed unsigned char * buffer with a 32-bit
251 integer pointer type. This violates the strict aliasing rule, where a
252 compiler can assume, for optimization purposes, that two pointers to
253 fundamentally different types won't ever point to the same memory. This can
254 manifest as a problem only if one of the pointers is written to. This code
255 only reads from those pointers. So long as this code remains isolated in
256 this compilation unit, there won't be a problem. For this reason, this code
257 should not be copied and pasted into a compilation unit in which other code
258 writes to the buffer that is passed to these routines.
259 */
260
261/* ========================================================================= */
262#define DOLIT4 c ^= *buf4++; \
263 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
264 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
265#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
266
267/* ========================================================================= */
268local unsigned long crc32_little(crc, buf, len)
269 unsigned long crc;
270 const unsigned char FAR *buf;
271 z_size_t len;
272{
273 register z_crc_t c;
274 register const z_crc_t FAR *buf4;
275
276 c = (z_crc_t)crc;
277 c = ~c;
278 while (len && ((ptrdiff_t)buf & 3)) {
279 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
280 len--;
281 }
282
283 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
284 while (len >= 32) {
285 DOLIT32;
286 len -= 32;
287 }
288 while (len >= 4) {
289 DOLIT4;
290 len -= 4;
291 }
292 buf = (const unsigned char FAR *)buf4;
293
294 if (len) do {
295 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
296 } while (--len);
297 c = ~c;
298 return (unsigned long)c;
299}
300
301/* ========================================================================= */
302#define DOBIG4 c ^= *buf4++; \
303 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
304 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
305#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
306
307/* ========================================================================= */
308local unsigned long crc32_big(crc, buf, len)
309 unsigned long crc;
310 const unsigned char FAR *buf;
311 z_size_t len;
312{
313 register z_crc_t c;
314 register const z_crc_t FAR *buf4;
315
316 c = ZSWAP32((z_crc_t)crc);
317 c = ~c;
318 while (len && ((ptrdiff_t)buf & 3)) {
319 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
320 len--;
321 }
322
323 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
324 while (len >= 32) {
325 DOBIG32;
326 len -= 32;
327 }
328 while (len >= 4) {
329 DOBIG4;
330 len -= 4;
331 }
332 buf = (const unsigned char FAR *)buf4;
333
334 if (len) do {
335 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
336 } while (--len);
337 c = ~c;
338 return (unsigned long)(ZSWAP32(c));
339}
340
341#endif /* BYFOUR */
342
343#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
344
345/* ========================================================================= */
346local unsigned long gf2_matrix_times(mat, vec)
347 unsigned long *mat;
348 unsigned long vec;
349{
350 unsigned long sum;
351
352 sum = 0;
353 while (vec) {
354 if (vec & 1)
355 sum ^= *mat;
356 vec >>= 1;
357 mat++;
358 }
359 return sum;
360}
361
362/* ========================================================================= */
363local void gf2_matrix_square(square, mat)
364 unsigned long *square;
365 unsigned long *mat;
366{
367 int n;
368
369 for (n = 0; n < GF2_DIM; n++)
370 square[n] = gf2_matrix_times(mat, mat[n]);
371}
372
373/* ========================================================================= */
374local uLong crc32_combine_(crc1, crc2, len2)
375 uLong crc1;
376 uLong crc2;
377 z_off64_t len2;
378{
379 int n;
380 unsigned long row;
381 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
382 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
383
384 /* degenerate case (also disallow negative lengths) */
385 if (len2 <= 0)
386 return crc1;
387
388 /* put operator for one zero bit in odd */
389 odd[0] = 0xedb88320UL; /* CRC-32 polynomial */
390 row = 1;
391 for (n = 1; n < GF2_DIM; n++) {
392 odd[n] = row;
393 row <<= 1;
394 }
395
396 /* put operator for two zero bits in even */
397 gf2_matrix_square(even, odd);
398
399 /* put operator for four zero bits in odd */
400 gf2_matrix_square(odd, even);
401
402 /* apply len2 zeros to crc1 (first square will put the operator for one
403 zero byte, eight zero bits, in even) */
404 do {
405 /* apply zeros operator for this bit of len2 */
406 gf2_matrix_square(even, odd);
407 if (len2 & 1)
408 crc1 = gf2_matrix_times(even, crc1);
409 len2 >>= 1;
410
411 /* if no more bits set, then done */
412 if (len2 == 0)
413 break;
414
415 /* another iteration of the loop with odd and even swapped */
416 gf2_matrix_square(odd, even);
417 if (len2 & 1)
418 crc1 = gf2_matrix_times(odd, crc1);
419 len2 >>= 1;
420
421 /* if no more bits set, then done */
422 } while (len2 != 0);
423
424 /* return combined crc */
425 crc1 ^= crc2;
426 return crc1;
427}
428
429/* ========================================================================= */
430uLong ZEXPORT crc32_combine(crc1, crc2, len2)
431 uLong crc1;
432 uLong crc2;
433 z_off_t len2;
434{
435 return crc32_combine_(crc1, crc2, len2);
436}
437
438uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
439 uLong crc1;
440 uLong crc2;
441 z_off64_t len2;
442{
443 return crc32_combine_(crc1, crc2, len2);
444}
445