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