Back to index

tetex-bin  3.0
crc32.c
Go to the documentation of this file.
00001 /* crc32.c -- compute the CRC-32 of a data stream
00002  * Copyright (C) 1995-2003 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h
00004  *
00005  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
00006  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
00007  * tables for updating the shift register in one step with three exclusive-ors
00008  * instead of four steps with four exclusive-ors.  This results about a factor
00009  * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
00010  */
00011 
00012 /* @(#) $Id$ */
00013 
00014 #ifdef MAKECRCH
00015 #  include <stdio.h>
00016 #  ifndef DYNAMIC_CRC_TABLE
00017 #    define DYNAMIC_CRC_TABLE
00018 #  endif /* !DYNAMIC_CRC_TABLE */
00019 #endif /* MAKECRCH */
00020 
00021 #include "zutil.h"      /* for STDC and FAR definitions */
00022 
00023 #define local static
00024 
00025 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
00026 #ifndef NOBYFOUR
00027 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
00028 #    include <limits.h>
00029 #    define BYFOUR
00030 #    if (UINT_MAX == 0xffffffffUL)
00031        typedef unsigned int u4;
00032 #    else
00033 #      if (ULONG_MAX == 0xffffffffUL)
00034          typedef unsigned long u4;
00035 #      else
00036 #        if (USHRT_MAX == 0xffffffffUL)
00037            typedef unsigned short u4;
00038 #        else
00039 #          undef BYFOUR     /* can't find a four-byte integer type! */
00040 #        endif
00041 #      endif
00042 #    endif
00043 #  endif /* STDC */
00044 #endif /* !NOBYFOUR */
00045 
00046 /* Definitions for doing the crc four data bytes at a time. */
00047 #ifdef BYFOUR
00048 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
00049                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
00050    local unsigned long crc32_little OF((unsigned long,
00051                         const unsigned char FAR *, unsigned));
00052    local unsigned long crc32_big OF((unsigned long,
00053                         const unsigned char FAR *, unsigned));
00054 #  define TBLS 8
00055 #else
00056 #  define TBLS 1
00057 #endif /* BYFOUR */
00058 
00059 #ifdef DYNAMIC_CRC_TABLE
00060 
00061 local int crc_table_empty = 1;
00062 local unsigned long FAR crc_table[TBLS][256];
00063 local void make_crc_table OF((void));
00064 #ifdef MAKECRCH
00065    local void write_table OF((FILE *, const unsigned long FAR *));
00066 #endif /* MAKECRCH */
00067 
00068 /*
00069   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
00070   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.
00071 
00072   Polynomials over GF(2) are represented in binary, one bit per coefficient,
00073   with the lowest powers in the most significant bit.  Then adding polynomials
00074   is just exclusive-or, and multiplying a polynomial by x is a right shift by
00075   one.  If we call the above polynomial p, and represent a byte as the
00076   polynomial q, also with the lowest power in the most significant bit (so the
00077   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
00078   where a mod b means the remainder after dividing a by b.
00079 
00080   This calculation is done using the shift-register method of multiplying and
00081   taking the remainder.  The register is initialized to zero, and for each
00082   incoming bit, x^32 is added mod p to the register if the bit is a one (where
00083   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
00084   x (which is shifting right by one and adding x^32 mod p if the bit shifted
00085   out is a one).  We start with the highest power (least significant bit) of
00086   q and repeat for all eight bits of q.
00087 
00088   The first table is simply the CRC of all possible eight bit values.  This is
00089   all the information needed to generate CRCs on data a byte at a time for all
00090   combinations of CRC register values and incoming bytes.  The remaining tables
00091   allow for word-at-a-time CRC calculation for both big-endian and little-
00092   endian machines, where a word is four bytes.
00093 */
00094 local void make_crc_table()
00095 {
00096     unsigned long c;
00097     int n, k;
00098     unsigned long poly;            /* polynomial exclusive-or pattern */
00099     /* terms of polynomial defining this crc (except x^32): */
00100     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
00101 
00102     /* make exclusive-or pattern from polynomial (0xedb88320UL) */
00103     poly = 0UL;
00104     for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
00105         poly |= 1UL << (31 - p[n]);
00106 
00107     /* generate a crc for every 8-bit value */
00108     for (n = 0; n < 256; n++) {
00109         c = (unsigned long)n;
00110         for (k = 0; k < 8; k++)
00111             c = c & 1 ? poly ^ (c >> 1) : c >> 1;
00112         crc_table[0][n] = c;
00113     }
00114 
00115 #ifdef BYFOUR
00116     /* generate crc for each value followed by one, two, and three zeros, and
00117        then the byte reversal of those as well as the first table */
00118     for (n = 0; n < 256; n++) {
00119         c = crc_table[0][n];
00120         crc_table[4][n] = REV(c);
00121         for (k = 1; k < 4; k++) {
00122             c = crc_table[0][c & 0xff] ^ (c >> 8);
00123             crc_table[k][n] = c;
00124             crc_table[k + 4][n] = REV(c);
00125         }
00126     }
00127 #endif /* BYFOUR */
00128 
00129   crc_table_empty = 0;
00130 
00131 #ifdef MAKECRCH
00132     /* write out CRC tables to crc32.h */
00133     {
00134         FILE *out;
00135 
00136         out = fopen("crc32.h", "w");
00137         if (out == NULL) return;
00138         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
00139         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
00140         fprintf(out, "local const unsigned long FAR ");
00141         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
00142         write_table(out, crc_table[0]);
00143 #  ifdef BYFOUR
00144         fprintf(out, "#ifdef BYFOUR\n");
00145         for (k = 1; k < 8; k++) {
00146             fprintf(out, "  },\n  {\n");
00147             write_table(out, crc_table[k]);
00148         }
00149         fprintf(out, "#endif\n");
00150 #  endif /* BYFOUR */
00151         fprintf(out, "  }\n};\n");
00152         fclose(out);
00153     }
00154 #endif /* MAKECRCH */
00155 }
00156 
00157 #ifdef MAKECRCH
00158 local void write_table(out, table)
00159     FILE *out;
00160     const unsigned long FAR *table;
00161 {
00162     int n;
00163 
00164     for (n = 0; n < 256; n++)
00165         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
00166                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
00167 }
00168 #endif /* MAKECRCH */
00169 
00170 #else /* !DYNAMIC_CRC_TABLE */
00171 /* ========================================================================
00172  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
00173  */
00174 #include "crc32.h"
00175 #endif /* DYNAMIC_CRC_TABLE */
00176 
00177 /* =========================================================================
00178  * This function can be used by asm versions of crc32()
00179  */
00180 const unsigned long FAR * ZEXPORT get_crc_table()
00181 {
00182 #ifdef DYNAMIC_CRC_TABLE
00183   if (crc_table_empty) make_crc_table();
00184 #endif /* DYNAMIC_CRC_TABLE */
00185   return (const unsigned long FAR *)crc_table;
00186 }
00187 
00188 /* ========================================================================= */
00189 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
00190 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
00191 
00192 /* ========================================================================= */
00193 unsigned long ZEXPORT crc32(crc, buf, len)
00194     unsigned long crc;
00195     const unsigned char FAR *buf;
00196     unsigned len;
00197 {
00198     if (buf == Z_NULL) return 0UL;
00199 
00200 #ifdef DYNAMIC_CRC_TABLE
00201     if (crc_table_empty)
00202         make_crc_table();
00203 #endif /* DYNAMIC_CRC_TABLE */
00204 
00205 #ifdef BYFOUR
00206     if (sizeof(void *) == sizeof(ptrdiff_t)) {
00207         u4 endian;
00208 
00209         endian = 1;
00210         if (*((unsigned char *)(&endian)))
00211             return crc32_little(crc, buf, len);
00212         else
00213             return crc32_big(crc, buf, len);
00214     }
00215 #endif /* BYFOUR */
00216     crc = crc ^ 0xffffffffUL;
00217     while (len >= 8) {
00218         DO8;
00219         len -= 8;
00220     }
00221     if (len) do {
00222         DO1;
00223     } while (--len);
00224     return crc ^ 0xffffffffUL;
00225 }
00226 
00227 #ifdef BYFOUR
00228 
00229 /* ========================================================================= */
00230 #define DOLIT4 c ^= *buf4++; \
00231         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
00232             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
00233 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
00234 
00235 /* ========================================================================= */
00236 local unsigned long crc32_little(crc, buf, len)
00237     unsigned long crc;
00238     const unsigned char FAR *buf;
00239     unsigned len;
00240 {
00241     register u4 c;
00242     register const u4 FAR *buf4;
00243 
00244     c = (u4)crc;
00245     c = ~c;
00246     while (len && ((ptrdiff_t)buf & 3)) {
00247         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00248         len--;
00249     }
00250 
00251     buf4 = (const u4 FAR *)buf;
00252     while (len >= 32) {
00253         DOLIT32;
00254         len -= 32;
00255     }
00256     while (len >= 4) {
00257         DOLIT4;
00258         len -= 4;
00259     }
00260     buf = (const unsigned char FAR *)buf4;
00261 
00262     if (len) do {
00263         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00264     } while (--len);
00265     c = ~c;
00266     return (unsigned long)c;
00267 }
00268 
00269 /* ========================================================================= */
00270 #define DOBIG4 c ^= *++buf4; \
00271         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
00272             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
00273 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
00274 
00275 /* ========================================================================= */
00276 local unsigned long crc32_big(crc, buf, len)
00277     unsigned long crc;
00278     const unsigned char FAR *buf;
00279     unsigned len;
00280 {
00281     register u4 c;
00282     register const u4 FAR *buf4;
00283 
00284     c = REV((u4)crc);
00285     c = ~c;
00286     while (len && ((ptrdiff_t)buf & 3)) {
00287         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00288         len--;
00289     }
00290 
00291     buf4 = (const u4 FAR *)buf;
00292     buf4--;
00293     while (len >= 32) {
00294         DOBIG32;
00295         len -= 32;
00296     }
00297     while (len >= 4) {
00298         DOBIG4;
00299         len -= 4;
00300     }
00301     buf4++;
00302     buf = (const unsigned char FAR *)buf4;
00303 
00304     if (len) do {
00305         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00306     } while (--len);
00307     c = ~c;
00308     return (unsigned long)(REV(c));
00309 }
00310 
00311 #endif /* BYFOUR */