LXR busybox/archival/libarchive/decompress

   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
  75IF_DESKTOP(long long) int FAST_FUNC
  76unpack_Z_stream(transformer_state_t *xstate)
  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(xstate, 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(xstate->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(xstate->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/*
 232                                        unsigned char *p;
 233
 234                                        posbits -= n_bits;
 235                                        p = &inbuf[posbits >> 3];
 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*/
 241                                        bb_error_msg("corrupted data");
 242                                        goto err;
 243                                }
 244
 245                                *--stackp = (unsigned char) finchar;
 246                                code = oldcode;
 247                        }
 248
 249                        /* Generate output characters in reverse order */
 250                        while (code >= 256) {
 251                                if (stackp <= &htabof(0))
 252                                        bb_error_msg_and_die("corrupted data");
 253                                *--stackp = tab_suffixof(code);
 254                                code = tab_prefixof(code);
 255                        }
 256
 257                        finchar = tab_suffixof(code);
 258                        *--stackp = (unsigned char) finchar;
 259
 260                        /* And put them out in forward order */
 261                        {
 262                                int i;
 263
 264                                i = de_stack - stackp;
 265                                if (outpos + i >= OBUFSIZ) {
 266                                        do {
 267                                                if (i > OBUFSIZ - outpos) {
 268                                                        i = OBUFSIZ - outpos;
 269                                                }
 270
 271                                                if (i > 0) {
 272                                                        memcpy(outbuf + outpos, stackp, i);
 273                                                        outpos += i;
 274                                                }
 275
 276                                                if (outpos >= OBUFSIZ) {
 277                                                        xtransformer_write(xstate, outbuf, outpos);
 278                                                        IF_DESKTOP(total_written += outpos;)
 279                                                        outpos = 0;
 280                                                }
 281                                                stackp += i;
 282                                                i = de_stack - stackp;
 283                                        } while (i > 0);
 284                                } else {
 285                                        memcpy(outbuf + outpos, stackp, i);
 286                                        outpos += i;
 287                                }
 288                        }
 289
 290                        /* Generate the new entry. */
 291                        if (free_ent < maxmaxcode) {
 292                                tab_prefixof(free_ent) = (unsigned short) oldcode;
 293                                tab_suffixof(free_ent) = (unsigned char) finchar;
 294                                free_ent++;
 295                        }
 296
 297                        /* Remember previous code.  */
 298                        oldcode = incode;
 299                }
 300
 301        } while (rsize > 0);
 302
 303        if (outpos > 0) {
 304                xtransformer_write(xstate, outbuf, outpos);
 305                IF_DESKTOP(total_written += outpos;)
 306        }
 307
 308        retval = IF_DESKTOP(total_written) + 0;
 309 err:
 310        free(inbuf);
 311        free(outbuf);
 312        free(htab);
 313        free(codetab);
 314        return retval;
 315}
 316