1 /*

     2  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     3  *

     4  * This code is free software; you can redistribute it and/or modify it

     5  * under the terms of the GNU General Public License version 2 only, as

     6  * published by the Free Software Foundation.  Oracle designates this

     7  * particular file as subject to the "Classpath" exception as provided

     8  * by Oracle in the LICENSE file that accompanied this code.

     9  *

    10  * This code is distributed in the hope that it will be useful, but WITHOUT

    11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    13  * version 2 for more details (a copy is included in the LICENSE file that

    14  * accompanied this code).

    15  *

    16  * You should have received a copy of the GNU General Public License version

    17  * 2 along with this work; if not, write to the Free Software Foundation,

    18  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    19  *

    20  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    21  * or visit www.oracle.com if you need additional information or have any

    22  * questions.

    23  */

    24 

    25 /* crc32.c -- compute the CRC-32 of a data stream

    26  * Copyright (C) 1995-2006, 2010, 2011, 2012 Mark Adler

    27  * For conditions of distribution and use, see copyright notice in zlib.h

    28  *

    29  * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster

    30  * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing

    31  * tables for updating the shift register in one step with three exclusive-ors

    32  * instead of four steps with four exclusive-ors.  This results in about a

    33  * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.

    34  */

    35 

    36 /* @(#) $Id$ */

    37 

    38 /*

    39   Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore

    40   protection on the static variables used to control the first-use generation

    41   of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should

    42   first call get_crc_table() to initialize the tables before allowing more than

    43   one thread to use crc32().

    44 

    45   DYNAMIC_CRC_TABLE and MAKECRCH can be #defined to write out crc32.h.

    46  */

    47 

    48 #ifdef MAKECRCH

    49 #  include <stdio.h>

    50 #  ifndef DYNAMIC_CRC_TABLE

    51 #    define DYNAMIC_CRC_TABLE

    52 #  endif /* !DYNAMIC_CRC_TABLE */

    53 #endif /* MAKECRCH */

    54 

    55 #include "zutil.h"      /* for STDC and FAR definitions */

    56 

    57 #define local static

    58 

    59 /* Definitions for doing the crc four data bytes at a time. */

    60 #if !defined(NOBYFOUR) && defined(Z_U4)

    61 #  define BYFOUR

    62 #endif

    63 #ifdef BYFOUR

    64    local unsigned long crc32_little OF((unsigned long,

    65                         const unsigned char FAR *, unsigned));

    66    local unsigned long crc32_big OF((unsigned long,

    67                         const unsigned char FAR *, unsigned));

    68 #  define TBLS 8

    69 #else

    70 #  define TBLS 1

    71 #endif /* BYFOUR */

    72 

    73 /* Local functions for crc concatenation */

    74 local unsigned long gf2_matrix_times OF((unsigned long *mat,

    75                                          unsigned long vec));

    76 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));

    77 local uLong crc32_combine_ OF((uLong crc1, uLong crc2, z_off64_t len2));

    78 

    79 

    80 #ifdef DYNAMIC_CRC_TABLE

    81 

    82 local volatile int crc_table_empty = 1;

    83 local z_crc_t FAR crc_table[TBLS][256];

    84 local void make_crc_table OF((void));

    85 #ifdef MAKECRCH

    86    local void write_table OF((FILE *, const z_crc_t FAR *));

    87 #endif /* MAKECRCH */

    88 /*

    89   Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:

    90   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.

    91 

    92   Polynomials over GF(2) are represented in binary, one bit per coefficient,

    93   with the lowest powers in the most significant bit.  Then adding polynomials

    94   is just exclusive-or, and multiplying a polynomial by x is a right shift by

    95   one.  If we call the above polynomial p, and represent a byte as the

    96   polynomial q, also with the lowest power in the most significant bit (so the

    97   byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,

    98   where a mod b means the remainder after dividing a by b.

    99 

   100   This calculation is done using the shift-register method of multiplying and

   101   taking the remainder.  The register is initialized to zero, and for each

   102   incoming bit, x^32 is added mod p to the register if the bit is a one (where

   103   x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by

   104   x (which is shifting right by one and adding x^32 mod p if the bit shifted

   105   out is a one).  We start with the highest power (least significant bit) of

   106   q and repeat for all eight bits of q.

   107 

   108   The first table is simply the CRC of all possible eight bit values.  This is

   109   all the information needed to generate CRCs on data a byte at a time for all

   110   combinations of CRC register values and incoming bytes.  The remaining tables

   111   allow for word-at-a-time CRC calculation for both big-endian and little-

   112   endian machines, where a word is four bytes.

   113 */

   114 local void make_crc_table()

   115 {

   116     z_crc_t c;

   117     int n, k;

   118     z_crc_t poly;                       /* polynomial exclusive-or pattern */

   119     /* terms of polynomial defining this crc (except x^32): */

   120     static volatile int first = 1;      /* flag to limit concurrent making */

   121     static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

   122 

   123     /* See if another task is already doing this (not thread-safe, but better

   124        than nothing -- significantly reduces duration of vulnerability in

   125        case the advice about DYNAMIC_CRC_TABLE is ignored) */

   126     if (first) {

   127         first = 0;

   128 

   129         /* make exclusive-or pattern from polynomial (0xedb88320UL) */

   130         poly = 0;

   131         for (n = 0; n < (int)(sizeof(p)/sizeof(unsigned char)); n++)

   132             poly |= (z_crc_t)1 << (31 - p[n]);

   133 

   134         /* generate a crc for every 8-bit value */

   135         for (n = 0; n < 256; n++) {

   136             c = (z_crc_t)n;

   137             for (k = 0; k < 8; k++)

   138                 c = c & 1 ? poly ^ (c >> 1) : c >> 1;

   139             crc_table[0][n] = c;

   140         }

   141 

   142 #ifdef BYFOUR

   143         /* generate crc for each value followed by one, two, and three zeros,

   144            and then the byte reversal of those as well as the first table */

   145         for (n = 0; n < 256; n++) {

   146             c = crc_table[0][n];

   147             crc_table[4][n] = ZSWAP32(c);

   148             for (k = 1; k < 4; k++) {

   149                 c = crc_table[0][c & 0xff] ^ (c >> 8);

   150                 crc_table[k][n] = c;

   151                 crc_table[k + 4][n] = ZSWAP32(c);

   152             }

   153         }

   154 #endif /* BYFOUR */

   155 

   156         crc_table_empty = 0;

   157     }

   158     else {      /* not first */

   159         /* wait for the other guy to finish (not efficient, but rare) */

   160         while (crc_table_empty)

   161             ;

   162     }

   163 

   164 #ifdef MAKECRCH

   165     /* write out CRC tables to crc32.h */

   166     {

   167         FILE *out;

   168 

   169         out = fopen("crc32.h", "w");

   170         if (out == NULL) return;

   171         fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");

   172         fprintf(out, " * Generated automatically by crc32.c\n */\n\n");

   173         fprintf(out, "local const z_crc_t FAR ");

   174         fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");

   175         write_table(out, crc_table[0]);

   176 #  ifdef BYFOUR

   177         fprintf(out, "#ifdef BYFOUR\n");

   178         for (k = 1; k < 8; k++) {

   179             fprintf(out, "  },\n  {\n");

   180             write_table(out, crc_table[k]);

   181         }

   182         fprintf(out, "#endif\n");

   183 #  endif /* BYFOUR */

   184         fprintf(out, "  }\n};\n");

   185         fclose(out);

   186     }

   187 #endif /* MAKECRCH */

   188 }

   189 

   190 #ifdef MAKECRCH

   191 local void write_table(out, table)

   192     FILE *out;

   193     const z_crc_t FAR *table;

   194 {

   195     int n;

   196 

   197     for (n = 0; n < 256; n++)

   198         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ",

   199                 (unsigned long)(table[n]),

   200                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));

   201 }

   202 #endif /* MAKECRCH */

   203 

   204 #else /* !DYNAMIC_CRC_TABLE */

   205 /* ========================================================================

   206  * Tables of CRC-32s of all single-byte values, made by make_crc_table().

   207  */

   208 #include "crc32.h"

   209 #endif /* DYNAMIC_CRC_TABLE */

   210 

   211 /* =========================================================================

   212  * This function can be used by asm versions of crc32()

   213  */

   214 const z_crc_t FAR * ZEXPORT get_crc_table()

   215 {

   216 #ifdef DYNAMIC_CRC_TABLE

   217     if (crc_table_empty)

   218         make_crc_table();

   219 #endif /* DYNAMIC_CRC_TABLE */

   220     return (const z_crc_t FAR *)crc_table;

   221 }

   222 

   223 /* ========================================================================= */

   224 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)

   225 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1

   226 

   227 /* ========================================================================= */

   228 uLong ZEXPORT crc32(crc, buf, len)

   229     uLong crc;

   230     const unsigned char FAR *buf;

   231     uInt len;

   232 {

   233     if (buf == Z_NULL) return 0UL;

   234 

   235 #ifdef DYNAMIC_CRC_TABLE

   236     if (crc_table_empty)

   237         make_crc_table();

   238 #endif /* DYNAMIC_CRC_TABLE */

   239 

   240 #ifdef BYFOUR

   241     if (sizeof(void *) == sizeof(ptrdiff_t)) {

   242         z_crc_t endian;

   243 

   244         endian = 1;

   245         if (*((unsigned char *)(&endian)))

   246             return (uLong)crc32_little(crc, buf, len);

   247         else

   248             return (uLong)crc32_big(crc, buf, len);

   249     }

   250 #endif /* BYFOUR */

   251     crc = crc ^ 0xffffffffUL;

   252     while (len >= 8) {

   253         DO8;

   254         len -= 8;

   255     }

   256     if (len) do {

   257         DO1;

   258     } while (--len);

   259     return crc ^ 0xffffffffUL;

   260 }

   261 

   262 #ifdef BYFOUR

   263 

   264 /* ========================================================================= */

   265 #define DOLIT4 c ^= *buf4++; \

   266         c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \

   267             crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]

   268 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4

   269 

   270 /* ========================================================================= */

   271 local unsigned long crc32_little(crc, buf, len)

   272     unsigned long crc;

   273     const unsigned char FAR *buf;

   274     unsigned len;

   275 {

   276     register z_crc_t c;

   277     register const z_crc_t FAR *buf4;

   278 

   279     c = (z_crc_t)crc;

   280     c = ~c;

   281     while (len && ((ptrdiff_t)buf & 3)) {

   282         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);

   283         len--;

   284     }

   285 

   286     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;

   287     while (len >= 32) {

   288         DOLIT32;

   289         len -= 32;

   290     }

   291     while (len >= 4) {

   292         DOLIT4;

   293         len -= 4;

   294     }

   295     buf = (const unsigned char FAR *)buf4;

   296 

   297     if (len) do {

   298         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);

   299     } while (--len);

   300     c = ~c;

   301     return (unsigned long)c;

   302 }

   303 

   304 /* ========================================================================= */

   305 #define DOBIG4 c ^= *++buf4; \

   306         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \

   307             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]

   308 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4

   309 

   310 /* ========================================================================= */

   311 local unsigned long crc32_big(crc, buf, len)

   312     unsigned long crc;

   313     const unsigned char FAR *buf;

   314     unsigned len;

   315 {

   316     register z_crc_t c;

   317     register const z_crc_t FAR *buf4;

   318 

   319     c = ZSWAP32((z_crc_t)crc);

   320     c = ~c;

   321     while (len && ((ptrdiff_t)buf & 3)) {

   322         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);

   323         len--;

   324     }

   325 

   326     buf4 = (const z_crc_t FAR *)(const void FAR *)buf;

   327     buf4--;

   328     while (len >= 32) {

   329         DOBIG32;

   330         len -= 32;

   331     }

   332     while (len >= 4) {

   333         DOBIG4;

   334         len -= 4;

   335     }

   336     buf4++;

   337     buf = (const unsigned char FAR *)buf4;

   338 

   339     if (len) do {

   340         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);

   341     } while (--len);

   342     c = ~c;

   343     return (unsigned long)(ZSWAP32(c));

   344 }

   345 

   346 #endif /* BYFOUR */

   347 

   348 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */

   349 

   350 /* ========================================================================= */

   351 local unsigned long gf2_matrix_times(mat, vec)

   352     unsigned long *mat;

   353     unsigned long vec;

   354 {

   355     unsigned long sum;

   356 

   357     sum = 0;

   358     while (vec) {

   359         if (vec & 1)

   360             sum ^= *mat;

   361         vec >>= 1;

   362         mat++;

   363     }

   364     return sum;

   365 }

   366 

   367 /* ========================================================================= */

   368 local void gf2_matrix_square(square, mat)

   369     unsigned long *square;

   370     unsigned long *mat;

   371 {

   372     int n;

   373 

   374     for (n = 0; n < GF2_DIM; n++)

   375         square[n] = gf2_matrix_times(mat, mat[n]);

   376 }

   377 

   378 /* ========================================================================= */

   379 local uLong crc32_combine_(crc1, crc2, len2)

   380     uLong crc1;

   381     uLong crc2;

   382     z_off64_t len2;

   383 {

   384     int n;

   385     unsigned long row;

   386     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */

   387     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */

   388 

   389     /* degenerate case (also disallow negative lengths) */

   390     if (len2 <= 0)

   391         return crc1;

   392 

   393     /* put operator for one zero bit in odd */

   394     odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */

   395     row = 1;

   396     for (n = 1; n < GF2_DIM; n++) {

   397         odd[n] = row;

   398         row <<= 1;

   399     }

   400 

   401     /* put operator for two zero bits in even */

   402     gf2_matrix_square(even, odd);

   403 

   404     /* put operator for four zero bits in odd */

   405     gf2_matrix_square(odd, even);

   406 

   407     /* apply len2 zeros to crc1 (first square will put the operator for one

   408        zero byte, eight zero bits, in even) */

   409     do {

   410         /* apply zeros operator for this bit of len2 */

   411         gf2_matrix_square(even, odd);

   412         if (len2 & 1)

   413             crc1 = gf2_matrix_times(even, crc1);

   414         len2 >>= 1;

   415 

   416         /* if no more bits set, then done */

   417         if (len2 == 0)

   418             break;

   419 

   420         /* another iteration of the loop with odd and even swapped */

   421         gf2_matrix_square(odd, even);

   422         if (len2 & 1)

   423             crc1 = gf2_matrix_times(odd, crc1);

   424         len2 >>= 1;

   425 

   426         /* if no more bits set, then done */

   427     } while (len2 != 0);

   428 

   429     /* return combined crc */

   430     crc1 ^= crc2;

   431     return crc1;

   432 }

   433 

   434 /* ========================================================================= */

   435 uLong ZEXPORT crc32_combine(crc1, crc2, len2)

   436     uLong crc1;

   437     uLong crc2;

   438     z_off_t len2;

   439 {

   440     return crc32_combine_(crc1, crc2, len2);

   441 }

   442 

   443 uLong ZEXPORT crc32_combine64(crc1, crc2, len2)

   444     uLong crc1;

   445     uLong crc2;

   446     z_off64_t len2;

   447 {

   448     return crc32_combine_(crc1, crc2, len2);

   449 }