1/* crc32.c -- compute the CRC-32 of a data stream
| 1/* crc32.c -- compute the CRC-32 of a data stream
|
2 * Copyright (C) 1995-2002 Mark Adler
3 * For conditions of distribution and use, see copyright notice in zlib.h
| 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.
|
4 */
5
6/* @(#) $Id$ */
7
| 10 */
11
12/* @(#) $Id$ */
13
|
8#include "zlib.h"
| 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 */
|
9
| 20
|
| 21#include "zutil.h" /* for STDC and FAR definitions */
22
|
10#define local static
11
| 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
|
12#ifdef DYNAMIC_CRC_TABLE
13
14local int crc_table_empty = 1;
| 59#ifdef DYNAMIC_CRC_TABLE
60
61local int crc_table_empty = 1;
|
15local uLongf crc_table[256];
| 62local unsigned long FAR crc_table[TBLS][256];
|
16local void make_crc_table OF((void));
| 63local void make_crc_table OF((void));
|
| 64#ifdef MAKECRCH
65 local void write_table OF((FILE *, const unsigned long FAR *));
66#endif /* MAKECRCH */
|
17
18/*
| 67
68/*
|
19 Generate a table for a byte-wise 32-bit CRC calculation on the polynomial:
| 69 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
|
20 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.
21
22 Polynomials over GF(2) are represented in binary, one bit per coefficient,
23 with the lowest powers in the most significant bit. Then adding polynomials
24 is just exclusive-or, and multiplying a polynomial by x is a right shift by
25 one. If we call the above polynomial p, and represent a byte as the
26 polynomial q, also with the lowest power in the most significant bit (so the
27 byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
28 where a mod b means the remainder after dividing a by b.
29
30 This calculation is done using the shift-register method of multiplying and
31 taking the remainder. The register is initialized to zero, and for each
32 incoming bit, x^32 is added mod p to the register if the bit is a one (where
33 x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
34 x (which is shifting right by one and adding x^32 mod p if the bit shifted
35 out is a one). We start with the highest power (least significant bit) of
36 q and repeat for all eight bits of q.
37
| 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
|
38 The table is simply the CRC of all possible eight bit values. This is all
39 the information needed to generate CRC's on data a byte at a time for all
40 combinations of CRC register values and incoming bytes.
| 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.
|
41*/
42local void make_crc_table()
43{
| 93*/
94local void make_crc_table()
95{
|
44 uLong c;
45 int n, k;
46 uLong poly; /* polynomial exclusive-or pattern */
47 /* terms of polynomial defining this crc (except x^32): */
48 static const Byte p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
| 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};
|
49
| 101
|
50 /* make exclusive-or pattern from polynomial (0xedb88320L) */
51 poly = 0L;
52 for (n = 0; n < sizeof(p)/sizeof(Byte); n++)
53 poly |= 1L << (31 - p[n]);
54
55 for (n = 0; n < 256; n++)
56 {
57 c = (uLong)n;
58 for (k = 0; k < 8; k++)
59 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
60 crc_table[n] = c;
61 }
| 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
|
62 crc_table_empty = 0;
| 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 */
|
63}
| 155}
|
64#else
| 156
157#ifdef MAKECRCH
158local 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 */
|
65/* ========================================================================
| 171/* ========================================================================
|
66 * Table of CRC-32's of all single-byte values (made by make_crc_table)
| 172 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
|
67 */
| 173 */
|
68local const uLongf crc_table[256] = {
69 0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
70 0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
71 0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
72 0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
73 0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
74 0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
75 0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
76 0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
77 0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
78 0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
79 0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
80 0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
81 0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
82 0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
83 0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
84 0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
85 0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
86 0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
87 0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
88 0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
89 0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
90 0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
91 0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
92 0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
93 0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
94 0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
95 0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
96 0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
97 0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
98 0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
99 0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
100 0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
101 0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
102 0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
103 0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
104 0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
105 0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
106 0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
107 0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
108 0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
109 0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
110 0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
111 0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
112 0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
113 0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
114 0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
115 0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
116 0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
117 0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
118 0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
119 0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
120 0x2d02ef8dL
121};
122#endif
| 174#include "crc32.h"
175#endif /* DYNAMIC_CRC_TABLE */
|
123
124/* =========================================================================
125 * This function can be used by asm versions of crc32()
126 */
| 176
177/* =========================================================================
178 * This function can be used by asm versions of crc32()
179 */
|
127const uLongf * ZEXPORT get_crc_table()
| 180const unsigned long FAR * ZEXPORT get_crc_table()
|
128{
129#ifdef DYNAMIC_CRC_TABLE
130 if (crc_table_empty) make_crc_table();
| 181{
182#ifdef DYNAMIC_CRC_TABLE
183 if (crc_table_empty) make_crc_table();
|
131#endif
132 return (const uLongf *)crc_table;
| 184#endif /* DYNAMIC_CRC_TABLE */
185 return (const unsigned long FAR *)crc_table;
|
133}
134
135/* ========================================================================= */
| 186}
187
188/* ========================================================================= */
|
136#define DO1(buf) crc = crc_table[((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8);
137#define DO2(buf) DO1(buf); DO1(buf);
138#define DO4(buf) DO2(buf); DO2(buf);
139#define DO8(buf) DO4(buf); DO4(buf);
| 189#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
190#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
|
140
141/* ========================================================================= */
| 191
192/* ========================================================================= */
|
142uLong ZEXPORT crc32(crc, buf, len)
143 uLong crc;
144 const Bytef *buf;
145 uInt len;
| 193unsigned long ZEXPORT crc32(crc, buf, len)
194 unsigned long crc;
195 const unsigned char FAR *buf;
196 unsigned len;
|
146{
| 197{
|
147 if (buf == Z_NULL) return 0L;
| 198 if (buf == Z_NULL) return 0UL;
199
|
148#ifdef DYNAMIC_CRC_TABLE
149 if (crc_table_empty)
| 200#ifdef DYNAMIC_CRC_TABLE
201 if (crc_table_empty)
|
150 make_crc_table();
151#endif
152 crc = crc ^ 0xffffffffL;
153 while (len >= 8)
154 {
155 DO8(buf);
156 len -= 8;
| 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);
|
157 }
| 214 }
|
| 215#endif /* BYFOUR */
216 crc = crc ^ 0xffffffffUL;
217 while (len >= 8) {
218 DO8;
219 len -= 8;
220 }
|
158 if (len) do {
| 221 if (len) do {
|
159 DO1(buf);
| 222 DO1;
|
160 } while (--len);
| 223 } while (--len);
|
161 return crc ^ 0xffffffffL;
| 224 return crc ^ 0xffffffffUL;
|
162}
| 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/* ========================================================================= */
236local 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/* ========================================================================= */
276local 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 */
|
| |