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