inflate.c

来自「kaffe Java 解释器语言,源码,Java的子集系统,开放源代码」· C语言 代码 · 共 837 行 · 第 1/2 页

    }
  }


  /* free decoding table for trees */
  huft_free(tl);


  /* restore the global bit buffer */
  pG->bb = b;
  pG->bk = k;


  /* build the decoding tables for literal/length and distance codes */
  bl = LBITS;
  i = huft_build(pG, ll, nl, 257, cplens, cplext, &tl, &bl);
  if (bl == 0)                        /* no literals or lengths */
    i = 1;
  if (i)
  {
    if (i == 1) {
      huft_free(tl);
    }
    return i;                   /* incomplete code set */
  }
  bd = DBITS;
  i = huft_build(pG, ll + nl, nd, 0, cpdist, cpdext, &td, &bd);
  if (bd == 0 && nl > 257)    /* lengths but no distances */
  {
    huft_free(tl);
    return 1;
  }
  if (i == 1) {
    i = 0;
  }
  if (i)
  {
    huft_free(tl);
    return i;
  }


  /* decompress until an end-of-block code */
  if (inflate_codes(pG, tl, td, bl, bd))
    return 1;


  /* free the decoding tables, return */
  huft_free(tl);
  huft_free(td);
  return 0;
}



static
int
inflate_block(inflateInfo* pG, int* e)
{
  unsigned t;           /* block type */
  register uint32 b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


  /* make local bit buffer */
  b = pG->bb;
  k = pG->bk;


  /* read in last block bit */
  NEEDBITS(pG, 1)
  *e = (int)b & 1;
  DUMPBITS(pG, 1)


  /* read in block type */
  NEEDBITS(pG, 2)
  t = (unsigned)b & 3;
  DUMPBITS(pG, 2)


  /* restore the global bit buffer */
  pG->bb = b;
  pG->bk = k;


  /* inflate that block type */
  if (t == 2)
    return inflate_dynamic(pG);
  if (t == 0)
    return inflate_stored(pG);
  if (t == 1)
    return inflate_fixed(pG);


  /* bad block type */
  return 2;
}

/*
 * Create a new inflater.
 */
inflateInfo*
inflate_new(void)
{
	inflateInfo* info;

	info = gc_malloc(sizeof(inflateInfo), GC_ALLOC_FIXED);
	if (!info) {
		return 0;
	}
	info->fixed_tl = 0;
	info->fixed_td = 0;
	info->fixed_bl = 0;
	info->fixed_bd = 0;
	info->slide = gc_malloc(WSIZE, GC_ALLOC_FIXED);
	if (!info->slide){
		gc_free(info);
		return 0;
	}

	return (info);
}

/*
 * We pass in a buffer of deflated data and a place to stored the inflated
 * result.  This does not provide continuous operation and should only be
 * use in "one shot" more.
 */
int
inflate_oneshot(uint8* ibuf, int ilen, uint8* obuf, int olen)
{
	int r;                /* result code: 0 on success */
	inflateInfo* pG;

	pG = inflate_new();

	if (!pG) {
		return 1;
	}
	
	pG->inbuf = ibuf;
	pG->insz = ilen;
	pG->outbuf = obuf;
	pG->outsz = olen;

	r = inflate(pG);

	inflate_free(pG);

	return (r);
}

/*
 * Inflate the given data into the given buffer.
 */
static
int
inflate(inflateInfo* pG)
{
  int e;                /* last block flag */
  int r;                /* result code */
  unsigned h;           /* maximum huft's malloc'ed */

  /* initialize window, bit buffer */
  pG->wp = 0;
  pG->bk = 0;
  pG->bb = 0;

  /* decompress until the last block */
  h = 0;
  do {
    pG->hufts = 0;
    if ((r = inflate_block(pG, &e)) != 0) {
      return r;
    }
    if (pG->hufts > h) {
      h = pG->hufts;
    }
  } while (!e);


  /* flush out G.slide */
  FLUSH(pG, pG->wp);

  /* return success */
  IDBG(dprintf("\n%u bytes in Huffman tables (%d/entry)\n", h * sizeof(huft), sizeof(huft)));
  return 0;
}

int
inflate_free(inflateInfo* pG)
{
  if (pG != 0) {
    if (pG->fixed_tl != 0) {
      huft_free(pG->fixed_td);
      huft_free(pG->fixed_tl);
      pG->fixed_td = pG->fixed_tl = 0;
    }
    gc_free(pG->slide);
    gc_free(pG);
  }

  return 0;
}


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

static
int
huft_build(inflateInfo* pG, unsigned* b, unsigned n, unsigned s, uint16* d, uint16* e, huft** t, int* m)
{
  unsigned a;                   /* counter for codes of length k */
  unsigned c[BMAX+1];           /* bit length count table */
  unsigned el;                  /* length of EOB code (value 256) */
  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 lx[BMAX+1];               /* memory for l[-1..BMAX-1] */
  int *l = lx+1;                /* stack of bits per table */
  register unsigned *p;         /* pointer into c[], b[], 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 */
  el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */
  memset(c, 0, sizeof(c));
  p = b;  i = n;
  do {
    c[*p]++; p++;               /* assume all entries <= BMAX */
  } while (--i);
  if (c[0] == n)                /* null input--all zero length codes */
  {
    *t = 0;
    *m = 0;
    return 0;
  }


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


  /* 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 */
  memset(v, 0, sizeof(v));
  p = b;  i = 0;
  do {
    if ((j = *p++) != 0)
      v[x[j]++] = i;
  } while (++i < n);
  n = x[g];                     /* set n to length of v */


  /* 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[-1] = 0;                /* no bits decoded yet */
  u[0] = 0;   /* just to keep compilers happy */
  q = 0;      /* 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[h++];            /* add bits already decoded */

        /* compute minimum size table less than or equal to *m bits */
        z = (z = g - w) > (unsigned)*m ? *m : z;        /* upper limit */
        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 */
          }
        }
        if ((unsigned)w + j > el && (unsigned)w < el)
          j = el - w;           /* make EOB code end at table */
        z = 1 << j;             /* table entries for j-bit table */
        l[h] = j;               /* set table size in stack */

        /* allocate and link in new table */
        if ((q = (huft *)gc_malloc((z + 1)*sizeof(huft), GC_ALLOC_FIXED)) ==
            0)
        {
          if (h)
            huft_free(u[0]);
          return 3;             /* not enough memory */
        }
        pG->hufts += z + 1;         /* track memory usage */
        *t = q + 1;             /* link to list for huft_free() */
        *(t = &(q->v.t)) = 0;
        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.b = (uint8)l[h-1];    /* bits to dump before this table */
          r.e = (uint8)(16 + j);  /* bits in this table */
          r.v.t = q;            /* pointer to this table */
          j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
          u[h-1][j] = r;        /* connect to last table */
        }
      }

      /* set up table entry in r */
      r.b = (uint8)(k - w);
      if (p >= v + n)
        r.e = 99;               /* out of values--invalid code */
      else if (*p < s)
      {
        r.e = (uint8)(*p < 256 ? 16 : 15);  /* 256 is end-of-block code */
        r.v.n = (uint16)*p++;                /* simple code is just the value */
      }
      else
      {
        r.e = (uint8)e[*p - s];   /* non-simple--look up in lists */
        r.v.n = 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;

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


  /* return actual size of base table */
  *m = l[0];


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



static
int
huft_free(huft* t)
{
  huft *p, *q;

  /* Go through linked list, freeing from the malloced (t[-1]) address. */
  p = t;
  while (p != 0)
  {
    q = (--p)->v.t;
    gc_free(p);
    p = q;
  }
  return 0;
}