usr.bin/gzip/zuncompress.c

   1 /*      $NetBSD: zuncompress.c,v 1.11 2011/08/16 13:55:02 joerg Exp $ */
   2 /*      $DragonFly: src/usr.bin/gzip/zuncompress.c,v 1.1 2004/10/26 11:19:31 joerg Exp $ */
   3
   4 /*-
   5  * Copyright (c) 1985, 1986, 1992, 1993
   6  *      The Regents of the University of California.  All rights reserved.
   7  *
   8  * This code is derived from software contributed to Berkeley by
   9  * Diomidis Spinellis and James A. Woods, derived from original
  10  * work by Spencer Thomas and Joseph Orost.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  * 3. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  * from: NetBSD: zopen.c,v 1.8 2003/08/07 11:13:29 agc Exp
  37  */
  38
  39 /* This file is #included by gzip.c */
  40
  41 static int      zread(void *, char *, int);
  42
  43 #define tab_prefixof(i) (zs->zs_codetab[i])
  44 #define tab_suffixof(i) ((char_type *)(zs->zs_htab))[i]
  45 #define de_stack        ((char_type *)&tab_suffixof(1 << BITS))
  46
  47 #define BITS            16              /* Default bits. */
  48 #define HSIZE           69001           /* 95% occupancy */ /* XXX may not need HSIZE */
  49 #define BIT_MASK        0x1f            /* Defines for third byte of header. */
  50 #define BLOCK_MASK      0x80
  51 #define CHECK_GAP       10000           /* Ratio check interval. */
  52 #define BUFSIZE         (64 * 1024)
  53
  54 /*
  55  * Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  56  * a fourth header byte (for expansion).
  57  */
  58 #define INIT_BITS       9       /* Initial number of bits/code. */
  59
  60 /*
  61  * the next two codes should not be changed lightly, as they must not
  62  * lie within the contiguous general code space.
  63  */
  64 #define FIRST   257             /* First free entry. */
  65 #define CLEAR   256             /* Table clear output code. */
  66
  67
  68 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
  69
  70 typedef long    code_int;
  71 typedef long    count_int;
  72 typedef u_char  char_type;
  73
  74 static char_type magic_header[] =
  75         {'\037', '\235'};       /* 1F 9D */
  76
  77 static char_type rmask[9] =
  78         {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  79
  80 /* XXX zuncompress global */
  81 off_t total_compressed_bytes;
  82 size_t compressed_prelen;
  83 char *compressed_pre;
  84
  85 struct s_zstate {
  86         FILE *zs_fp;                    /* File stream for I/O */
  87         char zs_mode;                   /* r or w */
  88         enum {
  89                 S_START, S_MIDDLE, S_EOF
  90         } zs_state;                     /* State of computation */
  91         int zs_n_bits;                  /* Number of bits/code. */
  92         int zs_maxbits;                 /* User settable max # bits/code. */
  93         code_int zs_maxcode;            /* Maximum code, given n_bits. */
  94         code_int zs_maxmaxcode;         /* Should NEVER generate this code. */
  95         count_int zs_htab [HSIZE];
  96         u_short zs_codetab [HSIZE];
  97         code_int zs_hsize;              /* For dynamic table sizing. */
  98         code_int zs_free_ent;           /* First unused entry. */
  99         /*
 100          * Block compression parameters -- after all codes are used up,
 101          * and compression rate changes, start over.
 102          */
 103         int zs_block_compress;
 104         int zs_clear_flg;
 105         long zs_ratio;
 106         count_int zs_checkpoint;
 107         int zs_offset;
 108         long zs_in_count;               /* Length of input. */
 109         long zs_bytes_out;              /* Length of compressed output. */
 110         long zs_out_count;              /* # of codes output (for debugging). */
 111         char_type zs_buf[BITS];
 112         union {
 113                 struct {
 114                         long zs_fcode;
 115                         code_int zs_ent;
 116                         code_int zs_hsize_reg;
 117                         int zs_hshift;
 118                 } w;                    /* Write paramenters */
 119                 struct {
 120                         char_type *zs_stackp;
 121                         int zs_finchar;
 122                         code_int zs_code, zs_oldcode, zs_incode;
 123                         int zs_roffset, zs_size;
 124                         char_type zs_gbuf[BITS];
 125                 } r;                    /* Read parameters */
 126         } u;
 127 };
 128
 129 static code_int getcode(struct s_zstate *zs);
 130
 131 static off_t
 132 zuncompress(FILE *in, FILE *out, char *pre, size_t prelen,
 133             off_t *compressed_bytes)
 134 {
 135         off_t bin, bout = 0;
 136         char *buf;
 137
 138         buf = malloc(BUFSIZE);
 139         if (buf == NULL)
 140                 return -1;
 141
 142         /* XXX */
 143         compressed_prelen = prelen;
 144         if (prelen != 0)
 145                 compressed_pre = pre;
 146         else
 147                 compressed_pre = NULL;
 148
 149         while ((bin = fread(buf, 1, sizeof(buf), in)) != 0) {
 150                 if (tflag == 0 && (off_t)fwrite(buf, 1, bin, out) != bin) {
 151                         free(buf);
 152                         return -1;
 153                 }
 154                 bout += bin;
 155         }
 156
 157         if (compressed_bytes)
 158                 *compressed_bytes = total_compressed_bytes;
 159
 160         free(buf);
 161         return bout;
 162 }
 163
 164 static int
 165 zclose(void *zs)
 166 {
 167         free(zs);
 168         /* We leave the caller to close the fd passed to zdopen() */
 169         return 0;
 170 }
 171
 172 FILE *
 173 zdopen(int fd)
 174 {
 175         struct s_zstate *zs;
 176
 177         if ((zs = calloc(1, sizeof(struct s_zstate))) == NULL)
 178                 return (NULL);
 179
 180         zs->zs_state = S_START;
 181
 182         /* XXX we can get rid of some of these */
 183         zs->zs_hsize = HSIZE;                   /* For dynamic table sizing. */
 184         zs->zs_free_ent = 0;                    /* First unused entry. */
 185         zs->zs_block_compress = BLOCK_MASK;
 186         zs->zs_clear_flg = 0;                   /* XXX we calloc()'d this structure why = 0? */
 187         zs->zs_ratio = 0;
 188         zs->zs_checkpoint = CHECK_GAP;
 189         zs->zs_in_count = 1;                    /* Length of input. */
 190         zs->zs_out_count = 0;                   /* # of codes output (for debugging). */
 191         zs->u.r.zs_roffset = 0;
 192         zs->u.r.zs_size = 0;
 193
 194         /*
 195          * Layering compress on top of stdio in order to provide buffering,
 196          * and ensure that reads and write work with the data specified.
 197          */
 198         if ((zs->zs_fp = fdopen(fd, "r")) == NULL) {
 199                 free(zs);
 200                 return NULL;
 201         }
 202
 203         return funopen(zs, zread, NULL, NULL, zclose);
 204 }
 205
 206 /*
 207  * Decompress read.  This routine adapts to the codes in the file building
 208  * the "string" table on-the-fly; requiring no table to be stored in the
 209  * compressed file.  The tables used herein are shared with those of the
 210  * compress() routine.  See the definitions above.
 211  */
 212 static int
 213 zread(void *cookie, char *rbp, int num)
 214 {
 215         u_int count, i;
 216         struct s_zstate *zs;
 217         u_char *bp, header[3];
 218
 219         if (num == 0)
 220                 return (0);
 221
 222         zs = cookie;
 223         count = num;
 224         bp = (u_char *)rbp;
 225         switch (zs->zs_state) {
 226         case S_START:
 227                 zs->zs_state = S_MIDDLE;
 228                 break;
 229         case S_MIDDLE:
 230                 goto middle;
 231         case S_EOF:
 232                 goto eof;
 233         }
 234
 235         /* Check the magic number */
 236         for (i = 0; i < 3 && compressed_prelen; i++, compressed_prelen--)
 237                 header[i] = *compressed_pre++;
 238
 239         if (fread(header + i, 1, sizeof(header) - i, zs->zs_fp) !=
 240                   sizeof(header) - i ||
 241             memcmp(header, magic_header, sizeof(magic_header)) != 0) {
 242                 errno = EFTYPE;
 243                 return (-1);
 244         }
 245         total_compressed_bytes = 0;
 246         zs->zs_maxbits = header[2];     /* Set -b from file. */
 247         zs->zs_block_compress = zs->zs_maxbits & BLOCK_MASK;
 248         zs->zs_maxbits &= BIT_MASK;
 249         zs->zs_maxmaxcode = 1L << zs->zs_maxbits;
 250         if (zs->zs_maxbits > BITS || zs->zs_maxbits < 12) {
 251                 errno = EFTYPE;
 252                 return (-1);
 253         }
 254         /* As above, initialize the first 256 entries in the table. */
 255         zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS);
 256         for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0; zs->u.r.zs_code--) {
 257                 tab_prefixof(zs->u.r.zs_code) = 0;
 258                 tab_suffixof(zs->u.r.zs_code) = (char_type) zs->u.r.zs_code;
 259         }
 260         zs->zs_free_ent = zs->zs_block_compress ? FIRST : 256;
 261         zs->u.r.zs_oldcode = -1;
 262         zs->u.r.zs_stackp = de_stack;
 263
 264         while ((zs->u.r.zs_code = getcode(zs)) > -1) {
 265
 266                 if ((zs->u.r.zs_code == CLEAR) && zs->zs_block_compress) {
 267                         for (zs->u.r.zs_code = 255; zs->u.r.zs_code >= 0;
 268                             zs->u.r.zs_code--)
 269                                 tab_prefixof(zs->u.r.zs_code) = 0;
 270                         zs->zs_clear_flg = 1;
 271                         zs->zs_free_ent = FIRST;
 272                         zs->u.r.zs_oldcode = -1;
 273                         continue;
 274 }
 275                 zs->u.r.zs_incode = zs->u.r.zs_code;
 276
 277                 /* Special case for KwKwK string. */
 278                 if (zs->u.r.zs_code >= zs->zs_free_ent) {
 279                         if (zs->u.r.zs_code > zs->zs_free_ent ||
 280                             zs->u.r.zs_oldcode == -1) {
 281                                 /* Bad stream. */
 282                                 errno = EINVAL;
 283                                 return (-1);
 284                         }
 285                         *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar;
 286                         zs->u.r.zs_code = zs->u.r.zs_oldcode;
 287                 }
 288                 /*
 289                  * The above condition ensures that code < free_ent.
 290                  * The construction of tab_prefixof in turn guarantees that
 291                  * each iteration decreases code and therefore stack usage is
 292                  * bound by 1 << BITS - 256.
 293                  */
 294
 295                 /* Generate output characters in reverse order. */
 296                 while (zs->u.r.zs_code >= 256) {
 297                         *zs->u.r.zs_stackp++ = tab_suffixof(zs->u.r.zs_code);
 298                         zs->u.r.zs_code = tab_prefixof(zs->u.r.zs_code);
 299                 }
 300                 *zs->u.r.zs_stackp++ = zs->u.r.zs_finchar = tab_suffixof(zs->u.r.zs_code);
 301
 302                 /* And put them out in forward order.  */
 303 middle:         do {
 304                         if (count-- == 0)
 305                                 return (num);
 306                         *bp++ = *--zs->u.r.zs_stackp;
 307                 } while (zs->u.r.zs_stackp > de_stack);
 308
 309                 /* Generate the new entry. */
 310                 if ((zs->u.r.zs_code = zs->zs_free_ent) < zs->zs_maxmaxcode &&
 311                     zs->u.r.zs_oldcode != -1) {
 312                         tab_prefixof(zs->u.r.zs_code) = (u_short) zs->u.r.zs_oldcode;
 313                         tab_suffixof(zs->u.r.zs_code) = zs->u.r.zs_finchar;
 314                         zs->zs_free_ent = zs->u.r.zs_code + 1;
 315                 }
 316
 317                 /* Remember previous code. */
 318                 zs->u.r.zs_oldcode = zs->u.r.zs_incode;
 319         }
 320         zs->zs_state = S_EOF;
 321 eof:    return (num - count);
 322 }
 323
 324 /*-
 325  * Read one code from the standard input.  If EOF, return -1.
 326  * Inputs:
 327  *      stdin
 328  * Outputs:
 329  *      code or -1 is returned.
 330  */
 331 static code_int
 332 getcode(struct s_zstate *zs)
 333 {
 334         code_int gcode;
 335         int r_off, bits, i;
 336         char_type *bp;
 337
 338         bp = zs->u.r.zs_gbuf;
 339         if (zs->zs_clear_flg > 0 || zs->u.r.zs_roffset >= zs->u.r.zs_size ||
 340             zs->zs_free_ent > zs->zs_maxcode) {
 341                 /*
 342                  * If the next entry will be too big for the current gcode
 343                  * size, then we must increase the size.  This implies reading
 344                  * a new buffer full, too.
 345                  */
 346                 if (zs->zs_free_ent > zs->zs_maxcode) {
 347                         zs->zs_n_bits++;
 348                         if (zs->zs_n_bits == zs->zs_maxbits)    /* Won't get any bigger now. */
 349                                 zs->zs_maxcode = zs->zs_maxmaxcode;
 350                         else
 351                                 zs->zs_maxcode = MAXCODE(zs->zs_n_bits);
 352                 }
 353                 if (zs->zs_clear_flg > 0) {
 354                         zs->zs_maxcode = MAXCODE(zs->zs_n_bits = INIT_BITS);
 355                         zs->zs_clear_flg = 0;
 356                 }
 357                 /* XXX */
 358                 for (i = 0; i < zs->zs_n_bits && compressed_prelen; i++, compressed_prelen--)
 359                         zs->u.r.zs_gbuf[i] = *compressed_pre++;
 360                 zs->u.r.zs_size = fread(zs->u.r.zs_gbuf + i, 1, zs->zs_n_bits - i, zs->zs_fp);
 361                 zs->u.r.zs_size += i;
 362                 if (zs->u.r.zs_size <= 0)                       /* End of file. */
 363                         return (-1);
 364                 zs->u.r.zs_roffset = 0;
 365
 366                 total_compressed_bytes += zs->u.r.zs_size;
 367
 368                 /* Round size down to integral number of codes. */
 369                 zs->u.r.zs_size = (zs->u.r.zs_size << 3) - (zs->zs_n_bits - 1);
 370         }
 371         r_off = zs->u.r.zs_roffset;
 372         bits = zs->zs_n_bits;
 373
 374         /* Get to the first byte. */
 375         bp += (r_off >> 3);
 376         r_off &= 7;
 377
 378         /* Get first part (low order bits). */
 379         gcode = (*bp++ >> r_off);
 380         bits -= (8 - r_off);
 381         r_off = 8 - r_off;      /* Now, roffset into gcode word. */
 382
 383         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
 384         if (bits >= 8) {
 385                 gcode |= *bp++ << r_off;
 386                 r_off += 8;
 387                 bits -= 8;
 388         }
 389
 390         /* High order bits. */
 391         gcode |= (*bp & rmask[bits]) << r_off;
 392         zs->u.r.zs_roffset += zs->zs_n_bits;
 393
 394         return (gcode);
 395 }