third_party/zlib/crc32.c

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