pgpzinflate.c

vc环境下的pgp源码

 * If that happens, the more expensive value, x2, is used.
 */
#define NEEDBITS2(x, x2, savestate) \
	NEEDBITS(x, if (k >= (unsigned)(x2)) {s=0; break;} savestate)

#define DUMPBITS(x) (b >>= x, k -= x)

/*
 * Huffman code decoding is performed using a multi-level table lookup.
 * The fastest way to decode is to simply build a lookup table whose
 * size is determined by the longest code.  However, the time it takes
 * to build this table can also be a factor if the data being decoded
 * is not very long.  The most common codes are necessarily the
 * shortest codes, so those codes dominate the decoding time, and hence
 * the speed.  The idea is you can have a shorter table that decodes the
 * shorter, more probable codes, and then point to subsidiary tables for
 * the longer codes.  The time it costs to decode the longer codes is
 * then traded against the time it takes to make longer tables.
 *
 * This results of this trade are in the values LBITS and DBITS
 * below.  LBITS is the number of bits the first level table for literal/
 * length codes can decode in one step, and DBITS is the same thing for
 * the distance codes.  Subsequent tables are also less than or equal to
 * those sizes.  These values may be adjusted either when all of the
 * codes are shorter than that, in which case the longest code length in
 * bits is used, or when the shortest code is *longer* than the requested
 * table size, in which case the length of the shortest code in bits is
 * used.
 *
 * There are two different values for the two tables, since they code a
 * different number of possibilities each.  The literal/length table
 * codes 286 possible values, or in a flat code, a little over eight
 * bits.  The distance table codes 30 possible values, or a little less
 * than five bits, flat.  The optimum values for speed end up being
 * about one bit more than those, so LBITS is 8+1 and DBITS is 5+1.
 * The optimum values may differ though from machine to machine, and
 * possibly even between compilers.  Your mileage may vary.
 */

#define LBITS 9   /* bits in base literal/length lookup table */
#define DBITS 6   /* bits in base distance lookup table */

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

#if defined(__STDC__) || defined(__cplusplus)
static int
huft_build( PGPContextRef context,
		unsigned char const *b, unsigned n, unsigned s, ush const *d,
	   ush const *e, huft **t, unsigned *m)
#else
static int
huft_build(context, b, n, s, d, e, t, m)
PGPContextRef context;	/* context for memory allocation */
unsigned char *b;       /* code lengths in bits (all assumed <= BMAX) */
unsigned n;             /* number of codes (assumed <= N_MAX) */
unsigned s;             /* number of simple-valued codes (0..s-1) */
ush const *d;           /* list of base values for non-simple codes */
ush const *e;           /* list of extra bits for non-simple codes */
huft **t;        /* result: starting table */
unsigned *m;            /* suggested lookup bits, returns actual */
#endif
/*
 * Given a list of code lengths and a maximum table size, make a set of
 * tables to decode that set of codes.  Return values:
 * 0 = success
 * 1 = the given code set is incomplete
 *     (the tables are still built in this case)
 * 2 = the input is invalid
 *     (all zero length codes or an oversubscribed set of lengths)
 * 3 = not enough memory.
 */
{
  unsigned a;                   /* counter for codes of length k */
  unsigned c[BMAX+1];           /* bit length count table */
  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 l;                        /* bits per table (returned in m) */
  register unsigned char const *bp;	/* pointer into b[] */
  register unsigned *p;         /* pointer into c[] 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 */
  pgpClearMemory( c,  sizeof(c));
  bp = b;  i = n;
  do {
    c[*bp++]++;                 /* assume all entries <= BMAX */
  } while (--i);
  if (c[0] == n)                /* null input--all zero length codes */
  {
    *t = (huft *)NULL;
    *m = 0;
    return 0;
  }


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


  /* 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 */
  bp = b;  i = 0;
  do {
    if ((j = *bp++) != 0)
      v[x[j]++] = i;
  } while (++i < n);


  /* 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;                       /* bits decoded == (l * h) */
  u[0] = (huft *)NULL;   /* just to keep compilers happy */
  q = (huft *)NULL;      /* 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;                 /* previous table always l bits */

	/* compute minimum size table less than or equal to l bits */
	z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
	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 */
	  }
	}
	z = 1 << j;             /* table entries for j-bit table */

	/* allocate and link in new table */
	if ((q = (huft *)pgpContextMemAlloc( context, (z + 1)*sizeof(huft),
		0)) == (huft *)NULL)
	{
	  if (h)
	    huft_free( context, u[0]);
	  return 3;             /* not enough memory */
	}
#if SECURE
	q->bits = (char)j;	/* Track size for free */
#endif
	*t = q + 1;             /* link to list for huft_free() */
	*(t = &(q->next)) = (huft *)NULL;
	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.bits = (char)l;     /* bits to dump before this table */
	  r.exop = -(char)j;    /* bits in this table */
	  r.next = q;           /* pointer to this table */
	  j = i >> (w - l);     /* (get around Turbo C bug) */
	  u[h-1][j] = r;        /* connect to last table */
	}
      }

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

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


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


#if defined(__STDC__) || defined(__cplusplus)
static int
huft_free(PGPContextRef context, huft *t)
#else
static int
huft_free( context, t)
PGPContextRef context;	/* context for memory allocation */
huft *t;				/* table to free */
#endif
/*
 * Free the malloc'ed tables built by huft_build(), which makes a linked
 * list of the tables it made, with the links in a dummy -1st entry of
 * each table.
 */
{
  register huft *p, *q;

  /* Go through linked list, freeing from the malloced (t[-1]) address. */
  p = t;
  while (p != (huft *)NULL)
  {
    q = (--p)->next;
#if SECURE
    pgpClearMemory( p,  (1+(1<<p->bits)) * sizeof(*p));
#endif
    pgpContextMemFree( context, p);
    p = q;
  }
  return 0;
}


/*
 * Colin's new code.
 */

#define STATE_START	0
#define	STATE_STOREDLEN	1
#define STATE_STORED	2
#define	STATE_DYN_HDR	3
#define	STATE_DYN_BITS	4
#define STATE_DYN_TREE	5
#define STATE_INFLATE	6
#define STATE_DONE	7
#define STATE_STOP	8

/*
 * All these functions return
 * 2 if the output buffer is full
 * 1 if the input buffer is empty
 *  0 if things should continue with the new ctx->state, and
 * <0 on error.
 */

static int
infStoredLen(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	unsigned t;

	LOADBITBUF;
	t = k & 7;
#if STRICT
	if (b & mask[t])	/* Require unused bits are zero */
		return INFERR_BADINPUT;
#endif
	DUMPBITS(t);

	NEEDBITS(32, (void)0);

	/* At this point, k is exactly 32 */

	ctx->copylen = (unsigned)b & 0xffff;
	t = ~(unsigned)(b>>16) & 0xffff;
	b = 0;
	k = 0;

	SAVEBITBUF;
	if (t != ctx->copylen)
		return INFERR_BADINPUT;	/* Two lengths not identical */

	ctx->state = STATE_STORED;
	ctx->substate = 0;

	return 0;
}

/*
 * Process the data in a stored block.  Copy the input data to
 * the circular buffer, flushing it as necessary.
 */
static int
infStored(InflateContext *ctx)
{
	int len;	/* # of bytes to copy */
	int retval = 1;	/* Out of memory */

	pgpAssert(ctx->bufbits == 0);

	len = ctx->inlen;
	if ((unsigned)len >= ctx->copylen) {
		len = ctx->copylen;	/* Copy done! */
		ctx->state = STATE_START;
		retval = 0;
	}
	if (len > ctx->slideend-ctx->outptr) {
		len = (int)(ctx->slideend-ctx->outptr);
		retval = 2;	/* Output buffer full */
		ctx->state = STATE_STORED;
	}

	memcpy(ctx->outptr, ctx->inptr, len);
	ctx->inptr += len;
	ctx->inlen -= len;
	ctx->outptr += len;
	ctx->copylen -= (unsigned)len;

	/* Return 2 if output full, 1 if input empty, 0 otherwise (copy done)*/
	return retval;
}

static int
infDynHdr(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;

	LOADBITBUF;
	NEEDBITS(14, (void)0);

	ctx->litcodes = 257 + ((unsigned)b & 0x1f);
	DUMPBITS(5);
	ctx->distcodes = 1 + ((unsigned)b & 0x1f);
	DUMPBITS(5);
	ctx->bitlengths = 4 + ((unsigned)b & 0xf);
	DUMPBITS(4);

	SAVEBITBUF;

#ifndef PKZIP_BUG_WORKAROUND
	if (ctx->litcodes > 286 || ctx->distcodes > 30)
		return INFERR_BADINPUT;	/* Bad lengths */
#endif
	ctx->state = STATE_DYN_BITS;
	return 0;
}

/* Load up the ctx->bitlen array with the bit lengths for the encoded
 * trees.  Unpermute them according to the border[] array.
 */
static int
infDynBits(InflateContext *ctx)
{
	ulg b;
	unsigned k;
	int s;
	unsigned char const *g;
	huft *t;
	int i, lim;

	LOADBITBUF;
	i = ctx->substate;
	lim = ctx->bitlengths;

	while (i < lim) {