archival/libunarchive/decompress_uncompress.c

/* vi: set sw=4 ts=4: */
/* uncompress for busybox -- (c) 2002 Robert Griebl
 *
 * based on the original compress42.c source
 * (see disclaimer below)
 */

/* (N)compress42.c - File compression ala IEEE Computer, Mar 1992.
 *
 * Authors:
 *   Spencer W. Thomas   (decvax!harpo!utah-cs!utah-gr!thomas)
 *   Jim McKie           (decvax!mcvax!jim)
 *   Steve Davies        (decvax!vax135!petsd!peora!srd)
 *   Ken Turkowski       (decvax!decwrl!turtlevax!ken)
 *   James A. Woods      (decvax!ihnp4!ames!jaw)
 *   Joe Orost           (decvax!vax135!petsd!joe)
 *   Dave Mack           (csu@alembic.acs.com)
 *   Peter Jannesen, Network Communication Systems
 *                       (peter@ncs.nl)
 *
 * marc@suse.de : a small security fix for a buffer overflow
 *
 * [... History snipped ...]
 *
 */

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


/* Default input buffer size */
#define	IBUFSIZ	2048

/* Default output buffer size */
#define	OBUFSIZ	2048

/* Defines for third byte of header */
#define BIT_MASK        0x1f    /* Mask for 'number of compresssion bits'       */
                                /* Masks 0x20 and 0x40 are free.                */
                                /* I think 0x20 should mean that there is       */
                                /* a fourth header byte (for expansion).        */
#define BLOCK_MODE      0x80    /* Block compression if table is full and       */
                                /* compression rate is dropping flush tables    */
                                /* the next two codes should not be changed lightly, as they must not   */
                                /* lie within the contiguous general code space.                        */
#define FIRST   257     /* first free entry */
#define CLEAR   256     /* table clear output code */

#define INIT_BITS 9     /* initial number of bits/code */


/* machine variants which require cc -Dmachine:  pdp11, z8000, DOS */
#define HBITS      17   /* 50% occupancy */
#define HSIZE      (1<<HBITS)
#define HMASK      (HSIZE-1)    /* unused */
#define HPRIME     9941         /* unused */
#define BITS       16
#define BITS_STR   "16"
#undef  MAXSEG_64K              /* unused */
#define MAXCODE(n) (1L << (n))

#define htabof(i)               htab[i]
#define codetabof(i)            codetab[i]
#define tab_prefixof(i)         codetabof(i)
#define tab_suffixof(i)         ((unsigned char *)(htab))[i]
#define de_stack                ((unsigned char *)&(htab[HSIZE-1]))
#define clear_tab_prefixof()    memset(codetab, 0, 256)

/*
 * Decompress stdin to stdout.  This routine adapts to the codes in the
 * file building the "string" table on-the-fly; requiring no table to
 * be stored in the compressed file.
 */

IF_DESKTOP(long long) int FAST_FUNC
unpack_Z_stream(int fd_in, int fd_out)
{
	IF_DESKTOP(long long total_written = 0;)
	IF_DESKTOP(long long) int retval = -1;
	unsigned char *stackp;
	long code;
	int finchar;
	long oldcode;
	long incode;
	int inbits;
	int posbits;
	int outpos;
	int insize;
	int bitmask;
	long free_ent;
	long maxcode;
	long maxmaxcode;
	int n_bits;
	int rsize = 0;
	unsigned char *inbuf; /* were eating insane amounts of stack - */
	unsigned char *outbuf; /* bad for some embedded targets */
	unsigned char *htab;
	unsigned short *codetab;

	/* Hmm, these were statics - why?! */
	/* user settable max # bits/code */
	int maxbits; /* = BITS; */
	/* block compress mode -C compatible with 2.0 */
	int block_mode; /* = BLOCK_MODE; */

	inbuf = xzalloc(IBUFSIZ + 64);
	outbuf = xzalloc(OBUFSIZ + 2048);
	htab = xzalloc(HSIZE);  /* wsn't zeroed out before, maybe can xmalloc? */
	codetab = xzalloc(HSIZE * sizeof(codetab[0]));

	insize = 0;

	/* xread isn't good here, we have to return - caller may want
	 * to do some cleanup (e.g. delete incomplete unpacked file etc) */
	if (full_read(fd_in, inbuf, 1) != 1) {
		bb_error_msg("short read");
		goto err;
	}

	maxbits = inbuf[0] & BIT_MASK;
	block_mode = inbuf[0] & BLOCK_MODE;
	maxmaxcode = MAXCODE(maxbits);

	if (maxbits > BITS) {
		bb_error_msg("compressed with %d bits, can only handle "
				BITS_STR" bits", maxbits);
		goto err;
	}

	n_bits = INIT_BITS;
	maxcode = MAXCODE(INIT_BITS) - 1;
	bitmask = (1 << INIT_BITS) - 1;
	oldcode = -1;
	finchar = 0;
	outpos = 0;
	posbits = 0 << 3;

	free_ent = ((block_mode) ? FIRST : 256);

	/* As above, initialize the first 256 entries in the table. */
	/*clear_tab_prefixof(); - done by xzalloc */

	for (code = 255; code >= 0; --code) {
		tab_suffixof(code) = (unsigned char) code;
	}

	do {
 resetbuf:
		{
			int i;
			int e;
			int o;

			o = posbits >> 3;
			e = insize - o;

			for (i = 0; i < e; ++i)
				inbuf[i] = inbuf[i + o];

			insize = e;
			posbits = 0;
		}

		if (insize < (int) (IBUFSIZ + 64) - IBUFSIZ) {
			rsize = safe_read(fd_in, inbuf + insize, IBUFSIZ);
//error check??
			insize += rsize;
		}

		inbits = ((rsize > 0) ? (insize - insize % n_bits) << 3 :
				  (insize << 3) - (n_bits - 1));

		while (inbits > posbits) {
			if (free_ent > maxcode) {
				posbits =
					((posbits - 1) +
					 ((n_bits << 3) -
					  (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
				++n_bits;
				if (n_bits == maxbits) {
					maxcode = maxmaxcode;
				} else {
					maxcode = MAXCODE(n_bits) - 1;
				}
				bitmask = (1 << n_bits) - 1;
				goto resetbuf;
			}
			{
				unsigned char *p = &inbuf[posbits >> 3];

				code = ((((long) (p[0])) | ((long) (p[1]) << 8) |
				         ((long) (p[2]) << 16)) >> (posbits & 0x7)) & bitmask;
			}
			posbits += n_bits;


			if (oldcode == -1) {
				oldcode = code;
				finchar = (int) oldcode;
				outbuf[outpos++] = (unsigned char) finchar;
				continue;
			}

			if (code == CLEAR && block_mode) {
				clear_tab_prefixof();
				free_ent = FIRST - 1;
				posbits =
					((posbits - 1) +
					 ((n_bits << 3) -
					  (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
				n_bits = INIT_BITS;
				maxcode = MAXCODE(INIT_BITS) - 1;
				bitmask = (1 << INIT_BITS) - 1;
				goto resetbuf;
			}

			incode = code;
			stackp = de_stack;

			/* Special case for KwKwK string. */
			if (code >= free_ent) {
				if (code > free_ent) {
					unsigned char *p;

					posbits -= n_bits;
					p = &inbuf[posbits >> 3];

					bb_error_msg
						("insize:%d posbits:%d inbuf:%02X %02X %02X %02X %02X (%d)",
						 insize, posbits, p[-1], p[0], p[1], p[2], p[3],
						 (posbits & 07));
					bb_error_msg("corrupted data");
					goto err;
				}

				*--stackp = (unsigned char) finchar;
				code = oldcode;
			}

			/* Generate output characters in reverse order */
			while ((long) code >= (long) 256) {
				*--stackp = tab_suffixof(code);
				code = tab_prefixof(code);
			}

			finchar = tab_suffixof(code);
			*--stackp = (unsigned char) finchar;

			/* And put them out in forward order */
			{
				int i;

				i = de_stack - stackp;
				if (outpos + i >= OBUFSIZ) {
					do {
						if (i > OBUFSIZ - outpos) {
							i = OBUFSIZ - outpos;
						}

						if (i > 0) {
							memcpy(outbuf + outpos, stackp, i);
							outpos += i;
						}

						if (outpos >= OBUFSIZ) {
							full_write(fd_out, outbuf, outpos);
//error check??
							IF_DESKTOP(total_written += outpos;)
							outpos = 0;
						}
						stackp += i;
						i = de_stack - stackp;
					} while (i > 0);
				} else {
					memcpy(outbuf + outpos, stackp, i);
					outpos += i;
				}
			}

			/* Generate the new entry. */
			code = free_ent;
			if (code < maxmaxcode) {
				tab_prefixof(code) = (unsigned short) oldcode;
				tab_suffixof(code) = (unsigned char) finchar;
				free_ent = code + 1;
			}

			/* Remember previous code.  */
			oldcode = incode;
		}

	} while (rsize > 0);

	if (outpos > 0) {
		full_write(fd_out, outbuf, outpos);
//error check??
		IF_DESKTOP(total_written += outpos;)
	}

	retval = IF_DESKTOP(total_written) + 0;
 err:
	free(inbuf);
	free(outbuf);
	free(htab);
	free(codetab);
	return retval;
}
1	niro	532	/* vi: set sw=4 ts=4: */
2			/* uncompress for busybox -- (c) 2002 Robert Griebl
3			*
4			* based on the original compress42.c source
5			* (see disclaimer below)
6			*/
7
8			/* (N)compress42.c - File compression ala IEEE Computer, Mar 1992.
9			*
10			* Authors:
11			* Spencer W. Thomas (decvax!harpo!utah-cs!utah-gr!thomas)
12			* Jim McKie (decvax!mcvax!jim)
13			* Steve Davies (decvax!vax135!petsd!peora!srd)
14			* Ken Turkowski (decvax!decwrl!turtlevax!ken)
15			* James A. Woods (decvax!ihnp4!ames!jaw)
16			* Joe Orost (decvax!vax135!petsd!joe)
17			* Dave Mack (csu@alembic.acs.com)
18			* Peter Jannesen, Network Communication Systems
19			* (peter@ncs.nl)
20			*
21			* marc@suse.de : a small security fix for a buffer overflow
22			*
23			* [... History snipped ...]
24			*
25			*/
26
27	niro	816	#include "libbb.h"
28			#include "unarchive.h"
29
30
31	niro	532	/* Default input buffer size */
32			#define IBUFSIZ 2048
33
34			/* Default output buffer size */
35			#define OBUFSIZ 2048
36
37			/* Defines for third byte of header */
38	niro	816	#define BIT_MASK 0x1f /* Mask for 'number of compresssion bits' */
39			/* Masks 0x20 and 0x40 are free. */
40			/* I think 0x20 should mean that there is */
41			/* a fourth header byte (for expansion). */
42			#define BLOCK_MODE 0x80 /* Block compression if table is full and */
43			/* compression rate is dropping flush tables */
44			/* the next two codes should not be changed lightly, as they must not */
45			/* lie within the contiguous general code space. */
46			#define FIRST 257 /* first free entry */
47			#define CLEAR 256 /* table clear output code */
48	niro	532
49	niro	816	#define INIT_BITS 9 /* initial number of bits/code */
50	niro	532
51
52			/* machine variants which require cc -Dmachine: pdp11, z8000, DOS */
53	niro	816	#define HBITS 17 /* 50% occupancy */
54			#define HSIZE (1<<HBITS)
55			#define HMASK (HSIZE-1) /* unused */
56			#define HPRIME 9941 /* unused */
57			#define BITS 16
58			#define BITS_STR "16"
59			#undef MAXSEG_64K /* unused */
60			#define MAXCODE(n) (1L << (n))
61	niro	532
62	niro	816	#define htabof(i) htab[i]
63			#define codetabof(i) codetab[i]
64			#define tab_prefixof(i) codetabof(i)
65			#define tab_suffixof(i) ((unsigned char *)(htab))[i]
66			#define de_stack ((unsigned char *)&(htab[HSIZE-1]))
67			#define clear_tab_prefixof() memset(codetab, 0, 256)
68	niro	532
69			/*
70			* Decompress stdin to stdout. This routine adapts to the codes in the
71			* file building the "string" table on-the-fly; requiring no table to
72	niro	816	* be stored in the compressed file.
73	niro	532	*/
74
75	niro	984	IF_DESKTOP(long long) int FAST_FUNC
76	niro	816	unpack_Z_stream(int fd_in, int fd_out)
77	niro	532	{
78	niro	984	IF_DESKTOP(long long total_written = 0;)
79			IF_DESKTOP(long long) int retval = -1;
80	niro	532	unsigned char *stackp;
81	niro	816	long code;
82	niro	532	int finchar;
83	niro	816	long oldcode;
84			long incode;
85	niro	532	int inbits;
86			int posbits;
87			int outpos;
88			int insize;
89			int bitmask;
90	niro	816	long free_ent;
91			long maxcode;
92			long maxmaxcode;
93	niro	532	int n_bits;
94			int rsize = 0;
95	niro	816	unsigned char inbuf; / were eating insane amounts of stack - */
96			unsigned char outbuf; / bad for some embedded targets */
97			unsigned char *htab;
98			unsigned short *codetab;
99	niro	532
100			/* Hmm, these were statics - why?! */
101			/* user settable max # bits/code */
102			int maxbits; /* = BITS; */
103			/* block compress mode -C compatible with 2.0 */
104			int block_mode; /* = BLOCK_MODE; */
105
106	niro	816	inbuf = xzalloc(IBUFSIZ + 64);
107			outbuf = xzalloc(OBUFSIZ + 2048);
108			htab = xzalloc(HSIZE); /* wsn't zeroed out before, maybe can xmalloc? */
109			codetab = xzalloc(HSIZE * sizeof(codetab[0]));
110	niro	532
111			insize = 0;
112
113			/* xread isn't good here, we have to return - caller may want
114			* to do some cleanup (e.g. delete incomplete unpacked file etc) */
115			if (full_read(fd_in, inbuf, 1) != 1) {
116			bb_error_msg("short read");
117	niro	816	goto err;
118	niro	532	}
119
120			maxbits = inbuf[0] & BIT_MASK;
121			block_mode = inbuf[0] & BLOCK_MODE;
122			maxmaxcode = MAXCODE(maxbits);
123
124			if (maxbits > BITS) {
125			bb_error_msg("compressed with %d bits, can only handle "
126	niro	816	BITS_STR" bits", maxbits);
127			goto err;
128	niro	532	}
129
130			n_bits = INIT_BITS;
131			maxcode = MAXCODE(INIT_BITS) - 1;
132			bitmask = (1 << INIT_BITS) - 1;
133			oldcode = -1;
134			finchar = 0;
135			outpos = 0;
136			posbits = 0 << 3;
137
138			free_ent = ((block_mode) ? FIRST : 256);
139
140			/* As above, initialize the first 256 entries in the table. */
141	niro	816	/clear_tab_prefixof(); - done by xzalloc /
142	niro	532
143			for (code = 255; code >= 0; --code) {
144			tab_suffixof(code) = (unsigned char) code;
145			}
146
147			do {
148			resetbuf:
149			{
150			int i;
151			int e;
152			int o;
153
154			o = posbits >> 3;
155			e = insize - o;
156
157			for (i = 0; i < e; ++i)
158			inbuf[i] = inbuf[i + o];
159
160			insize = e;
161			posbits = 0;
162			}
163
164			if (insize < (int) (IBUFSIZ + 64) - IBUFSIZ) {
165			rsize = safe_read(fd_in, inbuf + insize, IBUFSIZ);
166			//error check??
167			insize += rsize;
168			}
169
170			inbits = ((rsize > 0) ? (insize - insize % n_bits) << 3 :
171			(insize << 3) - (n_bits - 1));
172
173			while (inbits > posbits) {
174			if (free_ent > maxcode) {
175			posbits =
176			((posbits - 1) +
177			((n_bits << 3) -
178			(posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
179			++n_bits;
180			if (n_bits == maxbits) {
181			maxcode = maxmaxcode;
182			} else {
183			maxcode = MAXCODE(n_bits) - 1;
184			}
185			bitmask = (1 << n_bits) - 1;
186			goto resetbuf;
187			}
188			{
189			unsigned char *p = &inbuf[posbits >> 3];
190
191			code = ((((long) (p[0])) \| ((long) (p[1]) << 8) \|
192			((long) (p[2]) << 16)) >> (posbits & 0x7)) & bitmask;
193			}
194			posbits += n_bits;
195
196
197			if (oldcode == -1) {
198			oldcode = code;
199			finchar = (int) oldcode;
200			outbuf[outpos++] = (unsigned char) finchar;
201			continue;
202			}
203
204			if (code == CLEAR && block_mode) {
205			clear_tab_prefixof();
206			free_ent = FIRST - 1;
207			posbits =
208			((posbits - 1) +
209			((n_bits << 3) -
210			(posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
211			n_bits = INIT_BITS;
212			maxcode = MAXCODE(INIT_BITS) - 1;
213			bitmask = (1 << INIT_BITS) - 1;
214			goto resetbuf;
215			}
216
217			incode = code;
218			stackp = de_stack;
219
220			/* Special case for KwKwK string. */
221			if (code >= free_ent) {
222			if (code > free_ent) {
223			unsigned char *p;
224
225			posbits -= n_bits;
226			p = &inbuf[posbits >> 3];
227
228			bb_error_msg
229			("insize:%d posbits:%d inbuf:%02X %02X %02X %02X %02X (%d)",
230			insize, posbits, p[-1], p[0], p[1], p[2], p[3],
231			(posbits & 07));
232	niro	1123	bb_error_msg("corrupted data");
233	niro	816	goto err;
234	niro	532	}
235
236			*--stackp = (unsigned char) finchar;
237			code = oldcode;
238			}
239
240			/* Generate output characters in reverse order */
241	niro	816	while ((long) code >= (long) 256) {
242	niro	532	*--stackp = tab_suffixof(code);
243			code = tab_prefixof(code);
244			}
245
246			finchar = tab_suffixof(code);
247			*--stackp = (unsigned char) finchar;
248
249			/* And put them out in forward order */
250			{
251			int i;
252
253			i = de_stack - stackp;
254			if (outpos + i >= OBUFSIZ) {
255			do {
256			if (i > OBUFSIZ - outpos) {
257			i = OBUFSIZ - outpos;
258			}
259
260			if (i > 0) {
261			memcpy(outbuf + outpos, stackp, i);
262			outpos += i;
263			}
264
265			if (outpos >= OBUFSIZ) {
266			full_write(fd_out, outbuf, outpos);
267			//error check??
268	niro	984	IF_DESKTOP(total_written += outpos;)
269	niro	532	outpos = 0;
270			}
271			stackp += i;
272			i = de_stack - stackp;
273			} while (i > 0);
274			} else {
275			memcpy(outbuf + outpos, stackp, i);
276			outpos += i;
277			}
278			}
279
280			/* Generate the new entry. */
281			code = free_ent;
282			if (code < maxmaxcode) {
283			tab_prefixof(code) = (unsigned short) oldcode;
284			tab_suffixof(code) = (unsigned char) finchar;
285			free_ent = code + 1;
286			}
287
288			/* Remember previous code. */
289			oldcode = incode;
290			}
291
292			} while (rsize > 0);
293
294			if (outpos > 0) {
295			full_write(fd_out, outbuf, outpos);
296			//error check??
297	niro	984	IF_DESKTOP(total_written += outpos;)
298	niro	532	}
299
300	niro	984	retval = IF_DESKTOP(total_written) + 0;
301	niro	816	err:
302			free(inbuf);
303			free(outbuf);
304			free(htab);
305			free(codetab);
306			return retval;
307	niro	532	}