decompress_unzip.c

arm9200t上的一个叫busybox的东西

			d = w - t->v.n - ((unsigned) b & mask_bits[e]);
			b >>= e;
			k -= e;

			/* do the copy */
do_copy:		do {
				n -= (e =
					  (e =
					   gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e);
			   /* copy to new buffer to prevent possible overwrite */
				if (w - d >= e) {	/* (this test assumes unsigned comparison) */
					memcpy(gunzip_window + w, gunzip_window + d, e);
					w += e;
					d += e;
				} else {
				   /* do it slow to avoid memcpy() overlap */
				   /* !NOMEMCPY */
					do {
						gunzip_window[w++] = gunzip_window[d++];
					} while (--e);
				}
				if (w == gunzip_wsize) {
					gunzip_outbuf_count = (w);
					if (n) resumeCopy = 1;
					else resumeCopy = 0;
					//flush_gunzip_window();
					w = 0;
					return 1;
				}
			} while (n);
			resumeCopy = 0;
		}
	}

	/* restore the globals from the locals */
	gunzip_outbuf_count = w;			/* restore global gunzip_window pointer */
	gunzip_bb = b;				/* 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;
}

static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
{
	static int n, b_stored, k_stored, w;
	if (setup) {
		n = my_n;
		b_stored = my_b_stored;
		k_stored = my_k_stored;
		w = gunzip_outbuf_count;		/* initialize gunzip_window position */
		return 0; // Don't do anything first time
	}

	/* read and output the compressed data */
	while (n--) {
		b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
		gunzip_window[w++] = (unsigned char) b_stored;
		if (w == (unsigned int) gunzip_wsize) {
			gunzip_outbuf_count = (w);
			//flush_gunzip_window();
			w = 0;
			b_stored >>= 8;
			k_stored -= 8;
			return 1; // We have a block
		}
		b_stored >>= 8;
		k_stored -= 8;
	}

	/* restore the globals from the locals */
	gunzip_outbuf_count = w;		/* restore global gunzip_window pointer */
	gunzip_bb = b_stored;	/* restore global bit buffer */
	gunzip_bk = k_stored;
	return 0; // Finished
}

/*
 * decompress an inflated block
 * e: last block flag
 *
 * GLOBAL VARIABLES: bb, kk,
 */
 // Return values: -1 = inflate_stored, -2 = inflate_codes
static int inflate_block(int *e)
{
	unsigned t;			/* block type */
	register unsigned int b;	/* bit buffer */
	unsigned int 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(b, &k, 1);
	*e = (int) b & 1;
	b >>= 1;
	k -= 1;

	/* read in block type */
	b = fill_bitbuffer(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 int n;	/* number of bytes in block */
		unsigned int b_stored;	/* bit buffer */
		unsigned int 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(b_stored, &k_stored, 16);
		n = ((unsigned) b_stored & 0xffff);
		b_stored >>= 16;
		k_stored -= 16;

		b_stored = fill_bitbuffer(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(n, b_stored, k_stored, 1); // 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 int bl;			/* lookup bits for tl */
		unsigned int bd;			/* lookup bits for td */
		unsigned int 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;
		}
		for (; i < 280; i++) {
			l[i] = 7;
		}
		for (; i < 288; i++) {	/* make a complete, but wrong code set */
			l[i] = 8;
		}
		bl = 7;
		if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
			return i;
		}

		/* set up distance table */
		for (i = 0; i < 30; i++) {	/* make an incomplete code set */
			l[i] = 5;
		}
		bd = 5;
		if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
			huft_free(tl);
			return i;
		}

		/* decompress until an end-of-block code */
		inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes

		/* huft_free code moved into inflate_codes */

		return -2;
	}
	case 2:			/* Inflate dynamic */
	{
		const int dbits = 6;	/* bits in base distance lookup table */
		const int lbits = 9;	/* bits in base literal/length lookup table */

		huft_t *tl;		/* literal/length code table */
		huft_t *td;		/* distance code table */
		unsigned int i;			/* temporary variables */
		unsigned int j;
		unsigned int l;		/* last length */
		unsigned int m;		/* mask for bit lengths table */
		unsigned int n;		/* number of lengths to get */
		unsigned int bl;			/* lookup bits for tl */
		unsigned int bd;			/* lookup bits for td */
		unsigned int nb;	/* number of bit length codes */
		unsigned int nl;	/* number of literal/length codes */
		unsigned int nd;	/* number of distance codes */

		unsigned int ll[286 + 30];	/* literal/length and distance code lengths */
		unsigned int b_dynamic;	/* bit buffer */
		unsigned int k_dynamic;	/* number of bits in bit buffer */

		/* make local bit buffer */
		b_dynamic = gunzip_bb;
		k_dynamic = gunzip_bk;

		/* read in table lengths */
		b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
		nl = 257 + ((unsigned int) b_dynamic & 0x1f);	/* number of literal/length codes */

		b_dynamic >>= 5;
		k_dynamic -= 5;
		b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
		nd = 1 + ((unsigned int) b_dynamic & 0x1f);	/* number of distance codes */

		b_dynamic >>= 5;
		k_dynamic -= 5;
		b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
		nb = 4 + ((unsigned int) b_dynamic & 0xf);	/* number of bit length codes */

		b_dynamic >>= 4;
		k_dynamic -= 4;
		if (nl > 286 || nd > 30) {
			return 1;	/* bad lengths */
		}

		/* read in bit-length-code lengths */
		for (j = 0; j < nb; j++) {
			b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
			ll[border[j]] = (unsigned int) b_dynamic & 7;
			b_dynamic >>= 3;
			k_dynamic -= 3;
		}
		for (; j < 19; j++) {
			ll[border[j]] = 0;
		}

		/* build decoding table for trees--single level, 7 bit lookup */
		bl = 7;
		i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
		if (i != 0) {
			if (i == 1) {
				huft_free(tl);
			}
			return i;	/* incomplete code set */
		}

		/* read in literal and distance code lengths */
		n = nl + nd;
		m = mask_bits[bl];
		i = l = 0;
		while ((unsigned int) i < n) {
			b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned int)bl);
			j = (td = tl + ((unsigned int) b_dynamic & m))->b;
			b_dynamic >>= j;
			k_dynamic -= j;
			j = td->v.n;
			if (j < 16) {	/* length of code in bits (0..15) */
				ll[i++] = l = j;	/* save last length in l */
			} else if (j == 16) {	/* repeat last length 3 to 6 times */
				b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
				j = 3 + ((unsigned int) b_dynamic & 3);
				b_dynamic >>= 2;
				k_dynamic -= 2;
				if ((unsigned int) i + j > n) {
					return 1;
				}
				while (j--) {
					ll[i++] = l;
				}
			} else if (j == 17) {	/* 3 to 10 zero length codes */
				b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
				j = 3 + ((unsigned int) b_dynamic & 7);
				b_dynamic >>= 3;
				k_dynamic -= 3;
				if ((unsigned int) i + j > n) {
					return 1;
				}
				while (j--) {
					ll[i++] = 0;
				}
				l = 0;
			} else {	/* j == 18: 11 to 138 zero length codes */
				b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
				j = 11 + ((unsigned int) b_dynamic & 0x7f);
				b_dynamic >>= 7;
				k_dynamic -= 7;
				if ((unsigned int) i + j > n) {
					return 1;
				}
				while (j--) {
					ll[i++] = 0;
				}
				l = 0;
			}
		}

		/* free decoding table for trees */
		huft_free(tl);

		/* restore the global bit buffer */
		gunzip_bb = b_dynamic;
		gunzip_bk = k_dynamic;

		/* build the decoding tables for literal/length and distance codes */
		bl = lbits;

		if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
			if (i == 1) {
				bb_error_msg_and_die("Incomplete literal tree");
				huft_free(tl);
			}
			return i;	/* incomplete code set */
		}

		bd = dbits;
		if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
			if (i == 1) {
				bb_error_msg_and_die("incomplete distance tree");
				huft_free(td);
			}
			huft_free(tl);
			return i;	/* incomplete code set */
		}

		/* decompress until an end-of-block code */
		inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes

		/* huft_free code moved into inflate_codes */

		return -2;
	}
	default:
		/* bad block type */
		bb_error_msg_and_die("bad block type %d\n", t);
	}
}

static void calculate_gunzip_crc(void)
{
	int n;
	for (n = 0; n < gunzip_outbuf_count; n++) {
		gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
	}
	gunzip_bytes_out += gunzip_outbuf_count;
}

static int inflate_get_next_window(void)
{
	static int method = -1; // Method == -1 for stored, -2 for codes
	static int e = 0;
	static int needAnotherBlock = 1;

	gunzip_outbuf_count = 0;

	while(1) {
		int ret;

		if (needAnotherBlock) {
			if(e) {
				calculate_gunzip_crc();
				e = 0;
				needAnotherBlock = 1;
				return 0;
			} // Last block
			method = inflate_block(&e);
			needAnotherBlock = 0;
		}

		switch (method) {
			case -1:	ret = inflate_stored(0,0,0,0);
					break;
			case -2:	ret = inflate_codes(0,0,0,0,0);
					break;
			default:	bb_error_msg_and_die("inflate error %d", method);
		}

		if (ret == 1) {
			calculate_gunzip_crc();
			return 1; // More data left
		} else needAnotherBlock = 1; // End of that block
	}
	/* Doesnt get here */
}

/* Initialise bytebuffer, be careful not to overfill the buffer */
extern void inflate_init(unsigned int bufsize)
{
	/* Set the bytebuffer size, default is same as gunzip_wsize */
	bytebuffer_max = bufsize + 8;
	bytebuffer_offset = 4;
	bytebuffer_size = 0;
}

extern int inflate_unzip(int in, int out)
{
	ssize_t nwrote;
	typedef void (*sig_type) (int);

	/* Allocate all global buffers (for DYN_ALLOC option) */
	gunzip_window = xmalloc(gunzip_wsize);
	gunzip_outbuf_count = 0;
	gunzip_bytes_out = 0;
	gunzip_src_fd = in;

	/* initialize gunzip_window, bit buffer */
	gunzip_bk = 0;
	gunzip_bb = 0;

	/* Create the crc table */
	make_gunzip_crc_table();

	/* Allocate space for buffer */
	bytebuffer = xmalloc(bytebuffer_max);

	while(1) {
		int ret = inflate_get_next_window();
		nwrote = bb_full_write(out, gunzip_window, gunzip_outbuf_count);
		if (nwrote == -1) {
			bb_perror_msg("write");
			return -1;
		}
		if (ret == 0) break;
	}

	/* Cleanup */
	free(gunzip_window);
	free(gunzip_crc_table);

	/* Store unused bytes in a global buffer so calling applets can access it */
	if (gunzip_bk >= 8) {
		/* Undo too much lookahead. The next read will be byte aligned
		 * so we can discard unused bits in the last meaningful byte. */
		bytebuffer_offset--;
		bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
		gunzip_bb >>= 8;
		gunzip_bk -= 8;
	}
	return 0;
}

extern int inflate_gunzip(int in, int out)
{
	unsigned int stored_crc = 0;
	unsigned char count;

	inflate_unzip(in, out);

	/* top up the input buffer with the rest of the trailer */
	count = bytebuffer_size - bytebuffer_offset;
	if (count < 8) {
		bb_xread_all(in, &bytebuffer[bytebuffer_size], 8 - count);
		bytebuffer_size += 8 - count;
	}
	for (count = 0; count != 4; count++) {
		stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
		bytebuffer_offset++;
	}

	/* Validate decompression - crc */
	if (stored_crc != (gunzip_crc ^ 0xffffffffL)) {
		bb_error_msg("crc error");
	}

	/* Validate decompression - size */
	if (gunzip_bytes_out !=
		(bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
		(bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
		bb_error_msg("Incorrect length");
	}

	return 0;
}