zlib/crc32.c

   1 /* crc32.c -- compute the CRC-32 of a data stream
   2  * Copyright (C) 1995-2006, 2010, 2011, 2012 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   DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.
  22  */
  23
  24 #ifdef MAKECRCH
  25 #  include <stdio.h>
  26 #  ifndef DYNAMIC_CRC_TABLE
  27 #    define DYNAMIC_CRC_TABLE
  28 #  endif /* !DYNAMIC_CRC_TABLE */
  29 #endif /* MAKECRCH */
  30
  31 #include "zutil.h"      /* for STDC and FAR definitions */
  32
  33 #define local static
  34
  35 /* Definitions for doing the crc four data bytes at a time. */
  36 #if !defined(NOBYFOUR) && defined(Z_U4)
  37 #  define BYFOUR
  38 #endif
  39 #ifdef BYFOUR
  40    local unsigned long crc32_little OF((unsigned long,
  41                         const unsigned char FAR *, unsigned));
  42    local unsigned long crc32_big OF((unsigned long,
  43                         const unsigned char FAR *, unsigned));
  44 #  define TBLS 8
  45 #else
  46 #  define TBLS 1
  47 #endif /* BYFOUR */
  48
  49 /* Local functions for crc concatenation */
  50 local unsigned long gf2_matrix_times OF((unsigned long *mat,
  51                                          unsigned long vec));
  52 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
  53 local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));
  54
  55
  56 #ifdef DYNAMIC_CRC_TABLE
  57
  58 local volatile int crc_table_empty = 1;
  59 local z_crc_t FAR crc_table[TBLS][256];
  60 local void make_crc_table OF((void));
  61 #ifdef MAKECRCH
  62    local void write_table OF((FILE *, const z_crc_t FAR *));
  63 #endif /* MAKECRCH */
  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     z_crc_t c;
  93     int n, k;
  94     z_crc_t poly;                       /* polynomial exclusive-or pattern */
  95     /* terms of polynomial defining this crc (except x^32): */
  96     static volatile int first = 1;      /* flag to limit concurrent making */
  97     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
  98
  99     /* See if another task is already doing this (not thread-safe, but better
 100        than nothing -- significantly reduces duration of vulnerability in
 101        case the advice about DYNAMIC_CRC_TABLE is ignored) */
 102     if (first) {
 103         first = 0;
 104
 105         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
 106         poly = 0;
 107         for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)
 108             poly |= (z_crc_t)1 << (31 - p[n]);
 109
 110         /* generate a crc for every 8-bit value */
 111         for (n = 0; n < 256; n++) {
 112             c = (z_crc_t)n;
 113             for (k = 0; k < 8; k++)
 114                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
 115             crc_table[0][n] = c;
 116         }
 117
 118 #ifdef BYFOUR
 119         /* generate crc for each value followed by one, two, and three zeros,
 120            and then the byte reversal of those as well as the first table */
 121         for (n = 0; n < 256; n++) {
 122             c = crc_table[0][n];
 123             crc_table[4][n] = ZSWAP32(c);
 124             for (k = 1; k < 4; k++) {
 125                 c = crc_table[0][c & 0xff] ^ (c >> 8);
 126                 crc_table[k][n] = c;
 127                 crc_table[k + 4][n] = ZSWAP32(c);
 128             }
 129         }
 130 #endif /* BYFOUR */
 131
 132         crc_table_empty = 0;
 133     }
 134     else {      /* not first */
 135         /* wait for the other guy to finish (not efficient, but rare) */
 136         while (crc_table_empty)
 137             ;
 138     }
 139
 140 #ifdef MAKECRCH
 141     /* write out CRC tables to crc32.h */
 142     {
 143         FILE *out;
 144
 145         out = fopen("crc32.h", "w");
 146         if (out == NULL) return;
 147         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
 148         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
 149         fprintf(out, "local const z_crc_t FAR ");
 150         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
 151         write_table(out, crc_table[0]);
 152 #  ifdef BYFOUR
 153         fprintf(out, "#ifdef BYFOUR\n");
 154         for (k = 1; k < 8; k++) {
 155             fprintf(out, "  },\n  {\n");
 156             write_table(out, crc_table[k]);
 157         }
 158         fprintf(out, "#endif\n");
 159 #  endif /* BYFOUR */
 160         fprintf(out, "  }\n};\n");
 161         fclose(out);
 162     }
 163 #endif /* MAKECRCH */
 164 }
 165
 166 #ifdef MAKECRCH
 167 local void write_table(out, table)
 168     FILE *out;
 169     const z_crc_t FAR *table;
 170 {
 171     int n;
 172
 173     for (n = 0; n < 256; n++)
 174         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ",
 175                 (unsigned long)(table[n]),
 176                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
 177 }
 178 #endif /* MAKECRCH */
 179
 180 #else /* !DYNAMIC_CRC_TABLE */
 181 /* ========================================================================
 182  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
 183  */
 184 #include "crc32.h"
 185 #endif /* DYNAMIC_CRC_TABLE */
 186
 187 /* =========================================================================
 188  * This function can be used by asm versions of crc32()
 189  */
 190 const z_crc_t FAR * ZEXPORT get_crc_table()
 191 {
 192 #ifdef DYNAMIC_CRC_TABLE
 193     if (crc_table_empty)
 194         make_crc_table();
 195 #endif /* DYNAMIC_CRC_TABLE */
 196     return (const z_crc_t FAR *)crc_table;
 197 }
 198
 199 /* ========================================================================= */
 200 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
 201 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
 202
 203 /* ========================================================================= */
 204 unsigned long ZEXPORT crc32(crc, buf, len)
 205     unsigned long crc;
 206     const unsigned char FAR *buf;
 207     uInt len;
 208 {
 209     if (buf == Z_NULL) return 0UL;
 210
 211 #ifdef DYNAMIC_CRC_TABLE
 212     if (crc_table_empty)
 213         make_crc_table();
 214 #endif /* DYNAMIC_CRC_TABLE */
 215
 216 #ifdef BYFOUR
 217     if (sizeof(void *) == sizeof(ptrdiff_t)) {
 218         z_crc_t endian;
 219
 220         endian = 1;
 221         if (*((unsigned char *)(&endian)))
 222             return crc32_little(crc, buf, len);
 223         else
 224             return crc32_big(crc, buf, len);
 225     }
 226 #endif /* BYFOUR */
 227     crc = crc ^ 0xffffffffUL;
 228     while (len >= 8) {
 229         DO8;
 230         len -= 8;
 231     }
 232     if (len) do {
 233         DO1;
 234     } while (--len);
 235     return crc ^ 0xffffffffUL;
 236 }
 237
 238 #ifdef BYFOUR
 239
 240 /* ========================================================================= */
 241 #define DOLIT4 c ^= *buf4++; \
 242         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 243             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 244 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 245
 246 /* ========================================================================= */
 247 local unsigned long crc32_little(crc, buf, len)
 248     unsigned long crc;
 249     const unsigned char FAR *buf;
 250     unsigned len;
 251 {
 252     register z_crc_t c;
 253     register const z_crc_t FAR *buf4;
 254
 255     c = (z_crc_t)crc;
 256     c = ~c;
 257     while (len && ((ptrdiff_t)buf & 3)) {
 258         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 259         len--;
 260     }
 261
 262     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
 263     while (len >= 32) {
 264         DOLIT32;
 265         len -= 32;
 266     }
 267     while (len >= 4) {
 268         DOLIT4;
 269         len -= 4;
 270     }
 271     buf = (const unsigned char FAR *)buf4;
 272
 273     if (len) do {
 274         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 275     } while (--len);
 276     c = ~c;
 277     return (unsigned long)c;
 278 }
 279
 280 /* ========================================================================= */
 281 #define DOBIG4 c ^= *buf4++; \
 282         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 283             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 284 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 285
 286 /* ========================================================================= */
 287 local unsigned long crc32_big(crc, buf, len)
 288     unsigned long crc;
 289     const unsigned char FAR *buf;
 290     unsigned len;
 291 {
 292     register z_crc_t c;
 293     register const z_crc_t FAR *buf4;
 294
 295     c = ZSWAP32((z_crc_t)crc);
 296     c = ~c;
 297     while (len && ((ptrdiff_t)buf & 3)) {
 298         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 299         len--;
 300     }
 301
 302     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
 303     while (len >= 32) {
 304         DOBIG32;
 305         len -= 32;
 306     }
 307     while (len >= 4) {
 308         DOBIG4;
 309         len -= 4;
 310     }
 311     buf = (const unsigned char FAR *)buf4;
 312
 313     if (len) do {
 314         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 315     } while (--len);
 316     c = ~c;
 317     return (unsigned long)(ZSWAP32(c));
 318 }
 319
 320 #endif /* BYFOUR */
 321
 322 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 323
 324 /* ========================================================================= */
 325 local unsigned long gf2_matrix_times(mat, vec)
 326     unsigned long *mat;
 327     unsigned long vec;
 328 {
 329     unsigned long sum;
 330
 331     sum = 0;
 332     while (vec) {
 333         if (vec & 1)
 334             sum ^= *mat;
 335         vec >>= 1;
 336         mat++;
 337     }
 338     return sum;
 339 }
 340
 341 /* ========================================================================= */
 342 local void gf2_matrix_square(square, mat)
 343     unsigned long *square;
 344     unsigned long *mat;
 345 {
 346     int n;
 347
 348     for (n = 0; n < GF2_DIM; n++)
 349         square[n] = gf2_matrix_times(mat, mat[n]);
 350 }
 351
 352 /* ========================================================================= */
 353 local uLong crc32_combine_(crc1, crc2, len2)
 354     uLong crc1;
 355     uLong crc2;
 356     z_off64_t len2;
 357 {
 358     int n;
 359     unsigned long row;
 360     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
 361     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
 362
 363     /* degenerate case (also disallow negative lengths) */
 364     if (len2 <= 0)
 365         return crc1;
 366
 367     /* put operator for one zero bit in odd */
 368     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
 369     row = 1;
 370     for (n = 1; n < GF2_DIM; n++) {
 371         odd[n] = row;
 372         row <<= 1;
 373     }
 374
 375     /* put operator for two zero bits in even */
 376     gf2_matrix_square(even, odd);
 377
 378     /* put operator for four zero bits in odd */
 379     gf2_matrix_square(odd, even);
 380
 381     /* apply len2 zeros to crc1 (first square will put the operator for one
 382        zero byte, eight zero bits, in even) */
 383     do {
 384         /* apply zeros operator for this bit of len2 */
 385         gf2_matrix_square(even, odd);
 386         if (len2 & 1)
 387             crc1 = gf2_matrix_times(even, crc1);
 388         len2 >>= 1;
 389
 390         /* if no more bits set, then done */
 391         if (len2 == 0)
 392             break;
 393
 394         /* another iteration of the loop with odd and even swapped */
 395         gf2_matrix_square(odd, even);
 396         if (len2 & 1)
 397             crc1 = gf2_matrix_times(odd, crc1);
 398         len2 >>= 1;
 399
 400         /* if no more bits set, then done */
 401     } while (len2 != 0);
 402
 403     /* return combined crc */
 404     crc1 ^= crc2;
 405     return crc1;
 406 }
 407
 408 /* ========================================================================= */
 409 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 410     uLong crc1;
 411     uLong crc2;
 412     z_off_t len2;
 413 {
 414     return crc32_combine_(crc1, crc2, len2);
 415 }
 416
 417 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
 418     uLong crc1;
 419     uLong crc2;
 420     z_off64_t len2;
 421 {
 422     return crc32_combine_(crc1, crc2, len2);
 423 }