]> git.saurik.com Git - wxWidgets.git/blame - src/zlib/crc32.c
Add a few missing appearance screenshots for the manual.
[wxWidgets.git] / src / zlib / crc32.c
CommitLineData
c801d85f 1/* crc32.c -- compute the CRC-32 of a data stream
41faf807 2 * Copyright (C) 1995-2005 Mark Adler
e6ebb514 3 * For conditions of distribution and use, see copyright notice in zlib.h
51dbdf87
VS
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
41faf807
MW
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.
c801d85f
KB
10 */
11
c801d85f 12
ba0052f3
VS
13/*
14 Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
15 protection on the static variables used to control the first-use generation
16 of the crc tables. Therefore, if you #define DYNAMIC_CRC_TABLE, you should
17 first call get_crc_table() to initialize the tables before allowing more than
18 one thread to use crc32().
19 */
20
51dbdf87
VS
21#ifdef MAKECRCH
22# include <stdio.h>
23# ifndef DYNAMIC_CRC_TABLE
24# define DYNAMIC_CRC_TABLE
25# endif /* !DYNAMIC_CRC_TABLE */
26#endif /* MAKECRCH */
27
28#include "zutil.h" /* for STDC and FAR definitions */
c801d85f
KB
29
30#define local static
31
51dbdf87
VS
32/* Find a four-byte integer type for crc32_little() and crc32_big(). */
33#ifndef NOBYFOUR
34# ifdef STDC /* need ANSI C limits.h to determine sizes */
35# include <limits.h>
36# define BYFOUR
37# if (UINT_MAX == 0xffffffffUL)
38 typedef unsigned int u4;
39# else
40# if (ULONG_MAX == 0xffffffffUL)
41 typedef unsigned long u4;
42# else
43# if (USHRT_MAX == 0xffffffffUL)
44 typedef unsigned short u4;
45# else
46# undef BYFOUR /* can't find a four-byte integer type! */
47# endif
48# endif
49# endif
50# endif /* STDC */
51#endif /* !NOBYFOUR */
52
53/* Definitions for doing the crc four data bytes at a time. */
54#ifdef BYFOUR
55# define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
56 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
57 local unsigned long crc32_little OF((unsigned long,
58 const unsigned char FAR *, unsigned));
59 local unsigned long crc32_big OF((unsigned long,
60 const unsigned char FAR *, unsigned));
61# define TBLS 8
62#else
63# define TBLS 1
64#endif /* BYFOUR */
65
41faf807
MW
66/* Local functions for crc concatenation */
67local unsigned long gf2_matrix_times OF((unsigned long *mat,
68 unsigned long vec));
69local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
70
c801d85f
KB
71#ifdef DYNAMIC_CRC_TABLE
72
ba0052f3 73local volatile int crc_table_empty = 1;
51dbdf87 74local unsigned long FAR crc_table[TBLS][256];
c801d85f 75local void make_crc_table OF((void));
51dbdf87
VS
76#ifdef MAKECRCH
77 local void write_table OF((FILE *, const unsigned long FAR *));
78#endif /* MAKECRCH */
c801d85f 79/*
51dbdf87 80 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
c801d85f
KB
81 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.
82
83 Polynomials over GF(2) are represented in binary, one bit per coefficient,
84 with the lowest powers in the most significant bit. Then adding polynomials
85 is just exclusive-or, and multiplying a polynomial by x is a right shift by
86 one. If we call the above polynomial p, and represent a byte as the
87 polynomial q, also with the lowest power in the most significant bit (so the
88 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
89 where a mod b means the remainder after dividing a by b.
90
91 This calculation is done using the shift-register method of multiplying and
92 taking the remainder. The register is initialized to zero, and for each
93 incoming bit, x^32 is added mod p to the register if the bit is a one (where
94 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
95 x (which is shifting right by one and adding x^32 mod p if the bit shifted
96 out is a one). We start with the highest power (least significant bit) of
97 q and repeat for all eight bits of q.
98
51dbdf87
VS
99 The first table is simply the CRC of all possible eight bit values. This is
100 all the information needed to generate CRCs on data a byte at a time for all
101 combinations of CRC register values and incoming bytes. The remaining tables
102 allow for word-at-a-time CRC calculation for both big-endian and little-
103 endian machines, where a word is four bytes.
c801d85f
KB
104*/
105local void make_crc_table()
106{
51dbdf87
VS
107 unsigned long c;
108 int n, k;
ba0052f3 109 unsigned long poly; /* polynomial exclusive-or pattern */
51dbdf87 110 /* terms of polynomial defining this crc (except x^32): */
ba0052f3 111 static volatile int first = 1; /* flag to limit concurrent making */
51dbdf87
VS
112 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
113
ba0052f3
VS
114 /* See if another task is already doing this (not thread-safe, but better
115 than nothing -- significantly reduces duration of vulnerability in
116 case the advice about DYNAMIC_CRC_TABLE is ignored) */
117 if (first) {
118 first = 0;
119
120 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
121 poly = 0UL;
122 for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
123 poly |= 1UL << (31 - p[n]);
124
125 /* generate a crc for every 8-bit value */
126 for (n = 0; n < 256; n++) {
127 c = (unsigned long)n;
128 for (k = 0; k < 8; k++)
129 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
130 crc_table[0][n] = c;
131 }
51dbdf87
VS
132
133#ifdef BYFOUR
ba0052f3
VS
134 /* generate crc for each value followed by one, two, and three zeros,
135 and then the byte reversal of those as well as the first table */
136 for (n = 0; n < 256; n++) {
137 c = crc_table[0][n];
138 crc_table[4][n] = REV(c);
139 for (k = 1; k < 4; k++) {
140 c = crc_table[0][c & 0xff] ^ (c >> 8);
141 crc_table[k][n] = c;
142 crc_table[k + 4][n] = REV(c);
143 }
51dbdf87 144 }
51dbdf87
VS
145#endif /* BYFOUR */
146
ba0052f3
VS
147 crc_table_empty = 0;
148 }
149 else { /* not first */
150 /* wait for the other guy to finish (not efficient, but rare) */
151 while (crc_table_empty)
152 ;
153 }
51dbdf87
VS
154
155#ifdef MAKECRCH
156 /* write out CRC tables to crc32.h */
157 {
158 FILE *out;
159
160 out = fopen("crc32.h", "w");
161 if (out == NULL) return;
162 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
163 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
164 fprintf(out, "local const unsigned long FAR ");
165 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
166 write_table(out, crc_table[0]);
167# ifdef BYFOUR
168 fprintf(out, "#ifdef BYFOUR\n");
169 for (k = 1; k < 8; k++) {
170 fprintf(out, " },\n {\n");
171 write_table(out, crc_table[k]);
172 }
173 fprintf(out, "#endif\n");
174# endif /* BYFOUR */
175 fprintf(out, " }\n};\n");
176 fclose(out);
177 }
178#endif /* MAKECRCH */
c801d85f 179}
51dbdf87
VS
180
181#ifdef MAKECRCH
182local void write_table(out, table)
183 FILE *out;
184 const unsigned long FAR *table;
185{
186 int n;
187
188 for (n = 0; n < 256; n++)
189 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ", table[n],
190 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
191}
192#endif /* MAKECRCH */
193
194#else /* !DYNAMIC_CRC_TABLE */
c801d85f 195/* ========================================================================
51dbdf87 196 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
c801d85f 197 */
51dbdf87
VS
198#include "crc32.h"
199#endif /* DYNAMIC_CRC_TABLE */
c801d85f
KB
200
201/* =========================================================================
202 * This function can be used by asm versions of crc32()
203 */
51dbdf87 204const unsigned long FAR * ZEXPORT get_crc_table()
c801d85f
KB
205{
206#ifdef DYNAMIC_CRC_TABLE
ba0052f3
VS
207 if (crc_table_empty)
208 make_crc_table();
51dbdf87 209#endif /* DYNAMIC_CRC_TABLE */
ba0052f3 210 return (const unsigned long FAR *)crc_table;
c801d85f
KB
211}
212
213/* ========================================================================= */
51dbdf87
VS
214#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
215#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
c801d85f
KB
216
217/* ========================================================================= */
51dbdf87
VS
218unsigned long ZEXPORT crc32(crc, buf, len)
219 unsigned long crc;
220 const unsigned char FAR *buf;
221 unsigned len;
c801d85f 222{
51dbdf87
VS
223 if (buf == Z_NULL) return 0UL;
224
c801d85f
KB
225#ifdef DYNAMIC_CRC_TABLE
226 if (crc_table_empty)
51dbdf87
VS
227 make_crc_table();
228#endif /* DYNAMIC_CRC_TABLE */
229
230#ifdef BYFOUR
231 if (sizeof(void *) == sizeof(ptrdiff_t)) {
232 u4 endian;
233
234 endian = 1;
235 if (*((unsigned char *)(&endian)))
236 return crc32_little(crc, buf, len);
237 else
238 return crc32_big(crc, buf, len);
239 }
240#endif /* BYFOUR */
241 crc = crc ^ 0xffffffffUL;
242 while (len >= 8) {
243 DO8;
244 len -= 8;
245 }
246 if (len) do {
247 DO1;
248 } while (--len);
249 return crc ^ 0xffffffffUL;
250}
251
252#ifdef BYFOUR
253
254/* ========================================================================= */
255#define DOLIT4 c ^= *buf4++; \
256 c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
257 crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
258#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
259
260/* ========================================================================= */
261local unsigned long crc32_little(crc, buf, len)
262 unsigned long crc;
263 const unsigned char FAR *buf;
264 unsigned len;
265{
266 register u4 c;
267 register const u4 FAR *buf4;
268
269 c = (u4)crc;
270 c = ~c;
271 while (len && ((ptrdiff_t)buf & 3)) {
272 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
273 len--;
274 }
275
41faf807 276 buf4 = (const u4 FAR *)(const void FAR *)buf;
51dbdf87
VS
277 while (len >= 32) {
278 DOLIT32;
279 len -= 32;
280 }
281 while (len >= 4) {
282 DOLIT4;
283 len -= 4;
284 }
285 buf = (const unsigned char FAR *)buf4;
286
287 if (len) do {
288 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
289 } while (--len);
290 c = ~c;
291 return (unsigned long)c;
292}
293
294/* ========================================================================= */
295#define DOBIG4 c ^= *++buf4; \
296 c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
297 crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
298#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
299
300/* ========================================================================= */
301local unsigned long crc32_big(crc, buf, len)
302 unsigned long crc;
303 const unsigned char FAR *buf;
304 unsigned len;
305{
306 register u4 c;
307 register const u4 FAR *buf4;
308
309 c = REV((u4)crc);
310 c = ~c;
311 while (len && ((ptrdiff_t)buf & 3)) {
312 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
313 len--;
314 }
315
41faf807 316 buf4 = (const u4 FAR *)(const void FAR *)buf;
51dbdf87
VS
317 buf4--;
318 while (len >= 32) {
319 DOBIG32;
320 len -= 32;
c801d85f 321 }
51dbdf87
VS
322 while (len >= 4) {
323 DOBIG4;
324 len -= 4;
325 }
326 buf4++;
327 buf = (const unsigned char FAR *)buf4;
328
c801d85f 329 if (len) do {
51dbdf87 330 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
c801d85f 331 } while (--len);
51dbdf87
VS
332 c = ~c;
333 return (unsigned long)(REV(c));
c801d85f 334}
51dbdf87
VS
335
336#endif /* BYFOUR */
41faf807
MW
337
338#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
339
340/* ========================================================================= */
341local unsigned long gf2_matrix_times(mat, vec)
342 unsigned long *mat;
343 unsigned long vec;
344{
345 unsigned long sum;
346
347 sum = 0;
348 while (vec) {
349 if (vec & 1)
350 sum ^= *mat;
351 vec >>= 1;
352 mat++;
353 }
354 return sum;
355}
356
357/* ========================================================================= */
358local void gf2_matrix_square(square, mat)
359 unsigned long *square;
360 unsigned long *mat;
361{
362 int n;
363
364 for (n = 0; n < GF2_DIM; n++)
365 square[n] = gf2_matrix_times(mat, mat[n]);
366}
367
368/* ========================================================================= */
369uLong ZEXPORT crc32_combine(crc1, crc2, len2)
370 uLong crc1;
371 uLong crc2;
372 z_off_t len2;
373{
374 int n;
375 unsigned long row;
376 unsigned long even[GF2_DIM]; /* even-power-of-two zeros operator */
377 unsigned long odd[GF2_DIM]; /* odd-power-of-two zeros operator */
378
379 /* degenerate case */
380 if (len2 == 0)
381 return crc1;
382
383 /* put operator for one zero bit in odd */
384 odd[0] = 0xedb88320L; /* CRC-32 polynomial */
385 row = 1;
386 for (n = 1; n < GF2_DIM; n++) {
387 odd[n] = row;
388 row <<= 1;
389 }
390
391 /* put operator for two zero bits in even */
392 gf2_matrix_square(even, odd);
393
394 /* put operator for four zero bits in odd */
395 gf2_matrix_square(odd, even);
396
397 /* apply len2 zeros to crc1 (first square will put the operator for one
398 zero byte, eight zero bits, in even) */
399 do {
400 /* apply zeros operator for this bit of len2 */
401 gf2_matrix_square(even, odd);
402 if (len2 & 1)
403 crc1 = gf2_matrix_times(even, crc1);
404 len2 >>= 1;
405
406 /* if no more bits set, then done */
407 if (len2 == 0)
408 break;
409
410 /* another iteration of the loop with odd and even swapped */
411 gf2_matrix_square(odd, even);
412 if (len2 & 1)
413 crc1 = gf2_matrix_times(odd, crc1);
414 len2 >>= 1;
415
416 /* if no more bits set, then done */
417 } while (len2 != 0);
418
419 /* return combined crc */
420 crc1 ^= crc2;
421 return crc1;
422}