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