pgpzinflate.c

著名的加密软件的应用于电子邮件中

*/
#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(unsigned char const *b, unsigned n, unsigned s, ush const *d,
 ush const *e, struct huft **t, unsigned *m)
#else
static int
huft_build(b, n, s, d, e, t, m)
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 */
	struct 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 struct huft *q;	/* points to current table */
	struct huft r;	/* table entry for structure assignment */
	struct 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 */
	memset(c, 0, 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 = (struct 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] = (struct huft *)NULL; /* just to keep compilers happy */
		q = (struct 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 = (struct huft *)pgpMemAlloc((z + 1)*sizeof(struct huft))) ==
		(struct huft *)NULL)
		{
		if (h)
		huft_free(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)) = (struct 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(struct huft *t)
#else
	static int
	huft_free(t)
	struct 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 struct huft *p, *q;

/* Go through linked list, freeing from the malloced (t[-1]) address. */
p = t;
while (p != (struct huft *)NULL)
{
q = (--p)->next;
#if SECURE
memset(p, 0, (1+(1<<p->bits)) * sizeof(*p));
#endif
pgpMemFree(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(struct 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(struct 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 */
		}

		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(struct 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(struct InflateContext *ctx)
{
 ulg b;
 unsigned k;
 int s;
		unsigned char const *g;
		struct huft *t;
		int i, lim;

		LOADBITBUF;
		i = ctx->substate;