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