]> git.saurik.com Git - wxWidgets.git/blob - src/zlib/crc32.c
Fix some bugs
[wxWidgets.git] / src / zlib / crc32.c
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 #ifdef MAKECRCH
15 # include <stdio.h>
16 # ifndef DYNAMIC_CRC_TABLE
17 # define DYNAMIC_CRC_TABLE
18 # endif /* !DYNAMIC_CRC_TABLE */
19 #endif /* MAKECRCH */
20
21 #include "zutil.h" /* for STDC and FAR definitions */
22
23 #define local static
24
25 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
26 #ifndef NOBYFOUR
27 # ifdef STDC /* need ANSI C limits.h to determine sizes */
28 # include <limits.h>
29 # define BYFOUR
30 # if (UINT_MAX == 0xffffffffUL)
31 typedef unsigned int u4;
32 # else
33 # if (ULONG_MAX == 0xffffffffUL)
34 typedef unsigned long u4;
35 # else
36 # if (USHRT_MAX == 0xffffffffUL)
37 typedef unsigned short u4;
38 # else
39 # undef BYFOUR /* can't find a four-byte integer type! */
40 # endif
41 # endif
42 # endif
43 # endif /* STDC */
44 #endif /* !NOBYFOUR */
45
46 /* Definitions for doing the crc four data bytes at a time. */
47 #ifdef BYFOUR
48 # define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
49 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
50 local unsigned long crc32_little OF((unsigned long,
51 const unsigned char FAR *, unsigned));
52 local unsigned long crc32_big OF((unsigned long,
53 const unsigned char FAR *, unsigned));
54 # define TBLS 8
55 #else
56 # define TBLS 1
57 #endif /* BYFOUR */
58
59 #ifdef DYNAMIC_CRC_TABLE
60
61 local int crc_table_empty = 1;
62 local unsigned long FAR crc_table[TBLS][256];
63 local void make_crc_table OF((void));
64 #ifdef MAKECRCH
65 local void write_table OF((FILE *, const unsigned long FAR *));
66 #endif /* MAKECRCH */
67
68 /*
69 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
70 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.
71
72 Polynomials over GF(2) are represented in binary, one bit per coefficient,
73 with the lowest powers in the most significant bit. Then adding polynomials
74 is just exclusive-or, and multiplying a polynomial by x is a right shift by
75 one. If we call the above polynomial p, and represent a byte as the
76 polynomial q, also with the lowest power in the most significant bit (so the
77 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
78 where a mod b means the remainder after dividing a by b.
79
80 This calculation is done using the shift-register method of multiplying and
81 taking the remainder. The register is initialized to zero, and for each
82 incoming bit, x^32 is added mod p to the register if the bit is a one (where
83 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
84 x (which is shifting right by one and adding x^32 mod p if the bit shifted
85 out is a one). We start with the highest power (least significant bit) of
86 q and repeat for all eight bits of q.
87
88 The first table is simply the CRC of all possible eight bit values. This is
89 all the information needed to generate CRCs on data a byte at a time for all
90 combinations of CRC register values and incoming bytes. The remaining tables
91 allow for word-at-a-time CRC calculation for both big-endian and little-
92 endian machines, where a word is four bytes.
93 */
94 local void make_crc_table()
95 {
96 unsigned long c;
97 int n, k;
98 unsigned long poly; /* polynomial exclusive-or pattern */
99 /* terms of polynomial defining this crc (except x^32): */
100 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
101
102 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
103 poly = 0UL;
104 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
105 poly |= 1UL << (31 - p[n]);
106
107 /* generate a crc for every 8-bit value */
108 for (n = 0; n < 256; n++) {
109 c = (unsigned long)n;
110 for (k = 0; k < 8; k++)
111 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
112 crc_table[0][n] = c;
113 }
114
115 #ifdef BYFOUR
116 /* generate crc for each value followed by one, two, and three zeros, and
117 then the byte reversal of those as well as the first table */
118 for (n = 0; n < 256; n++) {
119 c = crc_table[0][n];
120 crc_table[4][n] = REV(c);
121 for (k = 1; k < 4; k++) {
122 c = crc_table[0][c & 0xff] ^ (c >> 8);
123 crc_table[k][n] = c;
124 crc_table[k + 4][n] = REV(c);
125 }
126 }
127 #endif /* BYFOUR */
128
129 crc_table_empty = 0;
130
131 #ifdef MAKECRCH
132 /* write out CRC tables to crc32.h */
133 {
134 FILE *out;
135
136 out = fopen("crc32.h", "w");
137 if (out == NULL) return;
138 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
139 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
140 fprintf(out, "local const unsigned long FAR ");
141 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
142 write_table(out, crc_table[0]);
143 # ifdef BYFOUR
144 fprintf(out, "#ifdef BYFOUR\n");
145 for (k = 1; k < 8; k++) {
146 fprintf(out, " },\n {\n");
147 write_table(out, crc_table[k]);
148 }
149 fprintf(out, "#endif\n");
150 # endif /* BYFOUR */
151 fprintf(out, " }\n};\n");
152 fclose(out);
153 }
154 #endif /* MAKECRCH */
155 }
156
157 #ifdef MAKECRCH
158 local void write_table(out, table)
159 FILE *out;
160 const unsigned long FAR *table;
161 {
162 int n;
163
164 for (n = 0; n < 256; n++)
165 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
166 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
167 }
168 #endif /* MAKECRCH */
169
170 #else /* !DYNAMIC_CRC_TABLE */
171 /* ========================================================================
172 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
173 */
174 #include "crc32.h"
175 #endif /* DYNAMIC_CRC_TABLE */
176
177 /* =========================================================================
178 * This function can be used by asm versions of crc32()
179 */
180 const unsigned long FAR * ZEXPORT get_crc_table()
181 {
182 #ifdef DYNAMIC_CRC_TABLE
183 if (crc_table_empty) make_crc_table();
184 #endif /* DYNAMIC_CRC_TABLE */
185 return (const unsigned long FAR *)crc_table;
186 }
187
188 /* ========================================================================= */
189 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
190 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
191
192 /* ========================================================================= */
193 unsigned long ZEXPORT crc32(crc, buf, len)
194 unsigned long crc;
195 const unsigned char FAR *buf;
196 unsigned len;
197 {
198 if (buf == Z_NULL) return 0UL;
199
200 #ifdef DYNAMIC_CRC_TABLE
201 if (crc_table_empty)
202 make_crc_table();
203 #endif /* DYNAMIC_CRC_TABLE */
204
205 #ifdef BYFOUR
206 if (sizeof(void *) == sizeof(ptrdiff_t)) {
207 u4 endian;
208
209 endian = 1;
210 if (*((unsigned char *)(&endian)))
211 return crc32_little(crc, buf, len);
212 else
213 return crc32_big(crc, buf, len);
214 }
215 #endif /* BYFOUR */
216 crc = crc ^ 0xffffffffUL;
217 while (len >= 8) {
218 DO8;
219 len -= 8;
220 }
221 if (len) do {
222 DO1;
223 } while (--len);
224 return crc ^ 0xffffffffUL;
225 }
226
227 #ifdef BYFOUR
228
229 /* ========================================================================= */
230 #define DOLIT4 c ^= *buf4++; \
231 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
232 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
233 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
234
235 /* ========================================================================= */
236 local unsigned long crc32_little(crc, buf, len)
237 unsigned long crc;
238 const unsigned char FAR *buf;
239 unsigned len;
240 {
241 register u4 c;
242 register const u4 FAR *buf4;
243
244 c = (u4)crc;
245 c = ~c;
246 while (len && ((ptrdiff_t)buf & 3)) {
247 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
248 len--;
249 }
250
251 buf4 = (const u4 FAR *)buf;
252 while (len >= 32) {
253 DOLIT32;
254 len -= 32;
255 }
256 while (len >= 4) {
257 DOLIT4;
258 len -= 4;
259 }
260 buf = (const unsigned char FAR *)buf4;
261
262 if (len) do {
263 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
264 } while (--len);
265 c = ~c;
266 return (unsigned long)c;
267 }
268
269 /* ========================================================================= */
270 #define DOBIG4 c ^= *++buf4; \
271 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
272 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
273 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
274
275 /* ========================================================================= */
276 local unsigned long crc32_big(crc, buf, len)
277 unsigned long crc;
278 const unsigned char FAR *buf;
279 unsigned len;
280 {
281 register u4 c;
282 register const u4 FAR *buf4;
283
284 c = REV((u4)crc);
285 c = ~c;
286 while (len && ((ptrdiff_t)buf & 3)) {
287 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
288 len--;
289 }
290
291 buf4 = (const u4 FAR *)buf;
292 buf4--;
293 while (len >= 32) {
294 DOBIG32;
295 len -= 32;
296 }
297 while (len >= 4) {
298 DOBIG4;
299 len -= 4;
300 }
301 buf4++;
302 buf = (const unsigned char FAR *)buf4;
303
304 if (len) do {
305 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
306 } while (--len);
307 c = ~c;
308 return (unsigned long)(REV(c));
309 }
310
311 #endif /* BYFOUR */