support/crc32.c

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