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    This BYFOUR code accesses the passed unsigned char * buffer with a 32-bit
 242    integer pointer type. This violates the strict aliasing rule, where a
 243    compiler can assume, for optimization purposes, that two pointers to
 244    fundamentally different types won't ever point to the same memory. This can
 245    manifest as a problem only if one of the pointers is written to. This code
 246    only reads from those pointers. So long as this code remains isolated in
 247    this compilation unit, there won't be a problem. For this reason, this code
 248    should not be copied and pasted into a compilation unit in which other code
 249    writes to the buffer that is passed to these routines.
 250  */
 251
 252 /* ========================================================================= */
 253 #define DOLIT4 c ^= *buf4++; \
 254         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 255             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 256 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 257
 258 /* ========================================================================= */
 259 local unsigned long crc32_little(crc, buf, len)
 260     unsigned long crc;
 261     const unsigned char FAR *buf;
 262     unsigned len;
 263 {
 264     register z_crc_t c;
 265     register const z_crc_t FAR *buf4;
 266
 267     c = (z_crc_t)crc;
 268     c = ~c;
 269     while (len && ((ptrdiff_t)buf & 3)) {
 270         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 271         len--;
 272     }
 273
 274     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
 275     while (len >= 32) {
 276         DOLIT32;
 277         len -= 32;
 278     }
 279     while (len >= 4) {
 280         DOLIT4;
 281         len -= 4;
 282     }
 283     buf = (const unsigned char FAR *)buf4;
 284
 285     if (len) do {
 286         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 287     } while (--len);
 288     c = ~c;
 289     return (unsigned long)c;
 290 }
 291
 292 /* ========================================================================= */
 293 #define DOBIG4 c ^= *buf4++; \
 294         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 295             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 296 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 297
 298 /* ========================================================================= */
 299 local unsigned long crc32_big(crc, buf, len)
 300     unsigned long crc;
 301     const unsigned char FAR *buf;
 302     unsigned len;
 303 {
 304     register z_crc_t c;
 305     register const z_crc_t FAR *buf4;
 306
 307     c = ZSWAP32((z_crc_t)crc);
 308     c = ~c;
 309     while (len && ((ptrdiff_t)buf & 3)) {
 310         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 311         len--;
 312     }
 313
 314     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;
 315     while (len >= 32) {
 316         DOBIG32;
 317         len -= 32;
 318     }
 319     while (len >= 4) {
 320         DOBIG4;
 321         len -= 4;
 322     }
 323     buf = (const unsigned char FAR *)buf4;
 324
 325     if (len) do {
 326         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 327     } while (--len);
 328     c = ~c;
 329     return (unsigned long)(ZSWAP32(c));
 330 }
 331
 332 #endif /* BYFOUR */
 333
 334 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 335
 336 /* ========================================================================= */
 337 local unsigned long gf2_matrix_times(mat, vec)
 338     unsigned long *mat;
 339     unsigned long vec;
 340 {
 341     unsigned long sum;
 342
 343     sum = 0;
 344     while (vec) {
 345         if (vec & 1)
 346             sum ^= *mat;
 347         vec >>= 1;
 348         mat++;
 349     }
 350     return sum;
 351 }
 352
 353 /* ========================================================================= */
 354 local void gf2_matrix_square(square, mat)
 355     unsigned long *square;
 356     unsigned long *mat;
 357 {
 358     int n;
 359
 360     for (n = 0; n < GF2_DIM; n++)
 361         square[n] = gf2_matrix_times(mat, mat[n]);
 362 }
 363
 364 /* ========================================================================= */
 365 local uLong crc32_combine_(crc1, crc2, len2)
 366     uLong crc1;
 367     uLong crc2;
 368     z_off64_t len2;
 369 {
 370     int n;
 371     unsigned long row;
 372     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
 373     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
 374
 375     /* degenerate case (also disallow negative lengths) */
 376     if (len2 <= 0)
 377         return crc1;
 378
 379     /* put operator for one zero bit in odd */
 380     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
 381     row = 1;
 382     for (n = 1; n < GF2_DIM; n++) {
 383         odd[n] = row;
 384         row <<= 1;
 385     }
 386
 387     /* put operator for two zero bits in even */
 388     gf2_matrix_square(even, odd);
 389
 390     /* put operator for four zero bits in odd */
 391     gf2_matrix_square(odd, even);
 392
 393     /* apply len2 zeros to crc1 (first square will put the operator for one
 394        zero byte, eight zero bits, in even) */
 395     do {
 396         /* apply zeros operator for this bit of len2 */
 397         gf2_matrix_square(even, odd);
 398         if (len2 & 1)
 399             crc1 = gf2_matrix_times(even, crc1);
 400         len2 >>= 1;
 401
 402         /* if no more bits set, then done */
 403         if (len2 == 0)
 404             break;
 405
 406         /* another iteration of the loop with odd and even swapped */
 407         gf2_matrix_square(odd, even);
 408         if (len2 & 1)
 409             crc1 = gf2_matrix_times(odd, crc1);
 410         len2 >>= 1;
 411
 412         /* if no more bits set, then done */
 413     } while (len2 != 0);
 414
 415     /* return combined crc */
 416     crc1 ^= crc2;
 417     return crc1;
 418 }
 419
 420 /* ========================================================================= */
 421 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
 422     uLong crc1;
 423     uLong crc2;
 424     z_off_t len2;
 425 {
 426     return crc32_combine_(crc1, crc2, len2);
 427 }
 428
 429 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
 430     uLong crc1;
 431     uLong crc2;
 432     z_off64_t len2;
 433 {
 434     return crc32_combine_(crc1, crc2, len2);
 435 }