Merge from vendor branch LIBARCHIVE:
[dragonfly.git] / contrib / libarchive-2.0 / libarchive / archive_read_support_compression_compress.c
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: src/lib/libarchive/archive_read_support_compression_compress.c,v 1.8 2007/03/03 07:37:36 kientzle Exp $");
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         int                      bit_buffer;
99         int                      bits_avail;
100         size_t                   bytes_in_section;
101
102         /* Output variables. */
103         size_t                   uncompressed_buffer_size;
104         void                    *uncompressed_buffer;
105         unsigned char           *read_next;   /* Data for client. */
106         unsigned char           *next_out;    /* Where to write new data. */
107         size_t                   avail_out;   /* Space at end of buffer. */
108
109         /* Decompression status variables. */
110         int                      use_reset_code;
111         int                      end_of_stream; /* EOF status. */
112         int                      maxcode;       /* Largest code. */
113         int                      maxcode_bits;  /* Length of largest code. */
114         int                      section_end_code; /* When to increase bits. */
115         int                      bits;          /* Current code length. */
116         int                      oldcode;       /* Previous code. */
117         int                      finbyte;       /* Last byte of prev code. */
118
119         /* Dictionary. */
120         int                      free_ent;       /* Next dictionary entry. */
121         unsigned char            suffix[65536];
122         uint16_t                 prefix[65536];
123
124         /*
125          * Scratch area for expanding dictionary entries.  Note:
126          * "worst" case here comes from compressing /dev/zero: the
127          * last code in the dictionary will code a sequence of
128          * 65536-256 zero bytes.  Thus, we need stack space to expand
129          * a 65280-byte dictionary entry.  (Of course, 32640:1
130          * compression could also be considered the "best" case. ;-)
131          */
132         unsigned char           *stackp;
133         unsigned char            stack[65300];
134 };
135
136 static int      bid(const void *, size_t);
137 static int      finish(struct archive_read *);
138 static int      init(struct archive_read *, const void *, size_t);
139 static ssize_t  read_ahead(struct archive_read *, const void **, size_t);
140 static ssize_t  read_consume(struct archive_read *, size_t);
141 static int      getbits(struct archive_read *, struct private_data *, int n);
142 static int      next_code(struct archive_read *a, struct private_data *state);
143
144 int
145 archive_read_support_compression_compress(struct archive *_a)
146 {
147         struct archive_read *a = (struct archive_read *)_a;
148         return (__archive_read_register_compression(a, bid, init));
149 }
150
151 /*
152  * Test whether we can handle this data.
153  *
154  * This logic returns zero if any part of the signature fails.  It
155  * also tries to Do The Right Thing if a very short buffer prevents us
156  * from verifying as much as we would like.
157  */
158 static int
159 bid(const void *buff, size_t len)
160 {
161         const unsigned char *buffer;
162         int bits_checked;
163
164         if (len < 1)
165                 return (0);
166
167         buffer = (const unsigned char *)buff;
168         bits_checked = 0;
169         if (buffer[0] != 037)   /* Verify first ID byte. */
170                 return (0);
171         bits_checked += 8;
172         if (len < 2)
173                 return (bits_checked);
174
175         if (buffer[1] != 0235)  /* Verify second ID byte. */
176                 return (0);
177         bits_checked += 8;
178         if (len < 3)
179                 return (bits_checked);
180
181         /*
182          * TODO: Verify more.
183          */
184
185         return (bits_checked);
186 }
187
188 /*
189  * Setup the callbacks.
190  */
191 static int
192 init(struct archive_read *a, const void *buff, size_t n)
193 {
194         struct private_data *state;
195         int code;
196
197         a->archive.compression_code = ARCHIVE_COMPRESSION_COMPRESS;
198         a->archive.compression_name = "compress (.Z)";
199
200         a->compression_read_ahead = read_ahead;
201         a->compression_read_consume = read_consume;
202         a->compression_skip = NULL; /* not supported */
203         a->compression_finish = finish;
204
205         state = (struct private_data *)malloc(sizeof(*state));
206         if (state == NULL) {
207                 archive_set_error(&a->archive, ENOMEM,
208                     "Can't allocate data for %s decompression",
209                     a->archive.compression_name);
210                 return (ARCHIVE_FATAL);
211         }
212         memset(state, 0, sizeof(*state));
213         a->compression_data = state;
214
215         state->uncompressed_buffer_size = 64 * 1024;
216         state->uncompressed_buffer = malloc(state->uncompressed_buffer_size);
217
218         if (state->uncompressed_buffer == NULL) {
219                 archive_set_error(&a->archive, ENOMEM,
220                     "Can't allocate %s decompression buffers",
221                     a->archive.compression_name);
222                 goto fatal;
223         }
224
225         state->next_in = (const unsigned char *)buff;
226         state->avail_in = n;
227         state->read_next = state->next_out = (unsigned char *)state->uncompressed_buffer;
228         state->avail_out = state->uncompressed_buffer_size;
229
230         code = getbits(a, state, 8);
231         if (code != 037) /* This should be impossible. */
232                 goto fatal;
233
234         code = getbits(a, state, 8);
235         if (code != 0235) {
236                 /* This can happen if the library is receiving 1-byte
237                  * blocks and gzip and compress are both enabled.
238                  * You can't distinguish gzip and compress only from
239                  * the first byte. */
240                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
241                     "Compress signature did not match.");
242                 goto fatal;
243         }
244
245         code = getbits(a, state, 8);
246         state->maxcode_bits = code & 0x1f;
247         state->maxcode = (1 << state->maxcode_bits);
248         state->use_reset_code = code & 0x80;
249
250         /* Initialize decompressor. */
251         state->free_ent = 256;
252         state->stackp = state->stack;
253         if (state->use_reset_code)
254                 state->free_ent++;
255         state->bits = 9;
256         state->section_end_code = (1<<state->bits) - 1;
257         state->oldcode = -1;
258         for (code = 255; code >= 0; code--) {
259                 state->prefix[code] = 0;
260                 state->suffix[code] = code;
261         }
262         next_code(a, state);
263         return (ARCHIVE_OK);
264
265 fatal:
266         finish(a);
267         return (ARCHIVE_FATAL);
268 }
269
270 /*
271  * Return a block of data from the decompression buffer.  Decompress more
272  * as necessary.
273  */
274 static ssize_t
275 read_ahead(struct archive_read *a, const void **p, size_t min)
276 {
277         struct private_data *state;
278         int read_avail, was_avail, ret;
279
280         state = (struct private_data *)a->compression_data;
281         was_avail = -1;
282         if (!a->client_reader) {
283                 archive_set_error(&a->archive, ARCHIVE_ERRNO_PROGRAMMER,
284                     "No read callback is registered?  "
285                     "This is probably an internal programming error.");
286                 return (ARCHIVE_FATAL);
287         }
288
289         read_avail = state->next_out - state->read_next;
290
291         if (read_avail < (int)min  &&  state->end_of_stream) {
292                 if (state->end_of_stream == ARCHIVE_EOF)
293                         return (0);
294                 else
295                         return (-1);
296         }
297
298         if (read_avail < (int)min) {
299                 memmove(state->uncompressed_buffer, state->read_next,
300                     read_avail);
301                 state->read_next = (unsigned char *)state->uncompressed_buffer;
302                 state->next_out = state->read_next + read_avail;
303                 state->avail_out
304                     = state->uncompressed_buffer_size - read_avail;
305
306                 while (read_avail < (int)state->uncompressed_buffer_size
307                         && !state->end_of_stream) {
308                         if (state->stackp > state->stack) {
309                                 *state->next_out++ = *--state->stackp;
310                                 state->avail_out--;
311                                 read_avail++;
312                         } else {
313                                 ret = next_code(a, state);
314                                 if (ret == ARCHIVE_EOF)
315                                         state->end_of_stream = ret;
316                                 else if (ret != ARCHIVE_OK)
317                                         return (ret);
318                         }
319                 }
320         }
321
322         *p = state->read_next;
323         return (read_avail);
324 }
325
326 /*
327  * Mark a previously-returned block of data as read.
328  */
329 static ssize_t
330 read_consume(struct archive_read *a, size_t n)
331 {
332         struct private_data *state;
333
334         state = (struct private_data *)a->compression_data;
335         a->archive.file_position += n;
336         state->read_next += n;
337         if (state->read_next > state->next_out)
338                 __archive_errx(1, "Request to consume too many "
339                     "bytes from compress decompressor");
340         return (n);
341 }
342
343 /*
344  * Clean up the decompressor.
345  */
346 static int
347 finish(struct archive_read *a)
348 {
349         struct private_data *state;
350         int ret = ARCHIVE_OK;
351
352         state = (struct private_data *)a->compression_data;
353
354         if (state != NULL) {
355                 if (state->uncompressed_buffer != NULL)
356                         free(state->uncompressed_buffer);
357                 free(state);
358         }
359
360         a->compression_data = NULL;
361         if (a->client_closer != NULL)
362                 ret = (a->client_closer)(&a->archive, a->client_data);
363
364         return (ret);
365 }
366
367 /*
368  * Process the next code and fill the stack with the expansion
369  * of the code.  Returns ARCHIVE_FATAL if there is a fatal I/O or
370  * format error, ARCHIVE_EOF if we hit end of data, ARCHIVE_OK otherwise.
371  */
372 static int
373 next_code(struct archive_read *a, struct private_data *state)
374 {
375         int code, newcode;
376
377         static int debug_buff[1024];
378         static unsigned debug_index;
379
380         code = newcode = getbits(a, state, state->bits);
381         if (code < 0)
382                 return (code);
383
384         debug_buff[debug_index++] = code;
385         if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0]))
386                 debug_index = 0;
387
388         /* If it's a reset code, reset the dictionary. */
389         if ((code == 256) && state->use_reset_code) {
390                 /*
391                  * The original 'compress' implementation blocked its
392                  * I/O in a manner that resulted in junk bytes being
393                  * inserted after every reset.  The next section skips
394                  * this junk.  (Yes, the number of *bytes* to skip is
395                  * a function of the current *bit* length.)
396                  */
397                 int skip_bytes =  state->bits -
398                     (state->bytes_in_section % state->bits);
399                 skip_bytes %= state->bits;
400                 state->bits_avail = 0; /* Discard rest of this byte. */
401                 while (skip_bytes-- > 0) {
402                         code = getbits(a, state, 8);
403                         if (code < 0)
404                                 return (code);
405                 }
406                 /* Now, actually do the reset. */
407                 state->bytes_in_section = 0;
408                 state->bits = 9;
409                 state->section_end_code = (1 << state->bits) - 1;
410                 state->free_ent = 257;
411                 state->oldcode = -1;
412                 return (next_code(a, state));
413         }
414
415         if (code > state->free_ent) {
416                 /* An invalid code is a fatal error. */
417                 archive_set_error(&a->archive, -1, "Invalid compressed data");
418                 return (ARCHIVE_FATAL);
419         }
420
421         /* Special case for KwKwK string. */
422         if (code >= state->free_ent) {
423                 *state->stackp++ = state->finbyte;
424                 code = state->oldcode;
425         }
426
427         /* Generate output characters in reverse order. */
428         while (code >= 256) {
429                 *state->stackp++ = state->suffix[code];
430                 code = state->prefix[code];
431         }
432         *state->stackp++ = state->finbyte = code;
433
434         /* Generate the new entry. */
435         code = state->free_ent;
436         if (code < state->maxcode && state->oldcode >= 0) {
437                 state->prefix[code] = state->oldcode;
438                 state->suffix[code] = state->finbyte;
439                 ++state->free_ent;
440         }
441         if (state->free_ent > state->section_end_code) {
442                 state->bits++;
443                 state->bytes_in_section = 0;
444                 if (state->bits == state->maxcode_bits)
445                         state->section_end_code = state->maxcode;
446                 else
447                         state->section_end_code = (1 << state->bits) - 1;
448         }
449
450         /* Remember previous code. */
451         state->oldcode = newcode;
452         return (ARCHIVE_OK);
453 }
454
455 /*
456  * Return next 'n' bits from stream.
457  *
458  * -1 indicates end of available data.
459  */
460 static int
461 getbits(struct archive_read *a, struct private_data *state, int n)
462 {
463         int code, ret;
464         static const int mask[] = {
465                 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
466                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
467         };
468
469
470         while (state->bits_avail < n) {
471                 if (state->avail_in <= 0) {
472                         ret = (a->client_reader)(&a->archive, a->client_data,
473                             (const void **)&state->next_in);
474                         if (ret < 0)
475                                 return (ARCHIVE_FATAL);
476                         if (ret == 0)
477                                 return (ARCHIVE_EOF);
478                         a->archive.raw_position += ret;
479                         state->avail_in = ret;
480                 }
481                 state->bit_buffer |= *state->next_in++ << state->bits_avail;
482                 state->avail_in--;
483                 state->bits_avail += 8;
484                 state->bytes_in_section++;
485         }
486
487         code = state->bit_buffer;
488         state->bit_buffer >>= n;
489         state->bits_avail -= n;
490
491         return (code & mask[n]);
492 }