lib_generic/zlib.c

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