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