zinflate.cpp

300种加密解密的算法源代码

  while (p != (huft *)NULL)
  {
	q = (--p)->v.t;
	free((char*)p);
	p = q;
  }
  return 0;
}


int Inflator::inflate_codes(huft *tl, huft *td, int bl, int bd)
/* inflate (decompress) the codes in a deflated (compressed) block.
   Return an error code or zero if it all goes ok. */
{
  register unsigned e;  /* table entry flag/number of extra bits */
  unsigned n, d;        /* length and index for copy */
  unsigned w;           /* current window position */
  huft *t;       /* pointer to table entry */
  unsigned ml, md;      /* masks for bl and bd bits */
  register word32 b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


  /* make local copies of globals */
  b = bb;                       /* initialize bit buffer */
  k = bk;
  w = wp;                       /* initialize window position */

  /* inflate the coded data */
  ml = mask_bits[bl];           /* precompute masks for speed */
  md = mask_bits[bd];
  for (;;)                      /* do until end of block */
  {
	NEEDBITS((unsigned)bl)
	if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
	  do {
		if (e == 99)
		  return 1;
		DUMPBITS(t->b)
		e -= 16;
		NEEDBITS(e)
	  } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
	DUMPBITS(t->b)
	if (e == 16)                /* then it's a literal */
	{
	  slide[w++] = (byte)t->v.n;
	  Tracevv((stderr, "%c", slide[w-1]));
	  if (w == WSIZE)
	  {
		flush_output(w);
		w = 0;
	  }
	}
	else                        /* it's an EOB or a length */
	{
	  /* exit if end of block */
	  if (e == 15)
		break;

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

	  /* decode distance of block to copy */
	  NEEDBITS((unsigned)bd)
	  if ((e = (t = td + ((unsigned)b & md))->e) > 16)
		do {
		  if (e == 99)
			return 1;
		  DUMPBITS(t->b)
		  e -= 16;
		  NEEDBITS(e)
		} while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
	  DUMPBITS(t->b)
	  NEEDBITS(e)
	  d = w - t->v.n - ((unsigned)b & mask_bits[e]);
	  DUMPBITS(e)
	  Tracevv((stderr,"\\[%d,%d]", w-d, n));

	  /* do the copy */
	  do {
		n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
#if !defined(NOMEMCPY) && !defined(DEBUG)
		if (w - d >= e)         /* (this test assumes unsigned comparison) */
		{
		  memcpy(slide + w, slide + d, e);
		  w += e;
		  d += e;
		}
		else                      /* do it slow to avoid memcpy() overlap */
#endif /* !NOMEMCPY */
		  do {
			slide[w++] = slide[d++];
		Tracevv((stderr, "%c", slide[w-1]));
		  } while (--e);
		if (w == WSIZE)
		{
		  flush_output(w);
		  w = 0;
		}
	  } while (n);
	}
  }


  /* restore the globals from the locals */
  wp = w;                       /* restore global window pointer */
  bb = b;                       /* restore global bit buffer */
  bk = k;

  /* done */
  return 0;
}



int Inflator::inflate_stored()
/* "decompress" an inflated type 0 (stored) block. */
{
  unsigned n;           /* number of bytes in block */
  unsigned w;           /* current window position */
  register word32 b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


  /* make local copies of globals */
  b = bb;                       /* initialize bit buffer */
  k = bk;
  w = wp;                       /* initialize window position */


  /* go to byte boundary */
  n = k & 7;
  DUMPBITS(n);


  /* get the length and its complement */
  NEEDBITS(16)
  n = ((unsigned)b & 0xffff);
  DUMPBITS(16)
  NEEDBITS(16)
  if (n != (unsigned)((~b) & 0xffff))
	return 1;                   /* error in compressed data */
  DUMPBITS(16)


  /* read and output the compressed data */
  while (n--)
  {
	NEEDBITS(8)
	slide[w++] = (byte)b;
	if (w == WSIZE)
	{
	  flush_output(w);
	  w = 0;
	}
	DUMPBITS(8)
  }


  /* restore the globals from the locals */
  wp = w;                       /* restore global window pointer */
  bb = b;                       /* restore global bit buffer */
  bk = k;
  return 0;
}



int Inflator::inflate_fixed()
/* decompress an inflated type 1 (fixed Huffman codes) block.  We should
   either replace this with a custom decoder, or at least precompute the
   Huffman tables. */
{
  int i;                /* temporary variable */
  huft *tl;      /* literal/length code table */
  huft *td;      /* distance code table */
  int bl;               /* lookup bits for tl */
  int bd;               /* lookup bits for td */
  unsigned l[288];      /* length list for huft_build */


  /* set up 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;
  bl = 7;
  if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
	return i;


  /* set up distance table */
  for (i = 0; i < 30; i++)      /* make an incomplete code set */
	l[i] = 5;
  bd = 5;
  if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
  {
	huft_free(tl);
	return i;
  }


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


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



int Inflator::inflate_dynamic()
/* decompress an inflated type 2 (dynamic Huffman codes) block. */
{
  int i;                /* temporary variables */
  unsigned j;
  unsigned l;           /* last length */
  unsigned m;           /* mask for bit lengths table */
  unsigned n;           /* number of lengths to get */
  huft *tl;      /* literal/length code table */
  huft *td;      /* distance code table */
  int bl;               /* lookup bits for tl */
  int bd;               /* lookup bits for td */
  unsigned nb;          /* number of bit length codes */
  unsigned nl;          /* number of literal/length codes */
  unsigned nd;          /* number of distance codes */
#ifdef PKZIP_BUG_WORKAROUND
  unsigned ll[288+32];  /* literal/length and distance code lengths */
#else
  unsigned ll[286+30];  /* literal/length and distance code lengths */
#endif
  register word32 b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


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


  /* read in table lengths */
  NEEDBITS(5)
  nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
  DUMPBITS(5)
  NEEDBITS(5)
  nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
  DUMPBITS(5)
  NEEDBITS(4)
  nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
  DUMPBITS(4)
#ifdef PKZIP_BUG_WORKAROUND
  if (nl > 288 || nd > 32)
#else
  if (nl > 286 || nd > 30)
#endif
	return 1;                   /* bad lengths */


  /* read in bit-length-code lengths */
  for (j = 0; j < nb; j++)
  {
	NEEDBITS(3)
	ll[border[j]] = (unsigned)b & 7;
	DUMPBITS(3)
  }
  for (; j < 19; j++)
	ll[border[j]] = 0;


  /* build decoding table for trees--single level, 7 bit lookup */
  bl = 7;
  if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
  {
	if (i == 1)
	  huft_free(tl);
	return i;                   /* incomplete code set */
  }


  /* read in literal and distance code lengths */
  n = nl + nd;
  m = mask_bits[bl];
  i = l = 0;
  while ((unsigned)i < n)
  {
	NEEDBITS((unsigned)bl)
	j = (td = tl + ((unsigned)b & m))->b;
	DUMPBITS(j)
	j = td->v.n;
	if (j < 16)                 /* length of code in bits (0..15) */
	  ll[i++] = l = j;          /* save last length in l */
	else if (j == 16)           /* repeat last length 3 to 6 times */
	{
	  NEEDBITS(2)
	  j = 3 + ((unsigned)b & 3);
	  DUMPBITS(2)
	  if ((unsigned)i + j > n)
		return 1;
	  while (j--)
		ll[i++] = l;
	}
	else if (j == 17)           /* 3 to 10 zero length codes */
	{
	  NEEDBITS(3)
	  j = 3 + ((unsigned)b & 7);
	  DUMPBITS(3)
	  if ((unsigned)i + j > n)
		return 1;
	  while (j--)
		ll[i++] = 0;
	  l = 0;
	}
	else                        /* j == 18: 11 to 138 zero length codes */
	{
	  NEEDBITS(7)
	  j = 11 + ((unsigned)b & 0x7f);
	  DUMPBITS(7)
	  if ((unsigned)i + j > n)
		return 1;
	  while (j--)
		ll[i++] = 0;
	  l = 0;
	}
  }


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


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


  /* build the decoding tables for literal/length and distance codes */
  bl = lbits;
  if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
  {
	if (i == 1) {
//      fprintf(stderr, " incomplete literal tree\n");
	  huft_free(tl);
	}
	return i;                   /* incomplete code set */
  }
  bd = dbits;
  if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
  {
	if (i == 1) {
//      fprintf(stderr, " incomplete distance tree\n");
#ifdef PKZIP_BUG_WORKAROUND
	  i = 0;
	}
#else
	  huft_free(td);
	}
	huft_free(tl);
	return i;                   /* incomplete code set */
#endif
  }


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


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



int Inflator::inflate_block(bool &e)
/* decompress an inflated block */
{
  unsigned t;           /* block type */
  register word32 b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


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


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


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


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


  int status;

  /* inflate that block type */
  switch (t)
  {
	case 0:
		status = inflate_stored();
		break;
	case 1:
		status = inflate_fixed();
		break;
	case 2:
		status = inflate_dynamic();
		break;
	default:
		status = 2;
  }
	if (status)
		throw Err("Inflator: error decompressing block");
	return status;
}

NAMESPACE_END