Rev 1896 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 1896 | Rev 3926 | ||
---|---|---|---|
Line 1... | Line 1... | ||
1 | /* crc32.c -- compute the CRC-32 of a data stream |
1 | /* crc32.c -- compute the CRC-32 of a data stream |
2 | * Copyright (C) 1995-2006, 2010 Mark Adler |
2 | * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler |
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
3 | * For conditions of distribution and use, see copyright notice in zlib.h |
4 | * |
4 | * |
5 | * Thanks to Rodney Brown |
5 | * Thanks to Rodney Brown |
6 | * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing |
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 |
7 | * tables for updating the shift register in one step with three exclusive-ors |
Line 15... | Line 15... | ||
15 | Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore |
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 |
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 |
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 |
18 | first call get_crc_table() to initialize the tables before allowing more than |
19 | one thread to use crc32(). |
19 | one thread to use crc32(). |
- | 20 | ||
- | 21 | DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h. |
|
20 | */ |
22 | */ |
Line 21... | Line 23... | ||
21 | 23 | ||
22 | #ifdef MAKECRCH |
24 | #ifdef MAKECRCH |
23 | # include |
25 | # include |
Line 28... | Line 30... | ||
28 | 30 | ||
Line 29... | Line 31... | ||
29 | #include "zutil.h" /* for STDC and FAR definitions */ |
31 | #include "zutil.h" /* for STDC and FAR definitions */ |
Line 30... | Line 32... | ||
30 | 32 | ||
31 | #define local static |
33 | #define local static |
32 | - | ||
33 | /* Find a four-byte integer type for crc32_little() and crc32_big(). */ |
- | |
34 | #ifndef NOBYFOUR |
34 | |
35 | # ifdef STDC /* need ANSI C limits.h to determine sizes */ |
- | |
36 | # include |
- | |
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; |
35 | /* Definitions for doing the crc four data bytes at a time. */ |
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 */ |
36 | #if !defined(NOBYFOUR) && defined(Z_U4) |
53 | - | ||
54 | /* Definitions for doing the crc four data bytes at a time. */ |
- | |
55 | #ifdef BYFOUR |
37 | # define BYFOUR |
56 | # define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \ |
38 | #endif |
57 | (((w)&0xff00)<<8)+(((w)&0xff)<<24)) |
39 | #ifdef BYFOUR |
58 | local unsigned long crc32_little OF((unsigned long, |
40 | local unsigned long crc32_little OF((unsigned long, |
59 | const unsigned char FAR *, unsigned)); |
41 | const unsigned char FAR *, unsigned)); |
Line 66... | Line 48... | ||
66 | 48 | ||
67 | /* Local functions for crc concatenation */ |
49 | /* Local functions for crc concatenation */ |
68 | local unsigned long gf2_matrix_times OF((unsigned long *mat, |
50 | local unsigned long gf2_matrix_times OF((unsigned long *mat, |
69 | unsigned long vec)); |
51 | unsigned long vec)); |
70 | local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); |
52 | local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat)); |
Line 71... | Line 53... | ||
71 | local uLong crc32_combine_(uLong crc1, uLong crc2, z_off64_t len2); |
53 | local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2)); |
Line 72... | Line 54... | ||
72 | 54 | ||
73 | 55 | ||
74 | #ifdef DYNAMIC_CRC_TABLE |
56 | #ifdef DYNAMIC_CRC_TABLE |
75 | 57 | ||
76 | local volatile int crc_table_empty = 1; |
58 | local volatile int crc_table_empty = 1; |
77 | local unsigned long FAR crc_table[TBLS][256]; |
59 | local z_crc_t FAR crc_table[TBLS][256]; |
78 | local void make_crc_table OF((void)); |
60 | local void make_crc_table OF((void)); |
79 | #ifdef MAKECRCH |
61 | #ifdef MAKECRCH |
80 | local void write_table OF((FILE *, const unsigned long FAR *)); |
62 | local void write_table OF((FILE *, const z_crc_t FAR *)); |
Line 105... | Line 87... | ||
105 | allow for word-at-a-time CRC calculation for both big-endian and little- |
87 | allow for word-at-a-time CRC calculation for both big-endian and little- |
106 | endian machines, where a word is four bytes. |
88 | endian machines, where a word is four bytes. |
107 | */ |
89 | */ |
108 | local void make_crc_table() |
90 | local void make_crc_table() |
109 | { |
91 | { |
110 | unsigned long c; |
92 | z_crc_t c; |
111 | int n, k; |
93 | int n, k; |
112 | unsigned long poly; /* polynomial exclusive-or pattern */ |
94 | z_crc_t poly; /* polynomial exclusive-or pattern */ |
113 | /* terms of polynomial defining this crc (except x^32): */ |
95 | /* terms of polynomial defining this crc (except x^32): */ |
114 | static volatile int first = 1; /* flag to limit concurrent making */ |
96 | static volatile int first = 1; /* flag to limit concurrent making */ |
115 | static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; |
97 | static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; |
Line 116... | Line 98... | ||
116 | 98 | ||
Line 119... | Line 101... | ||
119 | case the advice about DYNAMIC_CRC_TABLE is ignored) */ |
101 | case the advice about DYNAMIC_CRC_TABLE is ignored) */ |
120 | if (first) { |
102 | if (first) { |
121 | first = 0; |
103 | first = 0; |
Line 122... | Line 104... | ||
122 | 104 | ||
123 | /* make exclusive-or pattern from polynomial (0xedb88320UL) */ |
105 | /* make exclusive-or pattern from polynomial (0xedb88320UL) */ |
124 | poly = 0UL; |
106 | poly = 0; |
125 | for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) |
107 | for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++) |
Line 126... | Line 108... | ||
126 | poly |= 1UL << (31 - p[n]); |
108 | poly |= (z_crc_t)1 << (31 - p[n]); |
127 | 109 | ||
128 | /* generate a crc for every 8-bit value */ |
110 | /* generate a crc for every 8-bit value */ |
129 | for (n = 0; n < 256; n++) { |
111 | for (n = 0; n < 256; n++) { |
130 | c = (unsigned long)n; |
112 | c = (z_crc_t)n; |
131 | for (k = 0; k < 8; k++) |
113 | for (k = 0; k < 8; k++) |
132 | c = c & 1 ? poly ^ (c >> 1) : c >> 1; |
114 | c = c & 1 ? poly ^ (c >> 1) : c >> 1; |
Line 133... | Line 115... | ||
133 | crc_table[0][n] = c; |
115 | crc_table[0][n] = c; |
134 | } |
116 | } |
135 | 117 | ||
136 | #ifdef BYFOUR |
118 | #ifdef BYFOUR |
137 | /* generate crc for each value followed by one, two, and three zeros, |
119 | /* 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 */ |
120 | and then the byte reversal of those as well as the first table */ |
139 | for (n = 0; n < 256; n++) { |
121 | for (n = 0; n < 256; n++) { |
140 | c = crc_table[0][n]; |
122 | c = crc_table[0][n]; |
141 | crc_table[4][n] = REV(c); |
123 | crc_table[4][n] = ZSWAP32(c); |
142 | for (k = 1; k < 4; k++) { |
124 | for (k = 1; k < 4; k++) { |
143 | c = crc_table[0][c & 0xff] ^ (c >> 8); |
125 | c = crc_table[0][c & 0xff] ^ (c >> 8); |
144 | crc_table[k][n] = c; |
126 | crc_table[k][n] = c; |
145 | crc_table[k + 4][n] = REV(c); |
127 | crc_table[k + 4][n] = ZSWAP32(c); |
Line 146... | Line 128... | ||
146 | } |
128 | } |
Line 162... | Line 144... | ||
162 | 144 | ||
163 | out = fopen("crc32.h", "w"); |
145 | out = fopen("crc32.h", "w"); |
164 | if (out == NULL) return; |
146 | if (out == NULL) return; |
165 | fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); |
147 | fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); |
166 | fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); |
148 | fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); |
167 | fprintf(out, "local const unsigned long FAR "); |
149 | fprintf(out, "local const z_crc_t FAR "); |
168 | fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); |
150 | fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); |
169 | write_table(out, crc_table[0]); |
151 | write_table(out, crc_table[0]); |
170 | # ifdef BYFOUR |
152 | # ifdef BYFOUR |
171 | fprintf(out, "#ifdef BYFOUR\n"); |
153 | fprintf(out, "#ifdef BYFOUR\n"); |
Line 182... | Line 164... | ||
182 | } |
164 | } |
Line 183... | Line 165... | ||
183 | 165 | ||
184 | #ifdef MAKECRCH |
166 | #ifdef MAKECRCH |
185 | local void write_table(out, table) |
167 | local void write_table(out, table) |
186 | FILE *out; |
168 | FILE *out; |
187 | const unsigned long FAR *table; |
169 | const z_crc_t FAR *table; |
188 | { |
170 | { |
Line 189... | Line 171... | ||
189 | int n; |
171 | int n; |
190 | 172 | ||
- | 173 | for (n = 0; n < 256; n++) |
|
191 | for (n = 0; n < 256; n++) |
174 | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", |
192 | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], |
175 | (unsigned long)(table[n]), |
193 | n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); |
176 | n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); |
Line 194... | Line 177... | ||
194 | } |
177 | } |
Line 202... | Line 185... | ||
202 | #endif /* DYNAMIC_CRC_TABLE */ |
185 | #endif /* DYNAMIC_CRC_TABLE */ |
Line 203... | Line 186... | ||
203 | 186 | ||
204 | /* ========================================================================= |
187 | /* ========================================================================= |
205 | * This function can be used by asm versions of crc32() |
188 | * This function can be used by asm versions of crc32() |
206 | */ |
189 | */ |
207 | const unsigned long FAR * ZEXPORT get_crc_table() |
190 | const z_crc_t FAR * ZEXPORT get_crc_table() |
208 | { |
191 | { |
209 | #ifdef DYNAMIC_CRC_TABLE |
192 | #ifdef DYNAMIC_CRC_TABLE |
210 | if (crc_table_empty) |
193 | if (crc_table_empty) |
211 | make_crc_table(); |
194 | make_crc_table(); |
212 | #endif /* DYNAMIC_CRC_TABLE */ |
195 | #endif /* DYNAMIC_CRC_TABLE */ |
213 | return (const unsigned long FAR *)crc_table; |
196 | return (const z_crc_t FAR *)crc_table; |
Line 214... | Line 197... | ||
214 | } |
197 | } |
215 | 198 | ||
216 | /* ========================================================================= */ |
199 | /* ========================================================================= */ |
Line 230... | Line 213... | ||
230 | make_crc_table(); |
213 | make_crc_table(); |
231 | #endif /* DYNAMIC_CRC_TABLE */ |
214 | #endif /* DYNAMIC_CRC_TABLE */ |
Line 232... | Line 215... | ||
232 | 215 | ||
233 | #ifdef BYFOUR |
216 | #ifdef BYFOUR |
234 | if (sizeof(void *) == sizeof(ptrdiff_t)) { |
217 | if (sizeof(void *) == sizeof(ptrdiff_t)) { |
Line 235... | Line 218... | ||
235 | u4 endian; |
218 | z_crc_t endian; |
236 | 219 | ||
237 | endian = 1; |
220 | endian = 1; |
238 | if (*((unsigned char *)(&endian))) |
221 | if (*((unsigned char *)(&endian))) |
Line 264... | Line 247... | ||
264 | local unsigned long crc32_little(crc, buf, len) |
247 | local unsigned long crc32_little(crc, buf, len) |
265 | unsigned long crc; |
248 | unsigned long crc; |
266 | const unsigned char FAR *buf; |
249 | const unsigned char FAR *buf; |
267 | unsigned len; |
250 | unsigned len; |
268 | { |
251 | { |
269 | register u4 c; |
252 | register z_crc_t c; |
270 | register const u4 FAR *buf4; |
253 | register const z_crc_t FAR *buf4; |
Line 271... | Line 254... | ||
271 | 254 | ||
272 | c = (u4)crc; |
255 | c = (z_crc_t)crc; |
273 | c = ~c; |
256 | c = ~c; |
274 | while (len && ((ptrdiff_t)buf & 3)) { |
257 | while (len && ((ptrdiff_t)buf & 3)) { |
275 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |
258 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |
276 | len--; |
259 | len--; |
Line 277... | Line 260... | ||
277 | } |
260 | } |
278 | 261 | ||
279 | buf4 = (const u4 FAR *)(const void FAR *)buf; |
262 | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
280 | while (len >= 32) { |
263 | while (len >= 32) { |
281 | DOLIT32; |
264 | DOLIT32; |
282 | len -= 32; |
265 | len -= 32; |
Line 304... | Line 287... | ||
304 | local unsigned long crc32_big(crc, buf, len) |
287 | local unsigned long crc32_big(crc, buf, len) |
305 | unsigned long crc; |
288 | unsigned long crc; |
306 | const unsigned char FAR *buf; |
289 | const unsigned char FAR *buf; |
307 | unsigned len; |
290 | unsigned len; |
308 | { |
291 | { |
309 | register u4 c; |
292 | register z_crc_t c; |
310 | register const u4 FAR *buf4; |
293 | register const z_crc_t FAR *buf4; |
Line 311... | Line 294... | ||
311 | 294 | ||
312 | c = REV((u4)crc); |
295 | c = ZSWAP32((z_crc_t)crc); |
313 | c = ~c; |
296 | c = ~c; |
314 | while (len && ((ptrdiff_t)buf & 3)) { |
297 | while (len && ((ptrdiff_t)buf & 3)) { |
315 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
298 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
316 | len--; |
299 | len--; |
Line 317... | Line 300... | ||
317 | } |
300 | } |
318 | 301 | ||
319 | buf4 = (const u4 FAR *)(const void FAR *)buf; |
302 | buf4 = (const z_crc_t FAR *)(const void FAR *)buf; |
320 | buf4--; |
303 | buf4--; |
321 | while (len >= 32) { |
304 | while (len >= 32) { |
322 | DOBIG32; |
305 | DOBIG32; |
Line 331... | Line 314... | ||
331 | 314 | ||
332 | if (len) do { |
315 | if (len) do { |
333 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
316 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
334 | } while (--len); |
317 | } while (--len); |
335 | c = ~c; |
318 | c = ~c; |
336 | return (unsigned long)(REV(c)); |
319 | return (unsigned long)(ZSWAP32(c)); |
Line 337... | Line 320... | ||
337 | } |
320 | } |
Line 338... | Line 321... | ||
338 | 321 |