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 #undef OFF /* avoid conflicts */
33 /* To avoid a build time warning */
41 /* compile with -Dlocal if your debugger can't find static symbols */
43 typedef unsigned char uch;
45 typedef unsigned short ush;
47 typedef unsigned long ulg;
49 #define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
50 #define ERR_RETURN(strm,err) return (strm->msg = (char*)ERR_MSG(err), (err))
51 /* To be used only when the state is known to be valid */
54 #define NULL ((void *) 0)
57 /* common constants */
60 #define DEF_WBITS MAX_WBITS
62 /* default windowBits for decompression. MAX_WBITS is for compression only */
64 #if MAX_MEM_LEVEL >= 8
65 #define DEF_MEM_LEVEL 8
67 #define DEF_MEM_LEVEL MAX_MEM_LEVEL
69 /* default memLevel */
71 #define STORED_BLOCK 0
72 #define STATIC_TREES 1
74 /* The three kinds of block type */
78 /* The minimum and maximum match lengths */
82 #include <linux/string.h>
83 #define zmemcpy memcpy
84 #define zmemcmp memcmp
85 #define zmemzero(dest, len) memset(dest, 0, len)
87 /* Diagnostic functions */
90 extern void z_error OF((char *m));
91 #define Assert(cond,msg) {if(!(cond)) z_error(msg);}
92 #define fprintf(fp,...) printf(__VA_ARGS__)
93 #define Trace(x) {if (z_verbose>=0) fprintf x ;}
94 #define Tracev(x) {if (z_verbose>0) fprintf x ;}
95 #define Tracevv(x) {if (z_verbose>1) fprintf x ;}
96 #define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
97 #define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
99 #define Assert(cond,msg)
107 voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
108 void zcfree OF((voidpf opaque, voidpf ptr, unsigned size));
110 #define ZALLOC(strm, items, size) \
111 (*((strm)->zalloc))((strm)->opaque, (items), (size))
112 #define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), 0)
115 /* inftrees.h -- header to use inftrees.c
116 * Copyright (C) 1995-2005 Mark Adler
117 * For conditions of distribution and use, see copyright notice in zlib.h
120 /* WARNING: this file should *not* be used by applications. It is
121 part of the implementation of the compression library and is
122 subject to change. Applications should only use zlib.h.
125 /* Structure for decoding tables. Each entry provides either the
126 information needed to do the operation requested by the code that
127 indexed that table entry, or it provides a pointer to another
128 table that indexes more bits of the code. op indicates whether
129 the entry is a pointer to another table, a literal, a length or
130 distance, an end-of-block, or an invalid code. For a table
131 pointer, the low four bits of op is the number of index bits of
132 that table. For a length or distance, the low four bits of op
133 is the number of extra bits to get after the code. bits is
134 the number of bits in this code or part of the code to drop off
135 of the bit buffer. val is the actual byte to output in the case
136 of a literal, the base length or distance, or the offset from
137 the current table to the next table. Each entry is four bytes. */
140 unsigned char op; /* operation, extra bits, table bits */
141 unsigned char bits; /* bits in this part of the code */
142 unsigned short val; /* offset in table or code value */
145 /* Maximum size of dynamic tree. The maximum found in a long but non-
146 exhaustive search was 1444 code structures (852 for length/literals
147 and 592 for distances, the latter actually the result of an
148 exhaustive search). The true maximum is not known, but the value
149 below is more than safe. */
153 /* Type of code to build for inftable() */
160 extern int inflate_table OF((codetype type, unsigned short FAR *lens,
161 unsigned codes, code FAR * FAR *table,
162 unsigned FAR *bits, unsigned short FAR *work));
164 /* inflate.h -- internal inflate state definition
165 * Copyright (C) 1995-2004 Mark Adler
166 * For conditions of distribution and use, see copyright notice in zlib.h
169 /* WARNING: this file should *not* be used by applications. It is
170 part of the implementation of the compression library and is
171 subject to change. Applications should only use zlib.h.
176 /* Possible inflate modes between inflate() calls */
178 HEAD, /* i: waiting for magic header */
179 FLAGS, /* i: waiting for method and flags (gzip) */
180 TIME, /* i: waiting for modification time (gzip) */
181 OS, /* i: waiting for extra flags and operating system (gzip) */
182 EXLEN, /* i: waiting for extra length (gzip) */
183 EXTRA, /* i: waiting for extra bytes (gzip) */
184 NAME, /* i: waiting for end of file name (gzip) */
185 COMMENT, /* i: waiting for end of comment (gzip) */
186 HCRC, /* i: waiting for header crc (gzip) */
187 DICTID, /* i: waiting for dictionary check value */
188 DICT, /* waiting for inflateSetDictionary() call */
189 TYPE, /* i: waiting for type bits, including last-flag bit */
190 TYPEDO, /* i: same, but skip check to exit inflate on new block */
191 STORED, /* i: waiting for stored size (length and complement) */
192 COPY, /* i/o: waiting for input or output to copy stored block */
193 TABLE, /* i: waiting for dynamic block table lengths */
194 LENLENS, /* i: waiting for code length code lengths */
195 CODELENS, /* i: waiting for length/lit and distance code lengths */
196 LEN, /* i: waiting for length/lit code */
197 LENEXT, /* i: waiting for length extra bits */
198 DIST, /* i: waiting for distance code */
199 DISTEXT, /* i: waiting for distance extra bits */
200 MATCH, /* o: waiting for output space to copy string */
201 LIT, /* o: waiting for output space to write literal */
202 CHECK, /* i: waiting for 32-bit check value */
203 LENGTH, /* i: waiting for 32-bit length (gzip) */
204 DONE, /* finished check, done -- remain here until reset */
205 BAD, /* got a data error -- remain here until reset */
206 MEM, /* got an inflate() memory error -- remain here until reset */
207 SYNC, /* looking for synchronization bytes to restart inflate() */
215 State transitions between above modes -
217 (most modes can go to the BAD or MEM mode -- not shown for clarity)
220 HEAD -> (gzip) or (zlib)
221 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
222 NAME -> COMMENT -> HCRC -> TYPE
223 (zlib) -> DICTID or TYPE
224 DICTID -> DICT -> TYPE
226 TYPE -> STORED or TABLE or LEN or CHECK
227 STORED -> COPY -> TYPE
228 TABLE -> LENLENS -> CODELENS -> LEN
230 LEN -> LENEXT or LIT or TYPE
231 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
234 CHECK -> LENGTH -> DONE
237 /* state maintained between inflate() calls. Approximately 7K bytes. */
238 struct inflate_state {
239 inflate_mode mode; /* current inflate mode */
240 int last; /* true if processing last block */
241 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
242 int havedict; /* true if dictionary provided */
243 int flags; /* gzip header method and flags (0 if zlib) */
244 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
245 unsigned long check; /* protected copy of check value */
246 unsigned long total; /* protected copy of output count */
247 gz_headerp head; /* where to save gzip header information */
249 unsigned wbits; /* log base 2 of requested window size */
250 unsigned wsize; /* window size or zero if not using window */
251 unsigned whave; /* valid bytes in the window */
252 unsigned write; /* window write index */
253 unsigned char FAR *window; /* allocated sliding window, if needed */
254 /* bit accumulator */
255 unsigned long hold; /* input bit accumulator */
256 unsigned bits; /* number of bits in "in" */
257 /* for string and stored block copying */
258 unsigned length; /* literal or length of data to copy */
259 unsigned offset; /* distance back to copy string from */
260 /* for table and code decoding */
261 unsigned extra; /* extra bits needed */
262 /* fixed and dynamic code tables */
263 code const FAR *lencode; /* starting table for length/literal codes */
264 code const FAR *distcode; /* starting table for distance codes */
265 unsigned lenbits; /* index bits for lencode */
266 unsigned distbits; /* index bits for distcode */
267 /* dynamic table building */
268 unsigned ncode; /* number of code length code lengths */
269 unsigned nlen; /* number of length code lengths */
270 unsigned ndist; /* number of distance code lengths */
271 unsigned have; /* number of code lengths in lens[] */
272 code FAR *next; /* next available space in codes[] */
273 unsigned short lens[320]; /* temporary storage for code lengths */
274 unsigned short work[288]; /* work area for code table building */
275 code codes[ENOUGH]; /* space for code tables */
279 /* inffast.h -- header to use inffast.c
280 * Copyright (C) 1995-2003 Mark Adler
281 * For conditions of distribution and use, see copyright notice in zlib.h
284 /* WARNING: this file should *not* be used by applications. It is
285 part of the implementation of the compression library and is
286 subject to change. Applications should only use zlib.h.
289 void inflate_fast OF((z_streamp strm, unsigned start));
291 /* inffixed.h -- table for decoding fixed codes
292 * Generated automatically by makefixed().
295 /* WARNING: this file should *not* be used by applications. It
296 is part of the implementation of the compression library and
297 is subject to change. Applications should only use zlib.h.
300 static const code lenfix[512] = {
301 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
302 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
303 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
304 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
305 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
306 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
307 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
308 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
309 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
310 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
311 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
312 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
313 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
314 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
315 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
316 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
317 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
318 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
319 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
320 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
321 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
322 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
323 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
324 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
325 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
326 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
327 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
328 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
329 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
330 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
331 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
332 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
333 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
334 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
335 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
336 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
337 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
338 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
339 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
340 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
341 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
342 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
343 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
344 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
345 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
346 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
347 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
348 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
349 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
350 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
351 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
352 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
353 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
354 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
355 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
356 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
357 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
358 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
359 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
360 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
361 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
362 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
363 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
364 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
365 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
366 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
367 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
368 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
369 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
370 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
371 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
372 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
373 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
377 static const code distfix[32] = {
378 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
379 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
380 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
381 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
382 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
387 /* inffast.c -- fast decoding
388 * Copyright (C) 1995-2004 Mark Adler
389 * For conditions of distribution and use, see copyright notice in zlib.h
392 /* Allow machine dependent optimization for post-increment or pre-increment.
393 Based on testing to date,
394 Pre-increment preferred for:
396 - MIPS R5000 (Randers-Pehrson)
397 Post-increment preferred for:
399 No measurable difference:
400 - Pentium III (Anderson)
404 #define PUP(a) *++(a)
407 Decode literal, length, and distance codes and write out the resulting
408 literal and match bytes until either not enough input or output is
409 available, an end-of-block is encountered, or a data error is encountered.
410 When large enough input and output buffers are supplied to inflate(), for
411 example, a 16K input buffer and a 64K output buffer, more than 95% of the
412 inflate execution time is spent in this routine.
418 strm->avail_out >= 258
419 start >= strm->avail_out
422 On return, state->mode is one of:
424 LEN -- ran out of enough output space or enough available input
425 TYPE -- reached end of block code, inflate() to interpret next block
426 BAD -- error in block data
430 - The maximum input bits used by a length/distance pair is 15 bits for the
431 length code, 5 bits for the length extra, 15 bits for the distance code,
432 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
433 Therefore if strm->avail_in >= 6, then there is enough input to avoid
434 checking for available input while decoding.
436 - The maximum bytes that a single length/distance pair can output is 258
437 bytes, which is the maximum length that can be coded. inflate_fast()
438 requires strm->avail_out >= 258 for each loop to avoid checking for
441 void inflate_fast(strm, start)
443 unsigned start; /* inflate()'s starting value for strm->avail_out */
445 struct inflate_state FAR *state;
446 unsigned char FAR *in; /* local strm->next_in */
447 unsigned char FAR *last; /* while in < last, enough input available */
448 unsigned char FAR *out; /* local strm->next_out */
449 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
450 unsigned char FAR *end; /* while out < end, enough space available */
451 #ifdef INFLATE_STRICT
452 unsigned dmax; /* maximum distance from zlib header */
454 unsigned wsize; /* window size or zero if not using window */
455 unsigned whave; /* valid bytes in the window */
456 unsigned write; /* window write index */
457 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
458 unsigned long hold; /* local strm->hold */
459 unsigned bits; /* local strm->bits */
460 code const FAR *lcode; /* local strm->lencode */
461 code const FAR *dcode; /* local strm->distcode */
462 unsigned lmask; /* mask for first level of length codes */
463 unsigned dmask; /* mask for first level of distance codes */
464 code this; /* retrieved table entry */
465 unsigned op; /* code bits, operation, extra bits, or */
466 /* window position, window bytes to copy */
467 unsigned len; /* match length, unused bytes */
468 unsigned dist; /* match distance */
469 unsigned char FAR *from; /* where to copy match from */
471 /* copy state to local variables */
472 state = (struct inflate_state FAR *)strm->state;
473 in = strm->next_in - OFF;
474 last = in + (strm->avail_in - 5);
475 out = strm->next_out - OFF;
476 beg = out - (start - strm->avail_out);
477 end = out + (strm->avail_out - 257);
478 #ifdef INFLATE_STRICT
481 wsize = state->wsize;
482 whave = state->whave;
483 write = state->write;
484 window = state->window;
487 lcode = state->lencode;
488 dcode = state->distcode;
489 lmask = (1U << state->lenbits) - 1;
490 dmask = (1U << state->distbits) - 1;
492 /* decode literals and length/distances until end-of-block or not enough
493 input data or output space */
496 hold += (unsigned long)(PUP(in)) << bits;
498 hold += (unsigned long)(PUP(in)) << bits;
501 this = lcode[hold & lmask];
503 op = (unsigned)(this.bits);
506 op = (unsigned)(this.op);
507 if (op == 0) { /* literal */
508 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
509 "inflate: literal '%c'\n" :
510 "inflate: literal 0x%02x\n", this.val));
511 PUP(out) = (unsigned char)(this.val);
513 else if (op & 16) { /* length base */
514 len = (unsigned)(this.val);
515 op &= 15; /* number of extra bits */
518 hold += (unsigned long)(PUP(in)) << bits;
521 len += (unsigned)hold & ((1U << op) - 1);
525 Tracevv((stderr, "inflate: length %u\n", len));
527 hold += (unsigned long)(PUP(in)) << bits;
529 hold += (unsigned long)(PUP(in)) << bits;
532 this = dcode[hold & dmask];
534 op = (unsigned)(this.bits);
537 op = (unsigned)(this.op);
538 if (op & 16) { /* distance base */
539 dist = (unsigned)(this.val);
540 op &= 15; /* number of extra bits */
542 hold += (unsigned long)(PUP(in)) << bits;
545 hold += (unsigned long)(PUP(in)) << bits;
549 dist += (unsigned)hold & ((1U << op) - 1);
550 #ifdef INFLATE_STRICT
552 strm->msg = (char *)"invalid distance too far back";
559 Tracevv((stderr, "inflate: distance %u\n", dist));
560 op = (unsigned)(out - beg); /* max distance in output */
561 if (dist > op) { /* see if copy from window */
562 op = dist - op; /* distance back in window */
564 strm->msg = (char *)"invalid distance too far back";
569 if (write == 0) { /* very common case */
571 if (op < len) { /* some from window */
574 PUP(out) = PUP(from);
576 from = out - dist; /* rest from output */
579 else if (write < op) { /* wrap around window */
580 from += wsize + write - op;
582 if (op < len) { /* some from end of window */
585 PUP(out) = PUP(from);
588 if (write < len) { /* some from start of window */
592 PUP(out) = PUP(from);
594 from = out - dist; /* rest from output */
598 else { /* contiguous in window */
600 if (op < len) { /* some from window */
603 PUP(out) = PUP(from);
605 from = out - dist; /* rest from output */
609 PUP(out) = PUP(from);
610 PUP(out) = PUP(from);
611 PUP(out) = PUP(from);
615 PUP(out) = PUP(from);
617 PUP(out) = PUP(from);
621 from = out - dist; /* copy direct from output */
622 do { /* minimum length is three */
623 PUP(out) = PUP(from);
624 PUP(out) = PUP(from);
625 PUP(out) = PUP(from);
629 PUP(out) = PUP(from);
631 PUP(out) = PUP(from);
635 else if ((op & 64) == 0) { /* 2nd level distance code */
636 this = dcode[this.val + (hold & ((1U << op) - 1))];
640 strm->msg = (char *)"invalid distance code";
645 else if ((op & 64) == 0) { /* 2nd level length code */
646 this = lcode[this.val + (hold & ((1U << op) - 1))];
649 else if (op & 32) { /* end-of-block */
650 Tracevv((stderr, "inflate: end of block\n"));
655 strm->msg = (char *)"invalid literal/length code";
659 } while (in < last && out < end);
661 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
665 hold &= (1U << bits) - 1;
667 /* update state and return */
668 strm->next_in = in + OFF;
669 strm->next_out = out + OFF;
670 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
671 strm->avail_out = (unsigned)(out < end ?
672 257 + (end - out) : 257 - (out - end));
679 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
680 - Using bit fields for code structure
681 - Different op definition to avoid & for extra bits (do & for table bits)
682 - Three separate decoding do-loops for direct, window, and write == 0
683 - Special case for distance > 1 copies to do overlapped load and store copy
684 - Explicit branch predictions (based on measured branch probabilities)
685 - Deferring match copy and interspersed it with decoding subsequent codes
686 - Swapping literal/length else
687 - Swapping window/direct else
688 - Larger unrolled copy loops (three is about right)
689 - Moving len -= 3 statement into middle of loop
693 /* inftrees.c -- generate Huffman trees for efficient decoding
694 * Copyright (C) 1995-2005 Mark Adler
695 * For conditions of distribution and use, see copyright notice in zlib.h
700 If you use the zlib library in a product, an acknowledgment is welcome
701 in the documentation of your product. If for some reason you cannot
702 include such an acknowledgment, I would appreciate that you keep this
703 copyright string in the executable of your product.
707 Build a set of tables to decode the provided canonical Huffman code.
708 The code lengths are lens[0..codes-1]. The result starts at *table,
709 whose indices are 0..2^bits-1. work is a writable array of at least
710 lens shorts, which is used as a work area. type is the type of code
711 to be generated, CODES, LENS, or DISTS. On return, zero is success,
712 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
713 on return points to the next available entry's address. bits is the
714 requested root table index bits, and on return it is the actual root
715 table index bits. It will differ if the request is greater than the
716 longest code or if it is less than the shortest code.
718 int inflate_table(type, lens, codes, table, bits, work)
720 unsigned short FAR *lens;
722 code FAR * FAR *table;
724 unsigned short FAR *work;
726 unsigned len; /* a code's length in bits */
727 unsigned sym; /* index of code symbols */
728 unsigned min, max; /* minimum and maximum code lengths */
729 unsigned root; /* number of index bits for root table */
730 unsigned curr; /* number of index bits for current table */
731 unsigned drop; /* code bits to drop for sub-table */
732 int left; /* number of prefix codes available */
733 unsigned used; /* code entries in table used */
734 unsigned huff; /* Huffman code */
735 unsigned incr; /* for incrementing code, index */
736 unsigned fill; /* index for replicating entries */
737 unsigned low; /* low bits for current root entry */
738 unsigned mask; /* mask for low root bits */
739 code this; /* table entry for duplication */
740 code FAR *next; /* next available space in table */
741 const unsigned short FAR *base; /* base value table to use */
742 const unsigned short FAR *extra; /* extra bits table to use */
743 int end; /* use base and extra for symbol > end */
744 unsigned short count[MAXBITS+1]; /* number of codes of each length */
745 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
746 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
747 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
748 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
749 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
750 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
751 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
752 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
753 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
754 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
755 8193, 12289, 16385, 24577, 0, 0};
756 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
757 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
758 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
759 28, 28, 29, 29, 64, 64};
762 Process a set of code lengths to create a canonical Huffman code. The
763 code lengths are lens[0..codes-1]. Each length corresponds to the
764 symbols 0..codes-1. The Huffman code is generated by first sorting the
765 symbols by length from short to long, and retaining the symbol order
766 for codes with equal lengths. Then the code starts with all zero bits
767 for the first code of the shortest length, and the codes are integer
768 increments for the same length, and zeros are appended as the length
769 increases. For the deflate format, these bits are stored backwards
770 from their more natural integer increment ordering, and so when the
771 decoding tables are built in the large loop below, the integer codes
772 are incremented backwards.
774 This routine assumes, but does not check, that all of the entries in
775 lens[] are in the range 0..MAXBITS. The caller must assure this.
776 1..MAXBITS is interpreted as that code length. zero means that that
777 symbol does not occur in this code.
779 The codes are sorted by computing a count of codes for each length,
780 creating from that a table of starting indices for each length in the
781 sorted table, and then entering the symbols in order in the sorted
782 table. The sorted table is work[], with that space being provided by
785 The length counts are used for other purposes as well, i.e. finding
786 the minimum and maximum length codes, determining if there are any
787 codes at all, checking for a valid set of lengths, and looking ahead
788 at length counts to determine sub-table sizes when building the
792 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
793 for (len = 0; len <= MAXBITS; len++)
795 for (sym = 0; sym < codes; sym++)
798 /* bound code lengths, force root to be within code lengths */
800 for (max = MAXBITS; max >= 1; max--)
801 if (count[max] != 0) break;
802 if (root > max) root = max;
803 if (max == 0) { /* no symbols to code at all */
804 this.op = (unsigned char)64; /* invalid code marker */
805 this.bits = (unsigned char)1;
806 this.val = (unsigned short)0;
807 *(*table)++ = this; /* make a table to force an error */
810 return 0; /* no symbols, but wait for decoding to report error */
812 for (min = 1; min <= MAXBITS; min++)
813 if (count[min] != 0) break;
814 if (root < min) root = min;
816 /* check for an over-subscribed or incomplete set of lengths */
818 for (len = 1; len <= MAXBITS; len++) {
821 if (left < 0) return -1; /* over-subscribed */
823 if (left > 0 && (type == CODES || max != 1))
824 return -1; /* incomplete set */
826 /* generate offsets into symbol table for each length for sorting */
828 for (len = 1; len < MAXBITS; len++)
829 offs[len + 1] = offs[len] + count[len];
831 /* sort symbols by length, by symbol order within each length */
832 for (sym = 0; sym < codes; sym++)
833 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
836 Create and fill in decoding tables. In this loop, the table being
837 filled is at next and has curr index bits. The code being used is huff
838 with length len. That code is converted to an index by dropping drop
839 bits off of the bottom. For codes where len is less than drop + curr,
840 those top drop + curr - len bits are incremented through all values to
841 fill the table with replicated entries.
843 root is the number of index bits for the root table. When len exceeds
844 root, sub-tables are created pointed to by the root entry with an index
845 of the low root bits of huff. This is saved in low to check for when a
846 new sub-table should be started. drop is zero when the root table is
847 being filled, and drop is root when sub-tables are being filled.
849 When a new sub-table is needed, it is necessary to look ahead in the
850 code lengths to determine what size sub-table is needed. The length
851 counts are used for this, and so count[] is decremented as codes are
852 entered in the tables.
854 used keeps track of how many table entries have been allocated from the
855 provided *table space. It is checked when a LENS table is being made
856 against the space in *table, ENOUGH, minus the maximum space needed by
857 the worst case distance code, MAXD. This should never happen, but the
858 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
859 This assumes that when type == LENS, bits == 9.
861 sym increments through all symbols, and the loop terminates when
862 all codes of length max, i.e. all codes, have been processed. This
863 routine permits incomplete codes, so another loop after this one fills
864 in the rest of the decoding tables with invalid code markers.
867 /* set up for code type */
870 base = extra = work; /* dummy value--not used */
886 /* initialize state for loop */
887 huff = 0; /* starting code */
888 sym = 0; /* starting code symbol */
889 len = min; /* starting code length */
890 next = *table; /* current table to fill in */
891 curr = root; /* current table index bits */
892 drop = 0; /* current bits to drop from code for index */
893 low = (unsigned)(-1); /* trigger new sub-table when len > root */
894 used = 1U << root; /* use root table entries */
895 mask = used - 1; /* mask for comparing low */
897 /* check available table space */
898 if (type == LENS && used >= ENOUGH - MAXD)
901 /* process all codes and make table entries */
903 /* create table entry */
904 this.bits = (unsigned char)(len - drop);
905 if ((int)(work[sym]) < end) {
906 this.op = (unsigned char)0;
907 this.val = work[sym];
909 else if ((int)(work[sym]) > end) {
910 this.op = (unsigned char)(extra[work[sym]]);
911 this.val = base[work[sym]];
914 this.op = (unsigned char)(32 + 64); /* end of block */
918 /* replicate for those indices with low len bits equal to huff */
919 incr = 1U << (len - drop);
921 min = fill; /* save offset to next table */
924 next[(huff >> drop) + fill] = this;
927 /* backwards increment the len-bit code huff */
928 incr = 1U << (len - 1);
938 /* go to next symbol, update count, len */
940 if (--(count[len]) == 0) {
941 if (len == max) break;
942 len = lens[work[sym]];
945 /* create new sub-table if needed */
946 if (len > root && (huff & mask) != low) {
947 /* if first time, transition to sub-tables */
951 /* increment past last table */
952 next += min; /* here min is 1 << curr */
954 /* determine length of next table */
956 left = (int)(1 << curr);
957 while (curr + drop < max) {
958 left -= count[curr + drop];
959 if (left <= 0) break;
964 /* check for enough space */
966 if (type == LENS && used >= ENOUGH - MAXD)
969 /* point entry in root table to sub-table */
971 (*table)[low].op = (unsigned char)curr;
972 (*table)[low].bits = (unsigned char)root;
973 (*table)[low].val = (unsigned short)(next - *table);
978 Fill in rest of table for incomplete codes. This loop is similar to the
979 loop above in incrementing huff for table indices. It is assumed that
980 len is equal to curr + drop, so there is no loop needed to increment
981 through high index bits. When the current sub-table is filled, the loop
982 drops back to the root table to fill in any remaining entries there.
984 this.op = (unsigned char)64; /* invalid code marker */
985 this.bits = (unsigned char)(len - drop);
986 this.val = (unsigned short)0;
988 /* when done with sub-table, drop back to root table */
989 if (drop != 0 && (huff & mask) != low) {
993 this.bits = (unsigned char)len;
996 /* put invalid code marker in table */
997 next[huff >> drop] = this;
999 /* backwards increment the len-bit code huff */
1000 incr = 1U << (len - 1);
1011 /* set return parameters */
1018 /* inflate.c -- zlib decompression
1019 * Copyright (C) 1995-2005 Mark Adler
1020 * For conditions of distribution and use, see copyright notice in zlib.h
1022 local void fixedtables OF((struct inflate_state FAR *state));
1023 local int updatewindow OF((z_streamp strm, unsigned out));
1025 int ZEXPORT inflateReset(strm)
1028 struct inflate_state FAR *state;
1030 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1031 state = (struct inflate_state FAR *)strm->state;
1032 strm->total_in = strm->total_out = state->total = 0;
1034 strm->adler = 1; /* to support ill-conceived Java test suite */
1037 state->havedict = 0;
1038 state->dmax = 32768U;
1039 state->head = Z_NULL;
1045 state->lencode = state->distcode = state->next = state->codes;
1046 if (strm->outcb != Z_NULL)
1047 (*strm->outcb)(Z_NULL, 0);
1048 Tracev((stderr, "inflate: reset\n"));
1052 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1055 const char *version;
1058 struct inflate_state FAR *state;
1060 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1061 stream_size != (int)(sizeof(z_stream)))
1062 return Z_VERSION_ERROR;
1063 if (strm == Z_NULL) return Z_STREAM_ERROR;
1064 strm->msg = Z_NULL; /* in case we return an error */
1065 if (strm->zalloc == (alloc_func)0) {
1066 strm->zalloc = zcalloc;
1067 strm->opaque = (voidpf)0;
1069 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1070 state = (struct inflate_state FAR *)
1071 ZALLOC(strm, 1, sizeof(struct inflate_state));
1072 if (state == Z_NULL) return Z_MEM_ERROR;
1073 Tracev((stderr, "inflate: allocated\n"));
1074 strm->state = (struct internal_state FAR *)state;
1075 if (windowBits < 0) {
1077 windowBits = -windowBits;
1080 state->wrap = (windowBits >> 4) + 1;
1082 if (windowBits < 48) windowBits &= 15;
1085 if (windowBits < 8 || windowBits > 15) {
1087 strm->state = Z_NULL;
1088 return Z_STREAM_ERROR;
1090 state->wbits = (unsigned)windowBits;
1091 state->window = Z_NULL;
1092 return inflateReset(strm);
1095 int ZEXPORT inflateInit_(strm, version, stream_size)
1097 const char *version;
1100 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
1103 local void fixedtables(state)
1104 struct inflate_state FAR *state;
1106 state->lencode = lenfix;
1108 state->distcode = distfix;
1109 state->distbits = 5;
1113 Update the window with the last wsize (normally 32K) bytes written before
1114 returning. If window does not exist yet, create it. This is only called
1115 when a window is already in use, or when output has been written during this
1116 inflate call, but the end of the deflate stream has not been reached yet.
1117 It is also called to create a window for dictionary data when a dictionary
1120 Providing output buffers larger than 32K to inflate() should provide a speed
1121 advantage, since only the last 32K of output is copied to the sliding window
1122 upon return from inflate(), and since all distances after the first 32K of
1123 output will fall in the output data, making match copies simpler and faster.
1124 The advantage may be dependent on the size of the processor's data caches.
1126 local int updatewindow(strm, out)
1130 struct inflate_state FAR *state;
1131 unsigned copy, dist;
1133 state = (struct inflate_state FAR *)strm->state;
1135 /* if it hasn't been done already, allocate space for the window */
1136 if (state->window == Z_NULL) {
1137 state->window = (unsigned char FAR *)
1138 ZALLOC(strm, 1U << state->wbits,
1139 sizeof(unsigned char));
1140 if (state->window == Z_NULL) return 1;
1143 /* if window not in use yet, initialize */
1144 if (state->wsize == 0) {
1145 state->wsize = 1U << state->wbits;
1150 /* copy state->wsize or less output bytes into the circular window */
1151 copy = out - strm->avail_out;
1152 if (copy >= state->wsize) {
1153 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1155 state->whave = state->wsize;
1158 dist = state->wsize - state->write;
1159 if (dist > copy) dist = copy;
1160 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1163 zmemcpy(state->window, strm->next_out - copy, copy);
1164 state->write = copy;
1165 state->whave = state->wsize;
1168 state->write += dist;
1169 if (state->write == state->wsize) state->write = 0;
1170 if (state->whave < state->wsize) state->whave += dist;
1176 /* Macros for inflate(): */
1178 /* check function to use adler32() for zlib or crc32() for gzip */
1179 #define UPDATE(check, buf, len) \
1180 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1182 /* check macros for header crc */
1183 #define CRC2(check, word) \
1185 hbuf[0] = (unsigned char)(word); \
1186 hbuf[1] = (unsigned char)((word) >> 8); \
1187 check = crc32(check, hbuf, 2); \
1190 #define CRC4(check, word) \
1192 hbuf[0] = (unsigned char)(word); \
1193 hbuf[1] = (unsigned char)((word) >> 8); \
1194 hbuf[2] = (unsigned char)((word) >> 16); \
1195 hbuf[3] = (unsigned char)((word) >> 24); \
1196 check = crc32(check, hbuf, 4); \
1199 /* Load registers with state in inflate() for speed */
1202 put = strm->next_out; \
1203 left = strm->avail_out; \
1204 next = strm->next_in; \
1205 have = strm->avail_in; \
1206 hold = state->hold; \
1207 bits = state->bits; \
1210 /* Restore state from registers in inflate() */
1213 strm->next_out = put; \
1214 strm->avail_out = left; \
1215 strm->next_in = next; \
1216 strm->avail_in = have; \
1217 state->hold = hold; \
1218 state->bits = bits; \
1221 /* Clear the input bit accumulator */
1222 #define INITBITS() \
1228 /* Get a byte of input into the bit accumulator, or return from inflate()
1229 if there is no input available. */
1230 #define PULLBYTE() \
1232 if (have == 0) goto inf_leave; \
1234 hold += (unsigned long)(*next++) << bits; \
1238 /* Assure that there are at least n bits in the bit accumulator. If there is
1239 not enough available input to do that, then return from inflate(). */
1240 #define NEEDBITS(n) \
1242 while (bits < (unsigned)(n)) \
1246 /* Return the low n bits of the bit accumulator (n < 16) */
1248 ((unsigned)hold & ((1U << (n)) - 1))
1250 /* Remove n bits from the bit accumulator */
1251 #define DROPBITS(n) \
1254 bits -= (unsigned)(n); \
1257 /* Remove zero to seven bits as needed to go to a byte boundary */
1258 #define BYTEBITS() \
1260 hold >>= bits & 7; \
1264 /* Reverse the bytes in a 32-bit value */
1265 #define REVERSE(q) \
1266 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1267 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1270 inflate() uses a state machine to process as much input data and generate as
1271 much output data as possible before returning. The state machine is
1272 structured roughly as follows:
1274 for (;;) switch (state) {
1277 if (not enough input data or output space to make progress)
1279 ... make progress ...
1285 so when inflate() is called again, the same case is attempted again, and
1286 if the appropriate resources are provided, the machine proceeds to the
1287 next state. The NEEDBITS() macro is usually the way the state evaluates
1288 whether it can proceed or should return. NEEDBITS() does the return if
1289 the requested bits are not available. The typical use of the BITS macros
1293 ... do something with BITS(n) ...
1296 where NEEDBITS(n) either returns from inflate() if there isn't enough
1297 input left to load n bits into the accumulator, or it continues. BITS(n)
1298 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1299 the low n bits off the accumulator. INITBITS() clears the accumulator
1300 and sets the number of available bits to zero. BYTEBITS() discards just
1301 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1302 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1304 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1305 if there is no input available. The decoding of variable length codes uses
1306 PULLBYTE() directly in order to pull just enough bytes to decode the next
1309 Some states loop until they get enough input, making sure that enough
1310 state information is maintained to continue the loop where it left off
1311 if NEEDBITS() returns in the loop. For example, want, need, and keep
1312 would all have to actually be part of the saved state in case NEEDBITS()
1316 while (want < need) {
1318 keep[want++] = BITS(n);
1324 As shown above, if the next state is also the next case, then the break
1327 A state may also return if there is not enough output space available to
1328 complete that state. Those states are copying stored data, writing a
1329 literal byte, and copying a matching string.
1331 When returning, a "goto inf_leave" is used to update the total counters,
1332 update the check value, and determine whether any progress has been made
1333 during that inflate() call in order to return the proper return code.
1334 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1335 When there is a window, goto inf_leave will update the window with the last
1336 output written. If a goto inf_leave occurs in the middle of decompression
1337 and there is no window currently, goto inf_leave will create one and copy
1338 output to the window for the next call of inflate().
1340 In this implementation, the flush parameter of inflate() only affects the
1341 return code (per zlib.h). inflate() always writes as much as possible to
1342 strm->next_out, given the space available and the provided input--the effect
1343 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1344 the allocation of and copying into a sliding window until necessary, which
1345 provides the effect documented in zlib.h for Z_FINISH when the entire input
1346 stream available. So the only thing the flush parameter actually does is:
1347 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1348 will return Z_BUF_ERROR if it has not reached the end of the stream.
1350 int ZEXPORT inflate(strm, flush)
1354 struct inflate_state FAR *state;
1355 unsigned char FAR *next; /* next input */
1356 unsigned char FAR *put; /* next output */
1357 unsigned have, left; /* available input and output */
1358 unsigned long hold; /* bit buffer */
1359 unsigned bits; /* bits in bit buffer */
1360 unsigned in, out; /* save starting available input and output */
1361 unsigned copy; /* number of stored or match bytes to copy */
1362 unsigned char FAR *from; /* where to copy match bytes from */
1363 code this; /* current decoding table entry */
1364 code last; /* parent table entry */
1365 unsigned len; /* length to copy for repeats, bits to drop */
1366 int ret; /* return code */
1368 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1370 static const unsigned short order[19] = /* permutation of code lengths */
1371 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1373 if (strm == Z_NULL || strm->state == Z_NULL ||
1374 (strm->next_in == Z_NULL && strm->avail_in != 0))
1375 return Z_STREAM_ERROR;
1377 state = (struct inflate_state FAR *)strm->state;
1378 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1384 switch (state->mode) {
1386 if (state->wrap == 0) {
1387 state->mode = TYPEDO;
1392 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1393 state->check = crc32(0L, Z_NULL, 0);
1394 CRC2(state->check, hold);
1396 state->mode = FLAGS;
1399 state->flags = 0; /* expect zlib header */
1400 if (state->head != Z_NULL)
1401 state->head->done = -1;
1402 if (!(state->wrap & 1) || /* check if zlib header allowed */
1406 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1407 strm->msg = (char *)"incorrect header check";
1411 if (BITS(4) != Z_DEFLATED) {
1412 strm->msg = (char *)"unknown compression method";
1418 if (len > state->wbits) {
1419 strm->msg = (char *)"invalid window size";
1423 state->dmax = 1U << len;
1424 Tracev((stderr, "inflate: zlib header ok\n"));
1425 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1426 state->mode = hold & 0x200 ? DICTID : TYPE;
1432 state->flags = (int)(hold);
1433 if ((state->flags & 0xff) != Z_DEFLATED) {
1434 strm->msg = (char *)"unknown compression method";
1438 if (state->flags & 0xe000) {
1439 strm->msg = (char *)"unknown header flags set";
1443 if (state->head != Z_NULL)
1444 state->head->text = (int)((hold >> 8) & 1);
1445 if (state->flags & 0x0200) CRC2(state->check, hold);
1450 if (state->head != Z_NULL)
1451 state->head->time = hold;
1452 if (state->flags & 0x0200) CRC4(state->check, hold);
1457 if (state->head != Z_NULL) {
1458 state->head->xflags = (int)(hold & 0xff);
1459 state->head->os = (int)(hold >> 8);
1461 if (state->flags & 0x0200) CRC2(state->check, hold);
1463 state->mode = EXLEN;
1465 if (state->flags & 0x0400) {
1467 state->length = (unsigned)(hold);
1468 if (state->head != Z_NULL)
1469 state->head->extra_len = (unsigned)hold;
1470 if (state->flags & 0x0200) CRC2(state->check, hold);
1473 else if (state->head != Z_NULL)
1474 state->head->extra = Z_NULL;
1475 state->mode = EXTRA;
1477 if (state->flags & 0x0400) {
1478 copy = state->length;
1479 if (copy > have) copy = have;
1481 if (state->head != Z_NULL &&
1482 state->head->extra != Z_NULL) {
1483 len = state->head->extra_len - state->length;
1484 zmemcpy(state->head->extra + len, next,
1485 len + copy > state->head->extra_max ?
1486 state->head->extra_max - len : copy);
1488 if (state->flags & 0x0200)
1489 state->check = crc32(state->check, next, copy);
1492 state->length -= copy;
1494 if (state->length) goto inf_leave;
1499 if (state->flags & 0x0800) {
1500 if (have == 0) goto inf_leave;
1503 len = (unsigned)(next[copy++]);
1504 if (state->head != Z_NULL &&
1505 state->head->name != Z_NULL &&
1506 state->length < state->head->name_max)
1507 state->head->name[state->length++] = len;
1508 } while (len && copy < have);
1509 if (state->flags & 0x0200)
1510 state->check = crc32(state->check, next, copy);
1513 if (len) goto inf_leave;
1515 else if (state->head != Z_NULL)
1516 state->head->name = Z_NULL;
1518 state->mode = COMMENT;
1520 if (state->flags & 0x1000) {
1521 if (have == 0) goto inf_leave;
1524 len = (unsigned)(next[copy++]);
1525 if (state->head != Z_NULL &&
1526 state->head->comment != Z_NULL &&
1527 state->length < state->head->comm_max)
1528 state->head->comment[state->length++] = len;
1529 } while (len && copy < have);
1530 if (state->flags & 0x0200)
1531 state->check = crc32(state->check, next, copy);
1534 if (len) goto inf_leave;
1536 else if (state->head != Z_NULL)
1537 state->head->comment = Z_NULL;
1540 if (state->flags & 0x0200) {
1542 if (hold != (state->check & 0xffff)) {
1543 strm->msg = (char *)"header crc mismatch";
1549 if (state->head != Z_NULL) {
1550 state->head->hcrc = (int)((state->flags >> 9) & 1);
1551 state->head->done = 1;
1553 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1559 strm->adler = state->check = REVERSE(hold);
1563 if (state->havedict == 0) {
1567 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1570 if (flush == Z_BLOCK) goto inf_leave;
1574 state->mode = CHECK;
1578 state->last = BITS(1);
1581 case 0: /* stored block */
1582 Tracev((stderr, "inflate: stored block%s\n",
1583 state->last ? " (last)" : ""));
1584 state->mode = STORED;
1586 case 1: /* fixed block */
1588 Tracev((stderr, "inflate: fixed codes block%s\n",
1589 state->last ? " (last)" : ""));
1590 state->mode = LEN; /* decode codes */
1592 case 2: /* dynamic block */
1593 Tracev((stderr, "inflate: dynamic codes block%s\n",
1594 state->last ? " (last)" : ""));
1595 state->mode = TABLE;
1598 strm->msg = (char *)"invalid block type";
1604 BYTEBITS(); /* go to byte boundary */
1606 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1607 strm->msg = (char *)"invalid stored block lengths";
1611 state->length = (unsigned)hold & 0xffff;
1612 Tracev((stderr, "inflate: stored length %u\n",
1617 copy = state->length;
1619 if (copy > have) copy = have;
1620 if (copy > left) copy = left;
1621 if (copy == 0) goto inf_leave;
1622 zmemcpy(put, next, copy);
1627 state->length -= copy;
1630 Tracev((stderr, "inflate: stored end\n"));
1635 state->nlen = BITS(5) + 257;
1637 state->ndist = BITS(5) + 1;
1639 state->ncode = BITS(4) + 4;
1641 #ifndef PKZIP_BUG_WORKAROUND
1642 if (state->nlen > 286 || state->ndist > 30) {
1643 strm->msg = (char *)"too many length or distance symbols";
1648 Tracev((stderr, "inflate: table sizes ok\n"));
1650 state->mode = LENLENS;
1652 while (state->have < state->ncode) {
1654 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1657 while (state->have < 19)
1658 state->lens[order[state->have++]] = 0;
1659 state->next = state->codes;
1660 state->lencode = (code const FAR *)(state->next);
1662 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1663 &(state->lenbits), state->work);
1665 strm->msg = (char *)"invalid code lengths set";
1669 Tracev((stderr, "inflate: code lengths ok\n"));
1671 state->mode = CODELENS;
1673 while (state->have < state->nlen + state->ndist) {
1675 this = state->lencode[BITS(state->lenbits)];
1676 if ((unsigned)(this.bits) <= bits) break;
1679 if (this.val < 16) {
1680 NEEDBITS(this.bits);
1681 DROPBITS(this.bits);
1682 state->lens[state->have++] = this.val;
1685 if (this.val == 16) {
1686 NEEDBITS(this.bits + 2);
1687 DROPBITS(this.bits);
1688 if (state->have == 0) {
1689 strm->msg = (char *)"invalid bit length repeat";
1693 len = state->lens[state->have - 1];
1697 else if (this.val == 17) {
1698 NEEDBITS(this.bits + 3);
1699 DROPBITS(this.bits);
1705 NEEDBITS(this.bits + 7);
1706 DROPBITS(this.bits);
1708 copy = 11 + BITS(7);
1711 if (state->have + copy > state->nlen + state->ndist) {
1712 strm->msg = (char *)"invalid bit length repeat";
1717 state->lens[state->have++] = (unsigned short)len;
1721 /* handle error breaks in while */
1722 if (state->mode == BAD) break;
1724 /* build code tables */
1725 state->next = state->codes;
1726 state->lencode = (code const FAR *)(state->next);
1728 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1729 &(state->lenbits), state->work);
1731 strm->msg = (char *)"invalid literal/lengths set";
1735 state->distcode = (code const FAR *)(state->next);
1736 state->distbits = 6;
1737 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1738 &(state->next), &(state->distbits), state->work);
1740 strm->msg = (char *)"invalid distances set";
1744 Tracev((stderr, "inflate: codes ok\n"));
1747 if (strm->outcb != Z_NULL) /* for watchdog (U-Boot) */
1748 (*strm->outcb)(Z_NULL, 0);
1749 if (have >= 6 && left >= 258) {
1751 inflate_fast(strm, out);
1756 this = state->lencode[BITS(state->lenbits)];
1757 if ((unsigned)(this.bits) <= bits) break;
1760 if (this.op && (this.op & 0xf0) == 0) {
1763 this = state->lencode[last.val +
1764 (BITS(last.bits + last.op) >> last.bits)];
1765 if ((unsigned)(last.bits + this.bits) <= bits) break;
1768 DROPBITS(last.bits);
1770 DROPBITS(this.bits);
1771 state->length = (unsigned)this.val;
1772 if ((int)(this.op) == 0) {
1773 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1774 "inflate: literal '%c'\n" :
1775 "inflate: literal 0x%02x\n", this.val));
1780 Tracevv((stderr, "inflate: end of block\n"));
1785 strm->msg = (char *)"invalid literal/length code";
1789 state->extra = (unsigned)(this.op) & 15;
1790 state->mode = LENEXT;
1793 NEEDBITS(state->extra);
1794 state->length += BITS(state->extra);
1795 DROPBITS(state->extra);
1797 Tracevv((stderr, "inflate: length %u\n", state->length));
1801 this = state->distcode[BITS(state->distbits)];
1802 if ((unsigned)(this.bits) <= bits) break;
1805 if ((this.op & 0xf0) == 0) {
1808 this = state->distcode[last.val +
1809 (BITS(last.bits + last.op) >> last.bits)];
1810 if ((unsigned)(last.bits + this.bits) <= bits) break;
1813 DROPBITS(last.bits);
1815 DROPBITS(this.bits);
1817 strm->msg = (char *)"invalid distance code";
1821 state->offset = (unsigned)this.val;
1822 state->extra = (unsigned)(this.op) & 15;
1823 state->mode = DISTEXT;
1826 NEEDBITS(state->extra);
1827 state->offset += BITS(state->extra);
1828 DROPBITS(state->extra);
1830 #ifdef INFLATE_STRICT
1831 if (state->offset > state->dmax) {
1832 strm->msg = (char *)"invalid distance too far back";
1837 if (state->offset > state->whave + out - left) {
1838 strm->msg = (char *)"invalid distance too far back";
1842 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1843 state->mode = MATCH;
1845 if (left == 0) goto inf_leave;
1847 if (state->offset > copy) { /* copy from window */
1848 copy = state->offset - copy;
1849 if (copy > state->write) {
1850 copy -= state->write;
1851 from = state->window + (state->wsize - copy);
1854 from = state->window + (state->write - copy);
1855 if (copy > state->length) copy = state->length;
1857 else { /* copy from output */
1858 from = put - state->offset;
1859 copy = state->length;
1861 if (copy > left) copy = left;
1863 state->length -= copy;
1867 if (state->length == 0) state->mode = LEN;
1870 if (left == 0) goto inf_leave;
1871 *put++ = (unsigned char)(state->length);
1879 strm->total_out += out;
1880 state->total += out;
1882 strm->adler = state->check =
1883 UPDATE(state->check, put - out, out);
1887 state->flags ? hold :
1889 REVERSE(hold)) != state->check) {
1890 strm->msg = (char *)"incorrect data check";
1895 Tracev((stderr, "inflate: check matches trailer\n"));
1898 state->mode = LENGTH;
1900 if (state->wrap && state->flags) {
1902 if (hold != (state->total & 0xffffffffUL)) {
1903 strm->msg = (char *)"incorrect length check";
1908 Tracev((stderr, "inflate: length matches trailer\n"));
1922 return Z_STREAM_ERROR;
1926 Return from inflate(), updating the total counts and the check value.
1927 If there was no progress during the inflate() call, return a buffer
1928 error. Call updatewindow() to create and/or update the window state.
1929 Note: a memory error from inflate() is non-recoverable.
1933 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1934 if (updatewindow(strm, out)) {
1938 in -= strm->avail_in;
1939 out -= strm->avail_out;
1940 strm->total_in += in;
1941 strm->total_out += out;
1942 state->total += out;
1943 if (state->wrap && out)
1944 strm->adler = state->check =
1945 UPDATE(state->check, strm->next_out - out, out);
1946 strm->data_type = state->bits + (state->last ? 64 : 0) +
1947 (state->mode == TYPE ? 128 : 0);
1948 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1953 int ZEXPORT inflateEnd(strm)
1956 struct inflate_state FAR *state;
1957 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1958 return Z_STREAM_ERROR;
1959 state = (struct inflate_state FAR *)strm->state;
1960 if (state->window != Z_NULL) {
1961 if (strm->outcb != Z_NULL)
1962 (*strm->outcb)(Z_NULL, 0);
1963 ZFREE(strm, state->window);
1965 ZFREE(strm, strm->state);
1966 strm->state = Z_NULL;
1967 Tracev((stderr, "inflate: end\n"));
1972 /* zutil.c -- target dependent utility functions for the compression library
1973 * Copyright (C) 1995-2005 Jean-loup Gailly.
1974 * For conditions of distribution and use, see copyright notice in zlib.h
1979 #ifndef NO_DUMMY_DECL
1980 struct internal_state {int dummy;}; /* for buggy compilers */
1983 const char * const z_errmsg[10] = {
1984 "need dictionary", /* Z_NEED_DICT 2 */
1985 "stream end", /* Z_STREAM_END 1 */
1987 "file error", /* Z_ERRNO (-1) */
1988 "stream error", /* Z_STREAM_ERROR (-2) */
1989 "data error", /* Z_DATA_ERROR (-3) */
1990 "insufficient memory", /* Z_MEM_ERROR (-4) */
1991 "buffer error", /* Z_BUF_ERROR (-5) */
1992 "incompatible version",/* Z_VERSION_ERROR (-6) */
2000 int z_verbose = verbose;
2005 fprintf(stderr, "%s\n", m);
2010 /* exported to allow conversion of error code to string for compress() and
2013 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
2016 extern voidp malloc OF((uInt size));
2017 extern voidp calloc OF((uInt items, uInt size));
2018 extern void free OF((voidpf ptr));
2021 voidpf zcalloc (opaque, items, size)
2027 items += size - size; /* make compiler happy */
2028 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2029 (voidpf)calloc(items, size);
2032 void zcfree (opaque, ptr, nb)
2039 return; /* make compiler happy */
2042 #endif /* MY_ZCALLOC */
2044 /* adler32.c -- compute the Adler-32 checksum of a data stream
2045 * Copyright (C) 1995-2004 Mark Adler
2046 * For conditions of distribution and use, see copyright notice in zlib.h
2051 #define BASE 65521UL /* largest prime smaller than 65536 */
2053 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2055 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2056 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2057 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2058 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2059 #define DO16(buf) DO8(buf,0); DO8(buf,8);
2061 /* use NO_DIVIDE if your processor does not do division in hardware */
2065 if (a >= (BASE << 16)) \
2066 a -= (BASE << 16); \
2067 if (a >= (BASE << 15)) \
2068 a -= (BASE << 15); \
2069 if (a >= (BASE << 14)) \
2070 a -= (BASE << 14); \
2071 if (a >= (BASE << 13)) \
2072 a -= (BASE << 13); \
2073 if (a >= (BASE << 12)) \
2074 a -= (BASE << 12); \
2075 if (a >= (BASE << 11)) \
2076 a -= (BASE << 11); \
2077 if (a >= (BASE << 10)) \
2078 a -= (BASE << 10); \
2079 if (a >= (BASE << 9)) \
2081 if (a >= (BASE << 8)) \
2083 if (a >= (BASE << 7)) \
2085 if (a >= (BASE << 6)) \
2087 if (a >= (BASE << 5)) \
2089 if (a >= (BASE << 4)) \
2091 if (a >= (BASE << 3)) \
2093 if (a >= (BASE << 2)) \
2095 if (a >= (BASE << 1)) \
2102 if (a >= (BASE << 4)) \
2104 if (a >= (BASE << 3)) \
2106 if (a >= (BASE << 2)) \
2108 if (a >= (BASE << 1)) \
2114 #define MOD(a) a %= BASE
2115 #define MOD4(a) a %= BASE
2118 /* ========================================================================= */
2119 uLong ZEXPORT adler32(adler, buf, len)
2127 /* split Adler-32 into component sums */
2128 sum2 = (adler >> 16) & 0xffff;
2131 /* in case user likes doing a byte at a time, keep it fast */
2139 return adler | (sum2 << 16);
2142 /* initial Adler-32 value (deferred check for len == 1 speed) */
2146 /* in case short lengths are provided, keep it somewhat fast */
2154 MOD4(sum2); /* only added so many BASE's */
2155 return adler | (sum2 << 16);
2158 /* do length NMAX blocks -- requires just one modulo operation */
2159 while (len >= NMAX) {
2161 n = NMAX / 16; /* NMAX is divisible by 16 */
2163 DO16(buf); /* 16 sums unrolled */
2170 /* do remaining bytes (less than NMAX, still just one modulo) */
2171 if (len) { /* avoid modulos if none remaining */
2185 /* return recombined sums */
2186 return adler | (sum2 << 16);