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