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