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