1/*-
2 * Copyright (c) 2003-2007 Tim Kientzle
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26/*
27 * This code borrows heavily from "compress" source code, which is
28 * protected by the following copyright.  (Clause 3 dropped by request
29 * of the Regents.)
30 */
31
32/*-
33 * Copyright (c) 1985, 1986, 1992, 1993
34 *	The Regents of the University of California.  All rights reserved.
35 *
36 * This code is derived from software contributed to Berkeley by
37 * Diomidis Spinellis and James A. Woods, derived from original
38 * work by Spencer Thomas and Joseph Orost.
39 *
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions
42 * are met:
43 * 1. Redistributions of source code must retain the above copyright
44 *    notice, this list of conditions and the following disclaimer.
45 * 2. Redistributions in binary form must reproduce the above copyright
46 *    notice, this list of conditions and the following disclaimer in the
47 *    documentation and/or other materials provided with the distribution.
48 * 4. Neither the name of the University nor the names of its contributors
49 *    may be used to endorse or promote products derived from this software
50 *    without specific prior written permission.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
53 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
55 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
56 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
57 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
58 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
59 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
60 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
61 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
62 * SUCH DAMAGE.
63 */
64
65
66#include "archive_platform.h"
67__FBSDID("$FreeBSD$");
68
69#ifdef HAVE_ERRNO_H
70#include <errno.h>
71#endif
72#ifdef HAVE_STDLIB_H
73#include <stdlib.h>
74#endif
75#ifdef HAVE_STRING_H
76#include <string.h>
77#endif
78#ifdef HAVE_UNISTD_H
79#include <unistd.h>
80#endif
81
82#include "archive.h"
83#include "archive_private.h"
84#include "archive_read_private.h"
85
86/*
87 * Because LZW decompression is pretty simple, I've just implemented
88 * the whole decompressor here (cribbing from "compress" source code,
89 * of course), rather than relying on an external library.  I have
90 * made an effort to clarify and simplify the algorithm, so the
91 * names and structure here don't exactly match those used by compress.
92 */
93
94struct private_data {
95	/* Input variables. */
96	const unsigned char	*next_in;
97	size_t			 avail_in;
98	size_t			 consume_unnotified;
99	int			 bit_buffer;
100	int			 bits_avail;
101	size_t			 bytes_in_section;
102
103	/* Output variables. */
104	size_t			 out_block_size;
105	void			*out_block;
106
107	/* Decompression status variables. */
108	int			 use_reset_code;
109	int			 end_of_stream;	/* EOF status. */
110	int			 maxcode;	/* Largest code. */
111	int			 maxcode_bits;	/* Length of largest code. */
112	int			 section_end_code; /* When to increase bits. */
113	int			 bits;		/* Current code length. */
114	int			 oldcode;	/* Previous code. */
115	int			 finbyte;	/* Last byte of prev code. */
116
117	/* Dictionary. */
118	int			 free_ent;       /* Next dictionary entry. */
119	unsigned char		 suffix[65536];
120	uint16_t		 prefix[65536];
121
122	/*
123	 * Scratch area for expanding dictionary entries.  Note:
124	 * "worst" case here comes from compressing /dev/zero: the
125	 * last code in the dictionary will code a sequence of
126	 * 65536-256 zero bytes.  Thus, we need stack space to expand
127	 * a 65280-byte dictionary entry.  (Of course, 32640:1
128	 * compression could also be considered the "best" case. ;-)
129	 */
130	unsigned char		*stackp;
131	unsigned char		 stack[65300];
132};
133
134static int	compress_bidder_bid(struct archive_read_filter_bidder *, struct archive_read_filter *);
135static int	compress_bidder_init(struct archive_read_filter *);
136static int	compress_bidder_free(struct archive_read_filter_bidder *);
137
138static ssize_t	compress_filter_read(struct archive_read_filter *, const void **);
139static int	compress_filter_close(struct archive_read_filter *);
140
141static int	getbits(struct archive_read_filter *, int n);
142static int	next_code(struct archive_read_filter *);
143
144#if ARCHIVE_VERSION_NUMBER < 4000000
145/* Deprecated; remove in libarchive 4.0 */
146int
147archive_read_support_compression_compress(struct archive *a)
148{
149	return archive_read_support_filter_compress(a);
150}
151#endif
152
153int
154archive_read_support_filter_compress(struct archive *_a)
155{
156	struct archive_read *a = (struct archive_read *)_a;
157	struct archive_read_filter_bidder *bidder;
158
159	archive_check_magic(_a, ARCHIVE_READ_MAGIC,
160	    ARCHIVE_STATE_NEW, "archive_read_support_filter_compress");
161
162	if (__archive_read_get_bidder(a, &bidder) != ARCHIVE_OK)
163		return (ARCHIVE_FATAL);
164
165	bidder->data = NULL;
166	bidder->name = "compress (.Z)";
167	bidder->bid = compress_bidder_bid;
168	bidder->init = compress_bidder_init;
169	bidder->options = NULL;
170	bidder->free = compress_bidder_free;
171	return (ARCHIVE_OK);
172}
173
174/*
175 * Test whether we can handle this data.
176 * This logic returns zero if any part of the signature fails.
177 */
178static int
179compress_bidder_bid(struct archive_read_filter_bidder *self,
180    struct archive_read_filter *filter)
181{
182	const unsigned char *buffer;
183	ssize_t avail;
184	int bits_checked;
185
186	(void)self; /* UNUSED */
187
188	/* Shortest valid compress file is 3 bytes. */
189	buffer = __archive_read_filter_ahead(filter, 3, &avail);
190
191	if (buffer == NULL)
192		return (0);
193
194	bits_checked = 0;
195	/* First two bytes are the magic value */
196	if (buffer[0] != 0x1F || buffer[1] != 0x9D)
197		return (0);
198	/* Third byte holds compression parameters. */
199	if (buffer[2] & 0x20) /* Reserved bit, must be zero. */
200		return (0);
201	if (buffer[2] & 0x40) /* Reserved bit, must be zero. */
202		return (0);
203	bits_checked += 18;
204
205	return (bits_checked);
206}
207
208/*
209 * Setup the callbacks.
210 */
211static int
212compress_bidder_init(struct archive_read_filter *self)
213{
214	struct private_data *state;
215	static const size_t out_block_size = 64 * 1024;
216	void *out_block;
217	int code;
218
219	self->code = ARCHIVE_FILTER_COMPRESS;
220	self->name = "compress (.Z)";
221
222	state = (struct private_data *)calloc(sizeof(*state), 1);
223	out_block = malloc(out_block_size);
224	if (state == NULL || out_block == NULL) {
225		free(out_block);
226		free(state);
227		archive_set_error(&self->archive->archive, ENOMEM,
228		    "Can't allocate data for %s decompression",
229		    self->name);
230		return (ARCHIVE_FATAL);
231	}
232
233	self->data = state;
234	state->out_block_size = out_block_size;
235	state->out_block = out_block;
236	self->read = compress_filter_read;
237	self->skip = NULL; /* not supported */
238	self->close = compress_filter_close;
239
240	/* XXX MOVE THE FOLLOWING OUT OF INIT() XXX */
241
242	(void)getbits(self, 8); /* Skip first signature byte. */
243	(void)getbits(self, 8); /* Skip second signature byte. */
244
245	/* Get compression parameters. */
246	code = getbits(self, 8);
247	if ((code & 0x1f) > 16) {
248		archive_set_error(&self->archive->archive, -1,
249		    "Invalid compressed data");
250		return (ARCHIVE_FATAL);
251	}
252	state->maxcode_bits = code & 0x1f;
253	state->maxcode = (1 << state->maxcode_bits);
254	state->use_reset_code = code & 0x80;
255
256	/* Initialize decompressor. */
257	state->free_ent = 256;
258	state->stackp = state->stack;
259	if (state->use_reset_code)
260		state->free_ent++;
261	state->bits = 9;
262	state->section_end_code = (1<<state->bits) - 1;
263	state->oldcode = -1;
264	for (code = 255; code >= 0; code--) {
265		state->prefix[code] = 0;
266		state->suffix[code] = code;
267	}
268	next_code(self);
269
270	return (ARCHIVE_OK);
271}
272
273/*
274 * Return a block of data from the decompression buffer.  Decompress more
275 * as necessary.
276 */
277static ssize_t
278compress_filter_read(struct archive_read_filter *self, const void **pblock)
279{
280	struct private_data *state;
281	unsigned char *p, *start, *end;
282	int ret;
283
284	state = (struct private_data *)self->data;
285	if (state->end_of_stream) {
286		*pblock = NULL;
287		return (0);
288	}
289	p = start = (unsigned char *)state->out_block;
290	end = start + state->out_block_size;
291
292	while (p < end && !state->end_of_stream) {
293		if (state->stackp > state->stack) {
294			*p++ = *--state->stackp;
295		} else {
296			ret = next_code(self);
297			if (ret == -1)
298				state->end_of_stream = ret;
299			else if (ret != ARCHIVE_OK)
300				return (ret);
301		}
302	}
303
304	*pblock = start;
305	return (p - start);
306}
307
308/*
309 * Clean up the reader.
310 */
311static int
312compress_bidder_free(struct archive_read_filter_bidder *self)
313{
314	self->data = NULL;
315	return (ARCHIVE_OK);
316}
317
318/*
319 * Close and release the filter.
320 */
321static int
322compress_filter_close(struct archive_read_filter *self)
323{
324	struct private_data *state = (struct private_data *)self->data;
325
326	free(state->out_block);
327	free(state);
328	return (ARCHIVE_OK);
329}
330
331/*
332 * Process the next code and fill the stack with the expansion
333 * of the code.  Returns ARCHIVE_FATAL if there is a fatal I/O or
334 * format error, ARCHIVE_EOF if we hit end of data, ARCHIVE_OK otherwise.
335 */
336static int
337next_code(struct archive_read_filter *self)
338{
339	struct private_data *state = (struct private_data *)self->data;
340	int code, newcode;
341
342	static int debug_buff[1024];
343	static unsigned debug_index;
344
345	code = newcode = getbits(self, state->bits);
346	if (code < 0)
347		return (code);
348
349	debug_buff[debug_index++] = code;
350	if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0]))
351		debug_index = 0;
352
353	/* If it's a reset code, reset the dictionary. */
354	if ((code == 256) && state->use_reset_code) {
355		/*
356		 * The original 'compress' implementation blocked its
357		 * I/O in a manner that resulted in junk bytes being
358		 * inserted after every reset.  The next section skips
359		 * this junk.  (Yes, the number of *bytes* to skip is
360		 * a function of the current *bit* length.)
361		 */
362		int skip_bytes =  state->bits -
363		    (state->bytes_in_section % state->bits);
364		skip_bytes %= state->bits;
365		state->bits_avail = 0; /* Discard rest of this byte. */
366		while (skip_bytes-- > 0) {
367			code = getbits(self, 8);
368			if (code < 0)
369				return (code);
370		}
371		/* Now, actually do the reset. */
372		state->bytes_in_section = 0;
373		state->bits = 9;
374		state->section_end_code = (1 << state->bits) - 1;
375		state->free_ent = 257;
376		state->oldcode = -1;
377		return (next_code(self));
378	}
379
380	if (code > state->free_ent
381	    || (code == state->free_ent && state->oldcode < 0)) {
382		/* An invalid code is a fatal error. */
383		archive_set_error(&(self->archive->archive), -1,
384		    "Invalid compressed data");
385		return (ARCHIVE_FATAL);
386	}
387
388	/* Special case for KwKwK string. */
389	if (code >= state->free_ent) {
390		*state->stackp++ = state->finbyte;
391		code = state->oldcode;
392	}
393
394	/* Generate output characters in reverse order. */
395	while (code >= 256) {
396		*state->stackp++ = state->suffix[code];
397		code = state->prefix[code];
398	}
399	*state->stackp++ = state->finbyte = code;
400
401	/* Generate the new entry. */
402	code = state->free_ent;
403	if (code < state->maxcode && state->oldcode >= 0) {
404		state->prefix[code] = state->oldcode;
405		state->suffix[code] = state->finbyte;
406		++state->free_ent;
407	}
408	if (state->free_ent > state->section_end_code) {
409		state->bits++;
410		state->bytes_in_section = 0;
411		if (state->bits == state->maxcode_bits)
412			state->section_end_code = state->maxcode;
413		else
414			state->section_end_code = (1 << state->bits) - 1;
415	}
416
417	/* Remember previous code. */
418	state->oldcode = newcode;
419	return (ARCHIVE_OK);
420}
421
422/*
423 * Return next 'n' bits from stream.
424 *
425 * -1 indicates end of available data.
426 */
427static int
428getbits(struct archive_read_filter *self, int n)
429{
430	struct private_data *state = (struct private_data *)self->data;
431	int code;
432	ssize_t ret;
433	static const int mask[] = {
434		0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
435		0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
436	};
437
438	while (state->bits_avail < n) {
439		if (state->avail_in <= 0) {
440			if (state->consume_unnotified) {
441				__archive_read_filter_consume(self->upstream,
442					state->consume_unnotified);
443				state->consume_unnotified = 0;
444			}
445			state->next_in
446			    = __archive_read_filter_ahead(self->upstream,
447				1, &ret);
448			if (ret == 0)
449				return (-1);
450			if (ret < 0 || state->next_in == NULL)
451				return (ARCHIVE_FATAL);
452			state->consume_unnotified = state->avail_in = ret;
453		}
454		state->bit_buffer |= *state->next_in++ << state->bits_avail;
455		state->avail_in--;
456		state->bits_avail += 8;
457		state->bytes_in_section++;
458	}
459
460	code = state->bit_buffer;
461	state->bit_buffer >>= n;
462	state->bits_avail -= n;
463
464	return (code & mask[n]);
465}
466