compress.c

   1
   2 /*
   3  * compress/uncompress archive
   4  *
   5  * Authors:     Spencer W. Thomas       (decvax!utah-cs!thomas)
   6  *              Jim McKie               (decvax!mcvax!jim)
   7  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
   8  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
   9  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  10  *              Joe Orost               (decvax!vax135!petsd!joe)
  11  *
  12  * NOTE: these functions also support "squash" (which is just a
  13  * 13-bit compress), and "crunch" (which is a 12-bit compress
  14  * with additional run-length encoding).  AJD
  15  *
  16  * $Header: compress.c 1.11 95/08/01 $
  17  * $Log:        compress.c,v $
  18  * Revision 1.11 95/08/01  xx:xx:xx  BB
  19  * Quite a few changes for Borland C/C++
  20  * Made htab and codetab arrays dynamic.
  21  * (Compile with -DBB_HUGE_STATIC_ARRAYS if you DO want these
  22  * huge static arrays in your executable.)
  23  * Changed pointers to normalized or huge pointers because
  24  * arrays span more than 64k.
  25  * Changed a few types from int to long because 32bits integers
  26  * are needed.
  27  *
  28  * Revision 1.10 95/01/25  12:49:43  arb
  29  * Bug fixes caused by 1.9
  30  *
  31  * Revision 1.9  95/01/06  12:00:06  arb
  32  * Fixes for Alpha.
  33  *
  34  * Revision 1.8  94/02/28  23:57:55  arb
  35  * Fixed number of compression bits for ArcFS format archives
  36  *
  37  * Revision 1.7  93/08/20  11:35:20  arb
  38  * Prevent printing of "uncompressed" etc. if quiet flag is set
  39  *
  40  * Revision 1.6  92/12/07  17:17:28  duplain
  41  * reformatted source.
  42  *
  43  * Revision 1.5  92/11/09  14:48:00  duplain
  44  * Initialised offset and size from getcode() each time uncompress() called.
  45  *
  46  * Revision 1.4  92/11/02  11:43:14  duplain
  47  * Correct comment about crunch/squash in header.
  48  *
  49  * Revision 1.3  92/10/23  14:08:13  duplain
  50  * Minor changes to printf's at end of uncompress.
  51  *
  52  * Revision 1.2  92/10/01  11:20:19  duplain
  53  * Added check for EOF.
  54  *
  55  * Revision 1.1  92/09/29  18:02:14  duplain
  56  * Initial revision
  57  *
  58  */
  59
  60 #include <stdio.h>
  61 #include <stdlib.h>
  62 #include "spark.h"
  63 #include "pack.h"
  64 #include "main.h"
  65 #include "crc.h"
  66 #include "garble.h"
  67 #include "error.h"
  68
  69 /* BB changed next line because of conflict with Borland's io.h */
  70
  71 /* #include "io.h" */
  72 #include "nsparkio.h"
  73 #include "arcfs.h"
  74
  75 #ifdef __MSDOS__
  76 #include <alloc.h>                              /* for farcalloc() */
  77 #endif                                                  /* __MSDOS__ */
  78
  79 #define PBITS 16
  80 #define CRUNCHBITS 12
  81 #define SQUASHBITS 13
  82 #define COMPRESSBITS 16
  83
  84 /* BB changed constant in next line to long: 16bits 65536 == 0 ! */
  85 #define HSIZE 65536L
  86 #define INIT_BITS 9                             /* initial number of bits/code */
  87
  88 /* BB changed next macros.
  89  * Arrays htab and codetab both exceed 64k. To prevent wraparound
  90    at the 64k boundary, normalized or huge pointers have to be used.
  91    Since subscripts are 16 bit ints under the Borland compiler,
  92    subscripts have to be made explicitely long.
  93    And finally COMPRESSBITS == 16, but 1 << 16 == 0 for 16 bits
  94    integers! */
  95
  96 /* #define MAXCODE(n_bits)      ((1 << (n_bits)) - 1) */
  97
  98 /* #define htabof(i) htab[i] */
  99
 100 /* #define codetabof(i) codetab[i] */
 101
 102 /* #define tab_prefixof(i)      codetabof(i) */
 103
 104 /* #define tab_suffixof(i)      ((char_type *)(htab))[i] */
 105
 106 /* #define de_stack ((char_type *)&tab_suffixof(1<<COMPRESSBITS)) */
 107 #ifdef __MSDOS__
 108 #define MAXCODE(n_bits) ((long)(1L << (n_bits)) - 1L)
 109 #define htabof(i) htab[(long)(i)]
 110 #define codetabof(i) codetab[(long)(i)]
 111 #define tab_prefixof(i) codetabof(i)
 112 #define tab_suffixof(i) ((char_type huge *)(htab))[(long)(i)]
 113 #define de_stack \
 114           ((char_type huge *)&tab_suffixof(1L<<COMPRESSBITS))
 115 #else
 116 #define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
 117 #define htabof(i) htab[i]
 118 #define codetabof(i) codetab[i]
 119 #define tab_prefixof(i) codetabof(i)
 120 #define tab_suffixof(i) ((char_type *)(htab))[i]
 121 #define de_stack ((char_type *)&tab_suffixof(1<<COMPRESSBITS))
 122 #endif                                                  /* __MSDOS__ */
 123 #define FIRST 257                               /* first free entry */
 124 #define CLEAR 256                               /* table clear output code */
 125
 126 /* BB changed next two lines. For 16 bits, the maximum code_int
 127    becomes zero again! (1 << 16 == 0).
 128    Debugging the un*x version shows that
 129    count_int should be a 32bits integer! */
 130
 131 /* typedef int code_int; */
 132
 133 /* typedef int count_int; */
 134 #ifdef __MSDOS__
 135 #define NSHUGE huge
 136 typedef long code_int;
 137 typedef long count_int;
 138 #else
 139 #define NSHUGE
 140 typedef int count_int;
 141 typedef int code_int;
 142 #endif                                                  /* __MSDOS__ */
 143 typedef unsigned char char_type;
 144
 145 static int n_bits;                              /* number of bits/code */
 146 static int maxbits;                             /* user settable max # bits/code */
 147 static code_int maxcode;                /* maximum code, given n_bits */
 148 static code_int maxmaxcode;             /* should NEVER generate this code */
 149
 150 /* BB changed next two lines.
 151    Under Borland C/C++ static arrays are REALLY static, i.e. they
 152    clog the executable with some 384k of `empty space'. So use
 153    dynamic arrays instead. */
 154
 155 /* static count_int htab[HSIZE]; */
 156
 157 /* static unsigned short codetab[HSIZE]; */
 158 #ifdef __MSDOS__
 159
 160 /* For those that do want to use static arrays:
 161    define BB_HUGE_STATIC_ARRAYS. */
 162 #ifdef BB_HUGE_STATIC_ARRAYS
 163 static count_int NSHUGE htab[HSIZE];
 164 static unsigned short NSHUGE codetab[HSIZE];
 165 #else                                                   /* BB_HUGE_STATIC_ARRAYS */
 166 static count_int NSHUGE *htab = NULL;
 167 static unsigned short NSHUGE *codetab = NULL;
 168 #endif                                                  /* BB_HUGE_STATIC_ARRAYS */
 169 #else                                                   /* __MSDOS__ */
 170 static count_int htab[HSIZE];
 171 static unsigned short codetab[HSIZE];
 172 #endif                                                  /* __MSDOS__ */
 173 static char_type rmask[9] =
 174         { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
 175 static code_int free_ent;               /* first unused entry */
 176 static int clear_flg;
 177 static long readsize;                   /* number of bytes left to read */
 178
 179 static code_int offset;         /* from getcode() */
 180 static size_t size;
 181
 182 static code_int getcode(FILE * ifp);
 183
 184
 185 Status
 186 uncompress(Header *header, FILE *ifp, FILE *ofp, CompType type)
 187 {
 188         /* BB changed next line. stackp points to huge pointers. */
 189         register char_type NSHUGE *stackp;
 190         register code_int finchar;
 191         register code_int code, oldcode, incode;
 192         char *message;
 193
 194         init_garble();
 195
 196 #if defined(__MSDOS__) && !defined(BB_HUGE_STATIC_ARRAYS)
 197         if (!htab)
 198                 htab = (count_int NSHUGE *) farcalloc(HSIZE, sizeof(count_int));
 199         if (!codetab)
 200                 codetab =
 201                         (unsigned short NSHUGE *) farcalloc(HSIZE,
 202                                                                                           sizeof(unsigned short));
 203         if (!htab || !codetab)
 204         {
 205                 error("%s: uncompress: out of memory", ourname);
 206                 exit(1);
 207         }
 208 #endif                                                  /* __MSDOS__ && ! BB_HUGE_STATIC_ARRAYS */
 209
 210         crc = 0;
 211         clear_flg = 0;
 212         offset = 0;
 213         size = 0;
 214         readsize = header->complen;
 215
 216         if (type == SQUASH)
 217                 maxbits = SQUASHBITS;
 218         else if (type == UNIX_COMPRESS)
 219         {
 220                 /* Read the unix compress header */
 221                 read_byte(ifp);
 222                 read_byte(ifp);
 223                 maxbits = read_byte(ifp) & 0x1f;
 224                 readsize -= 3;
 225         }
 226         else
 227         {
 228                 if (arcfs)
 229                 {
 230                         maxbits = arcfs_maxbits;
 231                         ungarble('\0'); // Need to consume one byte of password.
 232                 }
 233                 else
 234                 {
 235                         maxbits = read_byte(ifp);
 236                         readsize--;
 237                 }
 238         }
 239         maxmaxcode = MAXCODE(maxbits);
 240
 241         /*
 242          * As above, initialize the first 256 entries in the table.
 243          */
 244         maxcode = MAXCODE(n_bits = INIT_BITS);
 245         for (code = 255; code >= 0; code--)
 246         {
 247                 tab_prefixof(code) = 0;
 248                 tab_suffixof(code) = (char_type) code;
 249         }
 250         free_ent = FIRST;
 251
 252         finchar = oldcode = getcode(ifp);
 253         if (oldcode == -1)                      /* EOF already? */
 254                 goto compress_exit;             /* Get out of here */
 255
 256         /* first code must be 8 bits = char */
 257         if (type == CRUNCH)
 258         {
 259                 putc_init();
 260                 /* BB changed next line for Borland C/C++ 4 */
 261                 putc_ncr(ofp, (Byte) finchar);
 262         }
 263         else
 264         {
 265                 /* BB changed next three lines for Borland C/C++ 4 */
 266                 if (!testing)
 267                         write_byte(ofp, (Byte) finchar);
 268                 calccrc((Byte) finchar);
 269         }
 270
 271         stackp = de_stack;
 272
 273         while ((code = getcode(ifp)) != -1)
 274         {
 275                 if (check_stream(ifp) != FNOERR)
 276                         break;
 277                 if (code == CLEAR)
 278                 {
 279                         for (code = 255; code >= 0; code--)
 280                                 tab_prefixof(code) = 0;
 281                         clear_flg = 1;
 282                         free_ent = FIRST - 1;
 283                         if ((code = getcode(ifp)) == -1)        /* O, untimely death! */
 284                                 break;
 285                 }
 286                 incode = code;
 287                 /*
 288                  * Special case for KwKwK string.
 289                  */
 290                 if (code >= free_ent)
 291                 {
 292                         /* BB changed next line for Borland C/C++ 4 */
 293                         *stackp++ = (char_type) finchar;
 294                         code = oldcode;
 295                 }
 296                 /*
 297                  * Generate output characters in reverse order
 298                  */
 299
 300                 while (code >= 256)
 301                 {
 302                         if ((char NSHUGE *)(stackp+1) > (char NSHUGE *)(&htab[0] + HSIZE))
 303                         {
 304                                 error("%s: uncompress: corrupt or garbled archive file", ourname);
 305                                 exit(1);
 306                         }
 307                         *stackp++ = tab_suffixof(code);
 308                         code = tab_prefixof(code);
 309                 }
 310                 /* BB changed next line for Borland C/C++ 4 */
 311                 /* *stackp++ = finchar = tab_suffixof(code); */
 312 #ifdef __MSDOS__
 313                 finchar = tab_suffixof(code);
 314                 *stackp++ = (char_type) finchar;
 315 #else
 316                 if ((char *)(stackp+1) > (char *)(&htab[0] + HSIZE))
 317                 {
 318                         error("%s: uncompress: corrupt or garbled archive file", ourname);
 319                         exit(1);
 320                 }
 321                 *stackp++ = finchar = tab_suffixof(code);
 322 #endif
 323
 324                 /*
 325                  * And put them out in forward order
 326                  */
 327                 while (stackp > de_stack)
 328                 {
 329                         stackp--;
 330                         if (type == CRUNCH)
 331                                 putc_ncr(ofp, *stackp);
 332                         else
 333                         {
 334                                 if (!testing)
 335                                         write_byte(ofp, *stackp);
 336                                 calccrc(*stackp);
 337                         }
 338                 }
 339
 340                 /*
 341                  * Generate the new entry.
 342                  */
 343                 if ((code = free_ent) < maxmaxcode)
 344                 {
 345                         /* BB changed next two lines for Borland C/C++ 4 */
 346                         tab_prefixof(code) = (unsigned short) oldcode;
 347                         tab_suffixof(code) = (char_type) finchar;
 348                         free_ent = code + 1;
 349                 }
 350                 /*
 351                  * Remember previous code.
 352                  */
 353                 oldcode = incode;
 354         }
 355   compress_exit:
 356         if (check_stream(ifp) == FRWERR)
 357                 return (RERR);
 358         if (!testing && check_stream(ofp) == FRWERR)
 359                 return (WERR);
 360         if ((Halfword) crc != header->crc)
 361                 return (CRCERR);
 362         if (testing)
 363                 switch (type)
 364                 {
 365                 case COMPRESS:
 366                 case UNIX_COMPRESS:
 367                         message = "OK (compressed)";
 368                         break;
 369                 case CRUNCH:
 370                         message = "OK (crunched)";
 371                         break;
 372                 case SQUASH:
 373                         message = "OK (squashed)";
 374                         break;
 375                 default:
 376                         message = "internal error";
 377                         break;
 378                 }
 379         else
 380                 switch (type)
 381                 {
 382                 case COMPRESS:
 383                 case UNIX_COMPRESS:
 384                         message = "uncompressed";
 385                         break;
 386                 case CRUNCH:
 387                         message = "uncrunched";
 388                         break;
 389                 case SQUASH:
 390                         message = "unsquashed";
 391                         break;
 392                 default:
 393                         message = "internal error";
 394                         break;
 395                 }
 396         if (!quiet)
 397                 msg("%s", message);
 398         return (NOERR);
 399 }
 400
 401 /*
 402  * Read one code from the input.  If EOF, return -1.
 403  */
 404 static code_int
 405 getcode(FILE *ifp)
 406 {
 407         register code_int code;
 408         static char_type buf[COMPRESSBITS];
 409         register int r_off, bits;
 410         size_t i;
 411         /* BB changed next line. We are doing pointer-artithmatics
 412            and that can be dangerous if other than normalized (huge)
 413            pointers are being used. */
 414         register char_type NSHUGE *bp = buf;
 415
 416         if (clear_flg > 0 || offset >= size || free_ent > maxcode)
 417         {
 418                 /*
 419                  * If the next entry will be too big for the current code
 420                  * size, then we must increase the size.  This implies
 421                  * reading a new buffer full, too.
 422                  */
 423                 if (free_ent > maxcode)
 424                 {
 425                         n_bits++;
 426                         maxcode = n_bits == maxbits ? maxmaxcode : MAXCODE(n_bits);
 427                 }
 428                 if (clear_flg > 0)
 429                 {
 430                         maxcode = MAXCODE(n_bits = INIT_BITS);
 431                         clear_flg = 0;
 432                 }
 433                 if (readsize == 0)
 434                         return (-1);
 435                 /* BB added cast to next line */
 436                 size = readsize < n_bits ? (size_t) readsize : n_bits;
 437                 size = fread(buf, 1, size, ifp);
 438                 if (size == 0)
 439                         return (-1);            /* end of file */
 440                 for (i = 0; i < size; i++)
 441                 {
 442                         buf[i] = ungarble(buf[i]);
 443                 }
 444                 readsize -= size;
 445                 offset = 0;
 446                 /* Round size down to integral number of codes */
 447                 size = (size << 3) - (n_bits - 1);
 448         }
 449         r_off = (int)offset;
 450         bits = n_bits;
 451
 452         /*
 453          * Get to the first byte.
 454          */
 455         bp += (r_off >> 3);
 456         r_off &= 7;
 457         /* Get first part (low order bits) */
 458
 459         code = (*bp++ >> r_off);
 460         bits -= (8 - r_off);
 461         r_off = 8 - r_off;                      /* now, offset into code word */
 462         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
 463         if (bits >= 8)
 464         {
 465                 code |= *bp++ << r_off;
 466                 r_off += 8;
 467                 bits -= 8;
 468         }
 469         /* high order bits. */
 470         code |= (*bp & rmask[bits]) << r_off;
 471         offset += n_bits;
 472
 473         return (code);
 474 }