blob: e19484aaa07fbc7a05900f5159c58a795b251343 [file] [log] [blame]
wdenk4a5b6a32001-04-28 17:59:11 +00001/*
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002 * This file is derived from various .h and .c files from the zlib-1.2.3
wdenk4a5b6a32001-04-28 17:59:11 +00003 * 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
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040017 * Copyright (C) 1995-2005 Jean-loup Gailly.
wdenk4a5b6a32001-04-28 17:59:11 +000018 * 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
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040026#define ZUTIL_H
27#define ZLIB_INTERNAL
wdenk4a5b6a32001-04-28 17:59:11 +000028
Giuseppe CONDORELLI7662eb22009-09-03 07:37:46 -040029#include <common.h>
Joakim Tjernlundcd514ae2009-11-19 13:22:44 +010030#include <compiler.h>
31#include <asm/unaligned.h>
Stefan Roesef8526282010-09-08 15:34:58 +020032#include <watchdog.h>
Joakim Tjernlundcd514ae2009-11-19 13:22:44 +010033#include "u-boot/zlib.h"
Wolfgang Denka9f99ab2009-12-06 00:53:18 +010034#undef OFF /* avoid conflicts */
35
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040036/* To avoid a build time warning */
37#ifdef STDC
38#include <malloc.h>
39#endif
wdenk4a5b6a32001-04-28 17:59:11 +000040
41#ifndef local
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040042#define local static
wdenk4a5b6a32001-04-28 17:59:11 +000043#endif
44/* compile with -Dlocal if your debugger can't find static symbols */
45
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040046typedef unsigned char uch;
wdenk4a5b6a32001-04-28 17:59:11 +000047typedef uch FAR uchf;
48typedef unsigned short ush;
49typedef ush FAR ushf;
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040050typedef unsigned long ulg;
wdenk4a5b6a32001-04-28 17:59:11 +000051
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040052#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
53#define ERR_RETURN(strm,err) return (strm->msg = (char*)ERR_MSG(err), (err))
wdenk4a5b6a32001-04-28 17:59:11 +000054/* To be used only when the state is known to be valid */
55
56#ifndef NULL
57#define NULL ((void *) 0)
58#endif
59
wdenk8bde7f72003-06-27 21:31:46 +000060 /* common constants */
wdenk4a5b6a32001-04-28 17:59:11 +000061
wdenk4a5b6a32001-04-28 17:59:11 +000062#ifndef DEF_WBITS
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040063#define DEF_WBITS MAX_WBITS
wdenk4a5b6a32001-04-28 17:59:11 +000064#endif
65/* default windowBits for decompression. MAX_WBITS is for compression only */
66
67#if MAX_MEM_LEVEL >= 8
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040068#define DEF_MEM_LEVEL 8
wdenk4a5b6a32001-04-28 17:59:11 +000069#else
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040070#define DEF_MEM_LEVEL MAX_MEM_LEVEL
wdenk4a5b6a32001-04-28 17:59:11 +000071#endif
72/* default memLevel */
73
74#define STORED_BLOCK 0
75#define STATIC_TREES 1
76#define DYN_TREES 2
77/* The three kinds of block type */
78
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040079#define MIN_MATCH 3
80#define MAX_MATCH 258
wdenk4a5b6a32001-04-28 17:59:11 +000081/* The minimum and maximum match lengths */
82
wdenk8bde7f72003-06-27 21:31:46 +000083 /* functions */
wdenk4a5b6a32001-04-28 17:59:11 +000084
85#include <linux/string.h>
86#define zmemcpy memcpy
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040087#define zmemcmp memcmp
88#define zmemzero(dest, len) memset(dest, 0, len)
wdenk4a5b6a32001-04-28 17:59:11 +000089
90/* Diagnostic functions */
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040091#ifdef DEBUG
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040092 extern int z_verbose;
93 extern void z_error OF((char *m));
94#define Assert(cond,msg) {if(!(cond)) z_error(msg);}
Giuseppe CONDORELLI7662eb22009-09-03 07:37:46 -040095#define fprintf(fp,...) printf(__VA_ARGS__)
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -040096#define Trace(x) {if (z_verbose>=0) fprintf x ;}
97#define Tracev(x) {if (z_verbose>0) fprintf x ;}
98#define Tracevv(x) {if (z_verbose>1) fprintf x ;}
99#define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
100#define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
wdenk4a5b6a32001-04-28 17:59:11 +0000101#else
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400102#define Assert(cond,msg)
103#define Trace(x)
104#define Tracev(x)
105#define Tracevv(x)
106#define Tracec(c,x)
107#define Tracecv(c,x)
wdenk4a5b6a32001-04-28 17:59:11 +0000108#endif
109
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400110voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
111void zcfree OF((voidpf opaque, voidpf ptr, unsigned size));
wdenk4a5b6a32001-04-28 17:59:11 +0000112
113#define ZALLOC(strm, items, size) \
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400114 (*((strm)->zalloc))((strm)->opaque, (items), (size))
115#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), 0)
wdenk4a5b6a32001-04-28 17:59:11 +0000116
117/*+++++*/
118/* inftrees.h -- header to use inftrees.c
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400119 * Copyright (C) 1995-2005 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +0000120 * For conditions of distribution and use, see copyright notice in zlib.h
121 */
122
123/* WARNING: this file should *not* be used by applications. It is
124 part of the implementation of the compression library and is
125 subject to change. Applications should only use zlib.h.
126 */
127
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400128/* Structure for decoding tables. Each entry provides either the
129 information needed to do the operation requested by the code that
130 indexed that table entry, or it provides a pointer to another
131 table that indexes more bits of the code. op indicates whether
132 the entry is a pointer to another table, a literal, a length or
133 distance, an end-of-block, or an invalid code. For a table
134 pointer, the low four bits of op is the number of index bits of
135 that table. For a length or distance, the low four bits of op
136 is the number of extra bits to get after the code. bits is
137 the number of bits in this code or part of the code to drop off
138 of the bit buffer. val is the actual byte to output in the case
139 of a literal, the base length or distance, or the offset from
140 the current table to the next table. Each entry is four bytes. */
wdenk4a5b6a32001-04-28 17:59:11 +0000141
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400142typedef struct {
143 unsigned char op; /* operation, extra bits, table bits */
144 unsigned char bits; /* bits in this part of the code */
145 unsigned short val; /* offset in table or code value */
146} code;
wdenk4a5b6a32001-04-28 17:59:11 +0000147
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400148/* Maximum size of dynamic tree. The maximum found in a long but non-
149 exhaustive search was 1444 code structures (852 for length/literals
150 and 592 for distances, the latter actually the result of an
151 exhaustive search). The true maximum is not known, but the value
152 below is more than safe. */
153#define ENOUGH 2048
154#define MAXD 592
wdenk4a5b6a32001-04-28 17:59:11 +0000155
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400156/* Type of code to build for inftable() */
157typedef enum {
158 CODES,
159 LENS,
160 DISTS
161} codetype;
wdenk4a5b6a32001-04-28 17:59:11 +0000162
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400163extern int inflate_table OF((codetype type, unsigned short FAR *lens,
164 unsigned codes, code FAR * FAR *table,
165 unsigned FAR *bits, unsigned short FAR *work));
wdenk4a5b6a32001-04-28 17:59:11 +0000166/*+++++*/
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400167/* inflate.h -- internal inflate state definition
168 * Copyright (C) 1995-2004 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +0000169 * For conditions of distribution and use, see copyright notice in zlib.h
170 */
171
172/* WARNING: this file should *not* be used by applications. It is
173 part of the implementation of the compression library and is
174 subject to change. Applications should only use zlib.h.
175 */
176
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400177#define GUNZIP
wdenk4a5b6a32001-04-28 17:59:11 +0000178
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400179/* Possible inflate modes between inflate() calls */
180typedef enum {
181 HEAD, /* i: waiting for magic header */
182 FLAGS, /* i: waiting for method and flags (gzip) */
183 TIME, /* i: waiting for modification time (gzip) */
184 OS, /* i: waiting for extra flags and operating system (gzip) */
185 EXLEN, /* i: waiting for extra length (gzip) */
186 EXTRA, /* i: waiting for extra bytes (gzip) */
187 NAME, /* i: waiting for end of file name (gzip) */
188 COMMENT, /* i: waiting for end of comment (gzip) */
189 HCRC, /* i: waiting for header crc (gzip) */
190 DICTID, /* i: waiting for dictionary check value */
191 DICT, /* waiting for inflateSetDictionary() call */
192 TYPE, /* i: waiting for type bits, including last-flag bit */
193 TYPEDO, /* i: same, but skip check to exit inflate on new block */
194 STORED, /* i: waiting for stored size (length and complement) */
195 COPY, /* i/o: waiting for input or output to copy stored block */
196 TABLE, /* i: waiting for dynamic block table lengths */
197 LENLENS, /* i: waiting for code length code lengths */
198 CODELENS, /* i: waiting for length/lit and distance code lengths */
199 LEN, /* i: waiting for length/lit code */
200 LENEXT, /* i: waiting for length extra bits */
201 DIST, /* i: waiting for distance code */
202 DISTEXT, /* i: waiting for distance extra bits */
203 MATCH, /* o: waiting for output space to copy string */
204 LIT, /* o: waiting for output space to write literal */
205 CHECK, /* i: waiting for 32-bit check value */
206 LENGTH, /* i: waiting for 32-bit length (gzip) */
207 DONE, /* finished check, done -- remain here until reset */
208 BAD, /* got a data error -- remain here until reset */
209 MEM, /* got an inflate() memory error -- remain here until reset */
210 SYNC, /* looking for synchronization bytes to restart inflate() */
211 START,
212 WASH,
213 END,
214 BADCODE
215} inflate_mode;
wdenk4a5b6a32001-04-28 17:59:11 +0000216
217/*
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400218 State transitions between above modes -
219
220 (most modes can go to the BAD or MEM mode -- not shown for clarity)
221
222 Process header:
223 HEAD -> (gzip) or (zlib)
224 (gzip) -> FLAGS -> TIME -> OS -> EXLEN -> EXTRA -> NAME
225 NAME -> COMMENT -> HCRC -> TYPE
226 (zlib) -> DICTID or TYPE
227 DICTID -> DICT -> TYPE
228 Read deflate blocks:
229 TYPE -> STORED or TABLE or LEN or CHECK
230 STORED -> COPY -> TYPE
231 TABLE -> LENLENS -> CODELENS -> LEN
232 Read deflate codes:
233 LEN -> LENEXT or LIT or TYPE
234 LENEXT -> DIST -> DISTEXT -> MATCH -> LEN
235 LIT -> LEN
236 Process trailer:
237 CHECK -> LENGTH -> DONE
wdenk4a5b6a32001-04-28 17:59:11 +0000238 */
239
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400240/* state maintained between inflate() calls. Approximately 7K bytes. */
241struct inflate_state {
242 inflate_mode mode; /* current inflate mode */
243 int last; /* true if processing last block */
244 int wrap; /* bit 0 true for zlib, bit 1 true for gzip */
245 int havedict; /* true if dictionary provided */
246 int flags; /* gzip header method and flags (0 if zlib) */
247 unsigned dmax; /* zlib header max distance (INFLATE_STRICT) */
248 unsigned long check; /* protected copy of check value */
249 unsigned long total; /* protected copy of output count */
250 gz_headerp head; /* where to save gzip header information */
251 /* sliding window */
252 unsigned wbits; /* log base 2 of requested window size */
253 unsigned wsize; /* window size or zero if not using window */
254 unsigned whave; /* valid bytes in the window */
255 unsigned write; /* window write index */
256 unsigned char FAR *window; /* allocated sliding window, if needed */
257 /* bit accumulator */
258 unsigned long hold; /* input bit accumulator */
259 unsigned bits; /* number of bits in "in" */
260 /* for string and stored block copying */
261 unsigned length; /* literal or length of data to copy */
262 unsigned offset; /* distance back to copy string from */
263 /* for table and code decoding */
264 unsigned extra; /* extra bits needed */
265 /* fixed and dynamic code tables */
266 code const FAR *lencode; /* starting table for length/literal codes */
267 code const FAR *distcode; /* starting table for distance codes */
268 unsigned lenbits; /* index bits for lencode */
269 unsigned distbits; /* index bits for distcode */
270 /* dynamic table building */
271 unsigned ncode; /* number of code length code lengths */
272 unsigned nlen; /* number of length code lengths */
273 unsigned ndist; /* number of distance code lengths */
274 unsigned have; /* number of code lengths in lens[] */
275 code FAR *next; /* next available space in codes[] */
276 unsigned short lens[320]; /* temporary storage for code lengths */
277 unsigned short work[288]; /* work area for code table building */
278 code codes[ENOUGH]; /* space for code tables */
wdenk4a5b6a32001-04-28 17:59:11 +0000279};
280
wdenk4a5b6a32001-04-28 17:59:11 +0000281/*+++++*/
282/* inffast.h -- header to use inffast.c
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400283 * Copyright (C) 1995-2003 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +0000284 * For conditions of distribution and use, see copyright notice in zlib.h
285 */
286
287/* WARNING: this file should *not* be used by applications. It is
288 part of the implementation of the compression library and is
289 subject to change. Applications should only use zlib.h.
290 */
291
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400292void inflate_fast OF((z_streamp strm, unsigned start));
293/*+++++*/
294 /* inffixed.h -- table for decoding fixed codes
295 * Generated automatically by makefixed().
296 */
wdenk4a5b6a32001-04-28 17:59:11 +0000297
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400298 /* WARNING: this file should *not* be used by applications. It
299 is part of the implementation of the compression library and
300 is subject to change. Applications should only use zlib.h.
301 */
302
303 static const code lenfix[512] = {
304 {96,7,0},{0,8,80},{0,8,16},{20,8,115},{18,7,31},{0,8,112},{0,8,48},
305 {0,9,192},{16,7,10},{0,8,96},{0,8,32},{0,9,160},{0,8,0},{0,8,128},
306 {0,8,64},{0,9,224},{16,7,6},{0,8,88},{0,8,24},{0,9,144},{19,7,59},
307 {0,8,120},{0,8,56},{0,9,208},{17,7,17},{0,8,104},{0,8,40},{0,9,176},
308 {0,8,8},{0,8,136},{0,8,72},{0,9,240},{16,7,4},{0,8,84},{0,8,20},
309 {21,8,227},{19,7,43},{0,8,116},{0,8,52},{0,9,200},{17,7,13},{0,8,100},
310 {0,8,36},{0,9,168},{0,8,4},{0,8,132},{0,8,68},{0,9,232},{16,7,8},
311 {0,8,92},{0,8,28},{0,9,152},{20,7,83},{0,8,124},{0,8,60},{0,9,216},
312 {18,7,23},{0,8,108},{0,8,44},{0,9,184},{0,8,12},{0,8,140},{0,8,76},
313 {0,9,248},{16,7,3},{0,8,82},{0,8,18},{21,8,163},{19,7,35},{0,8,114},
314 {0,8,50},{0,9,196},{17,7,11},{0,8,98},{0,8,34},{0,9,164},{0,8,2},
315 {0,8,130},{0,8,66},{0,9,228},{16,7,7},{0,8,90},{0,8,26},{0,9,148},
316 {20,7,67},{0,8,122},{0,8,58},{0,9,212},{18,7,19},{0,8,106},{0,8,42},
317 {0,9,180},{0,8,10},{0,8,138},{0,8,74},{0,9,244},{16,7,5},{0,8,86},
318 {0,8,22},{64,8,0},{19,7,51},{0,8,118},{0,8,54},{0,9,204},{17,7,15},
319 {0,8,102},{0,8,38},{0,9,172},{0,8,6},{0,8,134},{0,8,70},{0,9,236},
320 {16,7,9},{0,8,94},{0,8,30},{0,9,156},{20,7,99},{0,8,126},{0,8,62},
321 {0,9,220},{18,7,27},{0,8,110},{0,8,46},{0,9,188},{0,8,14},{0,8,142},
322 {0,8,78},{0,9,252},{96,7,0},{0,8,81},{0,8,17},{21,8,131},{18,7,31},
323 {0,8,113},{0,8,49},{0,9,194},{16,7,10},{0,8,97},{0,8,33},{0,9,162},
324 {0,8,1},{0,8,129},{0,8,65},{0,9,226},{16,7,6},{0,8,89},{0,8,25},
325 {0,9,146},{19,7,59},{0,8,121},{0,8,57},{0,9,210},{17,7,17},{0,8,105},
326 {0,8,41},{0,9,178},{0,8,9},{0,8,137},{0,8,73},{0,9,242},{16,7,4},
327 {0,8,85},{0,8,21},{16,8,258},{19,7,43},{0,8,117},{0,8,53},{0,9,202},
328 {17,7,13},{0,8,101},{0,8,37},{0,9,170},{0,8,5},{0,8,133},{0,8,69},
329 {0,9,234},{16,7,8},{0,8,93},{0,8,29},{0,9,154},{20,7,83},{0,8,125},
330 {0,8,61},{0,9,218},{18,7,23},{0,8,109},{0,8,45},{0,9,186},{0,8,13},
331 {0,8,141},{0,8,77},{0,9,250},{16,7,3},{0,8,83},{0,8,19},{21,8,195},
332 {19,7,35},{0,8,115},{0,8,51},{0,9,198},{17,7,11},{0,8,99},{0,8,35},
333 {0,9,166},{0,8,3},{0,8,131},{0,8,67},{0,9,230},{16,7,7},{0,8,91},
334 {0,8,27},{0,9,150},{20,7,67},{0,8,123},{0,8,59},{0,9,214},{18,7,19},
335 {0,8,107},{0,8,43},{0,9,182},{0,8,11},{0,8,139},{0,8,75},{0,9,246},
336 {16,7,5},{0,8,87},{0,8,23},{64,8,0},{19,7,51},{0,8,119},{0,8,55},
337 {0,9,206},{17,7,15},{0,8,103},{0,8,39},{0,9,174},{0,8,7},{0,8,135},
338 {0,8,71},{0,9,238},{16,7,9},{0,8,95},{0,8,31},{0,9,158},{20,7,99},
339 {0,8,127},{0,8,63},{0,9,222},{18,7,27},{0,8,111},{0,8,47},{0,9,190},
340 {0,8,15},{0,8,143},{0,8,79},{0,9,254},{96,7,0},{0,8,80},{0,8,16},
341 {20,8,115},{18,7,31},{0,8,112},{0,8,48},{0,9,193},{16,7,10},{0,8,96},
342 {0,8,32},{0,9,161},{0,8,0},{0,8,128},{0,8,64},{0,9,225},{16,7,6},
343 {0,8,88},{0,8,24},{0,9,145},{19,7,59},{0,8,120},{0,8,56},{0,9,209},
344 {17,7,17},{0,8,104},{0,8,40},{0,9,177},{0,8,8},{0,8,136},{0,8,72},
345 {0,9,241},{16,7,4},{0,8,84},{0,8,20},{21,8,227},{19,7,43},{0,8,116},
346 {0,8,52},{0,9,201},{17,7,13},{0,8,100},{0,8,36},{0,9,169},{0,8,4},
347 {0,8,132},{0,8,68},{0,9,233},{16,7,8},{0,8,92},{0,8,28},{0,9,153},
348 {20,7,83},{0,8,124},{0,8,60},{0,9,217},{18,7,23},{0,8,108},{0,8,44},
349 {0,9,185},{0,8,12},{0,8,140},{0,8,76},{0,9,249},{16,7,3},{0,8,82},
350 {0,8,18},{21,8,163},{19,7,35},{0,8,114},{0,8,50},{0,9,197},{17,7,11},
351 {0,8,98},{0,8,34},{0,9,165},{0,8,2},{0,8,130},{0,8,66},{0,9,229},
352 {16,7,7},{0,8,90},{0,8,26},{0,9,149},{20,7,67},{0,8,122},{0,8,58},
353 {0,9,213},{18,7,19},{0,8,106},{0,8,42},{0,9,181},{0,8,10},{0,8,138},
354 {0,8,74},{0,9,245},{16,7,5},{0,8,86},{0,8,22},{64,8,0},{19,7,51},
355 {0,8,118},{0,8,54},{0,9,205},{17,7,15},{0,8,102},{0,8,38},{0,9,173},
356 {0,8,6},{0,8,134},{0,8,70},{0,9,237},{16,7,9},{0,8,94},{0,8,30},
357 {0,9,157},{20,7,99},{0,8,126},{0,8,62},{0,9,221},{18,7,27},{0,8,110},
358 {0,8,46},{0,9,189},{0,8,14},{0,8,142},{0,8,78},{0,9,253},{96,7,0},
359 {0,8,81},{0,8,17},{21,8,131},{18,7,31},{0,8,113},{0,8,49},{0,9,195},
360 {16,7,10},{0,8,97},{0,8,33},{0,9,163},{0,8,1},{0,8,129},{0,8,65},
361 {0,9,227},{16,7,6},{0,8,89},{0,8,25},{0,9,147},{19,7,59},{0,8,121},
362 {0,8,57},{0,9,211},{17,7,17},{0,8,105},{0,8,41},{0,9,179},{0,8,9},
363 {0,8,137},{0,8,73},{0,9,243},{16,7,4},{0,8,85},{0,8,21},{16,8,258},
364 {19,7,43},{0,8,117},{0,8,53},{0,9,203},{17,7,13},{0,8,101},{0,8,37},
365 {0,9,171},{0,8,5},{0,8,133},{0,8,69},{0,9,235},{16,7,8},{0,8,93},
366 {0,8,29},{0,9,155},{20,7,83},{0,8,125},{0,8,61},{0,9,219},{18,7,23},
367 {0,8,109},{0,8,45},{0,9,187},{0,8,13},{0,8,141},{0,8,77},{0,9,251},
368 {16,7,3},{0,8,83},{0,8,19},{21,8,195},{19,7,35},{0,8,115},{0,8,51},
369 {0,9,199},{17,7,11},{0,8,99},{0,8,35},{0,9,167},{0,8,3},{0,8,131},
370 {0,8,67},{0,9,231},{16,7,7},{0,8,91},{0,8,27},{0,9,151},{20,7,67},
371 {0,8,123},{0,8,59},{0,9,215},{18,7,19},{0,8,107},{0,8,43},{0,9,183},
372 {0,8,11},{0,8,139},{0,8,75},{0,9,247},{16,7,5},{0,8,87},{0,8,23},
373 {64,8,0},{19,7,51},{0,8,119},{0,8,55},{0,9,207},{17,7,15},{0,8,103},
374 {0,8,39},{0,9,175},{0,8,7},{0,8,135},{0,8,71},{0,9,239},{16,7,9},
375 {0,8,95},{0,8,31},{0,9,159},{20,7,99},{0,8,127},{0,8,63},{0,9,223},
376 {18,7,27},{0,8,111},{0,8,47},{0,9,191},{0,8,15},{0,8,143},{0,8,79},
377 {0,9,255}
378 };
379
380 static const code distfix[32] = {
381 {16,5,1},{23,5,257},{19,5,17},{27,5,4097},{17,5,5},{25,5,1025},
382 {21,5,65},{29,5,16385},{16,5,3},{24,5,513},{20,5,33},{28,5,8193},
383 {18,5,9},{26,5,2049},{22,5,129},{64,5,0},{16,5,2},{23,5,385},
384 {19,5,25},{27,5,6145},{17,5,7},{25,5,1537},{21,5,97},{29,5,24577},
385 {16,5,4},{24,5,769},{20,5,49},{28,5,12289},{18,5,13},{26,5,3073},
386 {22,5,193},{64,5,0}
387 };
wdenk4a5b6a32001-04-28 17:59:11 +0000388
389/*+++++*/
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400390/* inffast.c -- fast decoding
391 * Copyright (C) 1995-2004 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +0000392 * For conditions of distribution and use, see copyright notice in zlib.h
393 */
394
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400395/* Allow machine dependent optimization for post-increment or pre-increment.
396 Based on testing to date,
397 Pre-increment preferred for:
398 - PowerPC G3 (Adler)
399 - MIPS R5000 (Randers-Pehrson)
400 Post-increment preferred for:
401 - none
402 No measurable difference:
403 - Pentium III (Anderson)
404 - M68060 (Nikl)
405 */
406#define OFF 1
407#define PUP(a) *++(a)
Joakim Tjernlundcd514ae2009-11-19 13:22:44 +0100408#define UP_UNALIGNED(a) get_unaligned(++(a))
wdenk4a5b6a32001-04-28 17:59:11 +0000409
410/*
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400411 Decode literal, length, and distance codes and write out the resulting
412 literal and match bytes until either not enough input or output is
413 available, an end-of-block is encountered, or a data error is encountered.
414 When large enough input and output buffers are supplied to inflate(), for
415 example, a 16K input buffer and a 64K output buffer, more than 95% of the
416 inflate execution time is spent in this routine.
wdenk4a5b6a32001-04-28 17:59:11 +0000417
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400418 Entry assumptions:
419
420 state->mode == LEN
421 strm->avail_in >= 6
422 strm->avail_out >= 258
423 start >= strm->avail_out
424 state->bits < 8
425
426 On return, state->mode is one of:
427
428 LEN -- ran out of enough output space or enough available input
429 TYPE -- reached end of block code, inflate() to interpret next block
430 BAD -- error in block data
431
432 Notes:
433
434 - The maximum input bits used by a length/distance pair is 15 bits for the
435 length code, 5 bits for the length extra, 15 bits for the distance code,
436 and 13 bits for the distance extra. This totals 48 bits, or six bytes.
437 Therefore if strm->avail_in >= 6, then there is enough input to avoid
438 checking for available input while decoding.
439
440 - The maximum bytes that a single length/distance pair can output is 258
441 bytes, which is the maximum length that can be coded. inflate_fast()
442 requires strm->avail_out >= 258 for each loop to avoid checking for
443 output space.
wdenk4a5b6a32001-04-28 17:59:11 +0000444 */
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400445void inflate_fast(strm, start)
446z_streamp strm;
447unsigned start; /* inflate()'s starting value for strm->avail_out */
wdenk4a5b6a32001-04-28 17:59:11 +0000448{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400449 struct inflate_state FAR *state;
450 unsigned char FAR *in; /* local strm->next_in */
451 unsigned char FAR *last; /* while in < last, enough input available */
452 unsigned char FAR *out; /* local strm->next_out */
453 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
454 unsigned char FAR *end; /* while out < end, enough space available */
455#ifdef INFLATE_STRICT
456 unsigned dmax; /* maximum distance from zlib header */
wdenk4a5b6a32001-04-28 17:59:11 +0000457#endif
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400458 unsigned wsize; /* window size or zero if not using window */
459 unsigned whave; /* valid bytes in the window */
460 unsigned write; /* window write index */
461 unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
462 unsigned long hold; /* local strm->hold */
463 unsigned bits; /* local strm->bits */
464 code const FAR *lcode; /* local strm->lencode */
465 code const FAR *dcode; /* local strm->distcode */
466 unsigned lmask; /* mask for first level of length codes */
467 unsigned dmask; /* mask for first level of distance codes */
468 code this; /* retrieved table entry */
469 unsigned op; /* code bits, operation, extra bits, or */
470 /* window position, window bytes to copy */
471 unsigned len; /* match length, unused bytes */
472 unsigned dist; /* match distance */
473 unsigned char FAR *from; /* where to copy match from */
wdenk4a5b6a32001-04-28 17:59:11 +0000474
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400475 /* copy state to local variables */
476 state = (struct inflate_state FAR *)strm->state;
477 in = strm->next_in - OFF;
478 last = in + (strm->avail_in - 5);
479 out = strm->next_out - OFF;
480 beg = out - (start - strm->avail_out);
481 end = out + (strm->avail_out - 257);
482#ifdef INFLATE_STRICT
483 dmax = state->dmax;
484#endif
485 wsize = state->wsize;
486 whave = state->whave;
487 write = state->write;
488 window = state->window;
489 hold = state->hold;
490 bits = state->bits;
491 lcode = state->lencode;
492 dcode = state->distcode;
493 lmask = (1U << state->lenbits) - 1;
494 dmask = (1U << state->distbits) - 1;
wdenk4a5b6a32001-04-28 17:59:11 +0000495
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400496 /* decode literals and length/distances until end-of-block or not enough
497 input data or output space */
498 do {
499 if (bits < 15) {
500 hold += (unsigned long)(PUP(in)) << bits;
501 bits += 8;
502 hold += (unsigned long)(PUP(in)) << bits;
503 bits += 8;
504 }
505 this = lcode[hold & lmask];
506 dolen:
507 op = (unsigned)(this.bits);
508 hold >>= op;
509 bits -= op;
510 op = (unsigned)(this.op);
511 if (op == 0) { /* literal */
512 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
513 "inflate: literal '%c'\n" :
514 "inflate: literal 0x%02x\n", this.val));
515 PUP(out) = (unsigned char)(this.val);
516 }
517 else if (op & 16) { /* length base */
518 len = (unsigned)(this.val);
519 op &= 15; /* number of extra bits */
520 if (op) {
521 if (bits < op) {
522 hold += (unsigned long)(PUP(in)) << bits;
523 bits += 8;
524 }
525 len += (unsigned)hold & ((1U << op) - 1);
526 hold >>= op;
527 bits -= op;
528 }
529 Tracevv((stderr, "inflate: length %u\n", len));
530 if (bits < 15) {
531 hold += (unsigned long)(PUP(in)) << bits;
532 bits += 8;
533 hold += (unsigned long)(PUP(in)) << bits;
534 bits += 8;
535 }
536 this = dcode[hold & dmask];
537 dodist:
538 op = (unsigned)(this.bits);
539 hold >>= op;
540 bits -= op;
541 op = (unsigned)(this.op);
542 if (op & 16) { /* distance base */
543 dist = (unsigned)(this.val);
544 op &= 15; /* number of extra bits */
545 if (bits < op) {
546 hold += (unsigned long)(PUP(in)) << bits;
547 bits += 8;
548 if (bits < op) {
549 hold += (unsigned long)(PUP(in)) << bits;
550 bits += 8;
551 }
552 }
553 dist += (unsigned)hold & ((1U << op) - 1);
554#ifdef INFLATE_STRICT
555 if (dist > dmax) {
556 strm->msg = (char *)"invalid distance too far back";
557 state->mode = BAD;
558 break;
559 }
560#endif
561 hold >>= op;
562 bits -= op;
563 Tracevv((stderr, "inflate: distance %u\n", dist));
564 op = (unsigned)(out - beg); /* max distance in output */
565 if (dist > op) { /* see if copy from window */
566 op = dist - op; /* distance back in window */
567 if (op > whave) {
568 strm->msg = (char *)"invalid distance too far back";
569 state->mode = BAD;
570 break;
571 }
572 from = window - OFF;
573 if (write == 0) { /* very common case */
574 from += wsize - op;
575 if (op < len) { /* some from window */
576 len -= op;
577 do {
578 PUP(out) = PUP(from);
579 } while (--op);
580 from = out - dist; /* rest from output */
581 }
582 }
583 else if (write < op) { /* wrap around window */
584 from += wsize + write - op;
585 op -= write;
586 if (op < len) { /* some from end of window */
587 len -= op;
588 do {
589 PUP(out) = PUP(from);
590 } while (--op);
591 from = window - OFF;
592 if (write < len) { /* some from start of window */
593 op = write;
594 len -= op;
595 do {
596 PUP(out) = PUP(from);
597 } while (--op);
598 from = out - dist; /* rest from output */
599 }
600 }
601 }
602 else { /* contiguous in window */
603 from += write - op;
604 if (op < len) { /* some from window */
605 len -= op;
606 do {
607 PUP(out) = PUP(from);
608 } while (--op);
609 from = out - dist; /* rest from output */
610 }
611 }
612 while (len > 2) {
613 PUP(out) = PUP(from);
614 PUP(out) = PUP(from);
615 PUP(out) = PUP(from);
616 len -= 3;
617 }
618 if (len) {
619 PUP(out) = PUP(from);
620 if (len > 1)
621 PUP(out) = PUP(from);
622 }
623 }
624 else {
Joakim Tjernlundcd514ae2009-11-19 13:22:44 +0100625 unsigned short *sout;
626 unsigned long loops;
627
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400628 from = out - dist; /* copy direct from output */
Joakim Tjernlundcd514ae2009-11-19 13:22:44 +0100629 /* minimum length is three */
630 /* Align out addr */
631 if (!((long)(out - 1 + OFF) & 1)) {
632 PUP(out) = PUP(from);
633 len--;
634 }
635 sout = (unsigned short *)(out - OFF);
636 if (dist > 2 ) {
637 unsigned short *sfrom;
638
639 sfrom = (unsigned short *)(from - OFF);
640 loops = len >> 1;
641 do
642 PUP(sout) = UP_UNALIGNED(sfrom);
643 while (--loops);
644 out = (unsigned char *)sout + OFF;
645 from = (unsigned char *)sfrom + OFF;
646 } else { /* dist == 1 or dist == 2 */
647 unsigned short pat16;
648
649 pat16 = *(sout-2+2*OFF);
650 if (dist == 1)
651#if defined(__BIG_ENDIAN)
652 pat16 = (pat16 & 0xff) | ((pat16 & 0xff ) << 8);
653#elif defined(__LITTLE_ENDIAN)
654 pat16 = (pat16 & 0xff00) | ((pat16 & 0xff00 ) >> 8);
655#else
656#error __BIG_ENDIAN nor __LITTLE_ENDIAN is defined
657#endif
658 loops = len >> 1;
659 do
660 PUP(sout) = pat16;
661 while (--loops);
662 out = (unsigned char *)sout + OFF;
663 }
664 if (len & 1)
665 PUP(out) = PUP(from);
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400666 }
667 }
668 else if ((op & 64) == 0) { /* 2nd level distance code */
669 this = dcode[this.val + (hold & ((1U << op) - 1))];
670 goto dodist;
671 }
672 else {
673 strm->msg = (char *)"invalid distance code";
674 state->mode = BAD;
675 break;
676 }
677 }
678 else if ((op & 64) == 0) { /* 2nd level length code */
679 this = lcode[this.val + (hold & ((1U << op) - 1))];
680 goto dolen;
681 }
682 else if (op & 32) { /* end-of-block */
683 Tracevv((stderr, "inflate: end of block\n"));
684 state->mode = TYPE;
685 break;
686 }
687 else {
688 strm->msg = (char *)"invalid literal/length code";
689 state->mode = BAD;
690 break;
691 }
692 } while (in < last && out < end);
wdenk4a5b6a32001-04-28 17:59:11 +0000693
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400694 /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
695 len = bits >> 3;
696 in -= len;
697 bits -= len << 3;
698 hold &= (1U << bits) - 1;
wdenk4a5b6a32001-04-28 17:59:11 +0000699
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400700 /* update state and return */
701 strm->next_in = in + OFF;
702 strm->next_out = out + OFF;
703 strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
704 strm->avail_out = (unsigned)(out < end ?
705 257 + (end - out) : 257 - (out - end));
706 state->hold = hold;
707 state->bits = bits;
708 return;
wdenk4a5b6a32001-04-28 17:59:11 +0000709}
710
711/*
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400712 inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
713 - Using bit fields for code structure
714 - Different op definition to avoid & for extra bits (do & for table bits)
715 - Three separate decoding do-loops for direct, window, and write == 0
716 - Special case for distance > 1 copies to do overlapped load and store copy
717 - Explicit branch predictions (based on measured branch probabilities)
718 - Deferring match copy and interspersed it with decoding subsequent codes
719 - Swapping literal/length else
720 - Swapping window/direct else
721 - Larger unrolled copy loops (three is about right)
722 - Moving len -= 3 statement into middle of loop
wdenk4a5b6a32001-04-28 17:59:11 +0000723 */
wdenk4a5b6a32001-04-28 17:59:11 +0000724
725/*+++++*/
726/* inftrees.c -- generate Huffman trees for efficient decoding
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400727 * Copyright (C) 1995-2005 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +0000728 * For conditions of distribution and use, see copyright notice in zlib.h
729 */
730
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400731#define MAXBITS 15
732/*
733 If you use the zlib library in a product, an acknowledgment is welcome
734 in the documentation of your product. If for some reason you cannot
735 include such an acknowledgment, I would appreciate that you keep this
736 copyright string in the executable of your product.
737 */
wdenk4a5b6a32001-04-28 17:59:11 +0000738
Wolfgang Denkf33b3252009-07-24 14:24:07 +0200739/*
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400740 Build a set of tables to decode the provided canonical Huffman code.
741 The code lengths are lens[0..codes-1]. The result starts at *table,
742 whose indices are 0..2^bits-1. work is a writable array of at least
743 lens shorts, which is used as a work area. type is the type of code
744 to be generated, CODES, LENS, or DISTS. On return, zero is success,
745 -1 is an invalid code, and +1 means that ENOUGH isn't enough. table
746 on return points to the next available entry's address. bits is the
747 requested root table index bits, and on return it is the actual root
748 table index bits. It will differ if the request is greater than the
749 longest code or if it is less than the shortest code.
Wolfgang Denkf33b3252009-07-24 14:24:07 +0200750 */
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400751int inflate_table(type, lens, codes, table, bits, work)
752codetype type;
753unsigned short FAR *lens;
754unsigned codes;
755code FAR * FAR *table;
756unsigned FAR *bits;
757unsigned short FAR *work;
Wolfgang Denkf33b3252009-07-24 14:24:07 +0200758{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400759 unsigned len; /* a code's length in bits */
760 unsigned sym; /* index of code symbols */
761 unsigned min, max; /* minimum and maximum code lengths */
762 unsigned root; /* number of index bits for root table */
763 unsigned curr; /* number of index bits for current table */
764 unsigned drop; /* code bits to drop for sub-table */
765 int left; /* number of prefix codes available */
766 unsigned used; /* code entries in table used */
767 unsigned huff; /* Huffman code */
768 unsigned incr; /* for incrementing code, index */
769 unsigned fill; /* index for replicating entries */
770 unsigned low; /* low bits for current root entry */
771 unsigned mask; /* mask for low root bits */
772 code this; /* table entry for duplication */
773 code FAR *next; /* next available space in table */
774 const unsigned short FAR *base; /* base value table to use */
775 const unsigned short FAR *extra; /* extra bits table to use */
776 int end; /* use base and extra for symbol > end */
777 unsigned short count[MAXBITS+1]; /* number of codes of each length */
778 unsigned short offs[MAXBITS+1]; /* offsets in table for each length */
779 static const unsigned short lbase[31] = { /* Length codes 257..285 base */
780 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
781 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
782 static const unsigned short lext[31] = { /* Length codes 257..285 extra */
783 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 18, 18,
784 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 16, 201, 196};
785 static const unsigned short dbase[32] = { /* Distance codes 0..29 base */
786 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
787 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
788 8193, 12289, 16385, 24577, 0, 0};
789 static const unsigned short dext[32] = { /* Distance codes 0..29 extra */
790 16, 16, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22,
791 23, 23, 24, 24, 25, 25, 26, 26, 27, 27,
792 28, 28, 29, 29, 64, 64};
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -0400793
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400794 /*
795 Process a set of code lengths to create a canonical Huffman code. The
796 code lengths are lens[0..codes-1]. Each length corresponds to the
797 symbols 0..codes-1. The Huffman code is generated by first sorting the
798 symbols by length from short to long, and retaining the symbol order
799 for codes with equal lengths. Then the code starts with all zero bits
800 for the first code of the shortest length, and the codes are integer
801 increments for the same length, and zeros are appended as the length
802 increases. For the deflate format, these bits are stored backwards
803 from their more natural integer increment ordering, and so when the
804 decoding tables are built in the large loop below, the integer codes
805 are incremented backwards.
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -0400806
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400807 This routine assumes, but does not check, that all of the entries in
808 lens[] are in the range 0..MAXBITS. The caller must assure this.
809 1..MAXBITS is interpreted as that code length. zero means that that
810 symbol does not occur in this code.
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -0400811
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -0400812 The codes are sorted by computing a count of codes for each length,
813 creating from that a table of starting indices for each length in the
814 sorted table, and then entering the symbols in order in the sorted
815 table. The sorted table is work[], with that space being provided by
816 the caller.
817
818 The length counts are used for other purposes as well, i.e. finding
819 the minimum and maximum length codes, determining if there are any
820 codes at all, checking for a valid set of lengths, and looking ahead
821 at length counts to determine sub-table sizes when building the
822 decoding tables.
823 */
824
825 /* accumulate lengths for codes (assumes lens[] all in 0..MAXBITS) */
826 for (len = 0; len <= MAXBITS; len++)
827 count[len] = 0;
828 for (sym = 0; sym < codes; sym++)
829 count[lens[sym]]++;
830
831 /* bound code lengths, force root to be within code lengths */
832 root = *bits;
833 for (max = MAXBITS; max >= 1; max--)
834 if (count[max] != 0) break;
835 if (root > max) root = max;
836 if (max == 0) { /* no symbols to code at all */
837 this.op = (unsigned char)64; /* invalid code marker */
838 this.bits = (unsigned char)1;
839 this.val = (unsigned short)0;
840 *(*table)++ = this; /* make a table to force an error */
841 *(*table)++ = this;
842 *bits = 1;
843 return 0; /* no symbols, but wait for decoding to report error */
844 }
845 for (min = 1; min <= MAXBITS; min++)
846 if (count[min] != 0) break;
847 if (root < min) root = min;
848
849 /* check for an over-subscribed or incomplete set of lengths */
850 left = 1;
851 for (len = 1; len <= MAXBITS; len++) {
852 left <<= 1;
853 left -= count[len];
854 if (left < 0) return -1; /* over-subscribed */
855 }
856 if (left > 0 && (type == CODES || max != 1))
857 return -1; /* incomplete set */
858
859 /* generate offsets into symbol table for each length for sorting */
860 offs[1] = 0;
861 for (len = 1; len < MAXBITS; len++)
862 offs[len + 1] = offs[len] + count[len];
863
864 /* sort symbols by length, by symbol order within each length */
865 for (sym = 0; sym < codes; sym++)
866 if (lens[sym] != 0) work[offs[lens[sym]]++] = (unsigned short)sym;
867
868 /*
869 Create and fill in decoding tables. In this loop, the table being
870 filled is at next and has curr index bits. The code being used is huff
871 with length len. That code is converted to an index by dropping drop
872 bits off of the bottom. For codes where len is less than drop + curr,
873 those top drop + curr - len bits are incremented through all values to
874 fill the table with replicated entries.
875
876 root is the number of index bits for the root table. When len exceeds
877 root, sub-tables are created pointed to by the root entry with an index
878 of the low root bits of huff. This is saved in low to check for when a
879 new sub-table should be started. drop is zero when the root table is
880 being filled, and drop is root when sub-tables are being filled.
881
882 When a new sub-table is needed, it is necessary to look ahead in the
883 code lengths to determine what size sub-table is needed. The length
884 counts are used for this, and so count[] is decremented as codes are
885 entered in the tables.
886
887 used keeps track of how many table entries have been allocated from the
888 provided *table space. It is checked when a LENS table is being made
889 against the space in *table, ENOUGH, minus the maximum space needed by
890 the worst case distance code, MAXD. This should never happen, but the
891 sufficiency of ENOUGH has not been proven exhaustively, hence the check.
892 This assumes that when type == LENS, bits == 9.
893
894 sym increments through all symbols, and the loop terminates when
895 all codes of length max, i.e. all codes, have been processed. This
896 routine permits incomplete codes, so another loop after this one fills
897 in the rest of the decoding tables with invalid code markers.
898 */
899
900 /* set up for code type */
901 switch (type) {
902 case CODES:
903 base = extra = work; /* dummy value--not used */
904 end = 19;
905 break;
906 case LENS:
907 base = lbase;
908 base -= 257;
909 extra = lext;
910 extra -= 257;
911 end = 256;
912 break;
913 default: /* DISTS */
914 base = dbase;
915 extra = dext;
916 end = -1;
917 }
918
919 /* initialize state for loop */
920 huff = 0; /* starting code */
921 sym = 0; /* starting code symbol */
922 len = min; /* starting code length */
923 next = *table; /* current table to fill in */
924 curr = root; /* current table index bits */
925 drop = 0; /* current bits to drop from code for index */
926 low = (unsigned)(-1); /* trigger new sub-table when len > root */
927 used = 1U << root; /* use root table entries */
928 mask = used - 1; /* mask for comparing low */
929
930 /* check available table space */
931 if (type == LENS && used >= ENOUGH - MAXD)
932 return 1;
933
934 /* process all codes and make table entries */
935 for (;;) {
936 /* create table entry */
937 this.bits = (unsigned char)(len - drop);
938 if ((int)(work[sym]) < end) {
939 this.op = (unsigned char)0;
940 this.val = work[sym];
941 }
942 else if ((int)(work[sym]) > end) {
943 this.op = (unsigned char)(extra[work[sym]]);
944 this.val = base[work[sym]];
945 }
946 else {
947 this.op = (unsigned char)(32 + 64); /* end of block */
948 this.val = 0;
949 }
950
951 /* replicate for those indices with low len bits equal to huff */
952 incr = 1U << (len - drop);
953 fill = 1U << curr;
954 min = fill; /* save offset to next table */
955 do {
956 fill -= incr;
957 next[(huff >> drop) + fill] = this;
958 } while (fill != 0);
959
960 /* backwards increment the len-bit code huff */
961 incr = 1U << (len - 1);
962 while (huff & incr)
963 incr >>= 1;
964 if (incr != 0) {
965 huff &= incr - 1;
966 huff += incr;
967 }
968 else
969 huff = 0;
970
971 /* go to next symbol, update count, len */
972 sym++;
973 if (--(count[len]) == 0) {
974 if (len == max) break;
975 len = lens[work[sym]];
976 }
977
978 /* create new sub-table if needed */
979 if (len > root && (huff & mask) != low) {
980 /* if first time, transition to sub-tables */
981 if (drop == 0)
982 drop = root;
983
984 /* increment past last table */
985 next += min; /* here min is 1 << curr */
986
987 /* determine length of next table */
988 curr = len - drop;
989 left = (int)(1 << curr);
990 while (curr + drop < max) {
991 left -= count[curr + drop];
992 if (left <= 0) break;
993 curr++;
994 left <<= 1;
995 }
996
997 /* check for enough space */
998 used += 1U << curr;
999 if (type == LENS && used >= ENOUGH - MAXD)
1000 return 1;
1001
1002 /* point entry in root table to sub-table */
1003 low = huff & mask;
1004 (*table)[low].op = (unsigned char)curr;
1005 (*table)[low].bits = (unsigned char)root;
1006 (*table)[low].val = (unsigned short)(next - *table);
1007 }
1008 }
1009
1010 /*
1011 Fill in rest of table for incomplete codes. This loop is similar to the
1012 loop above in incrementing huff for table indices. It is assumed that
1013 len is equal to curr + drop, so there is no loop needed to increment
1014 through high index bits. When the current sub-table is filled, the loop
1015 drops back to the root table to fill in any remaining entries there.
1016 */
1017 this.op = (unsigned char)64; /* invalid code marker */
1018 this.bits = (unsigned char)(len - drop);
1019 this.val = (unsigned short)0;
1020 while (huff != 0) {
1021 /* when done with sub-table, drop back to root table */
1022 if (drop != 0 && (huff & mask) != low) {
1023 drop = 0;
1024 len = root;
1025 next = *table;
1026 this.bits = (unsigned char)len;
1027 }
1028
1029 /* put invalid code marker in table */
1030 next[huff >> drop] = this;
1031
1032 /* backwards increment the len-bit code huff */
1033 incr = 1U << (len - 1);
1034 while (huff & incr)
1035 incr >>= 1;
1036 if (incr != 0) {
1037 huff &= incr - 1;
1038 huff += incr;
1039 }
1040 else
1041 huff = 0;
1042 }
1043
1044 /* set return parameters */
1045 *table += used;
1046 *bits = root;
1047 return 0;
1048}
1049
1050/*+++++*/
1051/* inflate.c -- zlib decompression
1052 * Copyright (C) 1995-2005 Mark Adler
1053 * For conditions of distribution and use, see copyright notice in zlib.h
1054 */
1055local void fixedtables OF((struct inflate_state FAR *state));
1056local int updatewindow OF((z_streamp strm, unsigned out));
1057
1058int ZEXPORT inflateReset(strm)
1059z_streamp strm;
1060{
1061 struct inflate_state FAR *state;
1062
1063 if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
1064 state = (struct inflate_state FAR *)strm->state;
1065 strm->total_in = strm->total_out = state->total = 0;
1066 strm->msg = Z_NULL;
1067 strm->adler = 1; /* to support ill-conceived Java test suite */
1068 state->mode = HEAD;
1069 state->last = 0;
1070 state->havedict = 0;
1071 state->dmax = 32768U;
1072 state->head = Z_NULL;
1073 state->wsize = 0;
1074 state->whave = 0;
1075 state->write = 0;
1076 state->hold = 0;
1077 state->bits = 0;
1078 state->lencode = state->distcode = state->next = state->codes;
Stefan Roesef8526282010-09-08 15:34:58 +02001079 WATCHDOG_RESET();
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001080 Tracev((stderr, "inflate: reset\n"));
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001081 return Z_OK;
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001082}
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04001083
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001084int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
1085z_streamp strm;
1086int windowBits;
1087const char *version;
1088int stream_size;
1089{
1090 struct inflate_state FAR *state;
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04001091
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001092 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;
1100 }
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;
1110 }
1111 else {
1112 state->wrap = (windowBits >> 4) + 1;
1113#ifdef GUNZIP
1114 if (windowBits < 48) windowBits &= 15;
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001115#endif
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04001116 }
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001117 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);
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001125}
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04001126
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001127int ZEXPORT inflateInit_(strm, version, stream_size)
1128z_streamp strm;
1129const char *version;
1130int stream_size;
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001131{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001132 return inflateInit2_(strm, DEF_WBITS, version, stream_size);
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001133}
1134
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001135local void fixedtables(state)
1136struct inflate_state FAR *state;
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001137{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001138 state->lencode = lenfix;
1139 state->lenbits = 9;
1140 state->distcode = distfix;
1141 state->distbits = 5;
1142}
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001143
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001144/*
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.
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04001151
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001152 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.
1157 */
1158local int updatewindow(strm, out)
1159z_streamp strm;
1160unsigned out;
1161{
1162 struct inflate_state FAR *state;
1163 unsigned copy, dist;
1164
1165 state = (struct inflate_state FAR *)strm->state;
1166
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;
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001173 }
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001174
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 }
1181
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;
1206}
1207
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 }
1316
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;
1385{
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 */
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001435#else
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001436 if (
Wolfgang Denkf33b3252009-07-24 14:24:07 +02001437#endif
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001438 ((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;
wdenk4a5b6a32001-04-28 17:59:11 +00001588#endif
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001589 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:
Stefan Roesebe4424c2010-09-08 15:35:31 +02001602 WATCHDOG_RESET();
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001603 if (flush == Z_BLOCK) goto inf_leave;
1604 case TYPEDO:
1605 if (state->last) {
1606 BYTEBITS();
1607 state->mode = CHECK;
1608 break;
1609 }
1610 NEEDBITS(3);
1611 state->last = BITS(1);
1612 DROPBITS(1);
1613 switch (BITS(2)) {
1614 case 0: /* stored block */
1615 Tracev((stderr, "inflate: stored block%s\n",
1616 state->last ? " (last)" : ""));
1617 state->mode = STORED;
1618 break;
1619 case 1: /* fixed block */
1620 fixedtables(state);
1621 Tracev((stderr, "inflate: fixed codes block%s\n",
1622 state->last ? " (last)" : ""));
1623 state->mode = LEN; /* decode codes */
1624 break;
1625 case 2: /* dynamic block */
1626 Tracev((stderr, "inflate: dynamic codes block%s\n",
1627 state->last ? " (last)" : ""));
1628 state->mode = TABLE;
1629 break;
1630 case 3:
1631 strm->msg = (char *)"invalid block type";
1632 state->mode = BAD;
1633 }
1634 DROPBITS(2);
1635 break;
1636 case STORED:
1637 BYTEBITS(); /* go to byte boundary */
1638 NEEDBITS(32);
1639 if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
1640 strm->msg = (char *)"invalid stored block lengths";
1641 state->mode = BAD;
1642 break;
1643 }
1644 state->length = (unsigned)hold & 0xffff;
1645 Tracev((stderr, "inflate: stored length %u\n",
1646 state->length));
1647 INITBITS();
1648 state->mode = COPY;
1649 case COPY:
1650 copy = state->length;
1651 if (copy) {
1652 if (copy > have) copy = have;
1653 if (copy > left) copy = left;
1654 if (copy == 0) goto inf_leave;
1655 zmemcpy(put, next, copy);
1656 have -= copy;
1657 next += copy;
1658 left -= copy;
1659 put += copy;
1660 state->length -= copy;
1661 break;
1662 }
1663 Tracev((stderr, "inflate: stored end\n"));
1664 state->mode = TYPE;
1665 break;
1666 case TABLE:
1667 NEEDBITS(14);
1668 state->nlen = BITS(5) + 257;
1669 DROPBITS(5);
1670 state->ndist = BITS(5) + 1;
1671 DROPBITS(5);
1672 state->ncode = BITS(4) + 4;
1673 DROPBITS(4);
1674#ifndef PKZIP_BUG_WORKAROUND
1675 if (state->nlen > 286 || state->ndist > 30) {
1676 strm->msg = (char *)"too many length or distance symbols";
1677 state->mode = BAD;
1678 break;
1679 }
1680#endif
1681 Tracev((stderr, "inflate: table sizes ok\n"));
1682 state->have = 0;
1683 state->mode = LENLENS;
1684 case LENLENS:
1685 while (state->have < state->ncode) {
1686 NEEDBITS(3);
1687 state->lens[order[state->have++]] = (unsigned short)BITS(3);
1688 DROPBITS(3);
1689 }
1690 while (state->have < 19)
1691 state->lens[order[state->have++]] = 0;
1692 state->next = state->codes;
1693 state->lencode = (code const FAR *)(state->next);
1694 state->lenbits = 7;
1695 ret = inflate_table(CODES, state->lens, 19, &(state->next),
1696 &(state->lenbits), state->work);
1697 if (ret) {
1698 strm->msg = (char *)"invalid code lengths set";
1699 state->mode = BAD;
1700 break;
1701 }
1702 Tracev((stderr, "inflate: code lengths ok\n"));
1703 state->have = 0;
1704 state->mode = CODELENS;
1705 case CODELENS:
1706 while (state->have < state->nlen + state->ndist) {
1707 for (;;) {
1708 this = state->lencode[BITS(state->lenbits)];
1709 if ((unsigned)(this.bits) <= bits) break;
1710 PULLBYTE();
1711 }
1712 if (this.val < 16) {
1713 NEEDBITS(this.bits);
1714 DROPBITS(this.bits);
1715 state->lens[state->have++] = this.val;
1716 }
1717 else {
1718 if (this.val == 16) {
1719 NEEDBITS(this.bits + 2);
1720 DROPBITS(this.bits);
1721 if (state->have == 0) {
1722 strm->msg = (char *)"invalid bit length repeat";
1723 state->mode = BAD;
1724 break;
1725 }
1726 len = state->lens[state->have - 1];
1727 copy = 3 + BITS(2);
1728 DROPBITS(2);
1729 }
1730 else if (this.val == 17) {
1731 NEEDBITS(this.bits + 3);
1732 DROPBITS(this.bits);
1733 len = 0;
1734 copy = 3 + BITS(3);
1735 DROPBITS(3);
1736 }
1737 else {
1738 NEEDBITS(this.bits + 7);
1739 DROPBITS(this.bits);
1740 len = 0;
1741 copy = 11 + BITS(7);
1742 DROPBITS(7);
1743 }
1744 if (state->have + copy > state->nlen + state->ndist) {
1745 strm->msg = (char *)"invalid bit length repeat";
1746 state->mode = BAD;
1747 break;
1748 }
1749 while (copy--)
1750 state->lens[state->have++] = (unsigned short)len;
1751 }
1752 }
1753
1754 /* handle error breaks in while */
1755 if (state->mode == BAD) break;
1756
1757 /* build code tables */
1758 state->next = state->codes;
1759 state->lencode = (code const FAR *)(state->next);
1760 state->lenbits = 9;
1761 ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1762 &(state->lenbits), state->work);
1763 if (ret) {
1764 strm->msg = (char *)"invalid literal/lengths set";
1765 state->mode = BAD;
1766 break;
1767 }
1768 state->distcode = (code const FAR *)(state->next);
1769 state->distbits = 6;
1770 ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1771 &(state->next), &(state->distbits), state->work);
1772 if (ret) {
1773 strm->msg = (char *)"invalid distances set";
1774 state->mode = BAD;
1775 break;
1776 }
1777 Tracev((stderr, "inflate: codes ok\n"));
1778 state->mode = LEN;
1779 case LEN:
Stefan Roesef8526282010-09-08 15:34:58 +02001780 WATCHDOG_RESET();
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001781 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;
wdenk4a5b6a32001-04-28 17:59:11 +00001983}
1984
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001985int ZEXPORT inflateEnd(strm)
1986z_streamp strm;
wdenk4a5b6a32001-04-28 17:59:11 +00001987{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001988 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;
Giuseppe CONDORELLI253cb832009-07-29 06:05:20 -04001992 if (state->window != Z_NULL) {
Stefan Roesef8526282010-09-08 15:34:58 +02001993 WATCHDOG_RESET();
Giuseppe CONDORELLI253cb832009-07-29 06:05:20 -04001994 ZFREE(strm, state->window);
1995 }
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04001996 ZFREE(strm, strm->state);
1997 strm->state = Z_NULL;
1998 Tracev((stderr, "inflate: end\n"));
1999 return Z_OK;
wdenk4a5b6a32001-04-28 17:59:11 +00002000}
2001
2002/*+++++*/
wdenk4a5b6a32001-04-28 17:59:11 +00002003/* zutil.c -- target dependent utility functions for the compression library
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002004 * Copyright (C) 1995-2005 Jean-loup Gailly.
wdenk4a5b6a32001-04-28 17:59:11 +00002005 * For conditions of distribution and use, see copyright notice in zlib.h
2006 */
2007
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002008/* @(#) $Id$ */
wdenk4a5b6a32001-04-28 17:59:11 +00002009
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002010#ifndef NO_DUMMY_DECL
2011struct internal_state {int dummy;}; /* for buggy compilers */
2012#endif
wdenk4a5b6a32001-04-28 17:59:11 +00002013
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002014const char * const z_errmsg[10] = {
2015"need dictionary", /* Z_NEED_DICT 2 */
2016"stream end", /* Z_STREAM_END 1 */
2017"", /* Z_OK 0 */
2018"file error", /* Z_ERRNO (-1) */
2019"stream error", /* Z_STREAM_ERROR (-2) */
2020"data error", /* Z_DATA_ERROR (-3) */
2021"insufficient memory", /* Z_MEM_ERROR (-4) */
2022"buffer error", /* Z_BUF_ERROR (-5) */
2023"incompatible version",/* Z_VERSION_ERROR (-6) */
wdenk4a5b6a32001-04-28 17:59:11 +00002024""};
2025
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002026#ifdef DEBUG
wdenk4a5b6a32001-04-28 17:59:11 +00002027
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002028#ifndef verbose
2029#define verbose 0
2030#endif
2031int z_verbose = verbose;
2032
2033void z_error (m)
2034 char *m;
2035{
2036 fprintf(stderr, "%s\n", m);
Giuseppe CONDORELLI7662eb22009-09-03 07:37:46 -04002037 hang ();
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002038}
2039#endif
2040
2041/* exported to allow conversion of error code to string for compress() and
2042 * uncompress()
2043 */
2044#ifndef MY_ZCALLOC /* Any system without a special alloc function */
2045
2046#ifndef STDC
2047extern voidp malloc OF((uInt size));
2048extern voidp calloc OF((uInt items, uInt size));
2049extern void free OF((voidpf ptr));
2050#endif
2051
2052voidpf zcalloc (opaque, items, size)
2053 voidpf opaque;
2054 unsigned items;
2055 unsigned size;
2056{
2057 if (opaque)
2058 items += size - size; /* make compiler happy */
2059 return sizeof(uInt) > 2 ? (voidpf)malloc(items * size) :
2060 (voidpf)calloc(items, size);
2061}
2062
2063void zcfree (opaque, ptr, nb)
2064 voidpf opaque;
2065 voidpf ptr;
2066 unsigned nb;
2067{
2068 free(ptr);
2069 if (opaque)
2070 return; /* make compiler happy */
2071}
2072
2073#endif /* MY_ZCALLOC */
wdenk4a5b6a32001-04-28 17:59:11 +00002074/*+++++*/
2075/* adler32.c -- compute the Adler-32 checksum of a data stream
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002076 * Copyright (C) 1995-2004 Mark Adler
wdenk4a5b6a32001-04-28 17:59:11 +00002077 * For conditions of distribution and use, see copyright notice in zlib.h
2078 */
2079
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002080/* @(#) $Id$ */
wdenk4a5b6a32001-04-28 17:59:11 +00002081
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002082#define BASE 65521UL /* largest prime smaller than 65536 */
wdenk4a5b6a32001-04-28 17:59:11 +00002083#define NMAX 5552
2084/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
2085
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002086#define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
2087#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
2088#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
2089#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
2090#define DO16(buf) DO8(buf,0); DO8(buf,8);
2091
2092/* use NO_DIVIDE if your processor does not do division in hardware */
2093#ifdef NO_DIVIDE
2094#define MOD(a) \
2095 do { \
2096 if (a >= (BASE << 16)) \
2097 a -= (BASE << 16); \
2098 if (a >= (BASE << 15)) \
2099 a -= (BASE << 15); \
2100 if (a >= (BASE << 14)) \
2101 a -= (BASE << 14); \
2102 if (a >= (BASE << 13)) \
2103 a -= (BASE << 13); \
2104 if (a >= (BASE << 12)) \
2105 a -= (BASE << 12); \
2106 if (a >= (BASE << 11)) \
2107 a -= (BASE << 11); \
2108 if (a >= (BASE << 10)) \
2109 a -= (BASE << 10); \
2110 if (a >= (BASE << 9)) \
2111 a -= (BASE << 9); \
2112 if (a >= (BASE << 8)) \
2113 a -= (BASE << 8); \
2114 if (a >= (BASE << 7)) \
2115 a -= (BASE << 7); \
2116 if (a >= (BASE << 6)) \
2117 a -= (BASE << 6); \
2118 if (a >= (BASE << 5)) \
2119 a -= (BASE << 5); \
2120 if (a >= (BASE << 4)) \
2121 a -= (BASE << 4); \
2122 if (a >= (BASE << 3)) \
2123 a -= (BASE << 3); \
2124 if (a >= (BASE << 2)) \
2125 a -= (BASE << 2); \
2126 if (a >= (BASE << 1)) \
2127 a -= (BASE << 1); \
2128 if (a >= BASE) \
2129 a -= BASE; \
2130 } while (0)
2131#define MOD4(a) \
2132 do { \
2133 if (a >= (BASE << 4)) \
2134 a -= (BASE << 4); \
2135 if (a >= (BASE << 3)) \
2136 a -= (BASE << 3); \
2137 if (a >= (BASE << 2)) \
2138 a -= (BASE << 2); \
2139 if (a >= (BASE << 1)) \
2140 a -= (BASE << 1); \
2141 if (a >= BASE) \
2142 a -= BASE; \
2143 } while (0)
2144#else
2145#define MOD(a) a %= BASE
2146#define MOD4(a) a %= BASE
2147#endif
wdenk4a5b6a32001-04-28 17:59:11 +00002148
2149/* ========================================================================= */
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002150uLong ZEXPORT adler32(adler, buf, len)
wdenk4a5b6a32001-04-28 17:59:11 +00002151 uLong adler;
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002152 const Bytef *buf;
wdenk4a5b6a32001-04-28 17:59:11 +00002153 uInt len;
2154{
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002155 unsigned long sum2;
2156 unsigned n;
wdenk4a5b6a32001-04-28 17:59:11 +00002157
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002158 /* split Adler-32 into component sums */
2159 sum2 = (adler >> 16) & 0xffff;
2160 adler &= 0xffff;
wdenk4a5b6a32001-04-28 17:59:11 +00002161
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002162 /* in case user likes doing a byte at a time, keep it fast */
2163 if (len == 1) {
2164 adler += buf[0];
2165 if (adler >= BASE)
2166 adler -= BASE;
2167 sum2 += adler;
2168 if (sum2 >= BASE)
2169 sum2 -= BASE;
2170 return adler | (sum2 << 16);
Giuseppe CONDORELLIb2011712009-07-23 04:54:45 -04002171 }
Giuseppe CONDORELLIdce3d792009-07-29 08:05:08 -04002172
2173 /* initial Adler-32 value (deferred check for len == 1 speed) */
2174 if (buf == Z_NULL)
2175 return 1L;
2176
2177 /* in case short lengths are provided, keep it somewhat fast */
2178 if (len < 16) {
2179 while (len--) {
2180 adler += *buf++;
2181 sum2 += adler;
2182 }
2183 if (adler >= BASE)
2184 adler -= BASE;
2185 MOD4(sum2); /* only added so many BASE's */
2186 return adler | (sum2 << 16);
2187 }
2188
2189 /* do length NMAX blocks -- requires just one modulo operation */
2190 while (len >= NMAX) {
2191 len -= NMAX;
2192 n = NMAX / 16; /* NMAX is divisible by 16 */
2193 do {
2194 DO16(buf); /* 16 sums unrolled */
2195 buf += 16;
2196 } while (--n);
2197 MOD(adler);
2198 MOD(sum2);
2199 }
2200
2201 /* do remaining bytes (less than NMAX, still just one modulo) */
2202 if (len) { /* avoid modulos if none remaining */
2203 while (len >= 16) {
2204 len -= 16;
2205 DO16(buf);
2206 buf += 16;
2207 }
2208 while (len--) {
2209 adler += *buf++;
2210 sum2 += adler;
2211 }
2212 MOD(adler);
2213 MOD(sum2);
2214 }
2215
2216 /* return recombined sums */
2217 return adler | (sum2 << 16);
wdenk4a5b6a32001-04-28 17:59:11 +00002218}