decompress_unzip.c

busybox最新版的源码:学习和应用的好东东,多的不说了,大家看后再说吧

			while (k > ws[htl + 1]) {
				w = ws[++htl];

				/* compute minimum size table less than or equal to *m bits */
				z = g - w;
				z = z > *m ? *m : z; /* upper limit on table size */
				j = k - w;
				f = 1 << j;
				if (f > 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 */
						f <<= 1;
						if (f <= *++xp) {
							break; /* enough codes to use up j bits */
						}
						f -= *xp; /* else deduct codes from patterns */
					}
				}
				j = (w + j > eob_len && w < eob_len) ? eob_len - w : j;	/* make EOB code end at table */
				z = 1 << j;	/* table entries for j-bit table */
				ws[htl+1] = w + j;	/* set bits decoded in stack */

				/* allocate and link in new table */
				q = xzalloc((z + 1) * sizeof(huft_t));
				*t = q + 1;	/* link to list for huft_free() */
				t = &(q->v.t);
				u[htl] = ++q;	/* table starts after link */

				/* connect to last table, if there is one */
				if (htl) {
					x[htl] = i; /* save pattern for backing up */
					r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
					r.e = (unsigned char) (16 + j); /* bits in this table */
					r.v.t = q; /* pointer to this table */
					j = (i & ((1 << w) - 1)) >> ws[htl - 1];
					u[htl - 1][j] = r; /* connect to last table */
				}
			}

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

			/* backup over finished tables */
			while ((i & ((1 << w) - 1)) != x[htl]) {
				w = ws[--htl];
			}
		}
	}

	/* return actual size of base table */
	*m = ws[1];

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


/*
 * inflate (decompress) the codes in a deflated (compressed) block.
 * Return an error code or zero if it all goes ok.
 *
 * tl, td: literal/length and distance decoder tables
 * bl, bd: number of bits decoded by tl[] and td[]
 */
/* called once from inflate_block */

/* map formerly local static variables to globals */
#define ml inflate_codes_ml
#define md inflate_codes_md
#define bb inflate_codes_bb
#define k  inflate_codes_k
#define w  inflate_codes_w
#define tl inflate_codes_tl
#define td inflate_codes_td
#define bl inflate_codes_bl
#define bd inflate_codes_bd
#define nn inflate_codes_nn
#define dd inflate_codes_dd
static void inflate_codes_setup(STATE_PARAM huft_t * my_tl, huft_t * my_td, const unsigned my_bl, const unsigned my_bd)
{
	tl = my_tl;
	td = my_td;
	bl = my_bl;
	bd = my_bd;
	/* make local copies of globals */
	bb = gunzip_bb;			/* initialize bit buffer */
	k = gunzip_bk;
	w = gunzip_outbuf_count;	/* initialize gunzip_window position */
	/* inflate the coded data */
	ml = mask_bits[bl];		/* precompute masks for speed */
	md = mask_bits[bd];
}
/* called once from inflate_get_next_window */
static int inflate_codes(STATE_PARAM_ONLY)
{
	unsigned e;	/* table entry flag/number of extra bits */
	huft_t *t;	/* pointer to table entry */

	if (resume_copy) goto do_copy;

	while (1) {			/* do until end of block */
		bb = fill_bitbuffer(PASS_STATE bb, &k, bl);
		t = tl + ((unsigned) bb & ml);
		e = t->e;
		if (e > 16)
			do {
				if (e == 99) {
//shouldn't we propagate error?
					bb_error_msg_and_die("inflate_codes error 1");
				}
				bb >>= t->b;
				k -= t->b;
				e -= 16;
				bb = fill_bitbuffer(PASS_STATE bb, &k, e);
				t = t->v.t + ((unsigned) bb & mask_bits[e]);
				e = t->e;
			} while (e > 16);
		bb >>= t->b;
		k -= t->b;
		if (e == 16) {	/* then it's a literal */
			gunzip_window[w++] = (unsigned char) t->v.n;
			if (w == GUNZIP_WSIZE) {
				gunzip_outbuf_count = w;
				//flush_gunzip_window();
				w = 0;
				return 1; // We have a block to read
			}
		} else {		/* it's an EOB or a length */
			/* exit if end of block */
			if (e == 15) {
				break;
			}

			/* get length of block to copy */
			bb = fill_bitbuffer(PASS_STATE bb, &k, e);
			nn = t->v.n + ((unsigned) bb & mask_bits[e]);
			bb >>= e;
			k -= e;

			/* decode distance of block to copy */
			bb = fill_bitbuffer(PASS_STATE bb, &k, bd);
			t = td + ((unsigned) bb & md);
			e = t->e;
			if (e > 16)
				do {
					if (e == 99)
//shouldn't we propagate error?
						bb_error_msg_and_die("inflate_codes error 2");
					bb >>= t->b;
					k -= t->b;
					e -= 16;
					bb = fill_bitbuffer(PASS_STATE bb, &k, e);
					t = t->v.t + ((unsigned) bb & mask_bits[e]);
					e = t->e;
				} while (e > 16);
			bb >>= t->b;
			k -= t->b;
			bb = fill_bitbuffer(PASS_STATE bb, &k, e);
			dd = w - t->v.n - ((unsigned) bb & mask_bits[e]);
			bb >>= e;
			k -= e;

			/* do the copy */
 do_copy:
			do {
				/* Was: nn -= (e = (e = GUNZIP_WSIZE - ((dd &= GUNZIP_WSIZE - 1) > w ? dd : w)) > nn ? nn : e); */
				/* Who wrote THAT?? rewritten as: */
				dd &= GUNZIP_WSIZE - 1;
				e = GUNZIP_WSIZE - (dd > w ? dd : w);
				if (e > nn) e = nn;
				nn -= e;

				/* copy to new buffer to prevent possible overwrite */
				if (w - dd >= e) {	/* (this test assumes unsigned comparison) */
					memcpy(gunzip_window + w, gunzip_window + dd, e);
					w += e;
					dd += e;
				} else {
					/* do it slow to avoid memcpy() overlap */
					/* !NOMEMCPY */
					do {
						gunzip_window[w++] = gunzip_window[dd++];
					} while (--e);
				}
				if (w == GUNZIP_WSIZE) {
					gunzip_outbuf_count = w;
					resume_copy = (nn != 0);
					//flush_gunzip_window();
					w = 0;
					return 1;
				}
			} while (nn);
			resume_copy = 0;
		}
	}

	/* restore the globals from the locals */
	gunzip_outbuf_count = w;	/* restore global gunzip_window pointer */
	gunzip_bb = bb;			/* restore global bit buffer */
	gunzip_bk = k;

	/* normally just after call to inflate_codes, but save code by putting it here */
	/* free the decoding tables, return */
	huft_free(tl);
	huft_free(td);

	/* done */
	return 0;
}
#undef ml
#undef md
#undef bb
#undef k
#undef w
#undef tl
#undef td
#undef bl
#undef bd
#undef nn
#undef dd


/* called once from inflate_block */
static void inflate_stored_setup(STATE_PARAM int my_n, int my_b, int my_k)
{
	inflate_stored_n = my_n;
	inflate_stored_b = my_b;
	inflate_stored_k = my_k;
	/* initialize gunzip_window position */
	inflate_stored_w = gunzip_outbuf_count;
}
/* called once from inflate_get_next_window */
static int inflate_stored(STATE_PARAM_ONLY)
{
	/* read and output the compressed data */
	while (inflate_stored_n--) {
		inflate_stored_b = fill_bitbuffer(PASS_STATE inflate_stored_b, &inflate_stored_k, 8);
		gunzip_window[inflate_stored_w++] = (unsigned char) inflate_stored_b;
		if (inflate_stored_w == GUNZIP_WSIZE) {
			gunzip_outbuf_count = inflate_stored_w;
			//flush_gunzip_window();
			inflate_stored_w = 0;
			inflate_stored_b >>= 8;
			inflate_stored_k -= 8;
			return 1; // We have a block
		}
		inflate_stored_b >>= 8;
		inflate_stored_k -= 8;
	}

	/* restore the globals from the locals */
	gunzip_outbuf_count = inflate_stored_w;		/* restore global gunzip_window pointer */
	gunzip_bb = inflate_stored_b;	/* restore global bit buffer */
	gunzip_bk = inflate_stored_k;
	return 0; // Finished
}


/*
 * decompress an inflated block
 * e: last block flag
 *
 * GLOBAL VARIABLES: bb, kk,
 */
/* Return values: -1 = inflate_stored, -2 = inflate_codes */
/* One callsite in inflate_get_next_window */
static int inflate_block(STATE_PARAM smallint *e)
{
	unsigned t;			/* block type */
	unsigned b;	/* bit buffer */
	unsigned k;	/* number of bits in bit buffer */

	/* make local bit buffer */

	b = gunzip_bb;
	k = gunzip_bk;

	/* read in last block bit */
	b = fill_bitbuffer(PASS_STATE b, &k, 1);
	*e = b & 1;
	b >>= 1;
	k -= 1;

	/* read in block type */
	b = fill_bitbuffer(PASS_STATE b, &k, 2);
	t = (unsigned) b & 3;
	b >>= 2;
	k -= 2;

	/* restore the global bit buffer */
	gunzip_bb = b;
	gunzip_bk = k;

	/* inflate that block type */
	switch (t) {
	case 0:			/* Inflate stored */
	{
		unsigned n;	/* number of bytes in block */
		unsigned b_stored;	/* bit buffer */
		unsigned k_stored;	/* number of bits in bit buffer */

		/* make local copies of globals */
		b_stored = gunzip_bb;	/* initialize bit buffer */
		k_stored = gunzip_bk;

		/* go to byte boundary */
		n = k_stored & 7;
		b_stored >>= n;
		k_stored -= n;

		/* get the length and its complement */
		b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
		n = ((unsigned) b_stored & 0xffff);
		b_stored >>= 16;
		k_stored -= 16;

		b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
		if (n != (unsigned) ((~b_stored) & 0xffff)) {
			return 1;	/* error in compressed data */
		}
		b_stored >>= 16;
		k_stored -= 16;

		inflate_stored_setup(PASS_STATE n, b_stored, k_stored); // Setup inflate_stored

		return -1;
	}
	case 1:
	/* 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_t *tl;		/* literal/length code table */
		huft_t *td;		/* distance code table */
		unsigned bl;			/* lookup bits for tl */
		unsigned 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;