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.
31 #include <asm/unaligned.h>
32 #include "u-boot/zlib.h"
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)
405 #define UP_UNALIGNED(a) get_unaligned(++(a))
408 Decode literal, length, and distance codes and write out the resulting
409 literal and match bytes until either not enough input or output is
410 available, an end-of-block is encountered, or a data error is encountered.
411 When large enough input and output buffers are supplied to inflate(), for
412 example, a 16K input buffer and a 64K output buffer, more than 95% of the
413 inflate execution time is spent in this routine.
419 strm->avail_out >= 258
420 start >= strm->avail_out
423 On return, state->mode is one of:
425 LEN -- ran out of enough output space or enough available input
426 TYPE -- reached end of block code, inflate() to interpret next block
427 BAD -- error in block data
431 - The maximum input bits used by a length/distance pair is 15 bits for the
432 length code, 5 bits for the length extra, 15 bits for the distance code,
433 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
434 Therefore if strm->avail_in >= 6, then there is enough input to avoid
435 checking for available input while decoding.
437 - The maximum bytes that a single length/distance pair can output is 258
438 bytes, which is the maximum length that can be coded. inflate_fast()
439 requires strm->avail_out >= 258 for each loop to avoid checking for
442 void inflate_fast(strm, start)
444 unsigned start; /* inflate()'s starting value for strm->avail_out */
446 struct inflate_state FAR *state;
447 unsigned char FAR *in; /* local strm->next_in */
448 unsigned char FAR *last; /* while in < last, enough input available */
449 unsigned char FAR *out; /* local strm->next_out */
450 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
451 unsigned char FAR *end; /* while out < end, enough space available */
452 #ifdef INFLATE_STRICT
453 unsigned dmax; /* maximum distance from zlib header */
455 unsigned wsize; /* window size or zero if not using window */
456 unsigned whave; /* valid bytes in the window */
457 unsigned write; /* window write index */
458 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
459 unsigned long hold; /* local strm->hold */
460 unsigned bits; /* local strm->bits */
461 code const FAR *lcode; /* local strm->lencode */
462 code const FAR *dcode; /* local strm->distcode */
463 unsigned lmask; /* mask for first level of length codes */
464 unsigned dmask; /* mask for first level of distance codes */
465 code this; /* retrieved table entry */
466 unsigned op; /* code bits, operation, extra bits, or */
467 /* window position, window bytes to copy */
468 unsigned len; /* match length, unused bytes */
469 unsigned dist; /* match distance */
470 unsigned char FAR *from; /* where to copy match from */
472 /* copy state to local variables */
473 state = (struct inflate_state FAR *)strm->state;
474 in = strm->next_in - OFF;
475 last = in + (strm->avail_in - 5);
476 out = strm->next_out - OFF;
477 beg = out - (start - strm->avail_out);
478 end = out + (strm->avail_out - 257);
479 #ifdef INFLATE_STRICT
482 wsize = state->wsize;
483 whave = state->whave;
484 write = state->write;
485 window = state->window;
488 lcode = state->lencode;
489 dcode = state->distcode;
490 lmask = (1U << state->lenbits) - 1;
491 dmask = (1U << state->distbits) - 1;
493 /* decode literals and length/distances until end-of-block or not enough
494 input data or output space */
497 hold += (unsigned long)(PUP(in)) << bits;
499 hold += (unsigned long)(PUP(in)) << bits;
502 this = lcode[hold & lmask];
504 op = (unsigned)(this.bits);
507 op = (unsigned)(this.op);
508 if (op == 0) { /* literal */
509 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
510 "inflate: literal '%c'\n" :
511 "inflate: literal 0x%02x\n", this.val));
512 PUP(out) = (unsigned char)(this.val);
514 else if (op & 16) { /* length base */
515 len = (unsigned)(this.val);
516 op &= 15; /* number of extra bits */
519 hold += (unsigned long)(PUP(in)) << bits;
522 len += (unsigned)hold & ((1U << op) - 1);
526 Tracevv((stderr, "inflate: length %u\n", len));
528 hold += (unsigned long)(PUP(in)) << bits;
530 hold += (unsigned long)(PUP(in)) << bits;
533 this = dcode[hold & dmask];
535 op = (unsigned)(this.bits);
538 op = (unsigned)(this.op);
539 if (op & 16) { /* distance base */
540 dist = (unsigned)(this.val);
541 op &= 15; /* number of extra bits */
543 hold += (unsigned long)(PUP(in)) << bits;
546 hold += (unsigned long)(PUP(in)) << bits;
550 dist += (unsigned)hold & ((1U << op) - 1);
551 #ifdef INFLATE_STRICT
553 strm->msg = (char *)"invalid distance too far back";
560 Tracevv((stderr, "inflate: distance %u\n", dist));
561 op = (unsigned)(out - beg); /* max distance in output */
562 if (dist > op) { /* see if copy from window */
563 op = dist - op; /* distance back in window */
565 strm->msg = (char *)"invalid distance too far back";
570 if (write == 0) { /* very common case */
572 if (op < len) { /* some from window */
575 PUP(out) = PUP(from);
577 from = out - dist; /* rest from output */
580 else if (write < op) { /* wrap around window */
581 from += wsize + write - op;
583 if (op < len) { /* some from end of window */
586 PUP(out) = PUP(from);
589 if (write < len) { /* some from start of window */
593 PUP(out) = PUP(from);
595 from = out - dist; /* rest from output */
599 else { /* contiguous in window */
601 if (op < len) { /* some from window */
604 PUP(out) = PUP(from);
606 from = out - dist; /* rest from output */
610 PUP(out) = PUP(from);
611 PUP(out) = PUP(from);
612 PUP(out) = PUP(from);
616 PUP(out) = PUP(from);
618 PUP(out) = PUP(from);
622 unsigned short *sout;
625 from = out - dist; /* copy direct from output */
626 /* minimum length is three */
628 if (!((long)(out - 1 + OFF) & 1)) {
629 PUP(out) = PUP(from);
632 sout = (unsigned short *)(out - OFF);
634 unsigned short *sfrom;
636 sfrom = (unsigned short *)(from - OFF);
639 PUP(sout) = UP_UNALIGNED(sfrom);
641 out = (unsigned char *)sout + OFF;
642 from = (unsigned char *)sfrom + OFF;
643 } else { /* dist == 1 or dist == 2 */
644 unsigned short pat16;
646 pat16 = *(sout-2+2*OFF);
648 #if defined(__BIG_ENDIAN)
649 pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
650 #elif defined(__LITTLE_ENDIAN)
651 pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
653 #error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
659 out = (unsigned char *)sout + OFF;
662 PUP(out) = PUP(from);
665 else if ((op & 64) == 0) { /* 2nd level distance code */
666 this = dcode[this.val + (hold & ((1U << op) - 1))];
670 strm->msg = (char *)"invalid distance code";
675 else if ((op & 64) == 0) { /* 2nd level length code */
676 this = lcode[this.val + (hold & ((1U << op) - 1))];
679 else if (op & 32) { /* end-of-block */
680 Tracevv((stderr, "inflate: end of block\n"));
685 strm->msg = (char *)"invalid literal/length code";
689 } while (in < last && out < end);
691 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
695 hold &= (1U << bits) - 1;
697 /* update state and return */
698 strm->next_in = in + OFF;
699 strm->next_out = out + OFF;
700 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
701 strm->avail_out = (unsigned)(out < end ?
702 257 + (end - out) : 257 - (out - end));
709 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
710 - Using bit fields for code structure
711 - Different op definition to avoid & for extra bits (do & for table bits)
712 - Three separate decoding do-loops for direct, window, and write == 0
713 - Special case for distance > 1 copies to do overlapped load and store copy
714 - Explicit branch predictions (based on measured branch probabilities)
715 - Deferring match copy and interspersed it with decoding subsequent codes
716 - Swapping literal/length else
717 - Swapping window/direct else
718 - Larger unrolled copy loops (three is about right)
719 - Moving len -= 3 statement into middle of loop
723 /* inftrees.c -- generate Huffman trees for efficient decoding
724 * Copyright (C) 1995-2005 Mark Adler
725 * For conditions of distribution and use, see copyright notice in zlib.h
730 If you use the zlib library in a product, an acknowledgment is welcome
731 in the documentation of your product. If for some reason you cannot
732 include such an acknowledgment, I would appreciate that you keep this
733 copyright string in the executable of your product.
737 Build a set of tables to decode the provided canonical Huffman code.
738 The code lengths are lens[0..codes-1]. The result starts at *table,
739 whose indices are 0..2^bits-1. work is a writable array of at least
740 lens shorts, which is used as a work area. type is the type of code
741 to be generated, CODES, LENS, or DISTS. On return, zero is success,
742 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
743 on return points to the next available entry's address. bits is the
744 requested root table index bits, and on return it is the actual root
745 table index bits. It will differ if the request is greater than the
746 longest code or if it is less than the shortest code.
748 int inflate_table(type, lens, codes, table, bits, work)
750 unsigned short FAR *lens;
752 code FAR * FAR *table;
754 unsigned short FAR *work;
756 unsigned len; /* a code's length in bits */
757 unsigned sym; /* index of code symbols */
758 unsigned min, max; /* minimum and maximum code lengths */
759 unsigned root; /* number of index bits for root table */
760 unsigned curr; /* number of index bits for current table */
761 unsigned drop; /* code bits to drop for sub-table */
762 int left; /* number of prefix codes available */
763 unsigned used; /* code entries in table used */
764 unsigned huff; /* Huffman code */
765 unsigned incr; /* for incrementing code, index */
766 unsigned fill; /* index for replicating entries */
767 unsigned low; /* low bits for current root entry */
768 unsigned mask; /* mask for low root bits */
769 code this; /* table entry for duplication */
770 code FAR *next; /* next available space in table */
771 const unsigned short FAR *base; /* base value table to use */
772 const unsigned short FAR *extra; /* extra bits table to use */
773 int end; /* use base and extra for symbol > end */
774 unsigned short count[MAXBITS+1]; /* number of codes of each length */
775 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
776 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
777 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
778 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
779 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
780 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
781 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
782 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
783 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
784 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
785 8193, 12289, 16385, 24577, 0, 0};
786 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
787 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
788 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
789 28, 28, 29, 29, 64, 64};
792 Process a set of code lengths to create a canonical Huffman code. The
793 code lengths are lens[0..codes-1]. Each length corresponds to the
794 symbols 0..codes-1. The Huffman code is generated by first sorting the
795 symbols by length from short to long, and retaining the symbol order
796 for codes with equal lengths. Then the code starts with all zero bits
797 for the first code of the shortest length, and the codes are integer
798 increments for the same length, and zeros are appended as the length
799 increases. For the deflate format, these bits are stored backwards
800 from their more natural integer increment ordering, and so when the
801 decoding tables are built in the large loop below, the integer codes
802 are incremented backwards.
804 This routine assumes, but does not check, that all of the entries in
805 lens[] are in the range 0..MAXBITS. The caller must assure this.
806 1..MAXBITS is interpreted as that code length. zero means that that
807 symbol does not occur in this code.
809 The codes are sorted by computing a count of codes for each length,
810 creating from that a table of starting indices for each length in the
811 sorted table, and then entering the symbols in order in the sorted
812 table. The sorted table is work[], with that space being provided by
815 The length counts are used for other purposes as well, i.e. finding
816 the minimum and maximum length codes, determining if there are any
817 codes at all, checking for a valid set of lengths, and looking ahead
818 at length counts to determine sub-table sizes when building the
822 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
823 for (len = 0; len <= MAXBITS; len++)
825 for (sym = 0; sym < codes; sym++)
828 /* bound code lengths, force root to be within code lengths */
830 for (max = MAXBITS; max >= 1; max--)
831 if (count[max] != 0) break;
832 if (root > max) root = max;
833 if (max == 0) { /* no symbols to code at all */
834 this.op = (unsigned char)64; /* invalid code marker */
835 this.bits = (unsigned char)1;
836 this.val = (unsigned short)0;
837 *(*table)++ = this; /* make a table to force an error */
840 return 0; /* no symbols, but wait for decoding to report error */
842 for (min = 1; min <= MAXBITS; min++)
843 if (count[min] != 0) break;
844 if (root < min) root = min;
846 /* check for an over-subscribed or incomplete set of lengths */
848 for (len = 1; len <= MAXBITS; len++) {
851 if (left < 0) return -1; /* over-subscribed */
853 if (left > 0 && (type == CODES || max != 1))
854 return -1; /* incomplete set */
856 /* generate offsets into symbol table for each length for sorting */
858 for (len = 1; len < MAXBITS; len++)
859 offs[len + 1] = offs[len] + count[len];
861 /* sort symbols by length, by symbol order within each length */
862 for (sym = 0; sym < codes; sym++)
863 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
866 Create and fill in decoding tables. In this loop, the table being
867 filled is at next and has curr index bits. The code being used is huff
868 with length len. That code is converted to an index by dropping drop
869 bits off of the bottom. For codes where len is less than drop + curr,
870 those top drop + curr - len bits are incremented through all values to
871 fill the table with replicated entries.
873 root is the number of index bits for the root table. When len exceeds
874 root, sub-tables are created pointed to by the root entry with an index
875 of the low root bits of huff. This is saved in low to check for when a
876 new sub-table should be started. drop is zero when the root table is
877 being filled, and drop is root when sub-tables are being filled.
879 When a new sub-table is needed, it is necessary to look ahead in the
880 code lengths to determine what size sub-table is needed. The length
881 counts are used for this, and so count[] is decremented as codes are
882 entered in the tables.
884 used keeps track of how many table entries have been allocated from the
885 provided *table space. It is checked when a LENS table is being made
886 against the space in *table, ENOUGH, minus the maximum space needed by
887 the worst case distance code, MAXD. This should never happen, but the
888 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
889 This assumes that when type == LENS, bits == 9.
891 sym increments through all symbols, and the loop terminates when
892 all codes of length max, i.e. all codes, have been processed. This
893 routine permits incomplete codes, so another loop after this one fills
894 in the rest of the decoding tables with invalid code markers.
897 /* set up for code type */
900 base = extra = work; /* dummy value--not used */
916 /* initialize state for loop */
917 huff = 0; /* starting code */
918 sym = 0; /* starting code symbol */
919 len = min; /* starting code length */
920 next = *table; /* current table to fill in */
921 curr = root; /* current table index bits */
922 drop = 0; /* current bits to drop from code for index */
923 low = (unsigned)(-1); /* trigger new sub-table when len > root */
924 used = 1U << root; /* use root table entries */
925 mask = used - 1; /* mask for comparing low */
927 /* check available table space */
928 if (type == LENS && used >= ENOUGH - MAXD)
931 /* process all codes and make table entries */
933 /* create table entry */
934 this.bits = (unsigned char)(len - drop);
935 if ((int)(work[sym]) < end) {
936 this.op = (unsigned char)0;
937 this.val = work[sym];
939 else if ((int)(work[sym]) > end) {
940 this.op = (unsigned char)(extra[work[sym]]);
941 this.val = base[work[sym]];
944 this.op = (unsigned char)(32 + 64); /* end of block */
948 /* replicate for those indices with low len bits equal to huff */
949 incr = 1U << (len - drop);
951 min = fill; /* save offset to next table */
954 next[(huff >> drop) + fill] = this;
957 /* backwards increment the len-bit code huff */
958 incr = 1U << (len - 1);
968 /* go to next symbol, update count, len */
970 if (--(count[len]) == 0) {
971 if (len == max) break;
972 len = lens[work[sym]];
975 /* create new sub-table if needed */
976 if (len > root && (huff & mask) != low) {
977 /* if first time, transition to sub-tables */
981 /* increment past last table */
982 next += min; /* here min is 1 << curr */
984 /* determine length of next table */
986 left = (int)(1 << curr);
987 while (curr + drop < max) {
988 left -= count[curr + drop];
989 if (left <= 0) break;
994 /* check for enough space */
996 if (type == LENS && used >= ENOUGH - MAXD)
999 /* point entry in root table to sub-table */
1001 (*table)[low].op = (unsigned char)curr;
1002 (*table)[low].bits = (unsigned char)root;
1003 (*table)[low].val = (unsigned short)(next - *table);
1008 Fill in rest of table for incomplete codes. This loop is similar to the
1009 loop above in incrementing huff for table indices. It is assumed that
1010 len is equal to curr + drop, so there is no loop needed to increment
1011 through high index bits. When the current sub-table is filled, the loop
1012 drops back to the root table to fill in any remaining entries there.
1014 this.op = (unsigned char)64; /* invalid code marker */
1015 this.bits = (unsigned char)(len - drop);
1016 this.val = (unsigned short)0;
1018 /* when done with sub-table, drop back to root table */
1019 if (drop != 0 && (huff & mask) != low) {
1023 this.bits = (unsigned char)len;
1026 /* put invalid code marker in table */
1027 next[huff >> drop] = this;
1029 /* backwards increment the len-bit code huff */
1030 incr = 1U << (len - 1);
1041 /* set return parameters */
1048 /* inflate.c -- zlib decompression
1049 * Copyright (C) 1995-2005 Mark Adler
1050 * For conditions of distribution and use, see copyright notice in zlib.h
1052 local void fixedtables OF((struct inflate_state FAR *state));
1053 local int updatewindow OF((z_streamp strm, unsigned out));
1055 int ZEXPORT inflateReset(strm)
1058 struct inflate_state FAR *state;
1060 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1061 state = (struct inflate_state FAR *)strm->state;
1062 strm->total_in = strm->total_out = state->total = 0;
1064 strm->adler = 1; /* to support ill-conceived Java test suite */
1067 state->havedict = 0;
1068 state->dmax = 32768U;
1069 state->head = Z_NULL;
1075 state->lencode = state->distcode = state->next = state->codes;
1076 if (strm->outcb != Z_NULL)
1077 (*strm->outcb)(Z_NULL, 0);
1078 Tracev((stderr, "inflate: reset\n"));
1082 int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1085 const char *version;
1088 struct inflate_state FAR *state;
1090 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1091 stream_size != (int)(sizeof(z_stream)))
1092 return Z_VERSION_ERROR;
1093 if (strm == Z_NULL) return Z_STREAM_ERROR;
1094 strm->msg = Z_NULL; /* in case we return an error */
1095 if (strm->zalloc == (alloc_func)0) {
1096 strm->zalloc = zcalloc;
1097 strm->opaque = (voidpf)0;
1099 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1100 state = (struct inflate_state FAR *)
1101 ZALLOC(strm, 1, sizeof(struct inflate_state));
1102 if (state == Z_NULL) return Z_MEM_ERROR;
1103 Tracev((stderr, "inflate: allocated\n"));
1104 strm->state = (struct internal_state FAR *)state;
1105 if (windowBits < 0) {
1107 windowBits = -windowBits;
1110 state->wrap = (windowBits >> 4) + 1;
1112 if (windowBits < 48) windowBits &= 15;
1115 if (windowBits < 8 || windowBits > 15) {
1117 strm->state = Z_NULL;
1118 return Z_STREAM_ERROR;
1120 state->wbits = (unsigned)windowBits;
1121 state->window = Z_NULL;
1122 return inflateReset(strm);
1125 int ZEXPORT inflateInit_(strm, version, stream_size)
1127 const char *version;
1130 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
1133 local void fixedtables(state)
1134 struct inflate_state FAR *state;
1136 state->lencode = lenfix;
1138 state->distcode = distfix;
1139 state->distbits = 5;
1143 Update the window with the last wsize (normally 32K) bytes written before
1144 returning. If window does not exist yet, create it. This is only called
1145 when a window is already in use, or when output has been written during this
1146 inflate call, but the end of the deflate stream has not been reached yet.
1147 It is also called to create a window for dictionary data when a dictionary
1150 Providing output buffers larger than 32K to inflate() should provide a speed
1151 advantage, since only the last 32K of output is copied to the sliding window
1152 upon return from inflate(), and since all distances after the first 32K of
1153 output will fall in the output data, making match copies simpler and faster.
1154 The advantage may be dependent on the size of the processor's data caches.
1156 local int updatewindow(strm, out)
1160 struct inflate_state FAR *state;
1161 unsigned copy, dist;
1163 state = (struct inflate_state FAR *)strm->state;
1165 /* if it hasn't been done already, allocate space for the window */
1166 if (state->window == Z_NULL) {
1167 state->window = (unsigned char FAR *)
1168 ZALLOC(strm, 1U << state->wbits,
1169 sizeof(unsigned char));
1170 if (state->window == Z_NULL) return 1;
1173 /* if window not in use yet, initialize */
1174 if (state->wsize == 0) {
1175 state->wsize = 1U << state->wbits;
1180 /* copy state->wsize or less output bytes into the circular window */
1181 copy = out - strm->avail_out;
1182 if (copy >= state->wsize) {
1183 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1185 state->whave = state->wsize;
1188 dist = state->wsize - state->write;
1189 if (dist > copy) dist = copy;
1190 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1193 zmemcpy(state->window, strm->next_out - copy, copy);
1194 state->write = copy;
1195 state->whave = state->wsize;
1198 state->write += dist;
1199 if (state->write == state->wsize) state->write = 0;
1200 if (state->whave < state->wsize) state->whave += dist;
1206 /* Macros for inflate(): */
1208 /* check function to use adler32() for zlib or crc32() for gzip */
1209 #define UPDATE(check, buf, len) \
1210 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1212 /* check macros for header crc */
1213 #define CRC2(check, word) \
1215 hbuf[0] = (unsigned char)(word); \
1216 hbuf[1] = (unsigned char)((word) >> 8); \
1217 check = crc32(check, hbuf, 2); \
1220 #define CRC4(check, word) \
1222 hbuf[0] = (unsigned char)(word); \
1223 hbuf[1] = (unsigned char)((word) >> 8); \
1224 hbuf[2] = (unsigned char)((word) >> 16); \
1225 hbuf[3] = (unsigned char)((word) >> 24); \
1226 check = crc32(check, hbuf, 4); \
1229 /* Load registers with state in inflate() for speed */
1232 put = strm->next_out; \
1233 left = strm->avail_out; \
1234 next = strm->next_in; \
1235 have = strm->avail_in; \
1236 hold = state->hold; \
1237 bits = state->bits; \
1240 /* Restore state from registers in inflate() */
1243 strm->next_out = put; \
1244 strm->avail_out = left; \
1245 strm->next_in = next; \
1246 strm->avail_in = have; \
1247 state->hold = hold; \
1248 state->bits = bits; \
1251 /* Clear the input bit accumulator */
1252 #define INITBITS() \
1258 /* Get a byte of input into the bit accumulator, or return from inflate()
1259 if there is no input available. */
1260 #define PULLBYTE() \
1262 if (have == 0) goto inf_leave; \
1264 hold += (unsigned long)(*next++) << bits; \
1268 /* Assure that there are at least n bits in the bit accumulator. If there is
1269 not enough available input to do that, then return from inflate(). */
1270 #define NEEDBITS(n) \
1272 while (bits < (unsigned)(n)) \
1276 /* Return the low n bits of the bit accumulator (n < 16) */
1278 ((unsigned)hold & ((1U << (n)) - 1))
1280 /* Remove n bits from the bit accumulator */
1281 #define DROPBITS(n) \
1284 bits -= (unsigned)(n); \
1287 /* Remove zero to seven bits as needed to go to a byte boundary */
1288 #define BYTEBITS() \
1290 hold >>= bits & 7; \
1294 /* Reverse the bytes in a 32-bit value */
1295 #define REVERSE(q) \
1296 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1297 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1300 inflate() uses a state machine to process as much input data and generate as
1301 much output data as possible before returning. The state machine is
1302 structured roughly as follows:
1304 for (;;) switch (state) {
1307 if (not enough input data or output space to make progress)
1309 ... make progress ...
1315 so when inflate() is called again, the same case is attempted again, and
1316 if the appropriate resources are provided, the machine proceeds to the
1317 next state. The NEEDBITS() macro is usually the way the state evaluates
1318 whether it can proceed or should return. NEEDBITS() does the return if
1319 the requested bits are not available. The typical use of the BITS macros
1323 ... do something with BITS(n) ...
1326 where NEEDBITS(n) either returns from inflate() if there isn't enough
1327 input left to load n bits into the accumulator, or it continues. BITS(n)
1328 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1329 the low n bits off the accumulator. INITBITS() clears the accumulator
1330 and sets the number of available bits to zero. BYTEBITS() discards just
1331 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1332 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1334 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1335 if there is no input available. The decoding of variable length codes uses
1336 PULLBYTE() directly in order to pull just enough bytes to decode the next
1339 Some states loop until they get enough input, making sure that enough
1340 state information is maintained to continue the loop where it left off
1341 if NEEDBITS() returns in the loop. For example, want, need, and keep
1342 would all have to actually be part of the saved state in case NEEDBITS()
1346 while (want < need) {
1348 keep[want++] = BITS(n);
1354 As shown above, if the next state is also the next case, then the break
1357 A state may also return if there is not enough output space available to
1358 complete that state. Those states are copying stored data, writing a
1359 literal byte, and copying a matching string.
1361 When returning, a "goto inf_leave" is used to update the total counters,
1362 update the check value, and determine whether any progress has been made
1363 during that inflate() call in order to return the proper return code.
1364 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1365 When there is a window, goto inf_leave will update the window with the last
1366 output written. If a goto inf_leave occurs in the middle of decompression
1367 and there is no window currently, goto inf_leave will create one and copy
1368 output to the window for the next call of inflate().
1370 In this implementation, the flush parameter of inflate() only affects the
1371 return code (per zlib.h). inflate() always writes as much as possible to
1372 strm->next_out, given the space available and the provided input--the effect
1373 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1374 the allocation of and copying into a sliding window until necessary, which
1375 provides the effect documented in zlib.h for Z_FINISH when the entire input
1376 stream available. So the only thing the flush parameter actually does is:
1377 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1378 will return Z_BUF_ERROR if it has not reached the end of the stream.
1380 int ZEXPORT inflate(strm, flush)
1384 struct inflate_state FAR *state;
1385 unsigned char FAR *next; /* next input */
1386 unsigned char FAR *put; /* next output */
1387 unsigned have, left; /* available input and output */
1388 unsigned long hold; /* bit buffer */
1389 unsigned bits; /* bits in bit buffer */
1390 unsigned in, out; /* save starting available input and output */
1391 unsigned copy; /* number of stored or match bytes to copy */
1392 unsigned char FAR *from; /* where to copy match bytes from */
1393 code this; /* current decoding table entry */
1394 code last; /* parent table entry */
1395 unsigned len; /* length to copy for repeats, bits to drop */
1396 int ret; /* return code */
1398 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1400 static const unsigned short order[19] = /* permutation of code lengths */
1401 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1403 if (strm == Z_NULL || strm->state == Z_NULL ||
1404 (strm->next_in == Z_NULL && strm->avail_in != 0))
1405 return Z_STREAM_ERROR;
1407 state = (struct inflate_state FAR *)strm->state;
1408 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1414 switch (state->mode) {
1416 if (state->wrap == 0) {
1417 state->mode = TYPEDO;
1422 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1423 state->check = crc32(0L, Z_NULL, 0);
1424 CRC2(state->check, hold);
1426 state->mode = FLAGS;
1429 state->flags = 0; /* expect zlib header */
1430 if (state->head != Z_NULL)
1431 state->head->done = -1;
1432 if (!(state->wrap & 1) || /* check if zlib header allowed */
1436 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1437 strm->msg = (char *)"incorrect header check";
1441 if (BITS(4) != Z_DEFLATED) {
1442 strm->msg = (char *)"unknown compression method";
1448 if (len > state->wbits) {
1449 strm->msg = (char *)"invalid window size";
1453 state->dmax = 1U << len;
1454 Tracev((stderr, "inflate: zlib header ok\n"));
1455 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1456 state->mode = hold & 0x200 ? DICTID : TYPE;
1462 state->flags = (int)(hold);
1463 if ((state->flags & 0xff) != Z_DEFLATED) {
1464 strm->msg = (char *)"unknown compression method";
1468 if (state->flags & 0xe000) {
1469 strm->msg = (char *)"unknown header flags set";
1473 if (state->head != Z_NULL)
1474 state->head->text = (int)((hold >> 8) & 1);
1475 if (state->flags & 0x0200) CRC2(state->check, hold);
1480 if (state->head != Z_NULL)
1481 state->head->time = hold;
1482 if (state->flags & 0x0200) CRC4(state->check, hold);
1487 if (state->head != Z_NULL) {
1488 state->head->xflags = (int)(hold & 0xff);
1489 state->head->os = (int)(hold >> 8);
1491 if (state->flags & 0x0200) CRC2(state->check, hold);
1493 state->mode = EXLEN;
1495 if (state->flags & 0x0400) {
1497 state->length = (unsigned)(hold);
1498 if (state->head != Z_NULL)
1499 state->head->extra_len = (unsigned)hold;
1500 if (state->flags & 0x0200) CRC2(state->check, hold);
1503 else if (state->head != Z_NULL)
1504 state->head->extra = Z_NULL;
1505 state->mode = EXTRA;
1507 if (state->flags & 0x0400) {
1508 copy = state->length;
1509 if (copy > have) copy = have;
1511 if (state->head != Z_NULL &&
1512 state->head->extra != Z_NULL) {
1513 len = state->head->extra_len - state->length;
1514 zmemcpy(state->head->extra + len, next,
1515 len + copy > state->head->extra_max ?
1516 state->head->extra_max - len : copy);
1518 if (state->flags & 0x0200)
1519 state->check = crc32(state->check, next, copy);
1522 state->length -= copy;
1524 if (state->length) goto inf_leave;
1529 if (state->flags & 0x0800) {
1530 if (have == 0) goto inf_leave;
1533 len = (unsigned)(next[copy++]);
1534 if (state->head != Z_NULL &&
1535 state->head->name != Z_NULL &&
1536 state->length < state->head->name_max)
1537 state->head->name[state->length++] = len;
1538 } while (len && copy < have);
1539 if (state->flags & 0x0200)
1540 state->check = crc32(state->check, next, copy);
1543 if (len) goto inf_leave;
1545 else if (state->head != Z_NULL)
1546 state->head->name = Z_NULL;
1548 state->mode = COMMENT;
1550 if (state->flags & 0x1000) {
1551 if (have == 0) goto inf_leave;
1554 len = (unsigned)(next[copy++]);
1555 if (state->head != Z_NULL &&
1556 state->head->comment != Z_NULL &&
1557 state->length < state->head->comm_max)
1558 state->head->comment[state->length++] = len;
1559 } while (len && copy < have);
1560 if (state->flags & 0x0200)
1561 state->check = crc32(state->check, next, copy);
1564 if (len) goto inf_leave;
1566 else if (state->head != Z_NULL)
1567 state->head->comment = Z_NULL;
1570 if (state->flags & 0x0200) {
1572 if (hold != (state->check & 0xffff)) {
1573 strm->msg = (char *)"header crc mismatch";
1579 if (state->head != Z_NULL) {
1580 state->head->hcrc = (int)((state->flags >> 9) & 1);
1581 state->head->done = 1;
1583 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1589 strm->adler = state->check = REVERSE(hold);
1593 if (state->havedict == 0) {
1597 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1600 if (flush == Z_BLOCK) goto inf_leave;
1604 state->mode = CHECK;
1608 state->last = BITS(1);
1611 case 0: /* stored block */
1612 Tracev((stderr, "inflate: stored block%s\n",
1613 state->last ? " (last)" : ""));
1614 state->mode = STORED;
1616 case 1: /* fixed block */
1618 Tracev((stderr, "inflate: fixed codes block%s\n",
1619 state->last ? " (last)" : ""));
1620 state->mode = LEN; /* decode codes */
1622 case 2: /* dynamic block */
1623 Tracev((stderr, "inflate: dynamic codes block%s\n",
1624 state->last ? " (last)" : ""));
1625 state->mode = TABLE;
1628 strm->msg = (char *)"invalid block type";
1634 BYTEBITS(); /* go to byte boundary */
1636 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1637 strm->msg = (char *)"invalid stored block lengths";
1641 state->length = (unsigned)hold & 0xffff;
1642 Tracev((stderr, "inflate: stored length %u\n",
1647 copy = state->length;
1649 if (copy > have) copy = have;
1650 if (copy > left) copy = left;
1651 if (copy == 0) goto inf_leave;
1652 zmemcpy(put, next, copy);
1657 state->length -= copy;
1660 Tracev((stderr, "inflate: stored end\n"));
1665 state->nlen = BITS(5) + 257;
1667 state->ndist = BITS(5) + 1;
1669 state->ncode = BITS(4) + 4;
1671 #ifndef PKZIP_BUG_WORKAROUND
1672 if (state->nlen > 286 || state->ndist > 30) {
1673 strm->msg = (char *)"too many length or distance symbols";
1678 Tracev((stderr, "inflate: table sizes ok\n"));
1680 state->mode = LENLENS;
1682 while (state->have < state->ncode) {
1684 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1687 while (state->have < 19)
1688 state->lens[order[state->have++]] = 0;
1689 state->next = state->codes;
1690 state->lencode = (code const FAR *)(state->next);
1692 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1693 &(state->lenbits), state->work);
1695 strm->msg = (char *)"invalid code lengths set";
1699 Tracev((stderr, "inflate: code lengths ok\n"));
1701 state->mode = CODELENS;
1703 while (state->have < state->nlen + state->ndist) {
1705 this = state->lencode[BITS(state->lenbits)];
1706 if ((unsigned)(this.bits) <= bits) break;
1709 if (this.val < 16) {
1710 NEEDBITS(this.bits);
1711 DROPBITS(this.bits);
1712 state->lens[state->have++] = this.val;
1715 if (this.val == 16) {
1716 NEEDBITS(this.bits + 2);
1717 DROPBITS(this.bits);
1718 if (state->have == 0) {
1719 strm->msg = (char *)"invalid bit length repeat";
1723 len = state->lens[state->have - 1];
1727 else if (this.val == 17) {
1728 NEEDBITS(this.bits + 3);
1729 DROPBITS(this.bits);
1735 NEEDBITS(this.bits + 7);
1736 DROPBITS(this.bits);
1738 copy = 11 + BITS(7);
1741 if (state->have + copy > state->nlen + state->ndist) {
1742 strm->msg = (char *)"invalid bit length repeat";
1747 state->lens[state->have++] = (unsigned short)len;
1751 /* handle error breaks in while */
1752 if (state->mode == BAD) break;
1754 /* build code tables */
1755 state->next = state->codes;
1756 state->lencode = (code const FAR *)(state->next);
1758 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1759 &(state->lenbits), state->work);
1761 strm->msg = (char *)"invalid literal/lengths set";
1765 state->distcode = (code const FAR *)(state->next);
1766 state->distbits = 6;
1767 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1768 &(state->next), &(state->distbits), state->work);
1770 strm->msg = (char *)"invalid distances set";
1774 Tracev((stderr, "inflate: codes ok\n"));
1777 if (strm->outcb != Z_NULL) /* for watchdog (U-Boot) */
1778 (*strm->outcb)(Z_NULL, 0);
1779 if (have >= 6 && left >= 258) {
1781 inflate_fast(strm, out);
1786 this = state->lencode[BITS(state->lenbits)];
1787 if ((unsigned)(this.bits) <= bits) break;
1790 if (this.op && (this.op & 0xf0) == 0) {
1793 this = state->lencode[last.val +
1794 (BITS(last.bits + last.op) >> last.bits)];
1795 if ((unsigned)(last.bits + this.bits) <= bits) break;
1798 DROPBITS(last.bits);
1800 DROPBITS(this.bits);
1801 state->length = (unsigned)this.val;
1802 if ((int)(this.op) == 0) {
1803 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1804 "inflate: literal '%c'\n" :
1805 "inflate: literal 0x%02x\n", this.val));
1810 Tracevv((stderr, "inflate: end of block\n"));
1815 strm->msg = (char *)"invalid literal/length code";
1819 state->extra = (unsigned)(this.op) & 15;
1820 state->mode = LENEXT;
1823 NEEDBITS(state->extra);
1824 state->length += BITS(state->extra);
1825 DROPBITS(state->extra);
1827 Tracevv((stderr, "inflate: length %u\n", state->length));
1831 this = state->distcode[BITS(state->distbits)];
1832 if ((unsigned)(this.bits) <= bits) break;
1835 if ((this.op & 0xf0) == 0) {
1838 this = state->distcode[last.val +
1839 (BITS(last.bits + last.op) >> last.bits)];
1840 if ((unsigned)(last.bits + this.bits) <= bits) break;
1843 DROPBITS(last.bits);
1845 DROPBITS(this.bits);
1847 strm->msg = (char *)"invalid distance code";
1851 state->offset = (unsigned)this.val;
1852 state->extra = (unsigned)(this.op) & 15;
1853 state->mode = DISTEXT;
1856 NEEDBITS(state->extra);
1857 state->offset += BITS(state->extra);
1858 DROPBITS(state->extra);
1860 #ifdef INFLATE_STRICT
1861 if (state->offset > state->dmax) {
1862 strm->msg = (char *)"invalid distance too far back";
1867 if (state->offset > state->whave + out - left) {
1868 strm->msg = (char *)"invalid distance too far back";
1872 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1873 state->mode = MATCH;
1875 if (left == 0) goto inf_leave;
1877 if (state->offset > copy) { /* copy from window */
1878 copy = state->offset - copy;
1879 if (copy > state->write) {
1880 copy -= state->write;
1881 from = state->window + (state->wsize - copy);
1884 from = state->window + (state->write - copy);
1885 if (copy > state->length) copy = state->length;
1887 else { /* copy from output */
1888 from = put - state->offset;
1889 copy = state->length;
1891 if (copy > left) copy = left;
1893 state->length -= copy;
1897 if (state->length == 0) state->mode = LEN;
1900 if (left == 0) goto inf_leave;
1901 *put++ = (unsigned char)(state->length);
1909 strm->total_out += out;
1910 state->total += out;
1912 strm->adler = state->check =
1913 UPDATE(state->check, put - out, out);
1917 state->flags ? hold :
1919 REVERSE(hold)) != state->check) {
1920 strm->msg = (char *)"incorrect data check";
1925 Tracev((stderr, "inflate: check matches trailer\n"));
1928 state->mode = LENGTH;
1930 if (state->wrap && state->flags) {
1932 if (hold != (state->total & 0xffffffffUL)) {
1933 strm->msg = (char *)"incorrect length check";
1938 Tracev((stderr, "inflate: length matches trailer\n"));
1952 return Z_STREAM_ERROR;
1956 Return from inflate(), updating the total counts and the check value.
1957 If there was no progress during the inflate() call, return a buffer
1958 error. Call updatewindow() to create and/or update the window state.
1959 Note: a memory error from inflate() is non-recoverable.
1963 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1964 if (updatewindow(strm, out)) {
1968 in -= strm->avail_in;
1969 out -= strm->avail_out;
1970 strm->total_in += in;
1971 strm->total_out += out;
1972 state->total += out;
1973 if (state->wrap && out)
1974 strm->adler = state->check =
1975 UPDATE(state->check, strm->next_out - out, out);
1976 strm->data_type = state->bits + (state->last ? 64 : 0) +
1977 (state->mode == TYPE ? 128 : 0);
1978 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1983 int ZEXPORT inflateEnd(strm)
1986 struct inflate_state FAR *state;
1987 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1988 return Z_STREAM_ERROR;
1989 state = (struct inflate_state FAR *)strm->state;
1990 if (state->window != Z_NULL) {
1991 if (strm->outcb != Z_NULL)
1992 (*strm->outcb)(Z_NULL, 0);
1993 ZFREE(strm, state->window);
1995 ZFREE(strm, strm->state);
1996 strm->state = Z_NULL;
1997 Tracev((stderr, "inflate: end\n"));
2002 /* zutil.c -- target dependent utility functions for the compression library
2003 * Copyright (C) 1995-2005 Jean-loup Gailly.
2004 * For conditions of distribution and use, see copyright notice in zlib.h
2009 #ifndef NO_DUMMY_DECL
2010 struct internal_state {int dummy;}; /* for buggy compilers */
2013 const char * const z_errmsg[10] = {
2014 "need dictionary", /* Z_NEED_DICT 2 */
2015 "stream end", /* Z_STREAM_END 1 */
2017 "file error", /* Z_ERRNO (-1) */
2018 "stream error", /* Z_STREAM_ERROR (-2) */
2019 "data error", /* Z_DATA_ERROR (-3) */
2020 "insufficient memory", /* Z_MEM_ERROR (-4) */
2021 "buffer error", /* Z_BUF_ERROR (-5) */
2022 "incompatible version",/* Z_VERSION_ERROR (-6) */
2030 int z_verbose = verbose;
2035 fprintf(stderr, "%s\n", m);
2040 /* exported to allow conversion of error code to string for compress() and
2043 #ifndef MY_ZCALLOC /* Any system without a special alloc function */
2046 extern voidp malloc OF((uInt size));
2047 extern voidp calloc OF((uInt items, uInt size));
2048 extern void free OF((voidpf ptr));
2051 voidpf zcalloc (opaque, items, size)
2057 items += size - size; /* make compiler happy */
2058 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2059 (voidpf)calloc(items, size);
2062 void zcfree (opaque, ptr, nb)
2069 return; /* make compiler happy */
2072 #endif /* MY_ZCALLOC */
2074 /* adler32.c -- compute the Adler-32 checksum of a data stream
2075 * Copyright (C) 1995-2004 Mark Adler
2076 * For conditions of distribution and use, see copyright notice in zlib.h
2081 #define BASE 65521UL /* largest prime smaller than 65536 */
2083 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2085 #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2086 #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2087 #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2088 #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2089 #define DO16(buf) DO8(buf,0); DO8(buf,8);
2091 /* use NO_DIVIDE if your processor does not do division in hardware */
2095 if (a >= (BASE << 16)) \
2096 a -= (BASE << 16); \
2097 if (a >= (BASE << 15)) \
2098 a -= (BASE << 15); \
2099 if (a >= (BASE << 14)) \
2100 a -= (BASE << 14); \
2101 if (a >= (BASE << 13)) \
2102 a -= (BASE << 13); \
2103 if (a >= (BASE << 12)) \
2104 a -= (BASE << 12); \
2105 if (a >= (BASE << 11)) \
2106 a -= (BASE << 11); \
2107 if (a >= (BASE << 10)) \
2108 a -= (BASE << 10); \
2109 if (a >= (BASE << 9)) \
2111 if (a >= (BASE << 8)) \
2113 if (a >= (BASE << 7)) \
2115 if (a >= (BASE << 6)) \
2117 if (a >= (BASE << 5)) \
2119 if (a >= (BASE << 4)) \
2121 if (a >= (BASE << 3)) \
2123 if (a >= (BASE << 2)) \
2125 if (a >= (BASE << 1)) \
2132 if (a >= (BASE << 4)) \
2134 if (a >= (BASE << 3)) \
2136 if (a >= (BASE << 2)) \
2138 if (a >= (BASE << 1)) \
2144 #define MOD(a) a %= BASE
2145 #define MOD4(a) a %= BASE
2148 /* ========================================================================= */
2149 uLong ZEXPORT adler32(adler, buf, len)
2157 /* split Adler-32 into component sums */
2158 sum2 = (adler >> 16) & 0xffff;
2161 /* in case user likes doing a byte at a time, keep it fast */
2169 return adler | (sum2 << 16);
2172 /* initial Adler-32 value (deferred check for len == 1 speed) */
2176 /* in case short lengths are provided, keep it somewhat fast */
2184 MOD4(sum2); /* only added so many BASE's */
2185 return adler | (sum2 << 16);
2188 /* do length NMAX blocks -- requires just one modulo operation */
2189 while (len >= NMAX) {
2191 n = NMAX / 16; /* NMAX is divisible by 16 */
2193 DO16(buf); /* 16 sums unrolled */
2200 /* do remaining bytes (less than NMAX, still just one modulo) */
2201 if (len) { /* avoid modulos if none remaining */
2215 /* return recombined sums */
2216 return adler | (sum2 << 16);