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