Deleted Added
full compact
crc32.c (230837) crc32.c (237248)
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-2006, 2010, 2011 Mark Adler
2 * Copyright (C) 1995-2006, 2010, 2011, 2012 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 */

--- 16 unchanged lines hidden (view full) ---

27# define DYNAMIC_CRC_TABLE
28# endif /* !DYNAMIC_CRC_TABLE */
29#endif /* MAKECRCH */
30
31#include "zutil.h" /* for STDC and FAR definitions */
32
33#define local static
34
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 */

--- 16 unchanged lines hidden (view full) ---

27# define DYNAMIC_CRC_TABLE
28# endif /* !DYNAMIC_CRC_TABLE */
29#endif /* MAKECRCH */
30
31#include "zutil.h" /* for STDC and FAR definitions */
32
33#define local static
34
35/* Find a four-byte integer type for crc32_little() and crc32_big(). */
36#ifndef NOBYFOUR
37# ifdef STDC /* need ANSI C limits.h to determine sizes */
38# include <limits.h>
39# define BYFOUR
40# if (UINT_MAX == 0xffffffffUL)
41 typedef unsigned int u4;
42# else
43# if (ULONG_MAX == 0xffffffffUL)
44 typedef unsigned long u4;
45# else
46# if (USHRT_MAX == 0xffffffffUL)
47 typedef unsigned short u4;
48# else
49# undef BYFOUR /* can't find a four-byte integer type! */
50# endif
51# endif
52# endif
53# endif /* STDC */
54#endif /* !NOBYFOUR */
55
56/* Definitions for doing the crc four data bytes at a time. */
35/* Definitions for doing the crc four data bytes at a time. */
36#if !defined(NOBYFOUR) && defined(Z_U4)
37# define BYFOUR
38#endif
57#ifdef BYFOUR
39#ifdef BYFOUR
58 typedef u4 crc_table_t;
59# define REV(w) ((((w)>>24)&0xff)+(((w)>>8)&0xff00)+ \
60 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
61 local unsigned long crc32_little OF((unsigned long,
62 const unsigned char FAR *, unsigned));
63 local unsigned long crc32_big OF((unsigned long,
64 const unsigned char FAR *, unsigned));
65# define TBLS 8
66#else
40 local unsigned long crc32_little OF((unsigned long,
41 const unsigned char FAR *, unsigned));
42 local unsigned long crc32_big OF((unsigned long,
43 const unsigned char FAR *, unsigned));
44# define TBLS 8
45#else
67 typedef unsigned long crc_table_t;
68# define TBLS 1
69#endif /* BYFOUR */
70
71/* Local functions for crc concatenation */
72local unsigned long gf2_matrix_times OF((unsigned long *mat,
73 unsigned long vec));
74local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
75local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
76
77
78#ifdef DYNAMIC_CRC_TABLE
79
80local volatile int crc_table_empty = 1;
46# define TBLS 1
47#endif /* BYFOUR */
48
49/* Local functions for crc concatenation */
50local unsigned long gf2_matrix_times OF((unsigned long *mat,
51 unsigned long vec));
52local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
53local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
54
55
56#ifdef DYNAMIC_CRC_TABLE
57
58local volatile int crc_table_empty = 1;
81local crc_table_t FAR crc_table[TBLS][256];
59local z_crc_t FAR crc_table[TBLS][256];
82local void make_crc_table OF((void));
83#ifdef MAKECRCH
60local void make_crc_table OF((void));
61#ifdef MAKECRCH
84 local void write_table OF((FILE *, const crc_table_t FAR *));
62 local void write_table OF((FILE *, const z_crc_t FAR *));
85#endif /* MAKECRCH */
86/*
87 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
88 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.
89
90 Polynomials over GF(2) are represented in binary, one bit per coefficient,
91 with the lowest powers in the most significant bit. Then adding polynomials
92 is just exclusive-or, and multiplying a polynomial by x is a right shift by

--- 13 unchanged lines hidden (view full) ---

106 The first table is simply the CRC of all possible eight bit values. This is
107 all the information needed to generate CRCs on data a byte at a time for all
108 combinations of CRC register values and incoming bytes. The remaining tables
109 allow for word-at-a-time CRC calculation for both big-endian and little-
110 endian machines, where a word is four bytes.
111*/
112local void make_crc_table()
113{
63#endif /* MAKECRCH */
64/*
65 Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
66 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.
67
68 Polynomials over GF(2) are represented in binary, one bit per coefficient,
69 with the lowest powers in the most significant bit. Then adding polynomials
70 is just exclusive-or, and multiplying a polynomial by x is a right shift by

--- 13 unchanged lines hidden (view full) ---

84 The first table is simply the CRC of all possible eight bit values. This is
85 all the information needed to generate CRCs on data a byte at a time for all
86 combinations of CRC register values and incoming bytes. The remaining tables
87 allow for word-at-a-time CRC calculation for both big-endian and little-
88 endian machines, where a word is four bytes.
89*/
90local void make_crc_table()
91{
114 crc_table_t c;
92 z_crc_t c;
115 int n, k;
93 int n, k;
116 crc_table_t poly; /* polynomial exclusive-or pattern */
94 z_crc_t poly; /* polynomial exclusive-or pattern */
117 /* terms of polynomial defining this crc (except x^32): */
118 static volatile int first = 1; /* flag to limit concurrent making */
119 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
120
121 /* See if another task is already doing this (not thread-safe, but better
122 than nothing -- significantly reduces duration of vulnerability in
123 case the advice about DYNAMIC_CRC_TABLE is ignored) */
124 if (first) {
125 first = 0;
126
127 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
128 poly = 0;
129 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
95 /* terms of polynomial defining this crc (except x^32): */
96 static volatile int first = 1; /* flag to limit concurrent making */
97 static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
98
99 /* See if another task is already doing this (not thread-safe, but better
100 than nothing -- significantly reduces duration of vulnerability in
101 case the advice about DYNAMIC_CRC_TABLE is ignored) */
102 if (first) {
103 first = 0;
104
105 /* make exclusive-or pattern from polynomial (0xedb88320UL) */
106 poly = 0;
107 for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
130 poly |= (crc_table_t)1 << (31 - p[n]);
108 poly |= (z_crc_t)1 << (31 - p[n]);
131
132 /* generate a crc for every 8-bit value */
133 for (n = 0; n < 256; n++) {
109
110 /* generate a crc for every 8-bit value */
111 for (n = 0; n < 256; n++) {
134 c = (crc_table_t)n;
112 c = (z_crc_t)n;
135 for (k = 0; k < 8; k++)
136 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
137 crc_table[0][n] = c;
138 }
139
140#ifdef BYFOUR
141 /* generate crc for each value followed by one, two, and three zeros,
142 and then the byte reversal of those as well as the first table */
143 for (n = 0; n < 256; n++) {
144 c = crc_table[0][n];
113 for (k = 0; k < 8; k++)
114 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
115 crc_table[0][n] = c;
116 }
117
118#ifdef BYFOUR
119 /* generate crc for each value followed by one, two, and three zeros,
120 and then the byte reversal of those as well as the first table */
121 for (n = 0; n < 256; n++) {
122 c = crc_table[0][n];
145 crc_table[4][n] = REV(c);
123 crc_table[4][n] = ZSWAP32(c);
146 for (k = 1; k < 4; k++) {
147 c = crc_table[0][c & 0xff] ^ (c >> 8);
148 crc_table[k][n] = c;
124 for (k = 1; k < 4; k++) {
125 c = crc_table[0][c & 0xff] ^ (c >> 8);
126 crc_table[k][n] = c;
149 crc_table[k + 4][n] = REV(c);
127 crc_table[k + 4][n] = ZSWAP32(c);
150 }
151 }
152#endif /* BYFOUR */
153
154 crc_table_empty = 0;
155 }
156 else { /* not first */
157 /* wait for the other guy to finish (not efficient, but rare) */

--- 5 unchanged lines hidden (view full) ---

163 /* write out CRC tables to crc32.h */
164 {
165 FILE *out;
166
167 out = fopen("crc32.h", "w");
168 if (out == NULL) return;
169 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
170 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
128 }
129 }
130#endif /* BYFOUR */
131
132 crc_table_empty = 0;
133 }
134 else { /* not first */
135 /* wait for the other guy to finish (not efficient, but rare) */

--- 5 unchanged lines hidden (view full) ---

141 /* write out CRC tables to crc32.h */
142 {
143 FILE *out;
144
145 out = fopen("crc32.h", "w");
146 if (out == NULL) return;
147 fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
148 fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
171 fprintf(out, "local const crc_table_t FAR ");
149 fprintf(out, "local const z_crc_t FAR ");
172 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
173 write_table(out, crc_table[0]);
174# ifdef BYFOUR
175 fprintf(out, "#ifdef BYFOUR\n");
176 for (k = 1; k < 8; k++) {
177 fprintf(out, " },\n {\n");
178 write_table(out, crc_table[k]);
179 }
180 fprintf(out, "#endif\n");
181# endif /* BYFOUR */
182 fprintf(out, " }\n};\n");
183 fclose(out);
184 }
185#endif /* MAKECRCH */
186}
187
188#ifdef MAKECRCH
189local void write_table(out, table)
190 FILE *out;
150 fprintf(out, "crc_table[TBLS][256] =\n{\n {\n");
151 write_table(out, crc_table[0]);
152# ifdef BYFOUR
153 fprintf(out, "#ifdef BYFOUR\n");
154 for (k = 1; k < 8; k++) {
155 fprintf(out, " },\n {\n");
156 write_table(out, crc_table[k]);
157 }
158 fprintf(out, "#endif\n");
159# endif /* BYFOUR */
160 fprintf(out, " }\n};\n");
161 fclose(out);
162 }
163#endif /* MAKECRCH */
164}
165
166#ifdef MAKECRCH
167local void write_table(out, table)
168 FILE *out;
191 const crc_table_t FAR *table;
169 const z_crc_t FAR *table;
192{
193 int n;
194
195 for (n = 0; n < 256; n++)
196 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ",
197 (unsigned long)(table[n]),
198 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
199}

--- 4 unchanged lines hidden (view full) ---

204 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
205 */
206#include "crc32.h"
207#endif /* DYNAMIC_CRC_TABLE */
208
209/* =========================================================================
210 * This function can be used by asm versions of crc32()
211 */
170{
171 int n;
172
173 for (n = 0; n < 256; n++)
174 fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : " ",
175 (unsigned long)(table[n]),
176 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
177}

--- 4 unchanged lines hidden (view full) ---

182 * Tables of CRC-32s of all single-byte values, made by make_crc_table().
183 */
184#include "crc32.h"
185#endif /* DYNAMIC_CRC_TABLE */
186
187/* =========================================================================
188 * This function can be used by asm versions of crc32()
189 */
212const unsigned long FAR * ZEXPORT get_crc_table()
190const z_crc_t FAR * ZEXPORT get_crc_table()
213{
214#ifdef DYNAMIC_CRC_TABLE
215 if (crc_table_empty)
216 make_crc_table();
217#endif /* DYNAMIC_CRC_TABLE */
191{
192#ifdef DYNAMIC_CRC_TABLE
193 if (crc_table_empty)
194 make_crc_table();
195#endif /* DYNAMIC_CRC_TABLE */
218 return (const unsigned long FAR *)crc_table;
196 return (const z_crc_t FAR *)crc_table;
219}
220
221/* ========================================================================= */
222#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
223#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
224
225/* ========================================================================= */
226unsigned long ZEXPORT crc32(crc, buf, len)

--- 5 unchanged lines hidden (view full) ---

232
233#ifdef DYNAMIC_CRC_TABLE
234 if (crc_table_empty)
235 make_crc_table();
236#endif /* DYNAMIC_CRC_TABLE */
237
238#ifdef BYFOUR
239 if (sizeof(void *) == sizeof(ptrdiff_t)) {
197}
198
199/* ========================================================================= */
200#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
201#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
202
203/* ========================================================================= */
204unsigned long ZEXPORT crc32(crc, buf, len)

--- 5 unchanged lines hidden (view full) ---

210
211#ifdef DYNAMIC_CRC_TABLE
212 if (crc_table_empty)
213 make_crc_table();
214#endif /* DYNAMIC_CRC_TABLE */
215
216#ifdef BYFOUR
217 if (sizeof(void *) == sizeof(ptrdiff_t)) {
240 u4 endian;
218 z_crc_t endian;
241
242 endian = 1;
243 if (*((unsigned char *)(&endian)))
244 return crc32_little(crc, buf, len);
245 else
246 return crc32_big(crc, buf, len);
247 }
248#endif /* BYFOUR */

--- 17 unchanged lines hidden (view full) ---

266#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
267
268/* ========================================================================= */
269local unsigned long crc32_little(crc, buf, len)
270 unsigned long crc;
271 const unsigned char FAR *buf;
272 unsigned len;
273{
219
220 endian = 1;
221 if (*((unsigned char *)(&endian)))
222 return crc32_little(crc, buf, len);
223 else
224 return crc32_big(crc, buf, len);
225 }
226#endif /* BYFOUR */

--- 17 unchanged lines hidden (view full) ---

244#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
245
246/* ========================================================================= */
247local unsigned long crc32_little(crc, buf, len)
248 unsigned long crc;
249 const unsigned char FAR *buf;
250 unsigned len;
251{
274 register u4 c;
275 register const u4 FAR *buf4;
252 register z_crc_t c;
253 register const z_crc_t FAR *buf4;
276
254
277 c = (u4)crc;
255 c = (z_crc_t)crc;
278 c = ~c;
279 while (len && ((ptrdiff_t)buf & 3)) {
280 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
281 len--;
282 }
283
256 c = ~c;
257 while (len && ((ptrdiff_t)buf & 3)) {
258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
259 len--;
260 }
261
284 buf4 = (const u4 FAR *)(const void FAR *)buf;
262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
285 while (len >= 32) {
286 DOLIT32;
287 len -= 32;
288 }
289 while (len >= 4) {
290 DOLIT4;
291 len -= 4;
292 }

--- 13 unchanged lines hidden (view full) ---

306#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
307
308/* ========================================================================= */
309local unsigned long crc32_big(crc, buf, len)
310 unsigned long crc;
311 const unsigned char FAR *buf;
312 unsigned len;
313{
263 while (len >= 32) {
264 DOLIT32;
265 len -= 32;
266 }
267 while (len >= 4) {
268 DOLIT4;
269 len -= 4;
270 }

--- 13 unchanged lines hidden (view full) ---

284#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
285
286/* ========================================================================= */
287local unsigned long crc32_big(crc, buf, len)
288 unsigned long crc;
289 const unsigned char FAR *buf;
290 unsigned len;
291{
314 register u4 c;
315 register const u4 FAR *buf4;
292 register z_crc_t c;
293 register const z_crc_t FAR *buf4;
316
294
317 c = REV((u4)crc);
295 c = ZSWAP32((z_crc_t)crc);
318 c = ~c;
319 while (len && ((ptrdiff_t)buf & 3)) {
320 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
321 len--;
322 }
323
296 c = ~c;
297 while (len && ((ptrdiff_t)buf & 3)) {
298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
299 len--;
300 }
301
324 buf4 = (const u4 FAR *)(const void FAR *)buf;
302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
325 buf4--;
326 while (len >= 32) {
327 DOBIG32;
328 len -= 32;
329 }
330 while (len >= 4) {
331 DOBIG4;
332 len -= 4;
333 }
334 buf4++;
335 buf = (const unsigned char FAR *)buf4;
336
337 if (len) do {
338 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
339 } while (--len);
340 c = ~c;
303 buf4--;
304 while (len >= 32) {
305 DOBIG32;
306 len -= 32;
307 }
308 while (len >= 4) {
309 DOBIG4;
310 len -= 4;
311 }
312 buf4++;
313 buf = (const unsigned char FAR *)buf4;
314
315 if (len) do {
316 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
317 } while (--len);
318 c = ~c;
341 return (unsigned long)(REV(c));
319 return (unsigned long)(ZSWAP32(c));
342}
343
344#endif /* BYFOUR */
345
346#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
347
348/* ========================================================================= */
349local unsigned long gf2_matrix_times(mat, vec)

--- 98 unchanged lines hidden ---
320}
321
322#endif /* BYFOUR */
323
324#define GF2_DIM 32 /* dimension of GF(2) vectors (length of CRC) */
325
326/* ========================================================================= */
327local unsigned long gf2_matrix_times(mat, vec)

--- 98 unchanged lines hidden ---