archival/libunarchive/decompress_uncompress.c

/* vi: set sw=4 ts=4: */
#include "libbb.h"

/* 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 <stdio.h>
#include <string.h>
#include <unistd.h>

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

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

/* Defines for third byte of header */
#define	MAGIC_1		(char_type)'\037'	/* First byte of compressed file               */
#define	MAGIC_2		(char_type)'\235'	/* Second byte of compressed file              */
#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 compresssion 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 FAST

#define	HBITS		17	/* 50% occupancy */
#define	HSIZE	   (1<<HBITS)
#define	HMASK	   (HSIZE-1)
#define	HPRIME		 9941
#define	BITS		   16
#undef	MAXSEG_64K
#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_htab()			memset(htab, -1, HSIZE)
#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.  The tables used herein are shared
 * with those of the compress() routine.  See the definitions above.
 */

USE_DESKTOP(long long) int
uncompress(int fd_in, int fd_out)
{
	USE_DESKTOP(long long total_written = 0;)
	unsigned char *stackp;
	long int code;
	int finchar;
	long int oldcode;
	long int incode;
	int inbits;
	int posbits;
	int outpos;
	int insize;
	int bitmask;
	long int free_ent;
	long int maxcode;
	long int maxmaxcode;
	int n_bits;
	int rsize = 0;
	RESERVE_CONFIG_UBUFFER(inbuf, IBUFSIZ + 64);
	RESERVE_CONFIG_UBUFFER(outbuf, OBUFSIZ + 2048);
	unsigned char htab[HSIZE];
	unsigned short codetab[HSIZE];

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

	memset(inbuf, 0, IBUFSIZ + 64);
	memset(outbuf, 0, OBUFSIZ + 2048);

	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");
		return -1;
	}

	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 "
				"%d bits", maxbits, BITS);
		return -1;
	}

	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();

	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("uncompress: corrupt input");
					return -1;
				}

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

			/* Generate output characters in reverse order */
			while ((long int) code >= (long int) 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??
							USE_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??
		USE_DESKTOP(total_written += outpos;)
	}

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