ECCE @ EIC Software
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
inffast.c
Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file inffast.c
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  */
50 void ZLIB_INTERNAL inflate_fast(strm, start)
51 z_streamp strm;
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 */