]> git.ipfire.org Git - people/ms/u-boot.git/blame - lib_generic/zlib.c
projects / people / ms / u-boot.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
mxc_nand: Remove Freescale's "All Rights Reserved."
[people/ms/u-boot.git] / lib_generic / zlib.c
CommitLineData
4a5b6a35 1/*
dce3d797 2 * This file is derived from various .h and .c files from the zlib-1.2.3
4a5b6a35
WD		 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.
7 *
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
13 */
14
15/*+++++*/
16/* zutil.h -- internal interface and configuration of the compression library
dce3d797 17 * Copyright (C) 1995-2005 Jean-loup Gailly.
4a5b6a35
WD		 18 * For conditions of distribution and use, see copyright notice in zlib.h
19 */
20
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.
24 */
25
dce3d797
GC		 26#define ZUTIL_H
27#define ZLIB_INTERNAL
4a5b6a35 28
a31e091a 29#include "u-boot/zlib.h"
dce3d797
GC		 30/* To avoid a build time warning */
31#ifdef STDC
32#include <malloc.h>
33#endif
4a5b6a35
WD		 34
35#ifndef local
dce3d797 36#define local static
4a5b6a35
WD		 37#endif
38/* compile with -Dlocal if your debugger can't find static symbols */
39
dce3d797 40typedef unsigned char uch;
4a5b6a35
WD		 41typedef uch FAR uchf;
42typedef unsigned short ush;
43typedef ush FAR ushf;
dce3d797 44typedef unsigned long ulg;
f33b325a 45
dce3d797
GC		 46#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
47#define ERR_RETURN(strm,err) return (strm->msg = (char*)ERR_MSG(err), (err))
4a5b6a35
WD		 48/* To be used only when the state is known to be valid */
49
50#ifndef NULL
51#define NULL ((void *) 0)
52#endif
53
8bde7f77 54 /* common constants */
4a5b6a35 55
4a5b6a35 56#ifndef DEF_WBITS
dce3d797 57#define DEF_WBITS MAX_WBITS
4a5b6a35
WD		 58#endif
59/* default windowBits for decompression. MAX_WBITS is for compression only */
60
61#if MAX_MEM_LEVEL >= 8
dce3d797 62#define DEF_MEM_LEVEL 8
4a5b6a35 63#else
dce3d797 64#define DEF_MEM_LEVEL MAX_MEM_LEVEL
4a5b6a35
WD		 65#endif
66/* default memLevel */
67
68#define STORED_BLOCK 0
69#define STATIC_TREES 1
70#define DYN_TREES 2
71/* The three kinds of block type */
72
dce3d797
GC		 73#define MIN_MATCH 3
74#define MAX_MATCH 258
4a5b6a35
WD		 75/* The minimum and maximum match lengths */
76
8bde7f77 77 /* functions */
4a5b6a35
WD		 78
79#include <linux/string.h>
80#define zmemcpy memcpy
dce3d797
GC		 81#define zmemcmp memcmp
82#define zmemzero(dest, len) memset(dest, 0, len)
4a5b6a35
WD		 83
84/* Diagnostic functions */
dce3d797
GC		 85#ifdef DEBUG
86#include <stdio.h>
87 extern int z_verbose;
88 extern void z_error OF((char *m));
89#define Assert(cond,msg) {if(!(cond)) z_error(msg);}
90#define Trace(x) {if (z_verbose>=0) fprintf x ;}
91#define Tracev(x) {if (z_verbose>0) fprintf x ;}
92#define Tracevv(x) {if (z_verbose>1) fprintf x ;}
93#define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
94#define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
4a5b6a35 95#else
dce3d797
GC		 96#define Assert(cond,msg)
97#define Trace(x)
98#define Tracev(x)
99#define Tracevv(x)
100#define Tracec(c,x)
101#define Tracecv(c,x)
4a5b6a35
WD		 102#endif
103
dce3d797
GC		 104voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
105void zcfree OF((voidpf opaque, voidpf ptr, unsigned size));
4a5b6a35
WD		 106
107#define ZALLOC(strm, items, size) \
dce3d797
GC		 108 (*((strm)->zalloc))((strm)->opaque, (items), (size))
109#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), 0)
4a5b6a35 110
dce3d797
GC		 111/*+++++*/
112/* inftrees.h -- header to use inftrees.c
113 * Copyright (C) 1995-2005 Mark Adler
4a5b6a35
WD		 114 * For conditions of distribution and use, see copyright notice in zlib.h
115 */
116
117/* WARNING: this file should *not* be used by applications. It is
118 part of the implementation of the compression library and is
119 subject to change. Applications should only use zlib.h.
120 */
121
dce3d797
GC		 122/* Structure for decoding tables. Each entry provides either the
123 information needed to do the operation requested by the code that
124 indexed that table entry, or it provides a pointer to another
125 table that indexes more bits of the code. op indicates whether
126 the entry is a pointer to another table, a literal, a length or
127 distance, an end-of-block, or an invalid code. For a table
128 pointer, the low four bits of op is the number of index bits of
129 that table. For a length or distance, the low four bits of op
130 is the number of extra bits to get after the code. bits is
131 the number of bits in this code or part of the code to drop off
132 of the bit buffer. val is the actual byte to output in the case
133 of a literal, the base length or distance, or the offset from
134 the current table to the next table. Each entry is four bytes. */
135
136typedef struct {
137 unsigned char op; /* operation, extra bits, table bits */
138 unsigned char bits; /* bits in this part of the code */
139 unsigned short val; /* offset in table or code value */
140} code;
141
142/* Maximum size of dynamic tree. The maximum found in a long but non-
143 exhaustive search was 1444 code structures (852 for length/literals
144 and 592 for distances, the latter actually the result of an
145 exhaustive search). The true maximum is not known, but the value
146 below is more than safe. */
147#define ENOUGH 2048
148#define MAXD 592
149
150/* Type of code to build for inftable() */
151typedef enum {
152 CODES,
153 LENS,
154 DISTS
155} codetype;
156
157extern int inflate_table OF((codetype type, unsigned short FAR *lens,
158 unsigned codes, code FAR * FAR *table,
159 unsigned FAR *bits, unsigned short FAR *work));
4a5b6a35 160/*+++++*/
dce3d797
GC		 161/* inflate.h -- internal inflate state definition
162 * Copyright (C) 1995-2004 Mark Adler
4a5b6a35
WD		 163 * For conditions of distribution and use, see copyright notice in zlib.h
164 */
165
166/* WARNING: this file should *not* be used by applications. It is
167 part of the implementation of the compression library and is
168 subject to change. Applications should only use zlib.h.
169 */
170
dce3d797
GC		 171#define GUNZIP
172
173/* Possible inflate modes between inflate() calls */
174typedef enum {
175 HEAD, /* i: waiting for magic header */
176 FLAGS, /* i: waiting for method and flags (gzip) */
177 TIME, /* i: waiting for modification time (gzip) */
178 OS, /* i: waiting for extra flags and operating system (gzip) */
179 EXLEN, /* i: waiting for extra length (gzip) */
180 EXTRA, /* i: waiting for extra bytes (gzip) */
181 NAME, /* i: waiting for end of file name (gzip) */
182 COMMENT, /* i: waiting for end of comment (gzip) */
183 HCRC, /* i: waiting for header crc (gzip) */
184 DICTID, /* i: waiting for dictionary check value */
185 DICT, /* waiting for inflateSetDictionary() call */
186 TYPE, /* i: waiting for type bits, including last-flag bit */
187 TYPEDO, /* i: same, but skip check to exit inflate on new block */
188 STORED, /* i: waiting for stored size (length and complement) */
189 COPY, /* i/o: waiting for input or output to copy stored block */
190 TABLE, /* i: waiting for dynamic block table lengths */
191 LENLENS, /* i: waiting for code length code lengths */
192 CODELENS, /* i: waiting for length/lit and distance code lengths */
193 LEN, /* i: waiting for length/lit code */
194 LENEXT, /* i: waiting for length extra bits */
195 DIST, /* i: waiting for distance code */
196 DISTEXT, /* i: waiting for distance extra bits */
197 MATCH, /* o: waiting for output space to copy string */
198 LIT, /* o: waiting for output space to write literal */
199 CHECK, /* i: waiting for 32-bit check value */
200 LENGTH, /* i: waiting for 32-bit length (gzip) */
201 DONE, /* finished check, done -- remain here until reset */
202 BAD, /* got a data error -- remain here until reset */
203 MEM, /* got an inflate() memory error -- remain here until reset */
204 SYNC, /* looking for synchronization bytes to restart inflate() */
205 START,
206 WASH,
207 END,
208 BADCODE
209} inflate_mode;
f33b325a 210
dce3d797
GC		 211/*
212 State transitions between above modes -
213
214 (most modes can go to the BAD or MEM mode -- not shown for clarity)
215
216 Process header:
217 HEAD -> (gzip) or (zlib)
218 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
219 NAME -> COMMENT -> HCRC -> TYPE
220 (zlib) -> DICTID or TYPE
221 DICTID -> DICT -> TYPE
222 Read deflate blocks:
223 TYPE -> STORED or TABLE or LEN or CHECK
224 STORED -> COPY -> TYPE
225 TABLE -> LENLENS -> CODELENS -> LEN
226 Read deflate codes:
227 LEN -> LENEXT or LIT or TYPE
228 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
229 LIT -> LEN
230 Process trailer:
231 CHECK -> LENGTH -> DONE
f33b325a
WD		 232 */
233
dce3d797
GC		 234/* state maintained between inflate() calls. Approximately 7K bytes. */
235struct inflate_state {
236 inflate_mode mode; /* current inflate mode */
237 int last; /* true if processing last block */
238 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
239 int havedict; /* true if dictionary provided */
240 int flags; /* gzip header method and flags (0 if zlib) */
241 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
242 unsigned long check; /* protected copy of check value */
243 unsigned long total; /* protected copy of output count */
244 gz_headerp head; /* where to save gzip header information */
245 /* sliding window */
246 unsigned wbits; /* log base 2 of requested window size */
247 unsigned wsize; /* window size or zero if not using window */
248 unsigned whave; /* valid bytes in the window */
249 unsigned write; /* window write index */
250 unsigned char FAR *window; /* allocated sliding window, if needed */
251 /* bit accumulator */
252 unsigned long hold; /* input bit accumulator */
253 unsigned bits; /* number of bits in "in" */
254 /* for string and stored block copying */
255 unsigned length; /* literal or length of data to copy */
256 unsigned offset; /* distance back to copy string from */
257 /* for table and code decoding */
258 unsigned extra; /* extra bits needed */
259 /* fixed and dynamic code tables */
260 code const FAR *lencode; /* starting table for length/literal codes */
261 code const FAR *distcode; /* starting table for distance codes */
262 unsigned lenbits; /* index bits for lencode */
263 unsigned distbits; /* index bits for distcode */
264 /* dynamic table building */
265 unsigned ncode; /* number of code length code lengths */
266 unsigned nlen; /* number of length code lengths */
267 unsigned ndist; /* number of distance code lengths */
268 unsigned have; /* number of code lengths in lens[] */
269 code FAR *next; /* next available space in codes[] */
270 unsigned short lens[320]; /* temporary storage for code lengths */
271 unsigned short work[288]; /* work area for code table building */
272 code codes[ENOUGH]; /* space for code tables */
4a5b6a35
WD		 273};
274
4a5b6a35 275/*+++++*/
dce3d797
GC		 276/* inffast.h -- header to use inffast.c
277 * Copyright (C) 1995-2003 Mark Adler
4a5b6a35
WD		 278 * For conditions of distribution and use, see copyright notice in zlib.h
279 */
280
281/* WARNING: this file should *not* be used by applications. It is
282 part of the implementation of the compression library and is
283 subject to change. Applications should only use zlib.h.
284 */
285
dce3d797
GC		 286void inflate_fast OF((z_streamp strm, unsigned start));
287/*+++++*/
288 /* inffixed.h -- table for decoding fixed codes
289 * Generated automatically by makefixed().
290 */
f33b325a 291
dce3d797
GC		 292 /* WARNING: this file should *not* be used by applications. It
293 is part of the implementation of the compression library and
294 is subject to change. Applications should only use zlib.h.
295 */
4a5b6a35 296
dce3d797
GC		 297 static const code lenfix[512] = {
298 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
299 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
300 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
301 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
302 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
303 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
304 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
305 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
306 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
307 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
308 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
309 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
310 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
311 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
312 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
313 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
314 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
315 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
316 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
317 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
318 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
319 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
320 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
321 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
322 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
323 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
324 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
325 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
326 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
327 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
328 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
329 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
330 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
331 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
332 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
333 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
334 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
335 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
336 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
337 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
338 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
339 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
340 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
341 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
342 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
343 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
344 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
345 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
346 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
347 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
348 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
349 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
350 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
351 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
352 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
353 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
354 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
355 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
356 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
357 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
358 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
359 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
360 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
361 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
362 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
363 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
364 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
365 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
366 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
367 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
368 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
369 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
370 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
371 {0,9,255}
372 };
373
374 static const code distfix[32] = {
375 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
376 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
377 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
378 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
379 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
380 {22,5,193},{64,5,0}
381 };
4a5b6a35
WD		 382
383/*+++++*/
dce3d797
GC		 384/* inffast.c -- fast decoding
385 * Copyright (C) 1995-2004 Mark Adler
4a5b6a35
WD		 386 * For conditions of distribution and use, see copyright notice in zlib.h
387 */
388
dce3d797
GC		 389/* Allow machine dependent optimization for post-increment or pre-increment.
390 Based on testing to date,
391 Pre-increment preferred for:
392 - PowerPC G3 (Adler)
393 - MIPS R5000 (Randers-Pehrson)
394 Post-increment preferred for:
395 - none
396 No measurable difference:
397 - Pentium III (Anderson)
398 - M68060 (Nikl)
399 */
400#define OFF 1
401#define PUP(a) *++(a)
4a5b6a35
WD		 402
403/*
dce3d797
GC		 404 Decode literal, length, and distance codes and write out the resulting
405 literal and match bytes until either not enough input or output is
406 available, an end-of-block is encountered, or a data error is encountered.
407 When large enough input and output buffers are supplied to inflate(), for
408 example, a 16K input buffer and a 64K output buffer, more than 95% of the
409 inflate execution time is spent in this routine.
410
411 Entry assumptions:
412
413 state->mode == LEN
414 strm->avail_in >= 6
415 strm->avail_out >= 258
416 start >= strm->avail_out
417 state->bits < 8
418
419 On return, state->mode is one of:
420
421 LEN -- ran out of enough output space or enough available input
422 TYPE -- reached end of block code, inflate() to interpret next block
423 BAD -- error in block data
424
425 Notes:
426
427 - The maximum input bits used by a length/distance pair is 15 bits for the
428 length code, 5 bits for the length extra, 15 bits for the distance code,
429 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
430 Therefore if strm->avail_in >= 6, then there is enough input to avoid
431 checking for available input while decoding.
432
433 - The maximum bytes that a single length/distance pair can output is 258
434 bytes, which is the maximum length that can be coded. inflate_fast()
435 requires strm->avail_out >= 258 for each loop to avoid checking for
436 output space.
4a5b6a35 437 */
dce3d797
GC		 438void inflate_fast(strm, start)
439z_streamp strm;
440unsigned start; /* inflate()'s starting value for strm->avail_out */
4a5b6a35 441{
dce3d797
GC		 442 struct inflate_state FAR *state;
443 unsigned char FAR *in; /* local strm->next_in */
444 unsigned char FAR *last; /* while in < last, enough input available */
445 unsigned char FAR *out; /* local strm->next_out */
446 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
447 unsigned char FAR *end; /* while out < end, enough space available */
448#ifdef INFLATE_STRICT
449 unsigned dmax; /* maximum distance from zlib header */
450#endif
451 unsigned wsize; /* window size or zero if not using window */
452 unsigned whave; /* valid bytes in the window */
453 unsigned write; /* window write index */
454 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
455 unsigned long hold; /* local strm->hold */
456 unsigned bits; /* local strm->bits */
457 code const FAR *lcode; /* local strm->lencode */
458 code const FAR *dcode; /* local strm->distcode */
459 unsigned lmask; /* mask for first level of length codes */
460 unsigned dmask; /* mask for first level of distance codes */
461 code this; /* retrieved table entry */
462 unsigned op; /* code bits, operation, extra bits, or */
463 /* window position, window bytes to copy */
464 unsigned len; /* match length, unused bytes */
465 unsigned dist; /* match distance */
466 unsigned char FAR *from; /* where to copy match from */
467
468 /* copy state to local variables */
469 state = (struct inflate_state FAR *)strm->state;
470 in = strm->next_in - OFF;
471 last = in + (strm->avail_in - 5);
472 out = strm->next_out - OFF;
473 beg = out - (start - strm->avail_out);
474 end = out + (strm->avail_out - 257);
475#ifdef INFLATE_STRICT
476 dmax = state->dmax;
477#endif
478 wsize = state->wsize;
479 whave = state->whave;
480 write = state->write;
481 window = state->window;
482 hold = state->hold;
483 bits = state->bits;
484 lcode = state->lencode;
485 dcode = state->distcode;
486 lmask = (1U << state->lenbits) - 1;
487 dmask = (1U << state->distbits) - 1;
488
489 /* decode literals and length/distances until end-of-block or not enough
490 input data or output space */
491 do {
492 if (bits < 15) {
493 hold += (unsigned long)(PUP(in)) << bits;
494 bits += 8;
495 hold += (unsigned long)(PUP(in)) << bits;
496 bits += 8;
497 }
498 this = lcode[hold & lmask];
499 dolen:
500 op = (unsigned)(this.bits);
501 hold >>= op;
502 bits -= op;
503 op = (unsigned)(this.op);
504 if (op == 0) { /* literal */
505 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
506 "inflate: literal '%c'\n" :
507 "inflate: literal 0x%02x\n", this.val));
508 PUP(out) = (unsigned char)(this.val);
509 }
510 else if (op & 16) { /* length base */
511 len = (unsigned)(this.val);
512 op &= 15; /* number of extra bits */
513 if (op) {
514 if (bits < op) {
515 hold += (unsigned long)(PUP(in)) << bits;
516 bits += 8;
517 }
518 len += (unsigned)hold & ((1U << op) - 1);
519 hold >>= op;
520 bits -= op;
521 }
522 Tracevv((stderr, "inflate: length %u\n", len));
523 if (bits < 15) {
524 hold += (unsigned long)(PUP(in)) << bits;
525 bits += 8;
526 hold += (unsigned long)(PUP(in)) << bits;
527 bits += 8;
528 }
529 this = dcode[hold & dmask];
530 dodist:
531 op = (unsigned)(this.bits);
532 hold >>= op;
533 bits -= op;
534 op = (unsigned)(this.op);
535 if (op & 16) { /* distance base */
536 dist = (unsigned)(this.val);
537 op &= 15; /* number of extra bits */
538 if (bits < op) {
539 hold += (unsigned long)(PUP(in)) << bits;
540 bits += 8;
541 if (bits < op) {
542 hold += (unsigned long)(PUP(in)) << bits;
543 bits += 8;
544 }
545 }
546 dist += (unsigned)hold & ((1U << op) - 1);
547#ifdef INFLATE_STRICT
548 if (dist > dmax) {
549 strm->msg = (char *)"invalid distance too far back";
550 state->mode = BAD;
551 break;
552 }
553#endif
554 hold >>= op;
555 bits -= op;
556 Tracevv((stderr, "inflate: distance %u\n", dist));
557 op = (unsigned)(out - beg); /* max distance in output */
558 if (dist > op) { /* see if copy from window */
559 op = dist - op; /* distance back in window */
560 if (op > whave) {
561 strm->msg = (char *)"invalid distance too far back";
562 state->mode = BAD;
563 break;
564 }
565 from = window - OFF;
566 if (write == 0) { /* very common case */
567 from += wsize - op;
568 if (op < len) { /* some from window */
569 len -= op;
570 do {
571 PUP(out) = PUP(from);
572 } while (--op);
573 from = out - dist; /* rest from output */
574 }
575 }
576 else if (write < op) { /* wrap around window */
577 from += wsize + write - op;
578 op -= write;
579 if (op < len) { /* some from end of window */
580 len -= op;
581 do {
582 PUP(out) = PUP(from);
583 } while (--op);
584 from = window - OFF;
585 if (write < len) { /* some from start of window */
586 op = write;
587 len -= op;
588 do {
589 PUP(out) = PUP(from);
590 } while (--op);
591 from = out - dist; /* rest from output */
592 }
593 }
594 }
595 else { /* contiguous in window */
596 from += write - op;
597 if (op < len) { /* some from window */
598 len -= op;
599 do {
600 PUP(out) = PUP(from);
601 } while (--op);
602 from = out - dist; /* rest from output */
603 }
604 }
605 while (len > 2) {
606 PUP(out) = PUP(from);
607 PUP(out) = PUP(from);
608 PUP(out) = PUP(from);
609 len -= 3;
610 }
611 if (len) {
612 PUP(out) = PUP(from);
613 if (len > 1)
614 PUP(out) = PUP(from);
615 }
616 }
617 else {
618 from = out - dist; /* copy direct from output */
619 do { /* minimum length is three */
620 PUP(out) = PUP(from);
621 PUP(out) = PUP(from);
622 PUP(out) = PUP(from);
623 len -= 3;
624 } while (len > 2);
625 if (len) {
626 PUP(out) = PUP(from);
627 if (len > 1)
628 PUP(out) = PUP(from);
629 }
630 }
631 }
632 else if ((op & 64) == 0) { /* 2nd level distance code */
633 this = dcode[this.val + (hold & ((1U << op) - 1))];
634 goto dodist;
635 }
636 else {
637 strm->msg = (char *)"invalid distance code";
638 state->mode = BAD;
639 break;
640 }
641 }
642 else if ((op & 64) == 0) { /* 2nd level length code */
643 this = lcode[this.val + (hold & ((1U << op) - 1))];
644 goto dolen;
645 }
646 else if (op & 32) { /* end-of-block */
647 Tracevv((stderr, "inflate: end of block\n"));
648 state->mode = TYPE;
649 break;
650 }
651 else {
652 strm->msg = (char *)"invalid literal/length code";
653 state->mode = BAD;
654 break;
655 }
656 } while (in < last && out < end);
657
658 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
659 len = bits >> 3;
660 in -= len;
661 bits -= len << 3;
662 hold &= (1U << bits) - 1;
663
664 /* update state and return */
665 strm->next_in = in + OFF;
666 strm->next_out = out + OFF;
667 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
668 strm->avail_out = (unsigned)(out < end ?
669 257 + (end - out) : 257 - (out - end));
670 state->hold = hold;
671 state->bits = bits;
672 return;
4a5b6a35
WD		 673}
674
4a5b6a35 675/*
dce3d797
GC		 676 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
677 - Using bit fields for code structure
678 - Different op definition to avoid & for extra bits (do & for table bits)
679 - Three separate decoding do-loops for direct, window, and write == 0
680 - Special case for distance > 1 copies to do overlapped load and store copy
681 - Explicit branch predictions (based on measured branch probabilities)
682 - Deferring match copy and interspersed it with decoding subsequent codes
683 - Swapping literal/length else
684 - Swapping window/direct else
685 - Larger unrolled copy loops (three is about right)
686 - Moving len -= 3 statement into middle of loop
4a5b6a35 687 */
4a5b6a35
WD		 688
689/*+++++*/
dce3d797
GC		 690/* inftrees.c -- generate Huffman trees for efficient decoding
691 * Copyright (C) 1995-2005 Mark Adler
4a5b6a35
WD		 692 * For conditions of distribution and use, see copyright notice in zlib.h
693 */
694
dce3d797
GC		 695#define MAXBITS 15
696/*
697 If you use the zlib library in a product, an acknowledgment is welcome
698 in the documentation of your product. If for some reason you cannot
699 include such an acknowledgment, I would appreciate that you keep this
700 copyright string in the executable of your product.
f33b325a
WD		 701 */
702
4a5b6a35 703/*
dce3d797
GC		 704 Build a set of tables to decode the provided canonical Huffman code.
705 The code lengths are lens[0..codes-1]. The result starts at *table,
706 whose indices are 0..2^bits-1. work is a writable array of at least
707 lens shorts, which is used as a work area. type is the type of code
708 to be generated, CODES, LENS, or DISTS. On return, zero is success,
709 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
710 on return points to the next available entry's address. bits is the
711 requested root table index bits, and on return it is the actual root
712 table index bits. It will differ if the request is greater than the
713 longest code or if it is less than the shortest code.
4a5b6a35 714 */
dce3d797
GC		 715int inflate_table(type, lens, codes, table, bits, work)
716codetype type;
717unsigned short FAR *lens;
718unsigned codes;
719code FAR * FAR *table;
720unsigned FAR *bits;
721unsigned short FAR *work;
4a5b6a35 722{
dce3d797
GC		 723 unsigned len; /* a code's length in bits */
724 unsigned sym; /* index of code symbols */
725 unsigned min, max; /* minimum and maximum code lengths */
726 unsigned root; /* number of index bits for root table */
727 unsigned curr; /* number of index bits for current table */
728 unsigned drop; /* code bits to drop for sub-table */
729 int left; /* number of prefix codes available */
730 unsigned used; /* code entries in table used */
731 unsigned huff; /* Huffman code */
732 unsigned incr; /* for incrementing code, index */
733 unsigned fill; /* index for replicating entries */
734 unsigned low; /* low bits for current root entry */
735 unsigned mask; /* mask for low root bits */
736 code this; /* table entry for duplication */
737 code FAR *next; /* next available space in table */
738 const unsigned short FAR *base; /* base value table to use */
739 const unsigned short FAR *extra; /* extra bits table to use */
740 int end; /* use base and extra for symbol > end */
741 unsigned short count[MAXBITS+1]; /* number of codes of each length */
742 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
743 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
744 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
745 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
746 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
747 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
748 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
749 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
750 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
751 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
752 8193, 12289, 16385, 24577, 0, 0};
753 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
754 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
755 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
756 28, 28, 29, 29, 64, 64};
757
758 /*
759 Process a set of code lengths to create a canonical Huffman code. The
760 code lengths are lens[0..codes-1]. Each length corresponds to the
761 symbols 0..codes-1. The Huffman code is generated by first sorting the
762 symbols by length from short to long, and retaining the symbol order
763 for codes with equal lengths. Then the code starts with all zero bits
764 for the first code of the shortest length, and the codes are integer
765 increments for the same length, and zeros are appended as the length
766 increases. For the deflate format, these bits are stored backwards
767 from their more natural integer increment ordering, and so when the
768 decoding tables are built in the large loop below, the integer codes
769 are incremented backwards.
770
771 This routine assumes, but does not check, that all of the entries in
772 lens[] are in the range 0..MAXBITS. The caller must assure this.
773 1..MAXBITS is interpreted as that code length. zero means that that
774 symbol does not occur in this code.
775
776 The codes are sorted by computing a count of codes for each length,
777 creating from that a table of starting indices for each length in the
778 sorted table, and then entering the symbols in order in the sorted
779 table. The sorted table is work[], with that space being provided by
780 the caller.
781
782 The length counts are used for other purposes as well, i.e. finding
783 the minimum and maximum length codes, determining if there are any
784 codes at all, checking for a valid set of lengths, and looking ahead
785 at length counts to determine sub-table sizes when building the
786 decoding tables.
787 */
f33b325a 788
dce3d797
GC		 789 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
790 for (len = 0; len <= MAXBITS; len++)
791 count[len] = 0;
792 for (sym = 0; sym < codes; sym++)
793 count[lens[sym]]++;
794
795 /* bound code lengths, force root to be within code lengths */
796 root = *bits;
797 for (max = MAXBITS; max >= 1; max--)
798 if (count[max] != 0) break;
799 if (root > max) root = max;
800 if (max == 0) { /* no symbols to code at all */
801 this.op = (unsigned char)64; /* invalid code marker */
802 this.bits = (unsigned char)1;
803 this.val = (unsigned short)0;
804 *(*table)++ = this; /* make a table to force an error */
805 *(*table)++ = this;
806 *bits = 1;
807 return 0; /* no symbols, but wait for decoding to report error */
808 }
809 for (min = 1; min <= MAXBITS; min++)
810 if (count[min] != 0) break;
811 if (root < min) root = min;
812
813 /* check for an over-subscribed or incomplete set of lengths */
814 left = 1;
815 for (len = 1; len <= MAXBITS; len++) {
816 left <<= 1;
817 left -= count[len];
818 if (left < 0) return -1; /* over-subscribed */
819 }
820 if (left > 0 && (type == CODES || max != 1))
821 return -1; /* incomplete set */
822
823 /* generate offsets into symbol table for each length for sorting */
824 offs[1] = 0;
825 for (len = 1; len < MAXBITS; len++)
826 offs[len + 1] = offs[len] + count[len];
827
828 /* sort symbols by length, by symbol order within each length */
829 for (sym = 0; sym < codes; sym++)
830 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
831
832 /*
833 Create and fill in decoding tables. In this loop, the table being
834 filled is at next and has curr index bits. The code being used is huff
835 with length len. That code is converted to an index by dropping drop
836 bits off of the bottom. For codes where len is less than drop + curr,
837 those top drop + curr - len bits are incremented through all values to
838 fill the table with replicated entries.
839
840 root is the number of index bits for the root table. When len exceeds
841 root, sub-tables are created pointed to by the root entry with an index
842 of the low root bits of huff. This is saved in low to check for when a
843 new sub-table should be started. drop is zero when the root table is
844 being filled, and drop is root when sub-tables are being filled.
845
846 When a new sub-table is needed, it is necessary to look ahead in the
847 code lengths to determine what size sub-table is needed. The length
848 counts are used for this, and so count[] is decremented as codes are
849 entered in the tables.
850
851 used keeps track of how many table entries have been allocated from the
852 provided *table space. It is checked when a LENS table is being made
853 against the space in *table, ENOUGH, minus the maximum space needed by
854 the worst case distance code, MAXD. This should never happen, but the
855 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
856 This assumes that when type == LENS, bits == 9.
857
858 sym increments through all symbols, and the loop terminates when
859 all codes of length max, i.e. all codes, have been processed. This
860 routine permits incomplete codes, so another loop after this one fills
861 in the rest of the decoding tables with invalid code markers.
862 */
f33b325a 863
dce3d797
GC		 864 /* set up for code type */
865 switch (type) {
f33b325a 866 case CODES:
dce3d797
GC		 867 base = extra = work; /* dummy value--not used */
868 end = 19;
869 break;
870 case LENS:
871 base = lbase;
872 base -= 257;
873 extra = lext;
874 extra -= 257;
875 end = 256;
876 break;
877 default: /* DISTS */
878 base = dbase;
879 extra = dext;
880 end = -1;
881 }
28958b8b 882
dce3d797
GC		 883 /* initialize state for loop */
884 huff = 0; /* starting code */
885 sym = 0; /* starting code symbol */
886 len = min; /* starting code length */
887 next = *table; /* current table to fill in */
888 curr = root; /* current table index bits */
889 drop = 0; /* current bits to drop from code for index */
890 low = (unsigned)(-1); /* trigger new sub-table when len > root */
891 used = 1U << root; /* use root table entries */
892 mask = used - 1; /* mask for comparing low */
893
894 /* check available table space */
895 if (type == LENS && used >= ENOUGH - MAXD)
896 return 1;
897
898 /* process all codes and make table entries */
899 for (;;) {
900 /* create table entry */
901 this.bits = (unsigned char)(len - drop);
902 if ((int)(work[sym]) < end) {
903 this.op = (unsigned char)0;
904 this.val = work[sym];
905 }
906 else if ((int)(work[sym]) > end) {
907 this.op = (unsigned char)(extra[work[sym]]);
908 this.val = base[work[sym]];
909 }
910 else {
911 this.op = (unsigned char)(32 + 64); /* end of block */
912 this.val = 0;
913 }
914
915 /* replicate for those indices with low len bits equal to huff */
916 incr = 1U << (len - drop);
917 fill = 1U << curr;
918 min = fill; /* save offset to next table */
919 do {
920 fill -= incr;
921 next[(huff >> drop) + fill] = this;
922 } while (fill != 0);
923
924 /* backwards increment the len-bit code huff */
925 incr = 1U << (len - 1);
926 while (huff & incr)
927 incr >>= 1;
928 if (incr != 0) {
929 huff &= incr - 1;
930 huff += incr;
931 }
932 else
933 huff = 0;
934
935 /* go to next symbol, update count, len */
936 sym++;
937 if (--(count[len]) == 0) {
938 if (len == max) break;
939 len = lens[work[sym]];
940 }
941
942 /* create new sub-table if needed */
943 if (len > root && (huff & mask) != low) {
944 /* if first time, transition to sub-tables */
945 if (drop == 0)
946 drop = root;
947
948 /* increment past last table */
949 next += min; /* here min is 1 << curr */
950
951 /* determine length of next table */
952 curr = len - drop;
953 left = (int)(1 << curr);
954 while (curr + drop < max) {
955 left -= count[curr + drop];
956 if (left <= 0) break;
957 curr++;
958 left <<= 1;
959 }
960
961 /* check for enough space */
962 used += 1U << curr;
963 if (type == LENS && used >= ENOUGH - MAXD)
964 return 1;
965
966 /* point entry in root table to sub-table */
967 low = huff & mask;
968 (*table)[low].op = (unsigned char)curr;
969 (*table)[low].bits = (unsigned char)root;
970 (*table)[low].val = (unsigned short)(next - *table);
971 }
972 }
28958b8b 973
dce3d797
GC		 974 /*
975 Fill in rest of table for incomplete codes. This loop is similar to the
976 loop above in incrementing huff for table indices. It is assumed that
977 len is equal to curr + drop, so there is no loop needed to increment
978 through high index bits. When the current sub-table is filled, the loop
979 drops back to the root table to fill in any remaining entries there.
4a5b6a35 980 */
dce3d797
GC		 981 this.op = (unsigned char)64; /* invalid code marker */
982 this.bits = (unsigned char)(len - drop);
983 this.val = (unsigned short)0;
984 while (huff != 0) {
985 /* when done with sub-table, drop back to root table */
986 if (drop != 0 && (huff & mask) != low) {
987 drop = 0;
988 len = root;
989 next = *table;
990 this.bits = (unsigned char)len;
991 }
992
993 /* put invalid code marker in table */
994 next[huff >> drop] = this;
995
996 /* backwards increment the len-bit code huff */
997 incr = 1U << (len - 1);
998 while (huff & incr)
999 incr >>= 1;
1000 if (incr != 0) {
1001 huff &= incr - 1;
1002 huff += incr;
1003 }
1004 else
1005 huff = 0;
4a5b6a35 1006 }
4a5b6a35 1007
dce3d797
GC		 1008 /* set return parameters */
1009 *table += used;
1010 *bits = root;
1011 return 0;
4a5b6a35
WD		 1012}
1013
4a5b6a35 1014/*+++++*/
dce3d797
GC		 1015/* inflate.c -- zlib decompression
1016 * Copyright (C) 1995-2005 Mark Adler
4a5b6a35
WD		 1017 * For conditions of distribution and use, see copyright notice in zlib.h
1018 */
dce3d797
GC		 1019local void fixedtables OF((struct inflate_state FAR *state));
1020local int updatewindow OF((z_streamp strm, unsigned out));
4a5b6a35 1021
dce3d797
GC		 1022int ZEXPORT inflateReset(strm)
1023z_streamp strm;
4a5b6a35 1024{
dce3d797
GC		 1025 struct inflate_state FAR *state;
1026
1027 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1028 state = (struct inflate_state FAR *)strm->state;
1029 strm->total_in = strm->total_out = state->total = 0;
1030 strm->msg = Z_NULL;
1031 strm->adler = 1; /* to support ill-conceived Java test suite */
1032 state->mode = HEAD;
1033 state->last = 0;
1034 state->havedict = 0;
1035 state->dmax = 32768U;
1036 state->head = Z_NULL;
1037 state->wsize = 0;
1038 state->whave = 0;
1039 state->write = 0;
1040 state->hold = 0;
1041 state->bits = 0;
1042 state->lencode = state->distcode = state->next = state->codes;
253cb831
GC		 1043 if (strm->outcb != Z_NULL)
1044 (*strm->outcb)(Z_NULL, 0);
dce3d797 1045 Tracev((stderr, "inflate: reset\n"));
f33b325a 1046 return Z_OK;
f33b325a 1047}
4a5b6a35 1048
dce3d797
GC		 1049int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1050z_streamp strm;
1051int windowBits;
1052const char *version;
1053int stream_size;
f33b325a 1054{
dce3d797
GC		 1055 struct inflate_state FAR *state;
1056
1057 if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
1058 stream_size != (int)(sizeof(z_stream)))
1059 return Z_VERSION_ERROR;
1060 if (strm == Z_NULL) return Z_STREAM_ERROR;
1061 strm->msg = Z_NULL; /* in case we return an error */
1062 if (strm->zalloc == (alloc_func)0) {
1063 strm->zalloc = zcalloc;
1064 strm->opaque = (voidpf)0;
b201171f 1065 }
dce3d797
GC		 1066 if (strm->zfree == (free_func)0) strm->zfree = zcfree;
1067 state = (struct inflate_state FAR *)
1068 ZALLOC(strm, 1, sizeof(struct inflate_state));
1069 if (state == Z_NULL) return Z_MEM_ERROR;
1070 Tracev((stderr, "inflate: allocated\n"));
1071 strm->state = (struct internal_state FAR *)state;
1072 if (windowBits < 0) {
1073 state->wrap = 0;
1074 windowBits = -windowBits;
b201171f 1075 }
dce3d797
GC		 1076 else {
1077 state->wrap = (windowBits >> 4) + 1;
1078#ifdef GUNZIP
1079 if (windowBits < 48) windowBits &= 15;
f33b325a 1080#endif
dce3d797
GC		 1081 }
1082 if (windowBits < 8 || windowBits > 15) {
1083 ZFREE(strm, state);
1084 strm->state = Z_NULL;
1085 return Z_STREAM_ERROR;
1086 }
1087 state->wbits = (unsigned)windowBits;
1088 state->window = Z_NULL;
1089 return inflateReset(strm);
f33b325a 1090}
28958b8b 1091
dce3d797
GC		 1092int ZEXPORT inflateInit_(strm, version, stream_size)
1093z_streamp strm;
1094const char *version;
1095int stream_size;
f33b325a 1096{
dce3d797 1097 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
4a5b6a35
WD		 1098}
1099
dce3d797
GC		 1100local void fixedtables(state)
1101struct inflate_state FAR *state;
4a5b6a35 1102{
dce3d797
GC		 1103 state->lencode = lenfix;
1104 state->lenbits = 9;
1105 state->distcode = distfix;
1106 state->distbits = 5;
4a5b6a35
WD		 1107}
1108
dce3d797
GC		 1109/*
1110 Update the window with the last wsize (normally 32K) bytes written before
1111 returning. If window does not exist yet, create it. This is only called
1112 when a window is already in use, or when output has been written during this
1113 inflate call, but the end of the deflate stream has not been reached yet.
1114 It is also called to create a window for dictionary data when a dictionary
1115 is loaded.
1116
1117 Providing output buffers larger than 32K to inflate() should provide a speed
1118 advantage, since only the last 32K of output is copied to the sliding window
1119 upon return from inflate(), and since all distances after the first 32K of
1120 output will fall in the output data, making match copies simpler and faster.
1121 The advantage may be dependent on the size of the processor's data caches.
4a5b6a35 1122 */
dce3d797
GC		 1123local int updatewindow(strm, out)
1124z_streamp strm;
1125unsigned out;
1126{
1127 struct inflate_state FAR *state;
1128 unsigned copy, dist;
4a5b6a35 1129
dce3d797 1130 state = (struct inflate_state FAR *)strm->state;
4a5b6a35 1131
dce3d797
GC		 1132 /* if it hasn't been done already, allocate space for the window */
1133 if (state->window == Z_NULL) {
1134 state->window = (unsigned char FAR *)
1135 ZALLOC(strm, 1U << state->wbits,
1136 sizeof(unsigned char));
1137 if (state->window == Z_NULL) return 1;
1138 }
4a5b6a35 1139
dce3d797
GC		 1140 /* if window not in use yet, initialize */
1141 if (state->wsize == 0) {
1142 state->wsize = 1U << state->wbits;
1143 state->write = 0;
1144 state->whave = 0;
1145 }
4a5b6a35 1146
dce3d797
GC		 1147 /* copy state->wsize or less output bytes into the circular window */
1148 copy = out - strm->avail_out;
1149 if (copy >= state->wsize) {
1150 zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
1151 state->write = 0;
1152 state->whave = state->wsize;
1153 }
1154 else {
1155 dist = state->wsize - state->write;
1156 if (dist > copy) dist = copy;
1157 zmemcpy(state->window + state->write, strm->next_out - copy, dist);
1158 copy -= dist;
1159 if (copy) {
1160 zmemcpy(state->window, strm->next_out - copy, copy);
1161 state->write = copy;
1162 state->whave = state->wsize;
1163 }
1164 else {
1165 state->write += dist;
1166 if (state->write == state->wsize) state->write = 0;
1167 if (state->whave < state->wsize) state->whave += dist;
1168 }
1169 }
1170 return 0;
f33b325a 1171}
b201171f 1172
dce3d797
GC		 1173/* Macros for inflate(): */
1174
1175/* check function to use adler32() for zlib or crc32() for gzip */
1176#define UPDATE(check, buf, len) \
1177 (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
1178
1179/* check macros for header crc */
1180#define CRC2(check, word) \
1181 do { \
1182 hbuf[0] = (unsigned char)(word); \
1183 hbuf[1] = (unsigned char)((word) >> 8); \
1184 check = crc32(check, hbuf, 2); \
1185 } while (0)
1186
1187#define CRC4(check, word) \
1188 do { \
1189 hbuf[0] = (unsigned char)(word); \
1190 hbuf[1] = (unsigned char)((word) >> 8); \
1191 hbuf[2] = (unsigned char)((word) >> 16); \
1192 hbuf[3] = (unsigned char)((word) >> 24); \
1193 check = crc32(check, hbuf, 4); \
1194 } while (0)
1195
1196/* Load registers with state in inflate() for speed */
1197#define LOAD() \
1198 do { \
1199 put = strm->next_out; \
1200 left = strm->avail_out; \
1201 next = strm->next_in; \
1202 have = strm->avail_in; \
1203 hold = state->hold; \
1204 bits = state->bits; \
1205 } while (0)
1206
1207/* Restore state from registers in inflate() */
1208#define RESTORE() \
1209 do { \
1210 strm->next_out = put; \
1211 strm->avail_out = left; \
1212 strm->next_in = next; \
1213 strm->avail_in = have; \
1214 state->hold = hold; \
1215 state->bits = bits; \
1216 } while (0)
1217
1218/* Clear the input bit accumulator */
1219#define INITBITS() \
1220 do { \
1221 hold = 0; \
1222 bits = 0; \
1223 } while (0)
1224
1225/* Get a byte of input into the bit accumulator, or return from inflate()
1226 if there is no input available. */
1227#define PULLBYTE() \
1228 do { \
1229 if (have == 0) goto inf_leave; \
1230 have--; \
1231 hold += (unsigned long)(*next++) << bits; \
1232 bits += 8; \
1233 } while (0)
1234
1235/* Assure that there are at least n bits in the bit accumulator. If there is
1236 not enough available input to do that, then return from inflate(). */
1237#define NEEDBITS(n) \
1238 do { \
1239 while (bits < (unsigned)(n)) \
1240 PULLBYTE(); \
1241 } while (0)
1242
1243/* Return the low n bits of the bit accumulator (n < 16) */
1244#define BITS(n) \
1245 ((unsigned)hold & ((1U << (n)) - 1))
1246
1247/* Remove n bits from the bit accumulator */
1248#define DROPBITS(n) \
1249 do { \
1250 hold >>= (n); \
1251 bits -= (unsigned)(n); \
1252 } while (0)
1253
1254/* Remove zero to seven bits as needed to go to a byte boundary */
1255#define BYTEBITS() \
1256 do { \
1257 hold >>= bits & 7; \
1258 bits -= bits & 7; \
1259 } while (0)
1260
1261/* Reverse the bytes in a 32-bit value */
1262#define REVERSE(q) \
1263 ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
1264 (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
1265
1266/*
1267 inflate() uses a state machine to process as much input data and generate as
1268 much output data as possible before returning. The state machine is
1269 structured roughly as follows:
1270
1271 for (;;) switch (state) {
1272 ...
1273 case STATEn:
1274 if (not enough input data or output space to make progress)
1275 return;
1276 ... make progress ...
1277 state = STATEm;
1278 break;
1279 ...
1280 }
f33b325a 1281
dce3d797
GC		 1282 so when inflate() is called again, the same case is attempted again, and
1283 if the appropriate resources are provided, the machine proceeds to the
1284 next state. The NEEDBITS() macro is usually the way the state evaluates
1285 whether it can proceed or should return. NEEDBITS() does the return if
1286 the requested bits are not available. The typical use of the BITS macros
1287 is:
1288
1289 NEEDBITS(n);
1290 ... do something with BITS(n) ...
1291 DROPBITS(n);
1292
1293 where NEEDBITS(n) either returns from inflate() if there isn't enough
1294 input left to load n bits into the accumulator, or it continues. BITS(n)
1295 gives the low n bits in the accumulator. When done, DROPBITS(n) drops
1296 the low n bits off the accumulator. INITBITS() clears the accumulator
1297 and sets the number of available bits to zero. BYTEBITS() discards just
1298 enough bits to put the accumulator on a byte boundary. After BYTEBITS()
1299 and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
1300
1301 NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
1302 if there is no input available. The decoding of variable length codes uses
1303 PULLBYTE() directly in order to pull just enough bytes to decode the next
1304 code, and no more.
1305
1306 Some states loop until they get enough input, making sure that enough
1307 state information is maintained to continue the loop where it left off
1308 if NEEDBITS() returns in the loop. For example, want, need, and keep
1309 would all have to actually be part of the saved state in case NEEDBITS()
1310 returns:
1311
1312 case STATEw:
1313 while (want < need) {
1314 NEEDBITS(n);
1315 keep[want++] = BITS(n);
1316 DROPBITS(n);
1317 }
1318 state = STATEx;
1319 case STATEx:
1320
1321 As shown above, if the next state is also the next case, then the break
1322 is omitted.
1323
1324 A state may also return if there is not enough output space available to
1325 complete that state. Those states are copying stored data, writing a
1326 literal byte, and copying a matching string.
1327
1328 When returning, a "goto inf_leave" is used to update the total counters,
1329 update the check value, and determine whether any progress has been made
1330 during that inflate() call in order to return the proper return code.
1331 Progress is defined as a change in either strm->avail_in or strm->avail_out.
1332 When there is a window, goto inf_leave will update the window with the last
1333 output written. If a goto inf_leave occurs in the middle of decompression
1334 and there is no window currently, goto inf_leave will create one and copy
1335 output to the window for the next call of inflate().
1336
1337 In this implementation, the flush parameter of inflate() only affects the
1338 return code (per zlib.h). inflate() always writes as much as possible to
1339 strm->next_out, given the space available and the provided input--the effect
1340 documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
1341 the allocation of and copying into a sliding window until necessary, which
1342 provides the effect documented in zlib.h for Z_FINISH when the entire input
1343 stream available. So the only thing the flush parameter actually does is:
1344 when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
1345 will return Z_BUF_ERROR if it has not reached the end of the stream.
1346 */
1347int ZEXPORT inflate(strm, flush)
1348z_streamp strm;
1349int flush;
f33b325a 1350{
dce3d797
GC		 1351 struct inflate_state FAR *state;
1352 unsigned char FAR *next; /* next input */
1353 unsigned char FAR *put; /* next output */
1354 unsigned have, left; /* available input and output */
1355 unsigned long hold; /* bit buffer */
1356 unsigned bits; /* bits in bit buffer */
1357 unsigned in, out; /* save starting available input and output */
1358 unsigned copy; /* number of stored or match bytes to copy */
1359 unsigned char FAR *from; /* where to copy match bytes from */
1360 code this; /* current decoding table entry */
1361 code last; /* parent table entry */
1362 unsigned len; /* length to copy for repeats, bits to drop */
1363 int ret; /* return code */
1364#ifdef GUNZIP
1365 unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
1366#endif
1367 static const unsigned short order[19] = /* permutation of code lengths */
1368 {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1369
1370 if (strm == Z_NULL || strm->state == Z_NULL ||
1371 (strm->next_in == Z_NULL && strm->avail_in != 0))
1372 return Z_STREAM_ERROR;
1373
1374 state = (struct inflate_state FAR *)strm->state;
1375 if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
1376 LOAD();
1377 in = have;
1378 out = left;
1379 ret = Z_OK;
1380 for (;;)
1381 switch (state->mode) {
1382 case HEAD:
1383 if (state->wrap == 0) {
1384 state->mode = TYPEDO;
1385 break;
1386 }
1387 NEEDBITS(16);
1388#ifdef GUNZIP
1389 if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
1390 state->check = crc32(0L, Z_NULL, 0);
1391 CRC2(state->check, hold);
1392 INITBITS();
1393 state->mode = FLAGS;
1394 break;
1395 }
1396 state->flags = 0; /* expect zlib header */
1397 if (state->head != Z_NULL)
1398 state->head->done = -1;
1399 if (!(state->wrap & 1) || /* check if zlib header allowed */
f33b325a 1400#else
dce3d797
GC		 1401 if (
1402#endif
1403 ((BITS(8) << 8) + (hold >> 8)) % 31) {
1404 strm->msg = (char *)"incorrect header check";
1405 state->mode = BAD;
1406 break;
1407 }
1408 if (BITS(4) != Z_DEFLATED) {
1409 strm->msg = (char *)"unknown compression method";
1410 state->mode = BAD;
1411 break;
1412 }
1413 DROPBITS(4);
1414 len = BITS(4) + 8;
1415 if (len > state->wbits) {
1416 strm->msg = (char *)"invalid window size";
1417 state->mode = BAD;
1418 break;
1419 }
1420 state->dmax = 1U << len;
1421 Tracev((stderr, "inflate: zlib header ok\n"));
1422 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1423 state->mode = hold & 0x200 ? DICTID : TYPE;
1424 INITBITS();
1425 break;
1426#ifdef GUNZIP
1427 case FLAGS:
1428 NEEDBITS(16);
1429 state->flags = (int)(hold);
1430 if ((state->flags & 0xff) != Z_DEFLATED) {
1431 strm->msg = (char *)"unknown compression method";
1432 state->mode = BAD;
1433 break;
1434 }
1435 if (state->flags & 0xe000) {
1436 strm->msg = (char *)"unknown header flags set";
1437 state->mode = BAD;
1438 break;
1439 }
1440 if (state->head != Z_NULL)
1441 state->head->text = (int)((hold >> 8) & 1);
1442 if (state->flags & 0x0200) CRC2(state->check, hold);
1443 INITBITS();
1444 state->mode = TIME;
1445 case TIME:
1446 NEEDBITS(32);
1447 if (state->head != Z_NULL)
1448 state->head->time = hold;
1449 if (state->flags & 0x0200) CRC4(state->check, hold);
1450 INITBITS();
1451 state->mode = OS;
1452 case OS:
1453 NEEDBITS(16);
1454 if (state->head != Z_NULL) {
1455 state->head->xflags = (int)(hold & 0xff);
1456 state->head->os = (int)(hold >> 8);
1457 }
1458 if (state->flags & 0x0200) CRC2(state->check, hold);
1459 INITBITS();
1460 state->mode = EXLEN;
1461 case EXLEN:
1462 if (state->flags & 0x0400) {
1463 NEEDBITS(16);
1464 state->length = (unsigned)(hold);
1465 if (state->head != Z_NULL)
1466 state->head->extra_len = (unsigned)hold;
1467 if (state->flags & 0x0200) CRC2(state->check, hold);
1468 INITBITS();
1469 }
1470 else if (state->head != Z_NULL)
1471 state->head->extra = Z_NULL;
1472 state->mode = EXTRA;
1473 case EXTRA:
1474 if (state->flags & 0x0400) {
1475 copy = state->length;
1476 if (copy > have) copy = have;
1477 if (copy) {
1478 if (state->head != Z_NULL &&
1479 state->head->extra != Z_NULL) {
1480 len = state->head->extra_len - state->length;
1481 zmemcpy(state->head->extra + len, next,
1482 len + copy > state->head->extra_max ?
1483 state->head->extra_max - len : copy);
1484 }
1485 if (state->flags & 0x0200)
1486 state->check = crc32(state->check, next, copy);
1487 have -= copy;
1488 next += copy;
1489 state->length -= copy;
1490 }
1491 if (state->length) goto inf_leave;
1492 }
1493 state->length = 0;
1494 state->mode = NAME;
1495 case NAME:
1496 if (state->flags & 0x0800) {
1497 if (have == 0) goto inf_leave;
1498 copy = 0;
1499 do {
1500 len = (unsigned)(next[copy++]);
1501 if (state->head != Z_NULL &&
1502 state->head->name != Z_NULL &&
1503 state->length < state->head->name_max)
1504 state->head->name[state->length++] = len;
1505 } while (len && copy < have);
1506 if (state->flags & 0x0200)
1507 state->check = crc32(state->check, next, copy);
1508 have -= copy;
1509 next += copy;
1510 if (len) goto inf_leave;
1511 }
1512 else if (state->head != Z_NULL)
1513 state->head->name = Z_NULL;
1514 state->length = 0;
1515 state->mode = COMMENT;
1516 case COMMENT:
1517 if (state->flags & 0x1000) {
1518 if (have == 0) goto inf_leave;
1519 copy = 0;
1520 do {
1521 len = (unsigned)(next[copy++]);
1522 if (state->head != Z_NULL &&
1523 state->head->comment != Z_NULL &&
1524 state->length < state->head->comm_max)
1525 state->head->comment[state->length++] = len;
1526 } while (len && copy < have);
1527 if (state->flags & 0x0200)
1528 state->check = crc32(state->check, next, copy);
1529 have -= copy;
1530 next += copy;
1531 if (len) goto inf_leave;
1532 }
1533 else if (state->head != Z_NULL)
1534 state->head->comment = Z_NULL;
1535 state->mode = HCRC;
1536 case HCRC:
1537 if (state->flags & 0x0200) {
1538 NEEDBITS(16);
1539 if (hold != (state->check & 0xffff)) {
1540 strm->msg = (char *)"header crc mismatch";
1541 state->mode = BAD;
1542 break;
1543 }
1544 INITBITS();
1545 }
1546 if (state->head != Z_NULL) {
1547 state->head->hcrc = (int)((state->flags >> 9) & 1);
1548 state->head->done = 1;
1549 }
1550 strm->adler = state->check = crc32(0L, Z_NULL, 0);
1551 state->mode = TYPE;
1552 break;
b201171f 1553#endif
dce3d797
GC		 1554 case DICTID:
1555 NEEDBITS(32);
1556 strm->adler = state->check = REVERSE(hold);
1557 INITBITS();
1558 state->mode = DICT;
1559 case DICT:
1560 if (state->havedict == 0) {
1561 RESTORE();
1562 return Z_NEED_DICT;
1563 }
1564 strm->adler = state->check = adler32(0L, Z_NULL, 0);
1565 state->mode = TYPE;
1566 case TYPE:
1567 if (flush == Z_BLOCK) goto inf_leave;
1568 case TYPEDO:
1569 if (state->last) {
1570 BYTEBITS();
1571 state->mode = CHECK;
1572 break;
1573 }
1574 NEEDBITS(3);
1575 state->last = BITS(1);
1576 DROPBITS(1);
1577 switch (BITS(2)) {
1578 case 0: /* stored block */
1579 Tracev((stderr, "inflate: stored block%s\n",
1580 state->last ? " (last)" : ""));
1581 state->mode = STORED;
1582 break;
1583 case 1: /* fixed block */
1584 fixedtables(state);
1585 Tracev((stderr, "inflate: fixed codes block%s\n",
1586 state->last ? " (last)" : ""));
1587 state->mode = LEN; /* decode codes */
1588 break;
1589 case 2: /* dynamic block */
1590 Tracev((stderr, "inflate: dynamic codes block%s\n",
1591 state->last ? " (last)" : ""));
1592 state->mode = TABLE;
1593 break;
1594 case 3:
1595 strm->msg = (char *)"invalid block type";
1596 state->mode = BAD;
1597 }
1598 DROPBITS(2);
1599 break;
1600 case STORED:
1601 BYTEBITS(); /* go to byte boundary */
1602 NEEDBITS(32);
1603 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1604 strm->msg = (char *)"invalid stored block lengths";
1605 state->mode = BAD;
1606 break;
1607 }
1608 state->length = (unsigned)hold & 0xffff;
1609 Tracev((stderr, "inflate: stored length %u\n",
1610 state->length));
1611 INITBITS();
1612 state->mode = COPY;
1613 case COPY:
1614 copy = state->length;
1615 if (copy) {
1616 if (copy > have) copy = have;
1617 if (copy > left) copy = left;
1618 if (copy == 0) goto inf_leave;
1619 zmemcpy(put, next, copy);
1620 have -= copy;
1621 next += copy;
1622 left -= copy;
1623 put += copy;
1624 state->length -= copy;
1625 break;
1626 }
1627 Tracev((stderr, "inflate: stored end\n"));
1628 state->mode = TYPE;
1629 break;
1630 case TABLE:
1631 NEEDBITS(14);
1632 state->nlen = BITS(5) + 257;
1633 DROPBITS(5);
1634 state->ndist = BITS(5) + 1;
1635 DROPBITS(5);
1636 state->ncode = BITS(4) + 4;
1637 DROPBITS(4);
1638#ifndef PKZIP_BUG_WORKAROUND
1639 if (state->nlen > 286 || state->ndist > 30) {
1640 strm->msg = (char *)"too many length or distance symbols";
1641 state->mode = BAD;
1642 break;
1643 }
1644#endif
1645 Tracev((stderr, "inflate: table sizes ok\n"));
1646 state->have = 0;
1647 state->mode = LENLENS;
1648 case LENLENS:
1649 while (state->have < state->ncode) {
1650 NEEDBITS(3);
1651 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1652 DROPBITS(3);
1653 }
1654 while (state->have < 19)
1655 state->lens[order[state->have++]] = 0;
1656 state->next = state->codes;
1657 state->lencode = (code const FAR *)(state->next);
1658 state->lenbits = 7;
1659 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1660 &(state->lenbits), state->work);
1661 if (ret) {
1662 strm->msg = (char *)"invalid code lengths set";
1663 state->mode = BAD;
1664 break;
1665 }
1666 Tracev((stderr, "inflate: code lengths ok\n"));
1667 state->have = 0;
1668 state->mode = CODELENS;
1669 case CODELENS:
1670 while (state->have < state->nlen + state->ndist) {
1671 for (;;) {
1672 this = state->lencode[BITS(state->lenbits)];
1673 if ((unsigned)(this.bits) <= bits) break;
1674 PULLBYTE();
1675 }
1676 if (this.val < 16) {
1677 NEEDBITS(this.bits);
1678 DROPBITS(this.bits);
1679 state->lens[state->have++] = this.val;
1680 }
1681 else {
1682 if (this.val == 16) {
1683 NEEDBITS(this.bits + 2);
1684 DROPBITS(this.bits);
1685 if (state->have == 0) {
1686 strm->msg = (char *)"invalid bit length repeat";
1687 state->mode = BAD;
1688 break;
1689 }
1690 len = state->lens[state->have - 1];
1691 copy = 3 + BITS(2);
1692 DROPBITS(2);
1693 }
1694 else if (this.val == 17) {
1695 NEEDBITS(this.bits + 3);
1696 DROPBITS(this.bits);
1697 len = 0;
1698 copy = 3 + BITS(3);
1699 DROPBITS(3);
1700 }
1701 else {
1702 NEEDBITS(this.bits + 7);
1703 DROPBITS(this.bits);
1704 len = 0;
1705 copy = 11 + BITS(7);
1706 DROPBITS(7);
1707 }
1708 if (state->have + copy > state->nlen + state->ndist) {
1709 strm->msg = (char *)"invalid bit length repeat";
1710 state->mode = BAD;
1711 break;
1712 }
1713 while (copy--)
1714 state->lens[state->have++] = (unsigned short)len;
1715 }
1716 }
1717
1718 /* handle error breaks in while */
1719 if (state->mode == BAD) break;
1720
1721 /* build code tables */
1722 state->next = state->codes;
1723 state->lencode = (code const FAR *)(state->next);
1724 state->lenbits = 9;
1725 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1726 &(state->lenbits), state->work);
1727 if (ret) {
1728 strm->msg = (char *)"invalid literal/lengths set";
1729 state->mode = BAD;
1730 break;
1731 }
1732 state->distcode = (code const FAR *)(state->next);
1733 state->distbits = 6;
1734 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1735 &(state->next), &(state->distbits), state->work);
1736 if (ret) {
1737 strm->msg = (char *)"invalid distances set";
1738 state->mode = BAD;
1739 break;
1740 }
1741 Tracev((stderr, "inflate: codes ok\n"));
1742 state->mode = LEN;
1743 case LEN:
1744 if (strm->outcb != Z_NULL) /* for watchdog (U-Boot) */
1745 (*strm->outcb)(Z_NULL, 0);
1746 if (have >= 6 && left >= 258) {
1747 RESTORE();
1748 inflate_fast(strm, out);
1749 LOAD();
1750 break;
1751 }
1752 for (;;) {
1753 this = state->lencode[BITS(state->lenbits)];
1754 if ((unsigned)(this.bits) <= bits) break;
1755 PULLBYTE();
1756 }
1757 if (this.op && (this.op & 0xf0) == 0) {
1758 last = this;
1759 for (;;) {
1760 this = state->lencode[last.val +
1761 (BITS(last.bits + last.op) >> last.bits)];
1762 if ((unsigned)(last.bits + this.bits) <= bits) break;
1763 PULLBYTE();
1764 }
1765 DROPBITS(last.bits);
1766 }
1767 DROPBITS(this.bits);
1768 state->length = (unsigned)this.val;
1769 if ((int)(this.op) == 0) {
1770 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
1771 "inflate: literal '%c'\n" :
1772 "inflate: literal 0x%02x\n", this.val));
1773 state->mode = LIT;
1774 break;
1775 }
1776 if (this.op & 32) {
1777 Tracevv((stderr, "inflate: end of block\n"));
1778 state->mode = TYPE;
1779 break;
1780 }
1781 if (this.op & 64) {
1782 strm->msg = (char *)"invalid literal/length code";
1783 state->mode = BAD;
1784 break;
1785 }
1786 state->extra = (unsigned)(this.op) & 15;
1787 state->mode = LENEXT;
1788 case LENEXT:
1789 if (state->extra) {
1790 NEEDBITS(state->extra);
1791 state->length += BITS(state->extra);
1792 DROPBITS(state->extra);
1793 }
1794 Tracevv((stderr, "inflate: length %u\n", state->length));
1795 state->mode = DIST;
1796 case DIST:
1797 for (;;) {
1798 this = state->distcode[BITS(state->distbits)];
1799 if ((unsigned)(this.bits) <= bits) break;
1800 PULLBYTE();
1801 }
1802 if ((this.op & 0xf0) == 0) {
1803 last = this;
1804 for (;;) {
1805 this = state->distcode[last.val +
1806 (BITS(last.bits + last.op) >> last.bits)];
1807 if ((unsigned)(last.bits + this.bits) <= bits) break;
1808 PULLBYTE();
1809 }
1810 DROPBITS(last.bits);
1811 }
1812 DROPBITS(this.bits);
1813 if (this.op & 64) {
1814 strm->msg = (char *)"invalid distance code";
1815 state->mode = BAD;
1816 break;
1817 }
1818 state->offset = (unsigned)this.val;
1819 state->extra = (unsigned)(this.op) & 15;
1820 state->mode = DISTEXT;
1821 case DISTEXT:
1822 if (state->extra) {
1823 NEEDBITS(state->extra);
1824 state->offset += BITS(state->extra);
1825 DROPBITS(state->extra);
1826 }
1827#ifdef INFLATE_STRICT
1828 if (state->offset > state->dmax) {
1829 strm->msg = (char *)"invalid distance too far back";
1830 state->mode = BAD;
1831 break;
1832 }
1833#endif
1834 if (state->offset > state->whave + out - left) {
1835 strm->msg = (char *)"invalid distance too far back";
1836 state->mode = BAD;
1837 break;
1838 }
1839 Tracevv((stderr, "inflate: distance %u\n", state->offset));
1840 state->mode = MATCH;
1841 case MATCH:
1842 if (left == 0) goto inf_leave;
1843 copy = out - left;
1844 if (state->offset > copy) { /* copy from window */
1845 copy = state->offset - copy;
1846 if (copy > state->write) {
1847 copy -= state->write;
1848 from = state->window + (state->wsize - copy);
1849 }
1850 else
1851 from = state->window + (state->write - copy);
1852 if (copy > state->length) copy = state->length;
1853 }
1854 else { /* copy from output */
1855 from = put - state->offset;
1856 copy = state->length;
1857 }
1858 if (copy > left) copy = left;
1859 left -= copy;
1860 state->length -= copy;
1861 do {
1862 *put++ = *from++;
1863 } while (--copy);
1864 if (state->length == 0) state->mode = LEN;
1865 break;
1866 case LIT:
1867 if (left == 0) goto inf_leave;
1868 *put++ = (unsigned char)(state->length);
1869 left--;
1870 state->mode = LEN;
1871 break;
1872 case CHECK:
1873 if (state->wrap) {
1874 NEEDBITS(32);
1875 out -= left;
1876 strm->total_out += out;
1877 state->total += out;
1878 if (out)
1879 strm->adler = state->check =
1880 UPDATE(state->check, put - out, out);
1881 out = left;
1882 if ((
1883#ifdef GUNZIP
1884 state->flags ? hold :
1885#endif
1886 REVERSE(hold)) != state->check) {
1887 strm->msg = (char *)"incorrect data check";
1888 state->mode = BAD;
1889 break;
1890 }
1891 INITBITS();
1892 Tracev((stderr, "inflate: check matches trailer\n"));
1893 }
1894#ifdef GUNZIP
1895 state->mode = LENGTH;
1896 case LENGTH:
1897 if (state->wrap && state->flags) {
1898 NEEDBITS(32);
1899 if (hold != (state->total & 0xffffffffUL)) {
1900 strm->msg = (char *)"incorrect length check";
1901 state->mode = BAD;
1902 break;
1903 }
1904 INITBITS();
1905 Tracev((stderr, "inflate: length matches trailer\n"));
1906 }
1907#endif
1908 state->mode = DONE;
1909 case DONE:
1910 ret = Z_STREAM_END;
1911 goto inf_leave;
1912 case BAD:
1913 ret = Z_DATA_ERROR;
1914 goto inf_leave;
1915 case MEM:
1916 return Z_MEM_ERROR;
1917 case SYNC:
1918 default:
1919 return Z_STREAM_ERROR;
1920 }
1921
1922 /*
1923 Return from inflate(), updating the total counts and the check value.
1924 If there was no progress during the inflate() call, return a buffer
1925 error. Call updatewindow() to create and/or update the window state.
1926 Note: a memory error from inflate() is non-recoverable.
1927 */
1928 inf_leave:
1929 RESTORE();
1930 if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
1931 if (updatewindow(strm, out)) {
1932 state->mode = MEM;
1933 return Z_MEM_ERROR;
1934 }
1935 in -= strm->avail_in;
1936 out -= strm->avail_out;
1937 strm->total_in += in;
1938 strm->total_out += out;
1939 state->total += out;
1940 if (state->wrap && out)
1941 strm->adler = state->check =
1942 UPDATE(state->check, strm->next_out - out, out);
1943 strm->data_type = state->bits + (state->last ? 64 : 0) +
1944 (state->mode == TYPE ? 128 : 0);
1945 if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
1946 ret = Z_BUF_ERROR;
1947 return ret;
f33b325a
WD		 1948}
1949
dce3d797
GC		 1950int ZEXPORT inflateEnd(strm)
1951z_streamp strm;
4a5b6a35 1952{
dce3d797
GC		 1953 struct inflate_state FAR *state;
1954 if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
1955 return Z_STREAM_ERROR;
1956 state = (struct inflate_state FAR *)strm->state;
253cb831
GC		 1957 if (state->window != Z_NULL) {
1958 if (strm->outcb != Z_NULL)
1959 (*strm->outcb)(Z_NULL, 0);
1960 ZFREE(strm, state->window);
1961 }
dce3d797
GC		 1962 ZFREE(strm, strm->state);
1963 strm->state = Z_NULL;
1964 Tracev((stderr, "inflate: end\n"));
1965 return Z_OK;
4a5b6a35
WD		 1966}
1967
f33b325a 1968/*+++++*/
dce3d797
GC		 1969/* zutil.c -- target dependent utility functions for the compression library
1970 * Copyright (C) 1995-2005 Jean-loup Gailly.
f33b325a 1971 * For conditions of distribution and use, see copyright notice in zlib.h
4a5b6a35
WD		 1972 */
1973
dce3d797 1974/* @(#) $Id$ */
4a5b6a35 1975
dce3d797
GC		 1976#ifndef NO_DUMMY_DECL
1977struct internal_state {int dummy;}; /* for buggy compilers */
1978#endif
f33b325a 1979
dce3d797
GC		 1980const char * const z_errmsg[10] = {
1981"need dictionary", /* Z_NEED_DICT 2 */
1982"stream end", /* Z_STREAM_END 1 */
1983"", /* Z_OK 0 */
1984"file error", /* Z_ERRNO (-1) */
1985"stream error", /* Z_STREAM_ERROR (-2) */
1986"data error", /* Z_DATA_ERROR (-3) */
1987"insufficient memory", /* Z_MEM_ERROR (-4) */
1988"buffer error", /* Z_BUF_ERROR (-5) */
1989"incompatible version",/* Z_VERSION_ERROR (-6) */
1990""};
f33b325a 1991
dce3d797
GC		 1992#ifdef DEBUG
1993
1994#ifndef verbose
1995#define verbose 0
1996#endif
1997int z_verbose = verbose;
1998
1999void z_error (m)
2000 char *m;
b201171f 2001{
dce3d797
GC		 2002 fprintf(stderr, "%s\n", m);
2003 exit(1);
b201171f 2004}
dce3d797 2005#endif
4a5b6a35 2006
dce3d797
GC		 2007/* exported to allow conversion of error code to string for compress() and
2008 * uncompress()
f33b325a 2009 */
dce3d797 2010#ifndef MY_ZCALLOC /* Any system without a special alloc function */
f33b325a 2011
dce3d797
GC		 2012#ifndef STDC
2013extern voidp malloc OF((uInt size));
2014extern voidp calloc OF((uInt items, uInt size));
2015extern void free OF((voidpf ptr));
2016#endif
f33b325a 2017
dce3d797
GC		 2018voidpf zcalloc (opaque, items, size)
2019 voidpf opaque;
2020 unsigned items;
2021 unsigned size;
2022{
2023 if (opaque)
2024 items += size - size; /* make compiler happy */
2025 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2026 (voidpf)calloc(items, size);
2027}
f33b325a 2028
dce3d797
GC		 2029void zcfree (opaque, ptr, nb)
2030 voidpf opaque;
2031 voidpf ptr;
2032 unsigned nb;
2033{
2034 free(ptr);
2035 if (opaque)
2036 return; /* make compiler happy */
2037}
f33b325a 2038
dce3d797 2039#endif /* MY_ZCALLOC */
4a5b6a35
WD		 2040/*+++++*/
2041/* adler32.c -- compute the Adler-32 checksum of a data stream
dce3d797 2042 * Copyright (C) 1995-2004 Mark Adler
4a5b6a35
WD		 2043 * For conditions of distribution and use, see copyright notice in zlib.h
2044 */
2045
dce3d797 2046/* @(#) $Id$ */
4a5b6a35 2047
dce3d797 2048#define BASE 65521UL /* largest prime smaller than 65536 */
4a5b6a35
WD		 2049#define NMAX 5552
2050/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2051
dce3d797
GC		 2052#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2053#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2054#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2055#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2056#define DO16(buf) DO8(buf,0); DO8(buf,8);
2057
2058/* use NO_DIVIDE if your processor does not do division in hardware */
2059#ifdef NO_DIVIDE
2060#define MOD(a) \
2061 do { \
2062 if (a >= (BASE << 16)) \
2063 a -= (BASE << 16); \
2064 if (a >= (BASE << 15)) \
2065 a -= (BASE << 15); \
2066 if (a >= (BASE << 14)) \
2067 a -= (BASE << 14); \
2068 if (a >= (BASE << 13)) \
2069 a -= (BASE << 13); \
2070 if (a >= (BASE << 12)) \
2071 a -= (BASE << 12); \
2072 if (a >= (BASE << 11)) \
2073 a -= (BASE << 11); \
2074 if (a >= (BASE << 10)) \
2075 a -= (BASE << 10); \
2076 if (a >= (BASE << 9)) \
2077 a -= (BASE << 9); \
2078 if (a >= (BASE << 8)) \
2079 a -= (BASE << 8); \
2080 if (a >= (BASE << 7)) \
2081 a -= (BASE << 7); \
2082 if (a >= (BASE << 6)) \
2083 a -= (BASE << 6); \
2084 if (a >= (BASE << 5)) \
2085 a -= (BASE << 5); \
2086 if (a >= (BASE << 4)) \
2087 a -= (BASE << 4); \
2088 if (a >= (BASE << 3)) \
2089 a -= (BASE << 3); \
2090 if (a >= (BASE << 2)) \
2091 a -= (BASE << 2); \
2092 if (a >= (BASE << 1)) \
2093 a -= (BASE << 1); \
2094 if (a >= BASE) \
2095 a -= BASE; \
2096 } while (0)
2097#define MOD4(a) \
2098 do { \
2099 if (a >= (BASE << 4)) \
2100 a -= (BASE << 4); \
2101 if (a >= (BASE << 3)) \
2102 a -= (BASE << 3); \
2103 if (a >= (BASE << 2)) \
2104 a -= (BASE << 2); \
2105 if (a >= (BASE << 1)) \
2106 a -= (BASE << 1); \
2107 if (a >= BASE) \
2108 a -= BASE; \
2109 } while (0)
2110#else
2111#define MOD(a) a %= BASE
2112#define MOD4(a) a %= BASE
2113#endif
4a5b6a35
WD		 2114
2115/* ========================================================================= */
dce3d797 2116uLong ZEXPORT adler32(adler, buf, len)
4a5b6a35 2117 uLong adler;
dce3d797 2118 const Bytef *buf;
4a5b6a35
WD		 2119 uInt len;
2120{
dce3d797
GC		 2121 unsigned long sum2;
2122 unsigned n;
2123
2124 /* split Adler-32 into component sums */
2125 sum2 = (adler >> 16) & 0xffff;
2126 adler &= 0xffff;
2127
2128 /* in case user likes doing a byte at a time, keep it fast */
2129 if (len == 1) {
2130 adler += buf[0];
2131 if (adler >= BASE)
2132 adler -= BASE;
2133 sum2 += adler;
2134 if (sum2 >= BASE)
2135 sum2 -= BASE;
2136 return adler | (sum2 << 16);
b201171f 2137 }
dce3d797
GC		 2138
2139 /* initial Adler-32 value (deferred check for len == 1 speed) */
2140 if (buf == Z_NULL)
2141 return 1L;
2142
2143 /* in case short lengths are provided, keep it somewhat fast */
2144 if (len < 16) {
2145 while (len--) {
2146 adler += *buf++;
2147 sum2 += adler;
2148 }
2149 if (adler >= BASE)
2150 adler -= BASE;
2151 MOD4(sum2); /* only added so many BASE's */
2152 return adler | (sum2 << 16);
2153 }
2154
2155 /* do length NMAX blocks -- requires just one modulo operation */
2156 while (len >= NMAX) {
2157 len -= NMAX;
2158 n = NMAX / 16; /* NMAX is divisible by 16 */
2159 do {
2160 DO16(buf); /* 16 sums unrolled */
2161 buf += 16;
2162 } while (--n);
2163 MOD(adler);
2164 MOD(sum2);
2165 }
2166
2167 /* do remaining bytes (less than NMAX, still just one modulo) */
2168 if (len) { /* avoid modulos if none remaining */
2169 while (len >= 16) {
2170 len -= 16;
2171 DO16(buf);
2172 buf += 16;
2173 }
2174 while (len--) {
2175 adler += *buf++;
2176 sum2 += adler;
2177 }
2178 MOD(adler);
2179 MOD(sum2);
2180 }
2181
2182 /* return recombined sums */
2183 return adler | (sum2 << 16);
4a5b6a35 2184}
"Das U-Boot" Source Tree