crc32.c

00001 /* crc32.c -- compute the CRC-32 of a data stream
00002  * Copyright (C) 1995-2006, 2010, 2011, 2012 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 in about a
00009  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
00010  */
00011 
00012 /* @(#) $Id$ */
00013 
00014 /*
00015   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
00016   protection on the static variables used to control the first-use generation
00017   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
00018   first call get_crc_table() to initialize the tables before allowing more than
00019   one thread to use crc32().
00020 
00021   DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.
00022  */
00023 
00024 #ifdef MAKECRCH
00025 #  include <stdio.h>
00026 #  ifndef DYNAMIC_CRC_TABLE
00027 #    define DYNAMIC_CRC_TABLE
00028 #  endif /* !DYNAMIC_CRC_TABLE */
00029 #endif /* MAKECRCH */
00030 
00031 #include "zutil.h"      /* for STDC and FAR definitions */
00032 
00033 #define local static
00034 
00035 /* Definitions for doing the crc four data bytes at a time. */
00036 #if !defined(NOBYFOUR) && defined(Z_U4)
00037 #  define BYFOUR
00038 #endif
00039 #ifdef BYFOUR
00040    local unsigned long crc32_little OF((unsigned long,
00041                         const unsigned char FAR *, unsigned));
00042    local unsigned long crc32_big OF((unsigned long,
00043                         const unsigned char FAR *, unsigned));
00044 #  define TBLS 8
00045 #else
00046 #  define TBLS 1
00047 #endif /* BYFOUR */
00048 
00049 /* Local functions for crc concatenation */
00050 local unsigned long gf2_matrix_times OF((unsigned long *mat,
00051                                          unsigned long vec));
00052 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
00053 local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
00054 
00055 
00056 #ifdef DYNAMIC_CRC_TABLE
00057 
00058 local volatile int crc_table_empty = 1;
00059 local z_crc_t FAR crc_table[TBLS][256];
00060 local void make_crc_table OF((void));
00061 #ifdef MAKECRCH
00062    local void write_table OF((FILE *, const z_crc_t FAR *));
00063 #endif /* MAKECRCH */
00064 /*
00065   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
00066   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.
00067 
00068   Polynomials over GF(2) are represented in binary, one bit per coefficient,
00069   with the lowest powers in the most significant bit.  Then adding polynomials
00070   is just exclusive-or, and multiplying a polynomial by x is a right shift by
00071   one.  If we call the above polynomial p, and represent a byte as the
00072   polynomial q, also with the lowest power in the most significant bit (so the
00073   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
00074   where a mod b means the remainder after dividing a by b.
00075 
00076   This calculation is done using the shift-register method of multiplying and
00077   taking the remainder.  The register is initialized to zero, and for each
00078   incoming bit, x^32 is added mod p to the register if the bit is a one (where
00079   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
00080   x (which is shifting right by one and adding x^32 mod p if the bit shifted
00081   out is a one).  We start with the highest power (least significant bit) of
00082   q and repeat for all eight bits of q.
00083 
00084   The first table is simply the CRC of all possible eight bit values.  This is
00085   all the information needed to generate CRCs on data a byte at a time for all
00086   combinations of CRC register values and incoming bytes.  The remaining tables
00087   allow for word-at-a-time CRC calculation for both big-endian and little-
00088   endian machines, where a word is four bytes.
00089 */
00090 local void make_crc_table()
00091 {
00092     z_crc_t c;
00093     int n, k;
00094     z_crc_t poly;                       /* polynomial exclusive-or pattern */
00095     /* terms of polynomial defining this crc (except x^32): */
00096     static volatile int first = 1;      /* flag to limit concurrent making */
00097     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
00098 
00099     /* See if another task is already doing this (not thread-safe, but better
00100        than nothing -- significantly reduces duration of vulnerability in
00101        case the advice about DYNAMIC_CRC_TABLE is ignored) */
00102     if (first) {
00103         first = 0;
00104 
00105         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
00106         poly = 0;
00107         for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
00108             poly |= (z_crc_t)1 << (31 - p[n]);
00109 
00110         /* generate a crc for every 8-bit value */
00111         for (n = 0; n < 256; n++) {
00112             c = (z_crc_t)n;
00113             for (k = 0; k < 8; k++)
00114                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
00115             crc_table[0][n] = c;
00116         }
00117 
00118 #ifdef BYFOUR
00119         /* generate crc for each value followed by one, two, and three zeros,
00120            and then the byte reversal of those as well as the first table */
00121         for (n = 0; n < 256; n++) {
00122             c = crc_table[0][n];
00123             crc_table[4][n] = ZSWAP32(c);
00124             for (k = 1; k < 4; k++) {
00125                 c = crc_table[0][c & 0xff] ^ (c >> 8);
00126                 crc_table[k][n] = c;
00127                 crc_table[k + 4][n] = ZSWAP32(c);
00128             }
00129         }
00130 #endif /* BYFOUR */
00131 
00132         crc_table_empty = 0;
00133     }
00134     else {      /* not first */
00135         /* wait for the other guy to finish (not efficient, but rare) */
00136         while (crc_table_empty)
00137             ;
00138     }
00139 
00140 #ifdef MAKECRCH
00141     /* write out CRC tables to crc32.h */
00142     {
00143         FILE *out;
00144 
00145         out = fopen("crc32.h", "w");
00146         if (out == NULL) return;
00147         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
00148         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
00149         fprintf(out, "local const z_crc_t FAR ");
00150         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
00151         write_table(out, crc_table[0]);
00152 #  ifdef BYFOUR
00153         fprintf(out, "#ifdef BYFOUR\n");
00154         for (k = 1; k < 8; k++) {
00155             fprintf(out, "  },\n  {\n");
00156             write_table(out, crc_table[k]);
00157         }
00158         fprintf(out, "#endif\n");
00159 #  endif /* BYFOUR */
00160         fprintf(out, "  }\n};\n");
00161         fclose(out);
00162     }
00163 #endif /* MAKECRCH */
00164 }
00165 
00166 #ifdef MAKECRCH
00167 local void write_table(out, table)
00168     FILE *out;
00169     const z_crc_t FAR *table;
00170 {
00171     int n;
00172 
00173     for (n = 0; n < 256; n++)
00174         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ",
00175                 (unsigned long)(table[n]),
00176                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
00177 }
00178 #endif /* MAKECRCH */
00179 
00180 #else /* !DYNAMIC_CRC_TABLE */
00181 /* ========================================================================
00182  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
00183  */
00184 #include "crc32.h"
00185 #endif /* DYNAMIC_CRC_TABLE */
00186 
00187 /* =========================================================================
00188  * This function can be used by asm versions of crc32()
00189  */
00190 const z_crc_t FAR * ZEXPORT get_crc_table()
00191 {
00192 #ifdef DYNAMIC_CRC_TABLE
00193     if (crc_table_empty)
00194         make_crc_table();
00195 #endif /* DYNAMIC_CRC_TABLE */
00196     return (const z_crc_t FAR *)crc_table;
00197 }
00198 
00199 /* ========================================================================= */
00200 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
00201 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
00202 
00203 /* ========================================================================= */
00204 unsigned long ZEXPORT crc32(crc, buf, len)
00205     unsigned long crc;
00206     const unsigned char FAR *buf;
00207     uInt len;
00208 {
00209     if (buf == Z_NULL) return 0UL;
00210 
00211 #ifdef DYNAMIC_CRC_TABLE
00212     if (crc_table_empty)
00213         make_crc_table();
00214 #endif /* DYNAMIC_CRC_TABLE */
00215 
00216 #ifdef BYFOUR
00217     if (sizeof(void *) == sizeof(ptrdiff_t)) {
00218         z_crc_t endian;
00219 
00220         endian = 1;
00221         if (*((unsigned char *)(&endian)))
00222             return crc32_little(crc, buf, len);
00223         else
00224             return crc32_big(crc, buf, len);
00225     }
00226 #endif /* BYFOUR */
00227     crc = crc ^ 0xffffffffUL;
00228     while (len >= 8) {
00229         DO8;
00230         len -= 8;
00231     }
00232     if (len) do {
00233         DO1;
00234     } while (--len);
00235     return crc ^ 0xffffffffUL;
00236 }
00237 
00238 #ifdef BYFOUR
00239 
00240 /* ========================================================================= */
00241 #define DOLIT4 c ^= *buf4++; \
00242         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
00243             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
00244 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
00245 
00246 /* ========================================================================= */
00247 local unsigned long crc32_little(crc, buf, len)
00248     unsigned long crc;
00249     const unsigned char FAR *buf;
00250     unsigned len;
00251 {
00252     register z_crc_t c;
00253     register const z_crc_t FAR *buf4;
00254 
00255     c = (z_crc_t)crc;
00256     c = ~c;
00257     while (len && ((ptrdiff_t)buf & 3)) {
00258         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00259         len--;
00260     }
00261 
00262     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
00263     while (len >= 32) {
00264         DOLIT32;
00265         len -= 32;
00266     }
00267     while (len >= 4) {
00268         DOLIT4;
00269         len -= 4;
00270     }
00271     buf = (const unsigned char FAR *)buf4;
00272 
00273     if (len) do {
00274         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
00275     } while (--len);
00276     c = ~c;
00277     return (unsigned long)c;
00278 }
00279 
00280 /* ========================================================================= */
00281 #define DOBIG4 c ^= *++buf4; \
00282         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
00283             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
00284 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
00285 
00286 /* ========================================================================= */
00287 local unsigned long crc32_big(crc, buf, len)
00288     unsigned long crc;
00289     const unsigned char FAR *buf;
00290     unsigned len;
00291 {
00292     register z_crc_t c;
00293     register const z_crc_t FAR *buf4;
00294 
00295     c = ZSWAP32((z_crc_t)crc);
00296     c = ~c;
00297     while (len && ((ptrdiff_t)buf & 3)) {
00298         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00299         len--;
00300     }
00301 
00302     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
00303     buf4--;
00304     while (len >= 32) {
00305         DOBIG32;
00306         len -= 32;
00307     }
00308     while (len >= 4) {
00309         DOBIG4;
00310         len -= 4;
00311     }
00312     buf4++;
00313     buf = (const unsigned char FAR *)buf4;
00314 
00315     if (len) do {
00316         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
00317     } while (--len);
00318     c = ~c;
00319     return (unsigned long)(ZSWAP32(c));
00320 }
00321 
00322 #endif /* BYFOUR */
00323 
00324 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
00325 
00326 /* ========================================================================= */
00327 local unsigned long gf2_matrix_times(mat, vec)
00328     unsigned long *mat;
00329     unsigned long vec;
00330 {
00331     unsigned long sum;
00332 
00333     sum = 0;
00334     while (vec) {
00335         if (vec & 1)
00336             sum ^= *mat;
00337         vec >>= 1;
00338         mat++;
00339     }
00340     return sum;
00341 }
00342 
00343 /* ========================================================================= */
00344 local void gf2_matrix_square(square, mat)
00345     unsigned long *square;
00346     unsigned long *mat;
00347 {
00348     int n;
00349 
00350     for (n = 0; n < GF2_DIM; n++)
00351         square[n] = gf2_matrix_times(mat, mat[n]);
00352 }
00353 
00354 /* ========================================================================= */
00355 local uLong crc32_combine_(crc1, crc2, len2)
00356     uLong crc1;
00357     uLong crc2;
00358     z_off64_t len2;
00359 {
00360     int n;
00361     unsigned long row;
00362     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
00363     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
00364 
00365     /* degenerate case (also disallow negative lengths) */
00366     if (len2 <= 0)
00367         return crc1;
00368 
00369     /* put operator for one zero bit in odd */
00370     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
00371     row = 1;
00372     for (n = 1; n < GF2_DIM; n++) {
00373         odd[n] = row;
00374         row <<= 1;
00375     }
00376 
00377     /* put operator for two zero bits in even */
00378     gf2_matrix_square(even, odd);
00379 
00380     /* put operator for four zero bits in odd */
00381     gf2_matrix_square(odd, even);
00382 
00383     /* apply len2 zeros to crc1 (first square will put the operator for one
00384        zero byte, eight zero bits, in even) */
00385     do {
00386         /* apply zeros operator for this bit of len2 */
00387         gf2_matrix_square(even, odd);
00388         if (len2 & 1)
00389             crc1 = gf2_matrix_times(even, crc1);
00390         len2 >>= 1;
00391 
00392         /* if no more bits set, then done */
00393         if (len2 == 0)
00394             break;
00395 
00396         /* another iteration of the loop with odd and even swapped */
00397         gf2_matrix_square(odd, even);
00398         if (len2 & 1)
00399             crc1 = gf2_matrix_times(odd, crc1);
00400         len2 >>= 1;
00401 
00402         /* if no more bits set, then done */
00403     } while (len2 != 0);
00404 
00405     /* return combined crc */
00406     crc1 ^= crc2;
00407     return crc1;
00408 }
00409 
00410 /* ========================================================================= */
00411 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
00412     uLong crc1;
00413     uLong crc2;
00414     z_off_t len2;
00415 {
00416     return crc32_combine_(crc1, crc2, len2);
00417 }
00418 
00419 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
00420     uLong crc1;
00421     uLong crc2;
00422     z_off64_t len2;
00423 {
00424     return crc32_combine_(crc1, crc2, len2);
00425 }