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