contrib/libarchive/libarchive/archive_read_support_filter_compress.c

   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 }