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