stdlibs/libz/zlib/crc32.cpp
changeset 0 e4d67989cc36
equal deleted inserted replaced
-1:000000000000 0:e4d67989cc36
       
     1 /* crc32.cpp -- compute the CRC-32 of a data stream
       
     2  * Copyright (C) 1995-2005 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: crc32.cpp,v 1.1.2.1 2008/08/14 15:26:57 e0222316 Exp $ */
       
    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 
       
    22 #ifdef MAKECRCH
       
    23 #  include <stdio.h>
       
    24 #  ifndef DYNAMIC_CRC_TABLE
       
    25 #    define DYNAMIC_CRC_TABLE
       
    26 #  endif /* !DYNAMIC_CRC_TABLE */
       
    27 #endif /* MAKECRCH */
       
    28 
       
    29 /* These defines are usually taken from limits.h, however this file is not supported in Symbian. */
       
    30 #if (defined(__SYMBIAN32__) && !defined(__TOOLS2__) && !defined(__TOOLS__))  
       
    31   #define UINT_MAX  0xffffffffU  /* Values taken from _limits.h:from PIPS  */
       
    32   #define ULONG_MAX 0xffffffffUL /* Removing may slow down the crc operation */
       
    33   typedef int ptrdiff_t;
       
    34 #endif /* __SYMBIAN32__ && !__TOOLS2__) && !__TOOLS__ */
       
    35 
       
    36 #include "zutil.h"      /* for STDC and FAR definitions */
       
    37 
       
    38 
       
    39 /* Find a four-byte integer type for crc32_little() and crc32_big(). */
       
    40 #ifndef NOBYFOUR
       
    41 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */
       
    42 #  	 if (!defined(__SYMBIAN32__) || defined(__TOOLS2__) || defined(__TOOLS__)) /* only include for Tools builds */
       
    43 #      include <limits.h>
       
    44 #    endif /* !__SYMBIAN32__ || __TOOLS2__) || __TOOLS__ */
       
    45 #    define BYFOUR
       
    46 #    if (UINT_MAX == 0xffffffffUL)
       
    47 	   typedef unsigned int u4;
       
    48 #    else
       
    49 #      if (ULONG_MAX == 0xffffffffUL)
       
    50          typedef unsigned long u4;
       
    51 #      else
       
    52 #        if (USHRT_MAX == 0xffffffffUL)
       
    53            typedef unsigned short u4;
       
    54 #        else
       
    55 #          undef BYFOUR     /* can't find a four-byte integer type! */
       
    56 #        endif
       
    57 #      endif
       
    58 #    endif
       
    59 #  endif /* STDC */
       
    60 #endif /* !NOBYFOUR */
       
    61 
       
    62 /* Definitions for doing the crc four data bytes at a time. */
       
    63 #ifdef BYFOUR
       
    64 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
       
    65                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))
       
    66    local unsigned long crc32_little OF((unsigned long,
       
    67                         const unsigned char FAR *, unsigned));
       
    68    local unsigned long crc32_big OF((unsigned long,
       
    69                         const unsigned char FAR *, unsigned));
       
    70 #  define TBLS 8
       
    71 #else
       
    72 #  define TBLS 1
       
    73 #endif /* BYFOUR */
       
    74 
       
    75 /* Local functions for crc concatenation */
       
    76 local unsigned long gf2_matrix_times OF((unsigned long *mat,
       
    77                                          unsigned long vec));
       
    78 local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
       
    79 
       
    80 #ifdef DYNAMIC_CRC_TABLE
       
    81 
       
    82 local volatile int crc_table_empty = 1;
       
    83 local unsigned long FAR crc_table[TBLS][256];
       
    84 local void make_crc_table OF((void));
       
    85 #ifdef MAKECRCH
       
    86    local void write_table OF((FILE *, const unsigned long 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     unsigned long c;
       
   117     int n, k;
       
   118     unsigned long 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 = 0UL;
       
   131         for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
       
   132             poly |= 1UL << (31 - p[n]);
       
   133 
       
   134         /* generate a crc for every 8-bit value */
       
   135         for (n = 0; n < 256; n++) {
       
   136             c = (unsigned long)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] = REV(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] = REV(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 unsigned long 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 #ifdef __SYMBIAN32__
       
   192 local void write_table(FILE * out, const unsigned long FAR * table)
       
   193 #else	
       
   194 local void write_table(out, table)
       
   195     FILE *out;
       
   196     const unsigned long FAR *table;
       
   197 #endif //__SYMBIAN32__
       
   198 {
       
   199     int n;
       
   200 
       
   201     for (n = 0; n < 256; n++)
       
   202         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
       
   203                 n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
       
   204 }
       
   205 #endif /* MAKECRCH */
       
   206 
       
   207 #else /* !DYNAMIC_CRC_TABLE */
       
   208 /* ========================================================================
       
   209  * Tables of CRC-32s of all single-byte values, made by make_crc_table().
       
   210  */
       
   211 #include "crc32.h"
       
   212 #endif /* DYNAMIC_CRC_TABLE */
       
   213 
       
   214 /* =========================================================================
       
   215  * This function can be used by asm versions of crc32()
       
   216  */
       
   217 #ifdef __SYMBIAN32__
       
   218 EXPORT_C  const unsigned long FAR *   get_crc_table_r()
       
   219 #else
       
   220 const unsigned long FAR * ZEXPORT get_crc_table()
       
   221 #endif //__SYMBIAN32__
       
   222 {
       
   223 #ifdef DYNAMIC_CRC_TABLE
       
   224     if (crc_table_empty)
       
   225         make_crc_table();
       
   226 #endif /* DYNAMIC_CRC_TABLE */
       
   227     return (const unsigned long FAR *)crc_table;
       
   228 }
       
   229 
       
   230 /* ========================================================================= */
       
   231 #define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
       
   232 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
       
   233 
       
   234 /* ========================================================================= */
       
   235 
       
   236 #ifdef __SYMBIAN32__
       
   237 EXPORT_C unsigned long  crc32_r( unsigned long crc,  const unsigned char FAR *  buf,unsigned len)
       
   238 #else
       
   239 unsigned long ZEXPORT crc32(crc, buf, len)
       
   240     unsigned long crc;
       
   241     const unsigned char FAR *buf;
       
   242     unsigned len;
       
   243 #endif //__SYMBIAN32__
       
   244 {
       
   245     if (buf == Z_NULL) return 0UL;
       
   246 
       
   247 #ifdef DYNAMIC_CRC_TABLE
       
   248     if (crc_table_empty)
       
   249         make_crc_table();
       
   250 #endif /* DYNAMIC_CRC_TABLE */
       
   251 
       
   252 #ifdef BYFOUR
       
   253     if (sizeof(void *) == sizeof(ptrdiff_t)) {
       
   254         u4 endian;
       
   255 
       
   256         endian = 1;
       
   257         if (*((unsigned char *)(&endian)))
       
   258             return crc32_little(crc, buf, len);
       
   259         else
       
   260             return crc32_big(crc, buf, len);
       
   261     }
       
   262     else 
       
   263     {    	
       
   264 #endif /* BYFOUR */
       
   265     crc = crc ^ 0xffffffffUL;
       
   266     while (len >= 8) {
       
   267         DO8;
       
   268         len -= 8;
       
   269     }
       
   270     if (len) do {
       
   271         DO1;
       
   272     } while (--len);
       
   273     return crc ^ 0xffffffffUL;
       
   274  #ifdef BYFOUR
       
   275     }
       
   276  #endif    
       
   277 }
       
   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 #ifdef __SYMBIAN32__
       
   290 local unsigned long crc32_little(   unsigned long  crc,const unsigned char FAR *  buf,unsigned len)
       
   291 #else
       
   292 local unsigned long crc32_little(crc, buf, len)
       
   293     unsigned long crc;
       
   294     const unsigned char FAR *buf;
       
   295     unsigned len;
       
   296 #endif //__SYMBIAN32__
       
   297 {
       
   298     register u4 c;
       
   299     register const u4 FAR *buf4;
       
   300 
       
   301     c = (u4)crc;
       
   302     c = ~c;
       
   303     while (len && ((ptrdiff_t)buf & 3)) {
       
   304         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
       
   305         len--;
       
   306     }
       
   307 
       
   308     buf4 = (const u4 FAR *)(const void FAR *)buf;
       
   309     while (len >= 32) {
       
   310         DOLIT32;
       
   311         len -= 32;
       
   312     }
       
   313     while (len >= 4) {
       
   314         DOLIT4;
       
   315         len -= 4;
       
   316     }
       
   317     buf = (const unsigned char FAR *)buf4;
       
   318 
       
   319     if (len) do {
       
   320         c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
       
   321     } while (--len);
       
   322     c = ~c;
       
   323     return (unsigned long)c;
       
   324 }
       
   325 
       
   326 /* ========================================================================= */
       
   327 #define DOBIG4 c ^= *++buf4; \
       
   328         c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
       
   329             crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
       
   330 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
       
   331 
       
   332 /* ========================================================================= */
       
   333 #ifdef __SYMBIAN32__
       
   334 local unsigned long crc32_big(    unsigned long crc,    const unsigned char FAR *  buf,unsigned  len)
       
   335 #else
       
   336 local unsigned long crc32_big(crc, buf, len)
       
   337     unsigned long crc;
       
   338     const unsigned char FAR *buf;
       
   339     unsigned len;
       
   340 #endif //__SYMBIAN32__
       
   341 {
       
   342     register u4 c;
       
   343     register const u4 FAR *buf4;
       
   344 
       
   345     c = REV((u4)crc);
       
   346     c = ~c;
       
   347     while (len && ((ptrdiff_t)buf & 3)) {
       
   348         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
       
   349         len--;
       
   350     }
       
   351 
       
   352     buf4 = (const u4 FAR *)(const void FAR *)buf;
       
   353     buf4--;
       
   354     while (len >= 32) {
       
   355         DOBIG32;
       
   356         len -= 32;
       
   357     }
       
   358     while (len >= 4) {
       
   359         DOBIG4;
       
   360         len -= 4;
       
   361     }
       
   362     buf4++;
       
   363     buf = (const unsigned char FAR *)buf4;
       
   364 
       
   365     if (len) do {
       
   366         c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
       
   367     } while (--len);
       
   368     c = ~c;
       
   369     return (unsigned long)(REV(c));
       
   370 }
       
   371 
       
   372 #endif /* BYFOUR */
       
   373 
       
   374 #define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
       
   375 
       
   376 /* ========================================================================= */
       
   377 
       
   378 #ifdef __SYMBIAN32__
       
   379 local unsigned long gf2_matrix_times( unsigned long * mat,  unsigned long vec)
       
   380 #else
       
   381 local unsigned long gf2_matrix_times(mat, vec)
       
   382     unsigned long *mat;
       
   383     unsigned long vec;
       
   384 #endif //__SYMBIAN32__
       
   385 {
       
   386     unsigned long sum;
       
   387 
       
   388     sum = 0;
       
   389     while (vec) {
       
   390         if (vec & 1)
       
   391             sum ^= *mat;
       
   392         vec >>= 1;
       
   393         mat++;
       
   394     }
       
   395     return sum;
       
   396 }
       
   397 
       
   398 /* ========================================================================= */
       
   399 
       
   400 #ifdef __SYMBIAN32__
       
   401 local void gf2_matrix_square(    unsigned long * square,unsigned long * mat)
       
   402 #else
       
   403 local void gf2_matrix_square(square, mat)
       
   404     unsigned long *square;
       
   405     unsigned long *mat;
       
   406 #endif //__SYMBIAN32__	
       
   407 {
       
   408     int n;
       
   409 
       
   410     for (n = 0; n < GF2_DIM; n++)
       
   411         square[n] = gf2_matrix_times(mat, mat[n]);
       
   412 }
       
   413 
       
   414 /* ========================================================================= */
       
   415 
       
   416 
       
   417 #ifdef __SYMBIAN32__
       
   418 EXPORT_C uLong crc32_combine_r(uLong crc1,uLong  crc2,z_off_t len2)
       
   419 #else
       
   420 uLong ZEXPORT crc32_combine(crc1, crc2, len2)
       
   421     uLong crc1;
       
   422     uLong crc2;
       
   423     z_off_t len2;
       
   424 #endif //__SYMBIAN32__	
       
   425 {
       
   426     int n;
       
   427     unsigned long row;
       
   428     unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
       
   429     unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
       
   430 
       
   431     /* degenerate case */
       
   432     if (len2 == 0)
       
   433         return crc1;
       
   434 
       
   435     /* put operator for one zero bit in odd */
       
   436     odd[0] = 0xedb88320L;           /* CRC-32 polynomial */
       
   437     row = 1;
       
   438     for (n = 1; n < GF2_DIM; n++) {
       
   439         odd[n] = row;
       
   440         row <<= 1;
       
   441     }
       
   442 
       
   443     /* put operator for two zero bits in even */
       
   444     gf2_matrix_square(even, odd);
       
   445 
       
   446     /* put operator for four zero bits in odd */
       
   447     gf2_matrix_square(odd, even);
       
   448 
       
   449     /* apply len2 zeros to crc1 (first square will put the operator for one
       
   450        zero byte, eight zero bits, in even) */
       
   451     do {
       
   452         /* apply zeros operator for this bit of len2 */
       
   453         gf2_matrix_square(even, odd);
       
   454         if (len2 & 1)
       
   455             crc1 = gf2_matrix_times(even, crc1);
       
   456         len2 >>= 1;
       
   457 
       
   458         /* if no more bits set, then done */
       
   459         if (len2 == 0)
       
   460             break;
       
   461 
       
   462         /* another iteration of the loop with odd and even swapped */
       
   463         gf2_matrix_square(odd, even);
       
   464         if (len2 & 1)
       
   465             crc1 = gf2_matrix_times(odd, crc1);
       
   466         len2 >>= 1;
       
   467 
       
   468         /* if no more bits set, then done */
       
   469     } while (len2 != 0);
       
   470 
       
   471     /* return combined crc */
       
   472     crc1 ^= crc2;
       
   473     return crc1;
       
   474 }
       
   475 
       
   476