1.1 --- a/sourcepawn/compiler/zlib/inffast.c Fri Mar 28 06:21:34 2008 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,318 +0,0 @@
1.4 -/* inffast.c -- fast decoding
1.5 - * Copyright (C) 1995-2004 Mark Adler
1.6 - * For conditions of distribution and use, see copyright notice in zlib.h
1.7 - */
1.8 -
1.9 -#include "zutil.h"
1.10 -#include "inftrees.h"
1.11 -#include "inflate.h"
1.12 -#include "inffast.h"
1.13 -
1.14 -#ifndef ASMINF
1.15 -
1.16 -/* Allow machine dependent optimization for post-increment or pre-increment.
1.17 - Based on testing to date,
1.18 - Pre-increment preferred for:
1.19 - - PowerPC G3 (Adler)
1.20 - - MIPS R5000 (Randers-Pehrson)
1.21 - Post-increment preferred for:
1.22 - - none
1.23 - No measurable difference:
1.24 - - Pentium III (Anderson)
1.25 - - M68060 (Nikl)
1.26 - */
1.27 -#ifdef POSTINC
1.28 -# define OFF 0
1.29 -# define PUP(a) *(a)++
1.30 -#else
1.31 -# define OFF 1
1.32 -# define PUP(a) *++(a)
1.33 -#endif
1.34 -
1.35 -/*
1.36 - Decode literal, length, and distance codes and write out the resulting
1.37 - literal and match bytes until either not enough input or output is
1.38 - available, an end-of-block is encountered, or a data error is encountered.
1.39 - When large enough input and output buffers are supplied to inflate(), for
1.40 - example, a 16K input buffer and a 64K output buffer, more than 95% of the
1.41 - inflate execution time is spent in this routine.
1.42 -
1.43 - Entry assumptions:
1.44 -
1.45 - state->mode == LEN
1.46 - strm->avail_in >= 6
1.47 - strm->avail_out >= 258
1.48 - start >= strm->avail_out
1.49 - state->bits < 8
1.50 -
1.51 - On return, state->mode is one of:
1.52 -
1.53 - LEN -- ran out of enough output space or enough available input
1.54 - TYPE -- reached end of block code, inflate() to interpret next block
1.55 - BAD -- error in block data
1.56 -
1.57 - Notes:
1.58 -
1.59 - - The maximum input bits used by a length/distance pair is 15 bits for the
1.60 - length code, 5 bits for the length extra, 15 bits for the distance code,
1.61 - and 13 bits for the distance extra. This totals 48 bits, or six bytes.
1.62 - Therefore if strm->avail_in >= 6, then there is enough input to avoid
1.63 - checking for available input while decoding.
1.64 -
1.65 - - The maximum bytes that a single length/distance pair can output is 258
1.66 - bytes, which is the maximum length that can be coded. inflate_fast()
1.67 - requires strm->avail_out >= 258 for each loop to avoid checking for
1.68 - output space.
1.69 - */
1.70 -void inflate_fast(strm, start)
1.71 -z_streamp strm;
1.72 -unsigned start; /* inflate()'s starting value for strm->avail_out */
1.73 -{
1.74 - struct inflate_state FAR *state;
1.75 - unsigned char FAR *in; /* local strm->next_in */
1.76 - unsigned char FAR *last; /* while in < last, enough input available */
1.77 - unsigned char FAR *out; /* local strm->next_out */
1.78 - unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
1.79 - unsigned char FAR *end; /* while out < end, enough space available */
1.80 -#ifdef INFLATE_STRICT
1.81 - unsigned dmax; /* maximum distance from zlib header */
1.82 -#endif
1.83 - unsigned wsize; /* window size or zero if not using window */
1.84 - unsigned whave; /* valid bytes in the window */
1.85 - unsigned write; /* window write index */
1.86 - unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
1.87 - unsigned long hold; /* local strm->hold */
1.88 - unsigned bits; /* local strm->bits */
1.89 - code const FAR *lcode; /* local strm->lencode */
1.90 - code const FAR *dcode; /* local strm->distcode */
1.91 - unsigned lmask; /* mask for first level of length codes */
1.92 - unsigned dmask; /* mask for first level of distance codes */
1.93 - code this; /* retrieved table entry */
1.94 - unsigned op; /* code bits, operation, extra bits, or */
1.95 - /* window position, window bytes to copy */
1.96 - unsigned len; /* match length, unused bytes */
1.97 - unsigned dist; /* match distance */
1.98 - unsigned char FAR *from; /* where to copy match from */
1.99 -
1.100 - /* copy state to local variables */
1.101 - state = (struct inflate_state FAR *)strm->state;
1.102 - in = strm->next_in - OFF;
1.103 - last = in + (strm->avail_in - 5);
1.104 - out = strm->next_out - OFF;
1.105 - beg = out - (start - strm->avail_out);
1.106 - end = out + (strm->avail_out - 257);
1.107 -#ifdef INFLATE_STRICT
1.108 - dmax = state->dmax;
1.109 -#endif
1.110 - wsize = state->wsize;
1.111 - whave = state->whave;
1.112 - write = state->write;
1.113 - window = state->window;
1.114 - hold = state->hold;
1.115 - bits = state->bits;
1.116 - lcode = state->lencode;
1.117 - dcode = state->distcode;
1.118 - lmask = (1U << state->lenbits) - 1;
1.119 - dmask = (1U << state->distbits) - 1;
1.120 -
1.121 - /* decode literals and length/distances until end-of-block or not enough
1.122 - input data or output space */
1.123 - do {
1.124 - if (bits < 15) {
1.125 - hold += (unsigned long)(PUP(in)) << bits;
1.126 - bits += 8;
1.127 - hold += (unsigned long)(PUP(in)) << bits;
1.128 - bits += 8;
1.129 - }
1.130 - this = lcode[hold & lmask];
1.131 - dolen:
1.132 - op = (unsigned)(this.bits);
1.133 - hold >>= op;
1.134 - bits -= op;
1.135 - op = (unsigned)(this.op);
1.136 - if (op == 0) { /* literal */
1.137 - Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1.138 - "inflate: literal '%c'\n" :
1.139 - "inflate: literal 0x%02x\n", this.val));
1.140 - PUP(out) = (unsigned char)(this.val);
1.141 - }
1.142 - else if (op & 16) { /* length base */
1.143 - len = (unsigned)(this.val);
1.144 - op &= 15; /* number of extra bits */
1.145 - if (op) {
1.146 - if (bits < op) {
1.147 - hold += (unsigned long)(PUP(in)) << bits;
1.148 - bits += 8;
1.149 - }
1.150 - len += (unsigned)hold & ((1U << op) - 1);
1.151 - hold >>= op;
1.152 - bits -= op;
1.153 - }
1.154 - Tracevv((stderr, "inflate: length %u\n", len));
1.155 - if (bits < 15) {
1.156 - hold += (unsigned long)(PUP(in)) << bits;
1.157 - bits += 8;
1.158 - hold += (unsigned long)(PUP(in)) << bits;
1.159 - bits += 8;
1.160 - }
1.161 - this = dcode[hold & dmask];
1.162 - dodist:
1.163 - op = (unsigned)(this.bits);
1.164 - hold >>= op;
1.165 - bits -= op;
1.166 - op = (unsigned)(this.op);
1.167 - if (op & 16) { /* distance base */
1.168 - dist = (unsigned)(this.val);
1.169 - op &= 15; /* number of extra bits */
1.170 - if (bits < op) {
1.171 - hold += (unsigned long)(PUP(in)) << bits;
1.172 - bits += 8;
1.173 - if (bits < op) {
1.174 - hold += (unsigned long)(PUP(in)) << bits;
1.175 - bits += 8;
1.176 - }
1.177 - }
1.178 - dist += (unsigned)hold & ((1U << op) - 1);
1.179 -#ifdef INFLATE_STRICT
1.180 - if (dist > dmax) {
1.181 - strm->msg = (char *)"invalid distance too far back";
1.182 - state->mode = BAD;
1.183 - break;
1.184 - }
1.185 -#endif
1.186 - hold >>= op;
1.187 - bits -= op;
1.188 - Tracevv((stderr, "inflate: distance %u\n", dist));
1.189 - op = (unsigned)(out - beg); /* max distance in output */
1.190 - if (dist > op) { /* see if copy from window */
1.191 - op = dist - op; /* distance back in window */
1.192 - if (op > whave) {
1.193 - strm->msg = (char *)"invalid distance too far back";
1.194 - state->mode = BAD;
1.195 - break;
1.196 - }
1.197 - from = window - OFF;
1.198 - if (write == 0) { /* very common case */
1.199 - from += wsize - op;
1.200 - if (op < len) { /* some from window */
1.201 - len -= op;
1.202 - do {
1.203 - PUP(out) = PUP(from);
1.204 - } while (--op);
1.205 - from = out - dist; /* rest from output */
1.206 - }
1.207 - }
1.208 - else if (write < op) { /* wrap around window */
1.209 - from += wsize + write - op;
1.210 - op -= write;
1.211 - if (op < len) { /* some from end of window */
1.212 - len -= op;
1.213 - do {
1.214 - PUP(out) = PUP(from);
1.215 - } while (--op);
1.216 - from = window - OFF;
1.217 - if (write < len) { /* some from start of window */
1.218 - op = write;
1.219 - len -= op;
1.220 - do {
1.221 - PUP(out) = PUP(from);
1.222 - } while (--op);
1.223 - from = out - dist; /* rest from output */
1.224 - }
1.225 - }
1.226 - }
1.227 - else { /* contiguous in window */
1.228 - from += write - op;
1.229 - if (op < len) { /* some from window */
1.230 - len -= op;
1.231 - do {
1.232 - PUP(out) = PUP(from);
1.233 - } while (--op);
1.234 - from = out - dist; /* rest from output */
1.235 - }
1.236 - }
1.237 - while (len > 2) {
1.238 - PUP(out) = PUP(from);
1.239 - PUP(out) = PUP(from);
1.240 - PUP(out) = PUP(from);
1.241 - len -= 3;
1.242 - }
1.243 - if (len) {
1.244 - PUP(out) = PUP(from);
1.245 - if (len > 1)
1.246 - PUP(out) = PUP(from);
1.247 - }
1.248 - }
1.249 - else {
1.250 - from = out - dist; /* copy direct from output */
1.251 - do { /* minimum length is three */
1.252 - PUP(out) = PUP(from);
1.253 - PUP(out) = PUP(from);
1.254 - PUP(out) = PUP(from);
1.255 - len -= 3;
1.256 - } while (len > 2);
1.257 - if (len) {
1.258 - PUP(out) = PUP(from);
1.259 - if (len > 1)
1.260 - PUP(out) = PUP(from);
1.261 - }
1.262 - }
1.263 - }
1.264 - else if ((op & 64) == 0) { /* 2nd level distance code */
1.265 - this = dcode[this.val + (hold & ((1U << op) - 1))];
1.266 - goto dodist;
1.267 - }
1.268 - else {
1.269 - strm->msg = (char *)"invalid distance code";
1.270 - state->mode = BAD;
1.271 - break;
1.272 - }
1.273 - }
1.274 - else if ((op & 64) == 0) { /* 2nd level length code */
1.275 - this = lcode[this.val + (hold & ((1U << op) - 1))];
1.276 - goto dolen;
1.277 - }
1.278 - else if (op & 32) { /* end-of-block */
1.279 - Tracevv((stderr, "inflate: end of block\n"));
1.280 - state->mode = TYPE;
1.281 - break;
1.282 - }
1.283 - else {
1.284 - strm->msg = (char *)"invalid literal/length code";
1.285 - state->mode = BAD;
1.286 - break;
1.287 - }
1.288 - } while (in < last && out < end);
1.289 -
1.290 - /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
1.291 - len = bits >> 3;
1.292 - in -= len;
1.293 - bits -= len << 3;
1.294 - hold &= (1U << bits) - 1;
1.295 -
1.296 - /* update state and return */
1.297 - strm->next_in = in + OFF;
1.298 - strm->next_out = out + OFF;
1.299 - strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
1.300 - strm->avail_out = (unsigned)(out < end ?
1.301 - 257 + (end - out) : 257 - (out - end));
1.302 - state->hold = hold;
1.303 - state->bits = bits;
1.304 - return;
1.305 -}
1.306 -
1.307 -/*
1.308 - inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
1.309 - - Using bit fields for code structure
1.310 - - Different op definition to avoid & for extra bits (do & for table bits)
1.311 - - Three separate decoding do-loops for direct, window, and write == 0
1.312 - - Special case for distance > 1 copies to do overlapped load and store copy
1.313 - - Explicit branch predictions (based on measured branch probabilities)
1.314 - - Deferring match copy and interspersed it with decoding subsequent codes
1.315 - - Swapping literal/length else
1.316 - - Swapping window/direct else
1.317 - - Larger unrolled copy loops (three is about right)
1.318 - - Moving len -= 3 statement into middle of loop
1.319 - */
1.320 -
1.321 -#endif /* !ASMINF */
