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