Import libarchive and bsdtar. The default tar (/usr/bin/tar) can be choosen
[dragonfly.git] / contrib / 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.3 2004/10/17 23:40:10 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_finish = finish;
194
195         state = malloc(sizeof(*state));
196         if (state == NULL) {
197                 archive_set_error(a, ENOMEM,
198                     "Can't allocate data for %s decompression",
199                     a->compression_name);
200                 return (ARCHIVE_FATAL);
201         }
202         memset(state, 0, sizeof(*state));
203
204         state->uncompressed_buffer_size = 64 * 1024;
205         state->uncompressed_buffer = malloc(state->uncompressed_buffer_size);
206
207         if (state->uncompressed_buffer == NULL) {
208                 archive_set_error(a, ENOMEM,
209                     "Can't allocate %s decompression buffers",
210                     a->compression_name);
211                 goto fatal;
212         }
213
214         state->next_in = buff;
215         state->avail_in = n;
216         state->read_next = state->next_out = state->uncompressed_buffer;
217         state->avail_out = state->uncompressed_buffer_size;
218
219         code = getbits(a, state, 8);
220         if (code != 037)
221                 goto fatal;
222
223         code = getbits(a, state, 8);
224         if (code != 0235)
225                 goto fatal;
226
227         code = getbits(a, state, 8);
228         state->maxcode_bits = code & 0x1f;
229         state->maxcode = (1 << state->maxcode_bits);
230         state->use_reset_code = code & 0x80;
231
232         /* Initialize decompressor. */
233         state->free_ent = 256;
234         state->stackp = state->stack;
235         if (state->use_reset_code)
236                 state->free_ent++;
237         state->bits = 9;
238         state->section_end_code = (1<<state->bits) - 1;
239         state->oldcode = -1;
240         for (code = 255; code >= 0; code--) {
241                 state->prefix[code] = 0;
242                 state->suffix[code] = code;
243         }
244         next_code(a, state);
245         a->compression_data = state;
246
247         return (ARCHIVE_OK);
248
249 fatal:
250         finish(a);
251         return (ARCHIVE_FATAL);
252 }
253
254 /*
255  * Return a block of data from the decompression buffer.  Decompress more
256  * as necessary.
257  */
258 static ssize_t
259 read_ahead(struct archive *a, const void **p, size_t min)
260 {
261         struct private_data *state;
262         int read_avail, was_avail, ret;
263
264         state = a->compression_data;
265         was_avail = -1;
266         if (!a->client_reader) {
267                 archive_set_error(a, ARCHIVE_ERRNO_PROGRAMMER,
268                     "No read callback is registered?  "
269                     "This is probably an internal programming error.");
270                 return (ARCHIVE_FATAL);
271         }
272
273         read_avail = state->next_out - state->read_next;
274
275         if (read_avail < (int)min  &&  state->end_of_stream) {
276                 if (state->end_of_stream == ARCHIVE_EOF)
277                         return (0);
278                 else
279                         return (-1);
280         }
281
282         if (read_avail < (int)min) {
283                 memmove(state->uncompressed_buffer, state->read_next,
284                     read_avail);
285                 state->read_next = state->uncompressed_buffer;
286                 state->next_out = state->read_next + read_avail;
287                 state->avail_out
288                     = state->uncompressed_buffer_size - read_avail;
289
290                 while (read_avail < (int)state->uncompressed_buffer_size
291                         && !state->end_of_stream) {
292                         if (state->stackp > state->stack) {
293                                 *state->next_out++ = *--state->stackp;
294                                 state->avail_out--;
295                                 read_avail++;
296                         } else {
297                                 ret = next_code(a, state);
298                                 if (ret == ARCHIVE_EOF)
299                                         state->end_of_stream = ret;
300                                 else if (ret != ARCHIVE_OK)
301                                         return (ret);
302                         }
303                 }
304         }
305
306         *p = state->read_next;
307         return (read_avail);
308 }
309
310 /*
311  * Mark a previously-returned block of data as read.
312  */
313 static ssize_t
314 read_consume(struct archive *a, size_t n)
315 {
316         struct private_data *state;
317
318         state = a->compression_data;
319         a->file_position += n;
320         state->read_next += n;
321         if (state->read_next > state->next_out)
322                 __archive_errx(1, "Request to consume too many "
323                     "bytes from compress decompressor");
324         return (n);
325 }
326
327 /*
328  * Clean up the decompressor.
329  */
330 static int
331 finish(struct archive *a)
332 {
333         struct private_data *state;
334         int ret;
335
336         state = a->compression_data;
337         ret = ARCHIVE_OK;
338
339         free(state->uncompressed_buffer);
340         free(state);
341
342         a->compression_data = NULL;
343         if (a->client_closer != NULL)
344                 (a->client_closer)(a, a->client_data);
345
346         return (ret);
347 }
348
349 /*
350  * Process the next code and fill the stack with the expansion
351  * of the code.  Returns ARCHIVE_FATAL if there is a fatal I/O or
352  * format error, ARCHIVE_EOF if we hit end of data, ARCHIVE_OK otherwise.
353  */
354 static int
355 next_code(struct archive *a, struct private_data *state)
356 {
357         int code, newcode;
358
359         static int debug_buff[1024];
360         static unsigned debug_index;
361
362         code = newcode = getbits(a, state, state->bits);
363         if (code < 0)
364                 return (code);
365
366         debug_buff[debug_index++] = code;
367         if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0]))
368                 debug_index = 0;
369
370         /* If it's a reset code, reset the dictionary. */
371         if ((code == 256) && state->use_reset_code) {
372                 /*
373                  * The original 'compress' implementation blocked its
374                  * I/O in a manner that resulted in junk bytes being
375                  * inserted after every reset.  The next section skips
376                  * this junk.  (Yes, the number of *bytes* to skip is
377                  * a function of the current *bit* length.)
378                  */
379                 int skip_bytes =  state->bits -
380                     (state->bytes_in_section % state->bits);
381                 skip_bytes %= state->bits;
382                 state->bits_avail = 0; /* Discard rest of this byte. */
383                 while (skip_bytes-- > 0) {
384                         code = getbits(a, state, 8);
385                         if (code < 0)
386                                 return (code);
387                 }
388                 /* Now, actually do the reset. */
389                 state->bytes_in_section = 0;
390                 state->bits = 9;
391                 state->section_end_code = (1 << state->bits) - 1;
392                 state->free_ent = 257;
393                 state->oldcode = -1;
394                 return (next_code(a, state));
395         }
396
397         if (code > state->free_ent) {
398                 /* An invalid code is a fatal error. */
399                 archive_set_error(a, -1, "Invalid compressed data");
400                 return (ARCHIVE_FATAL);
401         }
402
403         /* Special case for KwKwK string. */
404         if (code >= state->free_ent) {
405                 *state->stackp++ = state->finbyte;
406                 code = state->oldcode;
407         }
408
409         /* Generate output characters in reverse order. */
410         while (code >= 256) {
411                 *state->stackp++ = state->suffix[code];
412                 code = state->prefix[code];
413         }
414         *state->stackp++ = state->finbyte = code;
415
416         /* Generate the new entry. */
417         code = state->free_ent;
418         if (code < state->maxcode && state->oldcode >= 0) {
419                 state->prefix[code] = state->oldcode;
420                 state->suffix[code] = state->finbyte;
421                 ++state->free_ent;
422         }
423         if (state->free_ent > state->section_end_code) {
424                 state->bits++;
425                 state->bytes_in_section = 0;
426                 if (state->bits == state->maxcode_bits)
427                         state->section_end_code = state->maxcode;
428                 else
429                         state->section_end_code = (1 << state->bits) - 1;
430         }
431
432         /* Remember previous code. */
433         state->oldcode = newcode;
434         return (ARCHIVE_OK);
435 }
436
437 /*
438  * Return next 'n' bits from stream.
439  *
440  * -1 indicates end of available data.
441  */
442 static int
443 getbits(struct archive *a, struct private_data *state, int n)
444 {
445         int code, ret;
446         static const int mask[] = {
447                 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
448                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
449         };
450
451
452         while (state->bits_avail < n) {
453                 if (state->avail_in <= 0) {
454                         ret = (a->client_reader)(a, a->client_data,
455                             (const void **)&state->next_in);
456                         if (ret < 0)
457                                 return (ARCHIVE_FATAL);
458                         if (ret == 0)
459                                 return (ARCHIVE_EOF);
460                         a->raw_position += ret;
461                         state->avail_in = ret;
462                 }
463                 state->bit_buffer |= *state->next_in++ << state->bits_avail;
464                 state->avail_in--;
465                 state->bits_avail += 8;
466                 state->bytes_in_section++;
467         }
468
469         code = state->bit_buffer;
470         state->bit_buffer >>= n;
471         state->bits_avail -= n;
472
473         return (code & mask[n]);
474 }