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