libkern/zlib/z_crc32.c

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