archival/libunarchive/decompress_uncompress.c

   1 /* vi: set sw=4 ts=4: */
   2 #include "libbb.h"
   3
   4 /* uncompress for busybox -- (c) 2002 Robert Griebl
   5  *
   6  * based on the original compress42.c source
   7  * (see disclaimer below)
   8  */
   9
  10
  11 /* (N)compress42.c - File compression ala IEEE Computer, Mar 1992.
  12  *
  13  * Authors:
  14  *   Spencer W. Thomas   (decvax!harpo!utah-cs!utah-gr!thomas)
  15  *   Jim McKie           (decvax!mcvax!jim)
  16  *   Steve Davies        (decvax!vax135!petsd!peora!srd)
  17  *   Ken Turkowski       (decvax!decwrl!turtlevax!ken)
  18  *   James A. Woods      (decvax!ihnp4!ames!jaw)
  19  *   Joe Orost           (decvax!vax135!petsd!joe)
  20  *   Dave Mack           (csu@alembic.acs.com)
  21  *   Peter Jannesen, Network Communication Systems
  22  *                       (peter@ncs.nl)
  23  *
  24  * marc@suse.de : a small security fix for a buffer overflow
  25  *
  26  * [... History snipped ...]
  27  *
  28  */
  29 #include <stdio.h>
  30 #include <string.h>
  31 #include <unistd.h>
  32
  33 /* Default input buffer size */
  34 #define IBUFSIZ 2048
  35
  36 /* Default output buffer size */
  37 #define OBUFSIZ 2048
  38
  39 /* Defines for third byte of header */
  40 #define MAGIC_1         (char_type)'\037'       /* First byte of compressed file               */
  41 #define MAGIC_2         (char_type)'\235'       /* Second byte of compressed file              */
  42 #define BIT_MASK        0x1f    /* Mask for 'number of compresssion bits'       */
  43                                                         /* Masks 0x20 and 0x40 are free.                */
  44                                                         /* I think 0x20 should mean that there is       */
  45                                                         /* a fourth header byte (for expansion).        */
  46 #define BLOCK_MODE      0x80    /* Block compresssion if table is full and      */
  47                         /* compression rate is dropping flush tables    */
  48                         /* the next two codes should not be changed lightly, as they must not   */
  49                         /* lie within the contiguous general code space.                        */
  50 #define FIRST   257             /* first free entry                             */
  51 #define CLEAR   256             /* table clear output code                      */
  52
  53 #define INIT_BITS 9             /* initial number of bits/code */
  54
  55
  56 /* machine variants which require cc -Dmachine:  pdp11, z8000, DOS */
  57 #define FAST
  58
  59 #define HBITS           17      /* 50% occupancy */
  60 #define HSIZE      (1<<HBITS)
  61 #define HMASK      (HSIZE-1)
  62 #define HPRIME           9941
  63 #define BITS               16
  64 #undef  MAXSEG_64K
  65 #define MAXCODE(n)      (1L << (n))
  66
  67 /* Block compress mode -C compatible with 2.0 */
  68 static int block_mode = BLOCK_MODE;
  69
  70 /* user settable max # bits/code */
  71 static int maxbits = BITS;
  72
  73 /* Input buffer */
  74 static unsigned char inbuf[IBUFSIZ + 64];
  75
  76 /* Output buffer */
  77 static unsigned char outbuf[OBUFSIZ + 2048];
  78
  79
  80 static unsigned char htab[HSIZE];
  81 static unsigned short codetab[HSIZE];
  82
  83 #define htabof(i)                               htab[i]
  84 #define codetabof(i)                    codetab[i]
  85 #define tab_prefixof(i)                 codetabof(i)
  86 #define tab_suffixof(i)                 ((unsigned char *)(htab))[i]
  87 #define de_stack                                ((unsigned char *)&(htab[HSIZE-1]))
  88 #define clear_htab()                    memset(htab, -1, sizeof(htab))
  89 #define clear_tab_prefixof()    memset(codetab, 0, 256);
  90
  91
  92 /*
  93  * Decompress stdin to stdout.  This routine adapts to the codes in the
  94  * file building the "string" table on-the-fly; requiring no table to
  95  * be stored in the compressed file.  The tables used herein are shared
  96  * with those of the compress() routine.  See the definitions above.
  97  */
  98
  99 int uncompress(int fd_in, int fd_out)
 100 {
 101         unsigned char *stackp;
 102         long int code;
 103         int finchar;
 104         long int oldcode;
 105         long int incode;
 106         int inbits;
 107         int posbits;
 108         int outpos;
 109         int insize;
 110         int bitmask;
 111         long int free_ent;
 112         long int maxcode;
 113         long int maxmaxcode;
 114         int n_bits;
 115         int rsize = 0;
 116
 117         insize = 0;
 118
 119         inbuf[0] = xread_char(fd_in);
 120
 121         maxbits = inbuf[0] & BIT_MASK;
 122         block_mode = inbuf[0] & BLOCK_MODE;
 123         maxmaxcode = MAXCODE(maxbits);
 124
 125         if (maxbits > BITS) {
 126                 bb_error_msg("compressed with %d bits, can only handle %d bits", maxbits,
 127                                   BITS);
 128                 return -1;
 129         }
 130
 131         maxcode = MAXCODE(n_bits = INIT_BITS) - 1;
 132         bitmask = (1 << n_bits) - 1;
 133         oldcode = -1;
 134         finchar = 0;
 135         outpos = 0;
 136         posbits = 0 << 3;
 137
 138         free_ent = ((block_mode) ? FIRST : 256);
 139
 140         /* As above, initialize the first 256 entries in the table. */
 141         clear_tab_prefixof();
 142
 143         for (code = 255; code >= 0; --code) {
 144                 tab_suffixof(code) = (unsigned char) code;
 145         }
 146
 147         do {
 148           resetbuf:;
 149                 {
 150                         int i;
 151                         int e;
 152                         int o;
 153
 154                         e = insize - (o = (posbits >> 3));
 155
 156                         for (i = 0; i < e; ++i)
 157                                 inbuf[i] = inbuf[i + o];
 158
 159                         insize = e;
 160                         posbits = 0;
 161                 }
 162
 163                 if (insize < (int) sizeof(inbuf) - IBUFSIZ) {
 164                         rsize = safe_read(fd_in, inbuf + insize, IBUFSIZ);
 165                         insize += rsize;
 166                 }
 167
 168                 inbits = ((rsize > 0) ? (insize - insize % n_bits) << 3 :
 169                                   (insize << 3) - (n_bits - 1));
 170
 171                 while (inbits > posbits) {
 172                         if (free_ent > maxcode) {
 173                                 posbits =
 174                                         ((posbits - 1) +
 175                                          ((n_bits << 3) -
 176                                           (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
 177                                 ++n_bits;
 178                                 if (n_bits == maxbits) {
 179                                         maxcode = maxmaxcode;
 180                                 } else {
 181                                         maxcode = MAXCODE(n_bits) - 1;
 182                                 }
 183                                 bitmask = (1 << n_bits) - 1;
 184                                 goto resetbuf;
 185                         }
 186                         {
 187                                 unsigned char *p = &inbuf[posbits >> 3];
 188
 189                                 code =
 190                                         ((((long) (p[0])) | ((long) (p[1]) << 8) |
 191                                           ((long) (p[2]) << 16)) >> (posbits & 0x7)) & bitmask;
 192                         }
 193                         posbits += n_bits;
 194
 195
 196                         if (oldcode == -1) {
 197                                 outbuf[outpos++] = (unsigned char) (finchar =
 198                                                                                                 (int) (oldcode = code));
 199                                 continue;
 200                         }
 201
 202                         if (code == CLEAR && block_mode) {
 203                                 clear_tab_prefixof();
 204                                 free_ent = FIRST - 1;
 205                                 posbits =
 206                                         ((posbits - 1) +
 207                                          ((n_bits << 3) -
 208                                           (posbits - 1 + (n_bits << 3)) % (n_bits << 3)));
 209                                 maxcode = MAXCODE(n_bits = INIT_BITS) - 1;
 210                                 bitmask = (1 << n_bits) - 1;
 211                                 goto resetbuf;
 212                         }
 213
 214                         incode = code;
 215                         stackp = de_stack;
 216
 217                         /* Special case for KwKwK string. */
 218                         if (code >= free_ent) {
 219                                 if (code > free_ent) {
 220                                         unsigned char *p;
 221
 222                                         posbits -= n_bits;
 223                                         p = &inbuf[posbits >> 3];
 224
 225                                         bb_error_msg
 226                                                 ("insize:%d posbits:%d inbuf:%02X %02X %02X %02X %02X (%d)",
 227                                                  insize, posbits, p[-1], p[0], p[1], p[2], p[3],
 228                                                  (posbits & 07));
 229                                         bb_error_msg("uncompress: corrupt input");
 230                                         return -1;
 231                                 }
 232
 233                                 *--stackp = (unsigned char) finchar;
 234                                 code = oldcode;
 235                         }
 236
 237                         /* Generate output characters in reverse order */
 238                         while ((long int) code >= (long int) 256) {
 239                                 *--stackp = tab_suffixof(code);
 240                                 code = tab_prefixof(code);
 241                         }
 242
 243                         *--stackp = (unsigned char) (finchar = tab_suffixof(code));
 244
 245                         /* And put them out in forward order */
 246                         {
 247                                 int i;
 248
 249                                 if (outpos + (i = (de_stack - stackp)) >= OBUFSIZ) {
 250                                         do {
 251                                                 if (i > OBUFSIZ - outpos) {
 252                                                         i = OBUFSIZ - outpos;
 253                                                 }
 254
 255                                                 if (i > 0) {
 256                                                         memcpy(outbuf + outpos, stackp, i);
 257                                                         outpos += i;
 258                                                 }
 259
 260                                                 if (outpos >= OBUFSIZ) {
 261                                                         write(fd_out, outbuf, outpos);
 262                                                         outpos = 0;
 263                                                 }
 264                                                 stackp += i;
 265                                         } while ((i = (de_stack - stackp)) > 0);
 266                                 } else {
 267                                         memcpy(outbuf + outpos, stackp, i);
 268                                         outpos += i;
 269                                 }
 270                         }
 271
 272                         /* Generate the new entry. */
 273                         if ((code = free_ent) < maxmaxcode) {
 274                                 tab_prefixof(code) = (unsigned short) oldcode;
 275                                 tab_suffixof(code) = (unsigned char) finchar;
 276                                 free_ent = code + 1;
 277                         }
 278
 279                         /* Remember previous code.  */
 280                         oldcode = incode;
 281                 }
 282
 283         } while (rsize > 0);
 284
 285         if (outpos > 0) {
 286                 write(fd_out, outbuf, outpos);
 287         }
 288
 289         return 0;
 290 }