]> git.saurik.com Git - wxWidgets.git/blob - src/zlib/inflate.c
Fix some bugs
[wxWidgets.git] / src / zlib / inflate.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 "zutil.h"
84 #include "inftrees.h"
85 #include "inflate.h"
86 #include "inffast.h"
87
88 #ifdef MAKEFIXED
89 # ifndef BUILDFIXED
90 # define BUILDFIXED
91 # endif
92 #endif
93
94 /* function prototypes */
95 local void fixedtables OF((struct inflate_state FAR *state));
96 local int updatewindow OF((z_streamp strm, unsigned out));
97 #ifdef BUILDFIXED
98 void makefixed OF((void));
99 #endif
100 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
101 unsigned len));
102
103 int ZEXPORT inflateReset(strm)
104 z_streamp strm;
105 {
106 struct inflate_state FAR *state;
107
108 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
109 state = (struct inflate_state FAR *)strm->state;
110 strm->total_in = strm->total_out = state->total = 0;
111 strm->msg = Z_NULL;
112 state->mode = HEAD;
113 state->last = 0;
114 state->havedict = 0;
115 state->wsize = 0;
116 state->whave = 0;
117 state->hold = 0;
118 state->bits = 0;
119 state->lencode = state->distcode = state->next = state->codes;
120 Tracev((stderr, "inflate: reset\n"));
121 return Z_OK;
122 }
123
124 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
125 z_streamp strm;
126 int windowBits;
127 const char *version;
128 int stream_size;
129 {
130 struct inflate_state FAR *state;
131
132 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
133 stream_size != (int)(sizeof(z_stream)))
134 return Z_VERSION_ERROR;
135 if (strm == Z_NULL) return Z_STREAM_ERROR;
136 strm->msg = Z_NULL; /* in case we return an error */
137 if (strm->zalloc == (alloc_func)0) {
138 strm->zalloc = zcalloc;
139 strm->opaque = (voidpf)0;
140 }
141 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
142 state = (struct inflate_state FAR *)
143 ZALLOC(strm, 1, sizeof(struct inflate_state));
144 if (state == Z_NULL) return Z_MEM_ERROR;
145 Tracev((stderr, "inflate: allocated\n"));
146 strm->state = (voidpf)state;
147 if (windowBits < 0) {
148 state->wrap = 0;
149 windowBits = -windowBits;
150 }
151 else {
152 state->wrap = (windowBits >> 4) + 1;
153 #ifdef GUNZIP
154 if (windowBits < 48) windowBits &= 15;
155 #endif
156 }
157 if (windowBits < 8 || windowBits > 15) {
158 ZFREE(strm, state);
159 strm->state = Z_NULL;
160 return Z_STREAM_ERROR;
161 }
162 state->wbits = (unsigned)windowBits;
163 state->window = Z_NULL;
164 return inflateReset(strm);
165 }
166
167 int ZEXPORT inflateInit_(strm, version, stream_size)
168 z_streamp strm;
169 const char *version;
170 int stream_size;
171 {
172 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
173 }
174
175 /*
176 Return state with length and distance decoding tables and index sizes set to
177 fixed code decoding. Normally this returns fixed tables from inffixed.h.
178 If BUILDFIXED is defined, then instead this routine builds the tables the
179 first time it's called, and returns those tables the first time and
180 thereafter. This reduces the size of the code by about 2K bytes, in
181 exchange for a little execution time. However, BUILDFIXED should not be
182 used for threaded applications, since the rewriting of the tables and virgin
183 may not be thread-safe.
184 */
185 local void fixedtables(state)
186 struct inflate_state FAR *state;
187 {
188 #ifdef BUILDFIXED
189 static int virgin = 1;
190 static code *lenfix, *distfix;
191 static code fixed[544];
192
193 /* build fixed huffman tables if first call (may not be thread safe) */
194 if (virgin) {
195 unsigned sym, bits;
196 static code *next;
197
198 /* literal/length table */
199 sym = 0;
200 while (sym < 144) state->lens[sym++] = 8;
201 while (sym < 256) state->lens[sym++] = 9;
202 while (sym < 280) state->lens[sym++] = 7;
203 while (sym < 288) state->lens[sym++] = 8;
204 next = fixed;
205 lenfix = next;
206 bits = 9;
207 inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
208
209 /* distance table */
210 sym = 0;
211 while (sym < 32) state->lens[sym++] = 5;
212 distfix = next;
213 bits = 5;
214 inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
215
216 /* do this just once */
217 virgin = 0;
218 }
219 #else /* !BUILDFIXED */
220 # include "inffixed.h"
221 #endif /* BUILDFIXED */
222 state->lencode = lenfix;
223 state->lenbits = 9;
224 state->distcode = distfix;
225 state->distbits = 5;
226 }
227
228 #ifdef MAKEFIXED
229 #include <stdio.h>
230
231 /*
232 Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
233 defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
234 those tables to stdout, which would be piped to inffixed.h. A small program
235 can simply call makefixed to do this:
236
237 void makefixed(void);
238
239 int main(void)
240 {
241 makefixed();
242 return 0;
243 }
244
245 Then that can be linked with zlib built with MAKEFIXED defined and run:
246
247 a.out > inffixed.h
248 */
249 void makefixed()
250 {
251 unsigned low, size;
252 struct inflate_state state;
253
254 fixedtables(&state);
255 puts(" /* inffixed.h -- table for decoding fixed codes");
256 puts(" * Generated automatically by makefixed().");
257 puts(" */");
258 puts("");
259 puts(" /* WARNING: this file should *not* be used by applications.");
260 puts(" It is part of the implementation of this library and is");
261 puts(" subject to change. Applications should only use zlib.h.");
262 puts(" */");
263 puts("");
264 size = 1U << 9;
265 printf(" static const code lenfix[%u] = {", size);
266 low = 0;
267 for (;;) {
268 if ((low % 7) == 0) printf("\n ");
269 printf("{%u,%u,%d}", state.lencode[low].op, state.lencode[low].bits,
270 state.lencode[low].val);
271 if (++low == size) break;
272 putchar(',');
273 }
274 puts("\n };");
275 size = 1U << 5;
276 printf("\n static const code distfix[%u] = {", size);
277 low = 0;
278 for (;;) {
279 if ((low % 6) == 0) printf("\n ");
280 printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
281 state.distcode[low].val);
282 if (++low == size) break;
283 putchar(',');
284 }
285 puts("\n };");
286 }
287 #endif /* MAKEFIXED */
288
289 /*
290 Update the window with the last wsize (normally 32K) bytes written before
291 returning. If window does not exist yet, create it. This is only called
292 when a window is already in use, or when output has been written during this
293 inflate call, but the end of the deflate stream has not been reached yet.
294 It is also called to create a window for dictionary data when a dictionary
295 is loaded.
296
297 Providing output buffers larger than 32K to inflate() should provide a speed
298 advantage, since only the last 32K of output is copied to the sliding window
299 upon return from inflate(), and since all distances after the first 32K of
300 output will fall in the output data, making match copies simpler and faster.
301 The advantage may be dependent on the size of the processor's data caches.
302 */
303 local int updatewindow(strm, out)
304 z_streamp strm;
305 unsigned out;
306 {
307 struct inflate_state FAR *state;
308 unsigned copy, dist;
309
310 state = (struct inflate_state FAR *)strm->state;
311
312 /* if it hasn't been done already, allocate space for the window */
313 if (state->window == Z_NULL) {
314 state->window = (unsigned char FAR *)
315 ZALLOC(strm, 1U << state->wbits,
316 sizeof(unsigned char));
317 if (state->window == Z_NULL) return 1;
318 }
319
320 /* if window not in use yet, initialize */
321 if (state->wsize == 0) {
322 state->wsize = 1U << state->wbits;
323 state->write = 0;
324 state->whave = 0;
325 }
326
327 /* copy state->wsize or less output bytes into the circular window */
328 copy = out - strm->avail_out;
329 if (copy >= state->wsize) {
330 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
331 state->write = 0;
332 state->whave = state->wsize;
333 }
334 else {
335 dist = state->wsize - state->write;
336 if (dist > copy) dist = copy;
337 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
338 copy -= dist;
339 if (copy) {
340 zmemcpy(state->window, strm->next_out - copy, copy);
341 state->write = copy;
342 state->whave = state->wsize;
343 }
344 else {
345 state->write += dist;
346 if (state->write == state->wsize) state->write = 0;
347 if (state->whave < state->wsize) state->whave += dist;
348 }
349 }
350 return 0;
351 }
352
353 /* Macros for inflate(): */
354
355 /* check function to use adler32() for zlib or crc32() for gzip */
356 #ifdef GUNZIP
357 # define UPDATE(check, buf, len) \
358 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
359 #else
360 # define UPDATE(check, buf, len) adler32(check, buf, len)
361 #endif
362
363 /* check macros for header crc */
364 #ifdef GUNZIP
365 # define CRC2(check, word) \
366 do { \
367 hbuf[0] = (unsigned char)(word); \
368 hbuf[1] = (unsigned char)((word) >> 8); \
369 check = crc32(check, hbuf, 2); \
370 } while (0)
371
372 # define CRC4(check, word) \
373 do { \
374 hbuf[0] = (unsigned char)(word); \
375 hbuf[1] = (unsigned char)((word) >> 8); \
376 hbuf[2] = (unsigned char)((word) >> 16); \
377 hbuf[3] = (unsigned char)((word) >> 24); \
378 check = crc32(check, hbuf, 4); \
379 } while (0)
380 #endif
381
382 /* Load registers with state in inflate() for speed */
383 #define LOAD() \
384 do { \
385 put = strm->next_out; \
386 left = strm->avail_out; \
387 next = strm->next_in; \
388 have = strm->avail_in; \
389 hold = state->hold; \
390 bits = state->bits; \
391 } while (0)
392
393 /* Restore state from registers in inflate() */
394 #define RESTORE() \
395 do { \
396 strm->next_out = put; \
397 strm->avail_out = left; \
398 strm->next_in = next; \
399 strm->avail_in = have; \
400 state->hold = hold; \
401 state->bits = bits; \
402 } while (0)
403
404 /* Clear the input bit accumulator */
405 #define INITBITS() \
406 do { \
407 hold = 0; \
408 bits = 0; \
409 } while (0)
410
411 /* Get a byte of input into the bit accumulator, or return from inflate()
412 if there is no input available. */
413 #define PULLBYTE() \
414 do { \
415 if (have == 0) goto inf_leave; \
416 have--; \
417 hold += (unsigned long)(*next++) << bits; \
418 bits += 8; \
419 } while (0)
420
421 /* Assure that there are at least n bits in the bit accumulator. If there is
422 not enough available input to do that, then return from inflate(). */
423 #define NEEDBITS(n) \
424 do { \
425 while (bits < (unsigned)(n)) \
426 PULLBYTE(); \
427 } while (0)
428
429 /* Return the low n bits of the bit accumulator (n < 16) */
430 #define BITS(n) \
431 ((unsigned)hold & ((1U << (n)) - 1))
432
433 /* Remove n bits from the bit accumulator */
434 #define DROPBITS(n) \
435 do { \
436 hold >>= (n); \
437 bits -= (unsigned)(n); \
438 } while (0)
439
440 /* Remove zero to seven bits as needed to go to a byte boundary */
441 #define BYTEBITS() \
442 do { \
443 hold >>= bits & 7; \
444 bits -= bits & 7; \
445 } while (0)
446
447 /* Reverse the bytes in a 32-bit value */
448 #define REVERSE(q) \
449 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
450 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
451
452 /*
453 inflate() uses a state machine to process as much input data and generate as
454 much output data as possible before returning. The state machine is
455 structured roughly as follows:
456
457 for (;;) switch (state) {
458 ...
459 case STATEn:
460 if (not enough input data or output space to make progress)
461 return;
462 ... make progress ...
463 state = STATEm;
464 break;
465 ...
466 }
467
468 so when inflate() is called again, the same case is attempted again, and
469 if the appropriate resources are provided, the machine proceeds to the
470 next state. The NEEDBITS() macro is usually the way the state evaluates
471 whether it can proceed or should return. NEEDBITS() does the return if
472 the requested bits are not available. The typical use of the BITS macros
473 is:
474
475 NEEDBITS(n);
476 ... do something with BITS(n) ...
477 DROPBITS(n);
478
479 where NEEDBITS(n) either returns from inflate() if there isn't enough
480 input left to load n bits into the accumulator, or it continues. BITS(n)
481 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
482 the low n bits off the accumulator. INITBITS() clears the accumulator
483 and sets the number of available bits to zero. BYTEBITS() discards just
484 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
485 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
486
487 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
488 if there is no input available. The decoding of variable length codes uses
489 PULLBYTE() directly in order to pull just enough bytes to decode the next
490 code, and no more.
491
492 Some states loop until they get enough input, making sure that enough
493 state information is maintained to continue the loop where it left off
494 if NEEDBITS() returns in the loop. For example, want, need, and keep
495 would all have to actually be part of the saved state in case NEEDBITS()
496 returns:
497
498 case STATEw:
499 while (want < need) {
500 NEEDBITS(n);
501 keep[want++] = BITS(n);
502 DROPBITS(n);
503 }
504 state = STATEx;
505 case STATEx:
506
507 As shown above, if the next state is also the next case, then the break
508 is omitted.
509
510 A state may also return if there is not enough output space available to
511 complete that state. Those states are copying stored data, writing a
512 literal byte, and copying a matching string.
513
514 When returning, a "goto inf_leave" is used to update the total counters,
515 update the check value, and determine whether any progress has been made
516 during that inflate() call in order to return the proper return code.
517 Progress is defined as a change in either strm->avail_in or strm->avail_out.
518 When there is a window, goto inf_leave will update the window with the last
519 output written. If a goto inf_leave occurs in the middle of decompression
520 and there is no window currently, goto inf_leave will create one and copy
521 output to the window for the next call of inflate().
522
523 In this implementation, the flush parameter of inflate() only affects the
524 return code (per zlib.h). inflate() always writes as much as possible to
525 strm->next_out, given the space available and the provided input--the effect
526 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
527 the allocation of and copying into a sliding window until necessary, which
528 provides the effect documented in zlib.h for Z_FINISH when the entire input
529 stream available. So the only thing the flush parameter actually does is:
530 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
531 will return Z_BUF_ERROR if it has not reached the end of the stream.
532 */
533
534 int ZEXPORT inflate(strm, flush)
535 z_streamp strm;
536 int flush;
537 {
538 struct inflate_state FAR *state;
539 unsigned char FAR *next; /* next input */
540 unsigned char FAR *put; /* next output */
541 unsigned have, left; /* available input and output */
542 unsigned long hold; /* bit buffer */
543 unsigned bits; /* bits in bit buffer */
544 unsigned in, out; /* save starting available input and output */
545 unsigned copy; /* number of stored or match bytes to copy */
546 unsigned char FAR *from; /* where to copy match bytes from */
547 code this; /* current decoding table entry */
548 code last; /* parent table entry */
549 unsigned len; /* length to copy for repeats, bits to drop */
550 int ret; /* return code */
551 #ifdef GUNZIP
552 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
553 #endif
554 static const unsigned short order[19] = /* permutation of code lengths */
555 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
556
557 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
558 (strm->next_in == Z_NULL && strm->avail_in != 0))
559 return Z_STREAM_ERROR;
560
561 state = (struct inflate_state FAR *)strm->state;
562 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
563 LOAD();
564 in = have;
565 out = left;
566 ret = Z_OK;
567 for (;;)
568 switch (state->mode) {
569 case HEAD:
570 if (state->wrap == 0) {
571 state->mode = TYPEDO;
572 break;
573 }
574 NEEDBITS(16);
575 #ifdef GUNZIP
576 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
577 state->check = crc32(0L, Z_NULL, 0);
578 CRC2(state->check, hold);
579 INITBITS();
580 state->mode = FLAGS;
581 break;
582 }
583 state->flags = 0; /* expect zlib header */
584 if (!(state->wrap & 1) || /* check if zlib header allowed */
585 #else
586 if (
587 #endif
588 ((BITS(8) << 8) + (hold >> 8)) % 31) {
589 strm->msg = (char *)"incorrect header check";
590 state->mode = BAD;
591 break;
592 }
593 if (BITS(4) != Z_DEFLATED) {
594 strm->msg = (char *)"unknown compression method";
595 state->mode = BAD;
596 break;
597 }
598 DROPBITS(4);
599 if (BITS(4) + 8 > state->wbits) {
600 strm->msg = (char *)"invalid window size";
601 state->mode = BAD;
602 break;
603 }
604 Tracev((stderr, "inflate: zlib header ok\n"));
605 strm->adler = state->check = adler32(0L, Z_NULL, 0);
606 state->mode = hold & 0x200 ? DICTID : TYPE;
607 INITBITS();
608 break;
609 #ifdef GUNZIP
610 case FLAGS:
611 NEEDBITS(16);
612 state->flags = (int)(hold);
613 if ((state->flags & 0xff) != Z_DEFLATED) {
614 strm->msg = (char *)"unknown compression method";
615 state->mode = BAD;
616 break;
617 }
618 if (state->flags & 0xe000) {
619 strm->msg = (char *)"unknown header flags set";
620 state->mode = BAD;
621 break;
622 }
623 if (state->flags & 0x0200) CRC2(state->check, hold);
624 INITBITS();
625 state->mode = TIME;
626 case TIME:
627 NEEDBITS(32);
628 if (state->flags & 0x0200) CRC4(state->check, hold);
629 INITBITS();
630 state->mode = OS;
631 case OS:
632 NEEDBITS(16);
633 if (state->flags & 0x0200) CRC2(state->check, hold);
634 INITBITS();
635 state->mode = EXLEN;
636 case EXLEN:
637 if (state->flags & 0x0400) {
638 NEEDBITS(16);
639 state->length = (unsigned)(hold);
640 if (state->flags & 0x0200) CRC2(state->check, hold);
641 INITBITS();
642 }
643 state->mode = EXTRA;
644 case EXTRA:
645 if (state->flags & 0x0400) {
646 copy = state->length;
647 if (copy > have) copy = have;
648 if (copy) {
649 if (state->flags & 0x0200)
650 state->check = crc32(state->check, next, copy);
651 have -= copy;
652 next += copy;
653 state->length -= copy;
654 }
655 if (state->length) goto inf_leave;
656 }
657 state->mode = NAME;
658 case NAME:
659 if (state->flags & 0x0800) {
660 if (have == 0) goto inf_leave;
661 copy = 0;
662 do {
663 len = (unsigned)(next[copy++]);
664 } while (len && copy < have);
665 if (state->flags & 0x02000)
666 state->check = crc32(state->check, next, copy);
667 have -= copy;
668 next += copy;
669 if (len) goto inf_leave;
670 }
671 state->mode = COMMENT;
672 case COMMENT:
673 if (state->flags & 0x1000) {
674 if (have == 0) goto inf_leave;
675 copy = 0;
676 do {
677 len = (unsigned)(next[copy++]);
678 } while (len && copy < have);
679 if (state->flags & 0x02000)
680 state->check = crc32(state->check, next, copy);
681 have -= copy;
682 next += copy;
683 if (len) goto inf_leave;
684 }
685 state->mode = HCRC;
686 case HCRC:
687 if (state->flags & 0x0200) {
688 NEEDBITS(16);
689 if (hold != (state->check & 0xffff)) {
690 strm->msg = (char *)"header crc mismatch";
691 state->mode = BAD;
692 break;
693 }
694 INITBITS();
695 }
696 strm->adler = state->check = crc32(0L, Z_NULL, 0);
697 state->mode = TYPE;
698 break;
699 #endif
700 case DICTID:
701 NEEDBITS(32);
702 strm->adler = state->check = REVERSE(hold);
703 INITBITS();
704 state->mode = DICT;
705 case DICT:
706 if (state->havedict == 0) {
707 RESTORE();
708 return Z_NEED_DICT;
709 }
710 strm->adler = state->check = adler32(0L, Z_NULL, 0);
711 state->mode = TYPE;
712 case TYPE:
713 if (flush == Z_BLOCK) goto inf_leave;
714 case TYPEDO:
715 if (state->last) {
716 BYTEBITS();
717 state->mode = CHECK;
718 break;
719 }
720 NEEDBITS(3);
721 state->last = BITS(1);
722 DROPBITS(1);
723 switch (BITS(2)) {
724 case 0: /* stored block */
725 Tracev((stderr, "inflate: stored block%s\n",
726 state->last ? " (last)" : ""));
727 state->mode = STORED;
728 break;
729 case 1: /* fixed block */
730 fixedtables(state);
731 Tracev((stderr, "inflate: fixed codes block%s\n",
732 state->last ? " (last)" : ""));
733 state->mode = LEN; /* decode codes */
734 break;
735 case 2: /* dynamic block */
736 Tracev((stderr, "inflate: dynamic codes block%s\n",
737 state->last ? " (last)" : ""));
738 state->mode = TABLE;
739 break;
740 case 3:
741 strm->msg = (char *)"invalid block type";
742 state->mode = BAD;
743 }
744 DROPBITS(2);
745 break;
746 case STORED:
747 BYTEBITS(); /* go to byte boundary */
748 NEEDBITS(32);
749 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
750 strm->msg = (char *)"invalid stored block lengths";
751 state->mode = BAD;
752 break;
753 }
754 state->length = (unsigned)hold & 0xffff;
755 Tracev((stderr, "inflate: stored length %u\n",
756 state->length));
757 INITBITS();
758 state->mode = COPY;
759 case COPY:
760 copy = state->length;
761 if (copy) {
762 if (copy > have) copy = have;
763 if (copy > left) copy = left;
764 if (copy == 0) goto inf_leave;
765 zmemcpy(put, next, copy);
766 have -= copy;
767 next += copy;
768 left -= copy;
769 put += copy;
770 state->length -= copy;
771 break;
772 }
773 Tracev((stderr, "inflate: stored end\n"));
774 state->mode = TYPE;
775 break;
776 case TABLE:
777 NEEDBITS(14);
778 state->nlen = BITS(5) + 257;
779 DROPBITS(5);
780 state->ndist = BITS(5) + 1;
781 DROPBITS(5);
782 state->ncode = BITS(4) + 4;
783 DROPBITS(4);
784 #ifndef PKZIP_BUG_WORKAROUND
785 if (state->nlen > 286 || state->ndist > 30) {
786 strm->msg = (char *)"too many length or distance symbols";
787 state->mode = BAD;
788 break;
789 }
790 #endif
791 Tracev((stderr, "inflate: table sizes ok\n"));
792 state->have = 0;
793 state->mode = LENLENS;
794 case LENLENS:
795 while (state->have < state->ncode) {
796 NEEDBITS(3);
797 state->lens[order[state->have++]] = (unsigned short)BITS(3);
798 DROPBITS(3);
799 }
800 while (state->have < 19)
801 state->lens[order[state->have++]] = 0;
802 state->next = state->codes;
803 state->lencode = (code const FAR *)(state->next);
804 state->lenbits = 7;
805 ret = inflate_table(CODES, state->lens, 19, &(state->next),
806 &(state->lenbits), state->work);
807 if (ret) {
808 strm->msg = (char *)"invalid code lengths set";
809 state->mode = BAD;
810 break;
811 }
812 Tracev((stderr, "inflate: code lengths ok\n"));
813 state->have = 0;
814 state->mode = CODELENS;
815 case CODELENS:
816 while (state->have < state->nlen + state->ndist) {
817 for (;;) {
818 this = state->lencode[BITS(state->lenbits)];
819 if ((unsigned)(this.bits) <= bits) break;
820 PULLBYTE();
821 }
822 if (this.val < 16) {
823 NEEDBITS(this.bits);
824 DROPBITS(this.bits);
825 state->lens[state->have++] = this.val;
826 }
827 else {
828 if (this.val == 16) {
829 NEEDBITS(this.bits + 2);
830 DROPBITS(this.bits);
831 if (state->have == 0) {
832 strm->msg = (char *)"invalid bit length repeat";
833 state->mode = BAD;
834 break;
835 }
836 len = state->lens[state->have - 1];
837 copy = 3 + BITS(2);
838 DROPBITS(2);
839 }
840 else if (this.val == 17) {
841 NEEDBITS(this.bits + 3);
842 DROPBITS(this.bits);
843 len = 0;
844 copy = 3 + BITS(3);
845 DROPBITS(3);
846 }
847 else {
848 NEEDBITS(this.bits + 7);
849 DROPBITS(this.bits);
850 len = 0;
851 copy = 11 + BITS(7);
852 DROPBITS(7);
853 }
854 if (state->have + copy > state->nlen + state->ndist) {
855 strm->msg = (char *)"invalid bit length repeat";
856 state->mode = BAD;
857 break;
858 }
859 while (copy--)
860 state->lens[state->have++] = (unsigned short)len;
861 }
862 }
863
864 if (state->mode == BAD)
865 break;
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 }