crc32.c

   1 /* crc32.c -- compute the CRC-32 of a data stream
   2  * Copyright (C) 1995-2005 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 in about a
   9  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
  10  */
  11
  12 /* @(#) $Id: ./src/external/zlib-1.2.3/crc32.c, 2011/09/08 dcid Exp $
  13  */
  14
  15 /*
  16   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
  17   protection on the static variables used to control the first-use generation
  18   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
  19   first call get_crc_table() to initialize the tables before allowing more than
  20   one thread to use crc32().
  21  */
  22
  23 #ifdef MAKECRCH
  24 #  include <stdio.h>
  25 #  ifndef DYNAMIC_CRC_TABLE
  26 #    define DYNAMIC_CRC_TABLE
  27 #  endif /* !DYNAMIC_CRC_TABLE */
  28 #endif /* MAKECRCH */
  29
  30 #include "zutil.h"      /* for STDC and FAR definitions */
  31
  32 #define local static
  33
  34 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
  35 #ifndef NOBYFOUR
  36 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
  37 #    include <limits.h>
  38 #    define BYFOUR
  39 #    if (UINT_MAX == 0xffffffffUL)
  40        typedef unsigned int u4;
  41 #    else
  42 #      if (ULONG_MAX == 0xffffffffUL)
  43          typedef unsigned long u4;
  44 #      else
  45 #        if (USHRT_MAX == 0xffffffffUL)
  46            typedef unsigned short u4;
  47 #        else
  48 #          undef BYFOUR     /* can't find a four-byte integer type! */
  49 #        endif
  50 #      endif
  51 #    endif
  52 #  endif /* STDC */
  53 #endif /* !NOBYFOUR */
  54
  55 /* Definitions for doing the crc four data bytes at a time. */
  56 #ifdef BYFOUR
  57 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
  58                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
  59    local unsigned long crc32_little OF((unsigned long,
  60                         const unsigned char FAR *, unsigned));
  61    local unsigned long crc32_big OF((unsigned long,
  62                         const unsigned char FAR *, unsigned));
  63 #  define TBLS 8
  64 #else
  65 #  define TBLS 1
  66 #endif /* BYFOUR */
  67
  68 /* Local functions for crc concatenation */
  69 local unsigned long gf2_matrix_times OF((unsigned long *mat,
  70                                          unsigned long vec));
  71 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
  72
  73 #ifdef DYNAMIC_CRC_TABLE
  74
  75 local volatile int crc_table_empty = 1;
  76 local unsigned long FAR crc_table[TBLS][256];
  77 local void make_crc_table OF((void));
  78 #ifdef MAKECRCH
  79    local void write_table OF((FILE *, const unsigned long FAR *));
  80 #endif /* MAKECRCH */
  81 /*
  82   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
  83   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.
  84
  85   Polynomials over GF(2) are represented in binary, one bit per coefficient,
  86   with the lowest powers in the most significant bit.  Then adding polynomials
  87   is just exclusive-or, and multiplying a polynomial by x is a right shift by
  88   one.  If we call the above polynomial p, and represent a byte as the
  89   polynomial q, also with the lowest power in the most significant bit (so the
  90   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
  91   where a mod b means the remainder after dividing a by b.
  92
  93   This calculation is done using the shift-register method of multiplying and
  94   taking the remainder.  The register is initialized to zero, and for each
  95   incoming bit, x^32 is added mod p to the register if the bit is a one (where
  96   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
  97   x (which is shifting right by one and adding x^32 mod p if the bit shifted
  98   out is a one).  We start with the highest power (least significant bit) of
  99   q and repeat for all eight bits of q.
 100
 101   The first table is simply the CRC of all possible eight bit values.  This is
 102   all the information needed to generate CRCs on data a byte at a time for all
 103   combinations of CRC register values and incoming bytes.  The remaining tables
 104   allow for word-at-a-time CRC calculation for both big-endian and little-
 105   endian machines, where a word is four bytes.
 106 */
 107 local void make_crc_table()
 108 {
 109     unsigned long c;
 110     int n, k;
 111     unsigned long poly;                 /* polynomial exclusive-or pattern */
 112     /* terms of polynomial defining this crc (except x^32): */
 113     static volatile int first = 1;      /* flag to limit concurrent making */
 114     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
 115
 116     /* See if another task is already doing this (not thread-safe, but better
 117        than nothing -- significantly reduces duration of vulnerability in
 118        case the advice about DYNAMIC_CRC_TABLE is ignored) */
 119     if (first) {
 120         first = 0;
 121
 122         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
 123         poly = 0UL;
 124         for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
 125             poly |= 1UL << (31 - p[n]);
 126
 127         /* generate a crc for every 8-bit value */
 128         for (n = 0; n < 256; n++) {
 129             c = (unsigned long)n;
 130             for (k = 0; k < 8; k++)
 131                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
 132             crc_table[0][n] = c;
 133         }
 134
 135 #ifdef BYFOUR
 136         /* generate crc for each value followed by one, two, and three zeros,
 137            and then the byte reversal of those as well as the first table */
 138         for (n = 0; n < 256; n++) {
 139             c = crc_table[0][n];
 140             crc_table[4][n] = REV(c);
 141             for (k = 1; k < 4; k++) {
 142                 c = crc_table[0][c & 0xff] ^ (c >> 8);
 143                 crc_table[k][n] = c;
 144                 crc_table[k + 4][n] = REV(c);
 145             }
 146         }
 147 #endif /* BYFOUR */
 148
 149         crc_table_empty = 0;
 150     }
 151     else {      /* not first */
 152         /* wait for the other guy to finish (not efficient, but rare) */
 153         while (crc_table_empty)
 154             ;
 155     }
 156
 157 #ifdef MAKECRCH
 158     /* write out CRC tables to crc32.h */
 159     {
 160         FILE *out;
 161
 162         out = fopen("crc32.h", "w");
 163         if (out == NULL) return;
 164         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
 165         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
 166         fprintf(out, "local const unsigned long FAR ");
 167         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
 168         write_table(out, crc_table[0]);
 169 #  ifdef BYFOUR
 170         fprintf(out, "#ifdef BYFOUR\n");
 171         for (k = 1; k < 8; k++) {
 172             fprintf(out, "  },\n  {\n");
 173             write_table(out, crc_table[k]);
 174         }
 175         fprintf(out, "#endif\n");
 176 #  endif /* BYFOUR */
 177         fprintf(out, "  }\n};\n");
 178         fclose(out);
 179     }
 180 #endif /* MAKECRCH */
 181 }
 182
 183 #ifdef MAKECRCH
 184 local void write_table(out, table)
 185     FILE *out;
 186     const unsigned long FAR *table;
 187 {
 188     int n;
 189
 190     for (n = 0; n < 256; n++)
 191         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
 192                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
 193 }
 194 #endif /* MAKECRCH */
 195
 196 #else /* !DYNAMIC_CRC_TABLE */
 197 /* ========================================================================
 198  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
 199  */
 200 #include "crc32.h"
 201 #endif /* DYNAMIC_CRC_TABLE */
 202
 203 /* =========================================================================
 204  * This function can be used by asm versions of crc32()
 205  */
 206 const unsigned long FAR * ZEXPORT get_crc_table()
 207 {
 208 #ifdef DYNAMIC_CRC_TABLE
 209     if (crc_table_empty)
 210         make_crc_table();
 211 #endif /* DYNAMIC_CRC_TABLE */
 212     return (const unsigned long FAR *)crc_table;
 213 }
 214
 215 /* ========================================================================= */
 216 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
 217 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
 218
 219 /* ========================================================================= */
 220 unsigned long ZEXPORT crc32(crc, buf, len)
 221     unsigned long crc;
 222     const unsigned char FAR *buf;
 223     unsigned len;
 224 {
 225     if (buf == Z_NULL) return 0UL;
 226
 227 #ifdef DYNAMIC_CRC_TABLE
 228     if (crc_table_empty)
 229         make_crc_table();
 230 #endif /* DYNAMIC_CRC_TABLE */
 231
 232 #ifdef BYFOUR
 233     if (sizeof(void *) == sizeof(ptrdiff_t)) {
 234         u4 endian;
 235
 236         endian = 1;
 237         if (*((unsigned char *)(&endian)))
 238             return crc32_little(crc, buf, len);
 239         else
 240             return crc32_big(crc, buf, len);
 241     }
 242 #endif /* BYFOUR */
 243     crc = crc ^ 0xffffffffUL;
 244     while (len >= 8) {
 245         DO8;
 246         len -= 8;
 247     }
 248     if (len) do {
 249         DO1;
 250     } while (--len);
 251     return crc ^ 0xffffffffUL;
 252 }
 253
 254 #ifdef BYFOUR
 255
 256 /* ========================================================================= */
 257 #define DOLIT4 c ^= *buf4++; \
 258         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 259             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 260 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 261
 262 /* ========================================================================= */
 263 local unsigned long crc32_little(crc, buf, len)
 264     unsigned long crc;
 265     const unsigned char FAR *buf;
 266     unsigned len;
 267 {
 268     register u4 c;
 269     register const u4 FAR *buf4;
 270
 271     c = (u4)crc;
 272     c = ~c;
 273     while (len && ((ptrdiff_t)buf & 3)) {
 274         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 275         len--;
 276     }
 277
 278     buf4 = (const u4 FAR *)(const void FAR *)buf;
 279     while (len >= 32) {
 280         DOLIT32;
 281         len -= 32;
 282     }
 283     while (len >= 4) {
 284         DOLIT4;
 285         len -= 4;
 286     }
 287     buf = (const unsigned char FAR *)buf4;
 288
 289     if (len) do {
 290         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 291     } while (--len);
 292     c = ~c;
 293     return (unsigned long)c;
 294 }
 295
 296 /* ========================================================================= */
 297 #define DOBIG4 c ^= *++buf4; \
 298         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 299             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 300 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 301
 302 /* ========================================================================= */
 303 local unsigned long crc32_big(crc, buf, len)
 304     unsigned long crc;
 305     const unsigned char FAR *buf;
 306     unsigned len;
 307 {
 308     register u4 c;
 309     register const u4 FAR *buf4;
 310
 311     c = REV((u4)crc);
 312     c = ~c;
 313     while (len && ((ptrdiff_t)buf & 3)) {
 314         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 315         len--;
 316     }
 317
 318     buf4 = (const u4 FAR *)(const void FAR *)buf;
 319     buf4--;
 320     while (len >= 32) {
 321         DOBIG32;
 322         len -= 32;
 323     }
 324     while (len >= 4) {
 325         DOBIG4;
 326         len -= 4;
 327     }
 328     buf4++;
 329     buf = (const unsigned char FAR *)buf4;
 330
 331     if (len) do {
 332         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 333     } while (--len);
 334     c = ~c;
 335     return (unsigned long)(REV(c));
 336 }
 337
 338 #endif /* BYFOUR */
 339
 340 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 341
 342 /* ========================================================================= */
 343 local unsigned long gf2_matrix_times(mat, vec)
 344     unsigned long *mat;
 345     unsigned long vec;
 346 {
 347     unsigned long sum;
 348
 349     sum = 0;
 350     while (vec) {
 351         if (vec & 1)
 352             sum ^= *mat;
 353         vec >>= 1;
 354         mat++;
 355     }
 356     return sum;
 357 }
 358
 359 /* ========================================================================= */
 360 local void gf2_matrix_square(square, mat)
 361     unsigned long *square;
 362     unsigned long *mat;
 363 {
 364     int n;
 365
 366     for (n = 0; n < GF2_DIM; n++)
 367         square[n] = gf2_matrix_times(mat, mat[n]);
 368 }
 369
 370 /* ========================================================================= */
 371 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 372     uLong crc1;
 373     uLong crc2;
 374     z_off_t len2;
 375 {
 376     int n;
 377     unsigned long row;
 378     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
 379     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
 380
 381     /* degenerate case */
 382     if (len2 == 0)
 383         return crc1;
 384
 385     /* put operator for one zero bit in odd */
 386     odd[0] = 0xedb88320L;           /* CRC-32 polynomial */
 387     row = 1;
 388     for (n = 1; n < GF2_DIM; n++) {
 389         odd[n] = row;
 390         row <<= 1;
 391     }
 392
 393     /* put operator for two zero bits in even */
 394     gf2_matrix_square(even, odd);
 395
 396     /* put operator for four zero bits in odd */
 397     gf2_matrix_square(odd, even);
 398
 399     /* apply len2 zeros to crc1 (first square will put the operator for one
 400        zero byte, eight zero bits, in even) */
 401     do {
 402         /* apply zeros operator for this bit of len2 */
 403         gf2_matrix_square(even, odd);
 404         if (len2 & 1)
 405             crc1 = gf2_matrix_times(even, crc1);
 406         len2 >>= 1;
 407
 408         /* if no more bits set, then done */
 409         if (len2 == 0)
 410             break;
 411
 412         /* another iteration of the loop with odd and even swapped */
 413         gf2_matrix_square(odd, even);
 414         if (len2 & 1)
 415             crc1 = gf2_matrix_times(odd, crc1);
 416         len2 >>= 1;
 417
 418         /* if no more bits set, then done */
 419     } while (len2 != 0);
 420
 421     /* return combined crc */
 422     crc1 ^= crc2;
 423     return crc1;
 424 }