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
94 struct 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
134 static int compress_bidder_bid(struct archive_read_filter_bidder *, struct archive_read_filter *);
135 static int compress_bidder_init(struct archive_read_filter *);
136 static int compress_bidder_free(struct archive_read_filter_bidder *);
137
138 static ssize_t compress_filter_read(struct archive_read_filter *, const void **);
139 static int compress_filter_close(struct archive_read_filter *);
140
141 static int getbits(struct archive_read_filter *, int n);
142 static int next_code(struct archive_read_filter *);
143
144 #if ARCHIVE_VERSION_NUMBER < 4000000
145 /* Deprecated; remove in libarchive 4.0 */
146 int
archive_read_support_compression_compress(struct archive * a)147 archive_read_support_compression_compress(struct archive *a)
148 {
149 return archive_read_support_filter_compress(a);
150 }
151 #endif
152
153 int
archive_read_support_filter_compress(struct archive * _a)154 archive_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 */
178 static int
compress_bidder_bid(struct archive_read_filter_bidder * self,struct archive_read_filter * filter)179 compress_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 buffer = __archive_read_filter_ahead(filter, 2, &avail);
189
190 if (buffer == NULL)
191 return (0);
192
193 bits_checked = 0;
194 if (buffer[0] != 0x1F || buffer[1] != 0x9D)
195 return (0);
196 bits_checked += 16;
197
198 /*
199 * TODO: Verify more.
200 */
201
202 return (bits_checked);
203 }
204
205 /*
206 * Setup the callbacks.
207 */
208 static int
compress_bidder_init(struct archive_read_filter * self)209 compress_bidder_init(struct archive_read_filter *self)
210 {
211 struct private_data *state;
212 static const size_t out_block_size = 64 * 1024;
213 void *out_block;
214 int code;
215
216 self->code = ARCHIVE_FILTER_COMPRESS;
217 self->name = "compress (.Z)";
218
219 state = (struct private_data *)calloc(sizeof(*state), 1);
220 out_block = malloc(out_block_size);
221 if (state == NULL || out_block == NULL) {
222 free(out_block);
223 free(state);
224 archive_set_error(&self->archive->archive, ENOMEM,
225 "Can't allocate data for %s decompression",
226 self->name);
227 return (ARCHIVE_FATAL);
228 }
229
230 self->data = state;
231 state->out_block_size = out_block_size;
232 state->out_block = out_block;
233 self->read = compress_filter_read;
234 self->skip = NULL; /* not supported */
235 self->close = compress_filter_close;
236
237 /* XXX MOVE THE FOLLOWING OUT OF INIT() XXX */
238
239 (void)getbits(self, 8); /* Skip first signature byte. */
240 (void)getbits(self, 8); /* Skip second signature byte. */
241
242 code = getbits(self, 8);
243 state->maxcode_bits = code & 0x1f;
244 state->maxcode = (1 << state->maxcode_bits);
245 state->use_reset_code = code & 0x80;
246
247 /* Initialize decompressor. */
248 state->free_ent = 256;
249 state->stackp = state->stack;
250 if (state->use_reset_code)
251 state->free_ent++;
252 state->bits = 9;
253 state->section_end_code = (1<<state->bits) - 1;
254 state->oldcode = -1;
255 for (code = 255; code >= 0; code--) {
256 state->prefix[code] = 0;
257 state->suffix[code] = code;
258 }
259 next_code(self);
260
261 return (ARCHIVE_OK);
262 }
263
264 /*
265 * Return a block of data from the decompression buffer. Decompress more
266 * as necessary.
267 */
268 static ssize_t
compress_filter_read(struct archive_read_filter * self,const void ** pblock)269 compress_filter_read(struct archive_read_filter *self, const void **pblock)
270 {
271 struct private_data *state;
272 unsigned char *p, *start, *end;
273 int ret;
274
275 state = (struct private_data *)self->data;
276 if (state->end_of_stream) {
277 *pblock = NULL;
278 return (0);
279 }
280 p = start = (unsigned char *)state->out_block;
281 end = start + state->out_block_size;
282
283 while (p < end && !state->end_of_stream) {
284 if (state->stackp > state->stack) {
285 *p++ = *--state->stackp;
286 } else {
287 ret = next_code(self);
288 if (ret == -1)
289 state->end_of_stream = ret;
290 else if (ret != ARCHIVE_OK)
291 return (ret);
292 }
293 }
294
295 *pblock = start;
296 return (p - start);
297 }
298
299 /*
300 * Clean up the reader.
301 */
302 static int
compress_bidder_free(struct archive_read_filter_bidder * self)303 compress_bidder_free(struct archive_read_filter_bidder *self)
304 {
305 self->data = NULL;
306 return (ARCHIVE_OK);
307 }
308
309 /*
310 * Close and release the filter.
311 */
312 static int
compress_filter_close(struct archive_read_filter * self)313 compress_filter_close(struct archive_read_filter *self)
314 {
315 struct private_data *state = (struct private_data *)self->data;
316
317 free(state->out_block);
318 free(state);
319 return (ARCHIVE_OK);
320 }
321
322 /*
323 * Process the next code and fill the stack with the expansion
324 * of the code. Returns ARCHIVE_FATAL if there is a fatal I/O or
325 * format error, ARCHIVE_EOF if we hit end of data, ARCHIVE_OK otherwise.
326 */
327 static int
next_code(struct archive_read_filter * self)328 next_code(struct archive_read_filter *self)
329 {
330 struct private_data *state = (struct private_data *)self->data;
331 int code, newcode;
332
333 static int debug_buff[1024];
334 static unsigned debug_index;
335
336 code = newcode = getbits(self, state->bits);
337 if (code < 0)
338 return (code);
339
340 debug_buff[debug_index++] = code;
341 if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0]))
342 debug_index = 0;
343
344 /* If it's a reset code, reset the dictionary. */
345 if ((code == 256) && state->use_reset_code) {
346 /*
347 * The original 'compress' implementation blocked its
348 * I/O in a manner that resulted in junk bytes being
349 * inserted after every reset. The next section skips
350 * this junk. (Yes, the number of *bytes* to skip is
351 * a function of the current *bit* length.)
352 */
353 int skip_bytes = state->bits -
354 (state->bytes_in_section % state->bits);
355 skip_bytes %= state->bits;
356 state->bits_avail = 0; /* Discard rest of this byte. */
357 while (skip_bytes-- > 0) {
358 code = getbits(self, 8);
359 if (code < 0)
360 return (code);
361 }
362 /* Now, actually do the reset. */
363 state->bytes_in_section = 0;
364 state->bits = 9;
365 state->section_end_code = (1 << state->bits) - 1;
366 state->free_ent = 257;
367 state->oldcode = -1;
368 return (next_code(self));
369 }
370
371 if (code > state->free_ent) {
372 /* An invalid code is a fatal error. */
373 archive_set_error(&(self->archive->archive), -1,
374 "Invalid compressed data");
375 return (ARCHIVE_FATAL);
376 }
377
378 /* Special case for KwKwK string. */
379 if (code >= state->free_ent) {
380 *state->stackp++ = state->finbyte;
381 code = state->oldcode;
382 }
383
384 /* Generate output characters in reverse order. */
385 while (code >= 256) {
386 *state->stackp++ = state->suffix[code];
387 code = state->prefix[code];
388 }
389 *state->stackp++ = state->finbyte = code;
390
391 /* Generate the new entry. */
392 code = state->free_ent;
393 if (code < state->maxcode && state->oldcode >= 0) {
394 state->prefix[code] = state->oldcode;
395 state->suffix[code] = state->finbyte;
396 ++state->free_ent;
397 }
398 if (state->free_ent > state->section_end_code) {
399 state->bits++;
400 state->bytes_in_section = 0;
401 if (state->bits == state->maxcode_bits)
402 state->section_end_code = state->maxcode;
403 else
404 state->section_end_code = (1 << state->bits) - 1;
405 }
406
407 /* Remember previous code. */
408 state->oldcode = newcode;
409 return (ARCHIVE_OK);
410 }
411
412 /*
413 * Return next 'n' bits from stream.
414 *
415 * -1 indicates end of available data.
416 */
417 static int
getbits(struct archive_read_filter * self,int n)418 getbits(struct archive_read_filter *self, int n)
419 {
420 struct private_data *state = (struct private_data *)self->data;
421 int code;
422 ssize_t ret;
423 static const int mask[] = {
424 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
425 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
426 };
427
428 while (state->bits_avail < n) {
429 if (state->avail_in <= 0) {
430 if (state->consume_unnotified) {
431 __archive_read_filter_consume(self->upstream,
432 state->consume_unnotified);
433 state->consume_unnotified = 0;
434 }
435 state->next_in
436 = __archive_read_filter_ahead(self->upstream,
437 1, &ret);
438 if (ret == 0)
439 return (-1);
440 if (ret < 0 || state->next_in == NULL)
441 return (ARCHIVE_FATAL);
442 state->consume_unnotified = state->avail_in = ret;
443 }
444 state->bit_buffer |= *state->next_in++ << state->bits_avail;
445 state->avail_in--;
446 state->bits_avail += 8;
447 state->bytes_in_section++;
448 }
449
450 code = state->bit_buffer;
451 state->bit_buffer >>= n;
452 state->bits_avail -= n;
453
454 return (code & mask[n]);
455 }
456