1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/zlib/crc32.c	Thu Sep 08 06:28:38 2011 +0300
     1.3 @@ -0,0 +1,423 @@
     1.4 +/* crc32.c -- compute the CRC-32 of a data stream
     1.5 + * Copyright (C) 1995-2005 Mark Adler
     1.6 + * For conditions of distribution and use, see copyright notice in zlib.h
     1.7 + *
     1.8 + * Thanks to Rodney Brown <rbrown64@csc.com.au> for his contribution of faster
     1.9 + * CRC methods: exclusive-oring 32 bits of data at a time, and pre-computing
    1.10 + * tables for updating the shift register in one step with three exclusive-ors
    1.11 + * instead of four steps with four exclusive-ors.  This results in about a
    1.12 + * factor of two increase in speed on a Power PC G4 (PPC7455) using gcc -O3.
    1.13 + */
    1.14 +
    1.15 +/* @(#) $Id$ */
    1.16 +
    1.17 +/*
    1.18 +  Note on the use of DYNAMIC_CRC_TABLE: there is no mutex or semaphore
    1.19 +  protection on the static variables used to control the first-use generation
    1.20 +  of the crc tables.  Therefore, if you #define DYNAMIC_CRC_TABLE, you should
    1.21 +  first call get_crc_table() to initialize the tables before allowing more than
    1.22 +  one thread to use crc32().
    1.23 + */
    1.24 +
    1.25 +#ifdef MAKECRCH
    1.26 +#  include <stdio.h>
    1.27 +#  ifndef DYNAMIC_CRC_TABLE
    1.28 +#    define DYNAMIC_CRC_TABLE
    1.29 +#  endif /* !DYNAMIC_CRC_TABLE */
    1.30 +#endif /* MAKECRCH */
    1.31 +
    1.32 +#include "zutil.h"      /* for STDC and FAR definitions */
    1.33 +
    1.34 +#define local static
    1.35 +
    1.36 +/* Find a four-byte integer type for crc32_little() and crc32_big(). */
    1.37 +#ifndef NOBYFOUR
    1.38 +#  ifdef STDC           /* need ANSI C limits.h to determine sizes */
    1.39 +#    include <limits.h>
    1.40 +#    define BYFOUR
    1.41 +#    if (UINT_MAX == 0xffffffffUL)
    1.42 +       typedef unsigned int u4;
    1.43 +#    else
    1.44 +#      if (ULONG_MAX == 0xffffffffUL)
    1.45 +         typedef unsigned long u4;
    1.46 +#      else
    1.47 +#        if (USHRT_MAX == 0xffffffffUL)
    1.48 +           typedef unsigned short u4;
    1.49 +#        else
    1.50 +#          undef BYFOUR     /* can't find a four-byte integer type! */
    1.51 +#        endif
    1.52 +#      endif
    1.53 +#    endif
    1.54 +#  endif /* STDC */
    1.55 +#endif /* !NOBYFOUR */
    1.56 +
    1.57 +/* Definitions for doing the crc four data bytes at a time. */
    1.58 +#ifdef BYFOUR
    1.59 +#  define REV(w) (((w)>>24)+(((w)>>8)&0xff00)+ \
    1.60 +                (((w)&0xff00)<<8)+(((w)&0xff)<<24))
    1.61 +   local unsigned long crc32_little OF((unsigned long,
    1.62 +                        const unsigned char FAR *, unsigned));
    1.63 +   local unsigned long crc32_big OF((unsigned long,
    1.64 +                        const unsigned char FAR *, unsigned));
    1.65 +#  define TBLS 8
    1.66 +#else
    1.67 +#  define TBLS 1
    1.68 +#endif /* BYFOUR */
    1.69 +
    1.70 +/* Local functions for crc concatenation */
    1.71 +local unsigned long gf2_matrix_times OF((unsigned long *mat,
    1.72 +                                         unsigned long vec));
    1.73 +local void gf2_matrix_square OF((unsigned long *square, unsigned long *mat));
    1.74 +
    1.75 +#ifdef DYNAMIC_CRC_TABLE
    1.76 +
    1.77 +local volatile int crc_table_empty = 1;
    1.78 +local unsigned long FAR crc_table[TBLS][256];
    1.79 +local void make_crc_table OF((void));
    1.80 +#ifdef MAKECRCH
    1.81 +   local void write_table OF((FILE *, const unsigned long FAR *));
    1.82 +#endif /* MAKECRCH */
    1.83 +/*
    1.84 +  Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
    1.85 +  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.
    1.86 +
    1.87 +  Polynomials over GF(2) are represented in binary, one bit per coefficient,
    1.88 +  with the lowest powers in the most significant bit.  Then adding polynomials
    1.89 +  is just exclusive-or, and multiplying a polynomial by x is a right shift by
    1.90 +  one.  If we call the above polynomial p, and represent a byte as the
    1.91 +  polynomial q, also with the lowest power in the most significant bit (so the
    1.92 +  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
    1.93 +  where a mod b means the remainder after dividing a by b.
    1.94 +
    1.95 +  This calculation is done using the shift-register method of multiplying and
    1.96 +  taking the remainder.  The register is initialized to zero, and for each
    1.97 +  incoming bit, x^32 is added mod p to the register if the bit is a one (where
    1.98 +  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
    1.99 +  x (which is shifting right by one and adding x^32 mod p if the bit shifted
   1.100 +  out is a one).  We start with the highest power (least significant bit) of
   1.101 +  q and repeat for all eight bits of q.
   1.102 +
   1.103 +  The first table is simply the CRC of all possible eight bit values.  This is
   1.104 +  all the information needed to generate CRCs on data a byte at a time for all
   1.105 +  combinations of CRC register values and incoming bytes.  The remaining tables
   1.106 +  allow for word-at-a-time CRC calculation for both big-endian and little-
   1.107 +  endian machines, where a word is four bytes.
   1.108 +*/
   1.109 +local void make_crc_table()
   1.110 +{
   1.111 +    unsigned long c;
   1.112 +    int n, k;
   1.113 +    unsigned long poly;                 /* polynomial exclusive-or pattern */
   1.114 +    /* terms of polynomial defining this crc (except x^32): */
   1.115 +    static volatile int first = 1;      /* flag to limit concurrent making */
   1.116 +    static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
   1.117 +
   1.118 +    /* See if another task is already doing this (not thread-safe, but better
   1.119 +       than nothing -- significantly reduces duration of vulnerability in
   1.120 +       case the advice about DYNAMIC_CRC_TABLE is ignored) */
   1.121 +    if (first) {
   1.122 +        first = 0;
   1.123 +
   1.124 +        /* make exclusive-or pattern from polynomial (0xedb88320UL) */
   1.125 +        poly = 0UL;
   1.126 +        for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
   1.127 +            poly |= 1UL << (31 - p[n]);
   1.128 +
   1.129 +        /* generate a crc for every 8-bit value */
   1.130 +        for (n = 0; n < 256; n++) {
   1.131 +            c = (unsigned long)n;
   1.132 +            for (k = 0; k < 8; k++)
   1.133 +                c = c & 1 ? poly ^ (c >> 1) : c >> 1;
   1.134 +            crc_table[0][n] = c;
   1.135 +        }
   1.136 +
   1.137 +#ifdef BYFOUR
   1.138 +        /* generate crc for each value followed by one, two, and three zeros,
   1.139 +           and then the byte reversal of those as well as the first table */
   1.140 +        for (n = 0; n < 256; n++) {
   1.141 +            c = crc_table[0][n];
   1.142 +            crc_table[4][n] = REV(c);
   1.143 +            for (k = 1; k < 4; k++) {
   1.144 +                c = crc_table[0][c & 0xff] ^ (c >> 8);
   1.145 +                crc_table[k][n] = c;
   1.146 +                crc_table[k + 4][n] = REV(c);
   1.147 +            }
   1.148 +        }
   1.149 +#endif /* BYFOUR */
   1.150 +
   1.151 +        crc_table_empty = 0;
   1.152 +    }
   1.153 +    else {      /* not first */
   1.154 +        /* wait for the other guy to finish (not efficient, but rare) */
   1.155 +        while (crc_table_empty)
   1.156 +            ;
   1.157 +    }
   1.158 +
   1.159 +#ifdef MAKECRCH
   1.160 +    /* write out CRC tables to crc32.h */
   1.161 +    {
   1.162 +        FILE *out;
   1.163 +
   1.164 +        out = fopen("crc32.h", "w");
   1.165 +        if (out == NULL) return;
   1.166 +        fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
   1.167 +        fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
   1.168 +        fprintf(out, "local const unsigned long FAR ");
   1.169 +        fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
   1.170 +        write_table(out, crc_table[0]);
   1.171 +#  ifdef BYFOUR
   1.172 +        fprintf(out, "#ifdef BYFOUR\n");
   1.173 +        for (k = 1; k < 8; k++) {
   1.174 +            fprintf(out, "  },\n  {\n");
   1.175 +            write_table(out, crc_table[k]);
   1.176 +        }
   1.177 +        fprintf(out, "#endif\n");
   1.178 +#  endif /* BYFOUR */
   1.179 +        fprintf(out, "  }\n};\n");
   1.180 +        fclose(out);
   1.181 +    }
   1.182 +#endif /* MAKECRCH */
   1.183 +}
   1.184 +
   1.185 +#ifdef MAKECRCH
   1.186 +local void write_table(out, table)
   1.187 +    FILE *out;
   1.188 +    const unsigned long FAR *table;
   1.189 +{
   1.190 +    int n;
   1.191 +
   1.192 +    for (n = 0; n < 256; n++)
   1.193 +        fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
   1.194 +                n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
   1.195 +}
   1.196 +#endif /* MAKECRCH */
   1.197 +
   1.198 +#else /* !DYNAMIC_CRC_TABLE */
   1.199 +/* ========================================================================
   1.200 + * Tables of CRC-32s of all single-byte values, made by make_crc_table().
   1.201 + */
   1.202 +#include "crc32.h"
   1.203 +#endif /* DYNAMIC_CRC_TABLE */
   1.204 +
   1.205 +/* =========================================================================
   1.206 + * This function can be used by asm versions of crc32()
   1.207 + */
   1.208 +const unsigned long FAR * ZEXPORT get_crc_table()
   1.209 +{
   1.210 +#ifdef DYNAMIC_CRC_TABLE
   1.211 +    if (crc_table_empty)
   1.212 +        make_crc_table();
   1.213 +#endif /* DYNAMIC_CRC_TABLE */
   1.214 +    return (const unsigned long FAR *)crc_table;
   1.215 +}
   1.216 +
   1.217 +/* ========================================================================= */
   1.218 +#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
   1.219 +#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
   1.220 +
   1.221 +/* ========================================================================= */
   1.222 +unsigned long ZEXPORT crc32(crc, buf, len)
   1.223 +    unsigned long crc;
   1.224 +    const unsigned char FAR *buf;
   1.225 +    unsigned len;
   1.226 +{
   1.227 +    if (buf == Z_NULL) return 0UL;
   1.228 +
   1.229 +#ifdef DYNAMIC_CRC_TABLE
   1.230 +    if (crc_table_empty)
   1.231 +        make_crc_table();
   1.232 +#endif /* DYNAMIC_CRC_TABLE */
   1.233 +
   1.234 +#ifdef BYFOUR
   1.235 +    if (sizeof(void *) == sizeof(ptrdiff_t)) {
   1.236 +        u4 endian;
   1.237 +
   1.238 +        endian = 1;
   1.239 +        if (*((unsigned char *)(&endian)))
   1.240 +            return crc32_little(crc, buf, len);
   1.241 +        else
   1.242 +            return crc32_big(crc, buf, len);
   1.243 +    }
   1.244 +#endif /* BYFOUR */
   1.245 +    crc = crc ^ 0xffffffffUL;
   1.246 +    while (len >= 8) {
   1.247 +        DO8;
   1.248 +        len -= 8;
   1.249 +    }
   1.250 +    if (len) do {
   1.251 +        DO1;
   1.252 +    } while (--len);
   1.253 +    return crc ^ 0xffffffffUL;
   1.254 +}
   1.255 +
   1.256 +#ifdef BYFOUR
   1.257 +
   1.258 +/* ========================================================================= */
   1.259 +#define DOLIT4 c ^= *buf4++; \
   1.260 +        c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
   1.261 +            crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
   1.262 +#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
   1.263 +
   1.264 +/* ========================================================================= */
   1.265 +local unsigned long crc32_little(crc, buf, len)
   1.266 +    unsigned long crc;
   1.267 +    const unsigned char FAR *buf;
   1.268 +    unsigned len;
   1.269 +{
   1.270 +    register u4 c;
   1.271 +    register const u4 FAR *buf4;
   1.272 +
   1.273 +    c = (u4)crc;
   1.274 +    c = ~c;
   1.275 +    while (len && ((ptrdiff_t)buf & 3)) {
   1.276 +        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
   1.277 +        len--;
   1.278 +    }
   1.279 +
   1.280 +    buf4 = (const u4 FAR *)(const void FAR *)buf;
   1.281 +    while (len >= 32) {
   1.282 +        DOLIT32;
   1.283 +        len -= 32;
   1.284 +    }
   1.285 +    while (len >= 4) {
   1.286 +        DOLIT4;
   1.287 +        len -= 4;
   1.288 +    }
   1.289 +    buf = (const unsigned char FAR *)buf4;
   1.290 +
   1.291 +    if (len) do {
   1.292 +        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
   1.293 +    } while (--len);
   1.294 +    c = ~c;
   1.295 +    return (unsigned long)c;
   1.296 +}
   1.297 +
   1.298 +/* ========================================================================= */
   1.299 +#define DOBIG4 c ^= *++buf4; \
   1.300 +        c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
   1.301 +            crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
   1.302 +#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
   1.303 +
   1.304 +/* ========================================================================= */
   1.305 +local unsigned long crc32_big(crc, buf, len)
   1.306 +    unsigned long crc;
   1.307 +    const unsigned char FAR *buf;
   1.308 +    unsigned len;
   1.309 +{
   1.310 +    register u4 c;
   1.311 +    register const u4 FAR *buf4;
   1.312 +
   1.313 +    c = REV((u4)crc);
   1.314 +    c = ~c;
   1.315 +    while (len && ((ptrdiff_t)buf & 3)) {
   1.316 +        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
   1.317 +        len--;
   1.318 +    }
   1.319 +
   1.320 +    buf4 = (const u4 FAR *)(const void FAR *)buf;
   1.321 +    buf4--;
   1.322 +    while (len >= 32) {
   1.323 +        DOBIG32;
   1.324 +        len -= 32;
   1.325 +    }
   1.326 +    while (len >= 4) {
   1.327 +        DOBIG4;
   1.328 +        len -= 4;
   1.329 +    }
   1.330 +    buf4++;
   1.331 +    buf = (const unsigned char FAR *)buf4;
   1.332 +
   1.333 +    if (len) do {
   1.334 +        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
   1.335 +    } while (--len);
   1.336 +    c = ~c;
   1.337 +    return (unsigned long)(REV(c));
   1.338 +}
   1.339 +
   1.340 +#endif /* BYFOUR */
   1.341 +
   1.342 +#define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
   1.343 +
   1.344 +/* ========================================================================= */
   1.345 +local unsigned long gf2_matrix_times(mat, vec)
   1.346 +    unsigned long *mat;
   1.347 +    unsigned long vec;
   1.348 +{
   1.349 +    unsigned long sum;
   1.350 +
   1.351 +    sum = 0;
   1.352 +    while (vec) {
   1.353 +        if (vec & 1)
   1.354 +            sum ^= *mat;
   1.355 +        vec >>= 1;
   1.356 +        mat++;
   1.357 +    }
   1.358 +    return sum;
   1.359 +}
   1.360 +
   1.361 +/* ========================================================================= */
   1.362 +local void gf2_matrix_square(square, mat)
   1.363 +    unsigned long *square;
   1.364 +    unsigned long *mat;
   1.365 +{
   1.366 +    int n;
   1.367 +
   1.368 +    for (n = 0; n < GF2_DIM; n++)
   1.369 +        square[n] = gf2_matrix_times(mat, mat[n]);
   1.370 +}
   1.371 +
   1.372 +/* ========================================================================= */
   1.373 +uLong ZEXPORT crc32_combine(crc1, crc2, len2)
   1.374 +    uLong crc1;
   1.375 +    uLong crc2;
   1.376 +    z_off_t len2;
   1.377 +{
   1.378 +    int n;
   1.379 +    unsigned long row;
   1.380 +    unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
   1.381 +    unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
   1.382 +
   1.383 +    /* degenerate case */
   1.384 +    if (len2 == 0)
   1.385 +        return crc1;
   1.386 +
   1.387 +    /* put operator for one zero bit in odd */
   1.388 +    odd[0] = 0xedb88320L;           /* CRC-32 polynomial */
   1.389 +    row = 1;
   1.390 +    for (n = 1; n < GF2_DIM; n++) {
   1.391 +        odd[n] = row;
   1.392 +        row <<= 1;
   1.393 +    }
   1.394 +
   1.395 +    /* put operator for two zero bits in even */
   1.396 +    gf2_matrix_square(even, odd);
   1.397 +
   1.398 +    /* put operator for four zero bits in odd */
   1.399 +    gf2_matrix_square(odd, even);
   1.400 +
   1.401 +    /* apply len2 zeros to crc1 (first square will put the operator for one
   1.402 +       zero byte, eight zero bits, in even) */
   1.403 +    do {
   1.404 +        /* apply zeros operator for this bit of len2 */
   1.405 +        gf2_matrix_square(even, odd);
   1.406 +        if (len2 & 1)
   1.407 +            crc1 = gf2_matrix_times(even, crc1);
   1.408 +        len2 >>= 1;
   1.409 +
   1.410 +        /* if no more bits set, then done */
   1.411 +        if (len2 == 0)
   1.412 +            break;
   1.413 +
   1.414 +        /* another iteration of the loop with odd and even swapped */
   1.415 +        gf2_matrix_square(odd, even);
   1.416 +        if (len2 & 1)
   1.417 +            crc1 = gf2_matrix_times(odd, crc1);
   1.418 +        len2 >>= 1;
   1.419 +
   1.420 +        /* if no more bits set, then done */
   1.421 +    } while (len2 != 0);
   1.422 +
   1.423 +    /* return combined crc */
   1.424 +    crc1 ^= crc2;
   1.425 +    return crc1;
   1.426 +}