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