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 if (strm->outcb != Z_NULL)
1044 (*strm->outcb)(Z_NULL, 0);
1045 Tracev((stderr, "inflate: reset\n"));
1049 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1052 const char *version;
1055 struct inflate_state FAR *state;
1057 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1058 stream_size != (int)(sizeof(z_stream)))
1059 return Z_VERSION_ERROR;
1060 if (strm == Z_NULL) return Z_STREAM_ERROR;
1061 strm->msg = Z_NULL; /* in case we return an error */
1062 if (strm->zalloc == (alloc_func)0) {
1063 strm->zalloc = zcalloc;
1064 strm->opaque = (voidpf)0;
1066 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1067 state = (struct inflate_state FAR *)
1068 ZALLOC(strm, 1, sizeof(struct inflate_state));
1069 if (state == Z_NULL) return Z_MEM_ERROR;
1070 Tracev((stderr, "inflate: allocated\n"));
1071 strm->state = (struct internal_state FAR *)state;
1072 if (windowBits < 0) {
1074 windowBits = -windowBits;
1077 state->wrap = (windowBits >> 4) + 1;
1079 if (windowBits < 48) windowBits &= 15;
1082 if (windowBits < 8 || windowBits > 15) {
1084 strm->state = Z_NULL;
1085 return Z_STREAM_ERROR;
1087 state->wbits = (unsigned)windowBits;
1088 state->window = Z_NULL;
1089 return inflateReset(strm);
1092 int ZEXPORT inflateInit_(strm, version, stream_size)
1094 const char *version;
1097 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
1100 local void fixedtables(state)
1101 struct inflate_state FAR *state;
1103 state->lencode = lenfix;
1105 state->distcode = distfix;
1106 state->distbits = 5;
1110 Update the window with the last wsize (normally 32K) bytes written before
1111 returning. If window does not exist yet, create it. This is only called
1112 when a window is already in use, or when output has been written during this
1113 inflate call, but the end of the deflate stream has not been reached yet.
1114 It is also called to create a window for dictionary data when a dictionary
1117 Providing output buffers larger than 32K to inflate() should provide a speed
1118 advantage, since only the last 32K of output is copied to the sliding window
1119 upon return from inflate(), and since all distances after the first 32K of
1120 output will fall in the output data, making match copies simpler and faster.
1121 The advantage may be dependent on the size of the processor's data caches.
1123 local int updatewindow(strm, out)
1127 struct inflate_state FAR *state;
1128 unsigned copy, dist;
1130 state = (struct inflate_state FAR *)strm->state;
1132 /* if it hasn't been done already, allocate space for the window */
1133 if (state->window == Z_NULL) {
1134 state->window = (unsigned char FAR *)
1135 ZALLOC(strm, 1U << state->wbits,
1136 sizeof(unsigned char));
1137 if (state->window == Z_NULL) return 1;
1140 /* if window not in use yet, initialize */
1141 if (state->wsize == 0) {
1142 state->wsize = 1U << state->wbits;
1147 /* copy state->wsize or less output bytes into the circular window */
1148 copy = out - strm->avail_out;
1149 if (copy >= state->wsize) {
1150 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1152 state->whave = state->wsize;
1155 dist = state->wsize - state->write;
1156 if (dist > copy) dist = copy;
1157 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1160 zmemcpy(state->window, strm->next_out - copy, copy);
1161 state->write = copy;
1162 state->whave = state->wsize;
1165 state->write += dist;
1166 if (state->write == state->wsize) state->write = 0;
1167 if (state->whave < state->wsize) state->whave += dist;
1173 /* Macros for inflate(): */
1175 /* check function to use adler32() for zlib or crc32() for gzip */
1176 #define UPDATE(check, buf, len) \
1177 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1179 /* check macros for header crc */
1180 #define CRC2(check, word) \
1182 hbuf[0] = (unsigned char)(word); \
1183 hbuf[1] = (unsigned char)((word) >> 8); \
1184 check = crc32(check, hbuf, 2); \
1187 #define CRC4(check, word) \
1189 hbuf[0] = (unsigned char)(word); \
1190 hbuf[1] = (unsigned char)((word) >> 8); \
1191 hbuf[2] = (unsigned char)((word) >> 16); \
1192 hbuf[3] = (unsigned char)((word) >> 24); \
1193 check = crc32(check, hbuf, 4); \
1196 /* Load registers with state in inflate() for speed */
1199 put = strm->next_out; \
1200 left = strm->avail_out; \
1201 next = strm->next_in; \
1202 have = strm->avail_in; \
1203 hold = state->hold; \
1204 bits = state->bits; \
1207 /* Restore state from registers in inflate() */
1210 strm->next_out = put; \
1211 strm->avail_out = left; \
1212 strm->next_in = next; \
1213 strm->avail_in = have; \
1214 state->hold = hold; \
1215 state->bits = bits; \
1218 /* Clear the input bit accumulator */
1219 #define INITBITS() \
1225 /* Get a byte of input into the bit accumulator, or return from inflate()
1226 if there is no input available. */
1227 #define PULLBYTE() \
1229 if (have == 0) goto inf_leave; \
1231 hold += (unsigned long)(*next++) << bits; \
1235 /* Assure that there are at least n bits in the bit accumulator. If there is
1236 not enough available input to do that, then return from inflate(). */
1237 #define NEEDBITS(n) \
1239 while (bits < (unsigned)(n)) \
1243 /* Return the low n bits of the bit accumulator (n < 16) */
1245 ((unsigned)hold & ((1U << (n)) - 1))
1247 /* Remove n bits from the bit accumulator */
1248 #define DROPBITS(n) \
1251 bits -= (unsigned)(n); \
1254 /* Remove zero to seven bits as needed to go to a byte boundary */
1255 #define BYTEBITS() \
1257 hold >>= bits & 7; \
1261 /* Reverse the bytes in a 32-bit value */
1262 #define REVERSE(q) \
1263 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1264 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1267 inflate() uses a state machine to process as much input data and generate as
1268 much output data as possible before returning. The state machine is
1269 structured roughly as follows:
1271 for (;;) switch (state) {
1274 if (not enough input data or output space to make progress)
1276 ... make progress ...
1282 so when inflate() is called again, the same case is attempted again, and
1283 if the appropriate resources are provided, the machine proceeds to the
1284 next state. The NEEDBITS() macro is usually the way the state evaluates
1285 whether it can proceed or should return. NEEDBITS() does the return if
1286 the requested bits are not available. The typical use of the BITS macros
1290 ... do something with BITS(n) ...
1293 where NEEDBITS(n) either returns from inflate() if there isn't enough
1294 input left to load n bits into the accumulator, or it continues. BITS(n)
1295 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1296 the low n bits off the accumulator. INITBITS() clears the accumulator
1297 and sets the number of available bits to zero. BYTEBITS() discards just
1298 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1299 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1301 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1302 if there is no input available. The decoding of variable length codes uses
1303 PULLBYTE() directly in order to pull just enough bytes to decode the next
1306 Some states loop until they get enough input, making sure that enough
1307 state information is maintained to continue the loop where it left off
1308 if NEEDBITS() returns in the loop. For example, want, need, and keep
1309 would all have to actually be part of the saved state in case NEEDBITS()
1313 while (want < need) {
1315 keep[want++] = BITS(n);
1321 As shown above, if the next state is also the next case, then the break
1324 A state may also return if there is not enough output space available to
1325 complete that state. Those states are copying stored data, writing a
1326 literal byte, and copying a matching string.
1328 When returning, a "goto inf_leave" is used to update the total counters,
1329 update the check value, and determine whether any progress has been made
1330 during that inflate() call in order to return the proper return code.
1331 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1332 When there is a window, goto inf_leave will update the window with the last
1333 output written. If a goto inf_leave occurs in the middle of decompression
1334 and there is no window currently, goto inf_leave will create one and copy
1335 output to the window for the next call of inflate().
1337 In this implementation, the flush parameter of inflate() only affects the
1338 return code (per zlib.h). inflate() always writes as much as possible to
1339 strm->next_out, given the space available and the provided input--the effect
1340 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1341 the allocation of and copying into a sliding window until necessary, which
1342 provides the effect documented in zlib.h for Z_FINISH when the entire input
1343 stream available. So the only thing the flush parameter actually does is:
1344 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1345 will return Z_BUF_ERROR if it has not reached the end of the stream.
1347 int ZEXPORT inflate(strm, flush)
1351 struct inflate_state FAR *state;
1352 unsigned char FAR *next; /* next input */
1353 unsigned char FAR *put; /* next output */
1354 unsigned have, left; /* available input and output */
1355 unsigned long hold; /* bit buffer */
1356 unsigned bits; /* bits in bit buffer */
1357 unsigned in, out; /* save starting available input and output */
1358 unsigned copy; /* number of stored or match bytes to copy */
1359 unsigned char FAR *from; /* where to copy match bytes from */
1360 code this; /* current decoding table entry */
1361 code last; /* parent table entry */
1362 unsigned len; /* length to copy for repeats, bits to drop */
1363 int ret; /* return code */
1365 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1367 static const unsigned short order[19] = /* permutation of code lengths */
1368 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1370 if (strm == Z_NULL || strm->state == Z_NULL ||
1371 (strm->next_in == Z_NULL && strm->avail_in != 0))
1372 return Z_STREAM_ERROR;
1374 state = (struct inflate_state FAR *)strm->state;
1375 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1381 switch (state->mode) {
1383 if (state->wrap == 0) {
1384 state->mode = TYPEDO;
1389 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1390 state->check = crc32(0L, Z_NULL, 0);
1391 CRC2(state->check, hold);
1393 state->mode = FLAGS;
1396 state->flags = 0; /* expect zlib header */
1397 if (state->head != Z_NULL)
1398 state->head->done = -1;
1399 if (!(state->wrap & 1) || /* check if zlib header allowed */
1403 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1404 strm->msg = (char *)"incorrect header check";
1408 if (BITS(4) != Z_DEFLATED) {
1409 strm->msg = (char *)"unknown compression method";
1415 if (len > state->wbits) {
1416 strm->msg = (char *)"invalid window size";
1420 state->dmax = 1U << len;
1421 Tracev((stderr, "inflate: zlib header ok\n"));
1422 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1423 state->mode = hold & 0x200 ? DICTID : TYPE;
1429 state->flags = (int)(hold);
1430 if ((state->flags & 0xff) != Z_DEFLATED) {
1431 strm->msg = (char *)"unknown compression method";
1435 if (state->flags & 0xe000) {
1436 strm->msg = (char *)"unknown header flags set";
1440 if (state->head != Z_NULL)
1441 state->head->text = (int)((hold >> 8) & 1);
1442 if (state->flags & 0x0200) CRC2(state->check, hold);
1447 if (state->head != Z_NULL)
1448 state->head->time = hold;
1449 if (state->flags & 0x0200) CRC4(state->check, hold);
1454 if (state->head != Z_NULL) {
1455 state->head->xflags = (int)(hold & 0xff);
1456 state->head->os = (int)(hold >> 8);
1458 if (state->flags & 0x0200) CRC2(state->check, hold);
1460 state->mode = EXLEN;
1462 if (state->flags & 0x0400) {
1464 state->length = (unsigned)(hold);
1465 if (state->head != Z_NULL)
1466 state->head->extra_len = (unsigned)hold;
1467 if (state->flags & 0x0200) CRC2(state->check, hold);
1470 else if (state->head != Z_NULL)
1471 state->head->extra = Z_NULL;
1472 state->mode = EXTRA;
1474 if (state->flags & 0x0400) {
1475 copy = state->length;
1476 if (copy > have) copy = have;
1478 if (state->head != Z_NULL &&
1479 state->head->extra != Z_NULL) {
1480 len = state->head->extra_len - state->length;
1481 zmemcpy(state->head->extra + len, next,
1482 len + copy > state->head->extra_max ?
1483 state->head->extra_max - len : copy);
1485 if (state->flags & 0x0200)
1486 state->check = crc32(state->check, next, copy);
1489 state->length -= copy;
1491 if (state->length) goto inf_leave;
1496 if (state->flags & 0x0800) {
1497 if (have == 0) goto inf_leave;
1500 len = (unsigned)(next[copy++]);
1501 if (state->head != Z_NULL &&
1502 state->head->name != Z_NULL &&
1503 state->length < state->head->name_max)
1504 state->head->name[state->length++] = len;
1505 } while (len && copy < have);
1506 if (state->flags & 0x0200)
1507 state->check = crc32(state->check, next, copy);
1510 if (len) goto inf_leave;
1512 else if (state->head != Z_NULL)
1513 state->head->name = Z_NULL;
1515 state->mode = COMMENT;
1517 if (state->flags & 0x1000) {
1518 if (have == 0) goto inf_leave;
1521 len = (unsigned)(next[copy++]);
1522 if (state->head != Z_NULL &&
1523 state->head->comment != Z_NULL &&
1524 state->length < state->head->comm_max)
1525 state->head->comment[state->length++] = len;
1526 } while (len && copy < have);
1527 if (state->flags & 0x0200)
1528 state->check = crc32(state->check, next, copy);
1531 if (len) goto inf_leave;
1533 else if (state->head != Z_NULL)
1534 state->head->comment = Z_NULL;
1537 if (state->flags & 0x0200) {
1539 if (hold != (state->check & 0xffff)) {
1540 strm->msg = (char *)"header crc mismatch";
1546 if (state->head != Z_NULL) {
1547 state->head->hcrc = (int)((state->flags >> 9) & 1);
1548 state->head->done = 1;
1550 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1556 strm->adler = state->check = REVERSE(hold);
1560 if (state->havedict == 0) {
1564 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1567 if (flush == Z_BLOCK) goto inf_leave;
1571 state->mode = CHECK;
1575 state->last = BITS(1);
1578 case 0: /* stored block */
1579 Tracev((stderr, "inflate: stored block%s\n",
1580 state->last ? " (last)" : ""));
1581 state->mode = STORED;
1583 case 1: /* fixed block */
1585 Tracev((stderr, "inflate: fixed codes block%s\n",
1586 state->last ? " (last)" : ""));
1587 state->mode = LEN; /* decode codes */
1589 case 2: /* dynamic block */
1590 Tracev((stderr, "inflate: dynamic codes block%s\n",
1591 state->last ? " (last)" : ""));
1592 state->mode = TABLE;
1595 strm->msg = (char *)"invalid block type";
1601 BYTEBITS(); /* go to byte boundary */
1603 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1604 strm->msg = (char *)"invalid stored block lengths";
1608 state->length = (unsigned)hold & 0xffff;
1609 Tracev((stderr, "inflate: stored length %u\n",
1614 copy = state->length;
1616 if (copy > have) copy = have;
1617 if (copy > left) copy = left;
1618 if (copy == 0) goto inf_leave;
1619 zmemcpy(put, next, copy);
1624 state->length -= copy;
1627 Tracev((stderr, "inflate: stored end\n"));
1632 state->nlen = BITS(5) + 257;
1634 state->ndist = BITS(5) + 1;
1636 state->ncode = BITS(4) + 4;
1638 #ifndef PKZIP_BUG_WORKAROUND
1639 if (state->nlen > 286 || state->ndist > 30) {
1640 strm->msg = (char *)"too many length or distance symbols";
1645 Tracev((stderr, "inflate: table sizes ok\n"));
1647 state->mode = LENLENS;
1649 while (state->have < state->ncode) {
1651 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1654 while (state->have < 19)
1655 state->lens[order[state->have++]] = 0;
1656 state->next = state->codes;
1657 state->lencode = (code const FAR *)(state->next);
1659 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1660 &(state->lenbits), state->work);
1662 strm->msg = (char *)"invalid code lengths set";
1666 Tracev((stderr, "inflate: code lengths ok\n"));
1668 state->mode = CODELENS;
1670 while (state->have < state->nlen + state->ndist) {
1672 this = state->lencode[BITS(state->lenbits)];
1673 if ((unsigned)(this.bits) <= bits) break;
1676 if (this.val < 16) {
1677 NEEDBITS(this.bits);
1678 DROPBITS(this.bits);
1679 state->lens[state->have++] = this.val;
1682 if (this.val == 16) {
1683 NEEDBITS(this.bits + 2);
1684 DROPBITS(this.bits);
1685 if (state->have == 0) {
1686 strm->msg = (char *)"invalid bit length repeat";
1690 len = state->lens[state->have - 1];
1694 else if (this.val == 17) {
1695 NEEDBITS(this.bits + 3);
1696 DROPBITS(this.bits);
1702 NEEDBITS(this.bits + 7);
1703 DROPBITS(this.bits);
1705 copy = 11 + BITS(7);
1708 if (state->have + copy > state->nlen + state->ndist) {
1709 strm->msg = (char *)"invalid bit length repeat";
1714 state->lens[state->have++] = (unsigned short)len;
1718 /* handle error breaks in while */
1719 if (state->mode == BAD) break;
1721 /* build code tables */
1722 state->next = state->codes;
1723 state->lencode = (code const FAR *)(state->next);
1725 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1726 &(state->lenbits), state->work);
1728 strm->msg = (char *)"invalid literal/lengths set";
1732 state->distcode = (code const FAR *)(state->next);
1733 state->distbits = 6;
1734 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1735 &(state->next), &(state->distbits), state->work);
1737 strm->msg = (char *)"invalid distances set";
1741 Tracev((stderr, "inflate: codes ok\n"));
1744 if (strm->outcb != Z_NULL) /* for watchdog (U-Boot) */
1745 (*strm->outcb)(Z_NULL, 0);
1746 if (have >= 6 && left >= 258) {
1748 inflate_fast(strm, out);
1753 this = state->lencode[BITS(state->lenbits)];
1754 if ((unsigned)(this.bits) <= bits) break;
1757 if (this.op && (this.op & 0xf0) == 0) {
1760 this = state->lencode[last.val +
1761 (BITS(last.bits + last.op) >> last.bits)];
1762 if ((unsigned)(last.bits + this.bits) <= bits) break;
1765 DROPBITS(last.bits);
1767 DROPBITS(this.bits);
1768 state->length = (unsigned)this.val;
1769 if ((int)(this.op) == 0) {
1770 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1771 "inflate: literal '%c'\n" :
1772 "inflate: literal 0x%02x\n", this.val));
1777 Tracevv((stderr, "inflate: end of block\n"));
1782 strm->msg = (char *)"invalid literal/length code";
1786 state->extra = (unsigned)(this.op) & 15;
1787 state->mode = LENEXT;
1790 NEEDBITS(state->extra);
1791 state->length += BITS(state->extra);
1792 DROPBITS(state->extra);
1794 Tracevv((stderr, "inflate: length %u\n", state->length));
1798 this = state->distcode[BITS(state->distbits)];
1799 if ((unsigned)(this.bits) <= bits) break;
1802 if ((this.op & 0xf0) == 0) {
1805 this = state->distcode[last.val +
1806 (BITS(last.bits + last.op) >> last.bits)];
1807 if ((unsigned)(last.bits + this.bits) <= bits) break;
1810 DROPBITS(last.bits);
1812 DROPBITS(this.bits);
1814 strm->msg = (char *)"invalid distance code";
1818 state->offset = (unsigned)this.val;
1819 state->extra = (unsigned)(this.op) & 15;
1820 state->mode = DISTEXT;
1823 NEEDBITS(state->extra);
1824 state->offset += BITS(state->extra);
1825 DROPBITS(state->extra);
1827 #ifdef INFLATE_STRICT
1828 if (state->offset > state->dmax) {
1829 strm->msg = (char *)"invalid distance too far back";
1834 if (state->offset > state->whave + out - left) {
1835 strm->msg = (char *)"invalid distance too far back";
1839 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1840 state->mode = MATCH;
1842 if (left == 0) goto inf_leave;
1844 if (state->offset > copy) { /* copy from window */
1845 copy = state->offset - copy;
1846 if (copy > state->write) {
1847 copy -= state->write;
1848 from = state->window + (state->wsize - copy);
1851 from = state->window + (state->write - copy);
1852 if (copy > state->length) copy = state->length;
1854 else { /* copy from output */
1855 from = put - state->offset;
1856 copy = state->length;
1858 if (copy > left) copy = left;
1860 state->length -= copy;
1864 if (state->length == 0) state->mode = LEN;
1867 if (left == 0) goto inf_leave;
1868 *put++ = (unsigned char)(state->length);
1876 strm->total_out += out;
1877 state->total += out;
1879 strm->adler = state->check =
1880 UPDATE(state->check, put - out, out);
1884 state->flags ? hold :
1886 REVERSE(hold)) != state->check) {
1887 strm->msg = (char *)"incorrect data check";
1892 Tracev((stderr, "inflate: check matches trailer\n"));
1895 state->mode = LENGTH;
1897 if (state->wrap && state->flags) {
1899 if (hold != (state->total & 0xffffffffUL)) {
1900 strm->msg = (char *)"incorrect length check";
1905 Tracev((stderr, "inflate: length matches trailer\n"));
1919 return Z_STREAM_ERROR;
1923 Return from inflate(), updating the total counts and the check value.
1924 If there was no progress during the inflate() call, return a buffer
1925 error. Call updatewindow() to create and/or update the window state.
1926 Note: a memory error from inflate() is non-recoverable.
1930 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1931 if (updatewindow(strm, out)) {
1935 in -= strm->avail_in;
1936 out -= strm->avail_out;
1937 strm->total_in += in;
1938 strm->total_out += out;
1939 state->total += out;
1940 if (state->wrap && out)
1941 strm->adler = state->check =
1942 UPDATE(state->check, strm->next_out - out, out);
1943 strm->data_type = state->bits + (state->last ? 64 : 0) +
1944 (state->mode == TYPE ? 128 : 0);
1945 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1950 int ZEXPORT inflateEnd(strm)
1953 struct inflate_state FAR *state;
1954 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1955 return Z_STREAM_ERROR;
1956 state = (struct inflate_state FAR *)strm->state;
1957 if (state->window != Z_NULL) {
1958 if (strm->outcb != Z_NULL)
1959 (*strm->outcb)(Z_NULL, 0);
1960 ZFREE(strm, state->window);
1962 ZFREE(strm, strm->state);
1963 strm->state = Z_NULL;
1964 Tracev((stderr, "inflate: end\n"));
1969 /* zutil.c -- target dependent utility functions for the compression library
1970 * Copyright (C) 1995-2005 Jean-loup Gailly.
1971 * For conditions of distribution and use, see copyright notice in zlib.h
1976 #ifndef NO_DUMMY_DECL
1977 struct internal_state {int dummy;}; /* for buggy compilers */
1980 const char * const z_errmsg[10] = {
1981 "need dictionary", /* Z_NEED_DICT 2 */
1982 "stream end", /* Z_STREAM_END 1 */
1984 "file error", /* Z_ERRNO (-1) */
1985 "stream error", /* Z_STREAM_ERROR (-2) */
1986 "data error", /* Z_DATA_ERROR (-3) */
1987 "insufficient memory", /* Z_MEM_ERROR (-4) */
1988 "buffer error", /* Z_BUF_ERROR (-5) */
1989 "incompatible version",/* Z_VERSION_ERROR (-6) */
1997 int z_verbose = verbose;
2002 fprintf(stderr, "%s\n", m);
2007 /* exported to allow conversion of error code to string for compress() and
2010 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
2013 extern voidp malloc OF((uInt size));
2014 extern voidp calloc OF((uInt items, uInt size));
2015 extern void free OF((voidpf ptr));
2018 voidpf zcalloc (opaque, items, size)
2024 items += size - size; /* make compiler happy */
2025 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2026 (voidpf)calloc(items, size);
2029 void zcfree (opaque, ptr, nb)
2036 return; /* make compiler happy */
2039 #endif /* MY_ZCALLOC */
2041 /* adler32.c -- compute the Adler-32 checksum of a data stream
2042 * Copyright (C) 1995-2004 Mark Adler
2043 * For conditions of distribution and use, see copyright notice in zlib.h
2048 #define BASE 65521UL /* largest prime smaller than 65536 */
2050 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2052 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2053 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2054 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2055 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2056 #define DO16(buf) DO8(buf,0); DO8(buf,8);
2058 /* use NO_DIVIDE if your processor does not do division in hardware */
2062 if (a >= (BASE << 16)) \
2063 a -= (BASE << 16); \
2064 if (a >= (BASE << 15)) \
2065 a -= (BASE << 15); \
2066 if (a >= (BASE << 14)) \
2067 a -= (BASE << 14); \
2068 if (a >= (BASE << 13)) \
2069 a -= (BASE << 13); \
2070 if (a >= (BASE << 12)) \
2071 a -= (BASE << 12); \
2072 if (a >= (BASE << 11)) \
2073 a -= (BASE << 11); \
2074 if (a >= (BASE << 10)) \
2075 a -= (BASE << 10); \
2076 if (a >= (BASE << 9)) \
2078 if (a >= (BASE << 8)) \
2080 if (a >= (BASE << 7)) \
2082 if (a >= (BASE << 6)) \
2084 if (a >= (BASE << 5)) \
2086 if (a >= (BASE << 4)) \
2088 if (a >= (BASE << 3)) \
2090 if (a >= (BASE << 2)) \
2092 if (a >= (BASE << 1)) \
2099 if (a >= (BASE << 4)) \
2101 if (a >= (BASE << 3)) \
2103 if (a >= (BASE << 2)) \
2105 if (a >= (BASE << 1)) \
2111 #define MOD(a) a %= BASE
2112 #define MOD4(a) a %= BASE
2115 /* ========================================================================= */
2116 uLong ZEXPORT adler32(adler, buf, len)
2124 /* split Adler-32 into component sums */
2125 sum2 = (adler >> 16) & 0xffff;
2128 /* in case user likes doing a byte at a time, keep it fast */
2136 return adler | (sum2 << 16);
2139 /* initial Adler-32 value (deferred check for len == 1 speed) */
2143 /* in case short lengths are provided, keep it somewhat fast */
2151 MOD4(sum2); /* only added so many BASE's */
2152 return adler | (sum2 << 16);
2155 /* do length NMAX blocks -- requires just one modulo operation */
2156 while (len >= NMAX) {
2158 n = NMAX / 16; /* NMAX is divisible by 16 */
2160 DO16(buf); /* 16 sums unrolled */
2167 /* do remaining bytes (less than NMAX, still just one modulo) */
2168 if (len) { /* avoid modulos if none remaining */
2182 /* return recombined sums */
2183 return adler | (sum2 << 16);