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