1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/src/zlib/crc32.c	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,442 @@
     1.4 +/* crc32.c -- compute the CRC-32 of a data stream
     1.5 + * Copyright (C) 1995-2006, 2010 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)&0xff)+(((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 +local uLong crc32_combine_(uLong crc1, uLong crc2, z_off64_t len2);
    1.75 +
    1.76 +
    1.77 +#ifdef DYNAMIC_CRC_TABLE
    1.78 +
    1.79 +local volatile int crc_table_empty = 1;
    1.80 +local unsigned long FAR crc_table[TBLS][256];
    1.81 +local void make_crc_table OF((void));
    1.82 +#ifdef MAKECRCH
    1.83 +   local void write_table OF((FILE *, const unsigned long FAR *));
    1.84 +#endif /* MAKECRCH */
    1.85 +/*
    1.86 +  Generate tables for a byte-wise 32-bit CRC calculation on the polynomial:
    1.87 +  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.88 +
    1.89 +  Polynomials over GF(2) are represented in binary, one bit per coefficient,
    1.90 +  with the lowest powers in the most significant bit.  Then adding polynomials
    1.91 +  is just exclusive-or, and multiplying a polynomial by x is a right shift by
    1.92 +  one.  If we call the above polynomial p, and represent a byte as the
    1.93 +  polynomial q, also with the lowest power in the most significant bit (so the
    1.94 +  byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p,
    1.95 +  where a mod b means the remainder after dividing a by b.
    1.96 +
    1.97 +  This calculation is done using the shift-register method of multiplying and
    1.98 +  taking the remainder.  The register is initialized to zero, and for each
    1.99 +  incoming bit, x^32 is added mod p to the register if the bit is a one (where
   1.100 +  x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by
   1.101 +  x (which is shifting right by one and adding x^32 mod p if the bit shifted
   1.102 +  out is a one).  We start with the highest power (least significant bit) of
   1.103 +  q and repeat for all eight bits of q.
   1.104 +
   1.105 +  The first table is simply the CRC of all possible eight bit values.  This is
   1.106 +  all the information needed to generate CRCs on data a byte at a time for all
   1.107 +  combinations of CRC register values and incoming bytes.  The remaining tables
   1.108 +  allow for word-at-a-time CRC calculation for both big-endian and little-
   1.109 +  endian machines, where a word is four bytes.
   1.110 +*/
   1.111 +local void make_crc_table()
   1.112 +{
   1.113 +    unsigned long c;
   1.114 +    int n, k;
   1.115 +    unsigned long poly;                 /* polynomial exclusive-or pattern */
   1.116 +    /* terms of polynomial defining this crc (except x^32): */
   1.117 +    static volatile int first = 1;      /* flag to limit concurrent making */
   1.118 +    static const unsigned char p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
   1.119 +
   1.120 +    /* See if another task is already doing this (not thread-safe, but better
   1.121 +       than nothing -- significantly reduces duration of vulnerability in
   1.122 +       case the advice about DYNAMIC_CRC_TABLE is ignored) */
   1.123 +    if (first) {
   1.124 +        first = 0;
   1.125 +
   1.126 +        /* make exclusive-or pattern from polynomial (0xedb88320UL) */
   1.127 +        poly = 0UL;
   1.128 +        for (n = 0; n < sizeof(p)/sizeof(unsigned char); n++)
   1.129 +            poly |= 1UL << (31 - p[n]);
   1.130 +
   1.131 +        /* generate a crc for every 8-bit value */
   1.132 +        for (n = 0; n < 256; n++) {
   1.133 +            c = (unsigned long)n;
   1.134 +            for (k = 0; k < 8; k++)
   1.135 +                c = c & 1 ? poly ^ (c >> 1) : c >> 1;
   1.136 +            crc_table[0][n] = c;
   1.137 +        }
   1.138 +
   1.139 +#ifdef BYFOUR
   1.140 +        /* generate crc for each value followed by one, two, and three zeros,
   1.141 +           and then the byte reversal of those as well as the first table */
   1.142 +        for (n = 0; n < 256; n++) {
   1.143 +            c = crc_table[0][n];
   1.144 +            crc_table[4][n] = REV(c);
   1.145 +            for (k = 1; k < 4; k++) {
   1.146 +                c = crc_table[0][c & 0xff] ^ (c >> 8);
   1.147 +                crc_table[k][n] = c;
   1.148 +                crc_table[k + 4][n] = REV(c);
   1.149 +            }
   1.150 +        }
   1.151 +#endif /* BYFOUR */
   1.152 +
   1.153 +        crc_table_empty = 0;
   1.154 +    }
   1.155 +    else {      /* not first */
   1.156 +        /* wait for the other guy to finish (not efficient, but rare) */
   1.157 +        while (crc_table_empty)
   1.158 +            ;
   1.159 +    }
   1.160 +
   1.161 +#ifdef MAKECRCH
   1.162 +    /* write out CRC tables to crc32.h */
   1.163 +    {
   1.164 +        FILE *out;
   1.165 +
   1.166 +        out = fopen("crc32.h", "w");
   1.167 +        if (out == NULL) return;
   1.168 +        fprintf(out, "/* crc32.h -- tables for rapid CRC calculation\n");
   1.169 +        fprintf(out, " * Generated automatically by crc32.c\n */\n\n");
   1.170 +        fprintf(out, "local const unsigned long FAR ");
   1.171 +        fprintf(out, "crc_table[TBLS][256] =\n{\n  {\n");
   1.172 +        write_table(out, crc_table[0]);
   1.173 +#  ifdef BYFOUR
   1.174 +        fprintf(out, "#ifdef BYFOUR\n");
   1.175 +        for (k = 1; k < 8; k++) {
   1.176 +            fprintf(out, "  },\n  {\n");
   1.177 +            write_table(out, crc_table[k]);
   1.178 +        }
   1.179 +        fprintf(out, "#endif\n");
   1.180 +#  endif /* BYFOUR */
   1.181 +        fprintf(out, "  }\n};\n");
   1.182 +        fclose(out);
   1.183 +    }
   1.184 +#endif /* MAKECRCH */
   1.185 +}
   1.186 +
   1.187 +#ifdef MAKECRCH
   1.188 +local void write_table(out, table)
   1.189 +    FILE *out;
   1.190 +    const unsigned long FAR *table;
   1.191 +{
   1.192 +    int n;
   1.193 +
   1.194 +    for (n = 0; n < 256; n++)
   1.195 +        fprintf(out, "%s0x%08lxUL%s", n % 5 ? "" : "    ", table[n],
   1.196 +                n == 255 ? "\n" : (n % 5 == 4 ? ",\n" : ", "));
   1.197 +}
   1.198 +#endif /* MAKECRCH */
   1.199 +
   1.200 +#else /* !DYNAMIC_CRC_TABLE */
   1.201 +/* ========================================================================
   1.202 + * Tables of CRC-32s of all single-byte values, made by make_crc_table().
   1.203 + */
   1.204 +#include "crc32.h"
   1.205 +#endif /* DYNAMIC_CRC_TABLE */
   1.206 +
   1.207 +/* =========================================================================
   1.208 + * This function can be used by asm versions of crc32()
   1.209 + */
   1.210 +const unsigned long FAR * ZEXPORT get_crc_table()
   1.211 +{
   1.212 +#ifdef DYNAMIC_CRC_TABLE
   1.213 +    if (crc_table_empty)
   1.214 +        make_crc_table();
   1.215 +#endif /* DYNAMIC_CRC_TABLE */
   1.216 +    return (const unsigned long FAR *)crc_table;
   1.217 +}
   1.218 +
   1.219 +/* ========================================================================= */
   1.220 +#define DO1 crc = crc_table[0][((int)crc ^ (*buf++)) & 0xff] ^ (crc >> 8)
   1.221 +#define DO8 DO1; DO1; DO1; DO1; DO1; DO1; DO1; DO1
   1.222 +
   1.223 +/* ========================================================================= */
   1.224 +unsigned long ZEXPORT crc32(crc, buf, len)
   1.225 +    unsigned long crc;
   1.226 +    const unsigned char FAR *buf;
   1.227 +    uInt len;
   1.228 +{
   1.229 +    if (buf == Z_NULL) return 0UL;
   1.230 +
   1.231 +#ifdef DYNAMIC_CRC_TABLE
   1.232 +    if (crc_table_empty)
   1.233 +        make_crc_table();
   1.234 +#endif /* DYNAMIC_CRC_TABLE */
   1.235 +
   1.236 +#ifdef BYFOUR
   1.237 +    if (sizeof(void *) == sizeof(ptrdiff_t)) {
   1.238 +        u4 endian;
   1.239 +
   1.240 +        endian = 1;
   1.241 +        if (*((unsigned char *)(&endian)))
   1.242 +            return crc32_little(crc, buf, len);
   1.243 +        else
   1.244 +            return crc32_big(crc, buf, len);
   1.245 +    }
   1.246 +#endif /* BYFOUR */
   1.247 +    crc = crc ^ 0xffffffffUL;
   1.248 +    while (len >= 8) {
   1.249 +        DO8;
   1.250 +        len -= 8;
   1.251 +    }
   1.252 +    if (len) do {
   1.253 +        DO1;
   1.254 +    } while (--len);
   1.255 +    return crc ^ 0xffffffffUL;
   1.256 +}
   1.257 +
   1.258 +#ifdef BYFOUR
   1.259 +
   1.260 +/* ========================================================================= */
   1.261 +#define DOLIT4 c ^= *buf4++; \
   1.262 +        c = crc_table[3][c & 0xff] ^ crc_table[2][(c >> 8) & 0xff] ^ \
   1.263 +            crc_table[1][(c >> 16) & 0xff] ^ crc_table[0][c >> 24]
   1.264 +#define DOLIT32 DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4; DOLIT4
   1.265 +
   1.266 +/* ========================================================================= */
   1.267 +local unsigned long crc32_little(crc, buf, len)
   1.268 +    unsigned long crc;
   1.269 +    const unsigned char FAR *buf;
   1.270 +    unsigned len;
   1.271 +{
   1.272 +    register u4 c;
   1.273 +    register const u4 FAR *buf4;
   1.274 +
   1.275 +    c = (u4)crc;
   1.276 +    c = ~c;
   1.277 +    while (len && ((ptrdiff_t)buf & 3)) {
   1.278 +        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
   1.279 +        len--;
   1.280 +    }
   1.281 +
   1.282 +    buf4 = (const u4 FAR *)(const void FAR *)buf;
   1.283 +    while (len >= 32) {
   1.284 +        DOLIT32;
   1.285 +        len -= 32;
   1.286 +    }
   1.287 +    while (len >= 4) {
   1.288 +        DOLIT4;
   1.289 +        len -= 4;
   1.290 +    }
   1.291 +    buf = (const unsigned char FAR *)buf4;
   1.292 +
   1.293 +    if (len) do {
   1.294 +        c = crc_table[0][(c ^ *buf++) & 0xff] ^ (c >> 8);
   1.295 +    } while (--len);
   1.296 +    c = ~c;
   1.297 +    return (unsigned long)c;
   1.298 +}
   1.299 +
   1.300 +/* ========================================================================= */
   1.301 +#define DOBIG4 c ^= *++buf4; \
   1.302 +        c = crc_table[4][c & 0xff] ^ crc_table[5][(c >> 8) & 0xff] ^ \
   1.303 +            crc_table[6][(c >> 16) & 0xff] ^ crc_table[7][c >> 24]
   1.304 +#define DOBIG32 DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4; DOBIG4
   1.305 +
   1.306 +/* ========================================================================= */
   1.307 +local unsigned long crc32_big(crc, buf, len)
   1.308 +    unsigned long crc;
   1.309 +    const unsigned char FAR *buf;
   1.310 +    unsigned len;
   1.311 +{
   1.312 +    register u4 c;
   1.313 +    register const u4 FAR *buf4;
   1.314 +
   1.315 +    c = REV((u4)crc);
   1.316 +    c = ~c;
   1.317 +    while (len && ((ptrdiff_t)buf & 3)) {
   1.318 +        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
   1.319 +        len--;
   1.320 +    }
   1.321 +
   1.322 +    buf4 = (const u4 FAR *)(const void FAR *)buf;
   1.323 +    buf4--;
   1.324 +    while (len >= 32) {
   1.325 +        DOBIG32;
   1.326 +        len -= 32;
   1.327 +    }
   1.328 +    while (len >= 4) {
   1.329 +        DOBIG4;
   1.330 +        len -= 4;
   1.331 +    }
   1.332 +    buf4++;
   1.333 +    buf = (const unsigned char FAR *)buf4;
   1.334 +
   1.335 +    if (len) do {
   1.336 +        c = crc_table[4][(c >> 24) ^ *buf++] ^ (c << 8);
   1.337 +    } while (--len);
   1.338 +    c = ~c;
   1.339 +    return (unsigned long)(REV(c));
   1.340 +}
   1.341 +
   1.342 +#endif /* BYFOUR */
   1.343 +
   1.344 +#define GF2_DIM 32      /* dimension of GF(2) vectors (length of CRC) */
   1.345 +
   1.346 +/* ========================================================================= */
   1.347 +local unsigned long gf2_matrix_times(mat, vec)
   1.348 +    unsigned long *mat;
   1.349 +    unsigned long vec;
   1.350 +{
   1.351 +    unsigned long sum;
   1.352 +
   1.353 +    sum = 0;
   1.354 +    while (vec) {
   1.355 +        if (vec & 1)
   1.356 +            sum ^= *mat;
   1.357 +        vec >>= 1;
   1.358 +        mat++;
   1.359 +    }
   1.360 +    return sum;
   1.361 +}
   1.362 +
   1.363 +/* ========================================================================= */
   1.364 +local void gf2_matrix_square(square, mat)
   1.365 +    unsigned long *square;
   1.366 +    unsigned long *mat;
   1.367 +{
   1.368 +    int n;
   1.369 +
   1.370 +    for (n = 0; n < GF2_DIM; n++)
   1.371 +        square[n] = gf2_matrix_times(mat, mat[n]);
   1.372 +}
   1.373 +
   1.374 +/* ========================================================================= */
   1.375 +local uLong crc32_combine_(crc1, crc2, len2)
   1.376 +    uLong crc1;
   1.377 +    uLong crc2;
   1.378 +    z_off64_t len2;
   1.379 +{
   1.380 +    int n;
   1.381 +    unsigned long row;
   1.382 +    unsigned long even[GF2_DIM];    /* even-power-of-two zeros operator */
   1.383 +    unsigned long odd[GF2_DIM];     /* odd-power-of-two zeros operator */
   1.384 +
   1.385 +    /* degenerate case (also disallow negative lengths) */
   1.386 +    if (len2 <= 0)
   1.387 +        return crc1;
   1.388 +
   1.389 +    /* put operator for one zero bit in odd */
   1.390 +    odd[0] = 0xedb88320UL;          /* CRC-32 polynomial */
   1.391 +    row = 1;
   1.392 +    for (n = 1; n < GF2_DIM; n++) {
   1.393 +        odd[n] = row;
   1.394 +        row <<= 1;
   1.395 +    }
   1.396 +
   1.397 +    /* put operator for two zero bits in even */
   1.398 +    gf2_matrix_square(even, odd);
   1.399 +
   1.400 +    /* put operator for four zero bits in odd */
   1.401 +    gf2_matrix_square(odd, even);
   1.402 +
   1.403 +    /* apply len2 zeros to crc1 (first square will put the operator for one
   1.404 +       zero byte, eight zero bits, in even) */
   1.405 +    do {
   1.406 +        /* apply zeros operator for this bit of len2 */
   1.407 +        gf2_matrix_square(even, odd);
   1.408 +        if (len2 & 1)
   1.409 +            crc1 = gf2_matrix_times(even, crc1);
   1.410 +        len2 >>= 1;
   1.411 +
   1.412 +        /* if no more bits set, then done */
   1.413 +        if (len2 == 0)
   1.414 +            break;
   1.415 +
   1.416 +        /* another iteration of the loop with odd and even swapped */
   1.417 +        gf2_matrix_square(odd, even);
   1.418 +        if (len2 & 1)
   1.419 +            crc1 = gf2_matrix_times(odd, crc1);
   1.420 +        len2 >>= 1;
   1.421 +
   1.422 +        /* if no more bits set, then done */
   1.423 +    } while (len2 != 0);
   1.424 +
   1.425 +    /* return combined crc */
   1.426 +    crc1 ^= crc2;
   1.427 +    return crc1;
   1.428 +}
   1.429 +
   1.430 +/* ========================================================================= */
   1.431 +uLong ZEXPORT crc32_combine(crc1, crc2, len2)
   1.432 +    uLong crc1;
   1.433 +    uLong crc2;
   1.434 +    z_off_t len2;
   1.435 +{
   1.436 +    return crc32_combine_(crc1, crc2, len2);
   1.437 +}
   1.438 +
   1.439 +uLong ZEXPORT crc32_combine64(crc1, crc2, len2)
   1.440 +    uLong crc1;
   1.441 +    uLong crc2;
   1.442 +    z_off64_t len2;
   1.443 +{
   1.444 +    return crc32_combine_(crc1, crc2, len2);
   1.445 +}