/[pcsx2_0.9.7]/trunk/3rdparty/zlib/inffast.c
ViewVC logotype

Annotation of /trunk/3rdparty/zlib/inffast.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (hide annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (10 years, 2 months ago) by william
File MIME type: text/plain
File size: 13419 byte(s)
committing r3113 initial commit again...
1 william 31 /* inffast.c -- fast decoding
2     * Copyright (C) 1995-2008 Mark Adler
3     * For conditions of distribution and use, see copyright notice in zlib.h
4     */
5    
6     #include "zutil.h"
7     #include "inftrees.h"
8     #include "inflate.h"
9     #include "inffast.h"
10    
11     #ifndef ASMINF
12    
13     /* Allow machine dependent optimization for post-increment or pre-increment.
14     Based on testing to date,
15     Pre-increment preferred for:
16     - PowerPC G3 (Adler)
17     - MIPS R5000 (Randers-Pehrson)
18     Post-increment preferred for:
19     - none
20     No measurable difference:
21     - Pentium III (Anderson)
22     - M68060 (Nikl)
23     */
24     #ifdef POSTINC
25     # define OFF 0
26     # define PUP(a) *(a)++
27     #else
28     # define OFF 1
29     # define PUP(a) *++(a)
30     #endif
31    
32     /*
33     Decode literal, length, and distance codes and write out the resulting
34     literal and match bytes until either not enough input or output is
35     available, an end-of-block is encountered, or a data error is encountered.
36     When large enough input and output buffers are supplied to inflate(), for
37     example, a 16K input buffer and a 64K output buffer, more than 95% of the
38     inflate execution time is spent in this routine.
39    
40     Entry assumptions:
41    
42     state->mode == LEN
43     strm->avail_in >= 6
44     strm->avail_out >= 258
45     start >= strm->avail_out
46     state->bits < 8
47    
48     On return, state->mode is one of:
49    
50     LEN -- ran out of enough output space or enough available input
51     TYPE -- reached end of block code, inflate() to interpret next block
52     BAD -- error in block data
53    
54     Notes:
55    
56     - The maximum input bits used by a length/distance pair is 15 bits for the
57     length code, 5 bits for the length extra, 15 bits for the distance code,
58     and 13 bits for the distance extra. This totals 48 bits, or six bytes.
59     Therefore if strm->avail_in >= 6, then there is enough input to avoid
60     checking for available input while decoding.
61    
62     - The maximum bytes that a single length/distance pair can output is 258
63     bytes, which is the maximum length that can be coded. inflate_fast()
64     requires strm->avail_out >= 258 for each loop to avoid checking for
65     output space.
66     */
67     void inflate_fast(strm, start)
68     z_streamp strm;
69     unsigned start; /* inflate()'s starting value for strm->avail_out */
70     {
71     struct inflate_state FAR *state;
72     unsigned char FAR *in; /* local strm->next_in */
73     unsigned char FAR *last; /* while in < last, enough input available */
74     unsigned char FAR *out; /* local strm->next_out */
75     unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
76     unsigned char FAR *end; /* while out < end, enough space available */
77     #ifdef INFLATE_STRICT
78     unsigned dmax; /* maximum distance from zlib header */
79     #endif
80     unsigned wsize; /* window size or zero if not using window */
81     unsigned whave; /* valid bytes in the window */
82     unsigned wnext; /* window write index */
83     unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
84     unsigned long hold; /* local strm->hold */
85     unsigned bits; /* local strm->bits */
86     code const FAR *lcode; /* local strm->lencode */
87     code const FAR *dcode; /* local strm->distcode */
88     unsigned lmask; /* mask for first level of length codes */
89     unsigned dmask; /* mask for first level of distance codes */
90     code here; /* retrieved table entry */
91     unsigned op; /* code bits, operation, extra bits, or */
92     /* window position, window bytes to copy */
93     unsigned len; /* match length, unused bytes */
94     unsigned dist; /* match distance */
95     unsigned char FAR *from; /* where to copy match from */
96    
97     /* copy state to local variables */
98     state = (struct inflate_state FAR *)strm->state;
99     in = strm->next_in - OFF;
100     last = in + (strm->avail_in - 5);
101     out = strm->next_out - OFF;
102     beg = out - (start - strm->avail_out);
103     end = out + (strm->avail_out - 257);
104     #ifdef INFLATE_STRICT
105     dmax = state->dmax;
106     #endif
107     wsize = state->wsize;
108     whave = state->whave;
109     wnext = state->wnext;
110     window = state->window;
111     hold = state->hold;
112     bits = state->bits;
113     lcode = state->lencode;
114     dcode = state->distcode;
115     lmask = (1U << state->lenbits) - 1;
116     dmask = (1U << state->distbits) - 1;
117    
118     /* decode literals and length/distances until end-of-block or not enough
119     input data or output space */
120     do {
121     if (bits < 15) {
122     hold += (unsigned long)(PUP(in)) << bits;
123     bits += 8;
124     hold += (unsigned long)(PUP(in)) << bits;
125     bits += 8;
126     }
127     here = lcode[hold & lmask];
128     dolen:
129     op = (unsigned)(here.bits);
130     hold >>= op;
131     bits -= op;
132     op = (unsigned)(here.op);
133     if (op == 0) { /* literal */
134     Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
135     "inflate: literal '%c'\n" :
136     "inflate: literal 0x%02x\n", here.val));
137     PUP(out) = (unsigned char)(here.val);
138     }
139     else if (op & 16) { /* length base */
140     len = (unsigned)(here.val);
141     op &= 15; /* number of extra bits */
142     if (op) {
143     if (bits < op) {
144     hold += (unsigned long)(PUP(in)) << bits;
145     bits += 8;
146     }
147     len += (unsigned)hold & ((1U << op) - 1);
148     hold >>= op;
149     bits -= op;
150     }
151     Tracevv((stderr, "inflate: length %u\n", len));
152     if (bits < 15) {
153     hold += (unsigned long)(PUP(in)) << bits;
154     bits += 8;
155     hold += (unsigned long)(PUP(in)) << bits;
156     bits += 8;
157     }
158     here = dcode[hold & dmask];
159     dodist:
160     op = (unsigned)(here.bits);
161     hold >>= op;
162     bits -= op;
163     op = (unsigned)(here.op);
164     if (op & 16) { /* distance base */
165     dist = (unsigned)(here.val);
166     op &= 15; /* number of extra bits */
167     if (bits < op) {
168     hold += (unsigned long)(PUP(in)) << bits;
169     bits += 8;
170     if (bits < op) {
171     hold += (unsigned long)(PUP(in)) << bits;
172     bits += 8;
173     }
174     }
175     dist += (unsigned)hold & ((1U << op) - 1);
176     #ifdef INFLATE_STRICT
177     if (dist > dmax) {
178     strm->msg = (char *)"invalid distance too far back";
179     state->mode = BAD;
180     break;
181     }
182     #endif
183     hold >>= op;
184     bits -= op;
185     Tracevv((stderr, "inflate: distance %u\n", dist));
186     op = (unsigned)(out - beg); /* max distance in output */
187     if (dist > op) { /* see if copy from window */
188     op = dist - op; /* distance back in window */
189     if (op > whave) {
190     if (state->sane) {
191     strm->msg =
192     (char *)"invalid distance too far back";
193     state->mode = BAD;
194     break;
195     }
196     #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
197     if (len <= op - whave) {
198     do {
199     PUP(out) = 0;
200     } while (--len);
201     continue;
202     }
203     len -= op - whave;
204     do {
205     PUP(out) = 0;
206     } while (--op > whave);
207     if (op == 0) {
208     from = out - dist;
209     do {
210     PUP(out) = PUP(from);
211     } while (--len);
212     continue;
213     }
214     #endif
215     }
216     from = window - OFF;
217     if (wnext == 0) { /* very common case */
218     from += wsize - op;
219     if (op < len) { /* some from window */
220     len -= op;
221     do {
222     PUP(out) = PUP(from);
223     } while (--op);
224     from = out - dist; /* rest from output */
225     }
226     }
227     else if (wnext < op) { /* wrap around window */
228     from += wsize + wnext - op;
229     op -= wnext;
230     if (op < len) { /* some from end of window */
231     len -= op;
232     do {
233     PUP(out) = PUP(from);
234     } while (--op);
235     from = window - OFF;
236     if (wnext < len) { /* some from start of window */
237     op = wnext;
238     len -= op;
239     do {
240     PUP(out) = PUP(from);
241     } while (--op);
242     from = out - dist; /* rest from output */
243     }
244     }
245     }
246     else { /* contiguous in window */
247     from += wnext - op;
248     if (op < len) { /* some from window */
249     len -= op;
250     do {
251     PUP(out) = PUP(from);
252     } while (--op);
253     from = out - dist; /* rest from output */
254     }
255     }
256     while (len > 2) {
257     PUP(out) = PUP(from);
258     PUP(out) = PUP(from);
259     PUP(out) = PUP(from);
260     len -= 3;
261     }
262     if (len) {
263     PUP(out) = PUP(from);
264     if (len > 1)
265     PUP(out) = PUP(from);
266     }
267     }
268     else {
269     from = out - dist; /* copy direct from output */
270     do { /* minimum length is three */
271     PUP(out) = PUP(from);
272     PUP(out) = PUP(from);
273     PUP(out) = PUP(from);
274     len -= 3;
275     } while (len > 2);
276     if (len) {
277     PUP(out) = PUP(from);
278     if (len > 1)
279     PUP(out) = PUP(from);
280     }
281     }
282     }
283     else if ((op & 64) == 0) { /* 2nd level distance code */
284     here = dcode[here.val + (hold & ((1U << op) - 1))];
285     goto dodist;
286     }
287     else {
288     strm->msg = (char *)"invalid distance code";
289     state->mode = BAD;
290     break;
291     }
292     }
293     else if ((op & 64) == 0) { /* 2nd level length code */
294     here = lcode[here.val + (hold & ((1U << op) - 1))];
295     goto dolen;
296     }
297     else if (op & 32) { /* end-of-block */
298     Tracevv((stderr, "inflate: end of block\n"));
299     state->mode = TYPE;
300     break;
301     }
302     else {
303     strm->msg = (char *)"invalid literal/length code";
304     state->mode = BAD;
305     break;
306     }
307     } while (in < last && out < end);
308    
309     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
310     len = bits >> 3;
311     in -= len;
312     bits -= len << 3;
313     hold &= (1U << bits) - 1;
314    
315     /* update state and return */
316     strm->next_in = in + OFF;
317     strm->next_out = out + OFF;
318     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
319     strm->avail_out = (unsigned)(out < end ?
320     257 + (end - out) : 257 - (out - end));
321     state->hold = hold;
322     state->bits = bits;
323     return;
324     }
325    
326     /*
327     inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
328     - Using bit fields for code structure
329     - Different op definition to avoid & for extra bits (do & for table bits)
330     - Three separate decoding do-loops for direct, window, and wnext == 0
331     - Special case for distance > 1 copies to do overlapped load and store copy
332     - Explicit branch predictions (based on measured branch probabilities)
333     - Deferring match copy and interspersed it with decoding subsequent codes
334     - Swapping literal/length else
335     - Swapping window/direct else
336     - Larger unrolled copy loops (three is about right)
337     - Moving len -= 3 statement into middle of loop
338     */
339    
340     #endif /* !ASMINF */

  ViewVC Help
Powered by ViewVC 1.1.22