1 /* Portions Copyright (c) 2007-2009 Nokia Corporation and/or its subsidiary(-ies).

     2  * All rights reserved.

     3  */

     4 

     5 /* crc32.cpp -- compute the CRC-32 of a data stream

     6  * Copyright (C) 1995-2005 Mark Adler

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

     8  *

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

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

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

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

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

    14  */

    15 

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

    17 

    18 /*

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

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

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

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

    23   one thread to use crc32().

    24  */

    25 

    26 #ifdef MAKECRCH

    27 #  include <stdio.h>

    28 #  ifndef DYNAMIC_CRC_TABLE

    29 #    define DYNAMIC_CRC_TABLE

    30 #  endif /* !DYNAMIC_CRC_TABLE */

    31 #endif /* MAKECRCH */

    32 

    33 /* These defines are usually taken from limits.h, however this file is not supported in Symbian. */

    34 #if (defined(__SYMBIAN32__) && !defined(__TOOLS2__) && !defined(__TOOLS__))  

    35   #define UINT_MAX  0xffffffffU  /* Values taken from _limits.h:from PIPS  */

    36   #define ULONG_MAX 0xffffffffUL /* Removing may slow down the crc operation */

    37   typedef int ptrdiff_t;

    38 #endif /* __SYMBIAN32__ && !__TOOLS2__) && !__TOOLS__ */

    39 

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

    41 

    42 

    43 /* Find a four-byte integer type for crc32_little() and crc32_big(). */

    44 #ifndef NOBYFOUR

    45 #  ifdef STDC           /* need ANSI C limits.h to determine sizes */

    46 #  	 if (!defined(__SYMBIAN32__) || defined(__TOOLS2__) || defined(__TOOLS__)) /* only include for Tools builds */

    47 #      include <limits.h>

    48 #    endif /* !__SYMBIAN32__ || __TOOLS2__) || __TOOLS__ */

    49 #    define BYFOUR

    50 #    if (UINT_MAX == 0xffffffffUL)

    51 	   typedef unsigned int u4;

    52 #    else

    53 #      if (ULONG_MAX == 0xffffffffUL)

    54          typedef unsigned long u4;

    55 #      else

    56 #        if (USHRT_MAX == 0xffffffffUL)

    57            typedef unsigned short u4;

    58 #        else

    59 #          undef BYFOUR     /* can't find a four-byte integer type! */

    60 #        endif

    61 #      endif

    62 #    endif

    63 #  endif /* STDC */

    64 #endif /* !NOBYFOUR */

    65 

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

    67 #ifdef BYFOUR

    68 #  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \

    69                 (((w)&0xff00)<<8)+(((w)&0xff)<<24))

    70    local unsigned long crc32_little OF((unsigned long,

    71                         const unsigned char FAR *, unsigned));

    72    local unsigned long crc32_big OF((unsigned long,

    73                         const unsigned char FAR *, unsigned));

    74 #  define TBLS 8

    75 #else

    76 #  define TBLS 1

    77 #endif /* BYFOUR */

    78 

    79 /* Local functions for crc concatenation */

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

    81                                          unsigned long vec));

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

    83 

    84 #ifdef DYNAMIC_CRC_TABLE

    85 

    86 local volatile int crc_table_empty = 1;

    87 local unsigned long FAR crc_table[TBLS][256];

    88 local void make_crc_table OF((void));

    89 #ifdef MAKECRCH

    90    local void write_table OF((FILE *, const unsigned long FAR *));

    91 #endif /* MAKECRCH */

    92 /*

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

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

    95 

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

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

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

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

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

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

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

   103 

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

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

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

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

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

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

   110   q and repeat for all eight bits of q.

   111 

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

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

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

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

   116   endian machines, where a word is four bytes.

   117 */

   118 local void make_crc_table()

   119 {

   120     unsigned long c;

   121     int n, k;

   122     unsigned long poly;                 /* polynomial exclusive-or pattern */

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

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

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

   126 

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

   128        than nothing -- significantly reduces duration of vulnerability in

   129        case the advice about DYNAMIC_CRC_TABLE is ignored) */

   130     if (first) {

   131         first = 0;

   132 

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

   134         poly = 0UL;

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

   136             poly |= 1UL << (31 - p[n]);

   137 

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

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

   140             c = (unsigned long)n;

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

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

   143             crc_table[0][n] = c;

   144         }

   145 

   146 #ifdef BYFOUR

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

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

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

   150             c = crc_table[0][n];

   151             crc_table[4][n] = REV(c);

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

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

   154                 crc_table[k][n] = c;

   155                 crc_table[k + 4][n] = REV(c);

   156             }

   157         }

   158 #endif /* BYFOUR */

   159 

   160         crc_table_empty = 0;

   161     }

   162     else {      /* not first */

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

   164         while (crc_table_empty)

   165             ;

   166     }

   167 

   168 #ifdef MAKECRCH

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

   170     {

   171         FILE *out;

   172 

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

   174         if (out == NULL) return;

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

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

   177         fprintf(out, "local const unsigned long FAR ");

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

   179         write_table(out, crc_table[0]);

   180 #  ifdef BYFOUR

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

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

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

   184             write_table(out, crc_table[k]);

   185         }

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

   187 #  endif /* BYFOUR */

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

   189         fclose(out);

   190     }

   191 #endif /* MAKECRCH */

   192 }

   193 

   194 #ifdef MAKECRCH

   195 #ifdef __SYMBIAN32__

   196 local void write_table(FILE * out, const unsigned long FAR * table)

   197 #else	

   198 local void write_table(out, table)

   199     FILE *out;

   200     const unsigned long FAR *table;

   201 #endif //__SYMBIAN32__

   202 {

   203     int n;

   204 

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

   206         fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],

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

   208 }

   209 #endif /* MAKECRCH */

   210 

   211 #else /* !DYNAMIC_CRC_TABLE */

   212 /* ========================================================================

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

   214  */

   215 #include "crc32.h"

   216 #endif /* DYNAMIC_CRC_TABLE */

   217 

   218 /* =========================================================================

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

   220  */

   221 #ifdef __SYMBIAN32__

   222 EXPORT_C  const unsigned long FAR *   get_crc_table_r()

   223 #else

   224 const unsigned long FAR * ZEXPORT get_crc_table()

   225 #endif //__SYMBIAN32__

   226 {

   227 #ifdef DYNAMIC_CRC_TABLE

   228     if (crc_table_empty)

   229         make_crc_table();

   230 #endif /* DYNAMIC_CRC_TABLE */

   231     return (const unsigned long FAR *)crc_table;

   232 }

   233 

   234 /* ========================================================================= */

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

   236 #define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1

   237 

   238 /* ========================================================================= */

   239 

   240 #ifdef __SYMBIAN32__

   241 EXPORT_C unsigned long  crc32_r( unsigned long crc,  const unsigned char FAR *  buf,unsigned len)

   242 #else

   243 unsigned long ZEXPORT crc32(crc, buf, len)

   244     unsigned long crc;

   245     const unsigned char FAR *buf;

   246     unsigned len;

   247 #endif //__SYMBIAN32__

   248 {

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

   250 

   251 #ifdef DYNAMIC_CRC_TABLE

   252     if (crc_table_empty)

   253         make_crc_table();

   254 #endif /* DYNAMIC_CRC_TABLE */

   255 

   256 #ifdef BYFOUR

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

   258         u4 endian;

   259 

   260         endian = 1;

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

   262             return crc32_little(crc, buf, len);

   263         else

   264             return crc32_big(crc, buf, len);

   265     }

   266     else 

   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  #ifdef BYFOUR

   279     }

   280  #endif    

   281 }

   282 

   283 

   284 #ifdef BYFOUR

   285 

   286 /* ========================================================================= */

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

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

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

   290 #define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4

   291 

   292 /* ========================================================================= */

   293 #ifdef __SYMBIAN32__

   294 local unsigned long crc32_little(   unsigned long  crc,const unsigned char FAR *  buf,unsigned len)

   295 #else

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

   297     unsigned long crc;

   298     const unsigned char FAR *buf;

   299     unsigned len;

   300 #endif //__SYMBIAN32__

   301 {

   302     register u4 c;

   303     register const u4 FAR *buf4;

   304 

   305     c = (u4)crc;

   306     c = ~c;

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

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

   309         len--;

   310     }

   311 

   312     buf4 = (const u4 FAR *)(const void FAR *)buf;

   313     while (len >= 32) {

   314         DOLIT32;

   315         len -= 32;

   316     }

   317     while (len >= 4) {

   318         DOLIT4;

   319         len -= 4;

   320     }

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

   322 

   323     if (len) do {

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

   325     } while (--len);

   326     c = ~c;

   327     return (unsigned long)c;

   328 }

   329 

   330 /* ========================================================================= */

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

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

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

   334 #define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4

   335 

   336 /* ========================================================================= */

   337 #ifdef __SYMBIAN32__

   338 local unsigned long crc32_big(    unsigned long crc,    const unsigned char FAR *  buf,unsigned  len)

   339 #else

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

   341     unsigned long crc;

   342     const unsigned char FAR *buf;

   343     unsigned len;

   344 #endif //__SYMBIAN32__

   345 {

   346     register u4 c;

   347     register const u4 FAR *buf4;

   348 

   349     c = REV((u4)crc);

   350     c = ~c;

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

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

   353         len--;

   354     }

   355 

   356     buf4 = (const u4 FAR *)(const void FAR *)buf;

   357     buf4--;

   358     while (len >= 32) {

   359         DOBIG32;

   360         len -= 32;

   361     }

   362     while (len >= 4) {

   363         DOBIG4;

   364         len -= 4;

   365     }

   366     buf4++;

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

   368 

   369     if (len) do {

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

   371     } while (--len);

   372     c = ~c;

   373     return (unsigned long)(REV(c));

   374 }

   375 

   376 #endif /* BYFOUR */

   377 

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

   379 

   380 /* ========================================================================= */

   381 

   382 #ifdef __SYMBIAN32__

   383 local unsigned long gf2_matrix_times( unsigned long * mat,  unsigned long vec)

   384 #else

   385 local unsigned long gf2_matrix_times(mat, vec)

   386     unsigned long *mat;

   387     unsigned long vec;

   388 #endif //__SYMBIAN32__

   389 {

   390     unsigned long sum;

   391 

   392     sum = 0;

   393     while (vec) {

   394         if (vec & 1)

   395             sum ^= *mat;

   396         vec >>= 1;

   397         mat++;

   398     }

   399     return sum;

   400 }

   401 

   402 /* ========================================================================= */

   403 

   404 #ifdef __SYMBIAN32__

   405 local void gf2_matrix_square(    unsigned long * square,unsigned long * mat)

   406 #else

   407 local void gf2_matrix_square(square, mat)

   408     unsigned long *square;

   409     unsigned long *mat;

   410 #endif //__SYMBIAN32__	

   411 {

   412     int n;

   413 

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

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

   416 }

   417 

   418 /* ========================================================================= */

   419 

   420 

   421 #ifdef __SYMBIAN32__

   422 EXPORT_C uLong crc32_combine_r(uLong crc1,uLong  crc2,z_off_t len2)

   423 #else

   424 uLong ZEXPORT crc32_combine(crc1, crc2, len2)

   425     uLong crc1;

   426     uLong crc2;

   427     z_off_t len2;

   428 #endif //__SYMBIAN32__	

   429 {

   430     int n;

   431     unsigned long row;

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

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

   434 

   435     /* degenerate case */

   436     if (len2 == 0)

   437         return crc1;

   438 

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

   440     odd[0] = 0xedb88320L;           /* CRC-32 polynomial */

   441     row = 1;

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

   443         odd[n] = row;

   444         row <<= 1;

   445     }

   446 

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

   448     gf2_matrix_square(even, odd);

   449 

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

   451     gf2_matrix_square(odd, even);

   452 

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

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

   455     do {

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

   457         gf2_matrix_square(even, odd);

   458         if (len2 & 1)

   459             crc1 = gf2_matrix_times(even, crc1);

   460         len2 >>= 1;

   461 

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

   463         if (len2 == 0)

   464             break;

   465 

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

   467         gf2_matrix_square(odd, even);

   468         if (len2 & 1)

   469             crc1 = gf2_matrix_times(odd, crc1);

   470         len2 >>= 1;

   471 

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

   473     } while (len2 != 0);

   474 

   475     /* return combined crc */

   476     crc1 ^= crc2;

   477     return crc1;

   478 }

   479 

   480