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