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