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