src/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     buf4--;
 304     while (len >= 32) {
 305         DOBIG32;
 306         len -= 32;
 307     }
 308     while (len >= 4) {
 309         DOBIG4;
 310         len -= 4;
 311     }
 312     buf4++;
 313     buf = (const unsigned char FAR *)buf4;
 314
 315     if (len) do {
 316         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 317     } while (--len);
 318     c = ~c;
 319     return (unsigned long)(ZSWAP32(c));
 320 }
 321
 322 #endif /* BYFOUR */
 323
 324 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 325
 326 /* ========================================================================= */
 327 local unsigned long gf2_matrix_times(mat, vec)
 328     unsigned long *mat;
 329     unsigned long vec;
 330 {
 331     unsigned long sum;
 332
 333     sum = 0;
 334     while (vec) {
 335         if (vec & 1)
 336             sum ^= *mat;
 337         vec >>= 1;
 338         mat++;
 339     }
 340     return sum;
 341 }
 342
 343 /* ========================================================================= */
 344 local void gf2_matrix_square(square, mat)
 345     unsigned long *square;
 346     unsigned long *mat;
 347 {
 348     int n;
 349
 350     for (n = 0; n < GF2_DIM; n++)
 351         square[n] = gf2_matrix_times(mat, mat[n]);
 352 }
 353
 354 /* ========================================================================= */
 355 local uLong crc32_combine_(crc1, crc2, len2)
 356     uLong crc1;
 357     uLong crc2;
 358     z_off64_t len2;
 359 {
 360     int n;
 361     unsigned long row;
 362     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
 363     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
 364
 365     /* degenerate case (also disallow negative lengths) */
 366     if (len2 <= 0)
 367         return crc1;
 368
 369     /* put operator for one zero bit in odd */
 370     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
 371     row = 1;
 372     for (n = 1; n < GF2_DIM; n++) {
 373         odd[n] = row;
 374         row <<= 1;
 375     }
 376
 377     /* put operator for two zero bits in even */
 378     gf2_matrix_square(even, odd);
 379
 380     /* put operator for four zero bits in odd */
 381     gf2_matrix_square(odd, even);
 382
 383     /* apply len2 zeros to crc1 (first square will put the operator for one
 384        zero byte, eight zero bits, in even) */
 385     do {
 386         /* apply zeros operator for this bit of len2 */
 387         gf2_matrix_square(even, odd);
 388         if (len2 & 1)
 389             crc1 = gf2_matrix_times(even, crc1);
 390         len2 >>= 1;
 391
 392         /* if no more bits set, then done */
 393         if (len2 == 0)
 394             break;
 395
 396         /* another iteration of the loop with odd and even swapped */
 397         gf2_matrix_square(odd, even);
 398         if (len2 & 1)
 399             crc1 = gf2_matrix_times(odd, crc1);
 400         len2 >>= 1;
 401
 402         /* if no more bits set, then done */
 403     } while (len2 != 0);
 404
 405     /* return combined crc */
 406     crc1 ^= crc2;
 407     return crc1;
 408 }
 409
 410 /* ========================================================================= */
 411 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 412     uLong crc1;
 413     uLong crc2;
 414     z_off_t len2;
 415 {
 416     return crc32_combine_(crc1, crc2, len2);
 417 }
 418
 419 #if 0 /* XCSoar doesn't need large file support */
 420 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
 421     uLong crc1;
 422     uLong crc2;
 423     z_off64_t len2;
 424 {
 425     return crc32_combine_(crc1, crc2, len2);
 426 }
 427 #endif