archive_read_support_compression_compress.c revision 228761
1306196Sjkim/*- 2238405Sjkim * Copyright (c) 2003-2007 Tim Kientzle 3238405Sjkim * All rights reserved. 4238405Sjkim * 5238405Sjkim * Redistribution and use in source and binary forms, with or without 6238405Sjkim * modification, are permitted provided that the following conditions 7238405Sjkim * are met: 8238405Sjkim * 1. Redistributions of source code must retain the above copyright 9238405Sjkim * notice, this list of conditions and the following disclaimer. 10238405Sjkim * 2. Redistributions in binary form must reproduce the above copyright 11238405Sjkim * notice, this list of conditions and the following disclaimer in the 12238405Sjkim * documentation and/or other materials provided with the distribution. 13238405Sjkim * 14238405Sjkim * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR 15238405Sjkim * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 16238405Sjkim * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 17238405Sjkim * IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT, 18238405Sjkim * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 19238405Sjkim * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 20238405Sjkim * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 21238405Sjkim * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22238405Sjkim * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23238405Sjkim * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24238405Sjkim */ 25238405Sjkim 26238405Sjkim/* 27238405Sjkim * This code borrows heavily from "compress" source code, which is 28238405Sjkim * protected by the following copyright. (Clause 3 dropped by request 29238405Sjkim * of the Regents.) 30238405Sjkim */ 31238405Sjkim 32238405Sjkim/*- 33238405Sjkim * Copyright (c) 1985, 1986, 1992, 1993 34238405Sjkim * The Regents of the University of California. All rights reserved. 35238405Sjkim * 36238405Sjkim * This code is derived from software contributed to Berkeley by 37238405Sjkim * Diomidis Spinellis and James A. Woods, derived from original 38238405Sjkim * work by Spencer Thomas and Joseph Orost. 39238405Sjkim * 40238405Sjkim * Redistribution and use in source and binary forms, with or without 41276864Sjkim * modification, are permitted provided that the following conditions 42276864Sjkim * are met: 43238405Sjkim * 1. Redistributions of source code must retain the above copyright 44238405Sjkim * notice, this list of conditions and the following disclaimer. 45238405Sjkim * 2. Redistributions in binary form must reproduce the above copyright 46238405Sjkim * notice, this list of conditions and the following disclaimer in the 47238405Sjkim * documentation and/or other materials provided with the distribution. 48238405Sjkim * 4. Neither the name of the University nor the names of its contributors 49238405Sjkim * may be used to endorse or promote products derived from this software 50238405Sjkim * without specific prior written permission. 51238405Sjkim * 52238405Sjkim * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 53276864Sjkim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 54276864Sjkim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 55276864Sjkim * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 56238405Sjkim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 57276864Sjkim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 58276864Sjkim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 59276864Sjkim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 60276864Sjkim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 61276864Sjkim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 62276864Sjkim * SUCH DAMAGE. 63238405Sjkim */ 64276864Sjkim 65276864Sjkim 66276864Sjkim#include "archive_platform.h" 67276864Sjkim__FBSDID("$FreeBSD: head/lib/libarchive/archive_read_support_compression_compress.c 201094 2009-12-28 02:29:21Z kientzle $"); 68276864Sjkim 69238405Sjkim#ifdef HAVE_ERRNO_H 70276864Sjkim#include <errno.h> 71238405Sjkim#endif 72238405Sjkim#ifdef HAVE_STDLIB_H 73238405Sjkim#include <stdlib.h> 74238405Sjkim#endif 75238405Sjkim#ifdef HAVE_STRING_H 76238405Sjkim#include <string.h> 77238405Sjkim#endif 78238405Sjkim#ifdef HAVE_UNISTD_H 79238405Sjkim#include <unistd.h> 80238405Sjkim#endif 81238405Sjkim 82238405Sjkim#include "archive.h" 83238405Sjkim#include "archive_private.h" 84238405Sjkim#include "archive_read_private.h" 85238405Sjkim 86238405Sjkim/* 87238405Sjkim * Because LZW decompression is pretty simple, I've just implemented 88238405Sjkim * the whole decompressor here (cribbing from "compress" source code, 89238405Sjkim * of course), rather than relying on an external library. I have 90238405Sjkim * made an effort to clarify and simplify the algorithm, so the 91238405Sjkim * names and structure here don't exactly match those used by compress. 92238405Sjkim */ 93238405Sjkim 94238405Sjkimstruct private_data { 95238405Sjkim /* Input variables. */ 96238405Sjkim const unsigned char *next_in; 97238405Sjkim size_t avail_in; 98238405Sjkim int bit_buffer; 99238405Sjkim int bits_avail; 100238405Sjkim size_t bytes_in_section; 101238405Sjkim 102238405Sjkim /* Output variables. */ 103238405Sjkim size_t out_block_size; 104238405Sjkim void *out_block; 105238405Sjkim 106238405Sjkim /* Decompression status variables. */ 107238405Sjkim int use_reset_code; 108238405Sjkim int end_of_stream; /* EOF status. */ 109238405Sjkim int maxcode; /* Largest code. */ 110238405Sjkim int maxcode_bits; /* Length of largest code. */ 111238405Sjkim int section_end_code; /* When to increase bits. */ 112238405Sjkim int bits; /* Current code length. */ 113238405Sjkim int oldcode; /* Previous code. */ 114238405Sjkim int finbyte; /* Last byte of prev code. */ 115238405Sjkim 116238405Sjkim /* Dictionary. */ 117238405Sjkim int free_ent; /* Next dictionary entry. */ 118238405Sjkim unsigned char suffix[65536]; 119238405Sjkim uint16_t prefix[65536]; 120238405Sjkim 121238405Sjkim /* 122238405Sjkim * Scratch area for expanding dictionary entries. Note: 123238405Sjkim * "worst" case here comes from compressing /dev/zero: the 124238405Sjkim * last code in the dictionary will code a sequence of 125238405Sjkim * 65536-256 zero bytes. Thus, we need stack space to expand 126238405Sjkim * a 65280-byte dictionary entry. (Of course, 32640:1 127238405Sjkim * compression could also be considered the "best" case. ;-) 128238405Sjkim */ 129238405Sjkim unsigned char *stackp; 130238405Sjkim unsigned char stack[65300]; 131238405Sjkim}; 132238405Sjkim 133238405Sjkimstatic int compress_bidder_bid(struct archive_read_filter_bidder *, struct archive_read_filter *); 134238405Sjkimstatic int compress_bidder_init(struct archive_read_filter *); 135238405Sjkimstatic int compress_bidder_free(struct archive_read_filter_bidder *); 136306196Sjkim 137238405Sjkimstatic ssize_t compress_filter_read(struct archive_read_filter *, const void **); 138238405Sjkimstatic int compress_filter_close(struct archive_read_filter *); 139238405Sjkim 140238405Sjkimstatic int getbits(struct archive_read_filter *, int n); 141238405Sjkimstatic int next_code(struct archive_read_filter *); 142238405Sjkim 143238405Sjkimint 144238405Sjkimarchive_read_support_compression_compress(struct archive *_a) 145238405Sjkim{ 146238405Sjkim struct archive_read *a = (struct archive_read *)_a; 147238405Sjkim struct archive_read_filter_bidder *bidder = __archive_read_get_bidder(a); 148238405Sjkim 149238405Sjkim if (bidder == NULL) 150238405Sjkim return (ARCHIVE_FATAL); 151238405Sjkim 152238405Sjkim bidder->data = NULL; 153238405Sjkim bidder->bid = compress_bidder_bid; 154238405Sjkim bidder->init = compress_bidder_init; 155238405Sjkim bidder->options = NULL; 156238405Sjkim bidder->free = compress_bidder_free; 157238405Sjkim return (ARCHIVE_OK); 158238405Sjkim} 159238405Sjkim 160238405Sjkim/* 161238405Sjkim * Test whether we can handle this data. 162238405Sjkim * 163238405Sjkim * This logic returns zero if any part of the signature fails. It 164238405Sjkim * also tries to Do The Right Thing if a very short buffer prevents us 165238405Sjkim * from verifying as much as we would like. 166238405Sjkim */ 167238405Sjkimstatic int 168238405Sjkimcompress_bidder_bid(struct archive_read_filter_bidder *self, 169238405Sjkim struct archive_read_filter *filter) 170238405Sjkim{ 171238405Sjkim const unsigned char *buffer; 172238405Sjkim ssize_t avail; 173238405Sjkim int bits_checked; 174238405Sjkim 175238405Sjkim (void)self; /* UNUSED */ 176238405Sjkim 177238405Sjkim buffer = __archive_read_filter_ahead(filter, 2, &avail); 178238405Sjkim 179238405Sjkim if (buffer == NULL) 180238405Sjkim return (0); 181238405Sjkim 182238405Sjkim bits_checked = 0; 183238405Sjkim if (buffer[0] != 037) /* Verify first ID byte. */ 184238405Sjkim return (0); 185238405Sjkim bits_checked += 8; 186238405Sjkim 187238405Sjkim if (buffer[1] != 0235) /* Verify second ID byte. */ 188238405Sjkim return (0); 189238405Sjkim bits_checked += 8; 190238405Sjkim 191276864Sjkim /* 192238405Sjkim * TODO: Verify more. 193238405Sjkim */ 194238405Sjkim 195238405Sjkim return (bits_checked); 196238405Sjkim} 197238405Sjkim 198238405Sjkim/* 199238405Sjkim * Setup the callbacks. 200238405Sjkim */ 201238405Sjkimstatic int 202238405Sjkimcompress_bidder_init(struct archive_read_filter *self) 203238405Sjkim{ 204238405Sjkim struct private_data *state; 205238405Sjkim static const size_t out_block_size = 64 * 1024; 206238405Sjkim void *out_block; 207238405Sjkim int code; 208238405Sjkim 209276864Sjkim self->code = ARCHIVE_COMPRESSION_COMPRESS; 210238405Sjkim self->name = "compress (.Z)"; 211238405Sjkim 212238405Sjkim state = (struct private_data *)calloc(sizeof(*state), 1); 213238405Sjkim out_block = malloc(out_block_size); 214238405Sjkim if (state == NULL || out_block == NULL) { 215238405Sjkim free(out_block); 216238405Sjkim free(state); 217238405Sjkim archive_set_error(&self->archive->archive, ENOMEM, 218238405Sjkim "Can't allocate data for %s decompression", 219238405Sjkim self->name); 220238405Sjkim return (ARCHIVE_FATAL); 221238405Sjkim } 222238405Sjkim 223238405Sjkim self->data = state; 224238405Sjkim state->out_block_size = out_block_size; 225238405Sjkim state->out_block = out_block; 226238405Sjkim self->read = compress_filter_read; 227238405Sjkim self->skip = NULL; /* not supported */ 228238405Sjkim self->close = compress_filter_close; 229 230 /* XXX MOVE THE FOLLOWING OUT OF INIT() XXX */ 231 232 (void)getbits(self, 8); /* Skip first signature byte. */ 233 (void)getbits(self, 8); /* Skip second signature byte. */ 234 235 code = getbits(self, 8); 236 state->maxcode_bits = code & 0x1f; 237 state->maxcode = (1 << state->maxcode_bits); 238 state->use_reset_code = code & 0x80; 239 240 /* Initialize decompressor. */ 241 state->free_ent = 256; 242 state->stackp = state->stack; 243 if (state->use_reset_code) 244 state->free_ent++; 245 state->bits = 9; 246 state->section_end_code = (1<<state->bits) - 1; 247 state->oldcode = -1; 248 for (code = 255; code >= 0; code--) { 249 state->prefix[code] = 0; 250 state->suffix[code] = code; 251 } 252 next_code(self); 253 254 return (ARCHIVE_OK); 255} 256 257/* 258 * Return a block of data from the decompression buffer. Decompress more 259 * as necessary. 260 */ 261static ssize_t 262compress_filter_read(struct archive_read_filter *self, const void **pblock) 263{ 264 struct private_data *state; 265 unsigned char *p, *start, *end; 266 int ret; 267 268 state = (struct private_data *)self->data; 269 if (state->end_of_stream) { 270 *pblock = NULL; 271 return (0); 272 } 273 p = start = (unsigned char *)state->out_block; 274 end = start + state->out_block_size; 275 276 while (p < end && !state->end_of_stream) { 277 if (state->stackp > state->stack) { 278 *p++ = *--state->stackp; 279 } else { 280 ret = next_code(self); 281 if (ret == -1) 282 state->end_of_stream = ret; 283 else if (ret != ARCHIVE_OK) 284 return (ret); 285 } 286 } 287 288 *pblock = start; 289 return (p - start); 290} 291 292/* 293 * Clean up the reader. 294 */ 295static int 296compress_bidder_free(struct archive_read_filter_bidder *self) 297{ 298 self->data = NULL; 299 return (ARCHIVE_OK); 300} 301 302/* 303 * Close and release the filter. 304 */ 305static int 306compress_filter_close(struct archive_read_filter *self) 307{ 308 struct private_data *state = (struct private_data *)self->data; 309 310 free(state->out_block); 311 free(state); 312 return (ARCHIVE_OK); 313} 314 315/* 316 * Process the next code and fill the stack with the expansion 317 * of the code. Returns ARCHIVE_FATAL if there is a fatal I/O or 318 * format error, ARCHIVE_EOF if we hit end of data, ARCHIVE_OK otherwise. 319 */ 320static int 321next_code(struct archive_read_filter *self) 322{ 323 struct private_data *state = (struct private_data *)self->data; 324 int code, newcode; 325 326 static int debug_buff[1024]; 327 static unsigned debug_index; 328 329 code = newcode = getbits(self, state->bits); 330 if (code < 0) 331 return (code); 332 333 debug_buff[debug_index++] = code; 334 if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0])) 335 debug_index = 0; 336 337 /* If it's a reset code, reset the dictionary. */ 338 if ((code == 256) && state->use_reset_code) { 339 /* 340 * The original 'compress' implementation blocked its 341 * I/O in a manner that resulted in junk bytes being 342 * inserted after every reset. The next section skips 343 * this junk. (Yes, the number of *bytes* to skip is 344 * a function of the current *bit* length.) 345 */ 346 int skip_bytes = state->bits - 347 (state->bytes_in_section % state->bits); 348 skip_bytes %= state->bits; 349 state->bits_avail = 0; /* Discard rest of this byte. */ 350 while (skip_bytes-- > 0) { 351 code = getbits(self, 8); 352 if (code < 0) 353 return (code); 354 } 355 /* Now, actually do the reset. */ 356 state->bytes_in_section = 0; 357 state->bits = 9; 358 state->section_end_code = (1 << state->bits) - 1; 359 state->free_ent = 257; 360 state->oldcode = -1; 361 return (next_code(self)); 362 } 363 364 if (code > state->free_ent) { 365 /* An invalid code is a fatal error. */ 366 archive_set_error(&(self->archive->archive), -1, 367 "Invalid compressed data"); 368 return (ARCHIVE_FATAL); 369 } 370 371 /* Special case for KwKwK string. */ 372 if (code >= state->free_ent) { 373 *state->stackp++ = state->finbyte; 374 code = state->oldcode; 375 } 376 377 /* Generate output characters in reverse order. */ 378 while (code >= 256) { 379 *state->stackp++ = state->suffix[code]; 380 code = state->prefix[code]; 381 } 382 *state->stackp++ = state->finbyte = code; 383 384 /* Generate the new entry. */ 385 code = state->free_ent; 386 if (code < state->maxcode && state->oldcode >= 0) { 387 state->prefix[code] = state->oldcode; 388 state->suffix[code] = state->finbyte; 389 ++state->free_ent; 390 } 391 if (state->free_ent > state->section_end_code) { 392 state->bits++; 393 state->bytes_in_section = 0; 394 if (state->bits == state->maxcode_bits) 395 state->section_end_code = state->maxcode; 396 else 397 state->section_end_code = (1 << state->bits) - 1; 398 } 399 400 /* Remember previous code. */ 401 state->oldcode = newcode; 402 return (ARCHIVE_OK); 403} 404 405/* 406 * Return next 'n' bits from stream. 407 * 408 * -1 indicates end of available data. 409 */ 410static int 411getbits(struct archive_read_filter *self, int n) 412{ 413 struct private_data *state = (struct private_data *)self->data; 414 int code; 415 ssize_t ret; 416 static const int mask[] = { 417 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff, 418 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff 419 }; 420 421 while (state->bits_avail < n) { 422 if (state->avail_in <= 0) { 423 state->next_in 424 = __archive_read_filter_ahead(self->upstream, 425 1, &ret); 426 if (ret == 0) 427 return (-1); 428 if (ret < 0 || state->next_in == NULL) 429 return (ARCHIVE_FATAL); 430 state->avail_in = ret; 431 __archive_read_filter_consume(self->upstream, ret); 432 } 433 state->bit_buffer |= *state->next_in++ << state->bits_avail; 434 state->avail_in--; 435 state->bits_avail += 8; 436 state->bytes_in_section++; 437 } 438 439 code = state->bit_buffer; 440 state->bit_buffer >>= n; 441 state->bits_avail -= n; 442 443 return (code & mask[n]); 444} 445