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