src/com/jcraft/jzlib/InfCodes.java

/* -*-mode:java; c-basic-offset:2; -*- */
/*
Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice,
     this list of conditions and the following disclaimer.

  2. Redistributions in binary form must reproduce the above copyright
     notice, this list of conditions and the following disclaimer in
     the documentation and/or other materials provided with the distribution.

  3. The names of the authors may not be used to endorse or promote products
     derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * This program is based on zlib-1.1.3, so all credit should go authors
 * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
 * and contributors of zlib.
 */

package com.jcraft.jzlib;

final class InfCodes{

  static final private int[] inflate_mask = {
    0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
    0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
    0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
    0x00007fff, 0x0000ffff
  };

  static final private int Z_OK=0;
  static final private int Z_STREAM_END=1;
  static final private int Z_NEED_DICT=2;
  static final private int Z_ERRNO=-1;
  static final private int Z_STREAM_ERROR=-2;
  static final private int Z_DATA_ERROR=-3;
  static final private int Z_MEM_ERROR=-4;
  static final private int Z_BUF_ERROR=-5;
  static final private int Z_VERSION_ERROR=-6;

  // waiting for "i:"=input,
  //             "o:"=output,
  //             "x:"=nothing
  static final private int START=0;  // x: set up for LEN
  static final private int LEN=1;    // i: get length/literal/eob next
  static final private int LENEXT=2; // i: getting length extra (have base)
  static final private int DIST=3;   // i: get distance next
  static final private int DISTEXT=4;// i: getting distance extra
  static final private int COPY=5;   // o: copying bytes in window, waiting for space
  static final private int LIT=6;    // o: got literal, waiting for output space
  static final private int WASH=7;   // o: got eob, possibly still output waiting
  static final private int END=8;    // x: got eob and all data flushed
  static final private int BADCODE=9;// x: got error

  int mode;      // current inflate_codes mode

  // mode dependent information
  int len;

  int[] tree; // pointer into tree
  int tree_index=0;
  int need;   // bits needed

  int lit;

  // if EXT or COPY, where and how much
  int get;              // bits to get for extra
  int dist;             // distance back to copy from

  byte lbits;           // ltree bits decoded per branch
  byte dbits;           // dtree bits decoder per branch
  int[] ltree;          // literal/length/eob tree
  int ltree_index;      // literal/length/eob tree
  int[] dtree;          // distance tree
  int dtree_index;      // distance tree

  InfCodes(){
  }
  void init(int bl, int bd,
	   int[] tl, int tl_index,
	   int[] td, int td_index, ZStream z){
    mode=START;
    lbits=(byte)bl;
    dbits=(byte)bd;
    ltree=tl;
    ltree_index=tl_index;
    dtree = td;
    dtree_index=td_index;
    tree=null;
  }

  int proc(InfBlocks s, ZStream z, int r){
    int j;              // temporary storage
    int[] t;            // temporary pointer
    int tindex;         // temporary pointer
    int e;              // extra bits or operation
    int b=0;            // bit buffer
    int k=0;            // bits in bit buffer
    int p=0;            // input data pointer
    int n;              // bytes available there
    int q;              // output window write pointer
    int m;              // bytes to end of window or read pointer
    int f;              // pointer to copy strings from

    // copy input/output information to locals (UPDATE macro restores)
    p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
    q=s.write;m=q<s.read?s.read-q-1:s.end-q;

    // process input and output based on current state
    while (true){
      switch (mode){
	// waiting for "i:"=input, "o:"=output, "x:"=nothing
      case START:         // x: set up for LEN
	if (m >= 258 && n >= 10){

	  s.bitb=b;s.bitk=k;
	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	  s.write=q;
	  r = inflate_fast(lbits, dbits,
			   ltree, ltree_index,
			   dtree, dtree_index,
			   s, z);

	  p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
	  q=s.write;m=q<s.read?s.read-q-1:s.end-q;

	  if (r != Z_OK){
	    mode = r == Z_STREAM_END ? WASH : BADCODE;
	    break;
	  }
	}
	need = lbits;
	tree = ltree;
	tree_index=ltree_index;

	mode = LEN;
      case LEN:           // i: get length/literal/eob next
	j = need;

	while(k<(j)){
	  if(n!=0)r=Z_OK;
	  else{

	    s.bitb=b;s.bitk=k;
	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	    s.write=q;
	    return s.inflate_flush(z,r);
	  }
	  n--;
	  b|=(z.next_in[p++]&0xff)<<k;
	  k+=8;
	}

	tindex=(tree_index+(b&inflate_mask[j]))*3;

	b>>>=(tree[tindex+1]);
	k-=(tree[tindex+1]);

	e=tree[tindex];

	if(e == 0){               // literal
	  lit = tree[tindex+2];
	  mode = LIT;
	  break;
	}
	if((e & 16)!=0 ){          // length
	  get = e & 15;
	  len = tree[tindex+2];
	  mode = LENEXT;
	  break;
	}
	if ((e & 64) == 0){        // next table
	  need = e;
	  tree_index = tindex/3+tree[tindex+2];
	  break;
	}
	if ((e & 32)!=0){               // end of block
	  mode = WASH;
	  break;
	}
	mode = BADCODE;        // invalid code
	z.msg = "invalid literal/length code";
	r = Z_DATA_ERROR;

	s.bitb=b;s.bitk=k;
	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	s.write=q;
	return s.inflate_flush(z,r);

      case LENEXT:        // i: getting length extra (have base)
	j = get;

	while(k<(j)){
	  if(n!=0)r=Z_OK;
	  else{

	    s.bitb=b;s.bitk=k;
	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	    s.write=q;
	    return s.inflate_flush(z,r);
	  }
	  n--; b|=(z.next_in[p++]&0xff)<<k;
	  k+=8;
	}

	len += (b & inflate_mask[j]);

	b>>=j;
	k-=j;

	need = dbits;
	tree = dtree;
	tree_index=dtree_index;
	mode = DIST;
      case DIST:          // i: get distance next
	j = need;

	while(k<(j)){
	  if(n!=0)r=Z_OK;
	  else{

	    s.bitb=b;s.bitk=k;
	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	    s.write=q;
	    return s.inflate_flush(z,r);
	  }
	  n--; b|=(z.next_in[p++]&0xff)<<k;
	  k+=8;
	}

	tindex=(tree_index+(b & inflate_mask[j]))*3;

	b>>=tree[tindex+1];
	k-=tree[tindex+1];

	e = (tree[tindex]);
	if((e & 16)!=0){               // distance
	  get = e & 15;
	  dist = tree[tindex+2];
	  mode = DISTEXT;
	  break;
	}
	if ((e & 64) == 0){        // next table
	  need = e;
	  tree_index = tindex/3 + tree[tindex+2];
	  break;
	}
	mode = BADCODE;        // invalid code
	z.msg = "invalid distance code";
	r = Z_DATA_ERROR;

	s.bitb=b;s.bitk=k;
	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	s.write=q;
	return s.inflate_flush(z,r);

      case DISTEXT:       // i: getting distance extra
	j = get;

	while(k<(j)){
	  if(n!=0)r=Z_OK;
	  else{

	    s.bitb=b;s.bitk=k;
	    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	    s.write=q;
	    return s.inflate_flush(z,r);
	  }
	  n--; b|=(z.next_in[p++]&0xff)<<k;
	  k+=8;
	}

	dist += (b & inflate_mask[j]);

	b>>=j;
	k-=j;

	mode = COPY;
      case COPY:          // o: copying bytes in window, waiting for space
        f = q - dist;
        while(f < 0){     // modulo window size-"while" instead
          f += s.end;     // of "if" handles invalid distances
	}
	while (len!=0){

	  if(m==0){
	    if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	    if(m==0){
	      s.write=q; r=s.inflate_flush(z,r);
	      q=s.write;m=q<s.read?s.read-q-1:s.end-q;

	      if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}

	      if(m==0){
		s.bitb=b;s.bitk=k;
		z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
		s.write=q;
		return s.inflate_flush(z,r);
	      }
	    }
	  }

	  s.window[q++]=s.window[f++]; m--;

	  if (f == s.end)
            f = 0;
	  len--;
	}
	mode = START;
	break;
      case LIT:           // o: got literal, waiting for output space
	if(m==0){
	  if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	  if(m==0){
	    s.write=q; r=s.inflate_flush(z,r);
	    q=s.write;m=q<s.read?s.read-q-1:s.end-q;

	    if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	    if(m==0){
	      s.bitb=b;s.bitk=k;
	      z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	      s.write=q;
	      return s.inflate_flush(z,r);
	    }
	  }
	}
	r=Z_OK;

	s.window[q++]=(byte)lit; m--;

	mode = START;
	break;
      case WASH:           // o: got eob, possibly more output
	if (k > 7){        // return unused byte, if any
	  k -= 8;
	  n++;
	  p--;             // can always return one
	}

	s.write=q; r=s.inflate_flush(z,r);
	q=s.write;m=q<s.read?s.read-q-1:s.end-q;

	if (s.read != s.write){
	  s.bitb=b;s.bitk=k;
	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	  s.write=q;
	  return s.inflate_flush(z,r);
	}
	mode = END;
      case END:
	r = Z_STREAM_END;
	s.bitb=b;s.bitk=k;
	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	s.write=q;
	return s.inflate_flush(z,r);

      case BADCODE:       // x: got error

	r = Z_DATA_ERROR;

	s.bitb=b;s.bitk=k;
	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	s.write=q;
	return s.inflate_flush(z,r);

      default:
	r = Z_STREAM_ERROR;

	s.bitb=b;s.bitk=k;
	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	s.write=q;
	return s.inflate_flush(z,r);
      }
    }
  }

  void free(ZStream z){
    //  ZFREE(z, c);
  }

  // Called with number of bytes left to write in window at least 258
  // (the maximum string length) and number of input bytes available
  // at least ten.  The ten bytes are six bytes for the longest length/
  // distance pair plus four bytes for overloading the bit buffer.

  int inflate_fast(int bl, int bd,
		   int[] tl, int tl_index,
		   int[] td, int td_index,
		   InfBlocks s, ZStream z){
    int t;                // temporary pointer
    int[] tp;             // temporary pointer
    int tp_index;         // temporary pointer
    int e;                // extra bits or operation
    int b;                // bit buffer
    int k;                // bits in bit buffer
    int p;                // input data pointer
    int n;                // bytes available there
    int q;                // output window write pointer
    int m;                // bytes to end of window or read pointer
    int ml;               // mask for literal/length tree
    int md;               // mask for distance tree
    int c;                // bytes to copy
    int d;                // distance back to copy from
    int r;                // copy source pointer

    int tp_index_t_3;     // (tp_index+t)*3

    // load input, output, bit values
    p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
    q=s.write;m=q<s.read?s.read-q-1:s.end-q;

    // initialize masks
    ml = inflate_mask[bl];
    md = inflate_mask[bd];

    // do until not enough input or output space for fast loop
    do {                          // assume called with m >= 258 && n >= 10
      // get literal/length code
      while(k<(20)){              // max bits for literal/length code
	n--;
	b|=(z.next_in[p++]&0xff)<<k;k+=8;
      }

      t= b&ml;
      tp=tl;
      tp_index=tl_index;
      tp_index_t_3=(tp_index+t)*3;
      if ((e = tp[tp_index_t_3]) == 0){
	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);

	s.window[q++] = (byte)tp[tp_index_t_3+2];
	m--;
	continue;
      }
      do {

	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);

	if((e&16)!=0){
	  e &= 15;
	  c = tp[tp_index_t_3+2] + ((int)b & inflate_mask[e]);

	  b>>=e; k-=e;

	  // decode distance base of block to copy
	  while(k<(15)){           // max bits for distance code
	    n--;
	    b|=(z.next_in[p++]&0xff)<<k;k+=8;
	  }

	  t= b&md;
	  tp=td;
	  tp_index=td_index;
          tp_index_t_3=(tp_index+t)*3;
	  e = tp[tp_index_t_3];

	  do {

	    b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);

	    if((e&16)!=0){
	      // get extra bits to add to distance base
	      e &= 15;
	      while(k<(e)){         // get extra bits (up to 13)
		n--;
		b|=(z.next_in[p++]&0xff)<<k;k+=8;
	      }

	      d = tp[tp_index_t_3+2] + (b&inflate_mask[e]);

	      b>>=(e); k-=(e);

	      // do the copy
	      m -= c;
	      if (q >= d){                // offset before dest
		//  just copy
		r=q-d;
		if(q-r>0 && 2>(q-r)){
		  s.window[q++]=s.window[r++]; // minimum count is three,
		  s.window[q++]=s.window[r++]; // so unroll loop a little
		  c-=2;
		}
		else{
		  System.arraycopy(s.window, r, s.window, q, 2);
		  q+=2; r+=2; c-=2;
		}
	      }
	      else{                  // else offset after destination
                r=q-d;
                do{
                  r+=s.end;          // force pointer in window
                }while(r<0);         // covers invalid distances
		e=s.end-r;
		if(c>e){             // if source crosses,
		  c-=e;              // wrapped copy
		  if(q-r>0 && e>(q-r)){
		    do{s.window[q++] = s.window[r++];}
		    while(--e!=0);
		  }
		  else{
		    System.arraycopy(s.window, r, s.window, q, e);
		    q+=e; r+=e; e=0;
		  }
		  r = 0;                  // copy rest from start of window
		}

	      }

	      // copy all or what's left
	      if(q-r>0 && c>(q-r)){
		do{s.window[q++] = s.window[r++];}
		while(--c!=0);
	      }
	      else{
		System.arraycopy(s.window, r, s.window, q, c);
		q+=c; r+=c; c=0;
	      }
	      break;
	    }
	    else if((e&64)==0){
	      t+=tp[tp_index_t_3+2];
	      t+=(b&inflate_mask[e]);
	      tp_index_t_3=(tp_index+t)*3;
	      e=tp[tp_index_t_3];
	    }
	    else{
	      z.msg = "invalid distance code";

	      c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;

	      s.bitb=b;s.bitk=k;
	      z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	      s.write=q;

	      return Z_DATA_ERROR;
	    }
	  }
	  while(true);
	  break;
	}

	if((e&64)==0){
	  t+=tp[tp_index_t_3+2];
	  t+=(b&inflate_mask[e]);
	  tp_index_t_3=(tp_index+t)*3;
	  if((e=tp[tp_index_t_3])==0){

	    b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);

	    s.window[q++]=(byte)tp[tp_index_t_3+2];
	    m--;
	    break;
	  }
	}
	else if((e&32)!=0){

	  c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;

	  s.bitb=b;s.bitk=k;
	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	  s.write=q;

	  return Z_STREAM_END;
	}
	else{
	  z.msg="invalid literal/length code";

	  c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;

	  s.bitb=b;s.bitk=k;
	  z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	  s.write=q;

	  return Z_DATA_ERROR;
	}
      }
      while(true);
    }
    while(m>=258 && n>= 10);

    // not enough input or output--restore pointers and return
    c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;

    s.bitb=b;s.bitk=k;
    z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
    s.write=q;

    return Z_OK;
  }
}
Commit	Line	Data
	1	/* --mode:java; c-basic-offset:2; -- */
	2	/*
	3	Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved.
	4
	5	Redistribution and use in source and binary forms, with or without
	6	modification, are permitted provided that the following conditions are met:
	7
	8	1. Redistributions of source code must retain the above copyright notice,
	9	this list of conditions and the following disclaimer.
	10
	11	2. Redistributions in binary form must reproduce the above copyright
	12	notice, this list of conditions and the following disclaimer in
	13	the documentation and/or other materials provided with the distribution.
	14
	15	3. The names of the authors may not be used to endorse or promote products
	16	derived from this software without specific prior written permission.
	17
	18	THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES,
	19	INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
	20	FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT,
	21	INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT,
	22	INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	23	LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
	24	OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
	25	LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
	26	NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
	27	EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	28	*/
	29	/*
	30	* This program is based on zlib-1.1.3, so all credit should go authors
	31	* Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu)
	32	* and contributors of zlib.
	33	*/
	34
	35	package com.jcraft.jzlib;
	36
	37	final class InfCodes{
	38
	39	static final private int[] inflate_mask = {
	40	0x00000000, 0x00000001, 0x00000003, 0x00000007, 0x0000000f,
	41	0x0000001f, 0x0000003f, 0x0000007f, 0x000000ff, 0x000001ff,
	42	0x000003ff, 0x000007ff, 0x00000fff, 0x00001fff, 0x00003fff,
	43	0x00007fff, 0x0000ffff
	44	};
	45
	46	static final private int Z_OK=0;
	47	static final private int Z_STREAM_END=1;
	48	static final private int Z_NEED_DICT=2;
	49	static final private int Z_ERRNO=-1;
	50	static final private int Z_STREAM_ERROR=-2;
	51	static final private int Z_DATA_ERROR=-3;
	52	static final private int Z_MEM_ERROR=-4;
	53	static final private int Z_BUF_ERROR=-5;
	54	static final private int Z_VERSION_ERROR=-6;
	55
	56	// waiting for "i:"=input,
	57	// "o:"=output,
	58	// "x:"=nothing
	59	static final private int START=0; // x: set up for LEN
	60	static final private int LEN=1; // i: get length/literal/eob next
	61	static final private int LENEXT=2; // i: getting length extra (have base)
	62	static final private int DIST=3; // i: get distance next
	63	static final private int DISTEXT=4;// i: getting distance extra
	64	static final private int COPY=5; // o: copying bytes in window, waiting for space
	65	static final private int LIT=6; // o: got literal, waiting for output space
	66	static final private int WASH=7; // o: got eob, possibly still output waiting
	67	static final private int END=8; // x: got eob and all data flushed
	68	static final private int BADCODE=9;// x: got error
	69
	70	int mode; // current inflate_codes mode
	71
	72	// mode dependent information
	73	int len;
	74
	75	int[] tree; // pointer into tree
	76	int tree_index=0;
	77	int need; // bits needed
	78
	79	int lit;
	80
	81	// if EXT or COPY, where and how much
	82	int get; // bits to get for extra
	83	int dist; // distance back to copy from
	84
	85	byte lbits; // ltree bits decoded per branch
	86	byte dbits; // dtree bits decoder per branch
	87	int[] ltree; // literal/length/eob tree
	88	int ltree_index; // literal/length/eob tree
	89	int[] dtree; // distance tree
	90	int dtree_index; // distance tree
	91
	92	InfCodes(){
	93	}
	94	void init(int bl, int bd,
	95	int[] tl, int tl_index,
	96	int[] td, int td_index, ZStream z){
	97	mode=START;
	98	lbits=(byte)bl;
	99	dbits=(byte)bd;
	100	ltree=tl;
	101	ltree_index=tl_index;
	102	dtree = td;
	103	dtree_index=td_index;
	104	tree=null;
	105	}
	106
	107	int proc(InfBlocks s, ZStream z, int r){
	108	int j; // temporary storage
	109	int[] t; // temporary pointer
	110	int tindex; // temporary pointer
	111	int e; // extra bits or operation
	112	int b=0; // bit buffer
	113	int k=0; // bits in bit buffer
	114	int p=0; // input data pointer
	115	int n; // bytes available there
	116	int q; // output window write pointer
	117	int m; // bytes to end of window or read pointer
	118	int f; // pointer to copy strings from
	119
	120	// copy input/output information to locals (UPDATE macro restores)
	121	p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
	122	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	123
	124	// process input and output based on current state
	125	while (true){
	126	switch (mode){
	127	// waiting for "i:"=input, "o:"=output, "x:"=nothing
	128	case START: // x: set up for LEN
	129	if (m >= 258 && n >= 10){
	130
	131	s.bitb=b;s.bitk=k;
	132	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	133	s.write=q;
	134	r = inflate_fast(lbits, dbits,
	135	ltree, ltree_index,
	136	dtree, dtree_index,
	137	s, z);
	138
	139	p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
	140	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	141
	142	if (r != Z_OK){
	143	mode = r == Z_STREAM_END ? WASH : BADCODE;
	144	break;
	145	}
	146	}
	147	need = lbits;
	148	tree = ltree;
	149	tree_index=ltree_index;
	150
	151	mode = LEN;
	152	case LEN: // i: get length/literal/eob next
	153	j = need;
	154
	155	while(k<(j)){
	156	if(n!=0)r=Z_OK;
	157	else{
	158
	159	s.bitb=b;s.bitk=k;
	160	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	161	s.write=q;
	162	return s.inflate_flush(z,r);
	163	}
	164	n--;
	165	b\|=(z.next_in[p++]&0xff)<<k;
	166	k+=8;
	167	}
	168
	169	tindex=(tree_index+(b&inflate_mask[j]))*3;
	170
	171	b>>>=(tree[tindex+1]);
	172	k-=(tree[tindex+1]);
	173
	174	e=tree[tindex];
	175
	176	if(e == 0){ // literal
	177	lit = tree[tindex+2];
	178	mode = LIT;
	179	break;
	180	}
	181	if((e & 16)!=0 ){ // length
	182	get = e & 15;
	183	len = tree[tindex+2];
	184	mode = LENEXT;
	185	break;
	186	}
	187	if ((e & 64) == 0){ // next table
	188	need = e;
	189	tree_index = tindex/3+tree[tindex+2];
	190	break;
	191	}
	192	if ((e & 32)!=0){ // end of block
	193	mode = WASH;
	194	break;
	195	}
	196	mode = BADCODE; // invalid code
	197	z.msg = "invalid literal/length code";
	198	r = Z_DATA_ERROR;
	199
	200	s.bitb=b;s.bitk=k;
	201	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	202	s.write=q;
	203	return s.inflate_flush(z,r);
	204
	205	case LENEXT: // i: getting length extra (have base)
	206	j = get;
	207
	208	while(k<(j)){
	209	if(n!=0)r=Z_OK;
	210	else{
	211
	212	s.bitb=b;s.bitk=k;
	213	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	214	s.write=q;
	215	return s.inflate_flush(z,r);
	216	}
	217	n--; b\|=(z.next_in[p++]&0xff)<<k;
	218	k+=8;
	219	}
	220
	221	len += (b & inflate_mask[j]);
	222
	223	b>>=j;
	224	k-=j;
	225
	226	need = dbits;
	227	tree = dtree;
	228	tree_index=dtree_index;
	229	mode = DIST;
	230	case DIST: // i: get distance next
	231	j = need;
	232
	233	while(k<(j)){
	234	if(n!=0)r=Z_OK;
	235	else{
	236
	237	s.bitb=b;s.bitk=k;
	238	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	239	s.write=q;
	240	return s.inflate_flush(z,r);
	241	}
	242	n--; b\|=(z.next_in[p++]&0xff)<<k;
	243	k+=8;
	244	}
	245
	246	tindex=(tree_index+(b & inflate_mask[j]))*3;
	247
	248	b>>=tree[tindex+1];
	249	k-=tree[tindex+1];
	250
	251	e = (tree[tindex]);
	252	if((e & 16)!=0){ // distance
	253	get = e & 15;
	254	dist = tree[tindex+2];
	255	mode = DISTEXT;
	256	break;
	257	}
	258	if ((e & 64) == 0){ // next table
	259	need = e;
	260	tree_index = tindex/3 + tree[tindex+2];
	261	break;
	262	}
	263	mode = BADCODE; // invalid code
	264	z.msg = "invalid distance code";
	265	r = Z_DATA_ERROR;
	266
	267	s.bitb=b;s.bitk=k;
	268	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	269	s.write=q;
	270	return s.inflate_flush(z,r);
	271
	272	case DISTEXT: // i: getting distance extra
	273	j = get;
	274
	275	while(k<(j)){
	276	if(n!=0)r=Z_OK;
	277	else{
	278
	279	s.bitb=b;s.bitk=k;
	280	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	281	s.write=q;
	282	return s.inflate_flush(z,r);
	283	}
	284	n--; b\|=(z.next_in[p++]&0xff)<<k;
	285	k+=8;
	286	}
	287
	288	dist += (b & inflate_mask[j]);
	289
	290	b>>=j;
	291	k-=j;
	292
	293	mode = COPY;
	294	case COPY: // o: copying bytes in window, waiting for space
	295	f = q - dist;
	296	while(f < 0){ // modulo window size-"while" instead
	297	f += s.end; // of "if" handles invalid distances
	298	}
	299	while (len!=0){
	300
	301	if(m==0){
	302	if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	303	if(m==0){
	304	s.write=q; r=s.inflate_flush(z,r);
	305	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	306
	307	if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	308
	309	if(m==0){
	310	s.bitb=b;s.bitk=k;
	311	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	312	s.write=q;
	313	return s.inflate_flush(z,r);
	314	}
	315	}
	316	}
	317
	318	s.window[q++]=s.window[f++]; m--;
	319
	320	if (f == s.end)
	321	f = 0;
	322	len--;
	323	}
	324	mode = START;
	325	break;
	326	case LIT: // o: got literal, waiting for output space
	327	if(m==0){
	328	if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	329	if(m==0){
	330	s.write=q; r=s.inflate_flush(z,r);
	331	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	332
	333	if(q==s.end&&s.read!=0){q=0;m=q<s.read?s.read-q-1:s.end-q;}
	334	if(m==0){
	335	s.bitb=b;s.bitk=k;
	336	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	337	s.write=q;
	338	return s.inflate_flush(z,r);
	339	}
	340	}
	341	}
	342	r=Z_OK;
	343
	344	s.window[q++]=(byte)lit; m--;
	345
	346	mode = START;
	347	break;
	348	case WASH: // o: got eob, possibly more output
	349	if (k > 7){ // return unused byte, if any
	350	k -= 8;
	351	n++;
	352	p--; // can always return one
	353	}
	354
	355	s.write=q; r=s.inflate_flush(z,r);
	356	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	357
	358	if (s.read != s.write){
	359	s.bitb=b;s.bitk=k;
	360	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	361	s.write=q;
	362	return s.inflate_flush(z,r);
	363	}
	364	mode = END;
	365	case END:
	366	r = Z_STREAM_END;
	367	s.bitb=b;s.bitk=k;
	368	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	369	s.write=q;
	370	return s.inflate_flush(z,r);
	371
	372	case BADCODE: // x: got error
	373
	374	r = Z_DATA_ERROR;
	375
	376	s.bitb=b;s.bitk=k;
	377	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	378	s.write=q;
	379	return s.inflate_flush(z,r);
	380
	381	default:
	382	r = Z_STREAM_ERROR;
	383
	384	s.bitb=b;s.bitk=k;
	385	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	386	s.write=q;
	387	return s.inflate_flush(z,r);
	388	}
	389	}
	390	}
	391
	392	void free(ZStream z){
	393	// ZFREE(z, c);
	394	}
	395
	396	// Called with number of bytes left to write in window at least 258
	397	// (the maximum string length) and number of input bytes available
	398	// at least ten. The ten bytes are six bytes for the longest length/
	399	// distance pair plus four bytes for overloading the bit buffer.
	400
	401	int inflate_fast(int bl, int bd,
	402	int[] tl, int tl_index,
	403	int[] td, int td_index,
	404	InfBlocks s, ZStream z){
	405	int t; // temporary pointer
	406	int[] tp; // temporary pointer
	407	int tp_index; // temporary pointer
	408	int e; // extra bits or operation
	409	int b; // bit buffer
	410	int k; // bits in bit buffer
	411	int p; // input data pointer
	412	int n; // bytes available there
	413	int q; // output window write pointer
	414	int m; // bytes to end of window or read pointer
	415	int ml; // mask for literal/length tree
	416	int md; // mask for distance tree
	417	int c; // bytes to copy
	418	int d; // distance back to copy from
	419	int r; // copy source pointer
	420
	421	int tp_index_t_3; // (tp_index+t)*3
	422
	423	// load input, output, bit values
	424	p=z.next_in_index;n=z.avail_in;b=s.bitb;k=s.bitk;
	425	q=s.write;m=q<s.read?s.read-q-1:s.end-q;
	426
	427	// initialize masks
	428	ml = inflate_mask[bl];
	429	md = inflate_mask[bd];
	430
	431	// do until not enough input or output space for fast loop
	432	do { // assume called with m >= 258 && n >= 10
	433	// get literal/length code
	434	while(k<(20)){ // max bits for literal/length code
	435	n--;
	436	b\|=(z.next_in[p++]&0xff)<<k;k+=8;
	437	}
	438
	439	t= b&ml;
	440	tp=tl;
	441	tp_index=tl_index;
	442	tp_index_t_3=(tp_index+t)*3;
	443	if ((e = tp[tp_index_t_3]) == 0){
	444	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
	445
	446	s.window[q++] = (byte)tp[tp_index_t_3+2];
	447	m--;
	448	continue;
	449	}
	450	do {
	451
	452	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
	453
	454	if((e&16)!=0){
	455	e &= 15;
	456	c = tp[tp_index_t_3+2] + ((int)b & inflate_mask[e]);
	457
	458	b>>=e; k-=e;
	459
	460	// decode distance base of block to copy
	461	while(k<(15)){ // max bits for distance code
	462	n--;
	463	b\|=(z.next_in[p++]&0xff)<<k;k+=8;
	464	}
	465
	466	t= b&md;
	467	tp=td;
	468	tp_index=td_index;
	469	tp_index_t_3=(tp_index+t)*3;
	470	e = tp[tp_index_t_3];
	471
	472	do {
	473
	474	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
	475
	476	if((e&16)!=0){
	477	// get extra bits to add to distance base
	478	e &= 15;
	479	while(k<(e)){ // get extra bits (up to 13)
	480	n--;
	481	b\|=(z.next_in[p++]&0xff)<<k;k+=8;
	482	}
	483
	484	d = tp[tp_index_t_3+2] + (b&inflate_mask[e]);
	485
	486	b>>=(e); k-=(e);
	487
	488	// do the copy
	489	m -= c;
	490	if (q >= d){ // offset before dest
	491	// just copy
	492	r=q-d;
	493	if(q-r>0 && 2>(q-r)){
	494	s.window[q++]=s.window[r++]; // minimum count is three,
	495	s.window[q++]=s.window[r++]; // so unroll loop a little
	496	c-=2;
	497	}
	498	else{
	499	System.arraycopy(s.window, r, s.window, q, 2);
	500	q+=2; r+=2; c-=2;
	501	}
	502	}
	503	else{ // else offset after destination
	504	r=q-d;
	505	do{
	506	r+=s.end; // force pointer in window
	507	}while(r<0); // covers invalid distances
	508	e=s.end-r;
	509	if(c>e){ // if source crosses,
	510	c-=e; // wrapped copy
	511	if(q-r>0 && e>(q-r)){
	512	do{s.window[q++] = s.window[r++];}
	513	while(--e!=0);
	514	}
	515	else{
	516	System.arraycopy(s.window, r, s.window, q, e);
	517	q+=e; r+=e; e=0;
	518	}
	519	r = 0; // copy rest from start of window
	520	}
	521
	522	}
	523
	524	// copy all or what's left
	525	if(q-r>0 && c>(q-r)){
	526	do{s.window[q++] = s.window[r++];}
	527	while(--c!=0);
	528	}
	529	else{
	530	System.arraycopy(s.window, r, s.window, q, c);
	531	q+=c; r+=c; c=0;
	532	}
	533	break;
	534	}
	535	else if((e&64)==0){
	536	t+=tp[tp_index_t_3+2];
	537	t+=(b&inflate_mask[e]);
	538	tp_index_t_3=(tp_index+t)*3;
	539	e=tp[tp_index_t_3];
	540	}
	541	else{
	542	z.msg = "invalid distance code";
	543
	544	c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
	545
	546	s.bitb=b;s.bitk=k;
	547	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	548	s.write=q;
	549
	550	return Z_DATA_ERROR;
	551	}
	552	}
	553	while(true);
	554	break;
	555	}
	556
	557	if((e&64)==0){
	558	t+=tp[tp_index_t_3+2];
	559	t+=(b&inflate_mask[e]);
	560	tp_index_t_3=(tp_index+t)*3;
	561	if((e=tp[tp_index_t_3])==0){
	562
	563	b>>=(tp[tp_index_t_3+1]); k-=(tp[tp_index_t_3+1]);
	564
	565	s.window[q++]=(byte)tp[tp_index_t_3+2];
	566	m--;
	567	break;
	568	}
	569	}
	570	else if((e&32)!=0){
	571
	572	c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
	573
	574	s.bitb=b;s.bitk=k;
	575	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	576	s.write=q;
	577
	578	return Z_STREAM_END;
	579	}
	580	else{
	581	z.msg="invalid literal/length code";
	582
	583	c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
	584
	585	s.bitb=b;s.bitk=k;
	586	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	587	s.write=q;
	588
	589	return Z_DATA_ERROR;
	590	}
	591	}
	592	while(true);
	593	}
	594	while(m>=258 && n>= 10);
	595
	596	// not enough input or output--restore pointers and return
	597	c=z.avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;
	598
	599	s.bitb=b;s.bitk=k;
	600	z.avail_in=n;z.total_in+=p-z.next_in_index;z.next_in_index=p;
	601	s.write=q;
	602
	603	return Z_OK;
	604	}
	605	}