Back to index

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