]>
Commit | Line | Data |
---|---|---|
11fcec12 NB |
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 | * | |
12c7b44e JS |
5 | * Note: zlib license from from zlib.h added explicitly as mdadm does |
6 | * not include zlib.h. License from v1.2.2 of zlib: | |
7 | * | |
8 | * This software is provided 'as-is', without any express or implied | |
9 | * warranty. In no event will the authors be held liable for any damages | |
10 | * arising from the use of this software. | |
11 | * | |
12 | * Permission is granted to anyone to use this software for any purpose, | |
13 | * including commercial applications, and to alter it and redistribute it | |
14 | * freely, subject to the following restrictions: | |
15 | * | |
16 | * 1. The origin of this software must not be misrepresented; you must not | |
17 | * claim that you wrote the original software. If you use this software | |
18 | * in a product, an acknowledgment in the product documentation would be | |
19 | * appreciated but is not required. | |
20 | * 2. Altered source versions must be plainly marked as such, and must not be | |
21 | * misrepresented as being the original software. | |
22 | * 3. This notice may not be removed or altered from any source distribution. | |
23 | * | |
24 | * | |
11fcec12 NB |
25 | * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster |
26 | * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing | |
27 | * tables for updating the shift register in one step with three exclusive-ors | |
28 | * instead of four steps with four exclusive-ors. This results about a factor | |
29 | * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3. | |
30 | */ | |
31 | ||
32 | /* @(#) $Id$ */ | |
33 | ||
34 | /* | |
35 | Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore | |
36 | protection on the static variables used to control the first-use generation | |
37 | of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should | |
38 | first call get_crc_table() to initialize the tables before allowing more than | |
39 | one thread to use crc32(). | |
40 | */ | |
41 | ||
42 | #ifdef MAKECRCH | |
43 | # include <stdio.h> | |
44 | # ifndef DYNAMIC_CRC_TABLE | |
45 | # define DYNAMIC_CRC_TABLE | |
46 | # endif /* !DYNAMIC_CRC_TABLE */ | |
47 | #endif /* MAKECRCH */ | |
48 | ||
49 | /* #include "zutil.h" / * for STDC and FAR definitions */ | |
50 | #define STDC | |
51 | #define FAR | |
52 | #define Z_NULL ((void*)0) | |
53 | #define OF(X) X | |
54 | #define ZEXPORT | |
55 | typedef long ptrdiff_t; | |
56 | #define NOBYFOUR | |
57 | ||
58 | #define local static | |
59 | ||
60 | /* Find a four-byte integer type for crc32_little() and crc32_big(). */ | |
61 | #ifndef NOBYFOUR | |
62 | # ifdef STDC /* need ANSI C limits.h to determine sizes */ | |
63 | # include <limits.h> | |
64 | # define BYFOUR | |
65 | # if (UINT_MAX == 0xffffffffUL) | |
66 | typedef unsigned int u4; | |
67 | # else | |
68 | # if (ULONG_MAX == 0xffffffffUL) | |
69 | typedef unsigned long u4; | |
70 | # else | |
71 | # if (USHRT_MAX == 0xffffffffUL) | |
72 | typedef unsigned short u4; | |
73 | # else | |
74 | # undef BYFOUR /* can't find a four-byte integer type! */ | |
75 | # endif | |
76 | # endif | |
77 | # endif | |
78 | # endif /* STDC */ | |
79 | #endif /* !NOBYFOUR */ | |
80 | ||
81 | /* Definitions for doing the crc four data bytes at a time. */ | |
82 | #ifdef BYFOUR | |
83 | # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \ | |
84 | (((w)&0xff00)<<8)+(((w)&0xff)<<24)) | |
85 | local unsigned long crc32_little OF((unsigned long, | |
86 | const unsigned char FAR *, unsigned)); | |
87 | local unsigned long crc32_big OF((unsigned long, | |
88 | const unsigned char FAR *, unsigned)); | |
89 | # define TBLS 8 | |
90 | #else | |
91 | # define TBLS 1 | |
92 | #endif /* BYFOUR */ | |
93 | ||
94 | #ifdef DYNAMIC_CRC_TABLE | |
95 | ||
96 | local volatile int crc_table_empty = 1; | |
97 | local unsigned long FAR crc_table[TBLS][256]; | |
98 | local void make_crc_table OF((void)); | |
99 | #ifdef MAKECRCH | |
100 | local void write_table OF((FILE *, const unsigned long FAR *)); | |
101 | #endif /* MAKECRCH */ | |
102 | ||
103 | /* | |
104 | Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: | |
105 | 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. | |
106 | ||
107 | Polynomials over GF(2) are represented in binary, one bit per coefficient, | |
108 | with the lowest powers in the most significant bit. Then adding polynomials | |
109 | is just exclusive-or, and multiplying a polynomial by x is a right shift by | |
110 | one. If we call the above polynomial p, and represent a byte as the | |
111 | polynomial q, also with the lowest power in the most significant bit (so the | |
112 | byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, | |
113 | where a mod b means the remainder after dividing a by b. | |
114 | ||
115 | This calculation is done using the shift-register method of multiplying and | |
116 | taking the remainder. The register is initialized to zero, and for each | |
117 | incoming bit, x^32 is added mod p to the register if the bit is a one (where | |
118 | x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by | |
119 | x (which is shifting right by one and adding x^32 mod p if the bit shifted | |
120 | out is a one). We start with the highest power (least significant bit) of | |
121 | q and repeat for all eight bits of q. | |
122 | ||
123 | The first table is simply the CRC of all possible eight bit values. This is | |
124 | all the information needed to generate CRCs on data a byte at a time for all | |
125 | combinations of CRC register values and incoming bytes. The remaining tables | |
126 | allow for word-at-a-time CRC calculation for both big-endian and little- | |
127 | endian machines, where a word is four bytes. | |
128 | */ | |
129 | local void make_crc_table() | |
130 | { | |
131 | unsigned long c; | |
132 | int n, k; | |
133 | unsigned long poly; /* polynomial exclusive-or pattern */ | |
134 | /* terms of polynomial defining this crc (except x^32): */ | |
135 | static volatile int first = 1; /* flag to limit concurrent making */ | |
136 | static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26}; | |
137 | ||
138 | /* See if another task is already doing this (not thread-safe, but better | |
139 | than nothing -- significantly reduces duration of vulnerability in | |
140 | case the advice about DYNAMIC_CRC_TABLE is ignored) */ | |
141 | if (first) { | |
142 | first = 0; | |
143 | ||
144 | /* make exclusive-or pattern from polynomial (0xedb88320UL) */ | |
145 | poly = 0UL; | |
146 | for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++) | |
147 | poly |= 1UL << (31 - p[n]); | |
148 | ||
149 | /* generate a crc for every 8-bit value */ | |
150 | for (n = 0; n < 256; n++) { | |
151 | c = (unsigned long)n; | |
152 | for (k = 0; k < 8; k++) | |
153 | c = c & 1 ? poly ^ (c >> 1) : c >> 1; | |
154 | crc_table[0][n] = c; | |
155 | } | |
156 | ||
157 | #ifdef BYFOUR | |
158 | /* generate crc for each value followed by one, two, and three zeros, | |
159 | and then the byte reversal of those as well as the first table */ | |
160 | for (n = 0; n < 256; n++) { | |
161 | c = crc_table[0][n]; | |
162 | crc_table[4][n] = REV(c); | |
163 | for (k = 1; k < 4; k++) { | |
164 | c = crc_table[0][c & 0xff] ^ (c >> 8); | |
165 | crc_table[k][n] = c; | |
166 | crc_table[k + 4][n] = REV(c); | |
167 | } | |
168 | } | |
169 | #endif /* BYFOUR */ | |
170 | ||
171 | crc_table_empty = 0; | |
172 | } | |
173 | else { /* not first */ | |
174 | /* wait for the other guy to finish (not efficient, but rare) */ | |
175 | while (crc_table_empty) | |
176 | ; | |
177 | } | |
178 | ||
179 | #ifdef MAKECRCH | |
180 | /* write out CRC tables to crc32.h */ | |
181 | { | |
182 | FILE *out; | |
183 | ||
184 | out = fopen("crc32.h", "w"); | |
185 | if (out == NULL) return; | |
186 | fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n"); | |
187 | fprintf(out, " * Generated automatically by crc32.c\n */\n\n"); | |
188 | fprintf(out, "local const unsigned long FAR "); | |
189 | fprintf(out, "crc_table[TBLS][256] =\n{\n {\n"); | |
190 | write_table(out, crc_table[0]); | |
191 | # ifdef BYFOUR | |
192 | fprintf(out, "#ifdef BYFOUR\n"); | |
193 | for (k = 1; k < 8; k++) { | |
194 | fprintf(out, " },\n {\n"); | |
195 | write_table(out, crc_table[k]); | |
196 | } | |
197 | fprintf(out, "#endif\n"); | |
198 | # endif /* BYFOUR */ | |
199 | fprintf(out, " }\n};\n"); | |
200 | fclose(out); | |
201 | } | |
202 | #endif /* MAKECRCH */ | |
203 | } | |
204 | ||
205 | #ifdef MAKECRCH | |
206 | local void write_table(out, table) | |
207 | FILE *out; | |
208 | const unsigned long FAR *table; | |
209 | { | |
210 | int n; | |
211 | ||
212 | for (n = 0; n < 256; n++) | |
213 | fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n], | |
214 | n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", ")); | |
215 | } | |
216 | #endif /* MAKECRCH */ | |
217 | ||
218 | #else /* !DYNAMIC_CRC_TABLE */ | |
219 | /* ======================================================================== | |
220 | * Tables of CRC-32s of all single-byte values, made by make_crc_table(). | |
221 | */ | |
222 | #include "crc32.h" | |
223 | #endif /* DYNAMIC_CRC_TABLE */ | |
224 | ||
225 | /* ========================================================================= | |
226 | * This function can be used by asm versions of crc32() | |
227 | */ | |
228 | const unsigned long FAR * ZEXPORT get_crc_table(void) | |
229 | { | |
230 | #ifdef DYNAMIC_CRC_TABLE | |
231 | if (crc_table_empty) | |
232 | make_crc_table(); | |
233 | #endif /* DYNAMIC_CRC_TABLE */ | |
234 | return (const unsigned long FAR *)crc_table; | |
235 | } | |
236 | ||
237 | /* ========================================================================= */ | |
238 | #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8) | |
239 | #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1 | |
240 | ||
241 | /* ========================================================================= */ | |
242 | unsigned long ZEXPORT crc32( | |
243 | unsigned long crc, | |
244 | const unsigned char FAR *buf, | |
245 | unsigned len) | |
246 | { | |
247 | if (buf == Z_NULL) return 0UL; | |
248 | ||
249 | #ifdef DYNAMIC_CRC_TABLE | |
250 | if (crc_table_empty) | |
251 | make_crc_table(); | |
252 | #endif /* DYNAMIC_CRC_TABLE */ | |
253 | ||
254 | #ifdef BYFOUR | |
255 | if (sizeof(void *) == sizeof(ptrdiff_t)) { | |
256 | u4 endian; | |
257 | ||
258 | endian = 1; | |
259 | if (*((unsigned char *)(&endian))) | |
260 | return crc32_little(crc, buf, len); | |
261 | else | |
262 | return crc32_big(crc, buf, len); | |
263 | } | |
264 | #endif /* BYFOUR */ | |
265 | /* crc = crc ^ 0xffffffffUL;*/ | |
266 | while (len >= 8) { | |
267 | DO8; | |
268 | len -= 8; | |
269 | } | |
270 | if (len) do { | |
271 | DO1; | |
272 | } while (--len); | |
273 | return crc /* ^ 0xffffffffUL*/; | |
274 | } | |
275 | ||
276 | #ifdef BYFOUR | |
277 | ||
278 | /* ========================================================================= */ | |
279 | #define DOLIT4 c ^= *buf4++; \ | |
280 | c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \ | |
281 | crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24] | |
282 | #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4 | |
283 | ||
284 | /* ========================================================================= */ | |
285 | local unsigned long crc32_little(crc, buf, len) | |
286 | unsigned long crc; | |
287 | const unsigned char FAR *buf; | |
288 | unsigned len; | |
289 | { | |
290 | register u4 c; | |
291 | register const u4 FAR *buf4; | |
292 | ||
293 | c = (u4)crc; | |
294 | c = ~c; | |
295 | while (len && ((ptrdiff_t)buf & 3)) { | |
296 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); | |
297 | len--; | |
298 | } | |
299 | ||
300 | buf4 = (const u4 FAR *)buf; | |
301 | while (len >= 32) { | |
302 | DOLIT32; | |
303 | len -= 32; | |
304 | } | |
305 | while (len >= 4) { | |
306 | DOLIT4; | |
307 | len -= 4; | |
308 | } | |
309 | buf = (const unsigned char FAR *)buf4; | |
310 | ||
311 | if (len) do { | |
312 | c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8); | |
313 | } while (--len); | |
314 | c = ~c; | |
315 | return (unsigned long)c; | |
316 | } | |
317 | ||
318 | /* ========================================================================= */ | |
319 | #define DOBIG4 c ^= *++buf4; \ | |
320 | c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \ | |
321 | crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24] | |
322 | #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4 | |
323 | ||
324 | /* ========================================================================= */ | |
325 | local unsigned long crc32_big(crc, buf, len) | |
326 | unsigned long crc; | |
327 | const unsigned char FAR *buf; | |
328 | unsigned len; | |
329 | { | |
330 | register u4 c; | |
331 | register const u4 FAR *buf4; | |
332 | ||
333 | c = REV((u4)crc); | |
334 | c = ~c; | |
335 | while (len && ((ptrdiff_t)buf & 3)) { | |
336 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); | |
337 | len--; | |
338 | } | |
339 | ||
340 | buf4 = (const u4 FAR *)buf; | |
341 | buf4--; | |
342 | while (len >= 32) { | |
343 | DOBIG32; | |
344 | len -= 32; | |
345 | } | |
346 | while (len >= 4) { | |
347 | DOBIG4; | |
348 | len -= 4; | |
349 | } | |
350 | buf4++; | |
351 | buf = (const unsigned char FAR *)buf4; | |
352 | ||
353 | if (len) do { | |
354 | c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8); | |
355 | } while (--len); | |
356 | c = ~c; | |
357 | return (unsigned long)(REV(c)); | |
358 | } | |
359 | ||
360 | #endif /* BYFOUR */ |