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
 *
 * 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 <setjmp.h>
#include "libbb.h"
#include "unarchive.h"

typedef struct huft_t {
	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_t *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 */

	/* input (compressed) data */
	unsigned char *bytebuffer;      /* buffer itself */
	off_t to_read;			/* compressed bytes to read (unzip only, -1 for gunzip) */
//	unsigned bytebuffer_max;        /* buffer size */
	unsigned bytebuffer_offset;     /* buffer position */
	unsigned bytebuffer_size;       /* how much data is there (size <= max) */

	/* 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;

	const char *error_msg;
	jmp_buf error_jmp;
} 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 to_read             (S()to_read            )
// #define bytebuffer_max   (S()bytebuffer_max     )
// Both gunzip and unzip can use constant buffer size now (16k):
#define bytebuffer_max      0x4000
#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 error_msg           (S()error_msg          )
#define error_jmp           (S()error_jmp          )

/* This is a generic part */
#if STATE_IN_BSS /* Use global data segment */
#define DECLARE_STATE /*nothing*/
#define ALLOC_STATE /*nothing*/
#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;
#endif

#if STATE_IN_MALLOC /* Use malloc space */
#define DECLARE_STATE state_t *state
#define ALLOC_STATE (state = xzalloc(sizeof(*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
#endif


static const uint16_t 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 uint16_t 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 uint8_t 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 uint16_t 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 uint8_t 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 uint8_t border[] ALIGN1 = {
	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
};


/*
 * 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;
	}
}

static void huft_free_all(STATE_PARAM_ONLY)
{
	huft_free(inflate_codes_tl);
	huft_free(inflate_codes_td);
	inflate_codes_tl = NULL;
	inflate_codes_td = NULL;
}

static void abort_unzip(STATE_PARAM_ONLY) NORETURN;
static void abort_unzip(STATE_PARAM_ONLY)
{
	huft_free_all(PASS_STATE_ONLY);
	longjmp(error_jmp, 1);
}

static unsigned fill_bitbuffer(STATE_PARAM unsigned bitbuffer, unsigned *current, const unsigned required)
{
	while (*current < required) {
		if (bytebuffer_offset >= bytebuffer_size) {
			unsigned sz = bytebuffer_max - 4;
			if (to_read >= 0 && to_read < sz) /* unzip only */
				sz = to_read;
			/* Leave the first 4 bytes empty so we can always unwind the bitbuffer
			 * to the front of the bytebuffer */
			bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], sz);
			if ((int)bytebuffer_size < 1) {
				error_msg = "unexpected end of file";
				abort_unzip(PASS_STATE_ONLY);
			}
			if (to_read >= 0) /* unzip only */
				to_read -= bytebuffer_size;
			bytebuffer_size += 4;
			bytebuffer_offset = 4;
		}
		bitbuffer |= ((unsigned) bytebuffer[bytebuffer_offset]) << *current;
		bytebuffer_offset++;
		*current += 8;
	}
	return bitbuffer;
}


/* 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) - in this case stores NULL in *t.
 *
 * 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(const 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;

	*t = NULL;

	/* Generate counts for each bit length */
	memset(c, 0, sizeof(c));
	p = (unsigned *) b; /* cast allows us to reuse p for pointing to 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 */
		*m = 0;
		return 2;
	}

	/* Find minimum and maximum length, bound *m by those */
	for (j = 1; (c[j] == 0) && (j <= BMAX); j++)
		continue;
	k = j; /* minimum code length */
	for (i = BMAX; (c[i] == 0) && i; i--)
		continue;
	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 = (unsigned *) 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 */
			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() */