Rev 1896 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
1896 | serge | 1 | /* crc32.c -- compute the CRC-32 of a data stream |
3926 | Serge | 2 | * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler |
1896 | serge | 3 | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | * |
||
5 | * Thanks to Rodney Brown |
||
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(). |
||
3926 | Serge | 20 | |
21 | DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. |
||
1896 | serge | 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. */ |
||
3926 | Serge | 36 | #if !defined(NOBYFOUR) && defined(Z_U4) |
37 | # define BYFOUR |
||
38 | #endif |
||
1896 | serge | 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)); |
||
3926 | Serge | 53 | local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); |
1896 | serge | 54 | |
55 | |||
56 | #ifdef DYNAMIC_CRC_TABLE |
||
57 | |||
58 | local volatile int crc_table_empty = 1; |
||
3926 | Serge | 59 | local z_crc_t FAR crc_table[TBLS][256]; |
1896 | serge | 60 | local void make_crc_table OF((void)); |
61 | #ifdef MAKECRCH |
||
3926 | Serge | 62 | local void write_table OF((FILE *, const z_crc_t FAR *)); |
1896 | serge | 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 | { |
||
3926 | Serge | 92 | z_crc_t c; |
1896 | serge | 93 | int n, k; |
3926 | Serge | 94 | z_crc_t poly; /* polynomial exclusive-or pattern */ |
1896 | serge | 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) */ |
||
3926 | Serge | 106 | poly = 0; |
107 | for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) |
||
108 | poly |= (z_crc_t)1 << (31 - p[n]); |
||
1896 | serge | 109 | |
110 | /* generate a crc for every 8-bit value */ |
||
111 | for (n = 0; n < 256; n++) { |
||
3926 | Serge | 112 | c = (z_crc_t)n; |
1896 | serge | 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]; |
||
3926 | Serge | 123 | crc_table[4][n] = ZSWAP32(c); |
1896 | serge | 124 | for (k = 1; k < 4; k++) { |
125 | c = crc_table[0][c & 0xff] ^ (c >> 8); |
||
126 | crc_table[k][n] = c; |
||
3926 | Serge | 127 | crc_table[k + 4][n] = ZSWAP32(c); |
1896 | serge | 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"); |
||
3926 | Serge | 149 | fprintf(out, "local const z_crc_t FAR "); |
1896 | serge | 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(out, table) |
||
168 | FILE *out; |
||
3926 | Serge | 169 | const z_crc_t FAR *table; |
1896 | serge | 170 | { |
171 | int n; |
||
172 | |||
173 | for (n = 0; n < 256; n++) |
||
3926 | Serge | 174 | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", |
175 | (unsigned long)(table[n]), |
||
1896 | serge | 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 | */ |
||
3926 | Serge | 190 | const z_crc_t FAR * ZEXPORT get_crc_table() |
1896 | serge | 191 | { |
192 | #ifdef DYNAMIC_CRC_TABLE |
||
193 | if (crc_table_empty) |
||
194 | make_crc_table(); |
||
195 | #endif /* DYNAMIC_CRC_TABLE */ |
||
3926 | Serge | 196 | return (const z_crc_t FAR *)crc_table; |
1896 | serge | 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 | unsigned long ZEXPORT crc32(crc, buf, len) |
||
205 | unsigned long crc; |
||
206 | const unsigned char FAR *buf; |
||
207 | uInt 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)) { |
||
3926 | Serge | 218 | z_crc_t endian; |
1896 | serge | 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 | #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(crc, buf, len) |
||
248 | unsigned long crc; |
||
249 | const unsigned char FAR *buf; |
||
250 | unsigned len; |
||
251 | { |
||
3926 | Serge | 252 | register z_crc_t c; |
253 | register const z_crc_t FAR *buf4; |
||
1896 | serge | 254 | |
3926 | Serge | 255 | c = (z_crc_t)crc; |
1896 | serge | 256 | c = ~c; |
257 | while (len && ((ptrdiff_t)buf & 3)) { |
||
258 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |
||
259 | len--; |
||
260 | } |
||
261 | |||
3926 | Serge | 262 | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
1896 | serge | 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(crc, buf, len) |
||
288 | unsigned long crc; |
||
289 | const unsigned char FAR *buf; |
||
290 | unsigned len; |
||
291 | { |
||
3926 | Serge | 292 | register z_crc_t c; |
293 | register const z_crc_t FAR *buf4; |
||
1896 | serge | 294 | |
3926 | Serge | 295 | c = ZSWAP32((z_crc_t)crc); |
1896 | serge | 296 | c = ~c; |
297 | while (len && ((ptrdiff_t)buf & 3)) { |
||
298 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
||
299 | len--; |
||
300 | } |
||
301 | |||
3926 | Serge | 302 | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
1896 | serge | 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; |
||
3926 | Serge | 319 | return (unsigned long)(ZSWAP32(c)); |
1896 | serge | 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(mat, vec) |
||
328 | unsigned long *mat; |
||
329 | unsigned long vec; |
||
330 | { |
||
331 | unsigned long sum; |
||
332 | |||
333 | sum = 0; |
||
334 | while (vec) { |
||
335 | if (vec & 1) |
||
336 | sum ^= *mat; |
||
337 | vec >>= 1; |
||
338 | mat++; |
||
339 | } |
||
340 | return sum; |
||
341 | } |
||
342 | |||
343 | /* ========================================================================= */ |
||
344 | local void gf2_matrix_square(square, mat) |
||
345 | unsigned long *square; |
||
346 | unsigned long *mat; |
||
347 | { |
||
348 | int n; |
||
349 | |||
350 | for (n = 0; n < GF2_DIM; n++) |
||
351 | square[n] = gf2_matrix_times(mat, mat[n]); |
||
352 | } |
||
353 | |||
354 | /* ========================================================================= */ |
||
355 | local uLong crc32_combine_(crc1, crc2, len2) |
||
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 | if (len2 <= 0) |
||
367 | return crc1; |
||
368 | |||
369 | /* put operator for one zero bit in odd */ |
||
370 | odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ |
||
371 | row = 1; |
||
372 | for (n = 1; n < GF2_DIM; n++) { |
||
373 | odd[n] = row; |
||
374 | row <<= 1; |
||
375 | } |
||
376 | |||
377 | /* put operator for two zero bits in even */ |
||
378 | gf2_matrix_square(even, odd); |
||
379 | |||
380 | /* put operator for four zero bits in odd */ |
||
381 | 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 | gf2_matrix_square(even, odd); |
||
388 | if (len2 & 1) |
||
389 | crc1 = gf2_matrix_times(even, crc1); |
||
390 | len2 >>= 1; |
||
391 | |||
392 | /* if no more bits set, then done */ |
||
393 | if (len2 == 0) |
||
394 | break; |
||
395 | |||
396 | /* another iteration of the loop with odd and even swapped */ |
||
397 | gf2_matrix_square(odd, even); |
||
398 | if (len2 & 1) |
||
399 | crc1 = gf2_matrix_times(odd, crc1); |
||
400 | len2 >>= 1; |
||
401 | |||
402 | /* if no more bits set, then done */ |
||
403 | } while (len2 != 0); |
||
404 | |||
405 | /* return combined crc */ |
||
406 | crc1 ^= crc2; |
||
407 | return crc1; |
||
408 | } |
||
409 | |||
410 | /* ========================================================================= */ |
||
411 | uLong ZEXPORT crc32_combine(crc1, crc2, len2) |
||
412 | uLong crc1; |
||
413 | uLong crc2; |
||
414 | z_off_t len2; |
||
415 | { |
||
416 | return crc32_combine_(crc1, crc2, len2); |
||
417 | } |
||
418 | |||
419 | uLong ZEXPORT crc32_combine64(crc1, crc2, len2) |
||
420 | uLong crc1; |
||
421 | uLong crc2; |
||
422 | z_off64_t len2; |
||
423 | { |
||
424 | return crc32_combine_(crc1, crc2, len2); |
||
425 | }=><=>>=>>><>><>>>>>>>><>> |