1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/core/zlib/crc32.c Sun Mar 30 07:00:22 2008 +0000
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 <[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 +}
