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