"Fossies" - the Fresh Open Source Software Archive

Member "src/Common/Inflate.c" (10 Oct 2018, 45685 Bytes) of package /windows/misc/VeraCrypt_1.23-Hotfix-2_Source.zip:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "Inflate.c" see the Fossies "Dox" file reference documentation.

    1 /* inflate.c -- put in the public domain by Mark Adler */
    2 
    3 /* Decompresses raw data compressed using the DEFLATE algorithm (RFC 1951) */
    4 
    5 /* You can do whatever you like with this source file, though I would
    6    prefer that if you modify it and redistribute it that you include
    7    comments to that effect with your name and the date.  Thank you.
    8 
    9    History:
   10    vers    date          who           what
   11    ----  ---------  --------------  ------------------------------------
   12     a    ~~ Feb 92  M. Adler        used full (large, one-step) lookup table
   13     b1   21 Mar 92  M. Adler        first version with partial lookup tables
   14     b2   21 Mar 92  M. Adler        fixed bug in fixed-code blocks
   15     b3   22 Mar 92  M. Adler        sped up match copies, cleaned up some
   16     b4   25 Mar 92  M. Adler        added prototypes; removed window[] (now
   17                                     is the responsibility of unzip.h--also
   18                                     changed name to slide[]), so needs diffs
   19                                     for unzip.c and unzip.h (this allows
   20                                     compiling in the small model on MSDOS);
   21                                     fixed cast of q in huft_build();
   22     b5   26 Mar 92  M. Adler        got rid of unintended macro recursion.
   23     b6   27 Mar 92  M. Adler        got rid of nextbyte() routine.  fixed
   24                                     bug in inflate_fixed().
   25     c1   30 Mar 92  M. Adler        removed lbits, dbits environment variables.
   26                                     changed BMAX to 16 for explode.  Removed
   27                                     OUTB usage, and replaced it with flush()--
   28                                     this was a 20% speed improvement!  Added
   29                                     an explode.c (to replace unimplod.c) that
   30                                     uses the huft routines here.  Removed
   31                                     register union.
   32     c2    4 Apr 92  M. Adler        fixed bug for file sizes a multiple of 32k.
   33     c3   10 Apr 92  M. Adler        reduced memory of code tables made by
   34                                     huft_build significantly (factor of two to
   35                                     three).
   36     c4   15 Apr 92  M. Adler        added NOMEMCPY do kill use of memcpy().
   37                                     worked around a Turbo C optimization bug.
   38     c5   21 Apr 92  M. Adler        added the WSIZE #define to allow reducing
   39                                     the 32K window size for specialized
   40                                     applications.
   41     c6   31 May 92  M. Adler        added some typecasts to eliminate warnings
   42     c7   27 Jun 92  G. Roelofs      added some more typecasts (444:  MSC bug).
   43     c8    5 Oct 92  J-l. Gailly     added ifdef'd code to deal with PKZIP bug.
   44     c9    9 Oct 92  M. Adler        removed a memory error message (~line 416).
   45     c10  17 Oct 92  G. Roelofs      changed ULONG/UWORD/byte to ulg/ush/uch,
   46                                     removed old inflate, renamed inflate_entry
   47                                     to inflate, added Mark's fix to a comment.
   48    c10.5 14 Dec 92  M. Adler        fix up error messages for incomplete trees.
   49     c11   2 Jan 93  M. Adler        fixed bug in detection of incomplete
   50                                     tables, and removed assumption that EOB is
   51                                     the longest code (bad assumption).
   52     c12   3 Jan 93  M. Adler        make tables for fixed blocks only once.
   53     c13   5 Jan 93  M. Adler        allow all zero length codes (pkzip 2.04c
   54                                     outputs one zero length code for an empty
   55                                     distance tree).
   56     c14  12 Mar 93  M. Adler        made inflate.c standalone with the
   57                                     introduction of inflate.h.
   58    c14b  16 Jul 93  G. Roelofs      added (unsigned) typecast to w at 470.
   59    c14c  19 Jul 93  J. Bush         changed v[N_MAX], l[288], ll[28x+3x] arrays
   60                                     to static for Amiga.
   61    c14d  13 Aug 93  J-l. Gailly     de-complicatified Mark's c[*p++]++ thing.
   62    c14e   8 Oct 93  G. Roelofs      changed memset() to memzero().
   63    c14f  22 Oct 93  G. Roelofs      renamed quietflg to qflag; made Trace()
   64                                     conditional; added inflate_free().
   65    c14g  28 Oct 93  G. Roelofs      changed l/(lx+1) macro to pointer (Cray bug)
   66    c14h   7 Dec 93  C. Ghisler      huft_build() optimizations.
   67    c14i   9 Jan 94  A. Verheijen    set fixed_t{d,l} to NULL after freeing;
   68                     G. Roelofs      check NEXTBYTE macro for EOF.
   69    c14j  23 Jan 94  G. Roelofs      removed Ghisler "optimizations"; ifdef'd
   70                                     EOF check.
   71    c14k  27 Feb 94  G. Roelofs      added some typecasts to avoid warnings.
   72    c14l   9 Apr 94  G. Roelofs      fixed split comments on preprocessor lines
   73                                     to avoid bug in Encore compiler.
   74    c14m   7 Jul 94  P. Kienitz      modified to allow assembler version of
   75                                     inflate_codes() (define ASM_INFLATECODES)
   76    c14n  22 Jul 94  G. Roelofs      changed fprintf to macro for DLL versions
   77    c14o  23 Aug 94  C. Spieler      added a newline to a debug statement;
   78                     G. Roelofs      added another typecast to avoid MSC warning
   79    c14p   4 Oct 94  G. Roelofs      added (voidp *) cast to free() argument
   80    c14q  30 Oct 94  G. Roelofs      changed fprintf macro to MESSAGE()
   81    c14r   1 Nov 94  G. Roelofs      fixed possible redefinition of CHECK_EOF
   82    c14s   7 May 95  S. Maxwell      OS/2 DLL globals stuff incorporated;
   83                     P. Kienitz      "fixed" ASM_INFLATECODES macro/prototype
   84    c14t  18 Aug 95  G. Roelofs      added inflate() to use zlib functions;
   85                                     changed voidp to zvoid; moved huft_build()
   86                                     and huft_free() to end of file
   87    c14u   1 Oct 95  G. Roelofs      moved G into definition of MESSAGE macro
   88    c14v   8 Nov 95  P. Kienitz      changed ASM_INFLATECODES to use a regular
   89                                     call with __G__ instead of a macro
   90     c15   3 Aug 96  M. Adler        fixed bomb-bug on random input data (Adobe)
   91    c15b  24 Aug 96  M. Adler        more fixes for random input data
   92    c15c  28 Mar 97  G. Roelofs      changed USE_ZLIB fatal exit code from
   93                                     PK_MEM2 to PK_MEM3
   94     c16  20 Apr 97  J. Altman       added memzero(v[]) in huft_build()
   95    c16b  29 Mar 98  C. Spieler      modified DLL code for slide redirection
   96 
   97    fork  12 Dec 07                  Adapted for TrueCrypt
   98  */
   99 
  100 
  101 /*
  102    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
  103    method searches for as much of the current string of bytes (up to a
  104    length of 258) in the previous 32K bytes.  If it doesn't find any
  105    matches (of at least length 3), it codes the next byte.  Otherwise, it
  106    codes the length of the matched string and its distance backwards from
  107    the current position.  There is a single Huffman code that codes both
  108    single bytes (called "literals") and match lengths.  A second Huffman
  109    code codes the distance information, which follows a length code.  Each
  110    length or distance code actually represents a base value and a number
  111    of "extra" (sometimes zero) bits to get to add to the base value.  At
  112    the end of each deflated block is a special end-of-block (EOB) literal/
  113    length code.  The decoding process is basically: get a literal/length
  114    code; if EOB then done; if a literal, emit the decoded byte; if a
  115    length then get the distance and emit the referred-to bytes from the
  116    sliding window of previously emitted data.
  117 
  118    There are (currently) three kinds of inflate blocks: stored, fixed, and
  119    dynamic.  The compressor outputs a chunk of data at a time and decides
  120    which method to use on a chunk-by-chunk basis.  A chunk might typically
  121    be 32K to 64K, uncompressed.  If the chunk is uncompressible, then the
  122    "stored" method is used.  In this case, the bytes are simply stored as
  123    is, eight bits per byte, with none of the above coding.  The bytes are
  124    preceded by a count, since there is no longer an EOB code.
  125 
  126    If the data are compressible, then either the fixed or dynamic methods
  127    are used.  In the dynamic method, the compressed data are preceded by
  128    an encoding of the literal/length and distance Huffman codes that are
  129    to be used to decode this block.  The representation is itself Huffman
  130    coded, and so is preceded by a description of that code.  These code
  131    descriptions take up a little space, and so for small blocks, there is
  132    a predefined set of codes, called the fixed codes.  The fixed method is
  133    used if the block ends up smaller that way (usually for quite small
  134    chunks); otherwise the dynamic method is used.  In the latter case, the
  135    codes are customized to the probabilities in the current block and so
  136    can code it much better than the pre-determined fixed codes can.
  137 
  138    The Huffman codes themselves are decoded using a multi-level table
  139    lookup, in order to maximize the speed of decoding plus the speed of
  140    building the decoding tables.  See the comments below that precede the
  141    lbits and dbits tuning parameters.
  142 
  143    GRR:  return values(?)
  144            0  OK
  145            1  incomplete table
  146            2  bad input
  147            3  not enough memory
  148  */
  149 
  150 
  151 /*
  152    Notes beyond the 1.93a appnote.txt:
  153 
  154    1. Distance pointers never point before the beginning of the output
  155       stream.
  156    2. Distance pointers can point back across blocks, up to 32k away.
  157    3. There is an implied maximum of 7 bits for the bit length table and
  158       15 bits for the actual data.
  159    4. If only one code exists, then it is encoded using one bit.  (Zero
  160       would be more efficient, but perhaps a little confusing.)  If two
  161       codes exist, they are coded using one bit each (0 and 1).
  162    5. There is no way of sending zero distance codes--a dummy must be
  163       sent if there are none.  (History: a pre 2.0 version of PKZIP would
  164       store blocks with no distance codes, but this was discovered to be
  165       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
  166       zero distance codes, which is sent as one code of zero bits in
  167       length.
  168    6. There are up to 286 literal/length codes.  Code 256 represents the
  169       end-of-block.  Note however that the static length tree defines
  170       288 codes just to fill out the Huffman codes.  Codes 286 and 287
  171       cannot be used though, since there is no length base or extra bits
  172       defined for them.  Similarily, there are up to 30 distance codes.
  173       However, static trees define 32 codes (all 5 bits) to fill out the
  174       Huffman codes, but the last two had better not show up in the data.
  175    7. Unzip can check dynamic Huffman blocks for complete code sets.
  176       The exception is that a single code would not be complete (see #4).
  177    8. The five bits following the block type is really the number of
  178       literal codes sent minus 257.
  179    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
  180       (1+6+6).  Therefore, to output three times the length, you output
  181       three codes (1+1+1), whereas to output four times the same length,
  182       you only need two codes (1+3).  Hmm.
  183   10. In the tree reconstruction algorithm, Code = Code + Increment
  184       only if BitLength(i) is not zero.  (Pretty obvious.)
  185   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
  186   12. Note: length code 284 can represent 227-258, but length code 285
  187       really is 258.  The last length deserves its own, short code
  188       since it gets used a lot in very redundant files.  The length
  189       258 is special since 258 - 3 (the min match length) is 255.
  190   13. The literal/length and distance code bit lengths are read as a
  191       single stream of lengths.  It is possible (and advantageous) for
  192       a repeat code (16, 17, or 18) to go across the boundary between
  193       the two sets of lengths.
  194  */
  195 
  196 
  197 /* #define DEBUG */
  198 #define INFMOD          /* tell inflate.h to include code to be compiled */
  199 #include "inflate.h"
  200 
  201 
  202 #ifndef WSIZE           /* default is 32K */
  203 #  define WSIZE 0x8000  /* window size--must be a power of two, and at least */
  204 #endif                  /* 32K for zip's deflate method */
  205 
  206 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
  207 #  define wsize G._wsize    /* wsize is a variable */
  208 #else
  209 #  define wsize WSIZE       /* wsize is a constant */
  210 #endif
  211 
  212 
  213 #ifndef NEXTBYTE        /* default is to simply get a byte from stdin */
  214 #  define NEXTBYTE getchar()
  215 #endif
  216 
  217 #ifndef MESSAGE   /* only used twice, for fixed strings--NOT general-purpose */
  218 #  define MESSAGE(str,len,flag)  fprintf(stderr,(char *)(str))
  219 #endif
  220 
  221 #ifndef FLUSH           /* default is to simply write the buffer to stdout */
  222 #  define FLUSH(n) fwrite(redirSlide, 1, n, stdout)  /* return value not used */
  223 #endif
  224 /* Warning: the fwrite above might not work on 16-bit compilers, since
  225    0x8000 might be interpreted as -32,768 by the library function. */
  226 
  227 #ifndef Trace
  228 #  ifdef DEBUG
  229 #    define Trace(x) fprintf x
  230 #  else
  231 #    define Trace(x)
  232 #  endif
  233 #endif
  234 
  235 G_struct G;
  236 uch redirSlide [WSIZE];
  237 
  238 /*---------------------------------------------------------------------------*/
  239 #ifdef USE_ZLIB
  240 
  241 
  242 /*
  243    GRR:  return values for both original inflate() and inflate()
  244            0  OK
  245            1  incomplete table(?)
  246            2  bad input
  247            3  not enough memory
  248  */
  249 
  250 /**************************/
  251 /*  Function inflate()  */
  252 /**************************/
  253 
  254 int inflate(__G)   /* decompress an inflated entry using the zlib routines */
  255     __GDEF
  256 {
  257     int err=Z_OK;
  258 
  259 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
  260     if (G.redirect_slide)
  261         wsize = G.redirect_size, redirSlide = G.redirect_buffer;
  262     else
  263         wsize = WSIZE, redirSlide = slide;
  264 #endif
  265 
  266     G.dstrm.next_out = redirSlide;
  267     G.dstrm.avail_out = wsize;
  268 
  269     G.dstrm.next_in = G.inptr;
  270     G.dstrm.avail_in = G.incnt;
  271 
  272     if (!G.inflInit) {
  273         unsigned i;
  274         int windowBits;
  275 
  276         /* only need to test this stuff once */
  277         if (zlib_version[0] != ZLIB_VERSION[0]) {
  278             Info(slide, 0x21, ((char *)slide,
  279               "error:  incompatible zlib version (expected %s, found %s)\n",
  280               ZLIB_VERSION, zlib_version));
  281             return 3;
  282         } else if (strcmp(zlib_version, ZLIB_VERSION) != 0)
  283             Info(slide, 0x21, ((char *)slide,
  284               "warning:  different zlib version (expected %s, using %s)\n",
  285               ZLIB_VERSION, zlib_version));
  286 
  287         /* windowBits = log2(wsize) */
  288         for (i = ((unsigned)wsize * 2 - 1), windowBits = 0;
  289              !(i & 1);  i >>= 1, ++windowBits);
  290         if ((unsigned)windowBits > (unsigned)15)
  291             windowBits = 15;
  292         else if (windowBits < 8)
  293             windowBits = 8;
  294 
  295         G.dstrm.zalloc = (alloc_func)Z_NULL;
  296         G.dstrm.zfree = (free_func)Z_NULL;
  297 
  298         Trace((stderr, "initializing inflate()\n"));
  299         err = inflateInit2(&G.dstrm, -windowBits);
  300 
  301         if (err == Z_MEM_ERROR)
  302             return 3;
  303         else if (err != Z_OK)
  304             Trace((stderr, "oops!  (inflateInit2() err = %d)\n", err));
  305         G.inflInit = 1;
  306     }
  307 
  308 #ifdef FUNZIP
  309     while (err != Z_STREAM_END) {
  310 #else /* !FUNZIP */
  311     while (G.csize > 0) {
  312         Trace((stderr, "first loop:  G.csize = %ld\n", G.csize));
  313 #endif /* ?FUNZIP */
  314         while (G.dstrm.avail_out > 0) {
  315             err = inflate(&G.dstrm, Z_PARTIAL_FLUSH);
  316 
  317             if (err == Z_DATA_ERROR)
  318                 return 2;
  319             else if (err == Z_MEM_ERROR)
  320                 return 3;
  321             else if (err != Z_OK && err != Z_STREAM_END)
  322                 Trace((stderr, "oops!  (inflate(first loop) err = %d)\n", err));
  323 
  324 #ifdef FUNZIP
  325             if (err == Z_STREAM_END)    /* "END-of-entry-condition" ? */
  326 #else /* !FUNZIP */
  327             if (G.csize <= 0L)          /* "END-of-entry-condition" ? */
  328 #endif /* ?FUNZIP */
  329                 break;
  330 
  331             if (G.dstrm.avail_in <= 0) {
  332                 if (fillinbuf(__G) == 0)
  333                     return 2;  /* no "END-condition" yet, but no more data */
  334 
  335                 G.dstrm.next_in = G.inptr;
  336                 G.dstrm.avail_in = G.incnt;
  337             }
  338             Trace((stderr, "     avail_in = %d\n", G.dstrm.avail_in));
  339         }
  340         FLUSH(wsize - G.dstrm.avail_out);   /* flush slide[] */
  341         Trace((stderr, "inside loop:  flushing %ld bytes (ptr diff = %ld)\n",
  342           (long)(wsize - G.dstrm.avail_out),
  343           (long)(G.dstrm.next_out-(Bytef *)redirSlide)));
  344         G.dstrm.next_out = redirSlide;
  345         G.dstrm.avail_out = wsize;
  346     }
  347 
  348     /* no more input, so loop until we have all output */
  349     Trace((stderr, "beginning final loop:  err = %d\n", err));
  350     while (err != Z_STREAM_END) {
  351         err = inflate(&G.dstrm, Z_PARTIAL_FLUSH);
  352         if (err == Z_DATA_ERROR)
  353             return 2;
  354         else if (err == Z_MEM_ERROR)
  355             return 3;
  356         else if (err == Z_BUF_ERROR) {              /* DEBUG */
  357             Trace((stderr, "zlib inflate() did not detect stream end (%s, %s)\n"
  358               , G.zipfn, G.filename));
  359             break;
  360         } else if (err != Z_OK && err != Z_STREAM_END) {
  361             Trace((stderr, "oops!  (inflate(final loop) err = %d)\n", err));
  362             DESTROYGLOBALS()
  363             EXIT(PK_MEM3);
  364         }
  365         FLUSH(wsize - G.dstrm.avail_out);   /* final flush of slide[] */
  366         Trace((stderr, "final loop:  flushing %ld bytes (ptr diff = %ld)\n",
  367           (long)(wsize - G.dstrm.avail_out),
  368           (long)(G.dstrm.next_out-(Bytef *)redirSlide)));
  369         G.dstrm.next_out = redirSlide;
  370         G.dstrm.avail_out = wsize;
  371     }
  372     Trace((stderr, "total in = %ld, total out = %ld\n", G.dstrm.total_in,
  373       G.dstrm.total_out));
  374 
  375     G.inptr = (uch *)G.dstrm.next_in;
  376     G.incnt = (G.inbuf + INBUFSIZ) - G.inptr;  /* reset for other routines */
  377 
  378     err = inflateReset(&G.dstrm);
  379     if (err != Z_OK)
  380         Trace((stderr, "oops!  (inflateReset() err = %d)\n", err));
  381 
  382     return 0;
  383 }
  384 
  385 
  386 /*---------------------------------------------------------------------------*/
  387 #else /* !USE_ZLIB */
  388 
  389 
  390 /* Function prototypes */
  391 #ifndef OF
  392 #  ifdef __STDC__
  393 #    define OF(a) a
  394 #  else
  395 #    define OF(a) ()
  396 #  endif
  397 #endif /* !OF */
  398 int inflate_codes OF((__GPRO__ struct huft *tl, struct huft *td,
  399                       int bl, int bd));
  400 static int inflate_stored OF((__GPRO));
  401 static int inflate_fixed OF((__GPRO));
  402 static int inflate_dynamic OF((__GPRO));
  403 static int inflate_block OF((__GPRO__ int *e));
  404 
  405 
  406 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
  407    stream to find repeated byte strings.  This is implemented here as a
  408    circular buffer.  The index is updated simply by incrementing and then
  409    and'ing with 0x7fff (32K-1). */
  410 /* It is left to other modules to supply the 32K area.  It is assumed
  411    to be usable as if it were declared "uch slide[32768];" or as just
  412    "uch *slide;" and then malloc'ed in the latter case.  The definition
  413    must be in unzip.h, included above. */
  414 
  415 
  416 /* unsigned wp;  moved to globals.h */     /* current position in slide */
  417 
  418 
  419 /* Tables for deflate from PKZIP's appnote.txt. */
  420 static ZCONST unsigned border[] = { /* Order of the bit length code lengths */
  421         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
  422 static ZCONST ush cplens[] = {  /* Copy lengths for literal codes 257..285 */
  423         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
  424         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
  425         /* note: see note #13 above about the 258 in this list. */
  426 static ZCONST ush cplext[] = {  /* Extra bits for literal codes 257..285 */
  427         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
  428         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
  429 static ZCONST ush cpdist[] = {  /* Copy offsets for distance codes 0..29 */
  430         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
  431         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
  432         8193, 12289, 16385, 24577};
  433 static ZCONST ush cpdext[] = {  /* Extra bits for distance codes */
  434         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
  435         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
  436         12, 12, 13, 13};
  437 
  438 
  439 /* moved to consts.h (included in unzip.c), resp. funzip.c */
  440 #if 1
  441 /* And'ing with mask_bits[n] masks the lower n bits */
  442 ZCONST ush near mask_bits[] = {
  443     0x0000,
  444     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
  445     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
  446 };
  447 #endif /* 0 */
  448 
  449 
  450 /* Macros for inflate() bit peeking and grabbing.
  451    The usage is:
  452 
  453         NEEDBITS(j)
  454         x = b & mask_bits[j];
  455         DUMPBITS(j)
  456 
  457    where NEEDBITS makes sure that b has at least j bits in it, and
  458    DUMPBITS removes the bits from b.  The macros use the variable k
  459    for the number of bits in b.  Normally, b and k are register
  460    variables for speed and are initialized at the begining of a
  461    routine that uses these macros from a global bit buffer and count.
  462 
  463    In order to not ask for more bits than there are in the compressed
  464    stream, the Huffman tables are constructed to only ask for just
  465    enough bits to make up the end-of-block code (value 256).  Then no
  466    bytes need to be "returned" to the buffer at the end of the last
  467    block.  See the huft_build() routine.
  468  */
  469 
  470 /* These have been moved to globals.h */
  471 #if 0
  472 ulg bb;                         /* bit buffer */
  473 unsigned bk;                    /* bits in bit buffer */
  474 #endif
  475 
  476 #ifndef CHECK_EOF
  477 #  define CHECK_EOF   /* default as of 5.13/5.2 */
  478 #endif
  479 
  480 #ifndef CHECK_EOF
  481 #  define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE)<<k;k+=8;}}
  482 #else
  483 #  define NEEDBITS(n) {while(k<(n)){int c=NEXTBYTE;if(c==EOF)return 1;\
  484     b|=((ulg)c)<<k;k+=8;}}
  485 #endif                      /* Piet Plomp:  change "return 1" to "break" */
  486 
  487 #define DUMPBITS(n) {b>>=(n);k-=(n);}
  488 
  489 
  490 /*
  491    Huffman code decoding is performed using a multi-level table lookup.
  492    The fastest way to decode is to simply build a lookup table whose
  493    size is determined by the longest code.  However, the time it takes
  494    to build this table can also be a factor if the data being decoded
  495    are not very long.  The most common codes are necessarily the
  496    shortest codes, so those codes dominate the decoding time, and hence
  497    the speed.  The idea is you can have a shorter table that decodes the
  498    shorter, more probable codes, and then point to subsidiary tables for
  499    the longer codes.  The time it costs to decode the longer codes is
  500    then traded against the time it takes to make longer tables.
  501 
  502    This results of this trade are in the variables lbits and dbits
  503    below.  lbits is the number of bits the first level table for literal/
  504    length codes can decode in one step, and dbits is the same thing for
  505    the distance codes.  Subsequent tables are also less than or equal to
  506    those sizes.  These values may be adjusted either when all of the
  507    codes are shorter than that, in which case the longest code length in
  508    bits is used, or when the shortest code is *longer* than the requested
  509    table size, in which case the length of the shortest code in bits is
  510    used.
  511 
  512    There are two different values for the two tables, since they code a
  513    different number of possibilities each.  The literal/length table
  514    codes 286 possible values, or in a flat code, a little over eight
  515    bits.  The distance table codes 30 possible values, or a little less
  516    than five bits, flat.  The optimum values for speed end up being
  517    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
  518    The optimum values may differ though from machine to machine, and
  519    possibly even between compilers.  Your mileage may vary.
  520  */
  521 
  522 static ZCONST int lbits = 9;    /* bits in base literal/length lookup table */
  523 static ZCONST int dbits = 6;    /* bits in base distance lookup table */
  524 
  525 
  526 #ifndef ASM_INFLATECODES
  527 
  528 #pragma warning(disable:4131)
  529 
  530 int inflate_codes(__G__ tl, td, bl, bd)
  531      __GDEF
  532 struct huft *tl, *td;   /* literal/length and distance decoder tables */
  533 int bl, bd;             /* number of bits decoded by tl[] and td[] */
  534 /* inflate (decompress) the codes in a deflated (compressed) block.
  535    Return an error code or zero if it all goes ok. */
  536 {
  537   register unsigned e;  /* table entry flag/number of extra bits */
  538   unsigned n, d;        /* length and index for copy */
  539   unsigned w;           /* current window position */
  540   struct huft *t;       /* pointer to table entry */
  541   unsigned ml, md;      /* masks for bl and bd bits */
  542   register ulg b;       /* bit buffer */
  543   register unsigned k;  /* number of bits in bit buffer */
  544 
  545 
  546   /* make local copies of globals */
  547   b = G.bb;                       /* initialize bit buffer */
  548   k = G.bk;
  549   w = G.wp;                       /* initialize window position */
  550 
  551 
  552   /* inflate the coded data */
  553   ml = mask_bits[bl];           /* precompute masks for speed */
  554   md = mask_bits[bd];
  555   while (1)                     /* do until end of block */
  556   {
  557     NEEDBITS((unsigned)bl)
  558     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
  559       do {
  560         if (e == 99)
  561           return 1;
  562         DUMPBITS(t->b)
  563         e -= 16;
  564         NEEDBITS(e)
  565       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
  566     DUMPBITS(t->b)
  567     if (e == 16)                /* then it's a literal */
  568     {
  569       redirSlide[w++] = (uch)t->v.n;
  570       if (w == wsize)
  571       {
  572         FLUSH(w);
  573         w = 0;
  574       }
  575     }
  576     else                        /* it's an EOB or a length */
  577     {
  578       /* exit if end of block */
  579       if (e == 15)
  580         break;
  581 
  582       /* get length of block to copy */
  583       NEEDBITS(e)
  584       n = t->v.n + ((unsigned)b & mask_bits[e]);
  585       DUMPBITS(e);
  586 
  587       /* decode distance of block to copy */
  588       NEEDBITS((unsigned)bd)
  589       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
  590         do {
  591           if (e == 99)
  592             return 1;
  593           DUMPBITS(t->b)
  594           e -= 16;
  595           NEEDBITS(e)
  596         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
  597       DUMPBITS(t->b)
  598       NEEDBITS(e)
  599       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
  600       DUMPBITS(e)
  601 
  602       /* do the copy */
  603       do {
  604 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
  605         if (G.redirect_slide) {/* &= w/ wsize unnecessary & wrong if redirect */
  606           if (d >= wsize)
  607             return 1;           /* invalid compressed data */
  608           n -= (e = (e = wsize - (d > w ? d : w)) > n ? n : e);
  609         }
  610         else
  611 #endif
  612           n -= (e = (e = wsize - ((d &= wsize-1) > w ? d : w)) > n ? n : e);
  613 #ifndef NOMEMCPY
  614         if (w - d >= e)         /* (this test assumes unsigned comparison) */
  615         {
  616           memcpy(redirSlide + w, redirSlide + d, e);
  617           w += e;
  618           d += e;
  619         }
  620         else                    /* do it slowly to avoid memcpy() overlap */
  621 #endif /* !NOMEMCPY */
  622           do {
  623             redirSlide[w++] = redirSlide[d++];
  624           } while (--e);
  625         if (w == wsize)
  626         {
  627           FLUSH(w);
  628           w = 0;
  629         }
  630       } while (n);
  631     }
  632   }
  633 
  634 
  635   /* restore the globals from the locals */
  636   G.wp = w;                       /* restore global window pointer */
  637   G.bb = b;                       /* restore global bit buffer */
  638   G.bk = k;
  639 
  640 
  641   /* done */
  642   return 0;
  643 }
  644 
  645 #endif /* ASM_INFLATECODES */
  646 
  647 
  648 
  649 static int inflate_stored(__G)
  650      __GDEF
  651 /* "decompress" an inflated type 0 (stored) block. */
  652 {
  653   unsigned n;           /* number of bytes in block */
  654   unsigned w;           /* current window position */
  655   register ulg b;       /* bit buffer */
  656   register unsigned k;  /* number of bits in bit buffer */
  657 
  658 
  659   /* make local copies of globals */
  660   Trace((stderr, "\nstored block"));
  661   b = G.bb;                       /* initialize bit buffer */
  662   k = G.bk;
  663   w = G.wp;                       /* initialize window position */
  664 
  665 
  666   /* go to byte boundary */
  667   n = k & 7;
  668   DUMPBITS(n);
  669 
  670 
  671   /* get the length and its complement */
  672   NEEDBITS(16)
  673   n = ((unsigned)b & 0xffff);
  674   DUMPBITS(16)
  675   NEEDBITS(16)
  676   if (n != (unsigned)((~b) & 0xffff))
  677     return 1;                   /* error in compressed data */
  678   DUMPBITS(16)
  679 
  680 
  681   /* read and output the compressed data */
  682   while (n--)
  683   {
  684     NEEDBITS(8)
  685     redirSlide[w++] = (uch)b;
  686     if (w == wsize)
  687     {
  688       FLUSH(w);
  689       w = 0;
  690     }
  691     DUMPBITS(8)
  692   }
  693 
  694 
  695   /* restore the globals from the locals */
  696   G.wp = w;                       /* restore global window pointer */
  697   G.bb = b;                       /* restore global bit buffer */
  698   G.bk = k;
  699   return 0;
  700 }
  701 
  702 
  703 /* Globals for literal tables (built once) */
  704 /* Moved to globals.h                      */
  705 #if 0
  706 struct huft *fixed_tl = (struct huft *)NULL;
  707 struct huft *fixed_td;
  708 int fixed_bl, fixed_bd;
  709 #endif
  710 
  711 static int inflate_fixed(__G)
  712      __GDEF
  713 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
  714    either replace this with a custom decoder, or at least precompute the
  715    Huffman tables. */
  716 {
  717   /* if first time, set up tables for fixed blocks */
  718   Trace((stderr, "\nliteral block"));
  719   if (G.fixed_tl == (struct huft *)NULL)
  720   {
  721     int i;                /* temporary variable */
  722     unsigned l[288];      /* length list for huft_build */
  723 
  724     /* literal table */
  725     for (i = 0; i < 144; i++)
  726       l[i] = 8;
  727     for (; i < 256; i++)
  728       l[i] = 9;
  729     for (; i < 280; i++)
  730       l[i] = 7;
  731     for (; i < 288; i++)          /* make a complete, but wrong code set */
  732       l[i] = 8;
  733     G.fixed_bl = 7;
  734     if ((i = huft_build(__G__ l, 288, 257, cplens, cplext,
  735                         &G.fixed_tl, &G.fixed_bl)) != 0)
  736     {
  737       G.fixed_tl = (struct huft *)NULL;
  738       return i;
  739     }
  740 
  741     /* distance table */
  742     for (i = 0; i < 30; i++)      /* make an incomplete code set */
  743       l[i] = 5;
  744     G.fixed_bd = 5;
  745     if ((i = huft_build(__G__ l, 30, 0, cpdist, cpdext,
  746                         &G.fixed_td, &G.fixed_bd)) > 1)
  747     {
  748       huft_free(G.fixed_tl);
  749       G.fixed_tl = (struct huft *)NULL;
  750       return i;
  751     }
  752   }
  753 
  754   /* decompress until an end-of-block code */
  755   return inflate_codes(__G__ G.fixed_tl, G.fixed_td,
  756                              G.fixed_bl, G.fixed_bd) != 0;
  757 }
  758 
  759 
  760 
  761 static int inflate_dynamic(__G)
  762   __GDEF
  763 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
  764 {
  765   int i;                /* temporary variables */
  766   unsigned j;
  767   unsigned l;           /* last length */
  768   unsigned m;           /* mask for bit lengths table */
  769   unsigned n;           /* number of lengths to get */
  770   struct huft *tl;      /* literal/length code table */
  771   struct huft *td;      /* distance code table */
  772   int bl;               /* lookup bits for tl */
  773   int bd;               /* lookup bits for td */
  774   unsigned nb;          /* number of bit length codes */
  775   unsigned nl;          /* number of literal/length codes */
  776   unsigned nd;          /* number of distance codes */
  777 #ifdef PKZIP_BUG_WORKAROUND
  778   unsigned ll[288+32]; /* literal/length and distance code lengths */
  779 #else
  780   unsigned ll[286+30]; /* literal/length and distance code lengths */
  781 #endif
  782   register ulg b;       /* bit buffer */
  783   register unsigned k;  /* number of bits in bit buffer */
  784 
  785 
  786   /* make local bit buffer */
  787   Trace((stderr, "\ndynamic block"));
  788   b = G.bb;
  789   k = G.bk;
  790 
  791 
  792   /* read in table lengths */
  793   NEEDBITS(5)
  794   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
  795   DUMPBITS(5)
  796   NEEDBITS(5)
  797   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
  798   DUMPBITS(5)
  799   NEEDBITS(4)
  800   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
  801   DUMPBITS(4)
  802 #ifdef PKZIP_BUG_WORKAROUND
  803   if (nl > 288 || nd > 32)
  804 #else
  805   if (nl > 286 || nd > 30)
  806 #endif
  807     return 1;                   /* bad lengths */
  808 
  809 
  810   /* read in bit-length-code lengths */
  811   for (j = 0; j < nb; j++)
  812   {
  813     NEEDBITS(3)
  814     ll[border[j]] = (unsigned)b & 7;
  815     DUMPBITS(3)
  816   }
  817   for (; j < 19; j++)
  818     ll[border[j]] = 0;
  819 
  820 
  821   /* build decoding table for trees--single level, 7 bit lookup */
  822   bl = 7;
  823   i = huft_build(__G__ ll, 19, 19, NULL, NULL, &tl, &bl);
  824   if (bl == 0)                        /* no bit lengths */
  825     i = 1;
  826   if (i)
  827   {
  828     if (i == 1)
  829       huft_free(tl);
  830     return i;                   /* incomplete code set */
  831   }
  832 
  833 
  834   /* read in literal and distance code lengths */
  835   n = nl + nd;
  836   m = mask_bits[bl];
  837   i = l = 0;
  838   while ((unsigned)i < n)
  839   {
  840     NEEDBITS((unsigned)bl)
  841     j = (td = tl + ((unsigned)b & m))->b;
  842     DUMPBITS(j)
  843     j = td->v.n;
  844     if (j < 16)                 /* length of code in bits (0..15) */
  845       ll[i++] = l = j;          /* save last length in l */
  846     else if (j == 16)           /* repeat last length 3 to 6 times */
  847     {
  848       NEEDBITS(2)
  849       j = 3 + ((unsigned)b & 3);
  850       DUMPBITS(2)
  851       if ((unsigned)i + j > n)
  852       {
  853         huft_free(tl);
  854         return 1;
  855       }
  856       while (j--)
  857         ll[i++] = l;
  858     }
  859     else if (j == 17)           /* 3 to 10 zero length codes */
  860     {
  861       NEEDBITS(3)
  862       j = 3 + ((unsigned)b & 7);
  863       DUMPBITS(3)
  864       if ((unsigned)i + j > n)
  865       {
  866         huft_free(tl);
  867         return 1;
  868       }
  869       while (j--)
  870         ll[i++] = 0;
  871       l = 0;
  872     }
  873     else                        /* j == 18: 11 to 138 zero length codes */
  874     {
  875       NEEDBITS(7)
  876       j = 11 + ((unsigned)b & 0x7f);
  877       DUMPBITS(7)
  878       if ((unsigned)i + j > n)
  879       {
  880         huft_free(tl);
  881         return 1;
  882       }
  883       while (j--)
  884         ll[i++] = 0;
  885       l = 0;
  886     }
  887   }
  888 
  889 
  890   /* free decoding table for trees */
  891   huft_free(tl);
  892 
  893 
  894   /* restore the global bit buffer */
  895   G.bb = b;
  896   G.bk = k;
  897 
  898 
  899   /* build the decoding tables for literal/length and distance codes */
  900   bl = lbits;
  901   i = huft_build(__G__ ll, nl, 257, cplens, cplext, &tl, &bl);
  902   if (bl == 0)                        /* no literals or lengths */
  903     i = 1;
  904   if (i)
  905   {
  906     if (i == 1) {
  907       //if (!uO.qflag)
  908         MESSAGE((uch *)"(incomplete l-tree)  ", 21L, 1);
  909       huft_free(tl);
  910     }
  911     return i;                   /* incomplete code set */
  912   }
  913   bd = dbits;
  914   i = huft_build(__G__ ll + nl, nd, 0, cpdist, cpdext, &td, &bd);
  915   if (bd == 0 && nl > 257)    /* lengths but no distances */
  916   {
  917     //if (!uO.qflag)
  918       MESSAGE((uch *)"(incomplete d-tree)  ", 21L, 1);
  919     huft_free(tl);
  920     huft_free(td);
  921     return 1;
  922   }
  923   if (i == 1) {
  924 #ifdef PKZIP_BUG_WORKAROUND
  925     i = 0;
  926 #else
  927     //if (!uO.qflag)
  928       MESSAGE((uch *)"(incomplete d-tree)  ", 21L, 1);
  929     huft_free(td);
  930     td = NULL;
  931 #endif
  932   }
  933   if (i)
  934   {
  935     huft_free(tl);
  936     return i;
  937   }
  938 
  939 
  940   /* decompress until an end-of-block code */
  941   i = inflate_codes(__G__ tl, td, bl, bd);
  942 
  943   /* free the decoding tables, return */
  944   huft_free(tl);
  945   huft_free(td);
  946 
  947   if (i)
  948     return 1;
  949 
  950   return 0;
  951 }
  952 
  953 
  954 
  955 static int inflate_block(__G__ e)
  956   __GDEF
  957   int *e;               /* last block flag */
  958 /* decompress an inflated block */
  959 {
  960   unsigned t;           /* block type */
  961   register ulg b;       /* bit buffer */
  962   register unsigned k;  /* number of bits in bit buffer */
  963 
  964 
  965   /* make local bit buffer */
  966   b = G.bb;
  967   k = G.bk;
  968 
  969 
  970   /* read in last block bit */
  971   NEEDBITS(1)
  972   *e = (int)b & 1;
  973   DUMPBITS(1)
  974 
  975 
  976   /* read in block type */
  977   NEEDBITS(2)
  978   t = (unsigned)b & 3;
  979   DUMPBITS(2)
  980 
  981 
  982   /* restore the global bit buffer */
  983   G.bb = b;
  984   G.bk = k;
  985 
  986 
  987   /* inflate that block type */
  988   if (t == 2)
  989     return inflate_dynamic(__G);
  990   if (t == 0)
  991     return inflate_stored(__G);
  992   if (t == 1)
  993     return inflate_fixed(__G);
  994 
  995 
  996   /* bad block type */
  997   return 2;
  998 }
  999 
 1000 
 1001 
 1002 int inflate(__G)
 1003      __GDEF
 1004 /* decompress an inflated entry */
 1005 {
 1006   int e;                /* last block flag */
 1007   int r;                /* result code */
 1008 //#ifdef DEBUG
 1009 //  unsigned h = 0;       /* maximum struct huft's malloc'ed */
 1010 //#endif
 1011 
 1012 #if (defined(DLL) && !defined(NO_SLIDE_REDIR))
 1013   if (G.redirect_slide)
 1014     wsize = G.redirect_size, redirSlide = G.redirect_buffer;
 1015   else
 1016     wsize = WSIZE, redirSlide = slide;   /* how they're #defined if !DLL */
 1017 #endif
 1018 
 1019   /* initialize window, bit buffer */
 1020   G.wp = 0;
 1021   G.bk = 0;
 1022   G.bb = 0;
 1023 
 1024 
 1025   /* decompress until the last block */
 1026   do {
 1027 //#ifdef DEBUG
 1028 //    G.hufts = 0;
 1029 //#endif
 1030     if ((r = inflate_block(__G__ &e)) != 0)
 1031       return r;
 1032 //#ifdef DEBUG
 1033 //    if (G.hufts > h)
 1034 //      h = G.hufts;
 1035 //#endif
 1036   } while (!e);
 1037 
 1038 
 1039   /* flush out redirSlide */
 1040   FLUSH(G.wp);
 1041 
 1042 
 1043   /* return success */
 1044   //Trace((stderr, "\n%u bytes in Huffman tables (%d/entry)\n",
 1045   //       h * sizeof(struct huft), sizeof(struct huft)));
 1046   return 0;
 1047 }
 1048 
 1049 
 1050 
 1051 int inflate_free(__G)
 1052      __GDEF
 1053 {
 1054   if (G.fixed_tl != (struct huft *)NULL)
 1055   {
 1056     huft_free(G.fixed_td);
 1057     huft_free(G.fixed_tl);
 1058     G.fixed_td = G.fixed_tl = (struct huft *)NULL;
 1059   }
 1060   return 0;
 1061 }
 1062 
 1063 #endif /* ?USE_ZLIB */
 1064 
 1065 
 1066 /*
 1067  * GRR:  moved huft_build() and huft_free() down here; used by explode()
 1068  *       and fUnZip regardless of whether USE_ZLIB defined or not
 1069  */
 1070 
 1071 
 1072 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
 1073 #define BMAX 16         /* maximum bit length of any code (16 for explode) */
 1074 #define N_MAX 288       /* maximum number of codes in any set */
 1075 
 1076 
 1077 int huft_build(
 1078   __GDEF
 1079   ZCONST unsigned *b,   /* code lengths in bits (all assumed <= BMAX) */
 1080   unsigned n,           /* number of codes (assumed <= N_MAX) */
 1081   unsigned s,           /* number of simple-valued codes (0..s-1) */
 1082   ZCONST ush *d,        /* list of base values for non-simple codes */
 1083   ZCONST ush *e,        /* list of extra bits for non-simple codes */
 1084   struct huft **t,      /* result: starting table */
 1085   int *m                /* maximum lookup bits, returns actual */
 1086   )
 1087 /* Given a list of code lengths and a maximum table size, make a set of
 1088    tables to decode that set of codes.  Return zero on success, one if
 1089    the given code set is incomplete (the tables are still built in this
 1090    case), two if the input is invalid (all zero length codes or an
 1091    oversubscribed set of lengths), and three if not enough memory.
 1092    The code with value 256 is special, and the tables are constructed
 1093    so that no bits beyond that code are fetched when that code is
 1094    decoded. */
 1095 {
 1096   unsigned a;                   /* counter for codes of length k */
 1097   unsigned c[BMAX+1];           /* bit length count table */
 1098   unsigned el;                  /* length of EOB code (value 256) */
 1099   unsigned f;                   /* i repeats in table every f entries */
 1100   int g;                        /* maximum code length */
 1101   int h;                        /* table level */
 1102   register unsigned i;          /* counter, current code */
 1103   register unsigned j;          /* counter */
 1104   register int k;               /* number of bits in current code */
 1105   int lx[BMAX+1];               /* memory for l[-1..BMAX-1] */
 1106   int *l = lx+1;                /* stack of bits per table */
 1107   register unsigned *p;         /* pointer into c[], b[], or v[] */
 1108   register struct huft *q;      /* points to current table */
 1109   struct huft r;                /* table entry for structure assignment */
 1110   struct huft *u[BMAX];         /* table stack */
 1111   unsigned v[N_MAX];            /* values in order of bit length */
 1112   register int w;               /* bits before this table == (l * h) */
 1113   unsigned x[BMAX+1];           /* bit offsets, then code stack */
 1114   unsigned *xp;                 /* pointer into x */
 1115   int y;                        /* number of dummy codes added */
 1116   unsigned z;                   /* number of entries in current table */
 1117 
 1118 
 1119   /* Generate counts for each bit length */
 1120   el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */
 1121   memset(c, 0, sizeof(c));
 1122   p = (unsigned *)b;  i = n;
 1123   do {
 1124     c[*p]++; p++;               /* assume all entries <= BMAX */
 1125   } while (--i);
 1126   if (c[0] == n)                /* null input--all zero length codes */
 1127   {
 1128     *t = (struct huft *)NULL;
 1129     *m = 0;
 1130     return 0;
 1131   }
 1132 
 1133 
 1134   /* Find minimum and maximum length, bound *m by those */
 1135   for (j = 1; j <= BMAX; j++)
 1136     if (c[j])
 1137       break;
 1138   k = j;                        /* minimum code length */
 1139   if ((unsigned)*m < j)
 1140     *m = j;
 1141   for (i = BMAX; i; i--)
 1142     if (c[i])
 1143       break;
 1144   g = i;                        /* maximum code length */
 1145   if ((unsigned)*m > i)
 1146     *m = i;
 1147 
 1148 
 1149   /* Adjust last length count to fill out codes, if needed */
 1150   for (y = 1 << j; j < i; j++, y <<= 1)
 1151     if ((y -= c[j]) < 0)
 1152       return 2;                 /* bad input: more codes than bits */
 1153   if ((y -= c[i]) < 0)
 1154     return 2;
 1155   c[i] += y;
 1156 
 1157 
 1158   /* Generate starting offsets into the value table for each length */
 1159   x[1] = j = 0;
 1160   p = c + 1;  xp = x + 2;
 1161   while (--i) {                 /* note that i == g from above */
 1162     *xp++ = (j += *p++);
 1163   }
 1164 
 1165 
 1166   /* Make a table of values in order of bit lengths */
 1167   memset(v, 0, sizeof(v));
 1168   p = (unsigned *)b;  i = 0;
 1169   do {
 1170     if ((j = *p++) != 0)
 1171       v[x[j]++] = i;
 1172   } while (++i < n);
 1173   n = x[g];                     /* set n to length of v */
 1174 
 1175 
 1176   /* Generate the Huffman codes and for each, make the table entries */
 1177   x[0] = i = 0;                 /* first Huffman code is zero */
 1178   p = v;                        /* grab values in bit order */
 1179   h = -1;                       /* no tables yet--level -1 */
 1180   w = l[-1] = 0;                /* no bits decoded yet */
 1181   u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
 1182   q = (struct huft *)NULL;      /* ditto */
 1183   z = 0;                        /* ditto */
 1184 
 1185   /* go through the bit lengths (k already is bits in shortest code) */
 1186   for (; k <= g; k++)
 1187   {
 1188     a = c[k];
 1189     while (a--)
 1190     {
 1191       /* here i is the Huffman code of length k bits for value *p */
 1192       /* make tables up to required level */
 1193       while (k > w + l[h])
 1194       {
 1195         w += l[h++];            /* add bits already decoded */
 1196 
 1197         /* compute minimum size table less than or equal to *m bits */
 1198         z = (z = g - w) > (unsigned)*m ? *m : z;        /* upper limit */
 1199         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
 1200         {                       /* too few codes for k-w bit table */
 1201           f -= a + 1;           /* deduct codes from patterns left */
 1202           xp = c + k;
 1203           while (++j < z)       /* try smaller tables up to z bits */
 1204           {
 1205             if ((f <<= 1) <= *++xp)
 1206               break;            /* enough codes to use up j bits */
 1207             f -= *xp;           /* else deduct codes from patterns */
 1208           }
 1209         }
 1210         if ((unsigned)w + j > el && (unsigned)w < el)
 1211           j = el - w;           /* make EOB code end at table */
 1212         z = 1 << j;             /* table entries for j-bit table */
 1213         l[h] = j;               /* set table size in stack */
 1214 
 1215         /* allocate and link in new table */
 1216         if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
 1217             (struct huft *)NULL)
 1218         {
 1219           if (h)
 1220             huft_free(u[0]);
 1221           return 3;             /* not enough memory */
 1222         }
 1223 //#ifdef DEBUG
 1224 //        G.hufts += z + 1;         /* track memory usage */
 1225 //#endif
 1226         *t = q + 1;             /* link to list for huft_free() */
 1227         *(t = &(q->v.t)) = (struct huft *)NULL;
 1228         u[h] = ++q;             /* table starts after link */
 1229 
 1230         /* connect to last table, if there is one */
 1231         if (h)
 1232         {
 1233           x[h] = i;             /* save pattern for backing up */
 1234           r.b = (uch)l[h-1];    /* bits to dump before this table */
 1235           r.e = (uch)(16 + j);  /* bits in this table */
 1236           r.v.t = q;            /* pointer to this table */
 1237           j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
 1238           u[h-1][j] = r;        /* connect to last table */
 1239         }
 1240       }
 1241 
 1242       /* set up table entry in r */
 1243       r.b = (uch)(k - w);
 1244       if (p >= v + n)
 1245         r.e = 99;               /* out of values--invalid code */
 1246       else if (*p < s)
 1247       {
 1248         r.e = (uch)(*p < 256 ? 16 : 15);  /* 256 is end-of-block code */
 1249         r.v.n = (ush)*p++;                /* simple code is just the value */
 1250       }
 1251       else
 1252       {
 1253         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
 1254         r.v.n = d[*p++ - s];
 1255       }
 1256 
 1257       /* fill code-like entries with r */
 1258       f = 1 << (k - w);
 1259       for (j = i >> w; j < z; j += f)
 1260         q[j] = r;
 1261 
 1262       /* backwards increment the k-bit code i */
 1263       for (j = 1 << (k - 1); i & j; j >>= 1)
 1264         i ^= j;
 1265       i ^= j;
 1266 
 1267       /* backup over finished tables */
 1268       while ((i & ((1 << w) - 1)) != x[h])
 1269         w -= l[--h];            /* don't need to update q */
 1270     }
 1271   }
 1272 
 1273 
 1274   /* return actual size of base table */
 1275   *m = l[0];
 1276 
 1277 
 1278   /* Return true (1) if we were given an incomplete table */
 1279   return y != 0 && g != 1;
 1280 }
 1281 
 1282 
 1283 
 1284 int huft_free (struct huft *t)
 1285          /* table to free */
 1286 /* Free the malloc'ed tables built by huft_build(), which makes a linked
 1287    list of the tables it made, with the links in a dummy first entry of
 1288    each table. */
 1289 {
 1290   register struct huft *p, *q;
 1291 
 1292 
 1293   /* Go through linked list, freeing from the malloced (t[-1]) address. */
 1294   p = t;
 1295   while (p != (struct huft *)NULL)
 1296   {
 1297     q = (--p)->v.t;
 1298     free((zvoid *)p);
 1299     p = q;
 1300   }
 1301   return 0;
 1302 }
 1303 
 1304 
 1305 // Main public function. Decompresses raw data compressed using the DEFLATE algorithm (RFC 1951 - e.g. zlib, gzip).
 1306 // Returns 0 if decompression fails or, if successful, returns the size of the decompressed data.
 1307 int DecompressDeflatedData (char *out, char *in, int inLength)
 1308 {
 1309     G.outbufptr = out;
 1310     G.inptr = in;
 1311     G.incnt = inLength;
 1312     G.outCounter = 0;
 1313 
 1314     if (inflate(__G) != 0)
 1315     {
 1316         // Error decompressing
 1317         return 0;
 1318     }
 1319     return G.outCounter;
 1320 }
 1321