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