GPU unai update
[pcsx_rearmed.git] / deps / zlib / inffast.c
1 /* inffast.c -- fast decoding
2  * Copyright (C) 1995-2008, 2010, 2013 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 ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start)
68 {
69    struct inflate_state FAR *state;
70    unsigned char FAR *in;      /* local strm->next_in */
71    unsigned char FAR *last;    /* have enough input while in < last */
72    unsigned char FAR *out;     /* local strm->next_out */
73    unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
74    unsigned char FAR *end;     /* while out < end, enough space available */
75 #ifdef INFLATE_STRICT
76    unsigned dmax;              /* maximum distance from zlib header */
77 #endif
78    unsigned wsize;             /* window size or zero if not using window */
79    unsigned whave;             /* valid bytes in the window */
80    unsigned wnext;             /* window write index */
81    unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
82    unsigned long hold;         /* local strm->hold */
83    unsigned bits;              /* local strm->bits */
84    code const FAR *lcode;      /* local strm->lencode */
85    code const FAR *dcode;      /* local strm->distcode */
86    unsigned lmask;             /* mask for first level of length codes */
87    unsigned dmask;             /* mask for first level of distance codes */
88    code here;                  /* retrieved table entry */
89    unsigned op;                /* code bits, operation, extra bits, or */
90    /*  window position, window bytes to copy */
91    unsigned len;               /* match length, unused bytes */
92    unsigned dist;              /* match distance */
93    unsigned char FAR *from;    /* where to copy match from */
94
95    /* copy state to local variables */
96    state = (struct inflate_state FAR *)strm->state;
97    in = strm->next_in - OFF;
98    last = in + (strm->avail_in - 5);
99    out = strm->next_out - OFF;
100    beg = out - (start - strm->avail_out);
101    end = out + (strm->avail_out - 257);
102 #ifdef INFLATE_STRICT
103    dmax = state->dmax;
104 #endif
105    wsize = state->wsize;
106    whave = state->whave;
107    wnext = state->wnext;
108    window = state->window;
109    hold = state->hold;
110    bits = state->bits;
111    lcode = state->lencode;
112    dcode = state->distcode;
113    lmask = (1U << state->lenbits) - 1;
114    dmask = (1U << state->distbits) - 1;
115
116    /* decode literals and length/distances until end-of-block or not enough
117       input data or output space */
118    do {
119       if (bits < 15) {
120          hold += (unsigned long)(PUP(in)) << bits;
121          bits += 8;
122          hold += (unsigned long)(PUP(in)) << bits;
123          bits += 8;
124       }
125       here = lcode[hold & lmask];
126 dolen:
127       op = (unsigned)(here.bits);
128       hold >>= op;
129       bits -= op;
130       op = (unsigned)(here.op);
131       if (op == 0) {                          /* literal */
132          Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
133                   "inflate:         literal '%c'\n" :
134                   "inflate:         literal 0x%02x\n", here.val));
135          PUP(out) = (unsigned char)(here.val);
136       }
137       else if (op & 16) {                     /* length base */
138          len = (unsigned)(here.val);
139          op &= 15;                           /* number of extra bits */
140          if (op) {
141             if (bits < op) {
142                hold += (unsigned long)(PUP(in)) << bits;
143                bits += 8;
144             }
145             len += (unsigned)hold & ((1U << op) - 1);
146             hold >>= op;
147             bits -= op;
148          }
149          Tracevv((stderr, "inflate:         length %u\n", len));
150          if (bits < 15) {
151             hold += (unsigned long)(PUP(in)) << bits;
152             bits += 8;
153             hold += (unsigned long)(PUP(in)) << bits;
154             bits += 8;
155          }
156          here = dcode[hold & dmask];
157 dodist:
158          op = (unsigned)(here.bits);
159          hold >>= op;
160          bits -= op;
161          op = (unsigned)(here.op);
162          if (op & 16) {                      /* distance base */
163             dist = (unsigned)(here.val);
164             op &= 15;                       /* number of extra bits */
165             if (bits < op) {
166                hold += (unsigned long)(PUP(in)) << bits;
167                bits += 8;
168                if (bits < op) {
169                   hold += (unsigned long)(PUP(in)) << bits;
170                   bits += 8;
171                }
172             }
173             dist += (unsigned)hold & ((1U << op) - 1);
174 #ifdef INFLATE_STRICT
175             if (dist > dmax) {
176                strm->msg = (char *)"invalid distance too far back";
177                state->mode = BAD;
178                break;
179             }
180 #endif
181             hold >>= op;
182             bits -= op;
183             Tracevv((stderr, "inflate:         distance %u\n", dist));
184             op = (unsigned)(out - beg);     /* max distance in output */
185             if (dist > op) {                /* see if copy from window */
186                op = dist - op;             /* distance back in window */
187                if (op > whave) {
188                   if (state->sane) {
189                      strm->msg =
190                         (char *)"invalid distance too far back";
191                      state->mode = BAD;
192                      break;
193                   }
194 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
195                   if (len <= op - whave) {
196                      do {
197                         PUP(out) = 0;
198                      } while (--len);
199                      continue;
200                   }
201                   len -= op - whave;
202                   do {
203                      PUP(out) = 0;
204                   } while (--op > whave);
205                   if (op == 0) {
206                      from = out - dist;
207                      do {
208                         PUP(out) = PUP(from);
209                      } while (--len);
210                      continue;
211                   }
212 #endif
213                }
214                from = window - OFF;
215                if (wnext == 0) {           /* very common case */
216                   from += wsize - op;
217                   if (op < len) {         /* some from window */
218                      len -= op;
219                      do {
220                         PUP(out) = PUP(from);
221                      } while (--op);
222                      from = out - dist;  /* rest from output */
223                   }
224                }
225                else if (wnext < op) {      /* wrap around window */
226                   from += wsize + wnext - op;
227                   op -= wnext;
228                   if (op < len) {         /* some from end of window */
229                      len -= op;
230                      do {
231                         PUP(out) = PUP(from);
232                      } while (--op);
233                      from = window - OFF;
234                      if (wnext < len) {  /* some from start of window */
235                         op = wnext;
236                         len -= op;
237                         do {
238                            PUP(out) = PUP(from);
239                         } while (--op);
240                         from = out - dist;      /* rest from output */
241                      }
242                   }
243                }
244                else {                      /* contiguous in window */
245                   from += wnext - op;
246                   if (op < len) {         /* some from window */
247                      len -= op;
248                      do {
249                         PUP(out) = PUP(from);
250                      } while (--op);
251                      from = out - dist;  /* rest from output */
252                   }
253                }
254                while (len > 2) {
255                   PUP(out) = PUP(from);
256                   PUP(out) = PUP(from);
257                   PUP(out) = PUP(from);
258                   len -= 3;
259                }
260                if (len) {
261                   PUP(out) = PUP(from);
262                   if (len > 1)
263                      PUP(out) = PUP(from);
264                }
265             }
266             else {
267                from = out - dist;          /* copy direct from output */
268                do {                        /* minimum length is three */
269                   PUP(out) = PUP(from);
270                   PUP(out) = PUP(from);
271                   PUP(out) = PUP(from);
272                   len -= 3;
273                } while (len > 2);
274                if (len) {
275                   PUP(out) = PUP(from);
276                   if (len > 1)
277                      PUP(out) = PUP(from);
278                }
279             }
280          }
281          else if ((op & 64) == 0) {          /* 2nd level distance code */
282             here = dcode[here.val + (hold & ((1U << op) - 1))];
283             goto dodist;
284          }
285          else {
286             strm->msg = (char *)"invalid distance code";
287             state->mode = BAD;
288             break;
289          }
290       }
291       else if ((op & 64) == 0) {              /* 2nd level length code */
292          here = lcode[here.val + (hold & ((1U << op) - 1))];
293          goto dolen;
294       }
295       else if (op & 32) {                     /* end-of-block */
296          Tracevv((stderr, "inflate:         end of block\n"));
297          state->mode = TYPE;
298          break;
299       }
300       else {
301          strm->msg = (char *)"invalid literal/length code";
302          state->mode = BAD;
303          break;
304       }
305    } while (in < last && out < end);
306
307    /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
308    len = bits >> 3;
309    in -= len;
310    bits -= len << 3;
311    hold &= (1U << bits) - 1;
312
313    /* update state and return */
314    strm->next_in = in + OFF;
315    strm->next_out = out + OFF;
316    strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
317    strm->avail_out = (unsigned)(out < end ?
318          257 + (end - out) : 257 - (out - end));
319    state->hold = hold;
320    state->bits = bits;
321    return;
322 }
323
324 /*
325    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
326    - Using bit fields for code structure
327    - Different op definition to avoid & for extra bits (do & for table bits)
328    - Three separate decoding do-loops for direct, window, and wnext == 0
329    - Special case for distance > 1 copies to do overlapped load and store copy
330    - Explicit branch predictions (based on measured branch probabilities)
331    - Deferring match copy and interspersed it with decoding subsequent codes
332    - Swapping literal/length else
333    - Swapping window/direct else
334    - Larger unrolled copy loops (three is about right)
335    - Moving len -= 3 statement into middle of loop
336    */
337
338 #endif /* !ASMINF */