NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
infback.c
Go to the documentation of this file.
1 /* infback.c -- inflate using a call-back interface
2  * Copyright (C) 1995-2011 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 /*
7  This code is largely copied from inflate.c. Normally either infback.o or
8  inflate.o would be linked into an application--not both. The interface
9  with inffast.c is retained so that optimized assembler-coded versions of
10  inflate_fast() can be used with either inflate.c or infback.c.
11  */
12 
13 #include "zutil.h"
14 #include "inftrees.h"
15 #include "inflate.h"
16 #include "inffast.h"
17 
18 /* function prototypes */
19 local void fixedtables OF((struct inflate_state FAR *state));
20 
21 /*
22  strm provides memory allocation functions in zalloc and zfree, or
23  Z_NULL to use the library memory allocation functions.
24 
25  windowBits is in the range 8..15, and window is a user-supplied
26  window and output buffer that is 2**windowBits bytes.
27  */
28 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
29 z_streamp strm;
30 int windowBits;
31 unsigned char FAR *window;
32 const char *version;
33 int stream_size;
34 {
35  struct inflate_state FAR *state;
36 
37  if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
38  stream_size != (int)(sizeof(z_stream)))
39  return Z_VERSION_ERROR;
40  if (strm == Z_NULL || window == Z_NULL ||
41  windowBits < 8 || windowBits > 15)
42  return Z_STREAM_ERROR;
43  strm->msg = Z_NULL; /* in case we return an error */
44  if (strm->zalloc == (alloc_func)0) {
45 #ifdef Z_SOLO
46  return Z_STREAM_ERROR;
47 #else
48  strm->zalloc = zcalloc;
49  strm->opaque = (voidpf)0;
50 #endif
51  }
52  if (strm->zfree == (free_func)0)
53 #ifdef Z_SOLO
54  return Z_STREAM_ERROR;
55 #else
56  strm->zfree = zcfree;
57 #endif
58  state = (struct inflate_state FAR *)ZALLOC(strm, 1,
59  sizeof(struct inflate_state));
60  if (state == Z_NULL) return Z_MEM_ERROR;
61  Tracev((stderr, "inflate: allocated\n"));
62  strm->state = (struct internal_state FAR *)state;
63  state->dmax = 32768U;
64  state->wbits = windowBits;
65  state->wsize = 1U << windowBits;
66  state->window = window;
67  state->wnext = 0;
68  state->whave = 0;
69  return Z_OK;
70 }
71 
72 /*
73  Return state with length and distance decoding tables and index sizes set to
74  fixed code decoding. Normally this returns fixed tables from inffixed.h.
75  If BUILDFIXED is defined, then instead this routine builds the tables the
76  first time it's called, and returns those tables the first time and
77  thereafter. This reduces the size of the code by about 2K bytes, in
78  exchange for a little execution time. However, BUILDFIXED should not be
79  used for threaded applications, since the rewriting of the tables and virgin
80  may not be thread-safe.
81  */
82 local void fixedtables(state)
83 struct inflate_state FAR *state;
84 {
85 #ifdef BUILDFIXED
86  static int virgin = 1;
87  static code *lenfix, *distfix;
88  static code fixed[544];
89 
90  /* build fixed huffman tables if first call (may not be thread safe) */
91  if (virgin) {
92  unsigned sym, bits;
93  static code *next;
94 
95  /* literal/length table */
96  sym = 0;
97  while (sym < 144) state->lens[sym++] = 8;
98  while (sym < 256) state->lens[sym++] = 9;
99  while (sym < 280) state->lens[sym++] = 7;
100  while (sym < 288) state->lens[sym++] = 8;
101  next = fixed;
102  lenfix = next;
103  bits = 9;
104  inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
105 
106  /* distance table */
107  sym = 0;
108  while (sym < 32) state->lens[sym++] = 5;
109  distfix = next;
110  bits = 5;
111  inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
112 
113  /* do this just once */
114  virgin = 0;
115  }
116 #else /* !BUILDFIXED */
117 # include "inffixed.h"
118 #endif /* BUILDFIXED */
119  state->lencode = lenfix;
120  state->lenbits = 9;
121  state->distcode = distfix;
122  state->distbits = 5;
123 }
124 
125 /* Macros for inflateBack(): */
126 
127 /* Load returned state from inflate_fast() */
128 #define LOAD() \
129  do { \
130  put = strm->next_out; \
131  left = strm->avail_out; \
132  next = strm->next_in; \
133  have = strm->avail_in; \
134  hold = state->hold; \
135  bits = state->bits; \
136  } while (0)
137 
138 /* Set state from registers for inflate_fast() */
139 #define RESTORE() \
140  do { \
141  strm->next_out = put; \
142  strm->avail_out = left; \
143  strm->next_in = next; \
144  strm->avail_in = have; \
145  state->hold = hold; \
146  state->bits = bits; \
147  } while (0)
148 
149 /* Clear the input bit accumulator */
150 #define INITBITS() \
151  do { \
152  hold = 0; \
153  bits = 0; \
154  } while (0)
155 
156 /* Assure that some input is available. If input is requested, but denied,
157  then return a Z_BUF_ERROR from inflateBack(). */
158 #define PULL() \
159  do { \
160  if (have == 0) { \
161  have = in(in_desc, &next); \
162  if (have == 0) { \
163  next = Z_NULL; \
164  ret = Z_BUF_ERROR; \
165  goto inf_leave; \
166  } \
167  } \
168  } while (0)
169 
170 /* Get a byte of input into the bit accumulator, or return from inflateBack()
171  with an error if there is no input available. */
172 #define PULLBYTE() \
173  do { \
174  PULL(); \
175  have--; \
176  hold += (unsigned long)(*next++) << bits; \
177  bits += 8; \
178  } while (0)
179 
180 /* Assure that there are at least n bits in the bit accumulator. If there is
181  not enough available input to do that, then return from inflateBack() with
182  an error. */
183 #define NEEDBITS(n) \
184  do { \
185  while (bits < (unsigned)(n)) \
186  PULLBYTE(); \
187  } while (0)
188 
189 /* Return the low n bits of the bit accumulator (n < 16) */
190 #define BITS(n) \
191  ((unsigned)hold & ((1U << (n)) - 1))
192 
193 /* Remove n bits from the bit accumulator */
194 #define DROPBITS(n) \
195  do { \
196  hold >>= (n); \
197  bits -= (unsigned)(n); \
198  } while (0)
199 
200 /* Remove zero to seven bits as needed to go to a byte boundary */
201 #define BYTEBITS() \
202  do { \
203  hold >>= bits & 7; \
204  bits -= bits & 7; \
205  } while (0)
206 
207 /* Assure that some output space is available, by writing out the window
208  if it's full. If the write fails, return from inflateBack() with a
209  Z_BUF_ERROR. */
210 #define ROOM() \
211  do { \
212  if (left == 0) { \
213  put = state->window; \
214  left = state->wsize; \
215  state->whave = left; \
216  if (out(out_desc, put, left)) { \
217  ret = Z_BUF_ERROR; \
218  goto inf_leave; \
219  } \
220  } \
221  } while (0)
222 
223 /*
224  strm provides the memory allocation functions and window buffer on input,
225  and provides information on the unused input on return. For Z_DATA_ERROR
226  returns, strm will also provide an error message.
227 
228  in() and out() are the call-back input and output functions. When
229  inflateBack() needs more input, it calls in(). When inflateBack() has
230  filled the window with output, or when it completes with data in the
231  window, it calls out() to write out the data. The application must not
232  change the provided input until in() is called again or inflateBack()
233  returns. The application must not change the window/output buffer until
234  inflateBack() returns.
235 
236  in() and out() are called with a descriptor parameter provided in the
237  inflateBack() call. This parameter can be a structure that provides the
238  information required to do the read or write, as well as accumulated
239  information on the input and output such as totals and check values.
240 
241  in() should return zero on failure. out() should return non-zero on
242  failure. If either in() or out() fails, than inflateBack() returns a
243  Z_BUF_ERROR. strm->next_in can be checked for Z_NULL to see whether it
244  was in() or out() that caused in the error. Otherwise, inflateBack()
245  returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
246  error, or Z_MEM_ERROR if it could not allocate memory for the state.
247  inflateBack() can also return Z_STREAM_ERROR if the input parameters
248  are not correct, i.e. strm is Z_NULL or the state was not initialized.
249  */
250 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
252 in_func in;
253 void FAR *in_desc;
254 out_func out;
255 void FAR *out_desc;
256 {
257  struct inflate_state FAR *state;
258  unsigned char FAR *next; /* next input */
259  unsigned char FAR *put; /* next output */
260  unsigned have, left; /* available input and output */
261  unsigned long hold; /* bit buffer */
262  unsigned bits; /* bits in bit buffer */
263  unsigned copy; /* number of stored or match bytes to copy */
264  unsigned char FAR *from; /* where to copy match bytes from */
265  code here; /* current decoding table entry */
266  code last; /* parent table entry */
267  unsigned len; /* length to copy for repeats, bits to drop */
268  int ret; /* return code */
269  static const unsigned short order[19] = /* permutation of code lengths */
270  {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
271 
272  /* Check that the strm exists and that the state was initialized */
273  if (strm == Z_NULL || strm->state == Z_NULL)
274  return Z_STREAM_ERROR;
275  state = (struct inflate_state FAR *)strm->state;
276 
277  /* Reset the state */
278  strm->msg = Z_NULL;
279  state->mode = TYPE;
280  state->last = 0;
281  state->whave = 0;
282  next = strm->next_in;
283  have = next != Z_NULL ? strm->avail_in : 0;
284  hold = 0;
285  bits = 0;
286  put = state->window;
287  left = state->wsize;
288 
289  /* Inflate until end of block marked as last */
290  for (;;)
291  switch (state->mode) {
292  case TYPE:
293  /* determine and dispatch block type */
294  if (state->last) {
295  BYTEBITS();
296  state->mode = DONE;
297  break;
298  }
299  NEEDBITS(3);
300  state->last = BITS(1);
301  DROPBITS(1);
302  switch (BITS(2)) {
303  case 0: /* stored block */
304  Tracev((stderr, "inflate: stored block%s\n",
305  state->last ? " (last)" : ""));
306  state->mode = STORED;
307  break;
308  case 1: /* fixed block */
309  fixedtables(state);
310  Tracev((stderr, "inflate: fixed codes block%s\n",
311  state->last ? " (last)" : ""));
312  state->mode = LEN; /* decode codes */
313  break;
314  case 2: /* dynamic block */
315  Tracev((stderr, "inflate: dynamic codes block%s\n",
316  state->last ? " (last)" : ""));
317  state->mode = TABLE;
318  break;
319  case 3:
320  strm->msg = (char *)"invalid block type";
321  state->mode = BAD;
322  }
323  DROPBITS(2);
324  break;
325 
326  case STORED:
327  /* get and verify stored block length */
328  BYTEBITS(); /* go to byte boundary */
329  NEEDBITS(32);
330  if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
331  strm->msg = (char *)"invalid stored block lengths";
332  state->mode = BAD;
333  break;
334  }
335  state->length = (unsigned)hold & 0xffff;
336  Tracev((stderr, "inflate: stored length %u\n",
337  state->length));
338  INITBITS();
339 
340  /* copy stored block from input to output */
341  while (state->length != 0) {
342  copy = state->length;
343  PULL();
344  ROOM();
345  if (copy > have) copy = have;
346  if (copy > left) copy = left;
347  zmemcpy(put, next, copy);
348  have -= copy;
349  next += copy;
350  left -= copy;
351  put += copy;
352  state->length -= copy;
353  }
354  Tracev((stderr, "inflate: stored end\n"));
355  state->mode = TYPE;
356  break;
357 
358  case TABLE:
359  /* get dynamic table entries descriptor */
360  NEEDBITS(14);
361  state->nlen = BITS(5) + 257;
362  DROPBITS(5);
363  state->ndist = BITS(5) + 1;
364  DROPBITS(5);
365  state->ncode = BITS(4) + 4;
366  DROPBITS(4);
367 #ifndef PKZIP_BUG_WORKAROUND
368  if (state->nlen > 286 || state->ndist > 30) {
369  strm->msg = (char *)"too many length or distance symbols";
370  state->mode = BAD;
371  break;
372  }
373 #endif
374  Tracev((stderr, "inflate: table sizes ok\n"));
375 
376  /* get code length code lengths (not a typo) */
377  state->have = 0;
378  while (state->have < state->ncode) {
379  NEEDBITS(3);
380  state->lens[order[state->have++]] = (unsigned short)BITS(3);
381  DROPBITS(3);
382  }
383  while (state->have < 19)
384  state->lens[order[state->have++]] = 0;
385  state->next = state->codes;
386  state->lencode = (code const FAR *)(state->next);
387  state->lenbits = 7;
388  ret = inflate_table(CODES, state->lens, 19, &(state->next),
389  &(state->lenbits), state->work);
390  if (ret) {
391  strm->msg = (char *)"invalid code lengths set";
392  state->mode = BAD;
393  break;
394  }
395  Tracev((stderr, "inflate: code lengths ok\n"));
396 
397  /* get length and distance code code lengths */
398  state->have = 0;
399  while (state->have < state->nlen + state->ndist) {
400  for (;;) {
401  here = state->lencode[BITS(state->lenbits)];
402  if ((unsigned)(here.bits) <= bits) break;
403  PULLBYTE();
404  }
405  if (here.val < 16) {
406  DROPBITS(here.bits);
407  state->lens[state->have++] = here.val;
408  }
409  else {
410  if (here.val == 16) {
411  NEEDBITS(here.bits + 2);
412  DROPBITS(here.bits);
413  if (state->have == 0) {
414  strm->msg = (char *)"invalid bit length repeat";
415  state->mode = BAD;
416  break;
417  }
418  len = (unsigned)(state->lens[state->have - 1]);
419  copy = 3 + BITS(2);
420  DROPBITS(2);
421  }
422  else if (here.val == 17) {
423  NEEDBITS(here.bits + 3);
424  DROPBITS(here.bits);
425  len = 0;
426  copy = 3 + BITS(3);
427  DROPBITS(3);
428  }
429  else {
430  NEEDBITS(here.bits + 7);
431  DROPBITS(here.bits);
432  len = 0;
433  copy = 11 + BITS(7);
434  DROPBITS(7);
435  }
436  if (state->have + copy > state->nlen + state->ndist) {
437  strm->msg = (char *)"invalid bit length repeat";
438  state->mode = BAD;
439  break;
440  }
441  while (copy--)
442  state->lens[state->have++] = (unsigned short)len;
443  }
444  }
445 
446  /* handle error breaks in while */
447  if (state->mode == BAD) break;
448 
449  /* check for end-of-block code (better have one) */
450  if (state->lens[256] == 0) {
451  strm->msg = (char *)"invalid code -- missing end-of-block";
452  state->mode = BAD;
453  break;
454  }
455 
456  /* build code tables -- note: do not change the lenbits or distbits
457  values here (9 and 6) without reading the comments in inftrees.h
458  concerning the ENOUGH constants, which depend on those values */
459  state->next = state->codes;
460  state->lencode = (code const FAR *)(state->next);
461  state->lenbits = 9;
462  ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
463  &(state->lenbits), state->work);
464  if (ret) {
465  strm->msg = (char *)"invalid literal/lengths set";
466  state->mode = BAD;
467  break;
468  }
469  state->distcode = (code const FAR *)(state->next);
470  state->distbits = 6;
471  ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
472  &(state->next), &(state->distbits), state->work);
473  if (ret) {
474  strm->msg = (char *)"invalid distances set";
475  state->mode = BAD;
476  break;
477  }
478  Tracev((stderr, "inflate: codes ok\n"));
479  state->mode = LEN;
480 
481  case LEN:
482  /* use inflate_fast() if we have enough input and output */
483  if (have >= 6 && left >= 258) {
484  RESTORE();
485  if (state->whave < state->wsize)
486  state->whave = state->wsize - left;
487  inflate_fast(strm, state->wsize);
488  LOAD();
489  break;
490  }
491 
492  /* get a literal, length, or end-of-block code */
493  for (;;) {
494  here = state->lencode[BITS(state->lenbits)];
495  if ((unsigned)(here.bits) <= bits) break;
496  PULLBYTE();
497  }
498  if (here.op && (here.op & 0xf0) == 0) {
499  last = here;
500  for (;;) {
501  here = state->lencode[last.val +
502  (BITS(last.bits + last.op) >> last.bits)];
503  if ((unsigned)(last.bits + here.bits) <= bits) break;
504  PULLBYTE();
505  }
506  DROPBITS(last.bits);
507  }
508  DROPBITS(here.bits);
509  state->length = (unsigned)here.val;
510 
511  /* process literal */
512  if (here.op == 0) {
513  Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
514  "inflate: literal '%c'\n" :
515  "inflate: literal 0x%02x\n", here.val));
516  ROOM();
517  *put++ = (unsigned char)(state->length);
518  left--;
519  state->mode = LEN;
520  break;
521  }
522 
523  /* process end of block */
524  if (here.op & 32) {
525  Tracevv((stderr, "inflate: end of block\n"));
526  state->mode = TYPE;
527  break;
528  }
529 
530  /* invalid code */
531  if (here.op & 64) {
532  strm->msg = (char *)"invalid literal/length code";
533  state->mode = BAD;
534  break;
535  }
536 
537  /* length code -- get extra bits, if any */
538  state->extra = (unsigned)(here.op) & 15;
539  if (state->extra != 0) {
540  NEEDBITS(state->extra);
541  state->length += BITS(state->extra);
542  DROPBITS(state->extra);
543  }
544  Tracevv((stderr, "inflate: length %u\n", state->length));
545 
546  /* get distance code */
547  for (;;) {
548  here = state->distcode[BITS(state->distbits)];
549  if ((unsigned)(here.bits) <= bits) break;
550  PULLBYTE();
551  }
552  if ((here.op & 0xf0) == 0) {
553  last = here;
554  for (;;) {
555  here = state->distcode[last.val +
556  (BITS(last.bits + last.op) >> last.bits)];
557  if ((unsigned)(last.bits + here.bits) <= bits) break;
558  PULLBYTE();
559  }
560  DROPBITS(last.bits);
561  }
562  DROPBITS(here.bits);
563  if (here.op & 64) {
564  strm->msg = (char *)"invalid distance code";
565  state->mode = BAD;
566  break;
567  }
568  state->offset = (unsigned)here.val;
569 
570  /* get distance extra bits, if any */
571  state->extra = (unsigned)(here.op) & 15;
572  if (state->extra != 0) {
573  NEEDBITS(state->extra);
574  state->offset += BITS(state->extra);
575  DROPBITS(state->extra);
576  }
577  if (state->offset > state->wsize - (state->whave < state->wsize ?
578  left : 0)) {
579  strm->msg = (char *)"invalid distance too far back";
580  state->mode = BAD;
581  break;
582  }
583  Tracevv((stderr, "inflate: distance %u\n", state->offset));
584 
585  /* copy match from window to output */
586  do {
587  ROOM();
588  copy = state->wsize - state->offset;
589  if (copy < left) {
590  from = put + copy;
591  copy = left - copy;
592  }
593  else {
594  from = put - state->offset;
595  copy = left;
596  }
597  if (copy > state->length) copy = state->length;
598  state->length -= copy;
599  left -= copy;
600  do {
601  *put++ = *from++;
602  } while (--copy);
603  } while (state->length != 0);
604  break;
605 
606  case DONE:
607  /* inflate stream terminated properly -- write leftover output */
608  ret = Z_STREAM_END;
609  if (left < state->wsize) {
610  if (out(out_desc, state->window, state->wsize - left))
611  ret = Z_BUF_ERROR;
612  }
613  goto inf_leave;
614 
615  case BAD:
616  ret = Z_DATA_ERROR;
617  goto inf_leave;
618 
619  default: /* can't happen, but makes compilers happy */
620  ret = Z_STREAM_ERROR;
621  goto inf_leave;
622  }
623 
624  /* Return unused input */
625  inf_leave:
626  strm->next_in = next;
627  strm->avail_in = have;
628  return ret;
629 }
630 
632 z_streamp strm;
633 {
634  if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
635  return Z_STREAM_ERROR;
636  ZFREE(strm, strm->state);
637  strm->state = Z_NULL;
638  Tracev((stderr, "inflate: end\n"));
639  return Z_OK;
640 }