2 * Copyright (c) 2003-2007 Tim Kientzle
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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.
27 * This code borrows heavily from "compress" source code, which is
28 * protected by the following copyright. (Clause 3 dropped by request
33 * Copyright (c) 1985, 1986, 1992, 1993
34 * The Regents of the University of California. All rights reserved.
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.
40 * Redistribution and use in source and binary forms, with or without
41 * modification, are permitted provided that the following conditions
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.
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
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 $");
83 #include "archive_private.h"
84 #include "archive_read_private.h"
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.
95 /* Input variables. */
96 const unsigned char *next_in
;
100 size_t bytes_in_section
;
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. */
109 /* Decompression status variables. */
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. */
120 int free_ent
; /* Next dictionary entry. */
121 unsigned char suffix
[65536];
122 uint16_t prefix
[65536];
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. ;-)
132 unsigned char *stackp
;
133 unsigned char stack
[65300];
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
);
145 archive_read_support_compression_compress(struct archive
*_a
)
147 struct archive_read
*a
= (struct archive_read
*)_a
;
148 return (__archive_read_register_compression(a
, bid
, init
));
152 * Test whether we can handle this data.
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.
159 bid(const void *buff
, size_t len
)
161 const unsigned char *buffer
;
167 buffer
= (const unsigned char *)buff
;
169 if (buffer
[0] != 037) /* Verify first ID byte. */
173 return (bits_checked
);
175 if (buffer
[1] != 0235) /* Verify second ID byte. */
179 return (bits_checked
);
185 return (bits_checked
);
189 * Setup the callbacks.
192 init(struct archive_read
*a
, const void *buff
, size_t n
)
194 struct private_data
*state
;
197 a
->archive
.compression_code
= ARCHIVE_COMPRESSION_COMPRESS
;
198 a
->archive
.compression_name
= "compress (.Z)";
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
;
205 state
= (struct private_data
*)malloc(sizeof(*state
));
207 archive_set_error(&a
->archive
, ENOMEM
,
208 "Can't allocate data for %s decompression",
209 a
->archive
.compression_name
);
210 return (ARCHIVE_FATAL
);
212 memset(state
, 0, sizeof(*state
));
213 a
->compression_data
= state
;
215 state
->uncompressed_buffer_size
= 64 * 1024;
216 state
->uncompressed_buffer
= malloc(state
->uncompressed_buffer_size
);
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
);
225 state
->next_in
= (const unsigned char *)buff
;
227 state
->read_next
= state
->next_out
= (unsigned char *)state
->uncompressed_buffer
;
228 state
->avail_out
= state
->uncompressed_buffer_size
;
230 code
= getbits(a
, state
, 8);
231 if (code
!= 037) /* This should be impossible. */
234 code
= getbits(a
, state
, 8);
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
240 archive_set_error(&a
->archive
, ARCHIVE_ERRNO_FILE_FORMAT
,
241 "Compress signature did not match.");
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;
250 /* Initialize decompressor. */
251 state
->free_ent
= 256;
252 state
->stackp
= state
->stack
;
253 if (state
->use_reset_code
)
256 state
->section_end_code
= (1<<state
->bits
) - 1;
258 for (code
= 255; code
>= 0; code
--) {
259 state
->prefix
[code
] = 0;
260 state
->suffix
[code
] = code
;
267 return (ARCHIVE_FATAL
);
271 * Return a block of data from the decompression buffer. Decompress more
275 read_ahead(struct archive_read
*a
, const void **p
, size_t min
)
277 struct private_data
*state
;
278 int read_avail
, was_avail
, ret
;
280 state
= (struct private_data
*)a
->compression_data
;
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
);
289 read_avail
= state
->next_out
- state
->read_next
;
291 if (read_avail
< (int)min
&& state
->end_of_stream
) {
292 if (state
->end_of_stream
== ARCHIVE_EOF
)
298 if (read_avail
< (int)min
) {
299 memmove(state
->uncompressed_buffer
, state
->read_next
,
301 state
->read_next
= (unsigned char *)state
->uncompressed_buffer
;
302 state
->next_out
= state
->read_next
+ read_avail
;
304 = state
->uncompressed_buffer_size
- read_avail
;
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
;
313 ret
= next_code(a
, state
);
314 if (ret
== ARCHIVE_EOF
)
315 state
->end_of_stream
= ret
;
316 else if (ret
!= ARCHIVE_OK
)
322 *p
= state
->read_next
;
327 * Mark a previously-returned block of data as read.
330 read_consume(struct archive_read
*a
, size_t n
)
332 struct private_data
*state
;
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");
344 * Clean up the decompressor.
347 finish(struct archive_read
*a
)
349 struct private_data
*state
;
350 int ret
= ARCHIVE_OK
;
352 state
= (struct private_data
*)a
->compression_data
;
355 if (state
->uncompressed_buffer
!= NULL
)
356 free(state
->uncompressed_buffer
);
360 a
->compression_data
= NULL
;
361 if (a
->client_closer
!= NULL
)
362 ret
= (a
->client_closer
)(&a
->archive
, a
->client_data
);
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.
373 next_code(struct archive_read
*a
, struct private_data
*state
)
377 static int debug_buff
[1024];
378 static unsigned debug_index
;
380 code
= newcode
= getbits(a
, state
, state
->bits
);
384 debug_buff
[debug_index
++] = code
;
385 if (debug_index
>= sizeof(debug_buff
)/sizeof(debug_buff
[0]))
388 /* If it's a reset code, reset the dictionary. */
389 if ((code
== 256) && state
->use_reset_code
) {
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.)
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);
406 /* Now, actually do the reset. */
407 state
->bytes_in_section
= 0;
409 state
->section_end_code
= (1 << state
->bits
) - 1;
410 state
->free_ent
= 257;
412 return (next_code(a
, state
));
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
);
421 /* Special case for KwKwK string. */
422 if (code
>= state
->free_ent
) {
423 *state
->stackp
++ = state
->finbyte
;
424 code
= state
->oldcode
;
427 /* Generate output characters in reverse order. */
428 while (code
>= 256) {
429 *state
->stackp
++ = state
->suffix
[code
];
430 code
= state
->prefix
[code
];
432 *state
->stackp
++ = state
->finbyte
= code
;
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
;
441 if (state
->free_ent
> state
->section_end_code
) {
443 state
->bytes_in_section
= 0;
444 if (state
->bits
== state
->maxcode_bits
)
445 state
->section_end_code
= state
->maxcode
;
447 state
->section_end_code
= (1 << state
->bits
) - 1;
450 /* Remember previous code. */
451 state
->oldcode
= newcode
;
456 * Return next 'n' bits from stream.
458 * -1 indicates end of available data.
461 getbits(struct archive_read
*a
, struct private_data
*state
, int n
)
464 static const int mask
[] = {
465 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
466 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
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
);
475 return (ARCHIVE_FATAL
);
477 return (ARCHIVE_EOF
);
478 a
->archive
.raw_position
+= ret
;
479 state
->avail_in
= ret
;
481 state
->bit_buffer
|= *state
->next_in
++ << state
->bits_avail
;
483 state
->bits_avail
+= 8;
484 state
->bytes_in_section
++;
487 code
= state
->bit_buffer
;
488 state
->bit_buffer
>>= n
;
489 state
->bits_avail
-= n
;
491 return (code
& mask
[n
]);