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