/*
 * inflate.c -- Not copyrighted 1992,1993 by Mark Adler
 * Latest hacking on this version by Colin Plumb
 * version p3, 19 Oct 1995
 *
 * $Id: pgpZInflate.c,v 1.23 1999/03/22 16:47:03 hal Exp $
 */


/*
 * You can do whatever you like with this source file, though I would
 * prefer that if you modify it and redistribute it that you include
 * comments to that effect with your name and the date.  Thank you.
 *
 * History:
 * vers    date          who           what
 * ----  ---------  --------------  ------------------------------------
 *  a    ~~ Feb 92  M. Adler        used full (large, one-step) lookup table
 *  b1   21 Mar 92  M. Adler        first version with partial lookup tables
 *  b2   21 Mar 92  M. Adler        fixed bug in fixed-code blocks
 *  b3   22 Mar 92  M. Adler        sped up match copies, cleaned up some
 *  b4   25 Mar 92  M. Adler        added prototypes; removed window[] (now
 *                                  is the responsibility of unzip.h--also
 *                                  changed name to slide[]), so needs diffs
 *                                  for unzip.c and unzip.h (this allows
 *                                  compiling in the small model on MSDOS);
 *                                  fixed cast of q in huft_build();
 *  b5   26 Mar 92  M. Adler        got rid of unintended macro recursion.
 *  b6   27 Mar 92  M. Adler        got rid of nextbyte() routine.  fixed
 *                                  bug in inflate_fixed().
 *  c1   30 Mar 92  M. Adler        removed lbits, dbits environment variables.
 *                                  changed BMAX to 16 for explode.  Removed
 *                                  OUTB usage, and replaced it with flush()--
 *                                  this was a 20% speed improvement!  Added
 *                                  an explode.c (to replace unimplode.c) that
 *                                  uses the huft routines here.  Removed
 *                                  register union.
 *  c2    4 Apr 92  M. Adler        fixed bug for file sizes a multiple of 32k.
 *  c3   10 Apr 92  M. Adler        reduced memory of code tables made by
 *                                  huft_build significantly (factor of two to
 *                                  three).
 *  c4   15 Apr 92  M. Adler        added NOMEMCPY do kill use of memcpy().
 *                                  worked around a Turbo C optimization bug.
 *  c5   21 Apr 92  M. Adler        added the WSIZE #define to allow reducing
 *                                  the 32K window size for specialized
 *                                  applications.
 *  c6   31 May 92  M. Adler        added some typecasts to eliminate warnings
 *  c7   27 Jun 92  G. Roelofs      added some more typecasts (444:  MSC bug).
 *  c8    5 Oct 92  J-l. Gailly     added ifdef'd code to deal with PKZIP bug.
 *  c9    9 Oct 92  M. Adler        removed a memory error message (~line 416).
 *  c10  17 Oct 92  G. Roelofs      changed ULONG/UWORD/byte to ulg/ush/uch,
 *                                  removed old inflate, renamed inflate_entry
 *                                  to inflate, added Mark's fix to a comment.
 *  c11   2 Jan 93  M. Adler        fixed bug in detection of incomplete
 *                                  tables, and removed assumption that EOB is
 *                                  the longest code (bad assumption).
 *  c12   3 Jan 93  M. Adler        make tables for fixed blocks only once.
 *  c13   5 Jan 93  M. Adler        allow all zero length codes (pkzip 2.04c
 *                                  outputs one zero length code for an empty
 *                                  distance tree).
 *  c14  12 Mar 93  M. Adler        made inflate.c standalone with the
 *                                  introduction of inflate.h.
 *  d0   25 Apr 93  M. Adler        several speedups in inflate_codes of
 *                                  almost 20% (suggested by Urban Mueller)--
 *                                  now requires the use of backfill.[ch]
 *  d1    4 May 93  M. Adler        deleted extraneous statement in cheap loop,
 *                                  optimized common copy a little more.
 *  d2    5 May 93  M. Adler        calculate number of cheap loops, a few
 *                                  other small optimizations.
 *  p1      Nov 93  C. Plumb        Adpated to be able to suspend itself.
 *                                  Pretty massive reorganization.
 *                                  Many comments added.
 *  p2   18 Oct 95  C. Plumb        Improved interface some more.  Now
 *                                  nicely re-entrant.  Still more comments.
 *  p3   19 Oct 95  C. Plumb        Changed infInflate core function so that
 *                                  it sucks the input completely dry before
 *                                  returning.  This gets rid of the old ad-hoc
 *                                  technique for flushing out the last little
 *                                  bit of a compressed file by padding it
 *                                  with some dummy data, which was ugly.
 */


/*
 * Inflate deflated (PKZIP's method 8 compressed) data.  The compression
 * method searches for as much of the current string of bytes (up to a
 * length of 258) in the previous 32K bytes.  If it doesn't find any
 * matches (of at least length 3), it codes the next byte.  Otherwise, it
 * codes the length of the matched string and its distance backwards from
 * the current position.  There is a single Huffman code that codes both
 * single bytes (called "literals") and match lengths.  A second Huffman
 * code codes the distance information, which follows a length code.  Each
 * length or distance code actually represents a base value and a number
 * of "extra" (sometimes zero) bits to get to add to the base value.  At
 * the end of each deflated block is a special end-of-block (EOB) literal/
 * length code.  The decoding process is basically: get a literal/length
 * code; if EOB then done; if a literal, emit the decoded byte; if a
 * length then get the distance and emit the referred-to bytes from the
 * sliding window of previously emitted data.
 *
 * There are (currently) three kinds of inflate blocks: stored, fixed, and
 * dynamic.  The compressor outputs a chunk of data at a time and decides
 * which method to use on a chunk-by-chunk basis.  A chunk might typically
 * be 32K to 64K, uncompressed.  If the chunk is uncompressible, then the
 * "stored" method is used.  In this case, the bytes are simply stored as
 * is, eight bits per byte, with none of the above coding.  The bytes are
 * preceded by a (16-bit) count, since there is no longer an EOB code.
 *
 * If the data is compressible, then either the fixed or dynamic methods
 * are used.  In the dynamic method, the compressed data is preceded by
 * an encoding of the literal/length and distance Huffman codes that are
 * to be used to decode this block.  The representation is itself Huffman
 * coded, and so is preceded by a description of that code.  These code
 * descriptions take up a little space, and so for small blocks, there is
 * a predefined set of codes, called the fixed codes.  The fixed method is
 * used if the block ends up smaller that way (usually for quite small
 * chunks); otherwise the dynamic method is used.  In the latter case, the
 * codes are customized to the probabilities in the current block and so
 * can code it much better than the pre-determined fixed codes can.
 *
 * The Huffman codes themselves are decoded using a mutli-level table
 * lookup, in order to maximize the speed of decoding plus the speed of
 * building the decoding tables.  See the comments below that precede the
 * LBITS and DBITS tuning parameters.
 */


/*
 *  Notes beyond the 1.93a appnote.txt:
 *
 *  1. Distance pointers never point before the beginning of the output
 *     stream.
 *  2. Distance pointers can point back across blocks, up to 32k away.
 *  3. There is an implied maximum of 7 bits for the bit length table and
 *     15 bits for the actual data.
 *  4. If only one code exists, then it is encoded using one bit.  (Zero
 *     would be more efficient, but perhaps a little confusing.)  If two
 *     codes exist, they are coded using one bit each (0 and 1).
 *  5. There is no way of sending zero distance codes--a dummy must be
 *     sent if there are none.  (History: a pre 2.0 version of PKZIP would
 *     store blocks with no distance codes, but this was discovered to be
 *     too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
 *     zero distance codes, which is sent as one code of zero bits in
 *     length.
 *  6. There are up to 286 literal/length codes.  Code 256 represents the
 *     end-of-block.  Note however that the static length tree defines
 *     288 codes just to fill out the Huffman codes.  Codes 286 and 287
 *     cannot be used though, since there is no length base or extra bits
 *     defined for them.  Similarily, there are up to 30 distance codes.
 *     However, static trees define 32 codes (all 5 bits) to fill out the
 *     Huffman codes, but the last two had better not show up in the data.
 *  7. Unzip can check dynamic Huffman blocks for complete code sets.
 *     The exception is that a single code would not be complete (see #4).
 *  8. The five bits following the block type is really the number of
 *     literal codes sent minus 257.
 *  9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
 *     (1+6+6).  Therefore, to output three times the length, you output
 *     three codes (1+1+1), whereas to output four times the same length,
 *     you only need two codes (1+3).  Hmm.
 * 10. In the tree reconstruction algorithm, Code = Code + Increment
 *     only if BitLength(i) is not zero.  (Pretty obvious.)
 * 11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
 * 12. Note: length code 284 can represent 227-258, but length code 285
 *     really is 258.  The last length deserves its own, short code
 *     since it gets used a lot in very redundant files.  The length
 *     258 is special since 258 - 3 (the min match length) is 255.
 * 13. The literal/length and distance code bit lengths are read as a
 *     single stream of lengths.  It is possible (and advantageous) for
 *     a repeat code (16, 17, or 18) to go across the boundary between
 *     the two sets of lengths.
 */

#include "pgpConfig.h"

#include <string.h>

#include "pgpDebug.h"
#include "pgpMem.h"
#include "pgpUsuals.h"
#include "pgpZInflate.h"

/* Increasing these only wastes space, so they can be changed if necessary */
typedef PGPUInt16 ush;
typedef PGPUInt32 ulg;


typedef struct huft	huft;
/* Private context structure for use by all functions. */
struct InflateContext {
	PGPContextRef	context;
	/* Major state information */
	int state;
	int substate;
	int lastblock;

	/* static trees*/
	huft *		fixed_tl;
	huft *		fixed_td;
	PGPUInt32	fixed_bl;
	PGPUInt32	fixed_bd;

	/* Output-related information */
	unsigned char *slide;	/* Circular output buffer */
	unsigned char *slideend;
	unsigned slidelen;      /* slideend-slide - MUST BE POWER OF 2 */
	unsigned slidemask;	/* slidelen-1 */
	unsigned char *outptr;	/* Pointer into slide */
	unsigned char const *readptr;	/* Pointer into slide for reading */

	/* Input-related information */
	unsigned char const *inptr;	/* Input pointer */
	int inlen;		/* Input length */
	ulg bitbuffer;
	unsigned bufbits;

	/* The literal/length tree - also used for the bit-length tree */
	huft *tree1;
	unsigned bits1;

	/* The distance tree */
	huft *tree2;
	unsigned bits2;

	/* Encoded huffman tree */
	unsigned char bitlen[286+30];

	/* For dynamic trees */
	unsigned bitlengths;
	unsigned litcodes;
	unsigned distcodes;

	/* Used in various places */
	huft const *t;
	unsigned copylen;
	int distbase;
	int numbits;	/* # of bits in dyn. tree repeat and after dist. code*/
	unsigned index;	/* Position in dynamic tree bit lengths we've read to*/
	DEBUG_STRUCT_CONSTRUCTOR( InflateContext )
};

/* Options for behaviour */
#ifndef SECURE
#define SECURE 1	/* Wipe memory before freeing it? */
#endif

#ifndef WSIZE
#define WSIZE 32768	/* Window size - 32768 for PKZIP compatibility */
#endif

#ifndef STRICT
#define STRICT 1	/* Require unused bits to be zero? */
#endif

/*
 * Huffman code lookup table entry--this entry is four bytes for machines
 * that have 16-bit pointers (e.g. PC's in the small or medium model).
 * Valid extra bits are 0..13.  e == 32 is EOB (end of block), e == 16
 * means that v is a literal, e < 0 means that v is a pointer to the next
 * table, which codes -e bits, and lastly e == -128 indicates an unused
 * code.  If a code with e == -128 is looked up, this implies an error in
 * the data.
 */
struct huft {
	union {
		struct {
			signed char exop; /* # of extra bits or operation */
			char bits;	/* # of bits in this code/subcode */
		} what;
		char *pad;	/* pad structure to a power of 2 (4 bytes for*/
	} word;			/*  16-bit, 8 bytes for 32-bit machines) */
	union {
		ush base;	/* literal, length base, or distance base */
		huft *next; /* pointer to next level of table */
	} more;
};

#define base more.base
#define next more.next
#define exop word.what.exop
#define bits word.what.bits


/* Function prototypes */
#ifndef OF
#  if defined(__STDC__) || defined(__cplusplus)
#    define OF(a) a
#  else
#    define OF(a) ()
#  endif
#endif

static int huft_build OF(( PGPContextRef context,
				unsigned char const *, unsigned, unsigned,
                 ush const *, ush const *, huft **,
                  unsigned *));
static int huft_free OF(( PGPContextRef context, huft *));

/*
 * The inflate algorithm uses a sliding 32K byte window on the uncompressed
 * stream to find repeated byte strings.  This is implemented here as a
 * circular buffer.  The index is updated simply by incrementing and then
 * and'ing with 0x7fff (32K-1).
 */

/* Tables for deflate from PKZIP's appnote.txt. */
static unsigned const border[] = { /* Order of the bit length code lengths */
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};

static ush const cplens[] = { /* Copy lengths for literal codes 257..285 */
	1, 2, 3, 4, 5, 6, 7,  8,  9, 11, 13, 15, 17, 21, 25, 29,
	33, 41, 49, 57, 65, 81, 97, 113, 129, 161, 193, 225, 256, 0, 0};
	/* actually lengths - 2; also see note #13 above about 258 */

static ush const cplext[] = { /* Extra bits for literal codes 257..285 */
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
	3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 128, 128}; /* 128==invalid */

static ush const cpdist[] = { /* Copy offsets for distance codes 0..29 */
	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
	257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
	8193, 12289, 16385, 24577};

static ush const cpdext[] = { /* Extra bits for distance codes */
	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
	7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
	12, 12, 13, 13};

/* And'ing with mask[n] masks the lower n bits */
static unsigned const mask[17] = {
    0x0000,
    0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
    0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};


/* Macros for inflate() bit peeking and grabbing.
 * The usage is:
 *
 *	NEEDBITS(j)
 *	x = b & mask[j];
 *	DUMPBITS(j)
 *
 * where NEEDBITS makes sure that b has at least j bits in it, and
 * DUMPBITS removes the bits from b.  The macros use the variable k
 * for the number of bits in b.  Normally, b and k are register
 * variables for speed, and are initialized at the beginning of a
 * routine that uses these macros from a global bit buffer and count.
 *
 * It is allowed for more bits to be requested than actually used.
 * The remainder stay in the bit buffer.  NOTE that a few more
 * bytes than necessary may be grabbed at the end of input.
 * This should not be fatal as long as the grabbed bits stay
 * in the bit buffer.  The wrapup functions should check for this.

 * There is also the macro GRABBITS which is like NEEDBITS, but uses
 * *g++ to get the byte without checking availability.  This requires
 * using AVAILBYTES first to assure that the needed bytes are there
 * already.  g is set to inptr and then inptr is restored to g around
 * this usage.
 */

/*
 * Variable usage:
 * b = bit buffer, k least-significant bits valid
 * k = # of bits in bit buffer
 * g = grab bits pointer (pointer to next byte to add: b |= *g++ << k)
 * s = # of bytes available
 * ctx = InflateContext
 */

/* Functions to save the state of the bit buffer before returning */
#define LOADBITBUF \
	(b=ctx->bitbuffer, k=ctx->bufbits, g=ctx->inptr, s=ctx->inlen)
#define SAVEBITBUF \
	(ctx->bitbuffer=b, ctx->bufbits=k, ctx->inptr=g, ctx->inlen=s)
#define SAVEBITBUFEMPTY \
	(ctx->bitbuffer=b, ctx->bufbits=k, ctx->inptr=g, ctx->inlen=0)

/*
 * A simple macro to ensure that at least "x" bits are in the bit buffer.
 * Does NOT check for input underflow (s < 0).
 */
#define GRABBITS(x) \
	while (k < x) { \
		--s; \
		b |= (ulg)*g++ << k; \
		k += 8; \
	}

/*
 * Get "x" bits in the input buffer or execute the "whatif" code.
 * NOTE NOTE NOTE that if the "whatif" code is executed, s is set to -1!
 * (This is faster on a lot of machines.)  You will usually have to
 * reset it to 0 manually.
 */
#define GETBITSOR(x, whatif) \
	while (k < (unsigned)(x)) { \
		if (--s < 0) { \
			whatif; \
		} \
		b |= (ulg)*g++ << k; \
		k += 8; \
	}

/*
 * A macro to ensure that there are at least "x" bits available in the
 * bit buffer.  If there are not, the bit buffer is saved back into the
 * context, and any code in "savestate" is run to save any additional
 * context that might be needed.  Then, "return 1" means that more input is
 * needed.
 */
#define NEEDBITS(x, savestate) \
	GETBITSOR(x, savestate; SAVEBITBUFEMPTY; return 1)

/*
 * NEEDBITS2 uses two figures for the number of bits required.  The first,
 * x, is cheap to compute and is used unless we run out of input data.
 * If that happens, the more expensive value, x2, is used.
 */
#define NEEDBITS2(x, x2, savestate) \
	NEEDBITS(x, if (k >= (unsigned)(x2)) {s=0; break;} savestate)

#define DUMPBITS(x) (b >>= x, k -= x)

/*
 * Huffman code decoding is performed using a multi-level table lookup.
 * The fastest way to decode is to simply build a lookup table whose
 * size is determined by the longest code.  However, the time it takes
 * to build this table can also be a factor if the data being decoded
 * is not very long.  The most common codes are necessarily the
 * shortest codes, so those codes dominate the decoding time, and hence
 * the speed.  The idea is you can have a shorter table that decodes the
 * shorter, more probable codes, and then point to subsidiary tables for
 * the longer codes.  The time it costs to decode the longer codes is
 * then traded against the time it takes to make longer tables.
 *
 * This results of this trade are in the values LBITS and DBITS
 * below.  LBITS is the number of bits the first level table for literal/
 * length codes can decode in one step, and DBITS is the same thing for
 * the distance codes.  Subsequent tables are also less than or equal to
 * those sizes.  These values may be adjusted either when all of the
 * codes are shorter than that, in which case the longest code length in
 * bits is used, or when the shortest code is *longer* than the requested
 * table size, in which case the length of the shortest code in bits is
 * used.
 *
 * There are two different values for the two tables, since they code a
 * different number of possibilities each.  The literal/length table
 * codes 286 possible values, or in a flat code, a little over eight
 * bits.  The distance table codes 30 possible values, or a little less
 * than five bits, flat.  The optimum values for speed end up being
 * about one bit more than those, so LBITS is 8+1 and DBITS is 5+1.
 * The optimum values may differ though from machine to machine, and
 * possibly even between compilers.  Your mileage may vary.
 */

#define LBITS 9   /* bits in base literal/length lookup table */
#define DBITS 6   /* bits in base distance lookup table */

/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
#define BMAX 15         /* maximum bit length of any code (16 for explode) */
#define N_MAX 288       /* maximum number of codes in any set */

#if defined(__STDC__) || defined(__cplusplus)
static int
huft_build( PGPContextRef context,
		unsigned char const *b, unsigned n, unsigned s, ush const *d,
	   ush const *e, huft **t, unsigned *m)
#else
static int
huft_build(context, b, n, s, d, e, t, m)
PGPContextRef context;	/* context for memory allocation */
unsigned char *b;       /* code lengths in bits (all assumed <= BMAX) */
unsigned n;             /* number of codes (assumed <= N_MAX) */
unsigned s;             /* number of simple-valued codes (0..s-1) */
ush const *d;           /* list of base values for non-simple codes */
ush const *e;           /* list of extra bits for non-simple codes */
huft **t;        /* result: starting table */
unsigned *m;            /* suggested lookup bits, returns actual */
#endif
/*
 * Given a list of code lengths and a maximum table size, make a set of
 * tables to decode that set of codes.  Return values:
 * 0 = success
 * 1 = the given code set is incomplete
 *     (the tables are still built in this case)
 * 2 = the input is invalid
 *     (all zero length codes or an oversubscribed set of lengths)
 * 3 = not enough memory.
 */
{
  unsigned a;                   /* counter for codes of length k */
  unsigned c[BMAX+1];           /* bit length count table */
  unsigned f;                   /* i repeats in table every f entries */
  int g;                        /* maximum code length */
  int h;                        /* table level */
  register unsigned i;          /* counter, current code */
  register unsigned j;          /* counter */
  register int k;               /* number of bits in current code */
  int l;                        /* bits per table (returned in m) */
  register unsigned char const *bp;	/* pointer into b[] */
  register unsigned *p;         /* pointer into c[] or v[] */
  register huft *q;      /* points to current table */
  huft r;                /* table entry for structure assignment */
  huft *u[BMAX];         /* table stack */
  unsigned v[N_MAX];            /* values in order of bit length */
  register int w;               /* bits before this table == (l * h) */
  unsigned x[BMAX+1];           /* bit offsets, then code stack */
  unsigned *xp;                 /* pointer into x */
  int y;                        /* number of dummy codes added */
  unsigned z;                   /* number of entries in current table */


  /* Generate counts for each bit length */
  pgpClearMemory( c,  sizeof(c));
  bp = b;  i = n;
  do {
    c[*bp++]++;                 /* assume all entries <= BMAX */
  } while (--i);
  if (c[0] == n)                /* null input--all zero length codes */
  {
    *t = (huft *)NULL;
    *m = 0;
    return 0;
  }


  /* Find minimum and maximum length, bound *m by those */
  l = *m;
  for (j = 1; j <= BMAX; j++)
    if (c[j])
      break;
  k = j;                        /* minimum code length */
  if ((unsigned)l < j)
    l = j;
  for (i = BMAX; i; i--)
    if (c[i])
      break;
  g = i;                        /* maximum code length */
  if ((unsigned)l > i)
    l = i;
  *m = l;


  /* Adjust last length count to fill out codes, if needed */
  for (y = 1 << j; j < i; j++, y <<= 1)
    if ((y -= c[j]) < 0)
      return 2;                 /* bad input: more codes than bits */
  if ((y -= c[i]) < 0)
    return 2;
  c[i] += y;


  /* Generate starting offsets into the value table for each length */
  x[1] = j = 0;
  p = c + 1;  xp = x + 2;
  while (--i) {                 /* note that i == g from above */
    *xp++ = (j += *p++);
  }


  /* Make a table of values in order of bit lengths */
  bp = b;  i = 0;
  do {
    if ((j = *bp++) != 0)
      v[x[j]++] = i;
  } while (++i < n);


  /* Generate the Huffman codes and for each, make the table entries */
  x[0] = i = 0;                 /* first Huffman code is zero */
  p = v;                        /* grab values in bit order */
  h = -1;                       /* no tables yet--level -1 */
  w = -l;                       /* bits decoded == (l * h) */
  u[0] = (huft *)NULL;   /* just to keep compilers happy */
  q = (huft *)NULL;      /* ditto */
  z = 0;                        /* ditto */

  /* go through the bit lengths (k already is bits in shortest code) */
  for (; k <= g; k++) {
    a = c[k];
    while (a--) {
      /* here i is the Huffman code of length k bits for value *p */
      /* make tables up to required level */
      while (k > w + l) {
	h++;
	w += l;                 /* previous table always l bits */

	/* compute minimum size table less than or equal to l bits */
	z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
	if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
	{                       /* too few codes for k-w bit table */
	  f -= a + 1;           /* deduct codes from patterns left */
	  xp = c + k;
	  while (++j < z) {     /* try smaller tables up to z bits */
	    if ((f <<= 1) <= *++xp)
	      break;            /* enough codes to use up j bits */
	    f -= *xp;           /* else deduct codes from patterns */
	  }
	}
	z = 1 << j;             /* table entries for j-bit table */

	/* allocate and link in new table */
	if ((q = (huft *)pgpContextMemAlloc( context, (z + 1)*sizeof(huft),
		0)) == (huft *)NULL)
	{
	  if (h)
	    huft_free( context, u[0]);
	  return 3;             /* not enough memory */
	}
#if SECURE
	q->bits = (char)j;	/* Track size for free */
#endif
	*t = q + 1;             /* link to list for huft_free() */
	*(t = &(q->next)) = (huft *)NULL;
	u[h] = ++q;             /* table starts after link */

	/* connect to last table, if there is one */
	if (h) {
	  x[h] = i;             /* save pattern for backing up */
	  r.bits = (char)l;     /* bits to dump before this table */
	  r.exop = -(char)j;    /* bits in this table */
	  r.next = q;           /* pointer to this table */
	  j = i >> (w - l);     /* (get around Turbo C bug) */
	  u[h-1][j] = r;        /* connect to last table */
	}
      }

      /* set up table entry in r */
      r.bits = (char)(k - w);
      if (p >= v + n) {
	r.exop = -128;          /* out of values--invalid code */
      } else if (*p < s) {
	r.exop = (char)(*p < 256 ? 16 : 32);    /* 256 is end-of-block code */
	r.base = *p++;          /* simple code is just the value */
      } else {
	r.exop = (char)e[*p - s];       /* non-simple--look up in lists */
	r.base = d[*p++ - s];
      }

      /* fill code-like entries with r */
      f = 1 << (k - w);
      for (j = i >> w; j < z; j += f)
	q[j] = r;

      /* backwards increment the k-bit code i */
      for (j = 1 << (k - 1); i & j; j >>= 1)
	i ^= j;
      i ^= j;

      /* back up over finished tables */
      while ((i & ((1 << w) - 1)) != x[h]) {
	h--;                    /* don't need to update q */
	w -= l;
      }
    }
  }


  /* Return true (1) if we were given an incomplete table */
  return y != 0 && g != 1;
}


#if defined(__STDC__) || defined(__cplusplus)
static int
huft_free(PGPContextRef context, huft *t)
#else
static int
huft_free( context, t)
PGPContextRef context;	/* context for memory allocation */
huft *t;				/* table to free */
#endif
/*
 * Free the malloc'ed tables built by huft_build(), which makes a linked
 * list of the tables it made, with the links in a dummy -1st entry of
 * each table.
 */
{
  register huft *p, *q;

  /* Go through linked list, freeing from the malloced (t[-1]) address. */
  p = t;
  while (p != (huft *)NULL)
  {
    q = (--p)->next;
#if SECURE
    pgpClearMemory( p,  (1+(1<<p->bits)) * sizeof(*p));
#endif
    pgpContextMemFree( context, p);
    p = q;
  }
  return 0;
}


/*
 * Colin's new code.
 */

#define STATE_START	0
#define	STATE_STOREDLEN	1
#define STATE_STORED	2
#define	STATE_DYN_HDR	3
#define	STATE_DYN_BITS	4
#define STATE_DYN_TREE	5
#define STATE_INFLATE	6
#define STATE_DONE	7
#define STATE_STOP	8

/*
 * All these functions return
 * 2 if the output buffer is full
 * 1 if the input buffer is empty
 *  0 if things should continue with the new ctx->state, and
 * <0 on error.
 */

static int
infStoredLen(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	unsigned t;

	LOADBITBUF;
	t = k & 7;
#if STRICT
	if (b & mask[t])	/* Require unused bits are zero */
		return INFERR_BADINPUT;
#endif
	DUMPBITS(t);

	NEEDBITS(32, (void)0);

	/* At this point, k is exactly 32 */

	ctx->copylen = (unsigned)b & 0xffff;
	t = ~(unsigned)(b>>16) & 0xffff;
	b = 0;
	k = 0;

	SAVEBITBUF;
	if (t != ctx->copylen)
		return INFERR_BADINPUT;	/* Two lengths not identical */

	ctx->state = STATE_STORED;
	ctx->substate = 0;

	return 0;
}

/*
 * Process the data in a stored block.  Copy the input data to
 * the circular buffer, flushing it as necessary.
 */
static int
infStored(InflateContext *ctx)
{
	int len;	/* # of bytes to copy */
	int retval = 1;	/* Out of memory */

	pgpAssert(ctx->bufbits == 0);

	len = ctx->inlen;
	if ((unsigned)len >= ctx->copylen) {
		len = ctx->copylen;	/* Copy done! */
		ctx->state = STATE_START;
		retval = 0;
	}
	if (len > ctx->slideend-ctx->outptr) {
		len = (int)(ctx->slideend-ctx->outptr);
		retval = 2;	/* Output buffer full */
		ctx->state = STATE_STORED;
	}

	memcpy(ctx->outptr, ctx->inptr, len);
	ctx->inptr += len;
	ctx->inlen -= len;
	ctx->outptr += len;
	ctx->copylen -= (unsigned)len;

	/* Return 2 if output full, 1 if input empty, 0 otherwise (copy done)*/
	return retval;
}

static int
infDynHdr(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;

	LOADBITBUF;
	NEEDBITS(14, (void)0);

	ctx->litcodes = 257 + ((unsigned)b & 0x1f);
	DUMPBITS(5);
	ctx->distcodes = 1 + ((unsigned)b & 0x1f);
	DUMPBITS(5);
	ctx->bitlengths = 4 + ((unsigned)b & 0xf);
	DUMPBITS(4);

	SAVEBITBUF;

#ifndef PKZIP_BUG_WORKAROUND
	if (ctx->litcodes > 286 || ctx->distcodes > 30)
		return INFERR_BADINPUT;	/* Bad lengths */
#endif
	ctx->state = STATE_DYN_BITS;
	return 0;
}

/* Load up the ctx->bitlen array with the bit lengths for the encoded
 * trees.  Unpermute them according to the border[] array.
 */
static int
infDynBits(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	huft *t;
	int i, lim;

	LOADBITBUF;
	i = ctx->substate;
	lim = ctx->bitlengths;

	while (i < lim) {
		NEEDBITS(3, ctx->substate=i)
		ctx->bitlen[border[i++]] = (unsigned)b & 7;
		DUMPBITS(3);
	}
	SAVEBITBUF;

	while (i < 19)
		ctx->bitlen[border[i++]] = 0;

	k = 7;	/* Bits in tree table */

	i = huft_build( ctx->context, ctx->bitlen, 19, 19, NULL, NULL, &t, &k);
	if (i) {
		if (i == 1)
			huft_free( ctx->context,t);	/* Incomplete code set */
		return i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;
	}
	ctx->tree1 = t;
	ctx->bits1 = k;

	ctx->state = STATE_DYN_TREE;
	ctx->substate = 0;

	return 0;
}

static int
infFixedTree( InflateContext *	ctx )
{
	int i;
	unsigned char l[288];
	PGPContextRef	context	= ctx->context;

	if ( IsntNull( ctx->fixed_tl ) )
		return 0;	/* All okay */

	/* literal table */
	for (i = 0; i < 144; i++)
		l[i] = 8;
	for (; i < 256; i++)
		l[i] = 9;
	for (; i < 280; i++)
		l[i] = 7;
	for (; i < 288; i++)      /* make a complete, but wrong code set */
		l[i] = 8;
	ctx->fixed_bl = 7;
	i = huft_build( context, l,
		288, 257, cplens, cplext, &ctx->fixed_tl, &ctx->fixed_bl);
	if (i != 0) {
		ctx->fixed_tl = NULL;
		return INFERR_NOMEM;
	}

	/* distance table */
	for (i = 0; i < 30; i++)      /* make an incomplete code set */
		l[i] = 5;
	ctx->fixed_bd = 5;
	i = huft_build( context, l, 30, 0,
			cpdist, cpdext, &ctx->fixed_td, &ctx->fixed_bd);
	if (i > 1) {
		huft_free( context, ctx->fixed_tl);
		ctx->fixed_tl = NULL;
		return INFERR_NOMEM;
	}

	return 0;
}

static int
infDynTree(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	huft *tl, *td;
	unsigned bl, bd;
	unsigned i, j, l, m, lim;

	LOADBITBUF;
	i = ctx->index;
	l = ctx->numbits;	/* Previous # of bits for repeat code use */
	lim = ctx->litcodes + ctx->distcodes;
	tl = ctx->tree1;
	bl = ctx->bits1;
	m = mask[bl];

	switch(ctx->substate) {
	  case 0:
		i = 0;
		l = 0;
		/*FALLTHROUGH*/
	  case 1:
		while (i < lim) {
			NEEDBITS2(bl, tl[(unsigned)b & m].bits,
				ctx->index=i; ctx->numbits=l; ctx->substate=1)
			td = tl + ((unsigned)b & m);
			j = td->bits;
			DUMPBITS(j);
			j = td->base;
			if (j < 16) {
				ctx->bitlen[i++] = l = j;
			} else if (j == 16) {	/* 3 to 6 repeats */
				/*FALLTHROUGH*/
	  case 2:
				NEEDBITS(2, ctx->index=i; ctx->numbits=l;
							ctx->substate=2)
				j = 3 + ((unsigned)b & 3);
				DUMPBITS(2);
				if (i + j > lim)
					return INFERR_BADINPUT;
				do {
					ctx->bitlen[i++] = (unsigned char)l;
				} while (--j);
			} else if (j == 17) {	/* 3 to 10 zeros */
				/*FALLTHROUGH*/
	  case 3:
				NEEDBITS(3, ctx->index=i; ctx->substate=3)
				j = 3 + ((unsigned)b & 7);
				DUMPBITS(3);
				if (i + j > lim)
					return INFERR_BADINPUT;
				do {
					ctx->bitlen[i++] = 0;
				} while (--j);
				l = 0;
			} else {	/* j == 18 -- 11 to 138 zeros */
				pgpAssert(j == 18);
				/*FALLTHROUGH*/
	  case 4:
				NEEDBITS(7, ctx->index=i; ctx->substate=4)
				j = 11 + ((unsigned)b & 127);
				DUMPBITS(7);
				if (i + j > lim)
					return INFERR_BADINPUT;
				do {
					ctx->bitlen[i++] = 0;
				} while (--j);
				l = 0;
			}
		}
	}

	/* Input finished */
	SAVEBITBUF;
	huft_free( ctx->context, tl);
	ctx->tree1 = 0;

	/* Now build the trees - literal/length, then distance */

	bl = LBITS;
	i = huft_build( ctx->context, ctx->bitlen, ctx->litcodes, 257,
		       cplens, cplext, &tl, &bl);
	if (i != 0) {
		if (i == 1)
			huft_free(ctx->context, tl);
		return i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;
	}
	bd = DBITS;
	i = huft_build( ctx->context, ctx->bitlen+ctx->litcodes, ctx->distcodes, 0,
		       cpdist, cpdext, &td, &bd);
#ifdef PKZIP_BUG_WORKAROUND
	if (i > 1) {
#else
	if (i != 0) {
		if (i == 1)
			huft_free(ctx->context, td);
#endif
		huft_free( ctx->context, tl);
		return i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;
	}
	ctx->tree1 = tl;
	ctx->bits1 = bl;
	ctx->tree2 = td;
	ctx->bits2 = bd;

	ctx->state = STATE_INFLATE;
	ctx->substate = 0;

	return 0;
}

/*
 * This is the heart of ZIP inflation.  The code is heavily optimized
 * for speed, including for many brain-damaged compilers that can only
 * optimize one statement at a time.  To generate better code from
 * such idiot compilers (which are distressingly common on platforms
 * such as MS-DOS), expressions are made big and complex, and intermediate
 * results are ssigned to variables in the expression where possible
 * so the compiler won't try to use a disjoint temporary and have to
 * spill.  This makes the code a little hard to follow at times.
 * Sorry.
 *
 * Also, due to the deep nesting (it's all in one function, again, for
 * speed even on systems that can't inline), the indent amount is only
 * two spaces and variable names are very short.
 *
 * This does NOT currently detect a reference to before the beginning of
 * the file.  It just blindly uses the circular buffer.
 */
static int
infInflate(InflateContext *ctx)
{
  ulg b;		/* Bit buffer info - bit buffer itself */
  unsigned k;		/* Number of low0order bits of b that are valid */
  int s;		/* Bytes of valid input remaining */
  unsigned char const *g;	/* Input buffer pointer */

  unsigned char *w;	/* Window output write pointer */
  unsigned r;		/* Space available after w (always >0) */

  huft *tl, *td;	/* Tree info (const except for EOB processing) */
  unsigned bl, bd;
  unsigned ml, md;
  huft const *t;	/* Temporary tree pointer */

  unsigned char const *p;	/* Copy source pointer */
  int i;
  int e;
  unsigned n;		/* Copy length */
  unsigned d;		/* Copy distance */

  LOADBITBUF;		/* Load b, k, s, g */

  w = ctx->outptr;
  r = ctx->slideend-w;
  pgpAssert(r);

  tl = ctx->tree1;	/* Literal/length tree */
  bl = ctx->bits1;	/* Number of bits in top-level table */
  ml = mask[bl];	/* Mask of that many bits */

  td = ctx->tree2;	/* Distance tree */
  bd = ctx->bits2;	/* Number of bits in top-level table */
  md = mask[bd];	/* Mask of that many bits */

  /*
   * We don't always need all of these, but it's easier to always
   * load them than to do it conditionally.
   */
  t = ctx->t;
  n = ctx->copylen;
  d = ctx->distbase;
  e = ctx->numbits;

  switch (ctx->substate) {
  case 0:
    for (;;) {                     /* do until end of block */
      /*
       * This cheap loop does no input or output checking.
       * At most 258 bytes of output are produced per iteration,
       * so we must do no more than r/258 iterations.
       * Also, at most 15+5+15+13 = 48 bits = 6 bytes are consumed
       * every iteration, so we can do no more than s/6 iterations.
       * Also, to allow for starting with an empty bit buffer and
       * ending with a full one, subtract 4 bytes, so it's (s-4)/6.
       *
       * These are approximated by r/256-1 and (s-2)/8, respectively.
       * Note: for a file that compresses to 258 bytes per symbol (e.g. all
       * the same character), that approximation would break down if
       *
       *	r/256-1 > r/258
       * thus,	258 * r - 256 * 258 > 256*r
       * thus,	2 * r > 256 * 258
       * thus,	r > 128 * 258  = 33024 > 32768
       *
       * Of course, the window is <= 32768, so it's not a concern.
       *
       * For the input approximation to break down, you'd have to have
       *
       *	(s-2)/8 > (s-4)/6
       * thus,	6*s - 12 > 8*s - 32
       * thus,  20 > 2*s
       * thus,  10 > s
       *
       * But for s<10, both approximations (since this is integer math)
       * return 0, so it's not a problem.  The r/258 limit is usually
       * hit first, so the crudeness of this approximation is acceptable.
       */
      while (r >= 512 && s >= 10) {
         /* Compute number of iterations we can do, worst-case */
	if ((e = (s - 2) >> 3) < (i = (r >> 8) - 1))
	  i = e;
        /*
         * This is the cheap loop, which is performed i times before
         * the available buffer space is re-evaluated.  If you want to
         * understand how the inflation process works, this is the best
         * part of the code to read, since it isn't cluttered up with
         * error checking.  First comes a literal/length code, which
         * can be either a literal (0-255), an end of block code (256),
         */
	do {
	  GRABBITS(20)            /* max bits for literal/length code */
	  t = tl + ((unsigned)b & ml);
	  if ((e = t->exop) < 0) {
	    do {
	      if (e == -128)
		return INFERR_BADINPUT;
	      DUMPBITS(t->bits);
	      e = -e;
	      t = t->next + ((unsigned)b & mask[e]);
	    } while ((e = t->exop) < 0);
	  }
	  DUMPBITS(t->bits);
	  if (e & 16) {             /* then it's a literal */
	    *w++ = (unsigned char)t->base;
	    continue;
	  }
	  if (e & 32) 	/* EOB */
	    goto EOB;	/* At end of function */

	  /* Else length code */

	  /* get length of block to copy */
	  n = t->base + ((unsigned)b & mask[e]);
	  DUMPBITS(e);

	  /* decode distance of block to copy */
	  GRABBITS(15);
	  t = td + ((unsigned)b & md);
	  if ((e = t->exop) < 0) {
	    do {
	      if (e == -128)
		return INFERR_BADINPUT;
	      DUMPBITS(t->bits);
	      e = -e;
	      t = t->next + ((unsigned)b & mask[e]);
	    } while ((e = t->exop) < 0);
	  }
	  DUMPBITS(t->bits);
	  GRABBITS((unsigned)e)           /* get up to 13 extra bits */
	  d = t->base + ((unsigned)b & mask[e]);
	  DUMPBITS((unsigned)e);

#if WSIZE < 32768
	  if (d > ctx->slidelen)
	    return INFERR_BADINPUT;
#endif

	  /* do the copy */
	  if ((unsigned)(w - ctx->slide) >= d) {
	    p = w - d;
	    *w++ = *p++;
	    *w++ = *p++;
	    do {
	      *w++ = *p++;
	    } while (--n);
	  } else {
	    n += 2;
	    p = w - d + ctx->slidelen;
	    do {
	      n -= (e = (unsigned)(e = ctx->slideend - (p>w?p:w)) > n ? n : e);
	      do {
		*w++ = *p++;
	      } while (--e);
	      if (p == ctx->slideend)
		p = ctx->slide;
	    } while (n);
	  }
	} while (--i);

	r = ctx->slideend - w;
      } /* while (we can use the cheap loop) */

      /*
       * Okay, we've fallen through from the cheap loop to the
       * expensive loop.  This one checks each time it gets bits
       * from the input or writes bytes to the output that there
       * is enough room.  However, there are two versions of
       * much of *this*, too!  The first uses worst-case figures
       * for the amount of input data needed, and obtains one batch of
       * input bits for several uses.
       * The second carefully avoids asking for any more bits than it really
       * needs.  When it gives up and returns, it is really not possible
       * to extract any more symbols from the input data.
       */
      /* Pessimistic estimate of bits for literal/length: 15+5 */
      GETBITSOR(20, goto getlitlength2)
      t = tl + ((unsigned)b & ml);
      if ((e = t->exop) < 0) {
	do {
	  if (e == -128)
	    return INFERR_BADINPUT;
	  DUMPBITS(t->bits);
	  e = -e;
	  t = t->next + ((unsigned)b & mask[e]);
	} while ((e = t->exop) < 0);
      }
      DUMPBITS(t->bits);
      if (e & 16) {         /* then it's a literal */
	*w++ = (unsigned char)t->base;
	if (--r == 0) {
          SAVEBITBUF;
          ctx->outptr = w;
          ctx->substate = 0;	/* Restart at top of loop */
          return 2;	/* Output buffer full */
	}
	continue;
      }

      if (e & 32)
	break;	/* Leave infinite loop */

      goto gotlength;

getlitlength2:
      /* Method 2: We don't even have 20 bits available - do it bit-by-bit. */
      t = tl + ((unsigned)b & ml);
      /*
       * See if higher-order bits we're missing actually matter.
       * We don't have to try to fill the bit buffer, because we only get
       * here if s (number of following input bytes) is supposed to be zero.
       */
      if (k < (unsigned)t->bits) {
        ctx->outptr = w;
        ctx->substate = 0;
        SAVEBITBUFEMPTY;
        return 1;
      }
      /* Actually, s is set (see GETBITSOR comment) to -1, so reset it */
      s = 0;
      if ((e = t->exop) < 0) {
	do {
	  if (e == -128)
	    return INFERR_BADINPUT;
	  DUMPBITS(t->bits);
	  e = -e;
          t = t->next;
  case 1:
          NEEDBITS2(e, t[(unsigned)b & mask[e]].bits,
                    ctx->t=t; ctx->outptr=w; ctx->numbits=e; ctx->substate=1)
	  t += (unsigned)b & mask[e];
	} while ((e = t->exop) < 0);
      }
      DUMPBITS(t->bits);
      if (e & 16) {         /* then it's a literal */
	*w++ = (unsigned char)t->base;
	if (--r == 0) {
          /* We just filled the output buffer - return */
          SAVEBITBUF;
          ctx->outptr = w;
          ctx->substate = 0;	/* Restart at top of loop */
          return 2;	/* Output buffer full */
	}
	continue;
      }

      if (e & 32)	/* EOB */
	break;	/* Leave infinite loop */

      /*FALLTHROUGH*/
  case 2:
      NEEDBITS(e, ctx->t = t; ctx->outptr=w; ctx->numbits=e; ctx->substate=2)

gotlength:

      /* All data is available - compute total length of block to copy */
      n = t->base + ((unsigned)b & mask[e]);
      DUMPBITS((unsigned)e);

      /*FALLTHROUGH*/
  case 3:
      /* Get distance code - 15 is maximum code size */
      GETBITSOR(15, goto getdistance2)
      t = td + ((unsigned)b & md);
      /* Negative t->exop means there's a subtable of 2^-e entries */
      if ((e = t->exop) < 0) {
	do {
	  if (e == -128)
	    return INFERR_BADINPUT;	/* Invalid code (static table case) */
	  DUMPBITS(t->bits);
	  e = -e;
	  t = t->next + ((unsigned)b & mask[e]);
	} while ((e = t->exop) < 0);
      }
      goto gotdistance;

getdistance2:
      /* We don't even have 15 bits available - do it bit-by-bit. */
      t = td + ((unsigned)b & md);
      /*
       * See if higher-order bits we're missing actually matter.
       * We don't have to try to fill the bit buffer, because we only get
       * here if s (number of following input bytes) is supposed to be zero.
       */
      if (k < (unsigned)t->bits) {
        ctx->outptr = w;
        ctx->copylen = n;
        ctx->substate = 3;
        SAVEBITBUFEMPTY;
        return 1;
      }
      /* Actually (see GETBITSOR comment) s is set to -1, so reset it */
      s = 0;
      /* Negative t->exop means there's a subtable of 2^-e entries */
      if ((e = t->exop) < 0) {
	do {
	  if (e == -128)
	    return INFERR_BADINPUT;	/* Invalid code (static table case) */
	  DUMPBITS(t->bits);
	  e = -e;
	  t = t->next;
  case 4:
          NEEDBITS2(e, t[(unsigned)b & mask[e]].bits, ctx->t=t; ctx->outptr=w;
                       ctx->copylen = n; ctx->numbits=e; ctx->substate=4)
	  t += (unsigned)b & mask[e];
	} while ((e = t->exop) < 0);
      }

gotdistance:
      /* All data is available - compute the base distance */
      DUMPBITS(t->bits);
      d = t->base;
      /*FALLTHROUGH*/
  case 5:
      /* e is number of bits extra following distance code (0..13) */
      NEEDBITS(e, ctx->outptr=w; ctx->copylen=n; ctx->distbase=d;
                  ctx->numbits=e; ctx->substate=5)
      d += ((unsigned)b & mask[e]);
      DUMPBITS((unsigned)e);

#if WSIZE < 32768
      if (d > ctx->slidelen)
	return INFERR_BADINPUT;
#endif

      /* do the copy, with handling for wrapping around end of buffer */
      if ((unsigned)(w - ctx->slide) >= d && w + n < ctx->slideend - 2) {
        /* Simple case - neither source nor dest cross end of buffer */
	p = w - d;
	r -= n + 2;
	*w++ = *p++;
	*w++ = *p++;
	do {
	  *w++ = *p++;
	} while (--n);
      } else {
	n += 2;	/* # of bytes to copy */
	p = ctx->slide + ((w - ctx->slide - d) & ctx->slidemask);  /* src */
	do {
          /* Set e to number of bytes we can copy at once */
	  n -= (e = (unsigned)(e = ctx->slideend - (p>w?p:w)) > n ? n : e);
	  r -= e;
	  do {
	    *w++ = *p++;
	  } while (--e);
	  if (r == 0) {	/* Did we just write everything we could? */
            SAVEBITBUF;
            ctx->outptr = w;
            ctx->copylen = n;
            ctx->distbase = d;	/* Save copy distance to recompute p */
            ctx->substate = 6;
            return 2;	/* Need more output space */
  case 6:
	    p = ctx->slide + ((w - ctx->slide - d) & ctx->slidemask);
	  }
	  if (p == ctx->slideend)
	    p = ctx->slide;
	} while (n);
      }
    } /* for(;;) */
  } /* switch(ctx->subcase) */

EOB:
  /* End of Block */
  ctx->outptr = w;
  SAVEBITBUF;
  ctx->state = STATE_START;
  ctx->substate = 0;

  if (tl && tl != ctx->fixed_tl)
    huft_free(ctx->context, tl);
  if (td && td != ctx->fixed_td)
    huft_free( ctx->context, td);
  ctx->tree1 = 0;
  ctx->tree2 = 0;

  return 0;
}


/*
 * Start state - read 3 bits, which are last block flag (set to 1 on
 * last block), and 2 bits of block type.
 */
static int
infStart(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	int retval = 0;

	if (ctx->lastblock) {
		ctx->state = STATE_DONE;
		return 0;
	}

	LOADBITBUF;
	NEEDBITS(3, (void)0);

	ctx->lastblock = (int)(b & 1);
	DUMPBITS(1);

	switch(b & 3) {
	case 0:	/* Stored */
		ctx->state = STATE_STOREDLEN;
		break;
	case 1: /* Static - build fixed trees and start decoding */
		retval = infFixedTree( ctx );
		ctx->tree1 = ctx->fixed_tl;
		ctx->bits1 = ctx->fixed_bl;
		ctx->tree2 = ctx->fixed_td;
		ctx->bits2 = ctx->fixed_bd;
		ctx->state = STATE_INFLATE;
		break;
	case 2: /* Dynamic */
		ctx->state = STATE_DYN_HDR;
		break;
	case 3: /* Illegal */
		retval = INFERR_BADINPUT;
		break;
	}

	DUMPBITS(2);
	SAVEBITBUF;

	ctx->substate = 0;
	return retval;
}

/*
 * Get a pointer to available data in the output buffer
 */
unsigned char const *
infGetBytes(InflateContext *ctx, unsigned *len)
{
	*len = ctx->outptr - ctx->readptr;
	return *len ? ctx->readptr : 0;
}

/*
 * Mark data in the output buffer as already read.  We don't start
 * accepting new data until the entire output buffer has been read,
 * at which point the outptr is set back to the beginning of the
 * buffer.
 */
void
infSkipBytes(InflateContext *ctx, unsigned len)
{
	pgpAssert(len <= (unsigned)(ctx->outptr - ctx->readptr));

	ctx->readptr += len;

	/* If at end of buffer, recirculate */
	if (ctx->readptr == ctx->slideend) {
		PGPError dummy;

		pgpAssert(ctx->outptr == ctx->slideend);
		ctx->readptr = ctx->outptr = ctx->slide;
		/* Flush any pending output */
		(void)infWrite(ctx, NULL, 0, &dummy);
	}
}


/*
 * Returns number of bytes written.
 * *error < 0 on error, == 0 if no error (done with input or output full)
 */
size_t
infWrite(InflateContext *ctx, unsigned char const *buf, size_t len,
         PGPError *error)
{
	int i	= 0;

	if (ctx->outptr == ctx->slideend) {
		*error = (ctx->state == STATE_STOP) ?
			kPGPError_NoErr : (PGPError)ctx->substate;
		return 0;	/* Out of output space! */
	}

	ctx->inptr = buf;
	/* Decompression code can't handle more than INT_MAX bytes at a time */
	ctx->inlen = len > INT_MAX ? INT_MAX : (int)len;

	do {
		switch(ctx->state) {
		  case STATE_START:
			i = infStart(ctx);
			break;
		  case STATE_STOREDLEN:
			i = infStoredLen(ctx);
			break;
		  case STATE_STORED:
			i = infStored(ctx);
			break;
		  case STATE_DYN_HDR:
			i = infDynHdr(ctx);
			break;
		  case STATE_DYN_BITS:
			i = infDynBits(ctx);
			break;
		  case STATE_DYN_TREE:
			i = infDynTree(ctx);
			break;
		  case STATE_INFLATE:
			i = infInflate(ctx);
			break;
		  case STATE_DONE:
			if (ctx->inlen || ctx->bufbits > 7)
				i = INFERR_LONG;
#if STRICT
			else if (ctx->bitbuffer & mask[ctx->bufbits])
				i = INFERR_BADINPUT;	/* Unused bits != 0 */
#endif
			else
				i = 2;	/* Read output, please */
			break;
		  case STATE_STOP:
			i = ctx->substate;
			break;
		  default:
		  	i	= 0;
		  	pgpDebugMsg( "impossible state" );
		  	break;
		}
	} while (i == 0);

	if (i < 0) {
		ctx->state = STATE_STOP;
		ctx->substate = i;
		*error = (PGPError)i;
	} else {
		*error = kPGPError_NoErr;
	}

	pgpAssert((size_t)(ctx->inptr - buf) == len - ctx->inlen);
	return (size_t)(ctx->inptr - buf);	/* Bytes read */
}

/*
 * Signal EOF, detecting truncated messages.
 * If another error has been reported, this just repeats it.
 */
/* New version, hopefully useful. */
int
infEOF(InflateContext *ctx)
{
	/* If processing is halted, just return the last error (if any) */
	if (ctx->state == STATE_STOP)
		return ctx->substate;

	/* If expecting still more input, we're short */
	if (ctx->state != STATE_DONE)
		return INFERR_SHORT;

	/* Otherwise, all is well. */
		return 0;
}

InflateContext *
infAlloc( PGPContextRef	context )
{
	InflateContext *ctx;
	unsigned char *slide;

	slide = (unsigned char *)pgpContextMemAlloc( context,
			WSIZE, kPGPMemoryMgrFlags_Clear);
	if (!slide)
		return 0;
	ctx = (InflateContext *)pgpContextMemAlloc( context,
			sizeof(*ctx), kPGPMemoryMgrFlags_Clear);
	if (!ctx) {
		pgpContextMemFree( context, slide);
		return 0;
	}
	ctx->context	= context;
	ctx->slide = slide;
	ctx->slideend = slide+WSIZE;
	ctx->slidelen = WSIZE;
	ctx->slidemask = WSIZE-1;

	ctx->outptr = slide;
	ctx->readptr = slide;

	ctx->state = STATE_START;
	ctx->substate = 0;
	ctx->inlen = 0;
	ctx->bitbuffer = 0;
	ctx->bufbits = 0;
	ctx->lastblock = 0;

	ctx->tree1 = 0;
	ctx->tree2 = 0;

	return ctx;
}

void
infFree(InflateContext *ctx)
{
	PGPContextRef context = ctx->context;

	if (ctx->tree1 && ctx->tree1 != ctx->fixed_tl)
		huft_free(context, ctx->tree1);
	if (ctx->tree2 && ctx->tree2 != ctx->fixed_td)
		huft_free(context, ctx->tree2);
	
	if ( IsntNull( ctx->fixed_tl ) )
	{
		huft_free(context, ctx->fixed_tl);
		ctx->fixed_tl	= NULL;
	}
	if ( IsntNull( ctx->fixed_td ) )
	{
		huft_free(context, ctx->fixed_td);
		ctx->fixed_tl	= NULL;
	}

	if (ctx->slide) {
#if SECURE
		pgpClearMemory(ctx->slide, ctx->slidelen);
#endif
		pgpContextMemFree( context, ctx->slide);
	}
#if SECURE
	pgpClearMemory( ctx,  sizeof(*ctx));
#endif
	pgpContextMemFree( context, ctx);
}
