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