1/* crc32.c -- compute the CRC-32 of a data stream
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
35/* Definitions for doing the crc four data bytes at a time. */
36#if !defined(NOBYFOUR) && defined(Z_U4)
37# define BYFOUR
38#endif
39#ifdef BYFOUR
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
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;
59local z_crc_t FAR crc_table[TBLS][256];
60local void make_crc_table OF((void));
61#ifdef MAKECRCH
62 local void write_table OF((FILE *, const z_crc_t FAR *));
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{
92 z_crc_t c;
93 int n, k;
94 z_crc_t poly; /* polynomial exclusive-or pattern */
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++)
108 poly |= (z_crc_t)1 << (31 - p[n]);
109
110 /* generate a crc for every 8-bit value */
111 for (n = 0; n < 256; n++) {
112 c = (z_crc_t)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];
123 crc_table[4][n] = ZSWAP32(c);
124 for (k = 1; k < 4; k++) {
125 c = crc_table[0][c & 0xff] ^ (c >> 8);
126 crc_table[k][n] = c;
127 crc_table[k + 4][n] = ZSWAP32(c);
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");
149 fprintf(out, "local const z_crc_t FAR ");
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;
169 const z_crc_t FAR *table;
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 */
190const z_crc_t FAR * ZEXPORT get_crc_table()
191{
192#ifdef DYNAMIC_CRC_TABLE
193 if (crc_table_empty)
194 make_crc_table();
195#endif /* DYNAMIC_CRC_TABLE */
196 return (const z_crc_t FAR *)crc_table;
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)) {
218 z_crc_t endian;
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{
252 register z_crc_t c;
253 register const z_crc_t FAR *buf4;
254
255 c = (z_crc_t)crc;
256 c = ~c;
257 while (len && ((ptrdiff_t)buf & 3)) {
258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
259 len--;
260 }
261
262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
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{
292 register z_crc_t c;
293 register const z_crc_t FAR *buf4;
294
295 c = ZSWAP32((z_crc_t)crc);
296 c = ~c;
297 while (len && ((ptrdiff_t)buf & 3)) {
298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
299 len--;
300 }
301
302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
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;
319 return (unsigned long)(ZSWAP32(c));
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 ---
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
35/* Definitions for doing the crc four data bytes at a time. */
36#if !defined(NOBYFOUR) && defined(Z_U4)
37# define BYFOUR
38#endif
39#ifdef BYFOUR
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
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;
59local z_crc_t FAR crc_table[TBLS][256];
60local void make_crc_table OF((void));
61#ifdef MAKECRCH
62 local void write_table OF((FILE *, const z_crc_t FAR *));
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{
92 z_crc_t c;
93 int n, k;
94 z_crc_t poly; /* polynomial exclusive-or pattern */
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++)
108 poly |= (z_crc_t)1 << (31 - p[n]);
109
110 /* generate a crc for every 8-bit value */
111 for (n = 0; n < 256; n++) {
112 c = (z_crc_t)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];
123 crc_table[4][n] = ZSWAP32(c);
124 for (k = 1; k < 4; k++) {
125 c = crc_table[0][c & 0xff] ^ (c >> 8);
126 crc_table[k][n] = c;
127 crc_table[k + 4][n] = ZSWAP32(c);
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");
149 fprintf(out, "local const z_crc_t FAR ");
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;
169 const z_crc_t FAR *table;
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 */
190const z_crc_t FAR * ZEXPORT get_crc_table()
191{
192#ifdef DYNAMIC_CRC_TABLE
193 if (crc_table_empty)
194 make_crc_table();
195#endif /* DYNAMIC_CRC_TABLE */
196 return (const z_crc_t FAR *)crc_table;
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)) {
218 z_crc_t endian;
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{
252 register z_crc_t c;
253 register const z_crc_t FAR *buf4;
254
255 c = (z_crc_t)crc;
256 c = ~c;
257 while (len && ((ptrdiff_t)buf & 3)) {
258 c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
259 len--;
260 }
261
262 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
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{
292 register z_crc_t c;
293 register const z_crc_t FAR *buf4;
294
295 c = ZSWAP32((z_crc_t)crc);
296 c = ~c;
297 while (len && ((ptrdiff_t)buf & 3)) {
298 c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
299 len--;
300 }
301
302 buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
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;
319 return (unsigned long)(ZSWAP32(c));
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 ---