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  * Note: zlib license from from zlib.h added explicitly as mdadm does
   6  *       not include zlib.h. License from v1.2.2 of zlib:
   7  *
   8  *  This software is provided 'as-is', without any express or implied
   9  *  warranty.  In no event will the authors be held liable for any damages
  10  *  arising from the use of this software.
  11  *
  12  *  Permission is granted to anyone to use this software for any purpose,
  13  *  including commercial applications, and to alter it and redistribute it
  14  *  freely, subject to the following restrictions:
  15  *
  16  *  1. The origin of this software must not be misrepresented; you must not
  17  *     claim that you wrote the original software. If you use this software
  18  *     in a product, an acknowledgment in the product documentation would be
  19  *     appreciated but is not required.
  20  *  2. Altered source versions must be plainly marked as such, and must not be
  21  *     misrepresented as being the original software.
  22  *  3. This notice may not be removed or altered from any source distribution.
  23  *
  24  *
  25  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
  26  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
  27  * tables for updating the shift register in one step with three exclusive-ors
  28  * instead of four steps with four exclusive-ors.  This results about a factor
  29  * of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
  30  */
  31
  32 /* @(#) $Id$ */
  33
  34 /*
  35   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
  36   protection on the static variables used to control the first-use generation
  37   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
  38   first call get_crc_table() to initialize the tables before allowing more than
  39   one thread to use crc32().
  40  */
  41
  42 #ifdef MAKECRCH
  43 #  include <stdio.h>
  44 #  ifndef DYNAMIC_CRC_TABLE
  45 #    define DYNAMIC_CRC_TABLE
  46 #  endif /* !DYNAMIC_CRC_TABLE */
  47 #endif /* MAKECRCH */
  48
  49 /* #include "zutil.h"      / * for STDC and FAR definitions */
  50 #define STDC
  51 #define FAR
  52 #define Z_NULL ((void*)0)
  53 #define OF(X) X
  54 #define ZEXPORT
  55 typedef long ptrdiff_t;
  56 #define NOBYFOUR
  57
  58 #define local static
  59
  60 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
  61 #ifndef NOBYFOUR
  62 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
  63 #    include <limits.h>
  64 #    define BYFOUR
  65 #    if (UINT_MAX == 0xffffffffUL)
  66        typedef unsigned int u4;
  67 #    else
  68 #      if (ULONG_MAX == 0xffffffffUL)
  69          typedef unsigned long u4;
  70 #      else
  71 #        if (USHRT_MAX == 0xffffffffUL)
  72            typedef unsigned short u4;
  73 #        else
  74 #          undef BYFOUR     /* can't find a four-byte integer type! */
  75 #        endif
  76 #      endif
  77 #    endif
  78 #  endif /* STDC */
  79 #endif /* !NOBYFOUR */
  80
  81 /* Definitions for doing the crc four data bytes at a time. */
  82 #ifdef BYFOUR
  83 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
  84                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
  85    local unsigned long crc32_little OF((unsigned long,
  86                         const unsigned char FAR *, unsigned));
  87    local unsigned long crc32_big OF((unsigned long,
  88                         const unsigned char FAR *, unsigned));
  89 #  define TBLS 8
  90 #else
  91 #  define TBLS 1
  92 #endif /* BYFOUR */
  93
  94 #ifdef DYNAMIC_CRC_TABLE
  95
  96 local volatile int crc_table_empty = 1;
  97 local unsigned long FAR crc_table[TBLS][256];
  98 local void make_crc_table OF((void));
  99 #ifdef MAKECRCH
 100    local void write_table OF((FILE *, const unsigned long FAR *));
 101 #endif /* MAKECRCH */
 102
 103 /*
 104   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
 105   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.
 106
 107   Polynomials over GF(2) are represented in binary, one bit per coefficient,
 108   with the lowest powers in the most significant bit.  Then adding polynomials
 109   is just exclusive-or, and multiplying a polynomial by x is a right shift by
 110   one.  If we call the above polynomial p, and represent a byte as the
 111   polynomial q, also with the lowest power in the most significant bit (so the
 112   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
 113   where a mod b means the remainder after dividing a by b.
 114
 115   This calculation is done using the shift-register method of multiplying and
 116   taking the remainder.  The register is initialized to zero, and for each
 117   incoming bit, x^32 is added mod p to the register if the bit is a one (where
 118   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
 119   x (which is shifting right by one and adding x^32 mod p if the bit shifted
 120   out is a one).  We start with the highest power (least significant bit) of
 121   q and repeat for all eight bits of q.
 122
 123   The first table is simply the CRC of all possible eight bit values.  This is
 124   all the information needed to generate CRCs on data a byte at a time for all
 125   combinations of CRC register values and incoming bytes.  The remaining tables
 126   allow for word-at-a-time CRC calculation for both big-endian and little-
 127   endian machines, where a word is four bytes.
 128 */
 129 local void make_crc_table()
 130 {
 131     unsigned long c;
 132     int n, k;
 133     unsigned long poly;                 /* polynomial exclusive-or pattern */
 134     /* terms of polynomial defining this crc (except x^32): */
 135     static volatile int first = 1;      /* flag to limit concurrent making */
 136     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
 137
 138     /* See if another task is already doing this (not thread-safe, but better
 139        than nothing -- significantly reduces duration of vulnerability in
 140        case the advice about DYNAMIC_CRC_TABLE is ignored) */
 141     if (first) {
 142         first = 0;
 143
 144         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
 145         poly = 0UL;
 146         for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
 147             poly |= 1UL << (31 - p[n]);
 148
 149         /* generate a crc for every 8-bit value */
 150         for (n = 0; n < 256; n++) {
 151             c = (unsigned long)n;
 152             for (k = 0; k < 8; k++)
 153                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
 154             crc_table[0][n] = c;
 155         }
 156
 157 #ifdef BYFOUR
 158         /* generate crc for each value followed by one, two, and three zeros,
 159            and then the byte reversal of those as well as the first table */
 160         for (n = 0; n < 256; n++) {
 161             c = crc_table[0][n];
 162             crc_table[4][n] = REV(c);
 163             for (k = 1; k < 4; k++) {
 164                 c = crc_table[0][c & 0xff] ^ (c >> 8);
 165                 crc_table[k][n] = c;
 166                 crc_table[k + 4][n] = REV(c);
 167             }
 168         }
 169 #endif /* BYFOUR */
 170
 171         crc_table_empty = 0;
 172     }
 173     else {      /* not first */
 174         /* wait for the other guy to finish (not efficient, but rare) */
 175         while (crc_table_empty)
 176             ;
 177     }
 178
 179 #ifdef MAKECRCH
 180     /* write out CRC tables to crc32.h */
 181     {
 182         FILE *out;
 183
 184         out = fopen("crc32.h", "w");
 185         if (out == NULL) return;
 186         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
 187         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
 188         fprintf(out, "local const unsigned long FAR ");
 189         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
 190         write_table(out, crc_table[0]);
 191 #  ifdef BYFOUR
 192         fprintf(out, "#ifdef BYFOUR\n");
 193         for (k = 1; k < 8; k++) {
 194             fprintf(out, "  },\n  {\n");
 195             write_table(out, crc_table[k]);
 196         }
 197         fprintf(out, "#endif\n");
 198 #  endif /* BYFOUR */
 199         fprintf(out, "  }\n};\n");
 200         fclose(out);
 201     }
 202 #endif /* MAKECRCH */
 203 }
 204
 205 #ifdef MAKECRCH
 206 local void write_table(out, table)
 207     FILE *out;
 208     const unsigned long FAR *table;
 209 {
 210     int n;
 211
 212     for (n = 0; n < 256; n++)
 213         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
 214                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
 215 }
 216 #endif /* MAKECRCH */
 217
 218 #else /* !DYNAMIC_CRC_TABLE */
 219 /* ========================================================================
 220  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
 221  */
 222 #include "crc32.h"
 223 #endif /* DYNAMIC_CRC_TABLE */
 224
 225 /* =========================================================================
 226  * This function can be used by asm versions of crc32()
 227  */
 228 const unsigned long FAR * ZEXPORT get_crc_table(void)
 229 {
 230 #ifdef DYNAMIC_CRC_TABLE
 231     if (crc_table_empty)
 232         make_crc_table();
 233 #endif /* DYNAMIC_CRC_TABLE */
 234     return (const unsigned long FAR *)crc_table;
 235 }
 236
 237 /* ========================================================================= */
 238 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
 239 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
 240
 241 /* ========================================================================= */
 242 unsigned long ZEXPORT crc32(
 243         unsigned long crc,
 244         const unsigned char FAR *buf,
 245         unsigned len)
 246 {
 247     if (buf == Z_NULL) return 0UL;
 248
 249 #ifdef DYNAMIC_CRC_TABLE
 250     if (crc_table_empty)
 251         make_crc_table();
 252 #endif /* DYNAMIC_CRC_TABLE */
 253
 254 #ifdef BYFOUR
 255     if (sizeof(void *) == sizeof(ptrdiff_t)) {
 256         u4 endian;
 257
 258         endian = 1;
 259         if (*((unsigned char *)(&endian)))
 260             return crc32_little(crc, buf, len);
 261         else
 262             return crc32_big(crc, buf, len);
 263     }
 264 #endif /* BYFOUR */
 265 /*    crc = crc ^ 0xffffffffUL;*/
 266     while (len >= 8) {
 267         DO8;
 268         len -= 8;
 269     }
 270     if (len) do {
 271         DO1;
 272     } while (--len);
 273     return crc /* ^ 0xffffffffUL*/;
 274 }
 275
 276 #ifdef BYFOUR
 277
 278 /* ========================================================================= */
 279 #define DOLIT4 c ^= *buf4++; \
 280         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 281             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 282 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 283
 284 /* ========================================================================= */
 285 local unsigned long crc32_little(crc, buf, len)
 286     unsigned long crc;
 287     const unsigned char FAR *buf;
 288     unsigned len;
 289 {
 290     register u4 c;
 291     register const u4 FAR *buf4;
 292
 293     c = (u4)crc;
 294     c = ~c;
 295     while (len && ((ptrdiff_t)buf & 3)) {
 296         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 297         len--;
 298     }
 299
 300     buf4 = (const u4 FAR *)buf;
 301     while (len >= 32) {
 302         DOLIT32;
 303         len -= 32;
 304     }
 305     while (len >= 4) {
 306         DOLIT4;
 307         len -= 4;
 308     }
 309     buf = (const unsigned char FAR *)buf4;
 310
 311     if (len) do {
 312         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 313     } while (--len);
 314     c = ~c;
 315     return (unsigned long)c;
 316 }
 317
 318 /* ========================================================================= */
 319 #define DOBIG4 c ^= *++buf4; \
 320         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 321             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 322 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 323
 324 /* ========================================================================= */
 325 local unsigned long crc32_big(crc, buf, len)
 326     unsigned long crc;
 327     const unsigned char FAR *buf;
 328     unsigned len;
 329 {
 330     register u4 c;
 331     register const u4 FAR *buf4;
 332
 333     c = REV((u4)crc);
 334     c = ~c;
 335     while (len && ((ptrdiff_t)buf & 3)) {
 336         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 337         len--;
 338     }
 339
 340     buf4 = (const u4 FAR *)buf;
 341     buf4--;
 342     while (len >= 32) {
 343         DOBIG32;
 344         len -= 32;
 345     }
 346     while (len >= 4) {
 347         DOBIG4;
 348         len -= 4;
 349     }
 350     buf4++;
 351     buf = (const unsigned char FAR *)buf4;
 352
 353     if (len) do {
 354         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 355     } while (--len);
 356     c = ~c;
 357     return (unsigned long)(REV(c));
 358 }
 359
 360 #endif /* BYFOUR */