zlib.c

/*
 * This file is derived from various .h and .c files from the zlib-0.95
 * distribution by Jean-loup Gailly and Mark Adler, with some additions
 * by Paul Mackerras to aid in implementing Deflate compression and
 * decompression for PPP packets.  See zlib.h for conditions of
 * distribution and use.
 *
 * Changes that have been made include:
 * - changed functions not used outside this file to "local"
 * - added minCompression parameter to deflateInit2
 * - added Z_PACKET_FLUSH (see zlib.h for details)
 * - added inflateIncomp
 */

/*+++++*/
/* zutil.h -- internal interface and configuration of the compression library
 * Copyright (C) 1995 Jean-loup Gailly.
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

/* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */

#define _Z_UTIL_H

#include "u-boot/zlib.h"

#ifndef local
#  define local static
#endif
/* compile with -Dlocal if your debugger can't find static symbols */

#define FAR

typedef unsigned char  uch;
typedef uch FAR uchf;
typedef unsigned short ush;
typedef ush FAR ushf;
typedef unsigned long  ulg;

extern char *z_errmsg[]; /* indexed by 1-zlib_error */

#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
/* To be used only when the state is known to be valid */

#ifndef NULL
#define NULL	((void *) 0)
#endif

	/* common constants */

#define DEFLATED   8

#ifndef DEF_WBITS
#  define DEF_WBITS MAX_WBITS
#endif
/* default windowBits for decompression. MAX_WBITS is for compression only */

#if MAX_MEM_LEVEL >= 8
#  define DEF_MEM_LEVEL 8
#else
#  define DEF_MEM_LEVEL  MAX_MEM_LEVEL
#endif
/* default memLevel */

#define STORED_BLOCK 0
#define STATIC_TREES 1
#define DYN_TREES    2
/* The three kinds of block type */

#define MIN_MATCH  3
#define MAX_MATCH  258
/* The minimum and maximum match lengths */

	 /* functions */

#include <linux/string.h>
#define zmemcpy memcpy
#define zmemzero(dest, len)	memset(dest, 0, len)

/* Diagnostic functions */
#ifdef DEBUG_ZLIB
#  include <stdio.h>
#  ifndef verbose
#    define verbose 0
#  endif
#  define Assert(cond,msg) {if(!(cond)) z_error(msg);}
#  define Trace(x) fprintf x
#  define Tracev(x) {if (verbose) fprintf x ;}
#  define Tracevv(x) {if (verbose>1) fprintf x ;}
#  define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
#  define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
#else
#  define Assert(cond,msg)
#  define Trace(x)
#  define Tracev(x)
#  define Tracevv(x)
#  define Tracec(c,x)
#  define Tracecv(c,x)
#endif


typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));

/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
/* void   zcfree  OF((voidpf opaque, voidpf ptr)); */

#define ZALLOC(strm, items, size) \
	   (*((strm)->zalloc))((strm)->opaque, (items), (size))
#define ZFREE(strm, addr, size)	\
	   (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
#define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}

/* deflate.h -- internal compression state
 * Copyright (C) 1995 Jean-loup Gailly
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

/*+++++*/
/* infblock.h -- header to use infblock.c
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

struct inflate_blocks_state;
typedef struct inflate_blocks_state FAR inflate_blocks_statef;

local inflate_blocks_statef * inflate_blocks_new OF((
    z_stream *z,
    check_func c,               /* check function */
    uInt w));                   /* window size */

local int inflate_blocks OF((
    inflate_blocks_statef *,
    z_stream *,
    int));                      /* initial return code */

local void inflate_blocks_reset OF((
    inflate_blocks_statef *,
    z_stream *,
    uLongf *));                  /* check value on output */

local int inflate_blocks_free OF((
    inflate_blocks_statef *,
    z_stream *,
    uLongf *));                  /* check value on output */

local int inflate_addhistory OF((
    inflate_blocks_statef *,
    z_stream *));

local int inflate_packet_flush OF((
    inflate_blocks_statef *));

/*+++++*/
/* inftrees.h -- header to use inftrees.c
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

/* 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). */

typedef struct inflate_huft_s FAR inflate_huft;

struct inflate_huft_s {
  union {
    struct {
      Byte Exop;        /* number of extra bits or operation */
      Byte Bits;        /* number of bits in this code or subcode */
    } what;
    uInt Nalloc;	/* number of these allocated here */
    Bytef *pad;         /* pad structure to a power of 2 (4 bytes for */
  } word;               /*  16-bit, 8 bytes for 32-bit machines) */
  union {
    uInt Base;          /* literal, length base, or distance base */
    inflate_huft *Next; /* pointer to next level of table */
  } more;
};

#ifdef DEBUG_ZLIB
  local uInt inflate_hufts;
#endif

local int inflate_trees_bits OF((
    uIntf *,                    /* 19 code lengths */
    uIntf *,                    /* bits tree desired/actual depth */
    inflate_huft * FAR *,       /* bits tree result */
    z_stream *));               /* for zalloc, zfree functions */

local int inflate_trees_dynamic OF((
    uInt,                       /* number of literal/length codes */
    uInt,                       /* number of distance codes */
    uIntf *,                    /* that many (total) code lengths */
    uIntf *,                    /* literal desired/actual bit depth */
    uIntf *,                    /* distance desired/actual bit depth */
    inflate_huft * FAR *,       /* literal/length tree result */
    inflate_huft * FAR *,       /* distance tree result */
    z_stream *));               /* for zalloc, zfree functions */

local int inflate_trees_fixed OF((
    uIntf *,                    /* literal desired/actual bit depth */
    uIntf *,                    /* distance desired/actual bit depth */
    inflate_huft * FAR *,       /* literal/length tree result */
    inflate_huft * FAR *));     /* distance tree result */

local int inflate_trees_free OF((
    inflate_huft *,             /* tables to free */
    z_stream *));               /* for zfree function */


/*+++++*/
/* infcodes.h -- header to use infcodes.c
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

struct inflate_codes_state;
typedef struct inflate_codes_state FAR inflate_codes_statef;

local inflate_codes_statef *inflate_codes_new OF((
    uInt, uInt,
    inflate_huft *, inflate_huft *,
    z_stream *));

local int inflate_codes OF((
    inflate_blocks_statef *,
    z_stream *,
    int));

local void inflate_codes_free OF((
    inflate_codes_statef *,
    z_stream *));


/*+++++*/
/* inflate.c -- zlib interface to inflate modules
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* inflate private state */
struct internal_state {

  /* mode */
  enum {
      METHOD,   /* waiting for method byte */
      FLAG,     /* waiting for flag byte */
      BLOCKS,   /* decompressing blocks */
      CHECK4,   /* four check bytes to go */
      CHECK3,   /* three check bytes to go */
      CHECK2,   /* two check bytes to go */
      CHECK1,   /* one check byte to go */
      DONE,     /* finished check, done */
      BAD}      /* got an error--stay here */
    mode;               /* current inflate mode */

  /* mode dependent information */
  union {
    uInt method;        /* if FLAGS, method byte */
    struct {
      uLong was;                /* computed check value */
      uLong need;               /* stream check value */
    } check;            /* if CHECK, check values to compare */
    uInt marker;        /* if BAD, inflateSync's marker bytes count */
  } sub;        /* submode */

  /* mode independent information */
  int  nowrap;          /* flag for no wrapper */
  uInt wbits;           /* log2(window size)  (8..15, defaults to 15) */
  inflate_blocks_statef
    *blocks;            /* current inflate_blocks state */

};


int inflateReset(z)
z_stream *z;
{
  uLong c;

  if (z == Z_NULL || z->state == Z_NULL)
    return Z_STREAM_ERROR;
  z->total_in = z->total_out = 0;
  z->msg = Z_NULL;
  z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
  inflate_blocks_reset(z->state->blocks, z, &c);
  Trace((stderr, "inflate: reset\n"));
  return Z_OK;
}


int inflateEnd(z)
z_stream *z;
{
  uLong c;

  if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
    return Z_STREAM_ERROR;
  if (z->state->blocks != Z_NULL)
    inflate_blocks_free(z->state->blocks, z, &c);
  ZFREE(z, z->state, sizeof(struct internal_state));
  z->state = Z_NULL;
  Trace((stderr, "inflate: end\n"));
  return Z_OK;
}


int inflateInit2(z, w)
z_stream *z;
int w;
{
  /* initialize state */
  if (z == Z_NULL)
    return Z_STREAM_ERROR;
/*  if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
/*  if (z->zfree == Z_NULL) z->zfree = zcfree; */
  if ((z->state = (struct internal_state FAR *)
       ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
    return Z_MEM_ERROR;
  z->state->blocks = Z_NULL;

  /* handle undocumented nowrap option (no zlib header or check) */
  z->state->nowrap = 0;
  if (w < 0)
  {
    w = - w;
    z->state->nowrap = 1;
  }

  /* set window size */
  if (w < 8 || w > 15)
  {
    inflateEnd(z);
    return Z_STREAM_ERROR;
  }
  z->state->wbits = (uInt)w;

  /* create inflate_blocks state */
  if ((z->state->blocks =
       inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
      == Z_NULL)
  {
    inflateEnd(z);
    return Z_MEM_ERROR;
  }
  Trace((stderr, "inflate: allocated\n"));

  /* reset state */
  inflateReset(z);
  return Z_OK;
}


int inflateInit(z)
z_stream *z;
{
  return inflateInit2(z, DEF_WBITS);
}


#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)

int inflate(z, f)
z_stream *z;
int f;
{
  int r;
  uInt b;

  if (z == Z_NULL || z->next_in == Z_NULL)
    return Z_STREAM_ERROR;
  r = Z_BUF_ERROR;
  while (1) switch (z->state->mode)
  {
    case METHOD:
      NEEDBYTE
      if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
      {
	z->state->mode = BAD;
	z->msg = "unknown compression method";
	z->state->sub.marker = 5;       /* can't try inflateSync */
	break;
      }
      if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
      {
	z->state->mode = BAD;
	z->msg = "invalid window size";
	z->state->sub.marker = 5;       /* can't try inflateSync */
	break;
      }
      z->state->mode = FLAG;
    case FLAG:
      NEEDBYTE
      if ((b = NEXTBYTE) & 0x20)
      {
	z->state->mode = BAD;
	z->msg = "invalid reserved bit";
	z->state->sub.marker = 5;       /* can't try inflateSync */
	break;
      }
      if (((z->state->sub.method << 8) + b) % 31)
      {
	z->state->mode = BAD;
	z->msg = "incorrect header check";
	z->state->sub.marker = 5;       /* can't try inflateSync */
	break;
      }
      Trace((stderr, "inflate: zlib header ok\n"));
      z->state->mode = BLOCKS;
    case BLOCKS:
      r = inflate_blocks(z->state->blocks, z, r);
      if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
	  r = inflate_packet_flush(z->state->blocks);
      if (r == Z_DATA_ERROR)
      {
	z->state->mode = BAD;
	z->state->sub.marker = 0;       /* can try inflateSync */
	break;
      }
      if (r != Z_STREAM_END)
	return r;
      r = Z_OK;
      inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
      if (z->state->nowrap)
      {
	z->state->mode = DONE;
	break;
      }
      z->state->mode = CHECK4;
    case CHECK4:
      NEEDBYTE
      z->state->sub.check.need = (uLong)NEXTBYTE << 24;
      z->state->mode = CHECK3;
    case CHECK3:
      NEEDBYTE
      z->state->sub.check.need += (uLong)NEXTBYTE << 16;
      z->state->mode = CHECK2;
    case CHECK2:
      NEEDBYTE
      z->state->sub.check.need += (uLong)NEXTBYTE << 8;
      z->state->mode = CHECK1;
    case CHECK1:
      NEEDBYTE
      z->state->sub.check.need += (uLong)NEXTBYTE;

      if (z->state->sub.check.was != z->state->sub.check.need)
      {
	z->state->mode = BAD;
	z->msg = "incorrect data check";
	z->state->sub.marker = 5;       /* can't try inflateSync */
	break;
      }
      Trace((stderr, "inflate: zlib check ok\n"));
      z->state->mode = DONE;
    case DONE:
      return Z_STREAM_END;
    case BAD:
      return Z_DATA_ERROR;
    default:
      return Z_STREAM_ERROR;
  }

 empty:
  if (f != Z_PACKET_FLUSH)
    return r;
  z->state->mode = BAD;
  z->state->sub.marker = 0;       /* can try inflateSync */
  return Z_DATA_ERROR;
}

/*
 * This subroutine adds the data at next_in/avail_in to the output history
 * without performing any output.  The output buffer must be "caught up";
 * i.e. no pending output (hence s->read equals s->write), and the state must
 * be BLOCKS (i.e. we should be willing to see the start of a series of
 * BLOCKS).  On exit, the output will also be caught up, and the checksum
 * will have been updated if need be.
 */

int inflateIncomp(z)
z_stream *z;
{
    if (z->state->mode != BLOCKS)
	return Z_DATA_ERROR;
    return inflate_addhistory(z->state->blocks, z);
}


int inflateSync(z)
z_stream *z;
{
  uInt n;       /* number of bytes to look at */
  Bytef *p;     /* pointer to bytes */
  uInt m;       /* number of marker bytes found in a row */
  uLong r, w;   /* temporaries to save total_in and total_out */

  /* set up */
  if (z == Z_NULL || z->state == Z_NULL)
    return Z_STREAM_ERROR;
  if (z->state->mode != BAD)
  {
    z->state->mode = BAD;
    z->state->sub.marker = 0;
  }
  if ((n = z->avail_in) == 0)
    return Z_BUF_ERROR;
  p = z->next_in;
  m = z->state->sub.marker;

  /* search */
  while (n && m < 4)
  {
    if (*p == (Byte)(m < 2 ? 0 : 0xff))
      m++;
    else if (*p)
      m = 0;
    else
      m = 4 - m;
    p++, n--;
  }

  /* restore */
  z->total_in += p - z->next_in;
  z->next_in = p;
  z->avail_in = n;
  z->state->sub.marker = m;

  /* return no joy or set up to restart on a new block */
  if (m != 4)
    return Z_DATA_ERROR;
  r = z->total_in;  w = z->total_out;
  inflateReset(z);
  z->total_in = r;  z->total_out = w;
  z->state->mode = BLOCKS;
  return Z_OK;
}

#undef NEEDBYTE
#undef NEXTBYTE

/*+++++*/
/* infutil.h -- types and macros common to blocks and codes
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

/* inflate blocks semi-private state */
struct inflate_blocks_state {

  /* mode */
  enum {
      TYPE,     /* get type bits (3, including end bit) */
      LENS,     /* get lengths for stored */
      STORED,   /* processing stored block */
      TABLE,    /* get table lengths */
      BTREE,    /* get bit lengths tree for a dynamic block */
      DTREE,    /* get length, distance trees for a dynamic block */
      CODES,    /* processing fixed or dynamic block */
      DRY,      /* output remaining window bytes */
      DONEB,     /* finished last block, done */
      BADB}      /* got a data error--stuck here */
    mode;               /* current inflate_block mode */

  /* mode dependent information */
  union {
    uInt left;          /* if STORED, bytes left to copy */
    struct {
      uInt table;               /* table lengths (14 bits) */
      uInt index;               /* index into blens (or border) */
      uIntf *blens;             /* bit lengths of codes */
      uInt bb;                  /* bit length tree depth */
      inflate_huft *tb;         /* bit length decoding tree */
      int nblens;		/* # elements allocated at blens */
    } trees;            /* if DTREE, decoding info for trees */
    struct {
      inflate_huft *tl, *td;    /* trees to free */
      inflate_codes_statef
	 *codes;
    } decode;           /* if CODES, current state */
  } sub;                /* submode */
  uInt last;            /* true if this block is the last block */

  /* mode independent information */
  uInt bitk;            /* bits in bit buffer */
  uLong bitb;           /* bit buffer */
  Bytef *window;        /* sliding window */
  Bytef *end;           /* one byte after sliding window */
  Bytef *read;          /* window read pointer */
  Bytef *write;         /* window write pointer */
  check_func checkfn;   /* check function */
  uLong check;          /* check on output */

};


/* defines for inflate input/output */
/*   update pointers and return */
#define UPDBITS {s->bitb=b;s->bitk=k;}
#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
#define UPDOUT {s->write=q;}
#define UPDATE {UPDBITS UPDIN UPDOUT}
#define LEAVE {UPDATE return inflate_flush(s,z,r);}
/*   get bytes and bits */
#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
#define NEXTBYTE (n--,*p++)
#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
#define DUMPBITS(j) {b>>=(j);k-=(j);}
/*   output bytes */
#define WAVAIL (q<s->read?s->read-q-1:s->end-q)
#define LOADOUT {q=s->write;m=WAVAIL;}
#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
/*   load local pointers */
#define LOAD {LOADIN LOADOUT}

/*
 * The IBM 150 firmware munges the data right after _etext[].  This
 * protects it. -- Cort
 */
#if 0
local uInt protect_mask[] = {0, 0, 0, 0, 0, 0, 0, 0, 0 ,0 ,0 ,0};
#endif
/* And'ing with mask[n] masks the lower n bits */
local uInt inflate_mask[] = {
    0x0000,
    0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
    0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};

/* copy as much as possible from the sliding window to the output area */
local int inflate_flush OF((
    inflate_blocks_statef *,
    z_stream *,
    int));

/*+++++*/
/* inffast.h -- header to use inffast.c
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* WARNING: this file should *not* be used by applications. It is
   part of the implementation of the compression library and is
   subject to change. Applications should only use zlib.h.
 */

local int inflate_fast OF((
    uInt,
    uInt,
    inflate_huft *,
    inflate_huft *,
    inflate_blocks_statef *,
    z_stream *));


/*+++++*/
/* infblock.c -- interpret and process block types to last block
 * Copyright (C) 1995 Mark Adler
 * For conditions of distribution and use, see copyright notice in zlib.h
 */

/* Table for deflate from PKZIP's appnote.txt. */
local uInt 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};

/*
   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.
 */


local void inflate_blocks_reset(s, z, c)
inflate_blocks_statef *s;
z_stream *z;
uLongf *c;
{
  if (s->checkfn != Z_NULL)
    *c = s->check;
  if (s->mode == BTREE || s->mode == DTREE)
    ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
  if (s->mode == CODES)
  {
    inflate_codes_free(s->sub.decode.codes, z);
    inflate_trees_free(s->sub.decode.td, z);
    inflate_trees_free(s->sub.decode.tl, z);
  }
  s->mode = TYPE;
  s->bitk = 0;
  s->bitb = 0;
  s->read = s->write = s->window;
  if (s->checkfn != Z_NULL)
    s->check = (*s->checkfn)(0L, Z_NULL, 0);
  if (z->outcb != Z_NULL)
    (*z->outcb)(Z_NULL, 0);
  Trace((stderr, "inflate:   blocks reset\n"));
}


local inflate_blocks_statef *inflate_blocks_new(z, c, w)
z_stream *z;
check_func c;
uInt w;
{
  inflate_blocks_statef *s;

  if ((s = (inflate_blocks_statef *)ZALLOC
       (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
    return s;
  if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
  {
    ZFREE(z, s, sizeof(struct inflate_blocks_state));
    return Z_NULL;
  }
  s->end = s->window + w;
  s->checkfn = c;
  s->mode = TYPE;
  Trace((stderr, "inflate:   blocks allocated\n"));
  inflate_blocks_reset(s, z, &s->check);
  return s;
}


local int inflate_blocks(s, z, r)
inflate_blocks_statef *s;
z_stream *z;
int r;
{
  uInt t;               /* temporary storage */
  uLong b;              /* bit buffer */
  uInt k;               /* bits in bit buffer */
  Bytef *p;             /* input data pointer */
  uInt n;               /* bytes available there */
  Bytef *q;             /* output window write pointer */
  uInt m;               /* bytes to end of window or read pointer */

  /* copy input/output information to locals (UPDATE macro restores) */
  LOAD

  /* process input based on current state */
  while (1) switch (s->mode)
  {
    case TYPE:
      NEEDBITS(3)
      t = (uInt)b & 7;
      s->last = t & 1;
      switch (t >> 1)
      {
	case 0:                         /* stored */
	  Trace((stderr, "inflate:     stored block%s\n",
		 s->last ? " (last)" : ""));
	  DUMPBITS(3)
	  t = k & 7;                    /* go to byte boundary */
	  DUMPBITS(t)
	  s->mode = LENS;               /* get length of stored block */
	  break;
	case 1:                         /* fixed */
	  Trace((stderr, "inflate:     fixed codes block%s\n",
		 s->last ? " (last)" : ""));
	  {
	    uInt bl, bd;
	    inflate_huft *tl, *td;

	    inflate_trees_fixed(&bl, &bd, &tl, &td);
	    s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
	    if (s->sub.decode.codes == Z_NULL)
	    {
	      r = Z_MEM_ERROR;
	      LEAVE
	    }
	    s->sub.decode.tl = Z_NULL;  /* don't try to free these */
	    s->sub.decode.td = Z_NULL;
	  }
	  DUMPBITS(3)
	  s->mode = CODES;
	  break;
	case 2:                         /* dynamic */
	  Trace((stderr, "inflate:     dynamic codes block%s\n",
		 s->last ? " (last)" : ""));
	  DUMPBITS(3)
	  s->mode = TABLE;
	  break;
	case 3:                         /* illegal */
	  DUMPBITS(3)
	  s->mode = BADB;
	  z->msg = "invalid block type";
	  r = Z_DATA_ERROR;
	  LEAVE
      }
      break;
    case LENS:
      NEEDBITS(32)
      if (((~b) >> 16) != (b & 0xffff))
      {
	s->mode = BADB;
	z->msg = "invalid stored block lengths";
	r = Z_DATA_ERROR;
	LEAVE
      }
      s->sub.left = (uInt)b & 0xffff;
      b = k = 0;                      /* dump bits */
      Tracev((stderr, "inflate:       stored length %u\n", s->sub.left));
      s->mode = s->sub.left ? STORED : TYPE;
      break;
    case STORED:
      if (n == 0)
	LEAVE
      NEEDOUT
      t = s->sub.left;
      if (t > n) t = n;
      if (t > m) t = m;
      zmemcpy(q, p, t);
      p += t;  n -= t;
      q += t;  m -= t;
      if ((s->sub.left -= t) != 0)
	break;
      Tracev((stderr, "inflate:       stored end, %lu total out\n",
	      z->total_out + (q >= s->read ? q - s->read :
	      (s->end - s->read) + (q - s->window))));
      s->mode = s->last ? DRY : TYPE;
      break;
    case TABLE:
      NEEDBITS(14)
      s->sub.trees.table = t = (uInt)b & 0x3fff;
#ifndef PKZIP_BUG_WORKAROUND
      if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
      {
	s->mode = BADB;
	z->msg = "too many length or distance symbols";
	r = Z_DATA_ERROR;
	LEAVE
      }
#endif
      t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
      if (t < 19)
	t = 19;
      if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
      {
	r = Z_MEM_ERROR;
	LEAVE
      }
      s->sub.trees.nblens = t;
      DUMPBITS(14)
      s->sub.trees.index = 0;
      Tracev((stderr, "inflate:       table sizes ok\n"));
      s->mode = BTREE;
    case BTREE:
      while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
      {
	NEEDBITS(3)
	s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
	DUMPBITS(3)
      }
      while (s->sub.trees.index < 19)
	s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
      s->sub.trees.bb = 7;
      t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
			     &s->sub.trees.tb, z);
      if (t != Z_OK)
      {
	r = t;
	if (r == Z_DATA_ERROR)
	  s->mode = BADB;
	LEAVE
      }
      s->sub.trees.index = 0;
      Tracev((stderr, "inflate:       bits tree ok\n"));
      s->mode = DTREE;
    case DTREE:
      while (t = s->sub.trees.table,
	     s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
      {
	inflate_huft *h;
	uInt i, j, c;

	t = s->sub.trees.bb;
	NEEDBITS(t)
	h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
	t = h->word.what.Bits;
	c = h->more.Base;
	if (c < 16)
	{
	  DUMPBITS(t)
	  s->sub.trees.blens[s->sub.trees.index++] = c;
	}
	else /* c == 16..18 */
	{
	  i = c == 18 ? 7 : c - 14;
	  j = c == 18 ? 11 : 3;
	  NEEDBITS(t + i)
	  DUMPBITS(t)
	  j += (uInt)b & inflate_mask[i];
	  DUMPBITS(i)
	  i = s->sub.trees.index;
	  t = s->sub.trees.table;
	  if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
	      (c == 16 && i < 1))
	  {
	    s->mode = BADB;
	    z->msg = "invalid bit length repeat";
	    r = Z_DATA_ERROR;
	    LEAVE
	  }
	  c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
	  do {
	    s->sub.trees.blens[i++] = c;
	  } while (--j);
	  s->sub.trees.index = i;
	}
      }
      inflate_trees_free(s->sub.trees.tb, z);
      s->sub.trees.tb = Z_NULL;
      {
	uInt bl, bd;
	inflate_huft *tl, *td;
	inflate_codes_statef *c;

	bl = 9;         /* must be <= 9 for lookahead assumptions */
	bd = 6;         /* must be <= 9 for lookahead assumptions */
	t = s->sub.trees.table;
	t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
				  s->sub.trees.blens, &bl, &bd, &tl, &td, z);
	if (t != Z_OK)
	{
	  if (t == (uInt)Z_DATA_ERROR)
	    s->mode = BADB;
	  r = t;