pgpzinflate.c

PGP—Pretty Good Privacy

		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;