Watt-32 tcp/ip  2.2 dev-rel.10
zinflate.c
1 /* inflate.c -- zlib decompression
2  * Copyright (C) 1995-2003 Mark Adler
3  * For conditions of distribution and use, see copyright notice in zlib.h
4  */
5 
6 /*
7  * Change history:
8  *
9  * 1.2.beta0 24 Nov 2002
10  * - First version -- complete rewrite of inflate to simplify code, avoid
11  * creation of window when not needed, minimize use of window when it is
12  * needed, make inffast.c even faster, implement gzip decoding, and to
13  * improve code readability and style over the previous zlib inflate code
14  *
15  * 1.2.beta1 25 Nov 2002
16  * - Use pointers for available input and output checking in inffast.c
17  * - Remove input and output counters in inffast.c
18  * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
19  * - Remove unnecessary second byte pull from length extra in inffast.c
20  * - Unroll direct copy to three copies per loop in inffast.c
21  *
22  * 1.2.beta2 4 Dec 2002
23  * - Change external routine names to reduce potential conflicts
24  * - Correct filename to inffixed.h for fixed tables in inflate.c
25  * - Make hbuf[] unsigned char to match parameter type in inflate.c
26  * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
27  * to avoid negation problem on Alphas (64 bit) in inflate.c
28  *
29  * 1.2.beta3 22 Dec 2002
30  * - Add comments on state->bits assertion in inffast.c
31  * - Add comments on op field in inftrees.h
32  * - Fix bug in reuse of allocated window after inflateReset()
33  * - Remove bit fields--back to byte structure for speed
34  * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
35  * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
36  * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
37  * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
38  * - Use local copies of stream next and avail values, as well as local bit
39  * buffer and bit count in inflate()--for speed when inflate_fast() not used
40  *
41  * 1.2.beta4 1 Jan 2003
42  * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43  * - Move a comment on output buffer sizes from inffast.c to inflate.c
44  * - Add comments in inffast.c to introduce the inflate_fast() routine
45  * - Rearrange window copies in inflate_fast() for speed and simplification
46  * - Unroll last copy for window match in inflate_fast()
47  * - Use local copies of window variables in inflate_fast() for speed
48  * - Pull out common write == 0 case for speed in inflate_fast()
49  * - Make op and len in inflate_fast() unsigned for consistency
50  * - Add FAR to lcode and dcode declarations in inflate_fast()
51  * - Simplified bad distance check in inflate_fast()
52  * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53  * source file infback.c to provide a call-back interface to inflate for
54  * programs like gzip and unzip -- uses window as output buffer to avoid
55  * window copying
56  *
57  * 1.2.beta5 1 Jan 2003
58  * - Improved inflateBack() interface to allow the caller to provide initial
59  * input in strm.
60  * - Fixed stored blocks bug in inflateBack()
61  *
62  * 1.2.beta6 4 Jan 2003
63  * - Added comments in inffast.c on effectiveness of POSTINC
64  * - Typecasting all around to reduce compiler warnings
65  * - Changed loops from while (1) or do {} while (1) to for (;;), again to
66  * make compilers happy
67  * - Changed type of window in inflateBackInit() to unsigned char *
68  *
69  * 1.2.beta7 27 Jan 2003
70  * - Changed many types to unsigned or unsigned short to avoid warnings
71  * - Added inflateCopy() function
72  *
73  * 1.2.0 9 Mar 2003
74  * - Changed inflateBack() interface to provide separate opaque descriptors
75  * for the in() and out() functions
76  * - Changed inflateBack() argument and in_func typedef to swap the length
77  * and buffer address return values for the input function
78  * - Check next_in and next_out for Z_NULL on entry to inflate()
79  *
80  * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
81  */
82 
83 #include "wattcp.h"
84 #include "zutil.h"
85 #include "zinftree.h"
86 #include "zinflate.h"
87 #include "zinffast.h"
88 
89 #if defined(USE_GZIP) && !defined(Z_NO_INFLATE)
90 
91 #ifdef MAKEFIXED
92 # ifndef BUILDFIXED
93 # define BUILDFIXED
94 # endif
95 #endif
96 
97 /* function prototypes */
98 local void fixedtables OF((struct inflate_state FAR *state));
99 local int updatewindow OF((z_streamp strm, unsigned out));
100 #ifdef BUILDFIXED
101  void makefixed OF((void));
102 #endif
103 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
104  unsigned len));
105 
106 int ZEXPORT inflateReset(strm)
107 z_streamp strm;
108 {
109  struct inflate_state FAR *state;
110 
111  if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
112  state = (struct inflate_state FAR *)strm->state;
113  strm->total_in = strm->total_out = state->total = 0;
114  strm->msg = Z_NULL;
115  state->mode = HEAD;
116  state->last = 0;
117  state->havedict = 0;
118  state->wsize = 0;
119  state->whave = 0;
120  state->hold = 0;
121  state->bits = 0;
122  state->lencode = state->distcode = state->next = state->codes;
123  Tracev((stderr, "inflate: reset\n"));
124  return Z_OK;
125 }
126 
127 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
128 z_streamp strm;
129 int windowBits;
130 const char *version;
131 int stream_size;
132 {
133  struct inflate_state FAR *state;
134 
135  if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
136  stream_size != (int)(sizeof(z_stream)))
137  return Z_VERSION_ERROR;
138  if (strm == Z_NULL) return Z_STREAM_ERROR;
139  strm->msg = Z_NULL; /* in case we return an error */
140  if (strm->zalloc == (alloc_func)0) {
141  strm->zalloc = zcalloc;
142  strm->opaque = (voidpf)0;
143  }
144  if (strm->zfree == (free_func)0) strm->zfree = zcfree;
145  state = (struct inflate_state FAR *)
146  ZALLOC(strm, 1, sizeof(struct inflate_state));
147  if (state == Z_NULL) return Z_MEM_ERROR;
148  Tracev((stderr, "inflate: allocated\n"));
149  strm->state = (voidpf)state;
150  if (windowBits < 0) {
151  state->wrap = 0;
152  windowBits = -windowBits;
153  }
154  else {
155  state->wrap = (windowBits >> 4) + 1;
156 #ifdef GUNZIP
157  if (windowBits < 48) windowBits &= 15;
158 #endif
159  }
160  if (windowBits < 8 || windowBits > 15) {
161  ZFREE(strm, state);
162  strm->state = Z_NULL;
163  return Z_STREAM_ERROR;
164  }
165  state->wbits = (unsigned)windowBits;
166  state->window = Z_NULL;
167  return inflateReset(strm);
168 }
169 
170 int ZEXPORT inflateInit_(strm, version, stream_size)
171 z_streamp strm;
172 const char *version;
173 int stream_size;
174 {
175  return inflateInit2_(strm, DEF_WBITS, version, stream_size);
176 }
177 
178 /*
179  Return state with length and distance decoding tables and index sizes set to
180  fixed code decoding. Normally this returns fixed tables from inffixed.h.
181  If BUILDFIXED is defined, then instead this routine builds the tables the
182  first time it's called, and returns those tables the first time and
183  thereafter. This reduces the size of the code by about 2K bytes, in
184  exchange for a little execution time. However, BUILDFIXED should not be
185  used for threaded applications, since the rewriting of the tables and virgin
186  may not be thread-safe.
187  */
188 local void fixedtables(state)
189 struct inflate_state FAR *state;
190 {
191 #ifdef BUILDFIXED
192  static int virgin = 1;
193  static code *lenfix, *distfix;
194  static code fixed[544];
195 
196  /* build fixed huffman tables if first call (may not be thread safe) */
197  if (virgin) {
198  unsigned sym, bits;
199  static code *next;
200 
201  /* literal/length table */
202  sym = 0;
203  while (sym < 144) state->lens[sym++] = 8;
204  while (sym < 256) state->lens[sym++] = 9;
205  while (sym < 280) state->lens[sym++] = 7;
206  while (sym < 288) state->lens[sym++] = 8;
207  next = fixed;
208  lenfix = next;
209  bits = 9;
210  inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
211 
212  /* distance table */
213  sym = 0;
214  while (sym < 32) state->lens[sym++] = 5;
215  distfix = next;
216  bits = 5;
217  inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
218 
219  /* do this just once */
220  virgin = 0;
221  }
222 #else /* !BUILDFIXED */
223 # include "zinffix.h"
224 #endif /* BUILDFIXED */
225  state->lencode = lenfix;
226  state->lenbits = 9;
227  state->distcode = distfix;
228  state->distbits = 5;
229 }
230 
231 #ifdef MAKEFIXED
232 #include <stdio.h>
233 
234 /*
235  Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
236  defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
237  those tables to stdout, which would be piped to inffixed.h. A small program
238  can simply call makefixed to do this:
239 
240  void makefixed(void);
241 
242  int main(void)
243  {
244  makefixed();
245  return 0;
246  }
247 
248  Then that can be linked with zlib built with MAKEFIXED defined and run:
249 
250  a.out > inffixed.h
251  */
252 void makefixed()
253 {
254  unsigned low, size;
255  struct inflate_state state;
256 
257  fixedtables(&state);
258  puts(" /* inffixed.h -- table for decoding fixed codes");
259  puts(" * Generated automatically by makefixed().");
260  puts(" */");
261  puts("");
262  puts(" /* WARNING: this file should *not* be used by applications.");
263  puts(" It is part of the implementation of this library and is");
264  puts(" subject to change. Applications should only use zlib.h.");
265  puts(" */");
266  puts("");
267  size = 1U << 9;
268  printf(" static const code lenfix[%u] = {", size);
269  low = 0;
270  for (;;) {
271  if ((low % 7) == 0) printf("\n ");
272  printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
273  state.lencode[low].val);
274  if (++low == size) break;
275  putchar(',');
276  }
277  puts("\n };");
278  size = 1U << 5;
279  printf("\n static const code distfix[%u] = {", size);
280  low = 0;
281  for (;;) {
282  if ((low % 6) == 0) printf("\n ");
283  printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
284  state.distcode[low].val);
285  if (++low == size) break;
286  putchar(',');
287  }
288  puts("\n };");
289 }
290 #endif /* MAKEFIXED */
291 
292 /*
293  Update the window with the last wsize (normally 32K) bytes written before
294  returning. If window does not exist yet, create it. This is only called
295  when a window is already in use, or when output has been written during this
296  inflate call, but the end of the deflate stream has not been reached yet.
297  It is also called to create a window for dictionary data when a dictionary
298  is loaded.
299 
300  Providing output buffers larger than 32K to inflate() should provide a speed
301  advantage, since only the last 32K of output is copied to the sliding window
302  upon return from inflate(), and since all distances after the first 32K of
303  output will fall in the output data, making match copies simpler and faster.
304  The advantage may be dependent on the size of the processor's data caches.
305  */
306 local int updatewindow(strm, out)
307 z_streamp strm;
308 unsigned out;
309 {
310  struct inflate_state FAR *state;
311  unsigned copy, dist;
312 
313  state = (struct inflate_state FAR *)strm->state;
314 
315  /* if it hasn't been done already, allocate space for the window */
316  if (state->window == Z_NULL) {
317  state->window = (unsigned char FAR *)
318  ZALLOC(strm, 1U << state->wbits,
319  sizeof(unsigned char));
320  if (state->window == Z_NULL) return 1;
321  }
322 
323  /* if window not in use yet, initialize */
324  if (state->wsize == 0) {
325  state->wsize = 1U << state->wbits;
326  state->write = 0;
327  state->whave = 0;
328  }
329 
330  /* copy state->wsize or less output bytes into the circular window */
331  copy = out - strm->avail_out;
332  if (copy >= state->wsize) {
333  zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
334  state->write = 0;
335  state->whave = state->wsize;
336  }
337  else {
338  dist = state->wsize - state->write;
339  if (dist > copy) dist = copy;
340  zmemcpy(state->window + state->write, strm->next_out - copy, dist);
341  copy -= dist;
342  if (copy) {
343  zmemcpy(state->window, strm->next_out - copy, copy);
344  state->write = copy;
345  state->whave = state->wsize;
346  }
347  else {
348  state->write += dist;
349  if (state->write == state->wsize) state->write = 0;
350  if (state->whave < state->wsize) state->whave += dist;
351  }
352  }
353  return 0;
354 }
355 
356 /* Macros for inflate(): */
357 
358 /* check function to use adler32() for zlib or crc32() for gzip */
359 #ifdef GUNZIP
360 # define UPDATE(check, buf, len) \
361  (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
362 #else
363 # define UPDATE(check, buf, len) adler32(check, buf, len)
364 #endif
365 
366 /* check macros for header crc */
367 #ifdef GUNZIP
368 # define CRC2(check, word) \
369  do { \
370  hbuf[0] = (unsigned char)(word); \
371  hbuf[1] = (unsigned char)((word) >> 8); \
372  check = crc32(check, hbuf, 2); \
373  } while (0)
374 
375 # define CRC4(check, word) \
376  do { \
377  hbuf[0] = (unsigned char)(word); \
378  hbuf[1] = (unsigned char)((word) >> 8); \
379  hbuf[2] = (unsigned char)((word) >> 16); \
380  hbuf[3] = (unsigned char)((word) >> 24); \
381  check = crc32(check, hbuf, 4); \
382  } while (0)
383 #endif
384 
385 /* Load registers with state in inflate() for speed */
386 #define LOAD() \
387  do { \
388  put = strm->next_out; \
389  left = strm->avail_out; \
390  next = strm->next_in; \
391  have = strm->avail_in; \
392  hold = state->hold; \
393  bits = state->bits; \
394  } while (0)
395 
396 /* Restore state from registers in inflate() */
397 #define RESTORE() \
398  do { \
399  strm->next_out = put; \
400  strm->avail_out = left; \
401  strm->next_in = next; \
402  strm->avail_in = have; \
403  state->hold = hold; \
404  state->bits = bits; \
405  } while (0)
406 
407 /* Clear the input bit accumulator */
408 #define INITBITS() \
409  do { \
410  hold = 0; \
411  bits = 0; \
412  } while (0)
413 
414 /* Get a byte of input into the bit accumulator, or return from inflate()
415  if there is no input available. */
416 #define PULLBYTE() \
417  do { \
418  if (have == 0) goto inf_leave; \
419  have--; \
420  hold += (unsigned long)(*next++) << bits; \
421  bits += 8; \
422  } while (0)
423 
424 /* Assure that there are at least n bits in the bit accumulator. If there is
425  not enough available input to do that, then return from inflate(). */
426 #define NEEDBITS(n) \
427  do { \
428  while (bits < (unsigned)(n)) \
429  PULLBYTE(); \
430  } while (0)
431 
432 /* Return the low n bits of the bit accumulator (n < 16) */
433 #define BITS(n) \
434  ((unsigned)hold & ((1U << (n)) - 1))
435 
436 /* Remove n bits from the bit accumulator */
437 #define DROPBITS(n) \
438  do { \
439  hold >>= (n); \
440  bits -= (unsigned)(n); \
441  } while (0)
442 
443 /* Remove zero to seven bits as needed to go to a byte boundary */
444 #define BYTEBITS() \
445  do { \
446  hold >>= bits & 7; \
447  bits -= bits & 7; \
448  } while (0)
449 
450 /* Reverse the bytes in a 32-bit value */
451 #define REVERSE(q) \
452  ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
453  (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
454 
455 /*
456  inflate() uses a state machine to process as much input data and generate as
457  much output data as possible before returning. The state machine is
458  structured roughly as follows:
459 
460  for (;;) switch (state) {
461  ...
462  case STATEn:
463  if (not enough input data or output space to make progress)
464  return;
465  ... make progress ...
466  state = STATEm;
467  break;
468  ...
469  }
470 
471  so when inflate() is called again, the same case is attempted again, and
472  if the appropriate resources are provided, the machine proceeds to the
473  next state. The NEEDBITS() macro is usually the way the state evaluates
474  whether it can proceed or should return. NEEDBITS() does the return if
475  the requested bits are not available. The typical use of the BITS macros
476  is:
477 
478  NEEDBITS(n);
479  ... do something with BITS(n) ...
480  DROPBITS(n);
481 
482  where NEEDBITS(n) either returns from inflate() if there isn't enough
483  input left to load n bits into the accumulator, or it continues. BITS(n)
484  gives the low n bits in the accumulator. When done, DROPBITS(n) drops
485  the low n bits off the accumulator. INITBITS() clears the accumulator
486  and sets the number of available bits to zero. BYTEBITS() discards just
487  enough bits to put the accumulator on a byte boundary. After BYTEBITS()
488  and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
489 
490  NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
491  if there is no input available. The decoding of variable length codes uses
492  PULLBYTE() directly in order to pull just enough bytes to decode the next
493  code, and no more.
494 
495  Some states loop until they get enough input, making sure that enough
496  state information is maintained to continue the loop where it left off
497  if NEEDBITS() returns in the loop. For example, want, need, and keep
498  would all have to actually be part of the saved state in case NEEDBITS()
499  returns:
500 
501  case STATEw:
502  while (want < need) {
503  NEEDBITS(n);
504  keep[want++] = BITS(n);
505  DROPBITS(n);
506  }
507  state = STATEx;
508  case STATEx:
509 
510  As shown above, if the next state is also the next case, then the break
511  is omitted.
512 
513  A state may also return if there is not enough output space available to
514  complete that state. Those states are copying stored data, writing a
515  literal byte, and copying a matching string.
516 
517  When returning, a "goto inf_leave" is used to update the total counters,
518  update the check value, and determine whether any progress has been made
519  during that inflate() call in order to return the proper return code.
520  Progress is defined as a change in either strm->avail_in or strm->avail_out.
521  When there is a window, goto inf_leave will update the window with the last
522  output written. If a goto inf_leave occurs in the middle of decompression
523  and there is no window currently, goto inf_leave will create one and copy
524  output to the window for the next call of inflate().
525 
526  In this implementation, the flush parameter of inflate() only affects the
527  return code (per zlib.h). inflate() always writes as much as possible to
528  strm->next_out, given the space available and the provided input--the effect
529  documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
530  the allocation of and copying into a sliding window until necessary, which
531  provides the effect documented in zlib.h for Z_FINISH when the entire input
532  stream available. So the only thing the flush parameter actually does is:
533  when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
534  will return Z_BUF_ERROR if it has not reached the end of the stream.
535  */
536 
537 int ZEXPORT inflate(strm, flush)
538 z_streamp strm;
539 int flush;
540 {
541  struct inflate_state FAR *state;
542  unsigned char FAR *next; /* next input */
543  unsigned char FAR *put; /* next output */
544  unsigned have, left; /* available input and output */
545  unsigned long hold; /* bit buffer */
546  unsigned bits; /* bits in bit buffer */
547  unsigned in, out; /* save starting available input and output */
548  unsigned copy; /* number of stored or match bytes to copy */
549  unsigned char FAR *from; /* where to copy match bytes from */
550  code this; /* current decoding table entry */
551  code last; /* parent table entry */
552  unsigned len; /* length to copy for repeats, bits to drop */
553  int ret; /* return code */
554 #ifdef GUNZIP
555  unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
556 #endif
557  static const unsigned short order[19] = /* permutation of code lengths */
558  {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
559 
560  if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
561  (strm->next_in == Z_NULL && strm->avail_in != 0))
562  return Z_STREAM_ERROR;
563 
564  state = (struct inflate_state FAR *)strm->state;
565  if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
566  LOAD();
567  in = have;
568  out = left;
569  ret = Z_OK;
570  for (;;)
571  switch (state->mode) {
572  case HEAD:
573  if (state->wrap == 0) {
574  state->mode = TYPEDO;
575  break;
576  }
577  NEEDBITS(16);
578 #ifdef GUNZIP
579  if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
580  state->check = crc32(0L, Z_NULL, 0);
581  CRC2(state->check, hold);
582  INITBITS();
583  state->mode = FLAGS;
584  break;
585  }
586  state->flags = 0; /* expect zlib header */
587  if (!(state->wrap & 1) || /* check if zlib header allowed */
588 #else
589  if (
590 #endif
591  ((BITS(8) << 8) + (hold >> 8)) % 31) {
592  strm->msg = (char *)"incorrect header check";
593  state->mode = BAD;
594  break;
595  }
596  if (BITS(4) != Z_DEFLATED) {
597  strm->msg = (char *)"unknown compression method";
598  state->mode = BAD;
599  break;
600  }
601  DROPBITS(4);
602  if (BITS(4) + 8 > state->wbits) {
603  strm->msg = (char *)"invalid window size";
604  state->mode = BAD;
605  break;
606  }
607  Tracev((stderr, "inflate: zlib header ok\n"));
608  strm->adler = state->check = adler32(0L, Z_NULL, 0);
609  state->mode = hold & 0x200 ? DICTID : TYPE;
610  INITBITS();
611  break;
612 #ifdef GUNZIP
613  case FLAGS:
614  NEEDBITS(16);
615  state->flags = (int)(hold);
616  if ((state->flags & 0xff) != Z_DEFLATED) {
617  strm->msg = (char *)"unknown compression method";
618  state->mode = BAD;
619  break;
620  }
621  if (state->flags & 0xe000) {
622  strm->msg = (char *)"unknown header flags set";
623  state->mode = BAD;
624  break;
625  }
626  if (state->flags & 0x0200) CRC2(state->check, hold);
627  INITBITS();
628  state->mode = TIME;
629  case TIME:
630  NEEDBITS(32);
631  if (state->flags & 0x0200) CRC4(state->check, hold);
632  INITBITS();
633  state->mode = OS;
634  case OS:
635  NEEDBITS(16);
636  if (state->flags & 0x0200) CRC2(state->check, hold);
637  INITBITS();
638  state->mode = EXLEN;
639  case EXLEN:
640  if (state->flags & 0x0400) {
641  NEEDBITS(16);
642  state->length = (unsigned)(hold);
643  if (state->flags & 0x0200) CRC2(state->check, hold);
644  INITBITS();
645  }
646  state->mode = EXTRA;
647  case EXTRA:
648  if (state->flags & 0x0400) {
649  copy = state->length;
650  if (copy > have) copy = have;
651  if (copy) {
652  if (state->flags & 0x0200)
653  state->check = crc32(state->check, next, copy);
654  have -= copy;
655  next += copy;
656  state->length -= copy;
657  }
658  if (state->length) goto inf_leave;
659  }
660  state->mode = NAME;
661  case NAME:
662  if (state->flags & 0x0800) {
663  if (have == 0) goto inf_leave;
664  copy = 0;
665  do {
666  len = (unsigned)(next[copy++]);
667  } while (len && copy < have);
668  if (state->flags & 0x02000)
669  state->check = crc32(state->check, next, copy);
670  have -= copy;
671  next += copy;
672  if (len) goto inf_leave;
673  }
674  state->mode = COMMENT;
675  case COMMENT:
676  if (state->flags & 0x1000) {
677  if (have == 0) goto inf_leave;
678  copy = 0;
679  do {
680  len = (unsigned)(next[copy++]);
681  } while (len && copy < have);
682  if (state->flags & 0x02000)
683  state->check = crc32(state->check, next, copy);
684  have -= copy;
685  next += copy;
686  if (len) goto inf_leave;
687  }
688  state->mode = HCRC;
689  case HCRC:
690  if (state->flags & 0x0200) {
691  NEEDBITS(16);
692  if (hold != (state->check & 0xffff)) {
693  strm->msg = (char *)"header crc mismatch";
694  state->mode = BAD;
695  break;
696  }
697  INITBITS();
698  }
699  strm->adler = state->check = crc32(0L, Z_NULL, 0);
700  state->mode = TYPE;
701  break;
702 #endif
703  case DICTID:
704  NEEDBITS(32);
705  strm->adler = state->check = REVERSE(hold);
706  INITBITS();
707  state->mode = DICT;
708  case DICT:
709  if (state->havedict == 0) {
710  RESTORE();
711  return Z_NEED_DICT;
712  }
713  strm->adler = state->check = adler32(0L, Z_NULL, 0);
714  state->mode = TYPE;
715  case TYPE:
716  if (flush == Z_BLOCK) goto inf_leave;
717  case TYPEDO:
718  if (state->last) {
719  BYTEBITS();
720  state->mode = CHECK;
721  break;
722  }
723  NEEDBITS(3);
724  state->last = BITS(1);
725  DROPBITS(1);
726  switch (BITS(2)) {
727  case 0: /* stored block */
728  Tracev((stderr, "inflate: stored block%s\n",
729  state->last ? " (last)" : ""));
730  state->mode = STORED;
731  break;
732  case 1: /* fixed block */
733  fixedtables(state);
734  Tracev((stderr, "inflate: fixed codes block%s\n",
735  state->last ? " (last)" : ""));
736  state->mode = LEN; /* decode codes */
737  break;
738  case 2: /* dynamic block */
739  Tracev((stderr, "inflate: dynamic codes block%s\n",
740  state->last ? " (last)" : ""));
741  state->mode = TABLE;
742  break;
743  case 3:
744  strm->msg = (char *)"invalid block type";
745  state->mode = BAD;
746  }
747  DROPBITS(2);
748  break;
749  case STORED:
750  BYTEBITS(); /* go to byte boundary */
751  NEEDBITS(32);
752  if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
753  strm->msg = (char *)"invalid stored block lengths";
754  state->mode = BAD;
755  break;
756  }
757  state->length = (unsigned)hold & 0xffff;
758  Tracev((stderr, "inflate: stored length %u\n",
759  state->length));
760  INITBITS();
761  state->mode = COPY;
762  case COPY:
763  copy = state->length;
764  if (copy) {
765  if (copy > have) copy = have;
766  if (copy > left) copy = left;
767  if (copy == 0) goto inf_leave;
768  zmemcpy(put, next, copy);
769  have -= copy;
770  next += copy;
771  left -= copy;
772  put += copy;
773  state->length -= copy;
774  break;
775  }
776  Tracev((stderr, "inflate: stored end\n"));
777  state->mode = TYPE;
778  break;
779  case TABLE:
780  NEEDBITS(14);
781  state->nlen = BITS(5) + 257;
782  DROPBITS(5);
783  state->ndist = BITS(5) + 1;
784  DROPBITS(5);
785  state->ncode = BITS(4) + 4;
786  DROPBITS(4);
787 #ifndef PKZIP_BUG_WORKAROUND
788  if (state->nlen > 286 || state->ndist > 30) {
789  strm->msg = (char *)"too many length or distance symbols";
790  state->mode = BAD;
791  break;
792  }
793 #endif
794  Tracev((stderr, "inflate: table sizes ok\n"));
795  state->have = 0;
796  state->mode = LENLENS;
797  case LENLENS:
798  while (state->have < state->ncode) {
799  NEEDBITS(3);
800  state->lens[order[state->have++]] = (unsigned short)BITS(3);
801  DROPBITS(3);
802  }
803  while (state->have < 19)
804  state->lens[order[state->have++]] = 0;
805  state->next = state->codes;
806  state->lencode = (code const FAR *)(state->next);
807  state->lenbits = 7;
808  ret = inflate_table(CODES, state->lens, 19, &(state->next),
809  &(state->lenbits), state->work);
810  if (ret) {
811  strm->msg = (char *)"invalid code lengths set";
812  state->mode = BAD;
813  break;
814  }
815  Tracev((stderr, "inflate: code lengths ok\n"));
816  state->have = 0;
817  state->mode = CODELENS;
818  case CODELENS:
819  while (state->have < state->nlen + state->ndist) {
820  for (;;) {
821  this = state->lencode[BITS(state->lenbits)];
822  if ((unsigned)(this.bits) <= bits) break;
823  PULLBYTE();
824  }
825  if (this.val < 16) {
826  NEEDBITS(this.bits);
827  DROPBITS(this.bits);
828  state->lens[state->have++] = this.val;
829  }
830  else {
831  if (this.val == 16) {
832  NEEDBITS(this.bits + 2);
833  DROPBITS(this.bits);
834  if (state->have == 0) {
835  strm->msg = (char *)"invalid bit length repeat";
836  state->mode = BAD;
837  break;
838  }
839  len = state->lens[state->have - 1];
840  copy = 3 + BITS(2);
841  DROPBITS(2);
842  }
843  else if (this.val == 17) {
844  NEEDBITS(this.bits + 3);
845  DROPBITS(this.bits);
846  len = 0;
847  copy = 3 + BITS(3);
848  DROPBITS(3);
849  }
850  else {
851  NEEDBITS(this.bits + 7);
852  DROPBITS(this.bits);
853  len = 0;
854  copy = 11 + BITS(7);
855  DROPBITS(7);
856  }
857  if (state->have + copy > state->nlen + state->ndist) {
858  strm->msg = (char *)"invalid bit length repeat";
859  state->mode = BAD;
860  break;
861  }
862  while (copy--)
863  state->lens[state->have++] = (unsigned short)len;
864  }
865  }
866 
867  /* build code tables */
868  state->next = state->codes;
869  state->lencode = (code const FAR *)(state->next);
870  state->lenbits = 9;
871  ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
872  &(state->lenbits), state->work);
873  if (ret) {
874  strm->msg = (char *)"invalid literal/lengths set";
875  state->mode = BAD;
876  break;
877  }
878  state->distcode = (code const FAR *)(state->next);
879  state->distbits = 6;
880  ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
881  &(state->next), &(state->distbits), state->work);
882  if (ret) {
883  strm->msg = (char *)"invalid distances set";
884  state->mode = BAD;
885  break;
886  }
887  Tracev((stderr, "inflate: codes ok\n"));
888  state->mode = LEN;
889  case LEN:
890  if (have >= 6 && left >= 258) {
891  RESTORE();
892  inflate_fast(strm, out);
893  LOAD();
894  break;
895  }
896  for (;;) {
897  this = state->lencode[BITS(state->lenbits)];
898  if ((unsigned)(this.bits) <= bits) break;
899  PULLBYTE();
900  }
901  if (this.op && (this.op & 0xf0) == 0) {
902  last = this;
903  for (;;) {
904  this = state->lencode[last.val +
905  (BITS(last.bits + last.op) >> last.bits)];
906  if ((unsigned)(last.bits + this.bits) <= bits) break;
907  PULLBYTE();
908  }
909  DROPBITS(last.bits);
910  }
911  DROPBITS(this.bits);
912  state->length = (unsigned)this.val;
913  if ((int)(this.op) == 0) {
914  Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
915  "inflate: literal '%c'\n" :
916  "inflate: literal 0x%02x\n", this.val));
917  state->mode = LIT;
918  break;
919  }
920  if (this.op & 32) {
921  Tracevv((stderr, "inflate: end of block\n"));
922  state->mode = TYPE;
923  break;
924  }
925  if (this.op & 64) {
926  strm->msg = (char *)"invalid literal/length code";
927  state->mode = BAD;
928  break;
929  }
930  state->extra = (unsigned)(this.op) & 15;
931  state->mode = LENEXT;
932  case LENEXT:
933  if (state->extra) {
934  NEEDBITS(state->extra);
935  state->length += BITS(state->extra);
936  DROPBITS(state->extra);
937  }
938  Tracevv((stderr, "inflate: length %u\n", state->length));
939  state->mode = DIST;
940  case DIST:
941  for (;;) {
942  this = state->distcode[BITS(state->distbits)];
943  if ((unsigned)(this.bits) <= bits) break;
944  PULLBYTE();
945  }
946  if ((this.op & 0xf0) == 0) {
947  last = this;
948  for (;;) {
949  this = state->distcode[last.val +
950  (BITS(last.bits + last.op) >> last.bits)];
951  if ((unsigned)(last.bits + this.bits) <= bits) break;
952  PULLBYTE();
953  }
954  DROPBITS(last.bits);
955  }
956  DROPBITS(this.bits);
957  if (this.op & 64) {
958  strm->msg = (char *)"invalid distance code";
959  state->mode = BAD;
960  break;
961  }
962  state->offset = (unsigned)this.val;
963  state->extra = (unsigned)(this.op) & 15;
964  state->mode = DISTEXT;
965  case DISTEXT:
966  if (state->extra) {
967  NEEDBITS(state->extra);
968  state->offset += BITS(state->extra);
969  DROPBITS(state->extra);
970  }
971  if (state->offset > state->whave + out - left) {
972  strm->msg = (char *)"invalid distance too far back";
973  state->mode = BAD;
974  break;
975  }
976  Tracevv((stderr, "inflate: distance %u\n", state->offset));
977  state->mode = MATCH;
978  case MATCH:
979  if (left == 0) goto inf_leave;
980  copy = out - left;
981  if (state->offset > copy) { /* copy from window */
982  copy = state->offset - copy;
983  if (copy > state->write) {
984  copy -= state->write;
985  from = state->window + (state->wsize - copy);
986  }
987  else
988  from = state->window + (state->write - copy);
989  if (copy > state->length) copy = state->length;
990  }
991  else { /* copy from output */
992  from = put - state->offset;
993  copy = state->length;
994  }
995  if (copy > left) copy = left;
996  left -= copy;
997  state->length -= copy;
998  do {
999  *put++ = *from++;
1000  } while (--copy);
1001  if (state->length == 0) state->mode = LEN;
1002  break;
1003  case LIT:
1004  if (left == 0) goto inf_leave;
1005  *put++ = (unsigned char)(state->length);
1006  left--;
1007  state->mode = LEN;
1008  break;
1009  case CHECK:
1010  if (state->wrap) {
1011  NEEDBITS(32);
1012  out -= left;
1013  strm->total_out += out;
1014  state->total += out;
1015  if (out)
1016  strm->adler = state->check =
1017  UPDATE(state->check, put - out, out);
1018  out = left;
1019  if ((
1020 #ifdef GUNZIP
1021  state->flags ? hold :
1022 #endif
1023  REVERSE(hold)) != state->check) {
1024  strm->msg = (char *)"incorrect data check";
1025  state->mode = BAD;
1026  break;
1027  }
1028  INITBITS();
1029  Tracev((stderr, "inflate: check matches trailer\n"));
1030  }
1031 #ifdef GUNZIP
1032  state->mode = LENGTH;
1033  case LENGTH:
1034  if (state->wrap && state->flags) {
1035  NEEDBITS(32);
1036  if (hold != (state->total & 0xffffffffUL)) {
1037  strm->msg = (char *)"incorrect length check";
1038  state->mode = BAD;
1039  break;
1040  }
1041  INITBITS();
1042  Tracev((stderr, "inflate: length matches trailer\n"));
1043  }
1044 #endif
1045  state->mode = DONE;
1046  case DONE:
1047  ret = Z_STREAM_END;
1048  goto inf_leave;
1049  case BAD:
1050  ret = Z_DATA_ERROR;
1051  goto inf_leave;
1052  case MEM:
1053  return Z_MEM_ERROR;
1054  case SYNC:
1055  default:
1056  return Z_STREAM_ERROR;
1057  }
1058 
1059  /*
1060  Return from inflate(), updating the total counts and the check value.
1061  If there was no progress during the inflate() call, return a buffer
1062  error. Call updatewindow() to create and/or update the window state.
1063  Note: a memory error from inflate() is non-recoverable.
1064  */
1065  inf_leave:
1066  RESTORE();
1067  if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1068  if (updatewindow(strm, out)) {
1069  state->mode = MEM;
1070  return Z_MEM_ERROR;
1071  }
1072  in -= strm->avail_in;
1073  out -= strm->avail_out;
1074  strm->total_in += in;
1075  strm->total_out += out;
1076  state->total += out;
1077  if (state->wrap && out)
1078  strm->adler = state->check =
1079  UPDATE(state->check, strm->next_out - out, out);
1080  strm->data_type = state->bits + (state->last ? 64 : 0) +
1081  (state->mode == TYPE ? 128 : 0);
1082  if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1083  ret = Z_BUF_ERROR;
1084  return ret;
1085 }
1086 
1087 int ZEXPORT inflateEnd(strm)
1088 z_streamp strm;
1089 {
1090  struct inflate_state FAR *state;
1091  if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1092  return Z_STREAM_ERROR;
1093  state = (struct inflate_state FAR *)strm->state;
1094  if (state->window != Z_NULL) ZFREE(strm, state->window);
1095  ZFREE(strm, strm->state);
1096  strm->state = Z_NULL;
1097  Tracev((stderr, "inflate: end\n"));
1098  return Z_OK;
1099 }
1100 
1101 int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1102 z_streamp strm;
1103 const Bytef *dictionary;
1104 uInt dictLength;
1105 {
1106  struct inflate_state FAR *state;
1107  unsigned long id;
1108 
1109  /* check state */
1110  if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1111  state = (struct inflate_state FAR *)strm->state;
1112  if (state->mode != DICT) return Z_STREAM_ERROR;
1113 
1114  /* check for correct dictionary id */
1115  id = adler32(0L, Z_NULL, 0);
1116  id = adler32(id, dictionary, dictLength);
1117  if (id != state->check) return Z_DATA_ERROR;
1118 
1119  /* copy dictionary to window */
1120  if (updatewindow(strm, strm->avail_out)) {
1121  state->mode = MEM;
1122  return Z_MEM_ERROR;
1123  }
1124  if (dictLength > state->wsize) {
1125  zmemcpy(state->window, dictionary + dictLength - state->wsize,
1126  state->wsize);
1127  state->whave = state->wsize;
1128  }
1129  else {
1130  zmemcpy(state->window + state->wsize - dictLength, dictionary,
1131  dictLength);
1132  state->whave = dictLength;
1133  }
1134  state->havedict = 1;
1135  Tracev((stderr, "inflate: dictionary set\n"));
1136  return Z_OK;
1137 }
1138 
1139 /*
1140  Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1141  or when out of input. When called, *have is the number of pattern bytes
1142  found in order so far, in 0..3. On return *have is updated to the new
1143  state. If on return *have equals four, then the pattern was found and the
1144  return value is how many bytes were read including the last byte of the
1145  pattern. If *have is less than four, then the pattern has not been found
1146  yet and the return value is len. In the latter case, syncsearch() can be
1147  called again with more data and the *have state. *have is initialized to
1148  zero for the first call.
1149  */
1150 local unsigned syncsearch(have, buf, len)
1151 unsigned FAR *have;
1152 unsigned char FAR *buf;
1153 unsigned len;
1154 {
1155  unsigned got;
1156  unsigned next;
1157 
1158  got = *have;
1159  next = 0;
1160  while (next < len && got < 4) {
1161  if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1162  got++;
1163  else if (buf[next])
1164  got = 0;
1165  else
1166  got = 4 - got;
1167  next++;
1168  }
1169  *have = got;
1170  return next;
1171 }
1172 
1173 int ZEXPORT inflateSync(strm)
1174 z_streamp strm;
1175 {
1176  unsigned len; /* number of bytes to look at or looked at */
1177  unsigned long in, out; /* temporary to save total_in and total_out */
1178  unsigned char buf[4]; /* to restore bit buffer to byte string */
1179  struct inflate_state FAR *state;
1180 
1181  /* check parameters */
1182  if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1183  state = (struct inflate_state FAR *)strm->state;
1184  if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1185 
1186  /* if first time, start search in bit buffer */
1187  if (state->mode != SYNC) {
1188  state->mode = SYNC;
1189  state->hold <<= state->bits & 7;
1190  state->bits -= state->bits & 7;
1191  len = 0;
1192  while (state->bits >= 8) {
1193  buf[len++] = (unsigned char)(state->hold);
1194  state->hold >>= 8;
1195  state->bits -= 8;
1196  }
1197  state->have = 0;
1198  syncsearch(&(state->have), buf, len);
1199  }
1200 
1201  /* search available input */
1202  len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1203  strm->avail_in -= len;
1204  strm->next_in += len;
1205  strm->total_in += len;
1206 
1207  /* return no joy or set up to restart inflate() on a new block */
1208  if (state->have != 4) return Z_DATA_ERROR;
1209  in = strm->total_in; out = strm->total_out;
1210  inflateReset(strm);
1211  strm->total_in = in; strm->total_out = out;
1212  state->mode = TYPE;
1213  return Z_OK;
1214 }
1215 
1216 /*
1217  Returns true if inflate is currently at the end of a block generated by
1218  Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1219  implementation to provide an additional safety check. PPP uses
1220  Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1221  block. When decompressing, PPP checks that at the end of input packet,
1222  inflate is waiting for these length bytes.
1223  */
1224 int ZEXPORT inflateSyncPoint(strm)
1225 z_streamp strm;
1226 {
1227  struct inflate_state FAR *state;
1228 
1229  if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1230  state = (struct inflate_state FAR *)strm->state;
1231  return state->mode == STORED && state->bits == 0;
1232 }
1233 
1234 int ZEXPORT inflateCopy(dest, source)
1235 z_streamp dest;
1236 z_streamp source;
1237 {
1238  struct inflate_state FAR *state;
1239  struct inflate_state FAR *copy;
1240  unsigned char FAR *window;
1241 
1242  /* check input */
1243  if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
1244  source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
1245  return Z_STREAM_ERROR;
1246  state = (struct inflate_state FAR *)source->state;
1247 
1248  /* allocate space */
1249  copy = (struct inflate_state FAR *)
1250  ZALLOC(source, 1, sizeof(struct inflate_state));
1251  if (copy == Z_NULL) return Z_MEM_ERROR;
1252  window = Z_NULL;
1253  if (state->window != Z_NULL) {
1254  window = (unsigned char FAR *)
1255  ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1256  if (window == Z_NULL) {
1257  ZFREE(source, copy);
1258  return Z_MEM_ERROR;
1259  }
1260  }
1261 
1262  /* copy state */
1263  *dest = *source;
1264  *copy = *state;
1265  copy->lencode = copy->codes + (state->lencode - state->codes);
1266  copy->distcode = copy->codes + (state->distcode - state->codes);
1267  copy->next = copy->codes + (state->next - state->codes);
1268  if (window != Z_NULL)
1269  zmemcpy(window, state->window, 1U << state->wbits);
1270  copy->window = window;
1271  dest->state = (voidpf)copy;
1272  return Z_OK;
1273 }
1274 #endif /* USE_GZIP && !Z_NO_INFLATE */
1275 
Core definitions.
Definition: zinftree.h:24