libkern/zlib/crc32.c

   1 /*
   2  * Copyright (c) 2008 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /* crc32.c -- compute the CRC-32 of a data stream
  29  * Copyright (C) 1995-2005 Mark Adler
  30  * For conditions of distribution and use, see copyright notice in zlib.h
  31  *
  32  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
  33  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
  34  * tables for updating the shift register in one step with three exclusive-ors
  35  * instead of four steps with four exclusive-ors.  This results in about a
  36  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
  37  */
  38
  39 /* @(#) $Id$ */
  40
  41 /*
  42   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
  43   protection on the static variables used to control the first-use generation
  44   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
  45   first call get_crc_table() to initialize the tables before allowing more than
  46   one thread to use crc32().
  47  */
  48
  49 #ifdef MAKECRCH
  50 #  include <stdio.h>
  51 #  ifndef DYNAMIC_CRC_TABLE
  52 #    define DYNAMIC_CRC_TABLE
  53 #  endif /* !DYNAMIC_CRC_TABLE */
  54 #endif /* MAKECRCH */
  55
  56 #include "zutil.h"      /* for STDC and FAR definitions */
  57
  58 #define local static
  59
  60 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
  61 #ifndef NOBYFOUR
  62 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
  63 #    include <machine/limits.h>
  64 #    define BYFOUR
  65 #    if (UINT_MAX == 0xffffffffUL)
  66        typedef unsigned int u4;
  67 #    else
  68 #      if (ULONG_MAX == 0xffffffffUL)
  69          typedef unsigned long u4;
  70 #      else
  71 #        if (USHRT_MAX == 0xffffffffUL)
  72            typedef unsigned short u4;
  73 #        else
  74 #          undef BYFOUR     /* can't find a four-byte integer type! */
  75 #        endif
  76 #      endif
  77 #    endif
  78 #  endif /* STDC */
  79 #endif /* !NOBYFOUR */
  80
  81 /* Definitions for doing the crc four data bytes at a time. */
  82 #ifdef BYFOUR
  83 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
  84                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
  85    local unsigned long crc32_little OF((unsigned long,
  86                         const unsigned char FAR *, unsigned));
  87    local unsigned long crc32_big OF((unsigned long,
  88                         const unsigned char FAR *, unsigned));
  89 #  define TBLS 8
  90 #else
  91 #  define TBLS 1
  92 #endif /* BYFOUR */
  93
  94 /* Local functions for crc concatenation */
  95 local unsigned long gf2_matrix_times OF((unsigned long *mat,
  96                                          unsigned long vec));
  97 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
  98
  99 #ifdef DYNAMIC_CRC_TABLE
 100
 101 local volatile int crc_table_empty = 1;
 102 local unsigned long FAR crc_table[TBLS][256];
 103 local void make_crc_table OF((void));
 104 #ifdef MAKECRCH
 105    local void write_table OF((FILE *, const unsigned long FAR *));
 106 #endif /* MAKECRCH */
 107 /*
 108   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
 109   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.
 110
 111   Polynomials over GF(2) are represented in binary, one bit per coefficient,
 112   with the lowest powers in the most significant bit.  Then adding polynomials
 113   is just exclusive-or, and multiplying a polynomial by x is a right shift by
 114   one.  If we call the above polynomial p, and represent a byte as the
 115   polynomial q, also with the lowest power in the most significant bit (so the
 116   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
 117   where a mod b means the remainder after dividing a by b.
 118
 119   This calculation is done using the shift-register method of multiplying and
 120   taking the remainder.  The register is initialized to zero, and for each
 121   incoming bit, x^32 is added mod p to the register if the bit is a one (where
 122   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
 123   x (which is shifting right by one and adding x^32 mod p if the bit shifted
 124   out is a one).  We start with the highest power (least significant bit) of
 125   q and repeat for all eight bits of q.
 126
 127   The first table is simply the CRC of all possible eight bit values.  This is
 128   all the information needed to generate CRCs on data a byte at a time for all
 129   combinations of CRC register values and incoming bytes.  The remaining tables
 130   allow for word-at-a-time CRC calculation for both big-endian and little-
 131   endian machines, where a word is four bytes.
 132 */
 133 local void make_crc_table()
 134 {
 135     unsigned long c;
 136     int n, k;
 137     unsigned long poly;                 /* polynomial exclusive-or pattern */
 138     /* terms of polynomial defining this crc (except x^32): */
 139     static volatile int first = 1;      /* flag to limit concurrent making */
 140     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
 141
 142     /* See if another task is already doing this (not thread-safe, but better
 143        than nothing -- significantly reduces duration of vulnerability in
 144        case the advice about DYNAMIC_CRC_TABLE is ignored) */
 145     if (first) {
 146         first = 0;
 147
 148         /* make exclusive-or pattern from polynomial (0xedb88320UL) */
 149         poly = 0UL;
 150         for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
 151             poly |= 1UL << (31 - p[n]);
 152
 153         /* generate a crc for every 8-bit value */
 154         for (n = 0; n < 256; n++) {
 155             c = (unsigned long)n;
 156             for (k = 0; k < 8; k++)
 157                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;
 158             crc_table[0][n] = c;
 159         }
 160
 161 #ifdef BYFOUR
 162         /* generate crc for each value followed by one, two, and three zeros,
 163            and then the byte reversal of those as well as the first table */
 164         for (n = 0; n < 256; n++) {
 165             c = crc_table[0][n];
 166             crc_table[4][n] = REV(c);
 167             for (k = 1; k < 4; k++) {
 168                 c = crc_table[0][c & 0xff] ^ (c >> 8);
 169                 crc_table[k][n] = c;
 170                 crc_table[k + 4][n] = REV(c);
 171             }
 172         }
 173 #endif /* BYFOUR */
 174
 175         crc_table_empty = 0;
 176     }
 177     else {      /* not first */
 178         /* wait for the other guy to finish (not efficient, but rare) */
 179         while (crc_table_empty)
 180             ;
 181     }
 182
 183 #ifdef MAKECRCH
 184     /* write out CRC tables to crc32.h */
 185     {
 186         FILE *out;
 187
 188         out = fopen("crc32.h", "w");
 189         if (out == NULL) return;
 190         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
 191         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
 192         fprintf(out, "local const unsigned long FAR ");
 193         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
 194         write_table(out, crc_table[0]);
 195 #  ifdef BYFOUR
 196         fprintf(out, "#ifdef BYFOUR\n");
 197         for (k = 1; k < 8; k++) {
 198             fprintf(out, "  },\n  {\n");
 199             write_table(out, crc_table[k]);
 200         }
 201         fprintf(out, "#endif\n");
 202 #  endif /* BYFOUR */
 203         fprintf(out, "  }\n};\n");
 204         fclose(out);
 205     }
 206 #endif /* MAKECRCH */
 207 }
 208
 209 #ifdef MAKECRCH
 210 local void write_table(out, table)
 211     FILE *out;
 212     const unsigned long FAR *table;
 213 {
 214     int n;
 215
 216     for (n = 0; n < 256; n++)
 217         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
 218                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
 219 }
 220 #endif /* MAKECRCH */
 221
 222 #else /* !DYNAMIC_CRC_TABLE */
 223 /* ========================================================================
 224  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
 225  */
 226 #include "crc32.h"
 227 #endif /* DYNAMIC_CRC_TABLE */
 228
 229 /* =========================================================================
 230  * This function can be used by asm versions of crc32()
 231  */
 232 const unsigned long FAR * ZEXPORT get_crc_table()
 233 {
 234 #ifdef DYNAMIC_CRC_TABLE
 235     if (crc_table_empty)
 236         make_crc_table();
 237 #endif /* DYNAMIC_CRC_TABLE */
 238     return (const unsigned long FAR *)crc_table;
 239 }
 240
 241 /* ========================================================================= */
 242 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
 243 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
 244
 245 /* ========================================================================= */
 246 unsigned long ZEXPORT z_crc32(crc, buf, len)
 247     unsigned long crc;
 248     const unsigned char FAR *buf;
 249     unsigned len;
 250 {
 251     if (buf == Z_NULL) return 0UL;
 252
 253 #ifdef DYNAMIC_CRC_TABLE
 254     if (crc_table_empty)
 255         make_crc_table();
 256 #endif /* DYNAMIC_CRC_TABLE */
 257
 258 #ifdef BYFOUR
 259     if (sizeof(void *) == sizeof(ptrdiff_t)) {
 260         u4 endian;
 261
 262         endian = 1;
 263         if (*((unsigned char *)(&endian)))
 264             return crc32_little(crc, buf, len);
 265         else
 266             return crc32_big(crc, buf, len);
 267     }
 268 #endif /* BYFOUR */
 269     crc = crc ^ 0xffffffffUL;
 270     while (len >= 8) {
 271         DO8;
 272         len -= 8;
 273     }
 274     if (len) do {
 275         DO1;
 276     } while (--len);
 277     return crc ^ 0xffffffffUL;
 278 }
 279
 280 #ifdef BYFOUR
 281
 282 /* ========================================================================= */
 283 #define DOLIT4 c ^= *buf4++; \
 284         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
 285             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
 286 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
 287
 288 /* ========================================================================= */
 289 local unsigned long crc32_little(crc, buf, len)
 290     unsigned long crc;
 291     const unsigned char FAR *buf;
 292     unsigned len;
 293 {
 294     register u4 c;
 295     register const u4 FAR *buf4;
 296
 297     c = (u4)crc;
 298     c = ~c;
 299     while (len && ((ptrdiff_t)buf & 3)) {
 300         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 301         len--;
 302     }
 303
 304     buf4 = (const u4 FAR *)(const void FAR *)buf;
 305     while (len >= 32) {
 306         DOLIT32;
 307         len -= 32;
 308     }
 309     while (len >= 4) {
 310         DOLIT4;
 311         len -= 4;
 312     }
 313     buf = (const unsigned char FAR *)buf4;
 314
 315     if (len) do {
 316         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
 317     } while (--len);
 318     c = ~c;
 319     return (unsigned long)c;
 320 }
 321
 322 /* ========================================================================= */
 323 #define DOBIG4 c ^= *++buf4; \
 324         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
 325             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
 326 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
 327
 328 /* ========================================================================= */
 329 local unsigned long crc32_big(crc, buf, len)
 330     unsigned long crc;
 331     const unsigned char FAR *buf;
 332     unsigned len;
 333 {
 334     register u4 c;
 335     register const u4 FAR *buf4;
 336
 337     c = REV((u4)crc);
 338     c = ~c;
 339     while (len && ((ptrdiff_t)buf & 3)) {
 340         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 341         len--;
 342     }
 343
 344     buf4 = (const u4 FAR *)(const void FAR *)buf;
 345     buf4--;
 346     while (len >= 32) {
 347         DOBIG32;
 348         len -= 32;
 349     }
 350     while (len >= 4) {
 351         DOBIG4;
 352         len -= 4;
 353     }
 354     buf4++;
 355     buf = (const unsigned char FAR *)buf4;
 356
 357     if (len) do {
 358         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
 359     } while (--len);
 360     c = ~c;
 361     return (unsigned long)(REV(c));
 362 }
 363
 364 #endif /* BYFOUR */
 365
 366 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
 367
 368 /* ========================================================================= */
 369 local unsigned long gf2_matrix_times(mat, vec)
 370     unsigned long *mat;
 371     unsigned long vec;
 372 {
 373     unsigned long sum;
 374
 375     sum = 0;
 376     while (vec) {
 377         if (vec & 1)
 378             sum ^= *mat;
 379         vec >>= 1;
 380         mat++;
 381     }
 382     return sum;
 383 }
 384
 385 /* ========================================================================= */
 386 local void gf2_matrix_square(square, mat)
 387     unsigned long *square;
 388     unsigned long *mat;
 389 {
 390     int n;
 391
 392     for (n = 0; n < GF2_DIM; n++)
 393         square[n] = gf2_matrix_times(mat, mat[n]);
 394 }
 395
 396 /* ========================================================================= */
 397 uLong ZEXPORT z_crc32_combine(crc1, crc2, len2)
 398     uLong crc1;
 399     uLong crc2;
 400     z_off_t len2;
 401 {
 402     int n;
 403     unsigned long row;
 404     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
 405     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
 406
 407     /* degenerate case */
 408     if (len2 == 0)
 409         return crc1;
 410
 411     /* put operator for one zero bit in odd */
 412     odd[0] = 0xedb88320L;           /* CRC-32 polynomial */
 413     row = 1;
 414     for (n = 1; n < GF2_DIM; n++) {
 415         odd[n] = row;
 416         row <<= 1;
 417     }
 418
 419     /* put operator for two zero bits in even */
 420     gf2_matrix_square(even, odd);
 421
 422     /* put operator for four zero bits in odd */
 423     gf2_matrix_square(odd, even);
 424
 425     /* apply len2 zeros to crc1 (first square will put the operator for one
 426        zero byte, eight zero bits, in even) */
 427     do {
 428         /* apply zeros operator for this bit of len2 */
 429         gf2_matrix_square(even, odd);
 430         if (len2 & 1)
 431             crc1 = gf2_matrix_times(even, crc1);
 432         len2 >>= 1;
 433
 434         /* if no more bits set, then done */
 435         if (len2 == 0)
 436             break;
 437
 438         /* another iteration of the loop with odd and even swapped */
 439         gf2_matrix_square(odd, even);
 440         if (len2 & 1)
 441             crc1 = gf2_matrix_times(odd, crc1);
 442         len2 >>= 1;
 443
 444         /* if no more bits set, then done */
 445     } while (len2 != 0);
 446
 447     /* return combined crc */
 448     crc1 ^= crc2;
 449     return crc1;
 450 }