lib/libarchive/archive_read_support_compression_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         int                      bit_buffer;
  99         int                      bits_avail;
 100         size_t                   bytes_in_section;
 101
 102         /* Output variables. */
 103         size_t                   out_block_size;
 104         void                    *out_block;
 105
 106         /* Decompression status variables. */
 107         int                      use_reset_code;
 108         int                      end_of_stream; /* EOF status. */
 109         int                      maxcode;       /* Largest code. */
 110         int                      maxcode_bits;  /* Length of largest code. */
 111         int                      section_end_code; /* When to increase bits. */
 112         int                      bits;          /* Current code length. */
 113         int                      oldcode;       /* Previous code. */
 114         int                      finbyte;       /* Last byte of prev code. */
 115
 116         /* Dictionary. */
 117         int                      free_ent;       /* Next dictionary entry. */
 118         unsigned char            suffix[65536];
 119         uint16_t                 prefix[65536];
 120
 121         /*
 122          * Scratch area for expanding dictionary entries.  Note:
 123          * "worst" case here comes from compressing /dev/zero: the
 124          * last code in the dictionary will code a sequence of
 125          * 65536-256 zero bytes.  Thus, we need stack space to expand
 126          * a 65280-byte dictionary entry.  (Of course, 32640:1
 127          * compression could also be considered the "best" case. ;-)
 128          */
 129         unsigned char           *stackp;
 130         unsigned char            stack[65300];
 131 };
 132
 133 static int      compress_reader_bid(struct archive_reader *, const void *, size_t);
 134 static struct archive_read_source *compress_reader_init(struct archive_read *,
 135     struct archive_reader *, struct archive_read_source *,
 136     const void *, size_t);
 137 static int      compress_reader_free(struct archive_reader *);
 138
 139 static ssize_t  compress_source_read(struct archive_read_source *, const void **);
 140 static int      compress_source_close(struct archive_read_source *);
 141
 142 static int      getbits(struct archive_read_source *, int n);
 143 static int      next_code(struct archive_read_source *);
 144
 145 int
 146 archive_read_support_compression_compress(struct archive *_a)
 147 {
 148         struct archive_read *a = (struct archive_read *)_a;
 149         struct archive_reader *reader = __archive_read_get_reader(a);
 150
 151         if (reader == NULL)
 152                 return (ARCHIVE_FATAL);
 153
 154         reader->data = NULL;
 155         reader->bid = compress_reader_bid;
 156         reader->init = compress_reader_init;
 157         reader->free = compress_reader_free;
 158         return (ARCHIVE_OK);
 159 }
 160
 161 /*
 162  * Test whether we can handle this data.
 163  *
 164  * This logic returns zero if any part of the signature fails.  It
 165  * also tries to Do The Right Thing if a very short buffer prevents us
 166  * from verifying as much as we would like.
 167  */
 168 static int
 169 compress_reader_bid(struct archive_reader *self, const void *buff, size_t len)
 170 {
 171         const unsigned char *buffer;
 172         int bits_checked;
 173
 174         (void)self; /* UNUSED */
 175
 176         if (len < 1)
 177                 return (0);
 178
 179         buffer = (const unsigned char *)buff;
 180         bits_checked = 0;
 181         if (buffer[0] != 037)   /* Verify first ID byte. */
 182                 return (0);
 183         bits_checked += 8;
 184         if (len < 2)
 185                 return (bits_checked);
 186
 187         if (buffer[1] != 0235)  /* Verify second ID byte. */
 188                 return (0);
 189         bits_checked += 8;
 190         if (len < 3)
 191                 return (bits_checked);
 192
 193         /*
 194          * TODO: Verify more.
 195          */
 196
 197         return (bits_checked);
 198 }
 199
 200 /*
 201  * Setup the callbacks.
 202  */
 203 static struct archive_read_source *
 204 compress_reader_init(struct archive_read *a, struct archive_reader *reader,
 205     struct archive_read_source *upstream, const void *buff, size_t n)
 206 {
 207         struct archive_read_source *self;
 208         struct private_data *state;
 209         int code;
 210
 211         (void)reader; /* UNUSED */
 212
 213         a->archive.compression_code = ARCHIVE_COMPRESSION_COMPRESS;
 214         a->archive.compression_name = "compress (.Z)";
 215
 216         self = calloc(sizeof(*self), 1);
 217         if (self == NULL)
 218                 return (NULL);
 219
 220         self->read = compress_source_read;
 221         self->skip = NULL; /* not supported */
 222         self->close = compress_source_close;
 223         self->upstream = upstream;
 224         self->archive = a;
 225
 226         state = (struct private_data *)calloc(sizeof(*state), 1);
 227         if (state == NULL) {
 228                 archive_set_error(&a->archive, ENOMEM,
 229                     "Can't allocate data for %s decompression",
 230                     a->archive.compression_name);
 231                 free(self);
 232                 return (NULL);
 233         }
 234         self->data = state;
 235
 236         state->out_block_size = 64 * 1024;
 237         state->out_block = malloc(state->out_block_size);
 238
 239         if (state->out_block == NULL) {
 240                 archive_set_error(&a->archive, ENOMEM,
 241                     "Can't allocate %s decompression buffers",
 242                     a->archive.compression_name);
 243                 goto fatal;
 244         }
 245
 246         state->next_in = (const unsigned char *)buff;
 247         state->avail_in = n;
 248
 249         code = getbits(self, 8);
 250         if (code != 037) /* This should be impossible. */
 251                 goto fatal;
 252
 253         code = getbits(self, 8);
 254         if (code != 0235) {
 255                 /* This can happen if the library is receiving 1-byte
 256                  * blocks and gzip and compress are both enabled.
 257                  * You can't distinguish gzip and compress only from
 258                  * the first byte. */
 259                 archive_set_error(&a->archive, ARCHIVE_ERRNO_FILE_FORMAT,
 260                     "Compress signature did not match.");
 261                 goto fatal;
 262         }
 263
 264         code = getbits(self, 8);
 265         state->maxcode_bits = code & 0x1f;
 266         state->maxcode = (1 << state->maxcode_bits);
 267         state->use_reset_code = code & 0x80;
 268
 269         /* Initialize decompressor. */
 270         state->free_ent = 256;
 271         state->stackp = state->stack;
 272         if (state->use_reset_code)
 273                 state->free_ent++;
 274         state->bits = 9;
 275         state->section_end_code = (1<<state->bits) - 1;
 276         state->oldcode = -1;
 277         for (code = 255; code >= 0; code--) {
 278                 state->prefix[code] = 0;
 279                 state->suffix[code] = code;
 280         }
 281         next_code(self);
 282         return (self);
 283
 284 fatal:
 285         compress_source_close(self);
 286         return (NULL);
 287 }
 288
 289 /*
 290  * Return a block of data from the decompression buffer.  Decompress more
 291  * as necessary.
 292  */
 293 static ssize_t
 294 compress_source_read(struct archive_read_source *self, const void **pblock)
 295 {
 296         struct private_data *state;
 297         unsigned char *p, *start, *end;
 298         int ret;
 299
 300         state = (struct private_data *)self->data;
 301         if (state->end_of_stream) {
 302                 *pblock = NULL;
 303                 return (0);
 304         }
 305         p = start = (unsigned char *)state->out_block;
 306         end = start + state->out_block_size;
 307
 308         while (p < end && !state->end_of_stream) {
 309                 if (state->stackp > state->stack) {
 310                         *p++ = *--state->stackp;
 311                 } else {
 312                         ret = next_code(self);
 313                         if (ret == ARCHIVE_EOF)
 314                                 state->end_of_stream = ret;
 315                         else if (ret != ARCHIVE_OK)
 316                                 return (ret);
 317                 }
 318         }
 319
 320         *pblock = start;
 321         return (p - start);
 322 }
 323
 324 /*
 325  * Clean up the reader.
 326  */
 327 static int
 328 compress_reader_free(struct archive_reader *self)
 329 {
 330         self->data = NULL;
 331         return (ARCHIVE_OK);
 332 }
 333
 334 /*
 335  * Close and release a source.
 336  */
 337 static int
 338 compress_source_close(struct archive_read_source *self)
 339 {
 340         struct private_data *state = (struct private_data *)self->data;
 341
 342         self->upstream->close(self->upstream);
 343         free(state->out_block);
 344         free(state);
 345         free(self);
 346         return (ARCHIVE_OK);
 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_read_source *self)
 356 {
 357         struct private_data *state = (struct private_data *)self->data;
 358         int code, newcode;
 359
 360         static int debug_buff[1024];
 361         static unsigned debug_index;
 362
 363         code = newcode = getbits(self, state->bits);
 364         if (code < 0)
 365                 return (code);
 366
 367         debug_buff[debug_index++] = code;
 368         if (debug_index >= sizeof(debug_buff)/sizeof(debug_buff[0]))
 369                 debug_index = 0;
 370
 371         /* If it's a reset code, reset the dictionary. */
 372         if ((code == 256) && state->use_reset_code) {
 373                 /*
 374                  * The original 'compress' implementation blocked its
 375                  * I/O in a manner that resulted in junk bytes being
 376                  * inserted after every reset.  The next section skips
 377                  * this junk.  (Yes, the number of *bytes* to skip is
 378                  * a function of the current *bit* length.)
 379                  */
 380                 int skip_bytes =  state->bits -
 381                     (state->bytes_in_section % state->bits);
 382                 skip_bytes %= state->bits;
 383                 state->bits_avail = 0; /* Discard rest of this byte. */
 384                 while (skip_bytes-- > 0) {
 385                         code = getbits(self, 8);
 386                         if (code < 0)
 387                                 return (code);
 388                 }
 389                 /* Now, actually do the reset. */
 390                 state->bytes_in_section = 0;
 391                 state->bits = 9;
 392                 state->section_end_code = (1 << state->bits) - 1;
 393                 state->free_ent = 257;
 394                 state->oldcode = -1;
 395                 return (next_code(self));
 396         }
 397
 398         if (code > state->free_ent) {
 399                 /* An invalid code is a fatal error. */
 400                 archive_set_error(&(self->archive->archive), -1,
 401                     "Invalid compressed data");
 402                 return (ARCHIVE_FATAL);
 403         }
 404
 405         /* Special case for KwKwK string. */
 406         if (code >= state->free_ent) {
 407                 *state->stackp++ = state->finbyte;
 408                 code = state->oldcode;
 409         }
 410
 411         /* Generate output characters in reverse order. */
 412         while (code >= 256) {
 413                 *state->stackp++ = state->suffix[code];
 414                 code = state->prefix[code];
 415         }
 416         *state->stackp++ = state->finbyte = code;
 417
 418         /* Generate the new entry. */
 419         code = state->free_ent;
 420         if (code < state->maxcode && state->oldcode >= 0) {
 421                 state->prefix[code] = state->oldcode;
 422                 state->suffix[code] = state->finbyte;
 423                 ++state->free_ent;
 424         }
 425         if (state->free_ent > state->section_end_code) {
 426                 state->bits++;
 427                 state->bytes_in_section = 0;
 428                 if (state->bits == state->maxcode_bits)
 429                         state->section_end_code = state->maxcode;
 430                 else
 431                         state->section_end_code = (1 << state->bits) - 1;
 432         }
 433
 434         /* Remember previous code. */
 435         state->oldcode = newcode;
 436         return (ARCHIVE_OK);
 437 }
 438
 439 /*
 440  * Return next 'n' bits from stream.
 441  *
 442  * -1 indicates end of available data.
 443  */
 444 static int
 445 getbits(struct archive_read_source *self, int n)
 446 {
 447         struct private_data *state = (struct private_data *)self->data;
 448         int code, ret;
 449         static const int mask[] = {
 450                 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff,
 451                 0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff, 0x3fff, 0x7fff, 0xffff
 452         };
 453         const void *read_buf;
 454
 455         while (state->bits_avail < n) {
 456                 if (state->avail_in <= 0) {
 457                         read_buf = state->next_in;
 458                         ret = (self->upstream->read)(self->upstream, &read_buf);
 459                         state->next_in = read_buf;
 460                         if (ret < 0)
 461                                 return (ARCHIVE_FATAL);
 462                         if (ret == 0)
 463                                 return (ARCHIVE_EOF);
 464 /* TODO: Fix this                       a->archive.raw_position += ret; */
 465                         state->avail_in = ret;
 466                 }
 467                 state->bit_buffer |= *state->next_in++ << state->bits_avail;
 468                 state->avail_in--;
 469                 state->bits_avail += 8;
 470                 state->bytes_in_section++;
 471         }
 472
 473         code = state->bit_buffer;
 474         state->bit_buffer >>= n;
 475         state->bits_avail -= n;
 476
 477         return (code & mask[n]);
 478 }