decompress_unzip.c

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

/* vi: set sw=4 ts=4: */
/*
 * gunzip implementation for busybox
 *
 * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
 *
 * Originally adjusted for busybox by Sven Rudolph <[e-mail]>
 * based on gzip sources
 *
 * Adjusted further by Erik Andersen <[e-mail]> to support
 * files as well as stdin/stdout, and to generally behave itself wrt
 * command line handling.
 *
 * General cleanup to better adhere to the style guide and make use of standard
 * busybox functions by Glenn McGrath <[e-mail]>
 *
 * read_gz interface + associated hacking by Laurence Anderson
 *
 * Fixed huft_build() so decoding end-of-block code does not grab more bits
 * than necessary (this is required by unzip applet), added inflate_cleanup()
 * to free leaked bytebuffer memory (used in unzip.c), and some minor style
 * guide cleanups by Ed Clark
 *
 * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
 * Copyright (C) 1992-1993 Jean-loup Gailly
 * The unzip code was written and put in the public domain by Mark Adler.
 * Portions of the lzw code are derived from the public domain 'compress'
 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
 * Ken Turkowski, Dave Mack and Peter Jannesen.
 *
 * See the file algorithm.doc for the compression algorithms and file formats.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
 */

#include "libbb.h"
#include "unarchive.h"

typedef struct huft_s {
	unsigned char e;	/* number of extra bits or operation */
	unsigned char b;	/* number of bits in this code or subcode */
	union {
		unsigned short n;	/* literal, length base, or distance base */
		struct huft_s *t;	/* pointer to next level of table */
	} v;
} huft_t;

enum {
	/* gunzip_window size--must be a power of two, and
	 *  at least 32K for zip's deflate method */
	GUNZIP_WSIZE = 0x8000,
	/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
	BMAX = 16,	/* maximum bit length of any code (16 for explode) */
	N_MAX = 288,	/* maximum number of codes in any set */
};


/* This is somewhat complex-looking arrangement, but it allows
 * to place decompressor state either in bss or in
 * malloc'ed space simply by changing #defines below.
 * Sizes on i386:
 * text    data     bss     dec     hex
 * 5256       0     108    5364    14f4 - bss
 * 4915       0       0    4915    1333 - malloc
 */
#define STATE_IN_BSS 0
#define STATE_IN_MALLOC 1


typedef struct state_t {
	off_t gunzip_bytes_out; /* number of output bytes */
	uint32_t gunzip_crc;

	int gunzip_src_fd;
	unsigned gunzip_outbuf_count; /* bytes in output buffer */

	unsigned char *gunzip_window;

	uint32_t *gunzip_crc_table;

	/* bitbuffer */
	unsigned gunzip_bb; /* bit buffer */
	unsigned char gunzip_bk; /* bits in bit buffer */

	/* These control the size of the STATE()bytebuffer */
	unsigned bytebuffer_max;
	unsigned char *bytebuffer;
	unsigned bytebuffer_offset;
	unsigned bytebuffer_size;

	/* private data of inflate_codes() */
	unsigned inflate_codes_ml; /* masks for bl and bd bits */
	unsigned inflate_codes_md; /* masks for bl and bd bits */
	unsigned inflate_codes_bb; /* bit buffer */
	unsigned inflate_codes_k; /* number of bits in bit buffer */
	unsigned inflate_codes_w; /* current gunzip_window position */
	huft_t *inflate_codes_tl;
	huft_t *inflate_codes_td;
	unsigned inflate_codes_bl;
	unsigned inflate_codes_bd;
	unsigned inflate_codes_nn; /* length and index for copy */
	unsigned inflate_codes_dd;
	smallint resume_copy;

	/* private data of inflate_get_next_window() */
	smallint method; /* Method == -1 for stored, -2 for codes */
	smallint need_another_block;
	smallint end_reached;

	/* private data of inflate_stored() */
	unsigned inflate_stored_n;
	unsigned inflate_stored_b;
	unsigned inflate_stored_k;
	unsigned inflate_stored_w;
} state_t;
#define gunzip_bytes_out    (S()gunzip_bytes_out   )
#define gunzip_crc          (S()gunzip_crc         )
#define gunzip_src_fd       (S()gunzip_src_fd      )
#define gunzip_outbuf_count (S()gunzip_outbuf_count)
#define gunzip_window       (S()gunzip_window      )
#define gunzip_crc_table    (S()gunzip_crc_table   )
#define gunzip_bb           (S()gunzip_bb          )
#define gunzip_bk           (S()gunzip_bk          )
#define bytebuffer_max      (S()bytebuffer_max     )
#define bytebuffer          (S()bytebuffer         )
#define bytebuffer_offset   (S()bytebuffer_offset  )
#define bytebuffer_size     (S()bytebuffer_size    )
#define inflate_codes_ml    (S()inflate_codes_ml   )
#define inflate_codes_md    (S()inflate_codes_md   )
#define inflate_codes_bb    (S()inflate_codes_bb   )
#define inflate_codes_k     (S()inflate_codes_k    )
#define inflate_codes_w     (S()inflate_codes_w    )
#define inflate_codes_tl    (S()inflate_codes_tl   )
#define inflate_codes_td    (S()inflate_codes_td   )
#define inflate_codes_bl    (S()inflate_codes_bl   )
#define inflate_codes_bd    (S()inflate_codes_bd   )
#define inflate_codes_nn    (S()inflate_codes_nn   )
#define inflate_codes_dd    (S()inflate_codes_dd   )
#define resume_copy         (S()resume_copy        )
#define method              (S()method             )
#define need_another_block  (S()need_another_block )
#define end_reached         (S()end_reached        )
#define inflate_stored_n    (S()inflate_stored_n   )
#define inflate_stored_b    (S()inflate_stored_b   )
#define inflate_stored_k    (S()inflate_stored_k   )
#define inflate_stored_w    (S()inflate_stored_w   )
#define INIT_STATE ({ bytebuffer_size = 0; method = -1; need_another_block = 1; })


/* This is generic part */
#if STATE_IN_BSS /* Use global data segment */
#define DECLARE_STATE /*nothing*/
#define ALLOC_STATE (init_state())
#define DEALLOC_STATE ((void)0)
#define S() state.
#define PASS_STATE /*nothing*/
#define PASS_STATE_ONLY /*nothing*/
#define STATE_PARAM /*nothing*/
#define STATE_PARAM_ONLY void
static state_t state;
static void init_state(void)
{
	INIT_STATE;
}
#endif

#if STATE_IN_MALLOC /* Use malloc space */
#define DECLARE_STATE state_t *state
#define ALLOC_STATE (state = alloc_state())
#define DEALLOC_STATE free(state)
#define S() state->
#define PASS_STATE state,
#define PASS_STATE_ONLY state
#define STATE_PARAM state_t *state,
#define STATE_PARAM_ONLY state_t *state
static state_t* alloc_state(void)
{
	state_t* state = xzalloc(sizeof(*state));
	INIT_STATE;
	return state;
}
#endif


static const unsigned short mask_bits[] ALIGN2 = {
	0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
	0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};

/* Copy lengths for literal codes 257..285 */
static const unsigned short cplens[] ALIGN2 = {
	3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
	67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
};

/* note: see note #13 above about the 258 in this list. */
/* Extra bits for literal codes 257..285 */
static const unsigned char cplext[] ALIGN1 = {
	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,
	5, 5, 5, 0, 99, 99
}; /* 99 == invalid */

/* Copy offsets for distance codes 0..29 */
static const unsigned short cpdist[] ALIGN2 = {
	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
	769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
};

/* Extra bits for distance codes */
static const unsigned char cpdext[] ALIGN1 = {
	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
	11, 11, 12, 12, 13, 13
};

/* Tables for deflate from PKZIP's appnote.txt. */
/* Order of the bit length code lengths */
static const unsigned char border[] ALIGN1 = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};

static unsigned fill_bitbuffer(STATE_PARAM unsigned bitbuffer, unsigned *current, const unsigned required)
{
	while (*current < required) {
		if (bytebuffer_offset >= bytebuffer_size) {
			/* Leave the first 4 bytes empty so we can always unwind the bitbuffer
			 * to the front of the bytebuffer, leave 4 bytes free at end of tail
			 * so we can easily top up buffer in check_trailer_gzip() */
			bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8);
			if (1 > bytebuffer_size)
//shouldn't we propagate error?
				bb_error_msg_and_die("unexpected end of file");
			bytebuffer_size += 4;
			bytebuffer_offset = 4;
		}
		bitbuffer |= ((unsigned) bytebuffer[bytebuffer_offset]) << *current;
		bytebuffer_offset++;
		*current += 8;
	}
	return bitbuffer;
}

/*
 * 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 first entry of
 * each table.
 * t: table to free
 */
static void huft_free(huft_t * p)
{
	huft_t *q;

	/* Go through linked list, freeing from the malloced (t[-1]) address. */
	while (p) {
		q = (--p)->v.t;
		free(p);
		p = q;
	}
}

/* Given a list of code lengths and a maximum table size, make a set of
 * tables to decode that set of codes.  Return zero on success, one if
 * the given code set is incomplete (the tables are still built in this
 * case), two if the input is invalid (all zero length codes or an
 * oversubscribed set of lengths), and three if not enough memory.
 *
 * b:	code lengths in bits (all assumed <= BMAX)
 * n:	number of codes (assumed <= N_MAX)
 * s:	number of simple-valued codes (0..s-1)
 * d:	list of base values for non-simple codes
 * e:	list of extra bits for non-simple codes
 * t:	result: starting table
 * m:	maximum lookup bits, returns actual
 */
static int huft_build(unsigned *b, const unsigned n,
			   const unsigned s, const unsigned short *d,
			   const unsigned char *e, huft_t ** t, unsigned *m)
{
	unsigned a;				/* counter for codes of length k */
	unsigned c[BMAX + 1];	/* bit length count table */
	unsigned eob_len;		/* length of end-of-block code (value 256) */
	unsigned f;				/* i repeats in table every f entries */
	int g;					/* maximum code length */
	int htl;				/* table level */
	unsigned i;				/* counter, current code */
	unsigned j;				/* counter */
	int k;					/* number of bits in current code */
	unsigned *p;			/* pointer into c[], b[], or v[] */
	huft_t *q;				/* points to current table */
	huft_t r;				/* table entry for structure assignment */
	huft_t *u[BMAX];		/* table stack */
	unsigned v[N_MAX];		/* values in order of bit length */
	int ws[BMAX+1];			/* bits decoded stack */
	int w;					/* bits decoded */
	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 */

	/* Length of EOB code, if any */
	eob_len = n > 256 ? b[256] : BMAX;

	/* Generate counts for each bit length */
	memset(c, 0, sizeof(c));
	p = b;
	i = n;
	do {
		c[*p]++; /* assume all entries <= BMAX */
		p++; /* Can't combine with above line (Solaris bug) */
	} while (--i);
	if (c[0] == n) { /* null input--all zero length codes */
		*t = NULL;
		*m = 0;
		return 2;
	}

	/* Find minimum and maximum length, bound *m by those */
	for (j = 1; (c[j] == 0) && (j <= BMAX); j++);
	k = j; /* minimum code length */
	for (i = BMAX; (c[i] == 0) && i; i--);
	g = i; /* maximum code length */
	*m = (*m < j) ? j : ((*m > i) ? i : *m);

	/* Adjust last length count to fill out codes, if needed */
	for (y = 1 << j; j < i; j++, y <<= 1) {
		y -= c[j];
		if (y < 0) {
			return 2; /* bad input: more codes than bits */
		}
	}
	y -= c[i];
	if (y < 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 */
		j += *p++;
		*xp++ = j;
	}

	/* Make a table of values in order of bit lengths */
	p = b;
	i = 0;
	do {
		j = *p++;
		if (j != 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 */
	htl = -1;				/* no tables yet--level -1 */
	w = ws[0] = 0;			/* bits decoded */
	u[0] = NULL;	/* just to keep compilers happy */
	q = 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 */