1 /* $NetBSD: zlib.c,v 1.2 2015/02/05 01:26:54 agc Exp $ */
2
3 /* inflate.c -- zlib decompression
4 * Copyright (C) 1995-2005 Mark Adler
5 * For conditions of distribution and use, see copyright notice in zlib.h
6 */
7
8 /*
9 * Change history:
10 *
11 * 1.2.beta0 24 Nov 2002
12 * - First version -- complete rewrite of inflate to simplify code, avoid
13 * creation of window when not needed, minimize use of window when it is
14 * needed, make inffast.c even faster, implement gzip decoding, and to
15 * improve code readability and style over the previous zlib inflate code
16 *
17 * 1.2.beta1 25 Nov 2002
18 * - Use pointers for available input and output checking in inffast.c
19 * - Remove input and output counters in inffast.c
20 * - Change inffast.c entry and loop from avail_in >= 7 to >= 6
21 * - Remove unnecessary second byte pull from length extra in inffast.c
22 * - Unroll direct copy to three copies per loop in inffast.c
23 *
24 * 1.2.beta2 4 Dec 2002
25 * - Change external routine names to reduce potential conflicts
26 * - Correct filename to inffixed.h for fixed tables in inflate.c
27 * - Make hbuf[] unsigned char to match parameter type in inflate.c
28 * - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
29 * to avoid negation problem on Alphas (64 bit) in inflate.c
30 *
31 * 1.2.beta3 22 Dec 2002
32 * - Add comments on state->bits assertion in inffast.c
33 * - Add comments on op field in inftrees.h
34 * - Fix bug in reuse of allocated window after inflateReset()
35 * - Remove bit fields--back to byte structure for speed
36 * - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
37 * - Change post-increments to pre-increments in inflate_fast(), PPC biased?
38 * - Add compile time option, POSTINC, to use post-increments instead (Intel?)
39 * - Make MATCH copy in inflate() much faster for when inflate_fast() not used
40 * - Use local copies of stream next and avail values, as well as local bit
41 * buffer and bit count in inflate()--for speed when inflate_fast() not used
42 *
43 * 1.2.beta4 1 Jan 2003
44 * - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
45 * - Move a comment on output buffer sizes from inffast.c to inflate.c
46 * - Add comments in inffast.c to introduce the inflate_fast() routine
47 * - Rearrange window copies in inflate_fast() for speed and simplification
48 * - Unroll last copy for window match in inflate_fast()
49 * - Use local copies of window variables in inflate_fast() for speed
50 * - Pull out common write == 0 case for speed in inflate_fast()
51 * - Make op and len in inflate_fast() unsigned for consistency
52 * - Add FAR to lcode and dcode declarations in inflate_fast()
53 * - Simplified bad distance check in inflate_fast()
54 * - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
55 * source file infback.c to provide a call-back interface to inflate for
56 * programs like gzip and unzip -- uses window as output buffer to avoid
57 * window copying
58 *
59 * 1.2.beta5 1 Jan 2003
60 * - Improved inflateBack() interface to allow the caller to provide initial
61 * input in strm.
62 * - Fixed stored blocks bug in inflateBack()
63 *
64 * 1.2.beta6 4 Jan 2003
65 * - Added comments in inffast.c on effectiveness of POSTINC
66 * - Typecasting all around to reduce compiler warnings
67 * - Changed loops from while (1) or do {} while (1) to for (;;), again to
68 * make compilers happy
69 * - Changed type of window in inflateBackInit() to unsigned char *
70 *
71 * 1.2.beta7 27 Jan 2003
72 * - Changed many types to unsigned or unsigned short to avoid warnings
73 * - Added inflateCopy() function
74 *
75 * 1.2.0 9 Mar 2003
76 * - Changed inflateBack() interface to provide separate opaque descriptors
77 * for the in() and out() functions
78 * - Changed inflateBack() argument and in_func typedef to swap the length
79 * and buffer address return values for the input function
80 * - Check next_in and next_out for Z_NULL on entry to inflate()
81 *
82 * The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
83 */
84 #include "config.h"
85
86 #include <stdio.h>
87 #include <stdlib.h>
88 #include <string.h>
89
90 #include "zlib.h"
91
92 #ifdef MAKEFIXED
93 # ifndef BUILDFIXED
94 # define BUILDFIXED
95 # endif
96 #endif
97
98 #ifndef local
99 #define local static
100 #endif
101
102 #define ZALLOC(strm, items, size) \
103 (*((strm)->zalloc))((strm)->opaque, (items), (size))
104 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
105 #define Tracev(x)
106 #define Tracevv(x)
107
108 /* Possible inflate modes between inflate() calls */
109 typedef enum {
110 HEAD, /* i: waiting for magic header */
111 FLAGS, /* i: waiting for method and flags (gzip) */
112 TIME, /* i: waiting for modification time (gzip) */
113 OS, /* i: waiting for extra flags and operating system (gzip) */
114 EXLEN, /* i: waiting for extra length (gzip) */
115 EXTRA, /* i: waiting for extra bytes (gzip) */
116 NAME, /* i: waiting for end of file name (gzip) */
117 COMMENT, /* i: waiting for end of comment (gzip) */
118 HCRC, /* i: waiting for header crc (gzip) */
119 DICTID, /* i: waiting for dictionary check value */
120 DICT, /* waiting for inflateSetDictionary() call */
121 TYPE, /* i: waiting for type bits, including last-flag bit */
122 TYPEDO, /* i: same, but skip check to exit inflate on new block */
123 STORED, /* i: waiting for stored size (length and complement) */
124 COPY, /* i/o: waiting for input or output to copy stored block */
125 TABLE, /* i: waiting for dynamic block table lengths */
126 LENLENS, /* i: waiting for code length code lengths */
127 CODELENS, /* i: waiting for length/lit and distance code lengths */
128 LEN, /* i: waiting for length/lit code */
129 LENEXT, /* i: waiting for length extra bits */
130 DIST, /* i: waiting for distance code */
131 DISTEXT, /* i: waiting for distance extra bits */
132 MATCH, /* o: waiting for output space to copy string */
133 LIT, /* o: waiting for output space to write literal */
134 CHECK, /* i: waiting for 32-bit check value */
135 LENGTH, /* i: waiting for 32-bit length (gzip) */
136 DONE, /* finished check, done -- remain here until reset */
137 BAD, /* got a data error -- remain here until reset */
138 MEM, /* got an inflate() memory error -- remain here until reset */
139 SYNC /* looking for synchronization bytes to restart inflate() */
140 } inflate_mode;
141
142 /* Structure for decoding tables. Each entry provides either the
143 information needed to do the operation requested by the code that
144 indexed that table entry, or it provides a pointer to another
145 table that indexes more bits of the code. op indicates whether
146 the entry is a pointer to another table, a literal, a length or
147 distance, an end-of-block, or an invalid code. For a table
148 pointer, the low four bits of op is the number of index bits of
149 that table. For a length or distance, the low four bits of op
150 is the number of extra bits to get after the code. bits is
151 the number of bits in this code or part of the code to drop off
152 of the bit buffer. val is the actual byte to output in the case
153 of a literal, the base length or distance, or the offset from
154 the current table to the next table. Each entry is four bytes. */
155 typedef struct {
156 unsigned char op; /* operation, extra bits, table bits */
157 unsigned char bits; /* bits in this part of the code */
158 unsigned short val; /* offset in table or code value */
159 } code;
160
161 #define ENOUGH 2048
162
163 /* Type of code to build for inftable() */
164 typedef enum {
165 CODES,
166 LENS,
167 DISTS
168 } codetype;
169
170 #ifndef DEF_WBITS
171 # define DEF_WBITS MAX_WBITS
172 #endif
173
174 #define zmemcpy memcpy
175
176 /*
177 State transitions between above modes -
178
179 (most modes can go to the BAD or MEM mode -- not shown for clarity)
180
181 Process header:
182 HEAD -> (gzip) or (zlib)
183 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
184 NAME -> COMMENT -> HCRC -> TYPE
185 (zlib) -> DICTID or TYPE
186 DICTID -> DICT -> TYPE
187 Read deflate blocks:
188 TYPE -> STORED or TABLE or LEN or CHECK
189 STORED -> COPY -> TYPE
190 TABLE -> LENLENS -> CODELENS -> LEN
191 Read deflate codes:
192 LEN -> LENEXT or LIT or TYPE
193 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
194 LIT -> LEN
195 Process trailer:
196 CHECK -> LENGTH -> DONE
197 */
198
199 /* state maintained between inflate() calls. Approximately 7K bytes. */
200 struct inflate_state {
201 inflate_mode mode; /* current inflate mode */
202 int last; /* true if processing last block */
203 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
204 int havedict; /* true if dictionary provided */
205 int flags; /* gzip header method and flags (0 if zlib) */
206 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
207 unsigned long check; /* protected copy of check value */
208 unsigned long total; /* protected copy of output count */
209 gz_headerp head; /* where to save gzip header information */
210 /* sliding window */
211 unsigned wbits; /* log base 2 of requested window size */
212 unsigned wsize; /* window size or zero if not using window */
213 unsigned whave; /* valid bytes in the window */
214 unsigned write; /* window write index */
215 unsigned char FAR *window; /* allocated sliding window, if needed */
216 /* bit accumulator */
217 unsigned long hold; /* input bit accumulator */
218 unsigned bits; /* number of bits in "in" */
219 /* for string and stored block copying */
220 unsigned length; /* literal or length of data to copy */
221 unsigned offset; /* distance back to copy string from */
222 /* for table and code decoding */
223 unsigned extra; /* extra bits needed */
224 /* fixed and dynamic code tables */
225 code const FAR *lencode; /* starting table for length/literal codes */
226 code const FAR *distcode; /* starting table for distance codes */
227 unsigned lenbits; /* index bits for lencode */
228 unsigned distbits; /* index bits for distcode */
229 /* dynamic table building */
230 unsigned ncode; /* number of code length code lengths */
231 unsigned nlen; /* number of length code lengths */
232 unsigned ndist; /* number of distance code lengths */
233 unsigned have; /* number of code lengths in lens[] */
234 code FAR *next; /* next available space in codes[] */
235 unsigned short lens[320]; /* temporary storage for code lengths */
236 unsigned short work[288]; /* work area for code table building */
237 code codes[ENOUGH]; /* space for code tables */
238 };
239
240 voidpf zcalloc(voidpf /*opaque*/, unsigned /*items*/, unsigned /*size*/);
241 void zcfree (voidpf /*opaque*/, voidpf /*ptr*/);
242 int inflate_table(codetype /*type*/, unsigned short FAR */*lens*/, unsigned /*codes*/,
243 code FAR * FAR */*table*/, unsigned FAR */*bits*/, unsigned short FAR */*work*/);
244 void inflate_fast(z_streamp /*strm*/, unsigned /*start*/);
245
246 voidpf
zcalloc(voidpf opaque,unsigned items,unsigned size)247 zcalloc (voidpf opaque, unsigned items, unsigned size)
248 {
249 if (opaque) items += size - size; /* make compiler happy */
250 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
251 (voidpf)calloc(items, size);
252 }
253
254 void
zcfree(voidpf opaque,voidpf ptr)255 zcfree (voidpf opaque, voidpf ptr)
256 {
257 free(ptr);
258 if (opaque) return; /* make compiler happy */
259 }
260
261 /* function prototypes */
262 local void fixedtables OF((struct inflate_state FAR *state));
263 local int updatewindow OF((z_streamp strm, unsigned out));
264 #ifdef BUILDFIXED
265 void makefixed OF((void));
266 #endif
267 local unsigned syncsearch OF((unsigned FAR *have, unsigned char FAR *buf,
268 unsigned len));
269
inflateReset(z_streamp strm)270 int ZEXPORT inflateReset(z_streamp strm)
271 {
272 struct inflate_state FAR *state;
273
274 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
275 state = (struct inflate_state FAR *)(void *)strm->state;
276 strm->total_in = strm->total_out = state->total = 0;
277 strm->msg = Z_NULL;
278 strm->adler = 1; /* to support ill-conceived Java test suite */
279 state->mode = HEAD;
280 state->last = 0;
281 state->havedict = 0;
282 state->dmax = 32768U;
283 state->head = Z_NULL;
284 state->wsize = 0;
285 state->whave = 0;
286 state->write = 0;
287 state->hold = 0;
288 state->bits = 0;
289 state->lencode = state->distcode = state->next = state->codes;
290 Tracev((stderr, "inflate: reset\n"));
291 return Z_OK;
292 }
293
inflatePrime(z_streamp strm,int bits,int value)294 int ZEXPORT inflatePrime(z_streamp strm, int bits, int value)
295 {
296 struct inflate_state FAR *state;
297
298 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
299 state = (struct inflate_state FAR *)(void *)strm->state;
300 if (bits > 16 || state->bits + bits > 32) return Z_STREAM_ERROR;
301 value &= (1L << bits) - 1;
302 state->hold += value << state->bits;
303 state->bits += bits;
304 return Z_OK;
305 }
306
inflateInit2_(z_streamp strm,int windowBits,const char * version,int stream_size)307 int ZEXPORT inflateInit2_(z_streamp strm, int windowBits, const char *version, int stream_size)
308 {
309 struct inflate_state FAR *state;
310
311 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
312 stream_size != (int)(sizeof(z_stream)))
313 return Z_VERSION_ERROR;
314 if (strm == Z_NULL) return Z_STREAM_ERROR;
315 strm->msg = Z_NULL; /* in case we return an error */
316 if (strm->zalloc == (alloc_func)0) {
317 strm->zalloc = zcalloc;
318 strm->opaque = (voidpf)0;
319 }
320 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
321 state = (struct inflate_state FAR *)
322 ZALLOC(strm, 1, sizeof(struct inflate_state));
323 if (state == Z_NULL) return Z_MEM_ERROR;
324 Tracev((stderr, "inflate: allocated\n"));
325 strm->state = (struct internal_state FAR *)(void *)state;
326 if (windowBits < 0) {
327 state->wrap = 0;
328 windowBits = -windowBits;
329 }
330 else {
331 state->wrap = (windowBits >> 4) + 1;
332 #ifdef GUNZIP
333 if (windowBits < 48) windowBits &= 15;
334 #endif
335 }
336 if (windowBits < 8 || windowBits > 15) {
337 ZFREE(strm, state);
338 strm->state = Z_NULL;
339 return Z_STREAM_ERROR;
340 }
341 state->wbits = (unsigned)windowBits;
342 state->window = Z_NULL;
343 return inflateReset(strm);
344 }
345
inflateInit_(z_streamp strm,const char * version,int stream_size)346 int ZEXPORT inflateInit_( z_streamp strm, const char *version, int stream_size)
347 {
348 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
349 }
350
351 /*
352 Return state with length and distance decoding tables and index sizes set to
353 fixed code decoding. Normally this returns fixed tables from inffixed.h.
354 If BUILDFIXED is defined, then instead this routine builds the tables the
355 first time it's called, and returns those tables the first time and
356 thereafter. This reduces the size of the code by about 2K bytes, in
357 exchange for a little execution time. However, BUILDFIXED should not be
358 used for threaded applications, since the rewriting of the tables and virgin
359 may not be thread-safe.
360 */
361 local void
fixedtables(struct inflate_state FAR * state)362 fixedtables(struct inflate_state FAR *state)
363 {
364 /* $NetBSD: zlib.c,v 1.2 2015/02/05 01:26:54 agc Exp $ */
365
366 /* inffixed.h -- table for decoding fixed codes
367 * Generated automatically by makefixed().
368 */
369
370 /* WARNING: this file should *not* be used by applications. It
371 is part of the implementation of the compression library and
372 is subject to change. Applications should only use zlib.h.
373 */
374
375 static const code lenfix[512] = {
376 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
377 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
378 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
379 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
380 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
381 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
382 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
383 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
384 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
385 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
386 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
387 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
388 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
389 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
390 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
391 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
392 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
393 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
394 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
395 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
396 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
397 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
398 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
399 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
400 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
401 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
402 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
403 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
404 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
405 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
406 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
407 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
408 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
409 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
410 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
411 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
412 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
413 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
414 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
415 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
416 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
417 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
418 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
419 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
420 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
421 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
422 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
423 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
424 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
425 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
426 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
427 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
428 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
429 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
430 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
431 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
432 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
433 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
434 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
435 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
436 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
437 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
438 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
439 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
440 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
441 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
442 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
443 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
444 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
445 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
446 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
447 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
448 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
449 {0,9,255}
450 };
451
452 static const code distfix[32] = {
453 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
454 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
455 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
456 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
457 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
458 {22,5,193},{64,5,0}
459 };
460 state->lencode = lenfix;
461 state->lenbits = 9;
462 state->distcode = distfix;
463 state->distbits = 5;
464 }
465
466 /*
467 Update the window with the last wsize (normally 32K) bytes written before
468 returning. If window does not exist yet, create it. This is only called
469 when a window is already in use, or when output has been written during this
470 inflate call, but the end of the deflate stream has not been reached yet.
471 It is also called to create a window for dictionary data when a dictionary
472 is loaded.
473
474 Providing output buffers larger than 32K to inflate() should provide a speed
475 advantage, since only the last 32K of output is copied to the sliding window
476 upon return from inflate(), and since all distances after the first 32K of
477 output will fall in the output data, making match copies simpler and faster.
478 The advantage may be dependent on the size of the processor's data caches.
479 */
480 local int
updatewindow(z_streamp strm,unsigned out)481 updatewindow(z_streamp strm, unsigned out)
482 {
483 struct inflate_state FAR *state;
484 unsigned copy, dist;
485
486 state = (struct inflate_state FAR *)(void *)strm->state;
487
488 /* if it hasn't been done already, allocate space for the window */
489 if (state->window == Z_NULL) {
490 state->window = (unsigned char FAR *)
491 ZALLOC(strm, 1U << state->wbits,
492 sizeof(unsigned char));
493 if (state->window == Z_NULL) return 1;
494 }
495
496 /* if window not in use yet, initialize */
497 if (state->wsize == 0) {
498 state->wsize = 1U << state->wbits;
499 state->write = 0;
500 state->whave = 0;
501 }
502
503 /* copy state->wsize or less output bytes into the circular window */
504 copy = out - strm->avail_out;
505 if (copy >= state->wsize) {
506 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
507 state->write = 0;
508 state->whave = state->wsize;
509 }
510 else {
511 dist = state->wsize - state->write;
512 if (dist > copy) dist = copy;
513 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
514 copy -= dist;
515 if (copy) {
516 zmemcpy(state->window, strm->next_out - copy, copy);
517 state->write = copy;
518 state->whave = state->wsize;
519 }
520 else {
521 state->write += dist;
522 if (state->write == state->wsize) state->write = 0;
523 if (state->whave < state->wsize) state->whave += dist;
524 }
525 }
526 return 0;
527 }
528
529 #define BASE 65521UL /* largest prime smaller than 65536 */
530 #define NMAX 5552
531 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
532
533 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
534 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
535 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
536 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
537 #define DO16(buf) DO8(buf,0); DO8(buf,8);
538
539 /* use NO_DIVIDE if your processor does not do division in hardware */
540 #ifdef NO_DIVIDE
541 # define MOD(a) \
542 do { \
543 if (a >= (BASE << 16)) a -= (BASE << 16); \
544 if (a >= (BASE << 15)) a -= (BASE << 15); \
545 if (a >= (BASE << 14)) a -= (BASE << 14); \
546 if (a >= (BASE << 13)) a -= (BASE << 13); \
547 if (a >= (BASE << 12)) a -= (BASE << 12); \
548 if (a >= (BASE << 11)) a -= (BASE << 11); \
549 if (a >= (BASE << 10)) a -= (BASE << 10); \
550 if (a >= (BASE << 9)) a -= (BASE << 9); \
551 if (a >= (BASE << 8)) a -= (BASE << 8); \
552 if (a >= (BASE << 7)) a -= (BASE << 7); \
553 if (a >= (BASE << 6)) a -= (BASE << 6); \
554 if (a >= (BASE << 5)) a -= (BASE << 5); \
555 if (a >= (BASE << 4)) a -= (BASE << 4); \
556 if (a >= (BASE << 3)) a -= (BASE << 3); \
557 if (a >= (BASE << 2)) a -= (BASE << 2); \
558 if (a >= (BASE << 1)) a -= (BASE << 1); \
559 if (a >= BASE) a -= BASE; \
560 } while (0)
561 # define MOD4(a) \
562 do { \
563 if (a >= (BASE << 4)) a -= (BASE << 4); \
564 if (a >= (BASE << 3)) a -= (BASE << 3); \
565 if (a >= (BASE << 2)) a -= (BASE << 2); \
566 if (a >= (BASE << 1)) a -= (BASE << 1); \
567 if (a >= BASE) a -= BASE; \
568 } while (0)
569 #else
570 # define MOD(a) a %= BASE
571 # define MOD4(a) a %= BASE
572 #endif
573
574 /* ========================================================================= */
575 uLong ZEXPORT
adler32(uLong adler,const Bytef * buf,uInt len)576 adler32(uLong adler, const Bytef *buf, uInt len)
577 {
578 unsigned long sum2;
579 unsigned n;
580
581 /* split Adler-32 into component sums */
582 sum2 = (adler >> 16) & 0xffff;
583 adler &= 0xffff;
584
585 /* in case user likes doing a byte at a time, keep it fast */
586 if (len == 1) {
587 adler += buf[0];
588 if (adler >= BASE)
589 adler -= BASE;
590 sum2 += adler;
591 if (sum2 >= BASE)
592 sum2 -= BASE;
593 return adler | (sum2 << 16);
594 }
595
596 /* initial Adler-32 value (deferred check for len == 1 speed) */
597 if (buf == Z_NULL)
598 return 1L;
599
600 /* in case short lengths are provided, keep it somewhat fast */
601 if (len < 16) {
602 while (len--) {
603 adler += *buf++;
604 sum2 += adler;
605 }
606 if (adler >= BASE)
607 adler -= BASE;
608 MOD4(sum2); /* only added so many BASE's */
609 return adler | (sum2 << 16);
610 }
611
612 /* do length NMAX blocks -- requires just one modulo operation */
613 while (len >= NMAX) {
614 len -= NMAX;
615 n = NMAX / 16; /* NMAX is divisible by 16 */
616 do {
617 DO16(buf); /* 16 sums unrolled */
618 buf += 16;
619 } while (--n);
620 MOD(adler);
621 MOD(sum2);
622 }
623
624 /* do remaining bytes (less than NMAX, still just one modulo) */
625 if (len) { /* avoid modulos if none remaining */
626 while (len >= 16) {
627 len -= 16;
628 DO16(buf);
629 buf += 16;
630 }
631 while (len--) {
632 adler += *buf++;
633 sum2 += adler;
634 }
635 MOD(adler);
636 MOD(sum2);
637 }
638
639 /* return recombined sums */
640 return adler | (sum2 << 16);
641 }
642
643 /* Macros for inflate(): */
644
645 /* check function to use adler32() for zlib or crc32() for gzip */
646 #ifdef GUNZIP
647 # define UPDATE(check, buf, len) \
648 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
649 #else
650 # define UPDATE(check, buf, len) adler32(check, buf, len)
651 #endif
652
653 /* check macros for header crc */
654 #ifdef GUNZIP
655 # define CRC2(check, word) \
656 do { \
657 hbuf[0] = (unsigned char)(word); \
658 hbuf[1] = (unsigned char)((word) >> 8); \
659 check = crc32(check, hbuf, 2); \
660 } while (0)
661
662 # define CRC4(check, word) \
663 do { \
664 hbuf[0] = (unsigned char)(word); \
665 hbuf[1] = (unsigned char)((word) >> 8); \
666 hbuf[2] = (unsigned char)((word) >> 16); \
667 hbuf[3] = (unsigned char)((word) >> 24); \
668 check = crc32(check, hbuf, 4); \
669 } while (0)
670 #endif
671
672 /* Load registers with state in inflate() for speed */
673 #define LOAD() \
674 do { \
675 put = strm->next_out; \
676 left = strm->avail_out; \
677 next = strm->next_in; \
678 have = strm->avail_in; \
679 hold = state->hold; \
680 bits = state->bits; \
681 } while (0)
682
683 /* Restore state from registers in inflate() */
684 #define RESTORE() \
685 do { \
686 strm->next_out = put; \
687 strm->avail_out = left; \
688 strm->next_in = next; \
689 strm->avail_in = have; \
690 state->hold = hold; \
691 state->bits = bits; \
692 } while (0)
693
694 /* Clear the input bit accumulator */
695 #define INITBITS() \
696 do { \
697 hold = 0; \
698 bits = 0; \
699 } while (0)
700
701 /* Get a byte of input into the bit accumulator, or return from inflate()
702 if there is no input available. */
703 #define PULLBYTE() \
704 do { \
705 if (have == 0) goto inf_leave; \
706 have--; \
707 hold += (unsigned long)(*next++) << bits; \
708 bits += 8; \
709 } while (0)
710
711 /* Assure that there are at least n bits in the bit accumulator. If there is
712 not enough available input to do that, then return from inflate(). */
713 #define NEEDBITS(n) \
714 do { \
715 while (bits < (unsigned)(n)) \
716 PULLBYTE(); \
717 } while (0)
718
719 /* Return the low n bits of the bit accumulator (n < 16) */
720 #define BITS(n) \
721 ((unsigned)hold & ((1U << (n)) - 1))
722
723 /* Remove n bits from the bit accumulator */
724 #define DROPBITS(n) \
725 do { \
726 hold >>= (n); \
727 bits -= (unsigned)(n); \
728 } while (0)
729
730 /* Remove zero to seven bits as needed to go to a byte boundary */
731 #define BYTEBITS() \
732 do { \
733 hold >>= bits & 7; \
734 bits -= bits & 7; \
735 } while (0)
736
737 /* Reverse the bytes in a 32-bit value */
738 #define REVERSE(q) \
739 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
740 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
741
742 #define MAXBITS 15
743 #define MAXD 592
744
745 /*
746 If you use the zlib library in a product, an acknowledgment is welcome
747 in the documentation of your product. If for some reason you cannot
748 include such an acknowledgment, I would appreciate that you keep this
749 copyright string in the executable of your product.
750 */
751
752 /*
753 Build a set of tables to decode the provided canonical Huffman code.
754 The code lengths are lens[0..codes-1]. The result starts at *table,
755 whose indices are 0..2^bits-1. work is a writable array of at least
756 lens shorts, which is used as a work area. type is the type of code
757 to be generated, CODES, LENS, or DISTS. On return, zero is success,
758 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
759 on return points to the next available entry's address. bits is the
760 requested root table index bits, and on return it is the actual root
761 table index bits. It will differ if the request is greater than the
762 longest code or if it is less than the shortest code.
763 */
764 int
inflate_table(codetype type,unsigned short FAR * lens,unsigned codes,code FAR * FAR * table,unsigned FAR * bits,unsigned short FAR * work)765 inflate_table(codetype type, unsigned short FAR *lens, unsigned codes,
766 code FAR * FAR *table, unsigned FAR *bits, unsigned short FAR *work)
767 {
768 unsigned len; /* a code's length in bits */
769 unsigned sym; /* index of code symbols */
770 unsigned mmin, mmax; /* minimum and maximum code lengths */
771 unsigned root; /* number of index bits for root table */
772 unsigned curr; /* number of index bits for current table */
773 unsigned drop; /* code bits to drop for sub-table */
774 int left; /* number of prefix codes available */
775 unsigned used; /* code entries in table used */
776 unsigned huff; /* Huffman code */
777 unsigned incr; /* for incrementing code, index */
778 unsigned fill; /* index for replicating entries */
779 unsigned low; /* low bits for current root entry */
780 unsigned mask; /* mask for low root bits */
781 code this; /* table entry for duplication */
782 code FAR *next; /* next available space in table */
783 const unsigned short FAR *base; /* base value table to use */
784 const unsigned short FAR *extra; /* extra bits table to use */
785 int end; /* use base and extra for symbol > end */
786 unsigned short count[MAXBITS+1]; /* number of codes of each length */
787 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
788 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
789 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
790 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
791 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
792 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
793 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
794 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
795 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
796 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
797 8193, 12289, 16385, 24577, 0, 0};
798 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
799 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
800 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
801 28, 28, 29, 29, 64, 64};
802
803 /*
804 Process a set of code lengths to create a canonical Huffman code. The
805 code lengths are lens[0..codes-1]. Each length corresponds to the
806 symbols 0..codes-1. The Huffman code is generated by first sorting the
807 symbols by length from short to long, and retaining the symbol order
808 for codes with equal lengths. Then the code starts with all zero bits
809 for the first code of the shortest length, and the codes are integer
810 increments for the same length, and zeros are appended as the length
811 increases. For the deflate format, these bits are stored backwards
812 from their more natural integer increment ordering, and so when the
813 decoding tables are built in the large loop below, the integer codes
814 are incremented backwards.
815
816 This routine assumes, but does not check, that all of the entries in
817 lens[] are in the range 0..MAXBITS. The caller must assure this.
818 1..MAXBITS is interpreted as that code length. zero means that that
819 symbol does not occur in this code.
820
821 The codes are sorted by computing a count of codes for each length,
822 creating from that a table of starting indices for each length in the
823 sorted table, and then entering the symbols in order in the sorted
824 table. The sorted table is work[], with that space being provided by
825 the caller.
826
827 The length counts are used for other purposes as well, i.e. finding
828 the minimum and maximum length codes, determining if there are any
829 codes at all, checking for a valid set of lengths, and looking ahead
830 at length counts to determine sub-table sizes when building the
831 decoding tables.
832 */
833
834 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
835 for (len = 0; len <= MAXBITS; len++)
836 count[len] = 0;
837 for (sym = 0; sym < codes; sym++)
838 count[lens[sym]]++;
839
840 /* bound code lengths, force root to be within code lengths */
841 root = *bits;
842 for (mmax = MAXBITS; mmax >= 1; mmax--)
843 if (count[mmax] != 0) break;
844 if (root > mmax) root = mmax;
845 if (mmax == 0) { /* no symbols to code at all */
846 this.op = (unsigned char)64; /* invalid code marker */
847 this.bits = (unsigned char)1;
848 this.val = (unsigned short)0;
849 *(*table)++ = this; /* make a table to force an error */
850 *(*table)++ = this;
851 *bits = 1;
852 return 0; /* no symbols, but wait for decoding to report error */
853 }
854 for (mmin = 1; mmin <= MAXBITS; mmin++)
855 if (count[mmin] != 0) break;
856 if (root < mmin) root = mmin;
857
858 /* check for an over-subscribed or incomplete set of lengths */
859 left = 1;
860 for (len = 1; len <= MAXBITS; len++) {
861 left <<= 1;
862 left -= count[len];
863 if (left < 0) return -1; /* over-subscribed */
864 }
865 if (left > 0 && (type == CODES || mmax != 1))
866 return -1; /* incomplete set */
867
868 /* generate offsets into symbol table for each length for sorting */
869 offs[1] = 0;
870 for (len = 1; len < MAXBITS; len++)
871 offs[len + 1] = offs[len] + count[len];
872
873 /* sort symbols by length, by symbol order within each length */
874 for (sym = 0; sym < codes; sym++)
875 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
876
877 /*
878 Create and fill in decoding tables. In this loop, the table being
879 filled is at next and has curr index bits. The code being used is huff
880 with length len. That code is converted to an index by dropping drop
881 bits off of the bottom. For codes where len is less than drop + curr,
882 those top drop + curr - len bits are incremented through all values to
883 fill the table with replicated entries.
884
885 root is the number of index bits for the root table. When len exceeds
886 root, sub-tables are created pointed to by the root entry with an index
887 of the low root bits of huff. This is saved in low to check for when a
888 new sub-table should be started. drop is zero when the root table is
889 being filled, and drop is root when sub-tables are being filled.
890
891 When a new sub-table is needed, it is necessary to look ahead in the
892 code lengths to determine what size sub-table is needed. The length
893 counts are used for this, and so count[] is decremented as codes are
894 entered in the tables.
895
896 used keeps track of how many table entries have been allocated from the
897 provided *table space. It is checked when a LENS table is being made
898 against the space in *table, ENOUGH, minus the maximum space needed by
899 the worst case distance code, MAXD. This should never happen, but the
900 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
901 This assumes that when type == LENS, bits == 9.
902
903 sym increments through all symbols, and the loop terminates when
904 all codes of length mmax, i.e. all codes, have been processed. This
905 routine permits incomplete codes, so another loop after this one fills
906 in the rest of the decoding tables with invalid code markers.
907 */
908
909 /* set up for code type */
910 switch (type) {
911 case CODES:
912 base = extra = work; /* dummy value--not used */
913 end = 19;
914 break;
915 case LENS:
916 base = lbase;
917 base -= 257;
918 extra = lext;
919 extra -= 257;
920 end = 256;
921 break;
922 default: /* DISTS */
923 base = dbase;
924 extra = dext;
925 end = -1;
926 }
927
928 /* initialize state for loop */
929 huff = 0; /* starting code */
930 sym = 0; /* starting code symbol */
931 len = mmin; /* starting code length */
932 next = *table; /* current table to fill in */
933 curr = root; /* current table index bits */
934 drop = 0; /* current bits to drop from code for index */
935 low = (unsigned)(-1); /* trigger new sub-table when len > root */
936 used = 1U << root; /* use root table entries */
937 mask = used - 1; /* mask for comparing low */
938
939 /* check available table space */
940 if (type == LENS && used >= ENOUGH - MAXD)
941 return 1;
942
943 /* process all codes and make table entries */
944 for (;;) {
945 /* create table entry */
946 this.bits = (unsigned char)(len - drop);
947 if ((int)(work[sym]) < end) {
948 this.op = (unsigned char)0;
949 this.val = work[sym];
950 }
951 else if ((int)(work[sym]) > end) {
952 this.op = (unsigned char)(extra[work[sym]]);
953 this.val = base[work[sym]];
954 }
955 else {
956 this.op = (unsigned char)(32 + 64); /* end of block */
957 this.val = 0;
958 }
959
960 /* replicate for those indices with low len bits equal to huff */
961 incr = 1U << (len - drop);
962 fill = 1U << curr;
963 mmin = fill; /* save offset to next table */
964 do {
965 fill -= incr;
966 next[(huff >> drop) + fill] = this;
967 } while (fill != 0);
968
969 /* backwards increment the len-bit code huff */
970 incr = 1U << (len - 1);
971 while (huff & incr)
972 incr >>= 1;
973 if (incr != 0) {
974 huff &= incr - 1;
975 huff += incr;
976 }
977 else
978 huff = 0;
979
980 /* go to next symbol, update count, len */
981 sym++;
982 if (--(count[len]) == 0) {
983 if (len == mmax) break;
984 len = lens[work[sym]];
985 }
986
987 /* create new sub-table if needed */
988 if (len > root && (huff & mask) != low) {
989 /* if first time, transition to sub-tables */
990 if (drop == 0)
991 drop = root;
992
993 /* increment past last table */
994 next += mmin; /* here mmin is 1 << curr */
995
996 /* determine length of next table */
997 curr = len - drop;
998 left = (int)(1 << curr);
999 while (curr + drop < mmax) {
1000 left -= count[curr + drop];
1001 if (left <= 0) break;
1002 curr++;
1003 left <<= 1;
1004 }
1005
1006 /* check for enough space */
1007 used += 1U << curr;
1008 if (type == LENS && used >= ENOUGH - MAXD)
1009 return 1;
1010
1011 /* point entry in root table to sub-table */
1012 low = huff & mask;
1013 (*table)[low].op = (unsigned char)curr;
1014 (*table)[low].bits = (unsigned char)root;
1015 (*table)[low].val = (unsigned short)(next - *table);
1016 }
1017 }
1018
1019 /*
1020 Fill in rest of table for incomplete codes. This loop is similar to the
1021 loop above in incrementing huff for table indices. It is assumed that
1022 len is equal to curr + drop, so there is no loop needed to increment
1023 through high index bits. When the current sub-table is filled, the loop
1024 drops back to the root table to fill in any remaining entries there.
1025 */
1026 this.op = (unsigned char)64; /* invalid code marker */
1027 this.bits = (unsigned char)(len - drop);
1028 this.val = (unsigned short)0;
1029 while (huff != 0) {
1030 /* when done with sub-table, drop back to root table */
1031 if (drop != 0 && (huff & mask) != low) {
1032 drop = 0;
1033 len = root;
1034 next = *table;
1035 this.bits = (unsigned char)len;
1036 }
1037
1038 /* put invalid code marker in table */
1039 next[huff >> drop] = this;
1040
1041 /* backwards increment the len-bit code huff */
1042 incr = 1U << (len - 1);
1043 while (huff & incr)
1044 incr >>= 1;
1045 if (incr != 0) {
1046 huff &= incr - 1;
1047 huff += incr;
1048 }
1049 else
1050 huff = 0;
1051 }
1052
1053 /* set return parameters */
1054 *table += used;
1055 *bits = root;
1056 return 0;
1057 }
1058
1059 /* Allow machine dependent optimization for post-increment or pre-increment.
1060 Based on testing to date,
1061 Pre-increment preferred for:
1062 - PowerPC G3 (Adler)
1063 - MIPS R5000 (Randers-Pehrson)
1064 Post-increment preferred for:
1065 - none
1066 No measurable difference:
1067 - Pentium III (Anderson)
1068 - M68060 (Nikl)
1069 */
1070 #ifdef POSTINC
1071 # define OFF 0
1072 # define PUP(a) *(a)++
1073 #else
1074 # define OFF 1
1075 # define PUP(a) *++(a)
1076 #endif
1077
1078 /*
1079 Decode literal, length, and distance codes and write out the resulting
1080 literal and match bytes until either not enough input or output is
1081 available, an end-of-block is encountered, or a data error is encountered.
1082 When large enough input and output buffers are supplied to inflate(), for
1083 example, a 16K input buffer and a 64K output buffer, more than 95% of the
1084 inflate execution time is spent in this routine.
1085
1086 Entry assumptions:
1087
1088 state->mode == LEN
1089 strm->avail_in >= 6
1090 strm->avail_out >= 258
1091 start >= strm->avail_out
1092 state->bits < 8
1093
1094 On return, state->mode is one of:
1095
1096 LEN -- ran out of enough output space or enough available input
1097 TYPE -- reached end of block code, inflate() to interpret next block
1098 BAD -- error in block data
1099
1100 Notes:
1101
1102 - The maximum input bits used by a length/distance pair is 15 bits for the
1103 length code, 5 bits for the length extra, 15 bits for the distance code,
1104 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
1105 Therefore if strm->avail_in >= 6, then there is enough input to avoid
1106 checking for available input while decoding.
1107
1108 - The maximum bytes that a single length/distance pair can output is 258
1109 bytes, which is the maximum length that can be coded. inflate_fast()
1110 requires strm->avail_out >= 258 for each loop to avoid checking for
1111 output space.
1112 */
1113 void
inflate_fast(z_streamp strm,unsigned start)1114 inflate_fast(z_streamp strm, unsigned start)
1115 /* inflate()'s starting value for strm->avail_out */
1116 {
1117 struct inflate_state FAR *state;
1118 unsigned char FAR *in; /* local strm->next_in */
1119 unsigned char FAR *last; /* while in < last, enough input available */
1120 unsigned char FAR *out; /* local strm->next_out */
1121 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
1122 unsigned char FAR *end; /* while out < end, enough space available */
1123 #ifdef INFLATE_STRICT
1124 unsigned dmax; /* maximum distance from zlib header */
1125 #endif
1126 unsigned wsize; /* window size or zero if not using window */
1127 unsigned whave; /* valid bytes in the window */
1128 unsigned wwrite; /* window write index */
1129 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
1130 unsigned long hold; /* local strm->hold */
1131 unsigned bits; /* local strm->bits */
1132 code const FAR *lcode; /* local strm->lencode */
1133 code const FAR *dcode; /* local strm->distcode */
1134 unsigned lmask; /* mask for first level of length codes */
1135 unsigned dmask; /* mask for first level of distance codes */
1136 code this; /* retrieved table entry */
1137 unsigned op; /* code bits, operation, extra bits, or */
1138 /* window position, window bytes to copy */
1139 unsigned len; /* match length, unused bytes */
1140 unsigned dist; /* match distance */
1141 unsigned char FAR *from; /* where to copy match from */
1142
1143 /* copy state to local variables */
1144 state = (struct inflate_state FAR *)(void *)strm->state;
1145 in = strm->next_in - OFF;
1146 last = in + (strm->avail_in - 5);
1147 out = strm->next_out - OFF;
1148 beg = out - (start - strm->avail_out);
1149 end = out + (strm->avail_out - 257);
1150 #ifdef INFLATE_STRICT
1151 dmax = state->dmax;
1152 #endif
1153 wsize = state->wsize;
1154 whave = state->whave;
1155 wwrite = state->write;
1156 window = state->window;
1157 hold = state->hold;
1158 bits = state->bits;
1159 lcode = state->lencode;
1160 dcode = state->distcode;
1161 lmask = (1U << state->lenbits) - 1;
1162 dmask = (1U << state->distbits) - 1;
1163
1164 /* decode literals and length/distances until end-of-block or not enough
1165 input data or output space */
1166 do {
1167 if (bits < 15) {
1168 hold += (unsigned long)(PUP(in)) << bits;
1169 bits += 8;
1170 hold += (unsigned long)(PUP(in)) << bits;
1171 bits += 8;
1172 }
1173 this = lcode[hold & lmask];
1174 dolen:
1175 op = (unsigned)(this.bits);
1176 hold >>= op;
1177 bits -= op;
1178 op = (unsigned)(this.op);
1179 if (op == 0) { /* literal */
1180 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1181 "inflate: literal '%c'\n" :
1182 "inflate: literal 0x%02x\n", this.val));
1183 PUP(out) = (unsigned char)(this.val);
1184 }
1185 else if (op & 16) { /* length base */
1186 len = (unsigned)(this.val);
1187 op &= 15; /* number of extra bits */
1188 if (op) {
1189 if (bits < op) {
1190 hold += (unsigned long)(PUP(in)) << bits;
1191 bits += 8;
1192 }
1193 len += (unsigned)hold & ((1U << op) - 1);
1194 hold >>= op;
1195 bits -= op;
1196 }
1197 Tracevv((stderr, "inflate: length %u\n", len));
1198 if (bits < 15) {
1199 hold += (unsigned long)(PUP(in)) << bits;
1200 bits += 8;
1201 hold += (unsigned long)(PUP(in)) << bits;
1202 bits += 8;
1203 }
1204 this = dcode[hold & dmask];
1205 dodist:
1206 op = (unsigned)(this.bits);
1207 hold >>= op;
1208 bits -= op;
1209 op = (unsigned)(this.op);
1210 if (op & 16) { /* distance base */
1211 dist = (unsigned)(this.val);
1212 op &= 15; /* number of extra bits */
1213 if (bits < op) {
1214 hold += (unsigned long)(PUP(in)) << bits;
1215 bits += 8;
1216 if (bits < op) {
1217 hold += (unsigned long)(PUP(in)) << bits;
1218 bits += 8;
1219 }
1220 }
1221 dist += (unsigned)hold & ((1U << op) - 1);
1222 #ifdef INFLATE_STRICT
1223 if (dist > dmax) {
1224 strm->msg = (char *)"invalid distance too far back";
1225 state->mode = BAD;
1226 break;
1227 }
1228 #endif
1229 hold >>= op;
1230 bits -= op;
1231 Tracevv((stderr, "inflate: distance %u\n", dist));
1232 op = (unsigned)(out - beg); /* max distance in output */
1233 if (dist > op) { /* see if copy from window */
1234 op = dist - op; /* distance back in window */
1235 if (op > whave) {
1236 strm->msg = __UNCONST("invalid distance too far back");
1237 state->mode = BAD;
1238 break;
1239 }
1240 from = window - OFF;
1241 if (wwrite == 0) { /* very common case */
1242 from += wsize - op;
1243 if (op < len) { /* some from window */
1244 len -= op;
1245 do {
1246 PUP(out) = PUP(from);
1247 } while (--op);
1248 from = out - dist; /* rest from output */
1249 }
1250 }
1251 else if (wwrite < op) { /* wrap around window */
1252 from += wsize + wwrite - op;
1253 op -= wwrite;
1254 if (op < len) { /* some from end of window */
1255 len -= op;
1256 do {
1257 PUP(out) = PUP(from);
1258 } while (--op);
1259 from = window - OFF;
1260 if (wwrite < len) { /* some from start of window */
1261 op = wwrite;
1262 len -= op;
1263 do {
1264 PUP(out) = PUP(from);
1265 } while (--op);
1266 from = out - dist; /* rest from output */
1267 }
1268 }
1269 }
1270 else { /* contiguous in window */
1271 from += wwrite - op;
1272 if (op < len) { /* some from window */
1273 len -= op;
1274 do {
1275 PUP(out) = PUP(from);
1276 } while (--op);
1277 from = out - dist; /* rest from output */
1278 }
1279 }
1280 while (len > 2) {
1281 PUP(out) = PUP(from);
1282 PUP(out) = PUP(from);
1283 PUP(out) = PUP(from);
1284 len -= 3;
1285 }
1286 if (len) {
1287 PUP(out) = PUP(from);
1288 if (len > 1)
1289 PUP(out) = PUP(from);
1290 }
1291 }
1292 else {
1293 from = out - dist; /* copy direct from output */
1294 do { /* minimum length is three */
1295 PUP(out) = PUP(from);
1296 PUP(out) = PUP(from);
1297 PUP(out) = PUP(from);
1298 len -= 3;
1299 } while (len > 2);
1300 if (len) {
1301 PUP(out) = PUP(from);
1302 if (len > 1)
1303 PUP(out) = PUP(from);
1304 }
1305 }
1306 }
1307 else if ((op & 64) == 0) { /* 2nd level distance code */
1308 this = dcode[this.val + (hold & ((1U << op) - 1))];
1309 goto dodist;
1310 }
1311 else {
1312 strm->msg = __UNCONST("invalid distance code");
1313 state->mode = BAD;
1314 break;
1315 }
1316 }
1317 else if ((op & 64) == 0) { /* 2nd level length code */
1318 this = lcode[this.val + (hold & ((1U << op) - 1))];
1319 goto dolen;
1320 }
1321 else if (op & 32) { /* end-of-block */
1322 Tracevv((stderr, "inflate: end of block\n"));
1323 state->mode = TYPE;
1324 break;
1325 }
1326 else {
1327 strm->msg = __UNCONST("invalid literal/length code");
1328 state->mode = BAD;
1329 break;
1330 }
1331 } while (in < last && out < end);
1332
1333 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
1334 len = bits >> 3;
1335 in -= len;
1336 bits -= len << 3;
1337 hold &= (1U << bits) - 1;
1338
1339 /* update state and return */
1340 strm->next_in = in + OFF;
1341 strm->next_out = out + OFF;
1342 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
1343 strm->avail_out = (unsigned)(out < end ?
1344 257 + (end - out) : 257 - (out - end));
1345 state->hold = hold;
1346 state->bits = bits;
1347 return;
1348 }
1349
1350 /*
1351 inflate() uses a state machine to process as much input data and generate as
1352 much output data as possible before returning. The state machine is
1353 structured roughly as follows:
1354
1355 for (;;) switch (state) {
1356 ...
1357 case STATEn:
1358 if (not enough input data or output space to make progress)
1359 return;
1360 ... make progress ...
1361 state = STATEm;
1362 break;
1363 ...
1364 }
1365
1366 so when inflate() is called again, the same case is attempted again, and
1367 if the appropriate resources are provided, the machine proceeds to the
1368 next state. The NEEDBITS() macro is usually the way the state evaluates
1369 whether it can proceed or should return. NEEDBITS() does the return if
1370 the requested bits are not available. The typical use of the BITS macros
1371 is:
1372
1373 NEEDBITS(n);
1374 ... do something with BITS(n) ...
1375 DROPBITS(n);
1376
1377 where NEEDBITS(n) either returns from inflate() if there isn't enough
1378 input left to load n bits into the accumulator, or it continues. BITS(n)
1379 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1380 the low n bits off the accumulator. INITBITS() clears the accumulator
1381 and sets the number of available bits to zero. BYTEBITS() discards just
1382 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1383 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1384
1385 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1386 if there is no input available. The decoding of variable length codes uses
1387 PULLBYTE() directly in order to pull just enough bytes to decode the next
1388 code, and no more.
1389
1390 Some states loop until they get enough input, making sure that enough
1391 state information is maintained to continue the loop where it left off
1392 if NEEDBITS() returns in the loop. For example, want, need, and keep
1393 would all have to actually be part of the saved state in case NEEDBITS()
1394 returns:
1395
1396 case STATEw:
1397 while (want < need) {
1398 NEEDBITS(n);
1399 keep[want++] = BITS(n);
1400 DROPBITS(n);
1401 }
1402 state = STATEx;
1403 case STATEx:
1404
1405 As shown above, if the next state is also the next case, then the break
1406 is omitted.
1407
1408 A state may also return if there is not enough output space available to
1409 complete that state. Those states are copying stored data, writing a
1410 literal byte, and copying a matching string.
1411
1412 When returning, a "goto inf_leave" is used to update the total counters,
1413 update the check value, and determine whether any progress has been made
1414 during that inflate() call in order to return the proper return code.
1415 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1416 When there is a window, goto inf_leave will update the window with the last
1417 output written. If a goto inf_leave occurs in the middle of decompression
1418 and there is no window currently, goto inf_leave will create one and copy
1419 output to the window for the next call of inflate().
1420
1421 In this implementation, the flush parameter of inflate() only affects the
1422 return code (per zlib.h). inflate() always writes as much as possible to
1423 strm->next_out, given the space available and the provided input--the effect
1424 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1425 the allocation of and copying into a sliding window until necessary, which
1426 provides the effect documented in zlib.h for Z_FINISH when the entire input
1427 stream available. So the only thing the flush parameter actually does is:
1428 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1429 will return Z_BUF_ERROR if it has not reached the end of the stream.
1430 */
1431
1432 int ZEXPORT
inflate(z_streamp strm,int flush)1433 inflate(z_streamp strm, int flush)
1434 {
1435 struct inflate_state FAR *state;
1436 unsigned char FAR *next; /* next input */
1437 unsigned char FAR *put; /* next output */
1438 unsigned have, left; /* available input and output */
1439 unsigned long hold; /* bit buffer */
1440 unsigned bits; /* bits in bit buffer */
1441 unsigned in, out; /* save starting available input and output */
1442 unsigned copy; /* number of stored or match bytes to copy */
1443 unsigned char FAR *from; /* where to copy match bytes from */
1444 code this; /* current decoding table entry */
1445 code last; /* parent table entry */
1446 unsigned len; /* length to copy for repeats, bits to drop */
1447 int ret; /* return code */
1448 #ifdef GUNZIP
1449 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1450 #endif
1451 static const unsigned short order[19] = /* permutation of code lengths */
1452 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1453
1454 #if defined(__NetBSD__) && defined(_STANDALONE)
1455 /* Some kernels are loaded at address 0x0 so strm->next_out could be NULL */
1456 if (strm == Z_NULL || strm->state == Z_NULL ||
1457 (strm->next_in == Z_NULL && strm->avail_in != 0))
1458 return Z_STREAM_ERROR;
1459 #else
1460 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
1461 (strm->next_in == Z_NULL && strm->avail_in != 0))
1462 return Z_STREAM_ERROR;
1463 #endif
1464
1465 state = (struct inflate_state FAR *)(void *)strm->state;
1466 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1467 LOAD();
1468 in = have;
1469 out = left;
1470 ret = Z_OK;
1471 for (;;)
1472 switch (state->mode) {
1473 case HEAD:
1474 if (state->wrap == 0) {
1475 state->mode = TYPEDO;
1476 break;
1477 }
1478 NEEDBITS(16);
1479 #ifdef GUNZIP
1480 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1481 state->check = crc32(0L, Z_NULL, 0);
1482 CRC2(state->check, hold);
1483 INITBITS();
1484 state->mode = FLAGS;
1485 break;
1486 }
1487 state->flags = 0; /* expect zlib header */
1488 if (state->head != Z_NULL)
1489 state->head->done = -1;
1490 if (!(state->wrap & 1) || /* check if zlib header allowed */
1491 #else
1492 if (
1493 #endif
1494 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1495 strm->msg = __UNCONST("incorrect header check");
1496 state->mode = BAD;
1497 break;
1498 }
1499 if (BITS(4) != Z_DEFLATED) {
1500 strm->msg = __UNCONST("unknown compression method");
1501 state->mode = BAD;
1502 break;
1503 }
1504 DROPBITS(4);
1505 len = BITS(4) + 8;
1506 if (len > state->wbits) {
1507 strm->msg = __UNCONST("invalid window size");
1508 state->mode = BAD;
1509 break;
1510 }
1511 state->dmax = 1U << len;
1512 Tracev((stderr, "inflate: zlib header ok\n"));
1513 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1514 state->mode = hold & 0x200 ? DICTID : TYPE;
1515 INITBITS();
1516 break;
1517 #ifdef GUNZIP
1518 case FLAGS:
1519 NEEDBITS(16);
1520 state->flags = (int)(hold);
1521 if ((state->flags & 0xff) != Z_DEFLATED) {
1522 strm->msg = __UNCONST("unknown compression method");
1523 state->mode = BAD;
1524 break;
1525 }
1526 if (state->flags & 0xe000) {
1527 strm->msg = __UNCONST("unknown header flags set");
1528 state->mode = BAD;
1529 break;
1530 }
1531 if (state->head != Z_NULL)
1532 state->head->text = (int)((hold >> 8) & 1);
1533 if (state->flags & 0x0200) CRC2(state->check, hold);
1534 INITBITS();
1535 state->mode = TIME;
1536 case TIME:
1537 NEEDBITS(32);
1538 if (state->head != Z_NULL)
1539 state->head->time = hold;
1540 if (state->flags & 0x0200) CRC4(state->check, hold);
1541 INITBITS();
1542 state->mode = OS;
1543 case OS:
1544 NEEDBITS(16);
1545 if (state->head != Z_NULL) {
1546 state->head->xflags = (int)(hold & 0xff);
1547 state->head->os = (int)(hold >> 8);
1548 }
1549 if (state->flags & 0x0200) CRC2(state->check, hold);
1550 INITBITS();
1551 state->mode = EXLEN;
1552 case EXLEN:
1553 if (state->flags & 0x0400) {
1554 NEEDBITS(16);
1555 state->length = (unsigned)(hold);
1556 if (state->head != Z_NULL)
1557 state->head->extra_len = (unsigned)hold;
1558 if (state->flags & 0x0200) CRC2(state->check, hold);
1559 INITBITS();
1560 }
1561 else if (state->head != Z_NULL)
1562 state->head->extra = Z_NULL;
1563 state->mode = EXTRA;
1564 case EXTRA:
1565 if (state->flags & 0x0400) {
1566 copy = state->length;
1567 if (copy > have) copy = have;
1568 if (copy) {
1569 if (state->head != Z_NULL &&
1570 state->head->extra != Z_NULL) {
1571 len = state->head->extra_len - state->length;
1572 Assert (next != NULL, "next is null");
1573 zmemcpy(state->head->extra + len, next,
1574 len + copy > state->head->extra_max ?
1575 state->head->extra_max - len : copy);
1576 }
1577 if (state->flags & 0x0200)
1578 state->check = crc32(state->check, next, copy);
1579 have -= copy;
1580 next += copy;
1581 state->length -= copy;
1582 }
1583 if (state->length) goto inf_leave;
1584 }
1585 state->length = 0;
1586 state->mode = NAME;
1587 case NAME:
1588 if (state->flags & 0x0800) {
1589 if (have == 0) goto inf_leave;
1590 copy = 0;
1591 do {
1592 len = (unsigned)(next[copy++]);
1593 if (state->head != Z_NULL &&
1594 state->head->name != Z_NULL &&
1595 state->length < state->head->name_max)
1596 state->head->name[state->length++] = len;
1597 } while (len && copy < have);
1598 if (state->flags & 0x0200)
1599 state->check = crc32(state->check, next, copy);
1600 have -= copy;
1601 next += copy;
1602 if (len) goto inf_leave;
1603 }
1604 else if (state->head != Z_NULL)
1605 state->head->name = Z_NULL;
1606 state->length = 0;
1607 state->mode = COMMENT;
1608 case COMMENT:
1609 if (state->flags & 0x1000) {
1610 if (have == 0) goto inf_leave;
1611 copy = 0;
1612 do {
1613 len = (unsigned)(next[copy++]);
1614 if (state->head != Z_NULL &&
1615 state->head->comment != Z_NULL &&
1616 state->length < state->head->comm_max)
1617 state->head->comment[state->length++] = len;
1618 } while (len && copy < have);
1619 if (state->flags & 0x0200)
1620 state->check = crc32(state->check, next, copy);
1621 have -= copy;
1622 next += copy;
1623 if (len) goto inf_leave;
1624 }
1625 else if (state->head != Z_NULL)
1626 state->head->comment = Z_NULL;
1627 state->mode = HCRC;
1628 case HCRC:
1629 if (state->flags & 0x0200) {
1630 NEEDBITS(16);
1631 if (hold != (state->check & 0xffff)) {
1632 strm->msg = __UNCONST("header crc mismatch");
1633 state->mode = BAD;
1634 break;
1635 }
1636 INITBITS();
1637 }
1638 if (state->head != Z_NULL) {
1639 state->head->hcrc = (int)((state->flags >> 9) & 1);
1640 state->head->done = 1;
1641 }
1642 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1643 state->mode = TYPE;
1644 break;
1645 #endif
1646 case DICTID:
1647 NEEDBITS(32);
1648 strm->adler = state->check = REVERSE(hold);
1649 INITBITS();
1650 state->mode = DICT;
1651 case DICT:
1652 if (state->havedict == 0) {
1653 RESTORE();
1654 return Z_NEED_DICT;
1655 }
1656 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1657 state->mode = TYPE;
1658 case TYPE:
1659 if (flush == Z_BLOCK) goto inf_leave;
1660 case TYPEDO:
1661 if (state->last) {
1662 BYTEBITS();
1663 state->mode = CHECK;
1664 break;
1665 }
1666 NEEDBITS(3);
1667 state->last = BITS(1);
1668 DROPBITS(1);
1669 switch (BITS(2)) {
1670 case 0: /* stored block */
1671 Tracev((stderr, "inflate: stored block%s\n",
1672 state->last ? " (last)" : ""));
1673 state->mode = STORED;
1674 break;
1675 case 1: /* fixed block */
1676 fixedtables(state);
1677 Tracev((stderr, "inflate: fixed codes block%s\n",
1678 state->last ? " (last)" : ""));
1679 state->mode = LEN; /* decode codes */
1680 break;
1681 case 2: /* dynamic block */
1682 Tracev((stderr, "inflate: dynamic codes block%s\n",
1683 state->last ? " (last)" : ""));
1684 state->mode = TABLE;
1685 break;
1686 case 3:
1687 strm->msg = __UNCONST("invalid block type");
1688 state->mode = BAD;
1689 }
1690 DROPBITS(2);
1691 break;
1692 case STORED:
1693 BYTEBITS(); /* go to byte boundary */
1694 NEEDBITS(32);
1695 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1696 strm->msg = __UNCONST("invalid stored block lengths");
1697 state->mode = BAD;
1698 break;
1699 }
1700 state->length = (unsigned)hold & 0xffff;
1701 Tracev((stderr, "inflate: stored length %u\n",
1702 state->length));
1703 INITBITS();
1704 state->mode = COPY;
1705 case COPY:
1706 copy = state->length;
1707 if (copy) {
1708 if (copy > have) copy = have;
1709 if (copy > left) copy = left;
1710 if (copy == 0) goto inf_leave;
1711 zmemcpy(put, next, copy);
1712 have -= copy;
1713 next += copy;
1714 left -= copy;
1715 put += copy;
1716 state->length -= copy;
1717 break;
1718 }
1719 Tracev((stderr, "inflate: stored end\n"));
1720 state->mode = TYPE;
1721 break;
1722 case TABLE:
1723 NEEDBITS(14);
1724 state->nlen = BITS(5) + 257;
1725 DROPBITS(5);
1726 state->ndist = BITS(5) + 1;
1727 DROPBITS(5);
1728 state->ncode = BITS(4) + 4;
1729 DROPBITS(4);
1730 #ifndef PKZIP_BUG_WORKAROUND
1731 if (state->nlen > 286 || state->ndist > 30) {
1732 strm->msg = __UNCONST("too many length or distance symbols");
1733 state->mode = BAD;
1734 break;
1735 }
1736 #endif
1737 Tracev((stderr, "inflate: table sizes ok\n"));
1738 state->have = 0;
1739 state->mode = LENLENS;
1740 case LENLENS:
1741 while (state->have < state->ncode) {
1742 NEEDBITS(3);
1743 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1744 DROPBITS(3);
1745 }
1746 while (state->have < 19)
1747 state->lens[order[state->have++]] = 0;
1748 state->next = state->codes;
1749 state->lencode = (code const FAR *)(state->next);
1750 state->lenbits = 7;
1751 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1752 &(state->lenbits), state->work);
1753 if (ret) {
1754 strm->msg = __UNCONST("invalid code lengths set");
1755 state->mode = BAD;
1756 break;
1757 }
1758 Tracev((stderr, "inflate: code lengths ok\n"));
1759 state->have = 0;
1760 state->mode = CODELENS;
1761 case CODELENS:
1762 while (state->have < state->nlen + state->ndist) {
1763 for (;;) {
1764 this = state->lencode[BITS(state->lenbits)];
1765 if ((unsigned)(this.bits) <= bits) break;
1766 PULLBYTE();
1767 }
1768 if (this.val < 16) {
1769 NEEDBITS(this.bits);
1770 DROPBITS(this.bits);
1771 state->lens[state->have++] = this.val;
1772 }
1773 else {
1774 if (this.val == 16) {
1775 NEEDBITS(this.bits + 2);
1776 DROPBITS(this.bits);
1777 if (state->have == 0) {
1778 strm->msg = __UNCONST("invalid bit length repeat");
1779 state->mode = BAD;
1780 break;
1781 }
1782 len = state->lens[state->have - 1];
1783 copy = 3 + BITS(2);
1784 DROPBITS(2);
1785 }
1786 else if (this.val == 17) {
1787 NEEDBITS(this.bits + 3);
1788 DROPBITS(this.bits);
1789 len = 0;
1790 copy = 3 + BITS(3);
1791 DROPBITS(3);
1792 }
1793 else {
1794 NEEDBITS(this.bits + 7);
1795 DROPBITS(this.bits);
1796 len = 0;
1797 copy = 11 + BITS(7);
1798 DROPBITS(7);
1799 }
1800 if (state->have + copy > state->nlen + state->ndist) {
1801 strm->msg = __UNCONST("invalid bit length repeat");
1802 state->mode = BAD;
1803 break;
1804 }
1805 while (copy--)
1806 state->lens[state->have++] = (unsigned short)len;
1807 }
1808 }
1809
1810 /* handle error breaks in while */
1811 if (state->mode == BAD) break;
1812
1813 /* build code tables */
1814 state->next = state->codes;
1815 state->lencode = (code const FAR *)(state->next);
1816 state->lenbits = 9;
1817 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1818 &(state->lenbits), state->work);
1819 if (ret) {
1820 strm->msg = __UNCONST("invalid literal/lengths set");
1821 state->mode = BAD;
1822 break;
1823 }
1824 state->distcode = (code const FAR *)(state->next);
1825 state->distbits = 6;
1826 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1827 &(state->next), &(state->distbits), state->work);
1828 if (ret) {
1829 strm->msg = __UNCONST("invalid distances set");
1830 state->mode = BAD;
1831 break;
1832 }
1833 Tracev((stderr, "inflate: codes ok\n"));
1834 state->mode = LEN;
1835 case LEN:
1836 if (have >= 6 && left >= 258) {
1837 RESTORE();
1838 inflate_fast(strm, out);
1839 LOAD();
1840 break;
1841 }
1842 for (;;) {
1843 this = state->lencode[BITS(state->lenbits)];
1844 if ((unsigned)(this.bits) <= bits) break;
1845 PULLBYTE();
1846 }
1847 if (this.op && (this.op & 0xf0) == 0) {
1848 last = this;
1849 for (;;) {
1850 this = state->lencode[last.val +
1851 (BITS(last.bits + last.op) >> last.bits)];
1852 if ((unsigned)(last.bits + this.bits) <= bits) break;
1853 PULLBYTE();
1854 }
1855 DROPBITS(last.bits);
1856 }
1857 DROPBITS(this.bits);
1858 state->length = (unsigned)this.val;
1859 if ((int)(this.op) == 0) {
1860 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1861 "inflate: literal '%c'\n" :
1862 "inflate: literal 0x%02x\n", this.val));
1863 state->mode = LIT;
1864 break;
1865 }
1866 if (this.op & 32) {
1867 Tracevv((stderr, "inflate: end of block\n"));
1868 state->mode = TYPE;
1869 break;
1870 }
1871 if (this.op & 64) {
1872 strm->msg = __UNCONST("invalid literal/length code");
1873 state->mode = BAD;
1874 break;
1875 }
1876 state->extra = (unsigned)(this.op) & 15;
1877 state->mode = LENEXT;
1878 case LENEXT:
1879 if (state->extra) {
1880 NEEDBITS(state->extra);
1881 state->length += BITS(state->extra);
1882 DROPBITS(state->extra);
1883 }
1884 Tracevv((stderr, "inflate: length %u\n", state->length));
1885 state->mode = DIST;
1886 case DIST:
1887 for (;;) {
1888 this = state->distcode[BITS(state->distbits)];
1889 if ((unsigned)(this.bits) <= bits) break;
1890 PULLBYTE();
1891 }
1892 if ((this.op & 0xf0) == 0) {
1893 last = this;
1894 for (;;) {
1895 this = state->distcode[last.val +
1896 (BITS(last.bits + last.op) >> last.bits)];
1897 if ((unsigned)(last.bits + this.bits) <= bits) break;
1898 PULLBYTE();
1899 }
1900 DROPBITS(last.bits);
1901 }
1902 DROPBITS(this.bits);
1903 if (this.op & 64) {
1904 strm->msg = __UNCONST("invalid distance code");
1905 state->mode = BAD;
1906 break;
1907 }
1908 state->offset = (unsigned)this.val;
1909 state->extra = (unsigned)(this.op) & 15;
1910 state->mode = DISTEXT;
1911 case DISTEXT:
1912 if (state->extra) {
1913 NEEDBITS(state->extra);
1914 state->offset += BITS(state->extra);
1915 DROPBITS(state->extra);
1916 }
1917 #ifdef INFLATE_STRICT
1918 if (state->offset > state->dmax) {
1919 strm->msg = __UNCONST("invalid distance too far back");
1920 state->mode = BAD;
1921 break;
1922 }
1923 #endif
1924 if (state->offset > state->whave + out - left) {
1925 strm->msg = __UNCONST("invalid distance too far back");
1926 state->mode = BAD;
1927 break;
1928 }
1929 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1930 state->mode = MATCH;
1931 case MATCH:
1932 if (left == 0) goto inf_leave;
1933 copy = out - left;
1934 if (state->offset > copy) { /* copy from window */
1935 copy = state->offset - copy;
1936 if (copy > state->write) {
1937 copy -= state->write;
1938 from = state->window + (state->wsize - copy);
1939 }
1940 else
1941 from = state->window + (state->write - copy);
1942 if (copy > state->length) copy = state->length;
1943 }
1944 else { /* copy from output */
1945 from = put - state->offset;
1946 copy = state->length;
1947 }
1948 if (copy > left) copy = left;
1949 left -= copy;
1950 state->length -= copy;
1951 do {
1952 *put++ = *from++;
1953 } while (--copy);
1954 if (state->length == 0) state->mode = LEN;
1955 break;
1956 case LIT:
1957 if (left == 0) goto inf_leave;
1958 *put++ = (unsigned char)(state->length);
1959 left--;
1960 state->mode = LEN;
1961 break;
1962 case CHECK:
1963 if (state->wrap) {
1964 NEEDBITS(32);
1965 out -= left;
1966 strm->total_out += out;
1967 state->total += out;
1968 if (out)
1969 strm->adler = state->check =
1970 UPDATE(state->check, put - out, out);
1971 out = left;
1972 if ((
1973 #ifdef GUNZIP
1974 state->flags ? hold :
1975 #endif
1976 REVERSE(hold)) != state->check) {
1977 strm->msg = __UNCONST("incorrect data check");
1978 state->mode = BAD;
1979 break;
1980 }
1981 INITBITS();
1982 Tracev((stderr, "inflate: check matches trailer\n"));
1983 }
1984 #ifdef GUNZIP
1985 state->mode = LENGTH;
1986 case LENGTH:
1987 if (state->wrap && state->flags) {
1988 NEEDBITS(32);
1989 if (hold != (state->total & 0xffffffffUL)) {
1990 strm->msg = __UNCONST("incorrect length check");
1991 state->mode = BAD;
1992 break;
1993 }
1994 INITBITS();
1995 Tracev((stderr, "inflate: length matches trailer\n"));
1996 }
1997 #endif
1998 state->mode = DONE;
1999 case DONE:
2000 ret = Z_STREAM_END;
2001 goto inf_leave;
2002 case BAD:
2003 ret = Z_DATA_ERROR;
2004 goto inf_leave;
2005 case MEM:
2006 return Z_MEM_ERROR;
2007 case SYNC:
2008 default:
2009 return Z_STREAM_ERROR;
2010 }
2011
2012 /*
2013 Return from inflate(), updating the total counts and the check value.
2014 If there was no progress during the inflate() call, return a buffer
2015 error. Call updatewindow() to create and/or update the window state.
2016 Note: a memory error from inflate() is non-recoverable.
2017 */
2018 inf_leave:
2019 RESTORE();
2020 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
2021 if (updatewindow(strm, out)) {
2022 state->mode = MEM;
2023 return Z_MEM_ERROR;
2024 }
2025 in -= strm->avail_in;
2026 out -= strm->avail_out;
2027 strm->total_in += in;
2028 strm->total_out += out;
2029 state->total += out;
2030 if (state->wrap && out)
2031 strm->adler = state->check =
2032 UPDATE(state->check, strm->next_out - out, out);
2033 strm->data_type = state->bits + (state->last ? 64 : 0) +
2034 (state->mode == TYPE ? 128 : 0);
2035 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
2036 ret = Z_BUF_ERROR;
2037 return ret;
2038 }
2039
2040 int ZEXPORT
inflateEnd(z_streamp strm)2041 inflateEnd(z_streamp strm)
2042 {
2043 struct inflate_state FAR *state;
2044 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
2045 return Z_STREAM_ERROR;
2046 state = (struct inflate_state FAR *)(void *)strm->state;
2047 if (state->window != Z_NULL) ZFREE(strm, state->window);
2048 ZFREE(strm, strm->state);
2049 strm->state = Z_NULL;
2050 Tracev((stderr, "inflate: end\n"));
2051 return Z_OK;
2052 }
2053
2054 int ZEXPORT
inflateSetDictionary(z_streamp strm,const Bytef * dictionary,uInt dictLength)2055 inflateSetDictionary(z_streamp strm, const Bytef *dictionary, uInt dictLength)
2056 {
2057 struct inflate_state FAR *state;
2058 unsigned long id;
2059
2060 /* check state */
2061 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
2062 state = (struct inflate_state FAR *)(void *)strm->state;
2063 if (state->wrap != 0 && state->mode != DICT)
2064 return Z_STREAM_ERROR;
2065
2066 /* check for correct dictionary id */
2067 if (state->mode == DICT) {
2068 id = adler32(0L, Z_NULL, 0);
2069 id = adler32(id, dictionary, dictLength);
2070 if (id != state->check)
2071 return Z_DATA_ERROR;
2072 }
2073
2074 /* copy dictionary to window */
2075 if (updatewindow(strm, strm->avail_out)) {
2076 state->mode = MEM;
2077 return Z_MEM_ERROR;
2078 }
2079 if (dictLength > state->wsize) {
2080 zmemcpy(state->window, dictionary + dictLength - state->wsize,
2081 state->wsize);
2082 state->whave = state->wsize;
2083 }
2084 else {
2085 zmemcpy(state->window + state->wsize - dictLength, dictionary,
2086 dictLength);
2087 state->whave = dictLength;
2088 }
2089 state->havedict = 1;
2090 Tracev((stderr, "inflate: dictionary set\n"));
2091 return Z_OK;
2092 }
2093
2094 int ZEXPORT
inflateGetHeader(z_streamp strm,gz_headerp head)2095 inflateGetHeader(z_streamp strm, gz_headerp head)
2096 {
2097 struct inflate_state FAR *state;
2098
2099 /* check state */
2100 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
2101 state = (struct inflate_state FAR *)(void *)strm->state;
2102 if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
2103
2104 /* save header structure */
2105 state->head = head;
2106 head->done = 0;
2107 return Z_OK;
2108 }
2109
2110 /*
2111 Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
2112 or when out of input. When called, *have is the number of pattern bytes
2113 found in order so far, in 0..3. On return *have is updated to the new
2114 state. If on return *have equals four, then the pattern was found and the
2115 return value is how many bytes were read including the last byte of the
2116 pattern. If *have is less than four, then the pattern has not been found
2117 yet and the return value is len. In the latter case, syncsearch() can be
2118 called again with more data and the *have state. *have is initialized to
2119 zero for the first call.
2120 */
2121 local unsigned
syncsearch(unsigned FAR * have,unsigned char FAR * buf,unsigned len)2122 syncsearch(unsigned FAR *have, unsigned char FAR *buf, unsigned len)
2123 {
2124 unsigned got;
2125 unsigned next;
2126
2127 got = *have;
2128 next = 0;
2129 while (next < len && got < 4) {
2130 if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
2131 got++;
2132 else if (buf[next])
2133 got = 0;
2134 else
2135 got = 4 - got;
2136 next++;
2137 }
2138 *have = got;
2139 return next;
2140 }
2141
2142 int ZEXPORT
inflateSync(z_streamp strm)2143 inflateSync(z_streamp strm)
2144 {
2145 unsigned len; /* number of bytes to look at or looked at */
2146 unsigned long in, out; /* temporary to save total_in and total_out */
2147 unsigned char buf[4]; /* to restore bit buffer to byte string */
2148 struct inflate_state FAR *state;
2149
2150 /* check parameters */
2151 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
2152 state = (struct inflate_state FAR *)(void *)strm->state;
2153 if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
2154
2155 /* if first time, start search in bit buffer */
2156 if (state->mode != SYNC) {
2157 state->mode = SYNC;
2158 state->hold <<= state->bits & 7;
2159 state->bits -= state->bits & 7;
2160 len = 0;
2161 while (state->bits >= 8) {
2162 buf[len++] = (unsigned char)(state->hold);
2163 state->hold >>= 8;
2164 state->bits -= 8;
2165 }
2166 state->have = 0;
2167 syncsearch(&(state->have), buf, len);
2168 }
2169
2170 /* search available input */
2171 len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
2172 strm->avail_in -= len;
2173 strm->next_in += len;
2174 strm->total_in += len;
2175
2176 /* return no joy or set up to restart inflate() on a new block */
2177 if (state->have != 4) return Z_DATA_ERROR;
2178 in = strm->total_in; out = strm->total_out;
2179 inflateReset(strm);
2180 strm->total_in = in; strm->total_out = out;
2181 state->mode = TYPE;
2182 return Z_OK;
2183 }
2184
2185 /*
2186 Returns true if inflate is currently at the end of a block generated by
2187 Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
2188 implementation to provide an additional safety check. PPP uses
2189 Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
2190 block. When decompressing, PPP checks that at the end of input packet,
2191 inflate is waiting for these length bytes.
2192 */
2193 int ZEXPORT
inflateSyncPoint(z_streamp strm)2194 inflateSyncPoint(z_streamp strm)
2195 {
2196 struct inflate_state FAR *state;
2197
2198 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
2199 state = (struct inflate_state FAR *)(void *)strm->state;
2200 return state->mode == STORED && state->bits == 0;
2201 }
2202
2203 int ZEXPORT
inflateCopy(z_streamp dest,z_streamp source)2204 inflateCopy(z_streamp dest, z_streamp source)
2205 {
2206 struct inflate_state FAR *state;
2207 struct inflate_state FAR *copy;
2208 unsigned char FAR *window;
2209 unsigned wsize;
2210
2211 /* check input */
2212 if (dest == Z_NULL || source == Z_NULL || source->state == Z_NULL ||
2213 source->zalloc == (alloc_func)0 || source->zfree == (free_func)0)
2214 return Z_STREAM_ERROR;
2215 state = (struct inflate_state FAR *)(void *)source->state;
2216
2217 /* allocate space */
2218 copy = (struct inflate_state FAR *)
2219 ZALLOC(source, 1, sizeof(struct inflate_state));
2220 if (copy == Z_NULL) return Z_MEM_ERROR;
2221 window = Z_NULL;
2222 if (state->window != Z_NULL) {
2223 window = (unsigned char FAR *)
2224 ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
2225 if (window == Z_NULL) {
2226 ZFREE(source, copy);
2227 return Z_MEM_ERROR;
2228 }
2229 }
2230
2231 /* copy state */
2232 zmemcpy(dest, source, sizeof(z_stream));
2233 zmemcpy(copy, state, sizeof(struct inflate_state));
2234 if (state->lencode >= state->codes &&
2235 state->lencode <= state->codes + ENOUGH - 1) {
2236 copy->lencode = copy->codes + (state->lencode - state->codes);
2237 copy->distcode = copy->codes + (state->distcode - state->codes);
2238 }
2239 copy->next = copy->codes + (state->next - state->codes);
2240 if (window != Z_NULL) {
2241 wsize = 1U << state->wbits;
2242 zmemcpy(window, state->window, wsize);
2243 }
2244 copy->window = window;
2245 dest->state = (struct internal_state FAR *)copy;
2246 return Z_OK;
2247 }
2248