libbb/uncompress.c

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