pgpzinflate.c

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

		lim = ctx->bitlengths;

		while (i < lim) {
		 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->bitlen, 19, 19, NULL, NULL, &t, &k);
		if (i) {
		 if (i == 1)
		  huft_free(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;
}

/* The static tree (built on demand) */
static struct huft *fixed_tl = NULL;
static struct huft *fixed_td;
static unsigned fixed_bl, fixed_bd;

static int
infFixedTree(void)
{
		int i;
		unsigned char l[288];

		if (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;
fixed_bl = 7;
i = huft_build(l, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl);
	if (i != 0) {
	 fixed_tl = NULL;
	return INFERR_NOMEM;
	}

	/* distance table */
	for (i = 0; i < 30; i++)	/* make an incomplete code set */
	 l[i] = 5;
	fixed_bd = 5;
i = huft_build(l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd);
if (i > 1) {
 huft_free(fixed_tl);
 fixed_tl = NULL;
 return INFERR_NOMEM;
}

return 0;
}

static int
infDynTree(struct InflateContext *ctx)
{
ulg b;
unsigned k;
int s;
unsigned char const *g;
struct 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(tl);
		ctx->tree1 = 0;

		/* Now build the trees - literal/length, then distance */

		bl = LBITS;
		i = huft_build(ctx->bitlen, ctx->litcodes, 257,
			cplens, cplext, &tl, &bl);
		if (i != 0) {
		 if (i == 1)
		  huft_free(tl);
		 return i == 3 ? INFERR_NOMEM : INFERR_BADINPUT;
		}
		bd = DBITS;
		i = huft_build(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(td);
	#endif
			huft_free(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(struct 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) */

struct huft *tl, *td; /* Tree info (const except for EOB processing) */
unsigned bl, bd;
unsigned ml, md;
struct 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;