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