2 * This file is derived from various .h and .c files from the zlib-1.2.3
3 * distribution by Jean-loup Gailly and Mark Adler, with some additions
4 * by Paul Mackerras to aid in implementing Deflate compression and
5 * decompression for PPP packets. See zlib.h for conditions of
6 * distribution and use.
8 * Changes that have been made include:
9 * - changed functions not used outside this file to "local"
10 * - added minCompression parameter to deflateInit2
11 * - added Z_PACKET_FLUSH (see zlib.h for details)
12 * - added inflateIncomp
16 /* zutil.h -- internal interface and configuration of the compression library
17 * Copyright (C) 1995-2005 Jean-loup Gailly.
18 * For conditions of distribution and use, see copyright notice in zlib.h
21 /* WARNING: this file should *not* be used by applications. It is
22 part of the implementation of the compression library and is
23 subject to change. Applications should only use zlib.h.
29 #include "u-boot/zlib.h"
30 /* To avoid a build time warning */
38 /* compile with -Dlocal if your debugger can't find static symbols */
40 typedef unsigned char uch;
42 typedef unsigned short ush;
44 typedef unsigned long ulg;
46 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
47 #define ERR_RETURN(strm,err) return (strm->msg = (char*)ERR_MSG(err), (err))
48 /* To be used only when the state is known to be valid */
51 #define NULL ((void *) 0)
54 /* common constants */
57 #define DEF_WBITS MAX_WBITS
59 /* default windowBits for decompression. MAX_WBITS is for compression only */
61 #if MAX_MEM_LEVEL >= 8
62 #define DEF_MEM_LEVEL 8
64 #define DEF_MEM_LEVEL MAX_MEM_LEVEL
66 /* default memLevel */
68 #define STORED_BLOCK 0
69 #define STATIC_TREES 1
71 /* The three kinds of block type */
75 /* The minimum and maximum match lengths */
79 #include <linux/string.h>
80 #define zmemcpy memcpy
81 #define zmemcmp memcmp
82 #define zmemzero(dest, len) memset(dest, 0, len)
84 /* Diagnostic functions */
88 extern void z_error OF((char *m));
89 #define Assert(cond,msg) {if(!(cond)) z_error(msg);}
90 #define Trace(x) {if (z_verbose>=0) fprintf x ;}
91 #define Tracev(x) {if (z_verbose>0) fprintf x ;}
92 #define Tracevv(x) {if (z_verbose>1) fprintf x ;}
93 #define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
94 #define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
96 #define Assert(cond,msg)
104 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
105 void zcfree OF((voidpf opaque, voidpf ptr, unsigned size));
107 #define ZALLOC(strm, items, size) \
108 (*((strm)->zalloc))((strm)->opaque, (items), (size))
109 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), 0)
112 /* inftrees.h -- header to use inftrees.c
113 * Copyright (C) 1995-2005 Mark Adler
114 * For conditions of distribution and use, see copyright notice in zlib.h
117 /* WARNING: this file should *not* be used by applications. It is
118 part of the implementation of the compression library and is
119 subject to change. Applications should only use zlib.h.
122 /* Structure for decoding tables. Each entry provides either the
123 information needed to do the operation requested by the code that
124 indexed that table entry, or it provides a pointer to another
125 table that indexes more bits of the code. op indicates whether
126 the entry is a pointer to another table, a literal, a length or
127 distance, an end-of-block, or an invalid code. For a table
128 pointer, the low four bits of op is the number of index bits of
129 that table. For a length or distance, the low four bits of op
130 is the number of extra bits to get after the code. bits is
131 the number of bits in this code or part of the code to drop off
132 of the bit buffer. val is the actual byte to output in the case
133 of a literal, the base length or distance, or the offset from
134 the current table to the next table. Each entry is four bytes. */
137 unsigned char op; /* operation, extra bits, table bits */
138 unsigned char bits; /* bits in this part of the code */
139 unsigned short val; /* offset in table or code value */
142 /* Maximum size of dynamic tree. The maximum found in a long but non-
143 exhaustive search was 1444 code structures (852 for length/literals
144 and 592 for distances, the latter actually the result of an
145 exhaustive search). The true maximum is not known, but the value
146 below is more than safe. */
150 /* Type of code to build for inftable() */
157 extern int inflate_table OF((codetype type, unsigned short FAR *lens,
158 unsigned codes, code FAR * FAR *table,
159 unsigned FAR *bits, unsigned short FAR *work));
161 /* inflate.h -- internal inflate state definition
162 * Copyright (C) 1995-2004 Mark Adler
163 * For conditions of distribution and use, see copyright notice in zlib.h
166 /* WARNING: this file should *not* be used by applications. It is
167 part of the implementation of the compression library and is
168 subject to change. Applications should only use zlib.h.
173 /* Possible inflate modes between inflate() calls */
175 HEAD, /* i: waiting for magic header */
176 FLAGS, /* i: waiting for method and flags (gzip) */
177 TIME, /* i: waiting for modification time (gzip) */
178 OS, /* i: waiting for extra flags and operating system (gzip) */
179 EXLEN, /* i: waiting for extra length (gzip) */
180 EXTRA, /* i: waiting for extra bytes (gzip) */
181 NAME, /* i: waiting for end of file name (gzip) */
182 COMMENT, /* i: waiting for end of comment (gzip) */
183 HCRC, /* i: waiting for header crc (gzip) */
184 DICTID, /* i: waiting for dictionary check value */
185 DICT, /* waiting for inflateSetDictionary() call */
186 TYPE, /* i: waiting for type bits, including last-flag bit */
187 TYPEDO, /* i: same, but skip check to exit inflate on new block */
188 STORED, /* i: waiting for stored size (length and complement) */
189 COPY, /* i/o: waiting for input or output to copy stored block */
190 TABLE, /* i: waiting for dynamic block table lengths */
191 LENLENS, /* i: waiting for code length code lengths */
192 CODELENS, /* i: waiting for length/lit and distance code lengths */
193 LEN, /* i: waiting for length/lit code */
194 LENEXT, /* i: waiting for length extra bits */
195 DIST, /* i: waiting for distance code */
196 DISTEXT, /* i: waiting for distance extra bits */
197 MATCH, /* o: waiting for output space to copy string */
198 LIT, /* o: waiting for output space to write literal */
199 CHECK, /* i: waiting for 32-bit check value */
200 LENGTH, /* i: waiting for 32-bit length (gzip) */
201 DONE, /* finished check, done -- remain here until reset */
202 BAD, /* got a data error -- remain here until reset */
203 MEM, /* got an inflate() memory error -- remain here until reset */
204 SYNC, /* looking for synchronization bytes to restart inflate() */
212 State transitions between above modes -
214 (most modes can go to the BAD or MEM mode -- not shown for clarity)
217 HEAD -> (gzip) or (zlib)
218 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
219 NAME -> COMMENT -> HCRC -> TYPE
220 (zlib) -> DICTID or TYPE
221 DICTID -> DICT -> TYPE
223 TYPE -> STORED or TABLE or LEN or CHECK
224 STORED -> COPY -> TYPE
225 TABLE -> LENLENS -> CODELENS -> LEN
227 LEN -> LENEXT or LIT or TYPE
228 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
231 CHECK -> LENGTH -> DONE
234 /* state maintained between inflate() calls. Approximately 7K bytes. */
235 struct inflate_state {
236 inflate_mode mode; /* current inflate mode */
237 int last; /* true if processing last block */
238 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
239 int havedict; /* true if dictionary provided */
240 int flags; /* gzip header method and flags (0 if zlib) */
241 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
242 unsigned long check; /* protected copy of check value */
243 unsigned long total; /* protected copy of output count */
244 gz_headerp head; /* where to save gzip header information */
246 unsigned wbits; /* log base 2 of requested window size */
247 unsigned wsize; /* window size or zero if not using window */
248 unsigned whave; /* valid bytes in the window */
249 unsigned write; /* window write index */
250 unsigned char FAR *window; /* allocated sliding window, if needed */
251 /* bit accumulator */
252 unsigned long hold; /* input bit accumulator */
253 unsigned bits; /* number of bits in "in" */
254 /* for string and stored block copying */
255 unsigned length; /* literal or length of data to copy */
256 unsigned offset; /* distance back to copy string from */
257 /* for table and code decoding */
258 unsigned extra; /* extra bits needed */
259 /* fixed and dynamic code tables */
260 code const FAR *lencode; /* starting table for length/literal codes */
261 code const FAR *distcode; /* starting table for distance codes */
262 unsigned lenbits; /* index bits for lencode */
263 unsigned distbits; /* index bits for distcode */
264 /* dynamic table building */
265 unsigned ncode; /* number of code length code lengths */
266 unsigned nlen; /* number of length code lengths */
267 unsigned ndist; /* number of distance code lengths */
268 unsigned have; /* number of code lengths in lens[] */
269 code FAR *next; /* next available space in codes[] */
270 unsigned short lens[320]; /* temporary storage for code lengths */
271 unsigned short work[288]; /* work area for code table building */
272 code codes[ENOUGH]; /* space for code tables */
276 /* inffast.h -- header to use inffast.c
277 * Copyright (C) 1995-2003 Mark Adler
278 * For conditions of distribution and use, see copyright notice in zlib.h
281 /* WARNING: this file should *not* be used by applications. It is
282 part of the implementation of the compression library and is
283 subject to change. Applications should only use zlib.h.
286 void inflate_fast OF((z_streamp strm, unsigned start));
288 /* inffixed.h -- table for decoding fixed codes
289 * Generated automatically by makefixed().
292 /* WARNING: this file should *not* be used by applications. It
293 is part of the implementation of the compression library and
294 is subject to change. Applications should only use zlib.h.
297 static const code lenfix[512] = {
298 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
299 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
300 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
301 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
302 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
303 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
304 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
305 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
306 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
307 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
308 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
309 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
310 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
311 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
312 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
313 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
314 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
315 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
316 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
317 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
318 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
319 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
320 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
321 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
322 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
323 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
324 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
325 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
326 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
327 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
328 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
329 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
330 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
331 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
332 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
333 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
334 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
335 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
336 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
337 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
338 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
339 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
340 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
341 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
342 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
343 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
344 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
345 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
346 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
347 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
348 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
349 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
350 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
351 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
352 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
353 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
354 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
355 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
356 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
357 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
358 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
359 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
360 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
361 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
362 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
363 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
364 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
365 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
366 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
367 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
368 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
369 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
370 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
374 static const code distfix[32] = {
375 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
376 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
377 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
378 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
379 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
384 /* inffast.c -- fast decoding
385 * Copyright (C) 1995-2004 Mark Adler
386 * For conditions of distribution and use, see copyright notice in zlib.h
389 /* Allow machine dependent optimization for post-increment or pre-increment.
390 Based on testing to date,
391 Pre-increment preferred for:
393 - MIPS R5000 (Randers-Pehrson)
394 Post-increment preferred for:
396 No measurable difference:
397 - Pentium III (Anderson)
401 #define PUP(a) *++(a)
404 Decode literal, length, and distance codes and write out the resulting
405 literal and match bytes until either not enough input or output is
406 available, an end-of-block is encountered, or a data error is encountered.
407 When large enough input and output buffers are supplied to inflate(), for
408 example, a 16K input buffer and a 64K output buffer, more than 95% of the
409 inflate execution time is spent in this routine.
415 strm->avail_out >= 258
416 start >= strm->avail_out
419 On return, state->mode is one of:
421 LEN -- ran out of enough output space or enough available input
422 TYPE -- reached end of block code, inflate() to interpret next block
423 BAD -- error in block data
427 - The maximum input bits used by a length/distance pair is 15 bits for the
428 length code, 5 bits for the length extra, 15 bits for the distance code,
429 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
430 Therefore if strm->avail_in >= 6, then there is enough input to avoid
431 checking for available input while decoding.
433 - The maximum bytes that a single length/distance pair can output is 258
434 bytes, which is the maximum length that can be coded. inflate_fast()
435 requires strm->avail_out >= 258 for each loop to avoid checking for
438 void inflate_fast(strm, start)
440 unsigned start; /* inflate()'s starting value for strm->avail_out */
442 struct inflate_state FAR *state;
443 unsigned char FAR *in; /* local strm->next_in */
444 unsigned char FAR *last; /* while in < last, enough input available */
445 unsigned char FAR *out; /* local strm->next_out */
446 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
447 unsigned char FAR *end; /* while out < end, enough space available */
448 #ifdef INFLATE_STRICT
449 unsigned dmax; /* maximum distance from zlib header */
451 unsigned wsize; /* window size or zero if not using window */
452 unsigned whave; /* valid bytes in the window */
453 unsigned write; /* window write index */
454 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
455 unsigned long hold; /* local strm->hold */
456 unsigned bits; /* local strm->bits */
457 code const FAR *lcode; /* local strm->lencode */
458 code const FAR *dcode; /* local strm->distcode */
459 unsigned lmask; /* mask for first level of length codes */
460 unsigned dmask; /* mask for first level of distance codes */
461 code this; /* retrieved table entry */
462 unsigned op; /* code bits, operation, extra bits, or */
463 /* window position, window bytes to copy */
464 unsigned len; /* match length, unused bytes */
465 unsigned dist; /* match distance */
466 unsigned char FAR *from; /* where to copy match from */
468 /* copy state to local variables */
469 state = (struct inflate_state FAR *)strm->state;
470 in = strm->next_in - OFF;
471 last = in + (strm->avail_in - 5);
472 out = strm->next_out - OFF;
473 beg = out - (start - strm->avail_out);
474 end = out + (strm->avail_out - 257);
475 #ifdef INFLATE_STRICT
478 wsize = state->wsize;
479 whave = state->whave;
480 write = state->write;
481 window = state->window;
484 lcode = state->lencode;
485 dcode = state->distcode;
486 lmask = (1U << state->lenbits) - 1;
487 dmask = (1U << state->distbits) - 1;
489 /* decode literals and length/distances until end-of-block or not enough
490 input data or output space */
493 hold += (unsigned long)(PUP(in)) << bits;
495 hold += (unsigned long)(PUP(in)) << bits;
498 this = lcode[hold & lmask];
500 op = (unsigned)(this.bits);
503 op = (unsigned)(this.op);
504 if (op == 0) { /* literal */
505 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
506 "inflate: literal '%c'\n" :
507 "inflate: literal 0x%02x\n", this.val));
508 PUP(out) = (unsigned char)(this.val);
510 else if (op & 16) { /* length base */
511 len = (unsigned)(this.val);
512 op &= 15; /* number of extra bits */
515 hold += (unsigned long)(PUP(in)) << bits;
518 len += (unsigned)hold & ((1U << op) - 1);
522 Tracevv((stderr, "inflate: length %u\n", len));
524 hold += (unsigned long)(PUP(in)) << bits;
526 hold += (unsigned long)(PUP(in)) << bits;
529 this = dcode[hold & dmask];
531 op = (unsigned)(this.bits);
534 op = (unsigned)(this.op);
535 if (op & 16) { /* distance base */
536 dist = (unsigned)(this.val);
537 op &= 15; /* number of extra bits */
539 hold += (unsigned long)(PUP(in)) << bits;
542 hold += (unsigned long)(PUP(in)) << bits;
546 dist += (unsigned)hold & ((1U << op) - 1);
547 #ifdef INFLATE_STRICT
549 strm->msg = (char *)"invalid distance too far back";
556 Tracevv((stderr, "inflate: distance %u\n", dist));
557 op = (unsigned)(out - beg); /* max distance in output */
558 if (dist > op) { /* see if copy from window */
559 op = dist - op; /* distance back in window */
561 strm->msg = (char *)"invalid distance too far back";
566 if (write == 0) { /* very common case */
568 if (op < len) { /* some from window */
571 PUP(out) = PUP(from);
573 from = out - dist; /* rest from output */
576 else if (write < op) { /* wrap around window */
577 from += wsize + write - op;
579 if (op < len) { /* some from end of window */
582 PUP(out) = PUP(from);
585 if (write < len) { /* some from start of window */
589 PUP(out) = PUP(from);
591 from = out - dist; /* rest from output */
595 else { /* contiguous in window */
597 if (op < len) { /* some from window */
600 PUP(out) = PUP(from);
602 from = out - dist; /* rest from output */
606 PUP(out) = PUP(from);
607 PUP(out) = PUP(from);
608 PUP(out) = PUP(from);
612 PUP(out) = PUP(from);
614 PUP(out) = PUP(from);
618 from = out - dist; /* copy direct from output */
619 do { /* minimum length is three */
620 PUP(out) = PUP(from);
621 PUP(out) = PUP(from);
622 PUP(out) = PUP(from);
626 PUP(out) = PUP(from);
628 PUP(out) = PUP(from);
632 else if ((op & 64) == 0) { /* 2nd level distance code */
633 this = dcode[this.val + (hold & ((1U << op) - 1))];
637 strm->msg = (char *)"invalid distance code";
642 else if ((op & 64) == 0) { /* 2nd level length code */
643 this = lcode[this.val + (hold & ((1U << op) - 1))];
646 else if (op & 32) { /* end-of-block */
647 Tracevv((stderr, "inflate: end of block\n"));
652 strm->msg = (char *)"invalid literal/length code";
656 } while (in < last && out < end);
658 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
662 hold &= (1U << bits) - 1;
664 /* update state and return */
665 strm->next_in = in + OFF;
666 strm->next_out = out + OFF;
667 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
668 strm->avail_out = (unsigned)(out < end ?
669 257 + (end - out) : 257 - (out - end));
676 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
677 - Using bit fields for code structure
678 - Different op definition to avoid & for extra bits (do & for table bits)
679 - Three separate decoding do-loops for direct, window, and write == 0
680 - Special case for distance > 1 copies to do overlapped load and store copy
681 - Explicit branch predictions (based on measured branch probabilities)
682 - Deferring match copy and interspersed it with decoding subsequent codes
683 - Swapping literal/length else
684 - Swapping window/direct else
685 - Larger unrolled copy loops (three is about right)
686 - Moving len -= 3 statement into middle of loop
690 /* inftrees.c -- generate Huffman trees for efficient decoding
691 * Copyright (C) 1995-2005 Mark Adler
692 * For conditions of distribution and use, see copyright notice in zlib.h
697 If you use the zlib library in a product, an acknowledgment is welcome
698 in the documentation of your product. If for some reason you cannot
699 include such an acknowledgment, I would appreciate that you keep this
700 copyright string in the executable of your product.
704 Build a set of tables to decode the provided canonical Huffman code.
705 The code lengths are lens[0..codes-1]. The result starts at *table,
706 whose indices are 0..2^bits-1. work is a writable array of at least
707 lens shorts, which is used as a work area. type is the type of code
708 to be generated, CODES, LENS, or DISTS. On return, zero is success,
709 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
710 on return points to the next available entry's address. bits is the
711 requested root table index bits, and on return it is the actual root
712 table index bits. It will differ if the request is greater than the
713 longest code or if it is less than the shortest code.
715 int inflate_table(type, lens, codes, table, bits, work)
717 unsigned short FAR *lens;
719 code FAR * FAR *table;
721 unsigned short FAR *work;
723 unsigned len; /* a code's length in bits */
724 unsigned sym; /* index of code symbols */
725 unsigned min, max; /* minimum and maximum code lengths */
726 unsigned root; /* number of index bits for root table */
727 unsigned curr; /* number of index bits for current table */
728 unsigned drop; /* code bits to drop for sub-table */
729 int left; /* number of prefix codes available */
730 unsigned used; /* code entries in table used */
731 unsigned huff; /* Huffman code */
732 unsigned incr; /* for incrementing code, index */
733 unsigned fill; /* index for replicating entries */
734 unsigned low; /* low bits for current root entry */
735 unsigned mask; /* mask for low root bits */
736 code this; /* table entry for duplication */
737 code FAR *next; /* next available space in table */
738 const unsigned short FAR *base; /* base value table to use */
739 const unsigned short FAR *extra; /* extra bits table to use */
740 int end; /* use base and extra for symbol > end */
741 unsigned short count[MAXBITS+1]; /* number of codes of each length */
742 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
743 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
744 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
745 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
746 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
747 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
748 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
749 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
750 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
751 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
752 8193, 12289, 16385, 24577, 0, 0};
753 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
754 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
755 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
756 28, 28, 29, 29, 64, 64};
759 Process a set of code lengths to create a canonical Huffman code. The
760 code lengths are lens[0..codes-1]. Each length corresponds to the
761 symbols 0..codes-1. The Huffman code is generated by first sorting the
762 symbols by length from short to long, and retaining the symbol order
763 for codes with equal lengths. Then the code starts with all zero bits
764 for the first code of the shortest length, and the codes are integer
765 increments for the same length, and zeros are appended as the length
766 increases. For the deflate format, these bits are stored backwards
767 from their more natural integer increment ordering, and so when the
768 decoding tables are built in the large loop below, the integer codes
769 are incremented backwards.
771 This routine assumes, but does not check, that all of the entries in
772 lens[] are in the range 0..MAXBITS. The caller must assure this.
773 1..MAXBITS is interpreted as that code length. zero means that that
774 symbol does not occur in this code.
776 The codes are sorted by computing a count of codes for each length,
777 creating from that a table of starting indices for each length in the
778 sorted table, and then entering the symbols in order in the sorted
779 table. The sorted table is work[], with that space being provided by
782 The length counts are used for other purposes as well, i.e. finding
783 the minimum and maximum length codes, determining if there are any
784 codes at all, checking for a valid set of lengths, and looking ahead
785 at length counts to determine sub-table sizes when building the
789 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
790 for (len = 0; len <= MAXBITS; len++)
792 for (sym = 0; sym < codes; sym++)
795 /* bound code lengths, force root to be within code lengths */
797 for (max = MAXBITS; max >= 1; max--)
798 if (count[max] != 0) break;
799 if (root > max) root = max;
800 if (max == 0) { /* no symbols to code at all */
801 this.op = (unsigned char)64; /* invalid code marker */
802 this.bits = (unsigned char)1;
803 this.val = (unsigned short)0;
804 *(*table)++ = this; /* make a table to force an error */
807 return 0; /* no symbols, but wait for decoding to report error */
809 for (min = 1; min <= MAXBITS; min++)
810 if (count[min] != 0) break;
811 if (root < min) root = min;
813 /* check for an over-subscribed or incomplete set of lengths */
815 for (len = 1; len <= MAXBITS; len++) {
818 if (left < 0) return -1; /* over-subscribed */
820 if (left > 0 && (type == CODES || max != 1))
821 return -1; /* incomplete set */
823 /* generate offsets into symbol table for each length for sorting */
825 for (len = 1; len < MAXBITS; len++)
826 offs[len + 1] = offs[len] + count[len];
828 /* sort symbols by length, by symbol order within each length */
829 for (sym = 0; sym < codes; sym++)
830 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
833 Create and fill in decoding tables. In this loop, the table being
834 filled is at next and has curr index bits. The code being used is huff
835 with length len. That code is converted to an index by dropping drop
836 bits off of the bottom. For codes where len is less than drop + curr,
837 those top drop + curr - len bits are incremented through all values to
838 fill the table with replicated entries.
840 root is the number of index bits for the root table. When len exceeds
841 root, sub-tables are created pointed to by the root entry with an index
842 of the low root bits of huff. This is saved in low to check for when a
843 new sub-table should be started. drop is zero when the root table is
844 being filled, and drop is root when sub-tables are being filled.
846 When a new sub-table is needed, it is necessary to look ahead in the
847 code lengths to determine what size sub-table is needed. The length
848 counts are used for this, and so count[] is decremented as codes are
849 entered in the tables.
851 used keeps track of how many table entries have been allocated from the
852 provided *table space. It is checked when a LENS table is being made
853 against the space in *table, ENOUGH, minus the maximum space needed by
854 the worst case distance code, MAXD. This should never happen, but the
855 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
856 This assumes that when type == LENS, bits == 9.
858 sym increments through all symbols, and the loop terminates when
859 all codes of length max, i.e. all codes, have been processed. This
860 routine permits incomplete codes, so another loop after this one fills
861 in the rest of the decoding tables with invalid code markers.
864 /* set up for code type */
867 base = extra = work; /* dummy value--not used */
883 /* initialize state for loop */
884 huff = 0; /* starting code */
885 sym = 0; /* starting code symbol */
886 len = min; /* starting code length */
887 next = *table; /* current table to fill in */
888 curr = root; /* current table index bits */
889 drop = 0; /* current bits to drop from code for index */
890 low = (unsigned)(-1); /* trigger new sub-table when len > root */
891 used = 1U << root; /* use root table entries */
892 mask = used - 1; /* mask for comparing low */
894 /* check available table space */
895 if (type == LENS && used >= ENOUGH - MAXD)
898 /* process all codes and make table entries */
900 /* create table entry */
901 this.bits = (unsigned char)(len - drop);
902 if ((int)(work[sym]) < end) {
903 this.op = (unsigned char)0;
904 this.val = work[sym];
906 else if ((int)(work[sym]) > end) {
907 this.op = (unsigned char)(extra[work[sym]]);
908 this.val = base[work[sym]];
911 this.op = (unsigned char)(32 + 64); /* end of block */
915 /* replicate for those indices with low len bits equal to huff */
916 incr = 1U << (len - drop);
918 min = fill; /* save offset to next table */
921 next[(huff >> drop) + fill] = this;
924 /* backwards increment the len-bit code huff */
925 incr = 1U << (len - 1);
935 /* go to next symbol, update count, len */
937 if (--(count[len]) == 0) {
938 if (len == max) break;
939 len = lens[work[sym]];
942 /* create new sub-table if needed */
943 if (len > root && (huff & mask) != low) {
944 /* if first time, transition to sub-tables */
948 /* increment past last table */
949 next += min; /* here min is 1 << curr */
951 /* determine length of next table */
953 left = (int)(1 << curr);
954 while (curr + drop < max) {
955 left -= count[curr + drop];
956 if (left <= 0) break;
961 /* check for enough space */
963 if (type == LENS && used >= ENOUGH - MAXD)
966 /* point entry in root table to sub-table */
968 (*table)[low].op = (unsigned char)curr;
969 (*table)[low].bits = (unsigned char)root;
970 (*table)[low].val = (unsigned short)(next - *table);
975 Fill in rest of table for incomplete codes. This loop is similar to the
976 loop above in incrementing huff for table indices. It is assumed that
977 len is equal to curr + drop, so there is no loop needed to increment
978 through high index bits. When the current sub-table is filled, the loop
979 drops back to the root table to fill in any remaining entries there.
981 this.op = (unsigned char)64; /* invalid code marker */
982 this.bits = (unsigned char)(len - drop);
983 this.val = (unsigned short)0;
985 /* when done with sub-table, drop back to root table */
986 if (drop != 0 && (huff & mask) != low) {
990 this.bits = (unsigned char)len;
993 /* put invalid code marker in table */
994 next[huff >> drop] = this;
996 /* backwards increment the len-bit code huff */
997 incr = 1U << (len - 1);
1008 /* set return parameters */
1015 /* inflate.c -- zlib decompression
1016 * Copyright (C) 1995-2005 Mark Adler
1017 * For conditions of distribution and use, see copyright notice in zlib.h
1019 local void fixedtables OF((struct inflate_state FAR *state));
1020 local int updatewindow OF((z_streamp strm, unsigned out));
1022 int ZEXPORT inflateReset(strm)
1025 struct inflate_state FAR *state;
1027 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1028 state = (struct inflate_state FAR *)strm->state;
1029 strm->total_in = strm->total_out = state->total = 0;
1031 strm->adler = 1; /* to support ill-conceived Java test suite */
1034 state->havedict = 0;
1035 state->dmax = 32768U;
1036 state->head = Z_NULL;
1042 state->lencode = state->distcode = state->next = state->codes;
1043 Tracev((stderr, "inflate: reset\n"));
1047 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1050 const char *version;
1053 struct inflate_state FAR *state;
1055 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1056 stream_size != (int)(sizeof(z_stream)))
1057 return Z_VERSION_ERROR;
1058 if (strm == Z_NULL) return Z_STREAM_ERROR;
1059 strm->msg = Z_NULL; /* in case we return an error */
1060 if (strm->zalloc == (alloc_func)0) {
1061 strm->zalloc = zcalloc;
1062 strm->opaque = (voidpf)0;
1064 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1065 state = (struct inflate_state FAR *)
1066 ZALLOC(strm, 1, sizeof(struct inflate_state));
1067 if (state == Z_NULL) return Z_MEM_ERROR;
1068 Tracev((stderr, "inflate: allocated\n"));
1069 strm->state = (struct internal_state FAR *)state;
1070 if (windowBits < 0) {
1072 windowBits = -windowBits;
1075 state->wrap = (windowBits >> 4) + 1;
1077 if (windowBits < 48) windowBits &= 15;
1080 if (windowBits < 8 || windowBits > 15) {
1082 strm->state = Z_NULL;
1083 return Z_STREAM_ERROR;
1085 state->wbits = (unsigned)windowBits;
1086 state->window = Z_NULL;
1087 return inflateReset(strm);
1090 int ZEXPORT inflateInit_(strm, version, stream_size)
1092 const char *version;
1095 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
1098 local void fixedtables(state)
1099 struct inflate_state FAR *state;
1101 state->lencode = lenfix;
1103 state->distcode = distfix;
1104 state->distbits = 5;
1108 Update the window with the last wsize (normally 32K) bytes written before
1109 returning. If window does not exist yet, create it. This is only called
1110 when a window is already in use, or when output has been written during this
1111 inflate call, but the end of the deflate stream has not been reached yet.
1112 It is also called to create a window for dictionary data when a dictionary
1115 Providing output buffers larger than 32K to inflate() should provide a speed
1116 advantage, since only the last 32K of output is copied to the sliding window
1117 upon return from inflate(), and since all distances after the first 32K of
1118 output will fall in the output data, making match copies simpler and faster.
1119 The advantage may be dependent on the size of the processor's data caches.
1121 local int updatewindow(strm, out)
1125 struct inflate_state FAR *state;
1126 unsigned copy, dist;
1128 state = (struct inflate_state FAR *)strm->state;
1130 /* if it hasn't been done already, allocate space for the window */
1131 if (state->window == Z_NULL) {
1132 state->window = (unsigned char FAR *)
1133 ZALLOC(strm, 1U << state->wbits,
1134 sizeof(unsigned char));
1135 if (state->window == Z_NULL) return 1;
1138 /* if window not in use yet, initialize */
1139 if (state->wsize == 0) {
1140 state->wsize = 1U << state->wbits;
1145 /* copy state->wsize or less output bytes into the circular window */
1146 copy = out - strm->avail_out;
1147 if (copy >= state->wsize) {
1148 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1150 state->whave = state->wsize;
1153 dist = state->wsize - state->write;
1154 if (dist > copy) dist = copy;
1155 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1158 zmemcpy(state->window, strm->next_out - copy, copy);
1159 state->write = copy;
1160 state->whave = state->wsize;
1163 state->write += dist;
1164 if (state->write == state->wsize) state->write = 0;
1165 if (state->whave < state->wsize) state->whave += dist;
1171 /* Macros for inflate(): */
1173 /* check function to use adler32() for zlib or crc32() for gzip */
1174 #define UPDATE(check, buf, len) \
1175 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1177 /* check macros for header crc */
1178 #define CRC2(check, word) \
1180 hbuf[0] = (unsigned char)(word); \
1181 hbuf[1] = (unsigned char)((word) >> 8); \
1182 check = crc32(check, hbuf, 2); \
1185 #define CRC4(check, word) \
1187 hbuf[0] = (unsigned char)(word); \
1188 hbuf[1] = (unsigned char)((word) >> 8); \
1189 hbuf[2] = (unsigned char)((word) >> 16); \
1190 hbuf[3] = (unsigned char)((word) >> 24); \
1191 check = crc32(check, hbuf, 4); \
1194 /* Load registers with state in inflate() for speed */
1197 put = strm->next_out; \
1198 left = strm->avail_out; \
1199 next = strm->next_in; \
1200 have = strm->avail_in; \
1201 hold = state->hold; \
1202 bits = state->bits; \
1205 /* Restore state from registers in inflate() */
1208 strm->next_out = put; \
1209 strm->avail_out = left; \
1210 strm->next_in = next; \
1211 strm->avail_in = have; \
1212 state->hold = hold; \
1213 state->bits = bits; \
1216 /* Clear the input bit accumulator */
1217 #define INITBITS() \
1223 /* Get a byte of input into the bit accumulator, or return from inflate()
1224 if there is no input available. */
1225 #define PULLBYTE() \
1227 if (have == 0) goto inf_leave; \
1229 hold += (unsigned long)(*next++) << bits; \
1233 /* Assure that there are at least n bits in the bit accumulator. If there is
1234 not enough available input to do that, then return from inflate(). */
1235 #define NEEDBITS(n) \
1237 while (bits < (unsigned)(n)) \
1241 /* Return the low n bits of the bit accumulator (n < 16) */
1243 ((unsigned)hold & ((1U << (n)) - 1))
1245 /* Remove n bits from the bit accumulator */
1246 #define DROPBITS(n) \
1249 bits -= (unsigned)(n); \
1252 /* Remove zero to seven bits as needed to go to a byte boundary */
1253 #define BYTEBITS() \
1255 hold >>= bits & 7; \
1259 /* Reverse the bytes in a 32-bit value */
1260 #define REVERSE(q) \
1261 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1262 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1265 inflate() uses a state machine to process as much input data and generate as
1266 much output data as possible before returning. The state machine is
1267 structured roughly as follows:
1269 for (;;) switch (state) {
1272 if (not enough input data or output space to make progress)
1274 ... make progress ...
1280 so when inflate() is called again, the same case is attempted again, and
1281 if the appropriate resources are provided, the machine proceeds to the
1282 next state. The NEEDBITS() macro is usually the way the state evaluates
1283 whether it can proceed or should return. NEEDBITS() does the return if
1284 the requested bits are not available. The typical use of the BITS macros
1288 ... do something with BITS(n) ...
1291 where NEEDBITS(n) either returns from inflate() if there isn't enough
1292 input left to load n bits into the accumulator, or it continues. BITS(n)
1293 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1294 the low n bits off the accumulator. INITBITS() clears the accumulator
1295 and sets the number of available bits to zero. BYTEBITS() discards just
1296 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1297 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1299 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1300 if there is no input available. The decoding of variable length codes uses
1301 PULLBYTE() directly in order to pull just enough bytes to decode the next
1304 Some states loop until they get enough input, making sure that enough
1305 state information is maintained to continue the loop where it left off
1306 if NEEDBITS() returns in the loop. For example, want, need, and keep
1307 would all have to actually be part of the saved state in case NEEDBITS()
1311 while (want < need) {
1313 keep[want++] = BITS(n);
1319 As shown above, if the next state is also the next case, then the break
1322 A state may also return if there is not enough output space available to
1323 complete that state. Those states are copying stored data, writing a
1324 literal byte, and copying a matching string.
1326 When returning, a "goto inf_leave" is used to update the total counters,
1327 update the check value, and determine whether any progress has been made
1328 during that inflate() call in order to return the proper return code.
1329 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1330 When there is a window, goto inf_leave will update the window with the last
1331 output written. If a goto inf_leave occurs in the middle of decompression
1332 and there is no window currently, goto inf_leave will create one and copy
1333 output to the window for the next call of inflate().
1335 In this implementation, the flush parameter of inflate() only affects the
1336 return code (per zlib.h). inflate() always writes as much as possible to
1337 strm->next_out, given the space available and the provided input--the effect
1338 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1339 the allocation of and copying into a sliding window until necessary, which
1340 provides the effect documented in zlib.h for Z_FINISH when the entire input
1341 stream available. So the only thing the flush parameter actually does is:
1342 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1343 will return Z_BUF_ERROR if it has not reached the end of the stream.
1345 int ZEXPORT inflate(strm, flush)
1349 struct inflate_state FAR *state;
1350 unsigned char FAR *next; /* next input */
1351 unsigned char FAR *put; /* next output */
1352 unsigned have, left; /* available input and output */
1353 unsigned long hold; /* bit buffer */
1354 unsigned bits; /* bits in bit buffer */
1355 unsigned in, out; /* save starting available input and output */
1356 unsigned copy; /* number of stored or match bytes to copy */
1357 unsigned char FAR *from; /* where to copy match bytes from */
1358 code this; /* current decoding table entry */
1359 code last; /* parent table entry */
1360 unsigned len; /* length to copy for repeats, bits to drop */
1361 int ret; /* return code */
1363 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1365 static const unsigned short order[19] = /* permutation of code lengths */
1366 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1368 if (strm == Z_NULL || strm->state == Z_NULL || strm->next_out == Z_NULL ||
1369 (strm->next_in == Z_NULL && strm->avail_in != 0))
1370 return Z_STREAM_ERROR;
1372 state = (struct inflate_state FAR *)strm->state;
1373 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1379 switch (state->mode) {
1381 if (state->wrap == 0) {
1382 state->mode = TYPEDO;
1387 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1388 state->check = crc32(0L, Z_NULL, 0);
1389 CRC2(state->check, hold);
1391 state->mode = FLAGS;
1394 state->flags = 0; /* expect zlib header */
1395 if (state->head != Z_NULL)
1396 state->head->done = -1;
1397 if (!(state->wrap & 1) || /* check if zlib header allowed */
1401 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1402 strm->msg = (char *)"incorrect header check";
1406 if (BITS(4) != Z_DEFLATED) {
1407 strm->msg = (char *)"unknown compression method";
1413 if (len > state->wbits) {
1414 strm->msg = (char *)"invalid window size";
1418 state->dmax = 1U << len;
1419 Tracev((stderr, "inflate: zlib header ok\n"));
1420 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1421 state->mode = hold & 0x200 ? DICTID : TYPE;
1427 state->flags = (int)(hold);
1428 if ((state->flags & 0xff) != Z_DEFLATED) {
1429 strm->msg = (char *)"unknown compression method";
1433 if (state->flags & 0xe000) {
1434 strm->msg = (char *)"unknown header flags set";
1438 if (state->head != Z_NULL)
1439 state->head->text = (int)((hold >> 8) & 1);
1440 if (state->flags & 0x0200) CRC2(state->check, hold);
1445 if (state->head != Z_NULL)
1446 state->head->time = hold;
1447 if (state->flags & 0x0200) CRC4(state->check, hold);
1452 if (state->head != Z_NULL) {
1453 state->head->xflags = (int)(hold & 0xff);
1454 state->head->os = (int)(hold >> 8);
1456 if (state->flags & 0x0200) CRC2(state->check, hold);
1458 state->mode = EXLEN;
1460 if (state->flags & 0x0400) {
1462 state->length = (unsigned)(hold);
1463 if (state->head != Z_NULL)
1464 state->head->extra_len = (unsigned)hold;
1465 if (state->flags & 0x0200) CRC2(state->check, hold);
1468 else if (state->head != Z_NULL)
1469 state->head->extra = Z_NULL;
1470 state->mode = EXTRA;
1472 if (state->flags & 0x0400) {
1473 copy = state->length;
1474 if (copy > have) copy = have;
1476 if (state->head != Z_NULL &&
1477 state->head->extra != Z_NULL) {
1478 len = state->head->extra_len - state->length;
1479 zmemcpy(state->head->extra + len, next,
1480 len + copy > state->head->extra_max ?
1481 state->head->extra_max - len : copy);
1483 if (state->flags & 0x0200)
1484 state->check = crc32(state->check, next, copy);
1487 state->length -= copy;
1489 if (state->length) goto inf_leave;
1494 if (state->flags & 0x0800) {
1495 if (have == 0) goto inf_leave;
1498 len = (unsigned)(next[copy++]);
1499 if (state->head != Z_NULL &&
1500 state->head->name != Z_NULL &&
1501 state->length < state->head->name_max)
1502 state->head->name[state->length++] = len;
1503 } while (len && copy < have);
1504 if (state->flags & 0x0200)
1505 state->check = crc32(state->check, next, copy);
1508 if (len) goto inf_leave;
1510 else if (state->head != Z_NULL)
1511 state->head->name = Z_NULL;
1513 state->mode = COMMENT;
1515 if (state->flags & 0x1000) {
1516 if (have == 0) goto inf_leave;
1519 len = (unsigned)(next[copy++]);
1520 if (state->head != Z_NULL &&
1521 state->head->comment != Z_NULL &&
1522 state->length < state->head->comm_max)
1523 state->head->comment[state->length++] = len;
1524 } while (len && copy < have);
1525 if (state->flags & 0x0200)
1526 state->check = crc32(state->check, next, copy);
1529 if (len) goto inf_leave;
1531 else if (state->head != Z_NULL)
1532 state->head->comment = Z_NULL;
1535 if (state->flags & 0x0200) {
1537 if (hold != (state->check & 0xffff)) {
1538 strm->msg = (char *)"header crc mismatch";
1544 if (state->head != Z_NULL) {
1545 state->head->hcrc = (int)((state->flags >> 9) & 1);
1546 state->head->done = 1;
1548 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1554 strm->adler = state->check = REVERSE(hold);
1558 if (state->havedict == 0) {
1562 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1565 if (flush == Z_BLOCK) goto inf_leave;
1569 state->mode = CHECK;
1573 state->last = BITS(1);
1576 case 0: /* stored block */
1577 Tracev((stderr, "inflate: stored block%s\n",
1578 state->last ? " (last)" : ""));
1579 state->mode = STORED;
1581 case 1: /* fixed block */
1583 Tracev((stderr, "inflate: fixed codes block%s\n",
1584 state->last ? " (last)" : ""));
1585 state->mode = LEN; /* decode codes */
1587 case 2: /* dynamic block */
1588 Tracev((stderr, "inflate: dynamic codes block%s\n",
1589 state->last ? " (last)" : ""));
1590 state->mode = TABLE;
1593 strm->msg = (char *)"invalid block type";
1599 BYTEBITS(); /* go to byte boundary */
1601 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1602 strm->msg = (char *)"invalid stored block lengths";
1606 state->length = (unsigned)hold & 0xffff;
1607 Tracev((stderr, "inflate: stored length %u\n",
1612 copy = state->length;
1614 if (copy > have) copy = have;
1615 if (copy > left) copy = left;
1616 if (copy == 0) goto inf_leave;
1617 zmemcpy(put, next, copy);
1622 state->length -= copy;
1625 Tracev((stderr, "inflate: stored end\n"));
1630 state->nlen = BITS(5) + 257;
1632 state->ndist = BITS(5) + 1;
1634 state->ncode = BITS(4) + 4;
1636 #ifndef PKZIP_BUG_WORKAROUND
1637 if (state->nlen > 286 || state->ndist > 30) {
1638 strm->msg = (char *)"too many length or distance symbols";
1643 Tracev((stderr, "inflate: table sizes ok\n"));
1645 state->mode = LENLENS;
1647 while (state->have < state->ncode) {
1649 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1652 while (state->have < 19)
1653 state->lens[order[state->have++]] = 0;
1654 state->next = state->codes;
1655 state->lencode = (code const FAR *)(state->next);
1657 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1658 &(state->lenbits), state->work);
1660 strm->msg = (char *)"invalid code lengths set";
1664 Tracev((stderr, "inflate: code lengths ok\n"));
1666 state->mode = CODELENS;
1668 while (state->have < state->nlen + state->ndist) {
1670 this = state->lencode[BITS(state->lenbits)];
1671 if ((unsigned)(this.bits) <= bits) break;
1674 if (this.val < 16) {
1675 NEEDBITS(this.bits);
1676 DROPBITS(this.bits);
1677 state->lens[state->have++] = this.val;
1680 if (this.val == 16) {
1681 NEEDBITS(this.bits + 2);
1682 DROPBITS(this.bits);
1683 if (state->have == 0) {
1684 strm->msg = (char *)"invalid bit length repeat";
1688 len = state->lens[state->have - 1];
1692 else if (this.val == 17) {
1693 NEEDBITS(this.bits + 3);
1694 DROPBITS(this.bits);
1700 NEEDBITS(this.bits + 7);
1701 DROPBITS(this.bits);
1703 copy = 11 + BITS(7);
1706 if (state->have + copy > state->nlen + state->ndist) {
1707 strm->msg = (char *)"invalid bit length repeat";
1712 state->lens[state->have++] = (unsigned short)len;
1716 /* handle error breaks in while */
1717 if (state->mode == BAD) break;
1719 /* build code tables */
1720 state->next = state->codes;
1721 state->lencode = (code const FAR *)(state->next);
1723 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1724 &(state->lenbits), state->work);
1726 strm->msg = (char *)"invalid literal/lengths set";
1730 state->distcode = (code const FAR *)(state->next);
1731 state->distbits = 6;
1732 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1733 &(state->next), &(state->distbits), state->work);
1735 strm->msg = (char *)"invalid distances set";
1739 Tracev((stderr, "inflate: codes ok\n"));
1742 if (have >= 6 && left >= 258) {
1744 inflate_fast(strm, out);
1749 this = state->lencode[BITS(state->lenbits)];
1750 if ((unsigned)(this.bits) <= bits) break;
1753 if (this.op && (this.op & 0xf0) == 0) {
1756 this = state->lencode[last.val +
1757 (BITS(last.bits + last.op) >> last.bits)];
1758 if ((unsigned)(last.bits + this.bits) <= bits) break;
1761 DROPBITS(last.bits);
1763 DROPBITS(this.bits);
1764 state->length = (unsigned)this.val;
1765 if ((int)(this.op) == 0) {
1766 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1767 "inflate: literal '%c'\n" :
1768 "inflate: literal 0x%02x\n", this.val));
1773 Tracevv((stderr, "inflate: end of block\n"));
1778 strm->msg = (char *)"invalid literal/length code";
1782 state->extra = (unsigned)(this.op) & 15;
1783 state->mode = LENEXT;
1786 NEEDBITS(state->extra);
1787 state->length += BITS(state->extra);
1788 DROPBITS(state->extra);
1790 Tracevv((stderr, "inflate: length %u\n", state->length));
1794 this = state->distcode[BITS(state->distbits)];
1795 if ((unsigned)(this.bits) <= bits) break;
1798 if ((this.op & 0xf0) == 0) {
1801 this = state->distcode[last.val +
1802 (BITS(last.bits + last.op) >> last.bits)];
1803 if ((unsigned)(last.bits + this.bits) <= bits) break;
1806 DROPBITS(last.bits);
1808 DROPBITS(this.bits);
1810 strm->msg = (char *)"invalid distance code";
1814 state->offset = (unsigned)this.val;
1815 state->extra = (unsigned)(this.op) & 15;
1816 state->mode = DISTEXT;
1819 NEEDBITS(state->extra);
1820 state->offset += BITS(state->extra);
1821 DROPBITS(state->extra);
1823 #ifdef INFLATE_STRICT
1824 if (state->offset > state->dmax) {
1825 strm->msg = (char *)"invalid distance too far back";
1830 if (state->offset > state->whave + out - left) {
1831 strm->msg = (char *)"invalid distance too far back";
1835 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1836 state->mode = MATCH;
1838 if (left == 0) goto inf_leave;
1840 if (state->offset > copy) { /* copy from window */
1841 copy = state->offset - copy;
1842 if (copy > state->write) {
1843 copy -= state->write;
1844 from = state->window + (state->wsize - copy);
1847 from = state->window + (state->write - copy);
1848 if (copy > state->length) copy = state->length;
1850 else { /* copy from output */
1851 from = put - state->offset;
1852 copy = state->length;
1854 if (copy > left) copy = left;
1856 state->length -= copy;
1860 if (state->length == 0) state->mode = LEN;
1863 if (left == 0) goto inf_leave;
1864 *put++ = (unsigned char)(state->length);
1872 strm->total_out += out;
1873 state->total += out;
1875 strm->adler = state->check =
1876 UPDATE(state->check, put - out, out);
1880 state->flags ? hold :
1882 REVERSE(hold)) != state->check) {
1883 strm->msg = (char *)"incorrect data check";
1888 Tracev((stderr, "inflate: check matches trailer\n"));
1891 state->mode = LENGTH;
1893 if (state->wrap && state->flags) {
1895 if (hold != (state->total & 0xffffffffUL)) {
1896 strm->msg = (char *)"incorrect length check";
1901 Tracev((stderr, "inflate: length matches trailer\n"));
1915 return Z_STREAM_ERROR;
1919 Return from inflate(), updating the total counts and the check value.
1920 If there was no progress during the inflate() call, return a buffer
1921 error. Call updatewindow() to create and/or update the window state.
1922 Note: a memory error from inflate() is non-recoverable.
1926 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1927 if (updatewindow(strm, out)) {
1931 in -= strm->avail_in;
1932 out -= strm->avail_out;
1933 strm->total_in += in;
1934 strm->total_out += out;
1935 state->total += out;
1936 if (state->wrap && out)
1937 strm->adler = state->check =
1938 UPDATE(state->check, strm->next_out - out, out);
1939 strm->data_type = state->bits + (state->last ? 64 : 0) +
1940 (state->mode == TYPE ? 128 : 0);
1941 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1946 int ZEXPORT inflateEnd(strm)
1949 struct inflate_state FAR *state;
1950 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1951 return Z_STREAM_ERROR;
1952 state = (struct inflate_state FAR *)strm->state;
1953 if (state->window != Z_NULL) ZFREE(strm, state->window);
1954 ZFREE(strm, strm->state);
1955 strm->state = Z_NULL;
1956 Tracev((stderr, "inflate: end\n"));
1961 /* zutil.c -- target dependent utility functions for the compression library
1962 * Copyright (C) 1995-2005 Jean-loup Gailly.
1963 * For conditions of distribution and use, see copyright notice in zlib.h
1968 #ifndef NO_DUMMY_DECL
1969 struct internal_state {int dummy;}; /* for buggy compilers */
1972 const char * const z_errmsg[10] = {
1973 "need dictionary", /* Z_NEED_DICT 2 */
1974 "stream end", /* Z_STREAM_END 1 */
1976 "file error", /* Z_ERRNO (-1) */
1977 "stream error", /* Z_STREAM_ERROR (-2) */
1978 "data error", /* Z_DATA_ERROR (-3) */
1979 "insufficient memory", /* Z_MEM_ERROR (-4) */
1980 "buffer error", /* Z_BUF_ERROR (-5) */
1981 "incompatible version",/* Z_VERSION_ERROR (-6) */
1989 int z_verbose = verbose;
1994 fprintf(stderr, "%s\n", m);
1999 /* exported to allow conversion of error code to string for compress() and
2002 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
2005 extern voidp malloc OF((uInt size));
2006 extern voidp calloc OF((uInt items, uInt size));
2007 extern void free OF((voidpf ptr));
2010 voidpf zcalloc (opaque, items, size)
2016 items += size - size; /* make compiler happy */
2017 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2018 (voidpf)calloc(items, size);
2021 void zcfree (opaque, ptr, nb)
2028 return; /* make compiler happy */
2031 #endif /* MY_ZCALLOC */
2033 /* adler32.c -- compute the Adler-32 checksum of a data stream
2034 * Copyright (C) 1995-2004 Mark Adler
2035 * For conditions of distribution and use, see copyright notice in zlib.h
2040 #define BASE 65521UL /* largest prime smaller than 65536 */
2042 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2044 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2045 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2046 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2047 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2048 #define DO16(buf) DO8(buf,0); DO8(buf,8);
2050 /* use NO_DIVIDE if your processor does not do division in hardware */
2054 if (a >= (BASE << 16)) \
2055 a -= (BASE << 16); \
2056 if (a >= (BASE << 15)) \
2057 a -= (BASE << 15); \
2058 if (a >= (BASE << 14)) \
2059 a -= (BASE << 14); \
2060 if (a >= (BASE << 13)) \
2061 a -= (BASE << 13); \
2062 if (a >= (BASE << 12)) \
2063 a -= (BASE << 12); \
2064 if (a >= (BASE << 11)) \
2065 a -= (BASE << 11); \
2066 if (a >= (BASE << 10)) \
2067 a -= (BASE << 10); \
2068 if (a >= (BASE << 9)) \
2070 if (a >= (BASE << 8)) \
2072 if (a >= (BASE << 7)) \
2074 if (a >= (BASE << 6)) \
2076 if (a >= (BASE << 5)) \
2078 if (a >= (BASE << 4)) \
2080 if (a >= (BASE << 3)) \
2082 if (a >= (BASE << 2)) \
2084 if (a >= (BASE << 1)) \
2091 if (a >= (BASE << 4)) \
2093 if (a >= (BASE << 3)) \
2095 if (a >= (BASE << 2)) \
2097 if (a >= (BASE << 1)) \
2103 #define MOD(a) a %= BASE
2104 #define MOD4(a) a %= BASE
2107 /* ========================================================================= */
2108 uLong ZEXPORT adler32(adler, buf, len)
2116 /* split Adler-32 into component sums */
2117 sum2 = (adler >> 16) & 0xffff;
2120 /* in case user likes doing a byte at a time, keep it fast */
2128 return adler | (sum2 << 16);
2131 /* initial Adler-32 value (deferred check for len == 1 speed) */
2135 /* in case short lengths are provided, keep it somewhat fast */
2143 MOD4(sum2); /* only added so many BASE's */
2144 return adler | (sum2 << 16);
2147 /* do length NMAX blocks -- requires just one modulo operation */
2148 while (len >= NMAX) {
2150 n = NMAX / 16; /* NMAX is divisible by 16 */
2152 DO16(buf); /* 16 sums unrolled */
2159 /* do remaining bytes (less than NMAX, still just one modulo) */
2160 if (len) { /* avoid modulos if none remaining */
2174 /* return recombined sums */
2175 return adler | (sum2 << 16);