Commit | Line | Data |
f4c6fd49 |
1 | /* crc32.c -- compute the CRC-32 of a data stream |
2 | * Copyright (C) 1995-2003 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 about a factor |
9 | * 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 | #ifdef DYNAMIC_CRC_TABLE |
68 | |
69 | local volatile int crc_table_empty = 1; |
70 | local unsigned long FAR crc_table[TBLS][256]; |
71 | local void make_crc_table OF((void)); |
72 | #ifdef MAKECRCH |
73 | local void write_table OF((FILE *, const unsigned long FAR *)); |
74 | #endif /* MAKECRCH */ |
75 | |
76 | /* |
77 | Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: |
78 | 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. |
79 | |
80 | Polynomials over GF(2) are represented in binary, one bit per coefficient, |
81 | with the lowest powers in the most significant bit. Then adding polynomials |
82 | is just exclusive-or, and multiplying a polynomial by x is a right shift by |
83 | one. If we call the above polynomial p, and represent a byte as the |
84 | polynomial q, also with the lowest power in the most significant bit (so the |
85 | byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, |
86 | where a mod b means the remainder after dividing a by b. |
87 | |
88 | This calculation is done using the shift-register method of multiplying and |
89 | taking the remainder. The register is initialized to zero, and for each |
90 | incoming bit, x^32 is added mod p to the register if the bit is a one (where |
91 | x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by |
92 | x (which is shifting right by one and adding x^32 mod p if the bit shifted |
93 | out is a one). We start with the highest power (least significant bit) of |
94 | q and repeat for all eight bits of q. |
95 | |
96 | The first table is simply the CRC of all possible eight bit values. This is |
97 | all the information needed to generate CRCs on data a byte at a time for all |
98 | combinations of CRC register values and incoming bytes. The remaining tables |
99 | allow for word-at-a-time CRC calculation for both big-endian and little- |
100 | endian machines, where a word is four bytes. |
101 | */ |
102 | local void make_crc_table() |
103 | { |
104 | unsigned long c; |
105 | int n, k; |
106 | unsigned long poly; /* polynomial exclusive-or pattern */ |
107 | /* terms of polynomial defining this crc (except x^32): */ |
108 | static volatile int first = 1; /* flag to limit concurrent making */ |
109 | static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; |
110 | |
111 | /* See if another task is already doing this (not thread-safe, but better |
112 | than nothing -- significantly reduces duration of vulnerability in |
113 | case the advice about DYNAMIC_CRC_TABLE is ignored) */ |
114 | if (first) { |
115 | first = 0; |
116 | |
117 | /* make exclusive-or pattern from polynomial (0xedb88320UL) */ |
118 | poly = 0UL; |
119 | for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) |
120 | poly |= 1UL << (31 - p[n]); |
121 | |
122 | /* generate a crc for every 8-bit value */ |
123 | for (n = 0; n < 256; n++) { |
124 | c = (unsigned long)n; |
125 | for (k = 0; k < 8; k++) |
126 | c = c & 1 ? poly ^ (c >> 1) : c >> 1; |
127 | crc_table[0][n] = c; |
128 | } |
129 | |
130 | #ifdef BYFOUR |
131 | /* generate crc for each value followed by one, two, and three zeros, |
132 | and then the byte reversal of those as well as the first table */ |
133 | for (n = 0; n < 256; n++) { |
134 | c = crc_table[0][n]; |
135 | crc_table[4][n] = REV(c); |
136 | for (k = 1; k < 4; k++) { |
137 | c = crc_table[0][c & 0xff] ^ (c >> 8); |
138 | crc_table[k][n] = c; |
139 | crc_table[k + 4][n] = REV(c); |
140 | } |
141 | } |
142 | #endif /* BYFOUR */ |
143 | |
144 | crc_table_empty = 0; |
145 | } |
146 | else { /* not first */ |
147 | /* wait for the other guy to finish (not efficient, but rare) */ |
148 | while (crc_table_empty) |
149 | ; |
150 | } |
151 | |
152 | #ifdef MAKECRCH |
153 | /* write out CRC tables to crc32.h */ |
154 | { |
155 | FILE *out; |
156 | |
157 | out = fopen("crc32.h", "w"); |
158 | if (out == NULL) return; |
159 | fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); |
160 | fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); |
161 | fprintf(out, "local const unsigned long FAR "); |
162 | fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); |
163 | write_table(out, crc_table[0]); |
164 | # ifdef BYFOUR |
165 | fprintf(out, "#ifdef BYFOUR\n"); |
166 | for (k = 1; k < 8; k++) { |
167 | fprintf(out, " },\n {\n"); |
168 | write_table(out, crc_table[k]); |
169 | } |
170 | fprintf(out, "#endif\n"); |
171 | # endif /* BYFOUR */ |
172 | fprintf(out, " }\n};\n"); |
173 | fclose(out); |
174 | } |
175 | #endif /* MAKECRCH */ |
176 | } |
177 | |
178 | #ifdef MAKECRCH |
179 | local void write_table(out, table) |
180 | FILE *out; |
181 | const unsigned long FAR *table; |
182 | { |
183 | int n; |
184 | |
185 | for (n = 0; n < 256; n++) |
186 | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], |
187 | n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); |
188 | } |
189 | #endif /* MAKECRCH */ |
190 | |
191 | #else /* !DYNAMIC_CRC_TABLE */ |
192 | /* ======================================================================== |
193 | * Tables of CRC-32s of all single-byte values, made by make_crc_table(). |
194 | */ |
195 | #include "crc32.h" |
196 | #endif /* DYNAMIC_CRC_TABLE */ |
197 | |
198 | /* ========================================================================= |
199 | * This function can be used by asm versions of crc32() |
200 | */ |
201 | const unsigned long FAR * ZEXPORT get_crc_table() |
202 | { |
203 | #ifdef DYNAMIC_CRC_TABLE |
204 | if (crc_table_empty) |
205 | make_crc_table(); |
206 | #endif /* DYNAMIC_CRC_TABLE */ |
207 | return (const unsigned long FAR *)crc_table; |
208 | } |
209 | |
210 | /* ========================================================================= */ |
211 | #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) |
212 | #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 |
213 | |
214 | /* ========================================================================= */ |
215 | unsigned long ZEXPORT crc32(crc, buf, len) |
216 | unsigned long crc; |
217 | const unsigned char FAR *buf; |
218 | unsigned len; |
219 | { |
220 | if (buf == Z_NULL) return 0UL; |
221 | |
222 | #ifdef DYNAMIC_CRC_TABLE |
223 | if (crc_table_empty) |
224 | make_crc_table(); |
225 | #endif /* DYNAMIC_CRC_TABLE */ |
226 | |
227 | #ifdef BYFOUR |
228 | if (sizeof(void *) == sizeof(ptrdiff_t)) { |
229 | u4 endian; |
230 | |
231 | endian = 1; |
232 | if (*((unsigned char *)(&endian))) |
233 | return crc32_little(crc, buf, len); |
234 | else |
235 | return crc32_big(crc, buf, len); |
236 | } |
237 | #endif /* BYFOUR */ |
238 | crc = crc ^ 0xffffffffUL; |
239 | while (len >= 8) { |
240 | DO8; |
241 | len -= 8; |
242 | } |
243 | if (len) do { |
244 | DO1; |
245 | } while (--len); |
246 | return crc ^ 0xffffffffUL; |
247 | } |
248 | |
249 | #ifdef BYFOUR |
250 | |
251 | /* ========================================================================= */ |
252 | #define DOLIT4 c ^= *buf4++; \ |
253 | c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ |
254 | crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] |
255 | #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 |
256 | |
257 | /* ========================================================================= */ |
258 | local unsigned long crc32_little(crc, buf, len) |
259 | unsigned long crc; |
260 | const unsigned char FAR *buf; |
261 | unsigned len; |
262 | { |
263 | register u4 c; |
264 | register const u4 FAR *buf4; |
265 | |
266 | c = (u4)crc; |
267 | c = ~c; |
268 | while (len && ((ptrdiff_t)buf & 3)) { |
269 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |
270 | len--; |
271 | } |
272 | |
273 | buf4 = (const u4 FAR *)buf; |
274 | while (len >= 32) { |
275 | DOLIT32; |
276 | len -= 32; |
277 | } |
278 | while (len >= 4) { |
279 | DOLIT4; |
280 | len -= 4; |
281 | } |
282 | buf = (const unsigned char FAR *)buf4; |
283 | |
284 | if (len) do { |
285 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); |
286 | } while (--len); |
287 | c = ~c; |
288 | return (unsigned long)c; |
289 | } |
290 | |
291 | /* ========================================================================= */ |
292 | #define DOBIG4 c ^= *++buf4; \ |
293 | c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ |
294 | crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] |
295 | #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 |
296 | |
297 | /* ========================================================================= */ |
298 | local unsigned long crc32_big(crc, buf, len) |
299 | unsigned long crc; |
300 | const unsigned char FAR *buf; |
301 | unsigned len; |
302 | { |
303 | register u4 c; |
304 | register const u4 FAR *buf4; |
305 | |
306 | c = REV((u4)crc); |
307 | c = ~c; |
308 | while (len && ((ptrdiff_t)buf & 3)) { |
309 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
310 | len--; |
311 | } |
312 | |
313 | buf4 = (const u4 FAR *)buf; |
314 | buf4--; |
315 | while (len >= 32) { |
316 | DOBIG32; |
317 | len -= 32; |
318 | } |
319 | while (len >= 4) { |
320 | DOBIG4; |
321 | len -= 4; |
322 | } |
323 | buf4++; |
324 | buf = (const unsigned char FAR *)buf4; |
325 | |
326 | if (len) do { |
327 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); |
328 | } while (--len); |
329 | c = ~c; |
330 | return (unsigned long)(REV(c)); |
331 | } |
332 | |
333 | #endif /* BYFOUR */ |