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