1.1 --- a/sourcepawn/jit/zlib/crc32.c Fri Jul 11 06:51:21 2008 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,423 +0,0 @@
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 <[email protected]> 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 -}
