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"
31 /* To avoid a build time warning */
39 /* compile with -Dlocal if your debugger can't find static symbols */
41 typedef unsigned char uch;
43 typedef unsigned short ush;
45 typedef unsigned long ulg;
47 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
48 #define ERR_RETURN(strm,err) return (strm->msg = (char*)ERR_MSG(err), (err))
49 /* To be used only when the state is known to be valid */
52 #define NULL ((void *) 0)
55 /* common constants */
58 #define DEF_WBITS MAX_WBITS
60 /* default windowBits for decompression. MAX_WBITS is for compression only */
62 #if MAX_MEM_LEVEL >= 8
63 #define DEF_MEM_LEVEL 8
65 #define DEF_MEM_LEVEL MAX_MEM_LEVEL
67 /* default memLevel */
69 #define STORED_BLOCK 0
70 #define STATIC_TREES 1
72 /* The three kinds of block type */
76 /* The minimum and maximum match lengths */
80 #include <linux/string.h>
81 #define zmemcpy memcpy
82 #define zmemcmp memcmp
83 #define zmemzero(dest, len) memset(dest, 0, len)
85 /* Diagnostic functions */
88 extern void z_error OF((char *m));
89 #define Assert(cond,msg) {if(!(cond)) z_error(msg);}
90 #define fprintf(fp,...) printf(__VA_ARGS__)
91 #define Trace(x) {if (z_verbose>=0) fprintf x ;}
92 #define Tracev(x) {if (z_verbose>0) fprintf x ;}
93 #define Tracevv(x) {if (z_verbose>1) fprintf x ;}
94 #define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
95 #define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
97 #define Assert(cond,msg)
105 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
106 void zcfree OF((voidpf opaque, voidpf ptr, unsigned size));
108 #define ZALLOC(strm, items, size) \
109 (*((strm)->zalloc))((strm)->opaque, (items), (size))
110 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), 0)
113 /* inftrees.h -- header to use inftrees.c
114 * Copyright (C) 1995-2005 Mark Adler
115 * For conditions of distribution and use, see copyright notice in zlib.h
118 /* WARNING: this file should *not* be used by applications. It is
119 part of the implementation of the compression library and is
120 subject to change. Applications should only use zlib.h.
123 /* Structure for decoding tables. Each entry provides either the
124 information needed to do the operation requested by the code that
125 indexed that table entry, or it provides a pointer to another
126 table that indexes more bits of the code. op indicates whether
127 the entry is a pointer to another table, a literal, a length or
128 distance, an end-of-block, or an invalid code. For a table
129 pointer, the low four bits of op is the number of index bits of
130 that table. For a length or distance, the low four bits of op
131 is the number of extra bits to get after the code. bits is
132 the number of bits in this code or part of the code to drop off
133 of the bit buffer. val is the actual byte to output in the case
134 of a literal, the base length or distance, or the offset from
135 the current table to the next table. Each entry is four bytes. */
138 unsigned char op; /* operation, extra bits, table bits */
139 unsigned char bits; /* bits in this part of the code */
140 unsigned short val; /* offset in table or code value */
143 /* Maximum size of dynamic tree. The maximum found in a long but non-
144 exhaustive search was 1444 code structures (852 for length/literals
145 and 592 for distances, the latter actually the result of an
146 exhaustive search). The true maximum is not known, but the value
147 below is more than safe. */
151 /* Type of code to build for inftable() */
158 extern int inflate_table OF((codetype type, unsigned short FAR *lens,
159 unsigned codes, code FAR * FAR *table,
160 unsigned FAR *bits, unsigned short FAR *work));
162 /* inflate.h -- internal inflate state definition
163 * Copyright (C) 1995-2004 Mark Adler
164 * For conditions of distribution and use, see copyright notice in zlib.h
167 /* WARNING: this file should *not* be used by applications. It is
168 part of the implementation of the compression library and is
169 subject to change. Applications should only use zlib.h.
174 /* Possible inflate modes between inflate() calls */
176 HEAD, /* i: waiting for magic header */
177 FLAGS, /* i: waiting for method and flags (gzip) */
178 TIME, /* i: waiting for modification time (gzip) */
179 OS, /* i: waiting for extra flags and operating system (gzip) */
180 EXLEN, /* i: waiting for extra length (gzip) */
181 EXTRA, /* i: waiting for extra bytes (gzip) */
182 NAME, /* i: waiting for end of file name (gzip) */
183 COMMENT, /* i: waiting for end of comment (gzip) */
184 HCRC, /* i: waiting for header crc (gzip) */
185 DICTID, /* i: waiting for dictionary check value */
186 DICT, /* waiting for inflateSetDictionary() call */
187 TYPE, /* i: waiting for type bits, including last-flag bit */
188 TYPEDO, /* i: same, but skip check to exit inflate on new block */
189 STORED, /* i: waiting for stored size (length and complement) */
190 COPY, /* i/o: waiting for input or output to copy stored block */
191 TABLE, /* i: waiting for dynamic block table lengths */
192 LENLENS, /* i: waiting for code length code lengths */
193 CODELENS, /* i: waiting for length/lit and distance code lengths */
194 LEN, /* i: waiting for length/lit code */
195 LENEXT, /* i: waiting for length extra bits */
196 DIST, /* i: waiting for distance code */
197 DISTEXT, /* i: waiting for distance extra bits */
198 MATCH, /* o: waiting for output space to copy string */
199 LIT, /* o: waiting for output space to write literal */
200 CHECK, /* i: waiting for 32-bit check value */
201 LENGTH, /* i: waiting for 32-bit length (gzip) */
202 DONE, /* finished check, done -- remain here until reset */
203 BAD, /* got a data error -- remain here until reset */
204 MEM, /* got an inflate() memory error -- remain here until reset */
205 SYNC, /* looking for synchronization bytes to restart inflate() */
213 State transitions between above modes -
215 (most modes can go to the BAD or MEM mode -- not shown for clarity)
218 HEAD -> (gzip) or (zlib)
219 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
220 NAME -> COMMENT -> HCRC -> TYPE
221 (zlib) -> DICTID or TYPE
222 DICTID -> DICT -> TYPE
224 TYPE -> STORED or TABLE or LEN or CHECK
225 STORED -> COPY -> TYPE
226 TABLE -> LENLENS -> CODELENS -> LEN
228 LEN -> LENEXT or LIT or TYPE
229 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
232 CHECK -> LENGTH -> DONE
235 /* state maintained between inflate() calls. Approximately 7K bytes. */
236 struct inflate_state {
237 inflate_mode mode; /* current inflate mode */
238 int last; /* true if processing last block */
239 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
240 int havedict; /* true if dictionary provided */
241 int flags; /* gzip header method and flags (0 if zlib) */
242 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
243 unsigned long check; /* protected copy of check value */
244 unsigned long total; /* protected copy of output count */
245 gz_headerp head; /* where to save gzip header information */
247 unsigned wbits; /* log base 2 of requested window size */
248 unsigned wsize; /* window size or zero if not using window */
249 unsigned whave; /* valid bytes in the window */
250 unsigned write; /* window write index */
251 unsigned char FAR *window; /* allocated sliding window, if needed */
252 /* bit accumulator */
253 unsigned long hold; /* input bit accumulator */
254 unsigned bits; /* number of bits in "in" */
255 /* for string and stored block copying */
256 unsigned length; /* literal or length of data to copy */
257 unsigned offset; /* distance back to copy string from */
258 /* for table and code decoding */
259 unsigned extra; /* extra bits needed */
260 /* fixed and dynamic code tables */
261 code const FAR *lencode; /* starting table for length/literal codes */
262 code const FAR *distcode; /* starting table for distance codes */
263 unsigned lenbits; /* index bits for lencode */
264 unsigned distbits; /* index bits for distcode */
265 /* dynamic table building */
266 unsigned ncode; /* number of code length code lengths */
267 unsigned nlen; /* number of length code lengths */
268 unsigned ndist; /* number of distance code lengths */
269 unsigned have; /* number of code lengths in lens[] */
270 code FAR *next; /* next available space in codes[] */
271 unsigned short lens[320]; /* temporary storage for code lengths */
272 unsigned short work[288]; /* work area for code table building */
273 code codes[ENOUGH]; /* space for code tables */
277 /* inffast.h -- header to use inffast.c
278 * Copyright (C) 1995-2003 Mark Adler
279 * For conditions of distribution and use, see copyright notice in zlib.h
282 /* WARNING: this file should *not* be used by applications. It is
283 part of the implementation of the compression library and is
284 subject to change. Applications should only use zlib.h.
287 void inflate_fast OF((z_streamp strm, unsigned start));
289 /* inffixed.h -- table for decoding fixed codes
290 * Generated automatically by makefixed().
293 /* WARNING: this file should *not* be used by applications. It
294 is part of the implementation of the compression library and
295 is subject to change. Applications should only use zlib.h.
298 static const code lenfix[512] = {
299 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
300 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
301 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
302 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
303 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
304 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
305 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
306 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
307 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
308 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
309 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
310 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
311 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
312 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
313 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
314 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
315 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
316 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
317 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
318 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
319 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
320 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
321 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
322 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
323 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
324 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
325 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
326 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
327 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
328 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
329 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
330 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
331 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
332 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
333 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
334 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
335 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
336 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
337 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
338 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
339 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
340 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
341 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
342 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
343 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
344 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
345 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
346 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
347 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
348 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
349 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
350 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
351 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
352 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
353 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
354 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
355 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
356 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
357 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
358 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
359 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
360 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
361 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
362 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
363 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
364 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
365 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
366 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
367 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
368 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
369 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
370 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
371 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
375 static const code distfix[32] = {
376 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
377 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
378 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
379 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
380 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
385 /* inffast.c -- fast decoding
386 * Copyright (C) 1995-2004 Mark Adler
387 * For conditions of distribution and use, see copyright notice in zlib.h
390 /* Allow machine dependent optimization for post-increment or pre-increment.
391 Based on testing to date,
392 Pre-increment preferred for:
394 - MIPS R5000 (Randers-Pehrson)
395 Post-increment preferred for:
397 No measurable difference:
398 - Pentium III (Anderson)
402 #define PUP(a) *++(a)
405 Decode literal, length, and distance codes and write out the resulting
406 literal and match bytes until either not enough input or output is
407 available, an end-of-block is encountered, or a data error is encountered.
408 When large enough input and output buffers are supplied to inflate(), for
409 example, a 16K input buffer and a 64K output buffer, more than 95% of the
410 inflate execution time is spent in this routine.
416 strm->avail_out >= 258
417 start >= strm->avail_out
420 On return, state->mode is one of:
422 LEN -- ran out of enough output space or enough available input
423 TYPE -- reached end of block code, inflate() to interpret next block
424 BAD -- error in block data
428 - The maximum input bits used by a length/distance pair is 15 bits for the
429 length code, 5 bits for the length extra, 15 bits for the distance code,
430 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
431 Therefore if strm->avail_in >= 6, then there is enough input to avoid
432 checking for available input while decoding.
434 - The maximum bytes that a single length/distance pair can output is 258
435 bytes, which is the maximum length that can be coded. inflate_fast()
436 requires strm->avail_out >= 258 for each loop to avoid checking for
439 void inflate_fast(strm, start)
441 unsigned start; /* inflate()'s starting value for strm->avail_out */
443 struct inflate_state FAR *state;
444 unsigned char FAR *in; /* local strm->next_in */
445 unsigned char FAR *last; /* while in < last, enough input available */
446 unsigned char FAR *out; /* local strm->next_out */
447 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
448 unsigned char FAR *end; /* while out < end, enough space available */
449 #ifdef INFLATE_STRICT
450 unsigned dmax; /* maximum distance from zlib header */
452 unsigned wsize; /* window size or zero if not using window */
453 unsigned whave; /* valid bytes in the window */
454 unsigned write; /* window write index */
455 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
456 unsigned long hold; /* local strm->hold */
457 unsigned bits; /* local strm->bits */
458 code const FAR *lcode; /* local strm->lencode */
459 code const FAR *dcode; /* local strm->distcode */
460 unsigned lmask; /* mask for first level of length codes */
461 unsigned dmask; /* mask for first level of distance codes */
462 code this; /* retrieved table entry */
463 unsigned op; /* code bits, operation, extra bits, or */
464 /* window position, window bytes to copy */
465 unsigned len; /* match length, unused bytes */
466 unsigned dist; /* match distance */
467 unsigned char FAR *from; /* where to copy match from */
469 /* copy state to local variables */
470 state = (struct inflate_state FAR *)strm->state;
471 in = strm->next_in - OFF;
472 last = in + (strm->avail_in - 5);
473 out = strm->next_out - OFF;
474 beg = out - (start - strm->avail_out);
475 end = out + (strm->avail_out - 257);
476 #ifdef INFLATE_STRICT
479 wsize = state->wsize;
480 whave = state->whave;
481 write = state->write;
482 window = state->window;
485 lcode = state->lencode;
486 dcode = state->distcode;
487 lmask = (1U << state->lenbits) - 1;
488 dmask = (1U << state->distbits) - 1;
490 /* decode literals and length/distances until end-of-block or not enough
491 input data or output space */
494 hold += (unsigned long)(PUP(in)) << bits;
496 hold += (unsigned long)(PUP(in)) << bits;
499 this = lcode[hold & lmask];
501 op = (unsigned)(this.bits);
504 op = (unsigned)(this.op);
505 if (op == 0) { /* literal */
506 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
507 "inflate: literal '%c'\n" :
508 "inflate: literal 0x%02x\n", this.val));
509 PUP(out) = (unsigned char)(this.val);
511 else if (op & 16) { /* length base */
512 len = (unsigned)(this.val);
513 op &= 15; /* number of extra bits */
516 hold += (unsigned long)(PUP(in)) << bits;
519 len += (unsigned)hold & ((1U << op) - 1);
523 Tracevv((stderr, "inflate: length %u\n", len));
525 hold += (unsigned long)(PUP(in)) << bits;
527 hold += (unsigned long)(PUP(in)) << bits;
530 this = dcode[hold & dmask];
532 op = (unsigned)(this.bits);
535 op = (unsigned)(this.op);
536 if (op & 16) { /* distance base */
537 dist = (unsigned)(this.val);
538 op &= 15; /* number of extra bits */
540 hold += (unsigned long)(PUP(in)) << bits;
543 hold += (unsigned long)(PUP(in)) << bits;
547 dist += (unsigned)hold & ((1U << op) - 1);
548 #ifdef INFLATE_STRICT
550 strm->msg = (char *)"invalid distance too far back";
557 Tracevv((stderr, "inflate: distance %u\n", dist));
558 op = (unsigned)(out - beg); /* max distance in output */
559 if (dist > op) { /* see if copy from window */
560 op = dist - op; /* distance back in window */
562 strm->msg = (char *)"invalid distance too far back";
567 if (write == 0) { /* very common case */
569 if (op < len) { /* some from window */
572 PUP(out) = PUP(from);
574 from = out - dist; /* rest from output */
577 else if (write < op) { /* wrap around window */
578 from += wsize + write - op;
580 if (op < len) { /* some from end of window */
583 PUP(out) = PUP(from);
586 if (write < len) { /* some from start of window */
590 PUP(out) = PUP(from);
592 from = out - dist; /* rest from output */
596 else { /* contiguous in window */
598 if (op < len) { /* some from window */
601 PUP(out) = PUP(from);
603 from = out - dist; /* rest from output */
607 PUP(out) = PUP(from);
608 PUP(out) = PUP(from);
609 PUP(out) = PUP(from);
613 PUP(out) = PUP(from);
615 PUP(out) = PUP(from);
619 from = out - dist; /* copy direct from output */
620 do { /* minimum length is three */
621 PUP(out) = PUP(from);
622 PUP(out) = PUP(from);
623 PUP(out) = PUP(from);
627 PUP(out) = PUP(from);
629 PUP(out) = PUP(from);
633 else if ((op & 64) == 0) { /* 2nd level distance code */
634 this = dcode[this.val + (hold & ((1U << op) - 1))];
638 strm->msg = (char *)"invalid distance code";
643 else if ((op & 64) == 0) { /* 2nd level length code */
644 this = lcode[this.val + (hold & ((1U << op) - 1))];
647 else if (op & 32) { /* end-of-block */
648 Tracevv((stderr, "inflate: end of block\n"));
653 strm->msg = (char *)"invalid literal/length code";
657 } while (in < last && out < end);
659 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
663 hold &= (1U << bits) - 1;
665 /* update state and return */
666 strm->next_in = in + OFF;
667 strm->next_out = out + OFF;
668 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
669 strm->avail_out = (unsigned)(out < end ?
670 257 + (end - out) : 257 - (out - end));
677 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
678 - Using bit fields for code structure
679 - Different op definition to avoid & for extra bits (do & for table bits)
680 - Three separate decoding do-loops for direct, window, and write == 0
681 - Special case for distance > 1 copies to do overlapped load and store copy
682 - Explicit branch predictions (based on measured branch probabilities)
683 - Deferring match copy and interspersed it with decoding subsequent codes
684 - Swapping literal/length else
685 - Swapping window/direct else
686 - Larger unrolled copy loops (three is about right)
687 - Moving len -= 3 statement into middle of loop
691 /* inftrees.c -- generate Huffman trees for efficient decoding
692 * Copyright (C) 1995-2005 Mark Adler
693 * For conditions of distribution and use, see copyright notice in zlib.h
698 If you use the zlib library in a product, an acknowledgment is welcome
699 in the documentation of your product. If for some reason you cannot
700 include such an acknowledgment, I would appreciate that you keep this
701 copyright string in the executable of your product.
705 Build a set of tables to decode the provided canonical Huffman code.
706 The code lengths are lens[0..codes-1]. The result starts at *table,
707 whose indices are 0..2^bits-1. work is a writable array of at least
708 lens shorts, which is used as a work area. type is the type of code
709 to be generated, CODES, LENS, or DISTS. On return, zero is success,
710 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
711 on return points to the next available entry's address. bits is the
712 requested root table index bits, and on return it is the actual root
713 table index bits. It will differ if the request is greater than the
714 longest code or if it is less than the shortest code.
716 int inflate_table(type, lens, codes, table, bits, work)
718 unsigned short FAR *lens;
720 code FAR * FAR *table;
722 unsigned short FAR *work;
724 unsigned len; /* a code's length in bits */
725 unsigned sym; /* index of code symbols */
726 unsigned min, max; /* minimum and maximum code lengths */
727 unsigned root; /* number of index bits for root table */
728 unsigned curr; /* number of index bits for current table */
729 unsigned drop; /* code bits to drop for sub-table */
730 int left; /* number of prefix codes available */
731 unsigned used; /* code entries in table used */
732 unsigned huff; /* Huffman code */
733 unsigned incr; /* for incrementing code, index */
734 unsigned fill; /* index for replicating entries */
735 unsigned low; /* low bits for current root entry */
736 unsigned mask; /* mask for low root bits */
737 code this; /* table entry for duplication */
738 code FAR *next; /* next available space in table */
739 const unsigned short FAR *base; /* base value table to use */
740 const unsigned short FAR *extra; /* extra bits table to use */
741 int end; /* use base and extra for symbol > end */
742 unsigned short count[MAXBITS+1]; /* number of codes of each length */
743 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
744 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
745 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
746 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
747 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
748 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
749 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
750 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
751 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
752 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
753 8193, 12289, 16385, 24577, 0, 0};
754 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
755 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
756 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
757 28, 28, 29, 29, 64, 64};
760 Process a set of code lengths to create a canonical Huffman code. The
761 code lengths are lens[0..codes-1]. Each length corresponds to the
762 symbols 0..codes-1. The Huffman code is generated by first sorting the
763 symbols by length from short to long, and retaining the symbol order
764 for codes with equal lengths. Then the code starts with all zero bits
765 for the first code of the shortest length, and the codes are integer
766 increments for the same length, and zeros are appended as the length
767 increases. For the deflate format, these bits are stored backwards
768 from their more natural integer increment ordering, and so when the
769 decoding tables are built in the large loop below, the integer codes
770 are incremented backwards.
772 This routine assumes, but does not check, that all of the entries in
773 lens[] are in the range 0..MAXBITS. The caller must assure this.
774 1..MAXBITS is interpreted as that code length. zero means that that
775 symbol does not occur in this code.
777 The codes are sorted by computing a count of codes for each length,
778 creating from that a table of starting indices for each length in the
779 sorted table, and then entering the symbols in order in the sorted
780 table. The sorted table is work[], with that space being provided by
783 The length counts are used for other purposes as well, i.e. finding
784 the minimum and maximum length codes, determining if there are any
785 codes at all, checking for a valid set of lengths, and looking ahead
786 at length counts to determine sub-table sizes when building the
790 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
791 for (len = 0; len <= MAXBITS; len++)
793 for (sym = 0; sym < codes; sym++)
796 /* bound code lengths, force root to be within code lengths */
798 for (max = MAXBITS; max >= 1; max--)
799 if (count[max] != 0) break;
800 if (root > max) root = max;
801 if (max == 0) { /* no symbols to code at all */
802 this.op = (unsigned char)64; /* invalid code marker */
803 this.bits = (unsigned char)1;
804 this.val = (unsigned short)0;
805 *(*table)++ = this; /* make a table to force an error */
808 return 0; /* no symbols, but wait for decoding to report error */
810 for (min = 1; min <= MAXBITS; min++)
811 if (count[min] != 0) break;
812 if (root < min) root = min;
814 /* check for an over-subscribed or incomplete set of lengths */
816 for (len = 1; len <= MAXBITS; len++) {
819 if (left < 0) return -1; /* over-subscribed */
821 if (left > 0 && (type == CODES || max != 1))
822 return -1; /* incomplete set */
824 /* generate offsets into symbol table for each length for sorting */
826 for (len = 1; len < MAXBITS; len++)
827 offs[len + 1] = offs[len] + count[len];
829 /* sort symbols by length, by symbol order within each length */
830 for (sym = 0; sym < codes; sym++)
831 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
834 Create and fill in decoding tables. In this loop, the table being
835 filled is at next and has curr index bits. The code being used is huff
836 with length len. That code is converted to an index by dropping drop
837 bits off of the bottom. For codes where len is less than drop + curr,
838 those top drop + curr - len bits are incremented through all values to
839 fill the table with replicated entries.
841 root is the number of index bits for the root table. When len exceeds
842 root, sub-tables are created pointed to by the root entry with an index
843 of the low root bits of huff. This is saved in low to check for when a
844 new sub-table should be started. drop is zero when the root table is
845 being filled, and drop is root when sub-tables are being filled.
847 When a new sub-table is needed, it is necessary to look ahead in the
848 code lengths to determine what size sub-table is needed. The length
849 counts are used for this, and so count[] is decremented as codes are
850 entered in the tables.
852 used keeps track of how many table entries have been allocated from the
853 provided *table space. It is checked when a LENS table is being made
854 against the space in *table, ENOUGH, minus the maximum space needed by
855 the worst case distance code, MAXD. This should never happen, but the
856 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
857 This assumes that when type == LENS, bits == 9.
859 sym increments through all symbols, and the loop terminates when
860 all codes of length max, i.e. all codes, have been processed. This
861 routine permits incomplete codes, so another loop after this one fills
862 in the rest of the decoding tables with invalid code markers.
865 /* set up for code type */
868 base = extra = work; /* dummy value--not used */
884 /* initialize state for loop */
885 huff = 0; /* starting code */
886 sym = 0; /* starting code symbol */
887 len = min; /* starting code length */
888 next = *table; /* current table to fill in */
889 curr = root; /* current table index bits */
890 drop = 0; /* current bits to drop from code for index */
891 low = (unsigned)(-1); /* trigger new sub-table when len > root */
892 used = 1U << root; /* use root table entries */
893 mask = used - 1; /* mask for comparing low */
895 /* check available table space */
896 if (type == LENS && used >= ENOUGH - MAXD)
899 /* process all codes and make table entries */
901 /* create table entry */
902 this.bits = (unsigned char)(len - drop);
903 if ((int)(work[sym]) < end) {
904 this.op = (unsigned char)0;
905 this.val = work[sym];
907 else if ((int)(work[sym]) > end) {
908 this.op = (unsigned char)(extra[work[sym]]);
909 this.val = base[work[sym]];
912 this.op = (unsigned char)(32 + 64); /* end of block */
916 /* replicate for those indices with low len bits equal to huff */
917 incr = 1U << (len - drop);
919 min = fill; /* save offset to next table */
922 next[(huff >> drop) + fill] = this;
925 /* backwards increment the len-bit code huff */
926 incr = 1U << (len - 1);
936 /* go to next symbol, update count, len */
938 if (--(count[len]) == 0) {
939 if (len == max) break;
940 len = lens[work[sym]];
943 /* create new sub-table if needed */
944 if (len > root && (huff & mask) != low) {
945 /* if first time, transition to sub-tables */
949 /* increment past last table */
950 next += min; /* here min is 1 << curr */
952 /* determine length of next table */
954 left = (int)(1 << curr);
955 while (curr + drop < max) {
956 left -= count[curr + drop];
957 if (left <= 0) break;
962 /* check for enough space */
964 if (type == LENS && used >= ENOUGH - MAXD)
967 /* point entry in root table to sub-table */
969 (*table)[low].op = (unsigned char)curr;
970 (*table)[low].bits = (unsigned char)root;
971 (*table)[low].val = (unsigned short)(next - *table);
976 Fill in rest of table for incomplete codes. This loop is similar to the
977 loop above in incrementing huff for table indices. It is assumed that
978 len is equal to curr + drop, so there is no loop needed to increment
979 through high index bits. When the current sub-table is filled, the loop
980 drops back to the root table to fill in any remaining entries there.
982 this.op = (unsigned char)64; /* invalid code marker */
983 this.bits = (unsigned char)(len - drop);
984 this.val = (unsigned short)0;
986 /* when done with sub-table, drop back to root table */
987 if (drop != 0 && (huff & mask) != low) {
991 this.bits = (unsigned char)len;
994 /* put invalid code marker in table */
995 next[huff >> drop] = this;
997 /* backwards increment the len-bit code huff */
998 incr = 1U << (len - 1);
1009 /* set return parameters */
1016 /* inflate.c -- zlib decompression
1017 * Copyright (C) 1995-2005 Mark Adler
1018 * For conditions of distribution and use, see copyright notice in zlib.h
1020 local void fixedtables OF((struct inflate_state FAR *state));
1021 local int updatewindow OF((z_streamp strm, unsigned out));
1023 int ZEXPORT inflateReset(strm)
1026 struct inflate_state FAR *state;
1028 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1029 state = (struct inflate_state FAR *)strm->state;
1030 strm->total_in = strm->total_out = state->total = 0;
1032 strm->adler = 1; /* to support ill-conceived Java test suite */
1035 state->havedict = 0;
1036 state->dmax = 32768U;
1037 state->head = Z_NULL;
1043 state->lencode = state->distcode = state->next = state->codes;
1044 if (strm->outcb != Z_NULL)
1045 (*strm->outcb)(Z_NULL, 0);
1046 Tracev((stderr, "inflate: reset\n"));
1050 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1053 const char *version;
1056 struct inflate_state FAR *state;
1058 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1059 stream_size != (int)(sizeof(z_stream)))
1060 return Z_VERSION_ERROR;
1061 if (strm == Z_NULL) return Z_STREAM_ERROR;
1062 strm->msg = Z_NULL; /* in case we return an error */
1063 if (strm->zalloc == (alloc_func)0) {
1064 strm->zalloc = zcalloc;
1065 strm->opaque = (voidpf)0;
1067 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1068 state = (struct inflate_state FAR *)
1069 ZALLOC(strm, 1, sizeof(struct inflate_state));
1070 if (state == Z_NULL) return Z_MEM_ERROR;
1071 Tracev((stderr, "inflate: allocated\n"));
1072 strm->state = (struct internal_state FAR *)state;
1073 if (windowBits < 0) {
1075 windowBits = -windowBits;
1078 state->wrap = (windowBits >> 4) + 1;
1080 if (windowBits < 48) windowBits &= 15;
1083 if (windowBits < 8 || windowBits > 15) {
1085 strm->state = Z_NULL;
1086 return Z_STREAM_ERROR;
1088 state->wbits = (unsigned)windowBits;
1089 state->window = Z_NULL;
1090 return inflateReset(strm);
1093 int ZEXPORT inflateInit_(strm, version, stream_size)
1095 const char *version;
1098 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
1101 local void fixedtables(state)
1102 struct inflate_state FAR *state;
1104 state->lencode = lenfix;
1106 state->distcode = distfix;
1107 state->distbits = 5;
1111 Update the window with the last wsize (normally 32K) bytes written before
1112 returning. If window does not exist yet, create it. This is only called
1113 when a window is already in use, or when output has been written during this
1114 inflate call, but the end of the deflate stream has not been reached yet.
1115 It is also called to create a window for dictionary data when a dictionary
1118 Providing output buffers larger than 32K to inflate() should provide a speed
1119 advantage, since only the last 32K of output is copied to the sliding window
1120 upon return from inflate(), and since all distances after the first 32K of
1121 output will fall in the output data, making match copies simpler and faster.
1122 The advantage may be dependent on the size of the processor's data caches.
1124 local int updatewindow(strm, out)
1128 struct inflate_state FAR *state;
1129 unsigned copy, dist;
1131 state = (struct inflate_state FAR *)strm->state;
1133 /* if it hasn't been done already, allocate space for the window */
1134 if (state->window == Z_NULL) {
1135 state->window = (unsigned char FAR *)
1136 ZALLOC(strm, 1U << state->wbits,
1137 sizeof(unsigned char));
1138 if (state->window == Z_NULL) return 1;
1141 /* if window not in use yet, initialize */
1142 if (state->wsize == 0) {
1143 state->wsize = 1U << state->wbits;
1148 /* copy state->wsize or less output bytes into the circular window */
1149 copy = out - strm->avail_out;
1150 if (copy >= state->wsize) {
1151 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1153 state->whave = state->wsize;
1156 dist = state->wsize - state->write;
1157 if (dist > copy) dist = copy;
1158 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1161 zmemcpy(state->window, strm->next_out - copy, copy);
1162 state->write = copy;
1163 state->whave = state->wsize;
1166 state->write += dist;
1167 if (state->write == state->wsize) state->write = 0;
1168 if (state->whave < state->wsize) state->whave += dist;
1174 /* Macros for inflate(): */
1176 /* check function to use adler32() for zlib or crc32() for gzip */
1177 #define UPDATE(check, buf, len) \
1178 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1180 /* check macros for header crc */
1181 #define CRC2(check, word) \
1183 hbuf[0] = (unsigned char)(word); \
1184 hbuf[1] = (unsigned char)((word) >> 8); \
1185 check = crc32(check, hbuf, 2); \
1188 #define CRC4(check, word) \
1190 hbuf[0] = (unsigned char)(word); \
1191 hbuf[1] = (unsigned char)((word) >> 8); \
1192 hbuf[2] = (unsigned char)((word) >> 16); \
1193 hbuf[3] = (unsigned char)((word) >> 24); \
1194 check = crc32(check, hbuf, 4); \
1197 /* Load registers with state in inflate() for speed */
1200 put = strm->next_out; \
1201 left = strm->avail_out; \
1202 next = strm->next_in; \
1203 have = strm->avail_in; \
1204 hold = state->hold; \
1205 bits = state->bits; \
1208 /* Restore state from registers in inflate() */
1211 strm->next_out = put; \
1212 strm->avail_out = left; \
1213 strm->next_in = next; \
1214 strm->avail_in = have; \
1215 state->hold = hold; \
1216 state->bits = bits; \
1219 /* Clear the input bit accumulator */
1220 #define INITBITS() \
1226 /* Get a byte of input into the bit accumulator, or return from inflate()
1227 if there is no input available. */
1228 #define PULLBYTE() \
1230 if (have == 0) goto inf_leave; \
1232 hold += (unsigned long)(*next++) << bits; \
1236 /* Assure that there are at least n bits in the bit accumulator. If there is
1237 not enough available input to do that, then return from inflate(). */
1238 #define NEEDBITS(n) \
1240 while (bits < (unsigned)(n)) \
1244 /* Return the low n bits of the bit accumulator (n < 16) */
1246 ((unsigned)hold & ((1U << (n)) - 1))
1248 /* Remove n bits from the bit accumulator */
1249 #define DROPBITS(n) \
1252 bits -= (unsigned)(n); \
1255 /* Remove zero to seven bits as needed to go to a byte boundary */
1256 #define BYTEBITS() \
1258 hold >>= bits & 7; \
1262 /* Reverse the bytes in a 32-bit value */
1263 #define REVERSE(q) \
1264 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1265 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1268 inflate() uses a state machine to process as much input data and generate as
1269 much output data as possible before returning. The state machine is
1270 structured roughly as follows:
1272 for (;;) switch (state) {
1275 if (not enough input data or output space to make progress)
1277 ... make progress ...
1283 so when inflate() is called again, the same case is attempted again, and
1284 if the appropriate resources are provided, the machine proceeds to the
1285 next state. The NEEDBITS() macro is usually the way the state evaluates
1286 whether it can proceed or should return. NEEDBITS() does the return if
1287 the requested bits are not available. The typical use of the BITS macros
1291 ... do something with BITS(n) ...
1294 where NEEDBITS(n) either returns from inflate() if there isn't enough
1295 input left to load n bits into the accumulator, or it continues. BITS(n)
1296 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1297 the low n bits off the accumulator. INITBITS() clears the accumulator
1298 and sets the number of available bits to zero. BYTEBITS() discards just
1299 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1300 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1302 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1303 if there is no input available. The decoding of variable length codes uses
1304 PULLBYTE() directly in order to pull just enough bytes to decode the next
1307 Some states loop until they get enough input, making sure that enough
1308 state information is maintained to continue the loop where it left off
1309 if NEEDBITS() returns in the loop. For example, want, need, and keep
1310 would all have to actually be part of the saved state in case NEEDBITS()
1314 while (want < need) {
1316 keep[want++] = BITS(n);
1322 As shown above, if the next state is also the next case, then the break
1325 A state may also return if there is not enough output space available to
1326 complete that state. Those states are copying stored data, writing a
1327 literal byte, and copying a matching string.
1329 When returning, a "goto inf_leave" is used to update the total counters,
1330 update the check value, and determine whether any progress has been made
1331 during that inflate() call in order to return the proper return code.
1332 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1333 When there is a window, goto inf_leave will update the window with the last
1334 output written. If a goto inf_leave occurs in the middle of decompression
1335 and there is no window currently, goto inf_leave will create one and copy
1336 output to the window for the next call of inflate().
1338 In this implementation, the flush parameter of inflate() only affects the
1339 return code (per zlib.h). inflate() always writes as much as possible to
1340 strm->next_out, given the space available and the provided input--the effect
1341 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1342 the allocation of and copying into a sliding window until necessary, which
1343 provides the effect documented in zlib.h for Z_FINISH when the entire input
1344 stream available. So the only thing the flush parameter actually does is:
1345 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1346 will return Z_BUF_ERROR if it has not reached the end of the stream.
1348 int ZEXPORT inflate(strm, flush)
1352 struct inflate_state FAR *state;
1353 unsigned char FAR *next; /* next input */
1354 unsigned char FAR *put; /* next output */
1355 unsigned have, left; /* available input and output */
1356 unsigned long hold; /* bit buffer */
1357 unsigned bits; /* bits in bit buffer */
1358 unsigned in, out; /* save starting available input and output */
1359 unsigned copy; /* number of stored or match bytes to copy */
1360 unsigned char FAR *from; /* where to copy match bytes from */
1361 code this; /* current decoding table entry */
1362 code last; /* parent table entry */
1363 unsigned len; /* length to copy for repeats, bits to drop */
1364 int ret; /* return code */
1366 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1368 static const unsigned short order[19] = /* permutation of code lengths */
1369 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1371 if (strm == Z_NULL || strm->state == Z_NULL ||
1372 (strm->next_in == Z_NULL && strm->avail_in != 0))
1373 return Z_STREAM_ERROR;
1375 state = (struct inflate_state FAR *)strm->state;
1376 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1382 switch (state->mode) {
1384 if (state->wrap == 0) {
1385 state->mode = TYPEDO;
1390 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1391 state->check = crc32(0L, Z_NULL, 0);
1392 CRC2(state->check, hold);
1394 state->mode = FLAGS;
1397 state->flags = 0; /* expect zlib header */
1398 if (state->head != Z_NULL)
1399 state->head->done = -1;
1400 if (!(state->wrap & 1) || /* check if zlib header allowed */
1404 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1405 strm->msg = (char *)"incorrect header check";
1409 if (BITS(4) != Z_DEFLATED) {
1410 strm->msg = (char *)"unknown compression method";
1416 if (len > state->wbits) {
1417 strm->msg = (char *)"invalid window size";
1421 state->dmax = 1U << len;
1422 Tracev((stderr, "inflate: zlib header ok\n"));
1423 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1424 state->mode = hold & 0x200 ? DICTID : TYPE;
1430 state->flags = (int)(hold);
1431 if ((state->flags & 0xff) != Z_DEFLATED) {
1432 strm->msg = (char *)"unknown compression method";
1436 if (state->flags & 0xe000) {
1437 strm->msg = (char *)"unknown header flags set";
1441 if (state->head != Z_NULL)
1442 state->head->text = (int)((hold >> 8) & 1);
1443 if (state->flags & 0x0200) CRC2(state->check, hold);
1448 if (state->head != Z_NULL)
1449 state->head->time = hold;
1450 if (state->flags & 0x0200) CRC4(state->check, hold);
1455 if (state->head != Z_NULL) {
1456 state->head->xflags = (int)(hold & 0xff);
1457 state->head->os = (int)(hold >> 8);
1459 if (state->flags & 0x0200) CRC2(state->check, hold);
1461 state->mode = EXLEN;
1463 if (state->flags & 0x0400) {
1465 state->length = (unsigned)(hold);
1466 if (state->head != Z_NULL)
1467 state->head->extra_len = (unsigned)hold;
1468 if (state->flags & 0x0200) CRC2(state->check, hold);
1471 else if (state->head != Z_NULL)
1472 state->head->extra = Z_NULL;
1473 state->mode = EXTRA;
1475 if (state->flags & 0x0400) {
1476 copy = state->length;
1477 if (copy > have) copy = have;
1479 if (state->head != Z_NULL &&
1480 state->head->extra != Z_NULL) {
1481 len = state->head->extra_len - state->length;
1482 zmemcpy(state->head->extra + len, next,
1483 len + copy > state->head->extra_max ?
1484 state->head->extra_max - len : copy);
1486 if (state->flags & 0x0200)
1487 state->check = crc32(state->check, next, copy);
1490 state->length -= copy;
1492 if (state->length) goto inf_leave;
1497 if (state->flags & 0x0800) {
1498 if (have == 0) goto inf_leave;
1501 len = (unsigned)(next[copy++]);
1502 if (state->head != Z_NULL &&
1503 state->head->name != Z_NULL &&
1504 state->length < state->head->name_max)
1505 state->head->name[state->length++] = len;
1506 } while (len && copy < have);
1507 if (state->flags & 0x0200)
1508 state->check = crc32(state->check, next, copy);
1511 if (len) goto inf_leave;
1513 else if (state->head != Z_NULL)
1514 state->head->name = Z_NULL;
1516 state->mode = COMMENT;
1518 if (state->flags & 0x1000) {
1519 if (have == 0) goto inf_leave;
1522 len = (unsigned)(next[copy++]);
1523 if (state->head != Z_NULL &&
1524 state->head->comment != Z_NULL &&
1525 state->length < state->head->comm_max)
1526 state->head->comment[state->length++] = len;
1527 } while (len && copy < have);
1528 if (state->flags & 0x0200)
1529 state->check = crc32(state->check, next, copy);
1532 if (len) goto inf_leave;
1534 else if (state->head != Z_NULL)
1535 state->head->comment = Z_NULL;
1538 if (state->flags & 0x0200) {
1540 if (hold != (state->check & 0xffff)) {
1541 strm->msg = (char *)"header crc mismatch";
1547 if (state->head != Z_NULL) {
1548 state->head->hcrc = (int)((state->flags >> 9) & 1);
1549 state->head->done = 1;
1551 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1557 strm->adler = state->check = REVERSE(hold);
1561 if (state->havedict == 0) {
1565 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1568 if (flush == Z_BLOCK) goto inf_leave;
1572 state->mode = CHECK;
1576 state->last = BITS(1);
1579 case 0: /* stored block */
1580 Tracev((stderr, "inflate: stored block%s\n",
1581 state->last ? " (last)" : ""));
1582 state->mode = STORED;
1584 case 1: /* fixed block */
1586 Tracev((stderr, "inflate: fixed codes block%s\n",
1587 state->last ? " (last)" : ""));
1588 state->mode = LEN; /* decode codes */
1590 case 2: /* dynamic block */
1591 Tracev((stderr, "inflate: dynamic codes block%s\n",
1592 state->last ? " (last)" : ""));
1593 state->mode = TABLE;
1596 strm->msg = (char *)"invalid block type";
1602 BYTEBITS(); /* go to byte boundary */
1604 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1605 strm->msg = (char *)"invalid stored block lengths";
1609 state->length = (unsigned)hold & 0xffff;
1610 Tracev((stderr, "inflate: stored length %u\n",
1615 copy = state->length;
1617 if (copy > have) copy = have;
1618 if (copy > left) copy = left;
1619 if (copy == 0) goto inf_leave;
1620 zmemcpy(put, next, copy);
1625 state->length -= copy;
1628 Tracev((stderr, "inflate: stored end\n"));
1633 state->nlen = BITS(5) + 257;
1635 state->ndist = BITS(5) + 1;
1637 state->ncode = BITS(4) + 4;
1639 #ifndef PKZIP_BUG_WORKAROUND
1640 if (state->nlen > 286 || state->ndist > 30) {
1641 strm->msg = (char *)"too many length or distance symbols";
1646 Tracev((stderr, "inflate: table sizes ok\n"));
1648 state->mode = LENLENS;
1650 while (state->have < state->ncode) {
1652 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1655 while (state->have < 19)
1656 state->lens[order[state->have++]] = 0;
1657 state->next = state->codes;
1658 state->lencode = (code const FAR *)(state->next);
1660 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1661 &(state->lenbits), state->work);
1663 strm->msg = (char *)"invalid code lengths set";
1667 Tracev((stderr, "inflate: code lengths ok\n"));
1669 state->mode = CODELENS;
1671 while (state->have < state->nlen + state->ndist) {
1673 this = state->lencode[BITS(state->lenbits)];
1674 if ((unsigned)(this.bits) <= bits) break;
1677 if (this.val < 16) {
1678 NEEDBITS(this.bits);
1679 DROPBITS(this.bits);
1680 state->lens[state->have++] = this.val;
1683 if (this.val == 16) {
1684 NEEDBITS(this.bits + 2);
1685 DROPBITS(this.bits);
1686 if (state->have == 0) {
1687 strm->msg = (char *)"invalid bit length repeat";
1691 len = state->lens[state->have - 1];
1695 else if (this.val == 17) {
1696 NEEDBITS(this.bits + 3);
1697 DROPBITS(this.bits);
1703 NEEDBITS(this.bits + 7);
1704 DROPBITS(this.bits);
1706 copy = 11 + BITS(7);
1709 if (state->have + copy > state->nlen + state->ndist) {
1710 strm->msg = (char *)"invalid bit length repeat";
1715 state->lens[state->have++] = (unsigned short)len;
1719 /* handle error breaks in while */
1720 if (state->mode == BAD) break;
1722 /* build code tables */
1723 state->next = state->codes;
1724 state->lencode = (code const FAR *)(state->next);
1726 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1727 &(state->lenbits), state->work);
1729 strm->msg = (char *)"invalid literal/lengths set";
1733 state->distcode = (code const FAR *)(state->next);
1734 state->distbits = 6;
1735 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1736 &(state->next), &(state->distbits), state->work);
1738 strm->msg = (char *)"invalid distances set";
1742 Tracev((stderr, "inflate: codes ok\n"));
1745 if (strm->outcb != Z_NULL) /* for watchdog (U-Boot) */
1746 (*strm->outcb)(Z_NULL, 0);
1747 if (have >= 6 && left >= 258) {
1749 inflate_fast(strm, out);
1754 this = state->lencode[BITS(state->lenbits)];
1755 if ((unsigned)(this.bits) <= bits) break;
1758 if (this.op && (this.op & 0xf0) == 0) {
1761 this = state->lencode[last.val +
1762 (BITS(last.bits + last.op) >> last.bits)];
1763 if ((unsigned)(last.bits + this.bits) <= bits) break;
1766 DROPBITS(last.bits);
1768 DROPBITS(this.bits);
1769 state->length = (unsigned)this.val;
1770 if ((int)(this.op) == 0) {
1771 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1772 "inflate: literal '%c'\n" :
1773 "inflate: literal 0x%02x\n", this.val));
1778 Tracevv((stderr, "inflate: end of block\n"));
1783 strm->msg = (char *)"invalid literal/length code";
1787 state->extra = (unsigned)(this.op) & 15;
1788 state->mode = LENEXT;
1791 NEEDBITS(state->extra);
1792 state->length += BITS(state->extra);
1793 DROPBITS(state->extra);
1795 Tracevv((stderr, "inflate: length %u\n", state->length));
1799 this = state->distcode[BITS(state->distbits)];
1800 if ((unsigned)(this.bits) <= bits) break;
1803 if ((this.op & 0xf0) == 0) {
1806 this = state->distcode[last.val +
1807 (BITS(last.bits + last.op) >> last.bits)];
1808 if ((unsigned)(last.bits + this.bits) <= bits) break;
1811 DROPBITS(last.bits);
1813 DROPBITS(this.bits);
1815 strm->msg = (char *)"invalid distance code";
1819 state->offset = (unsigned)this.val;
1820 state->extra = (unsigned)(this.op) & 15;
1821 state->mode = DISTEXT;
1824 NEEDBITS(state->extra);
1825 state->offset += BITS(state->extra);
1826 DROPBITS(state->extra);
1828 #ifdef INFLATE_STRICT
1829 if (state->offset > state->dmax) {
1830 strm->msg = (char *)"invalid distance too far back";
1835 if (state->offset > state->whave + out - left) {
1836 strm->msg = (char *)"invalid distance too far back";
1840 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1841 state->mode = MATCH;
1843 if (left == 0) goto inf_leave;
1845 if (state->offset > copy) { /* copy from window */
1846 copy = state->offset - copy;
1847 if (copy > state->write) {
1848 copy -= state->write;
1849 from = state->window + (state->wsize - copy);
1852 from = state->window + (state->write - copy);
1853 if (copy > state->length) copy = state->length;
1855 else { /* copy from output */
1856 from = put - state->offset;
1857 copy = state->length;
1859 if (copy > left) copy = left;
1861 state->length -= copy;
1865 if (state->length == 0) state->mode = LEN;
1868 if (left == 0) goto inf_leave;
1869 *put++ = (unsigned char)(state->length);
1877 strm->total_out += out;
1878 state->total += out;
1880 strm->adler = state->check =
1881 UPDATE(state->check, put - out, out);
1885 state->flags ? hold :
1887 REVERSE(hold)) != state->check) {
1888 strm->msg = (char *)"incorrect data check";
1893 Tracev((stderr, "inflate: check matches trailer\n"));
1896 state->mode = LENGTH;
1898 if (state->wrap && state->flags) {
1900 if (hold != (state->total & 0xffffffffUL)) {
1901 strm->msg = (char *)"incorrect length check";
1906 Tracev((stderr, "inflate: length matches trailer\n"));
1920 return Z_STREAM_ERROR;
1924 Return from inflate(), updating the total counts and the check value.
1925 If there was no progress during the inflate() call, return a buffer
1926 error. Call updatewindow() to create and/or update the window state.
1927 Note: a memory error from inflate() is non-recoverable.
1931 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1932 if (updatewindow(strm, out)) {
1936 in -= strm->avail_in;
1937 out -= strm->avail_out;
1938 strm->total_in += in;
1939 strm->total_out += out;
1940 state->total += out;
1941 if (state->wrap && out)
1942 strm->adler = state->check =
1943 UPDATE(state->check, strm->next_out - out, out);
1944 strm->data_type = state->bits + (state->last ? 64 : 0) +
1945 (state->mode == TYPE ? 128 : 0);
1946 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1951 int ZEXPORT inflateEnd(strm)
1954 struct inflate_state FAR *state;
1955 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1956 return Z_STREAM_ERROR;
1957 state = (struct inflate_state FAR *)strm->state;
1958 if (state->window != Z_NULL) {
1959 if (strm->outcb != Z_NULL)
1960 (*strm->outcb)(Z_NULL, 0);
1961 ZFREE(strm, state->window);
1963 ZFREE(strm, strm->state);
1964 strm->state = Z_NULL;
1965 Tracev((stderr, "inflate: end\n"));
1970 /* zutil.c -- target dependent utility functions for the compression library
1971 * Copyright (C) 1995-2005 Jean-loup Gailly.
1972 * For conditions of distribution and use, see copyright notice in zlib.h
1977 #ifndef NO_DUMMY_DECL
1978 struct internal_state {int dummy;}; /* for buggy compilers */
1981 const char * const z_errmsg[10] = {
1982 "need dictionary", /* Z_NEED_DICT 2 */
1983 "stream end", /* Z_STREAM_END 1 */
1985 "file error", /* Z_ERRNO (-1) */
1986 "stream error", /* Z_STREAM_ERROR (-2) */
1987 "data error", /* Z_DATA_ERROR (-3) */
1988 "insufficient memory", /* Z_MEM_ERROR (-4) */
1989 "buffer error", /* Z_BUF_ERROR (-5) */
1990 "incompatible version",/* Z_VERSION_ERROR (-6) */
1998 int z_verbose = verbose;
2003 fprintf(stderr, "%s\n", m);
2008 /* exported to allow conversion of error code to string for compress() and
2011 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
2014 extern voidp malloc OF((uInt size));
2015 extern voidp calloc OF((uInt items, uInt size));
2016 extern void free OF((voidpf ptr));
2019 voidpf zcalloc (opaque, items, size)
2025 items += size - size; /* make compiler happy */
2026 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2027 (voidpf)calloc(items, size);
2030 void zcfree (opaque, ptr, nb)
2037 return; /* make compiler happy */
2040 #endif /* MY_ZCALLOC */
2042 /* adler32.c -- compute the Adler-32 checksum of a data stream
2043 * Copyright (C) 1995-2004 Mark Adler
2044 * For conditions of distribution and use, see copyright notice in zlib.h
2049 #define BASE 65521UL /* largest prime smaller than 65536 */
2051 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2053 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2054 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2055 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2056 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2057 #define DO16(buf) DO8(buf,0); DO8(buf,8);
2059 /* use NO_DIVIDE if your processor does not do division in hardware */
2063 if (a >= (BASE << 16)) \
2064 a -= (BASE << 16); \
2065 if (a >= (BASE << 15)) \
2066 a -= (BASE << 15); \
2067 if (a >= (BASE << 14)) \
2068 a -= (BASE << 14); \
2069 if (a >= (BASE << 13)) \
2070 a -= (BASE << 13); \
2071 if (a >= (BASE << 12)) \
2072 a -= (BASE << 12); \
2073 if (a >= (BASE << 11)) \
2074 a -= (BASE << 11); \
2075 if (a >= (BASE << 10)) \
2076 a -= (BASE << 10); \
2077 if (a >= (BASE << 9)) \
2079 if (a >= (BASE << 8)) \
2081 if (a >= (BASE << 7)) \
2083 if (a >= (BASE << 6)) \
2085 if (a >= (BASE << 5)) \
2087 if (a >= (BASE << 4)) \
2089 if (a >= (BASE << 3)) \
2091 if (a >= (BASE << 2)) \
2093 if (a >= (BASE << 1)) \
2100 if (a >= (BASE << 4)) \
2102 if (a >= (BASE << 3)) \
2104 if (a >= (BASE << 2)) \
2106 if (a >= (BASE << 1)) \
2112 #define MOD(a) a %= BASE
2113 #define MOD4(a) a %= BASE
2116 /* ========================================================================= */
2117 uLong ZEXPORT adler32(adler, buf, len)
2125 /* split Adler-32 into component sums */
2126 sum2 = (adler >> 16) & 0xffff;
2129 /* in case user likes doing a byte at a time, keep it fast */
2137 return adler | (sum2 << 16);
2140 /* initial Adler-32 value (deferred check for len == 1 speed) */
2144 /* in case short lengths are provided, keep it somewhat fast */
2152 MOD4(sum2); /* only added so many BASE's */
2153 return adler | (sum2 << 16);
2156 /* do length NMAX blocks -- requires just one modulo operation */
2157 while (len >= NMAX) {
2159 n = NMAX / 16; /* NMAX is divisible by 16 */
2161 DO16(buf); /* 16 sums unrolled */
2168 /* do remaining bytes (less than NMAX, still just one modulo) */
2169 if (len) { /* avoid modulos if none remaining */
2183 /* return recombined sums */
2184 return adler | (sum2 << 16);