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