archival/libarchive/decompress_uncompress.c

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