home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / msdos / arc_lbr / squash.arc / SQUASH.C next >
Text File  |  1987-11-12  |  32KB  |  1,238 lines
  1. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2.  * Squash - data compression program
  3.  *
  4.  *
  5.  * Squash.c - File compression ala IEEE Computer, June 1984.
  6.  *
  7.  * Authors:    Spencer W. Thomas    (decvax!harpo!utah-cs!utah-gr!thomas)
  8.  *        Jim McKie        (decvax!mcvax!jim)
  9.  *        Steve Davies        (decvax!vax135!petsd!peora!srd)
  10.  *        Ken Turkowski        (decvax!decwrl!turtlevax!ken)
  11.  *        James A. Woods        (decvax!ihnp4!ames!jaw)
  12.  *        Joe Orost        (decvax!vax135!petsd!joe)
  13.  *        Leslie Satenstein    (PCOMM/INFOCOM BBS Montreal as LESLIE)
  14.  *                    (514)-682-5884
  15.  *
  16.  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  17.  
  18. #define  MAIN
  19. #include <stdio.h>
  20. #include <ctype.h>
  21. #include <dos.h>
  22. #include <signal.h>
  23. #include <types.h>
  24. #include <stat.h>
  25. #include <squash.h>
  26. #include <io.h>
  27.  
  28. /* stuff for non-repeat packing */
  29. #define DLE 0x90            /* repeat sequence marker */
  30. static unsigned char state;        /* current packing state */
  31. /* non-repeat packing states */
  32. #define NOHIST    0            /* don't consider previous input*/
  33. #define INREP 1             /* sending a repeated value */
  34. #define SENTCHAR 1            /* lastchar set, no lookahead yet */
  35. #define SENDNEWC 2            /* run over, send new char next */
  36. #define SENDCNT 3            /* newchar set, send count next */
  37.  
  38.  
  39.  
  40. char *arc=".ARC";
  41. int exit_stat = 0;
  42.  
  43. int getcode();
  44.  
  45. int do_decomp = 0;
  46. int debug = 0;
  47. int quiet = 1;                /* don't tell me about compression */
  48. int kill=0;                /* don't delete input */
  49.  
  50. int force = 0;
  51. char ofname [70];
  52. int verbose = 0;
  53. int (*bgnd_flag)();
  54.  
  55. static int crctab[] =            /* CRC lookup table */
  56. {
  57.     0x0000, 0xC0C1, 0xC181, 0x0140, 0xC301, 0x03C0, 0x0280, 0xC241,
  58.     0xC601, 0x06C0, 0x0780, 0xC741, 0x0500, 0xC5C1, 0xC481, 0x0440,
  59.     0xCC01, 0x0CC0, 0x0D80, 0xCD41, 0x0F00, 0xCFC1, 0xCE81, 0x0E40,
  60.     0x0A00, 0xCAC1, 0xCB81, 0x0B40, 0xC901, 0x09C0, 0x0880, 0xC841,
  61.     0xD801, 0x18C0, 0x1980, 0xD941, 0x1B00, 0xDBC1, 0xDA81, 0x1A40,
  62.     0x1E00, 0xDEC1, 0xDF81, 0x1F40, 0xDD01, 0x1DC0, 0x1C80, 0xDC41,
  63.     0x1400, 0xD4C1, 0xD581, 0x1540, 0xD701, 0x17C0, 0x1680, 0xD641,
  64.     0xD201, 0x12C0, 0x1380, 0xD341, 0x1100, 0xD1C1, 0xD081, 0x1040,
  65.     0xF001, 0x30C0, 0x3180, 0xF141, 0x3300, 0xF3C1, 0xF281, 0x3240,
  66.     0x3600, 0xF6C1, 0xF781, 0x3740, 0xF501, 0x35C0, 0x3480, 0xF441,
  67.     0x3C00, 0xFCC1, 0xFD81, 0x3D40, 0xFF01, 0x3FC0, 0x3E80, 0xFE41,
  68.     0xFA01, 0x3AC0, 0x3B80, 0xFB41, 0x3900, 0xF9C1, 0xF881, 0x3840,
  69.     0x2800, 0xE8C1, 0xE981, 0x2940, 0xEB01, 0x2BC0, 0x2A80, 0xEA41,
  70.     0xEE01, 0x2EC0, 0x2F80, 0xEF41, 0x2D00, 0xEDC1, 0xEC81, 0x2C40,
  71.     0xE401, 0x24C0, 0x2580, 0xE541, 0x2700, 0xE7C1, 0xE681, 0x2640,
  72.     0x2200, 0xE2C1, 0xE381, 0x2340, 0xE101, 0x21C0, 0x2080, 0xE041,
  73.     0xA001, 0x60C0, 0x6180, 0xA141, 0x6300, 0xA3C1, 0xA281, 0x6240,
  74.     0x6600, 0xA6C1, 0xA781, 0x6740, 0xA501, 0x65C0, 0x6480, 0xA441,
  75.     0x6C00, 0xACC1, 0xAD81, 0x6D40, 0xAF01, 0x6FC0, 0x6E80, 0xAE41,
  76.     0xAA01, 0x6AC0, 0x6B80, 0xAB41, 0x6900, 0xA9C1, 0xA881, 0x6840,
  77.     0x7800, 0xB8C1, 0xB981, 0x7940, 0xBB01, 0x7BC0, 0x7A80, 0xBA41,
  78.     0xBE01, 0x7EC0, 0x7F80, 0xBF41, 0x7D00, 0xBDC1, 0xBC81, 0x7C40,
  79.     0xB401, 0x74C0, 0x7580, 0xB541, 0x7700, 0xB7C1, 0xB681, 0x7640,
  80.     0x7200, 0xB2C1, 0xB381, 0x7340, 0xB101, 0x71C0, 0x7080, 0xB041,
  81.     0x5000, 0x90C1, 0x9181, 0x5140, 0x9301, 0x53C0, 0x5280, 0x9241,
  82.     0x9601, 0x56C0, 0x5780, 0x9741, 0x5500, 0x95C1, 0x9481, 0x5440,
  83.     0x9C01, 0x5CC0, 0x5D80, 0x9D41, 0x5F00, 0x9FC1, 0x9E81, 0x5E40,
  84.     0x5A00, 0x9AC1, 0x9B81, 0x5B40, 0x9901, 0x59C0, 0x5880, 0x9841,
  85.     0x8801, 0x48C0, 0x4980, 0x8941, 0x4B00, 0x8BC1, 0x8A81, 0x4A40,
  86.     0x4E00, 0x8EC1, 0x8F81, 0x4F40, 0x8D01, 0x4DC0, 0x4C80, 0x8C41,
  87.     0x4400, 0x84C1, 0x8581, 0x4540, 0x8701, 0x47C0, 0x4680, 0x8641,
  88.     0x8201, 0x42C0, 0x4380, 0x8341, 0x4100, 0x81C1, 0x8081, 0x4040
  89. };
  90.  
  91. /*****************************************************************
  92.  * TAG( main )
  93.  *
  94.  * Algorithm from "A Technique for High Performance Data Compression",
  95.  * Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
  96.  *
  97.  * Usage: squash    [-fvcukVd] archive [filein]
  98.  *
  99.  * switches:
  100.  * All flags are optional.
  101.  *        -D => debug
  102.  *        -V => print Version; debug verbose
  103.  *        -v => unquiet
  104.  *        -u => do decompression
  105.  *        -f => force overwrite of output file
  106.  *        -F => force overwrite of output file
  107.  *        -n => no header: useful to uncompress old files
  108.  *        -k => delete file after inserting into archive
  109.  *        -K => delete file after inserting into archive
  110.  *        -q => complement of -v (quiet) shhhhh
  111.  *
  112.  *    -f:        Forces output archive to be generated, even if one already
  113.  *            exists.
  114.  *            If -f is not used, the user will be prompted to determine
  115.  *            if the output file should be overwritten.
  116.  *
  117.  *    -k:        Deletes input file after output file is created.
  118.  *
  119.  *    -v:        Write compression statistics
  120.  *
  121.  * Outputs:
  122.  *    file.ARC:   Compressed form of file with same mode,
  123.  *
  124.  * Assumptions:
  125.  *    When filenames are given, replaces with the compressed version
  126.  *    (.ARC suffix)
  127.  *
  128.  * Algorithm:
  129.  *
  130.  *    Modified Lempel-Ziv method (LZW).  Basically finds common
  131.  * substrings and replaces them with a variable size code.  This is
  132.  * deterministic, and can be done on the fly.  Thus, the decompression
  133.  * procedure needs no input table, but tracks the way the table was built.
  134.  */
  135.  
  136. main( argc, argv )
  137. register int argc;
  138. char **argv;
  139. {
  140.     int overwrite = 0;            /* Do not overwrite unless given -f flag */
  141.     char tempname[80];
  142.     char **filelist, **fileptr;
  143.     char *cp, *strrchr(char *,char), *malloc(int);
  144.     struct stat statbuf;
  145.     FILE *filein,*fileout;
  146.     extern onintr();
  147.  
  148.     /* trap control break */
  149.  
  150.     if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN )
  151.     {
  152.     signal ( SIGINT, onintr );
  153.     }
  154.  
  155.  
  156.     filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
  157.     *filelist = NULL;
  158.  
  159.     /*
  160.      * Argument Processing
  161.      */
  162.     for (argc--, argv++; argc > 0; argc--, argv++)
  163.     {
  164.     if (**argv == '-')
  165.     {                /* A flag argument */
  166.         while (*++(*argv))
  167.         {                /* Process all flags in this arg */
  168.         switch (**argv)
  169.         {
  170.         case 'D':
  171.             debug = 1;
  172.             break;
  173.         case 'V':
  174.             verbose = 1;
  175.             version();
  176.             break;
  177.         case 'v':
  178.             quiet = 0;
  179.             break;
  180.         case 'u':
  181.             do_decomp = 1;
  182.             break;
  183.         case 'f':
  184.         case 'F':
  185.             overwrite = 1;
  186.             force = 1;
  187.             break;
  188.         case 'k':
  189.         case 'K':
  190.             kill=1;
  191.             break;
  192.         case 'q':
  193.             quiet = 1;
  194.             break;
  195.         default:
  196.             printf( "Unknown flag: '%c'; ", **argv);
  197.             Usage();
  198.             exit(1);
  199.         }
  200.         }
  201.     }
  202.     else
  203.     {                /* Input file name */
  204.         *fileptr++ = *argv;     /* Build input file list */
  205.         *fileptr = NULL;
  206.         /* process nextarg; */
  207.     }
  208. nextarg:
  209.     continue;
  210.     }
  211.  
  212.  
  213.     if (*filelist != NULL)
  214.     {
  215.     for (fileptr = filelist; strupr(*fileptr); fileptr++)
  216.     {
  217.         exit_stat = 0;
  218.  
  219.         if (do_decomp != 0)
  220.         {                /* DECOMPRESSION */
  221.                     /* Check for .ARC suffix */
  222.         if (strcmp(*fileptr + strlen(*fileptr) - 4, arc) != 0)
  223.         {
  224.             /* No .ARC    tack one on */
  225.             strcpy(tempname, *fileptr);
  226.             if(!strrchr(tempname,'.')) strcat(tempname, arc);
  227.             *fileptr = tempname;
  228.         }
  229.         /* Open input file */
  230.  
  231.         if ((filein=fopen(*fileptr, "rb")) == NULL)
  232.         {
  233.             perror(*fileptr);
  234.             continue;
  235.         }
  236.  
  237.         /* Generate output filename */
  238.         if(read(fileno(filein),&ahead,sizeof(ahead))!=sizeof(ahead))
  239.         {
  240.             printf("IO error on input file %s\n",filein);
  241.             exit(1);
  242.         }
  243.         strcpy(ofname, ahead.name);
  244.         }
  245.         else
  246.         {                /* COMPRESSION */
  247.  
  248.         if (strcmp(*fileptr + strlen(*fileptr) - 4, arc) == 0)
  249.         {
  250.             printf("%s: already has .ARC suffix -- no change\n",
  251.             *fileptr);
  252.             continue;
  253.         }
  254.         /* Open input file */
  255.  
  256.         if ((filein=fopen(*fileptr, "rb")) == NULL)
  257.         {
  258.             perror(*fileptr);
  259.             continue;
  260.         }
  261.         /* Generate output filename */
  262.         /* Strip off drive id and path */
  263.         strcpy(ofname, *fileptr);
  264.         if(!(cp=strrchr(ofname,'\\') ))/* ms/pc dos */
  265.             if(!(cp=strrchr(ofname,'/') )) /* for unix */
  266.             if(!(cp=strrchr(ofname,':'))) cp=ofname-1;
  267.         cp++;            /* skip past the delimiter */
  268.         strcpy(ahead.name,cp);
  269.  
  270.  
  271.         if(cp=strrchr(ofname,'.')) strcpy(cp,arc);
  272.         else
  273.             strcat(ofname, arc);
  274.  
  275.         if ((cp=strrchr(ofname,'\\')) != NULL) cp++;
  276.         else
  277.             cp = ofname;
  278.         if (strlen(cp) > 12)
  279.         {
  280.             printf("%s: filename too long to tack on %s\n",cp,arc);
  281.             continue;
  282.         }
  283.  
  284.         }
  285.  
  286.         /* Check for overwrite of existing file */
  287.  
  288.         if (!overwrite)
  289.         {
  290.         if (stat(ofname, &statbuf) == 0)
  291.         {
  292.             char response[2];
  293.             response[0] = 'n';
  294.             printf( "%s already exists;", ofname);
  295.             if (foreground())
  296.             {
  297.             printf( " do you wish to overwrite %s (y or n)? ",
  298.             ofname);
  299.             fflush(stdout);
  300.             read(fileno(stdin), response,2 );
  301.             while (response[1] != '\n')
  302.             {
  303.                 if (read(fileno(stdin), response+1, 1) < 0)
  304.                 {        /* Ack! */
  305.                 perror("stdin");
  306.                 break;
  307.                 }
  308.             }
  309.             }
  310.             strupr(response);
  311.             if (response[0] != 'Y')
  312.             {
  313.             printf( "\tnot overwritten\n");
  314.             continue;
  315.             }
  316.         }
  317.         }
  318.         if((fileout=fopen(ofname, "wb")) == NULL)
  319.         {
  320.         perror(ofname);
  321.         continue;
  322.         }
  323.         if(!quiet)
  324.         printf( "%s: ", *fileptr);
  325.  
  326.         /* Actually do the compression/decompression */
  327.  
  328.         if (do_decomp == 0) docompress(fileout,filein);
  329.         else
  330.         dodecompress(fileout,filein,*fileptr);
  331.  
  332.         if((exit_stat == 1) || (!quiet))
  333.         putc('\n', stdout);
  334.     }
  335.     if (do_decomp == 0)        /* indicate end of file */
  336.     {
  337.         ahead.atype=0;
  338.         if(2!=write(fileno(fileout),&ahead,2))writeerr();
  339.         fclose(fileout);
  340.     }
  341.     }
  342.     else
  343.     {
  344.      Usage();
  345.     }
  346.     exit(exit_stat);
  347. }
  348. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  349.  
  350. docompress  -initialize compression
  351.  
  352. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  353.  
  354. docompress(fileout,filein)
  355. register FILE *filein,*fileout;
  356. {
  357.     long fpos;
  358.     fpos=fseek(fileout,0L,1);        /* save displacement into file */
  359.     ahead.archmark=0x1a;
  360.     ahead.length = filelength(fileno(filein));
  361.     getstamp(filein,&ahead.date,&ahead.time);
  362.     if(write(fileno(fileout),&ahead,sizeof(ahead)) !=sizeof(ahead))
  363.     {
  364.     printf( "Outfile error, disk full???\n");
  365.     writeerr();
  366.     }
  367.     bytes_out = crc=0;            /* excludes header */
  368.     if ( ahead.length < (1 << 12) )
  369.     {
  370.     state=NOHIST;
  371.     ahead.atype=8;            /* crunch */
  372.     hsize = 5003;
  373.     max_bits=12;
  374.     if(1!=write(fileno(fileout),&max_bits,1))writeerr();
  375.     bytes_out++;
  376.     }
  377.     else
  378.     {
  379.     ahead.atype=9;
  380.     hsize = HSIZE;
  381.     max_bits=BITS;
  382.     }
  383.  
  384.     compress(fileout,filein);
  385.     fclose(filein);
  386.     ahead.crc=crc;
  387.     ahead.lzwsize=bytes_out;
  388.     fseek(fileout,fpos,0);
  389.     if(write( fileno(fileout),&ahead,sizeof(ahead)) !=sizeof(ahead) )writeerr();
  390.     fseek(fileout,0L,2);
  391.     /*
  392.      * Print out stats on stdout
  393.     */
  394.  
  395.     if(!quiet)
  396.     {
  397.  
  398.     printf("%ld chars in, %ld codes (%ld bytes) out, compression factor: ",
  399.     in_count, out_count, bytes_out );
  400.     prratio( stdout, in_count, bytes_out );
  401.     printf( "\tCompression as in compact: " );
  402.     prratio( stdout, in_count-bytes_out, in_count );
  403.     printf( "\tLargest code (of last block) was %d (%d bits)\n",
  404.     free_ent - 1, n_bits );
  405.  
  406.     }
  407.     return(exit_stat);
  408.  
  409. }
  410.  
  411.  
  412. /*****************************************************************
  413.  * TAG( output )
  414.  *
  415.  * Output the given code.
  416.  * Inputs:
  417.  *    code:    A n_bits-bit integer.  If == -1, then EOF.  This assumes
  418.  *        that n_bits =< (long)wordsize - 1.
  419.  * Outputs:
  420.  *    Outputs code to the file.
  421.  * Assumptions:
  422.  *    Chars are 8 bits long.
  423.  * Algorithm:
  424.  *    Maintain a BITS character long buffer (so that 8 codes will
  425.  * fit in it exactly).    Extract a code from the buffer and use each
  426.  * code in turn.  When the buffer fills up empty it and start over.
  427.  *****************************************************************/
  428.  
  429. static    char iobuf[BITS];
  430.  
  431. unsigned char lmask[9] = {
  432.     0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  433. unsigned char rmask[9] = {
  434.     0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  435.  
  436. output( code,outf )
  437. FILE *outf;
  438. int  code;
  439. {
  440.     static int col = 0;
  441.  
  442.     register  char * bp = iobuf;
  443.     register int r_off = offset, bits= n_bits;
  444.  
  445.     if ( verbose )
  446.     printf( "%5d%c", code,
  447.     (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
  448.     if ( code >= 0 )
  449.     {
  450.  
  451.     /*
  452.      * Get to the first byte.
  453.      */
  454.  
  455.     bp += (r_off >> 3);
  456.     r_off &= 7;
  457.     /*
  458.      * Since code is always >= 8 bits, only need to mask the first
  459.      * hunk on the left.
  460.      */
  461.     *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  462.     bp++;
  463.     bits -= (8 - r_off);
  464.     code >>= 8 - r_off;
  465.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  466.     if ( bits >= 8 )
  467.     {
  468.         *bp++ = code;
  469.         code >>= 8;
  470.         bits -= 8;
  471.     }
  472.     /* Last bits. */
  473.     if(bits)
  474.         *bp = code;
  475.     offset += n_bits;
  476.     if ( offset == (n_bits << 3) )
  477.     {
  478.         bp = iobuf;
  479.         bits = n_bits;
  480.         bytes_out += bits;
  481.         write(fileno(outf),bp,bits);
  482.         offset=bits=0;
  483. /*
  484.         do
  485.         fputc(*bp++,outf);
  486.         while(--bits);
  487.         offset = 0;
  488. */
  489.     }
  490.  
  491.     /*
  492.      * If the next entry is going to be too big for the code size,
  493.      * then increase it, if possible.
  494.      */
  495.     if ( free_ent > maxcode || (clear_flg > 0))
  496.     {
  497.         /*
  498.          * Write the whole buffer, because the input side won't
  499.          * discover the size increase until after it has read it.
  500.          */
  501.         if ( offset > 0 )
  502.         {
  503.         if( write( fileno(outf),iobuf, n_bits) != n_bits)
  504.             writeerr();
  505.         bytes_out += n_bits;
  506.         }
  507.         offset = 0;
  508.  
  509.         if ( clear_flg )
  510.         {
  511.         maxcode = MAXCODE (INIT_BITS);
  512.         n_bits = INIT_BITS;
  513.         clear_flg = 0;
  514.         }
  515.         else
  516.         {
  517.         n_bits++;
  518.         if ( n_bits == max_bits)
  519.             maxcode = maxmaxcode;
  520.         else
  521.             maxcode = MAXCODE(n_bits);
  522.         }
  523.         if ( debug )
  524.         {
  525.         printf( "\nChange to %d bits\n", n_bits );
  526.         col = 0;
  527.         }
  528.     }
  529.     }
  530.     else
  531.     {
  532.     /*
  533.      * At EOF, write the rest of the buffer.
  534.      */
  535.     if ( offset > 0 )
  536.         write( fileno(outf),iobuf, offset= (offset + 7)>>3);
  537.     bytes_out += offset;
  538.     offset = 0;
  539.     fflush( outf );
  540.  
  541.     if ( verbose )
  542.         printf( "\n" );
  543.  
  544.     if( ferror( outf ) )
  545.         writeerr();
  546.     }
  547. }
  548.  
  549. /*****************************************************************
  550.  * TAG( getcode )
  551.  *
  552.  * Read one code from the standard input.  If EOF, return -1.
  553.  * Inputs:
  554.  *    filein
  555.  * Outputs:
  556.  *    code or -1 is returned.
  557.  ****************************************************************/
  558.  
  559. int getcode(inf)
  560. FILE *inf;
  561. {
  562.     register int code;
  563.     static int offset = 0, size = 0;
  564.     register int r_off, bits;
  565.     register unsigned char *bp = iobuf;
  566.  
  567.     if ( clear_flg > 0 || offset >= size || free_ent > maxcode )
  568.     {
  569.     /*
  570.      * If the next entry will be too big for the current code
  571.      * size, then we must increase the size.  This implies reading
  572.      * a new buffer full, too.
  573.      */
  574.  
  575.     if ( free_ent > maxcode )
  576.     {
  577.         n_bits++;
  578.         if ( n_bits == max_bits   )
  579.         maxcode = maxmaxcode;    /* won't get any bigger now */
  580.         else
  581.         maxcode = MAXCODE(n_bits);
  582.     }
  583.     if ( clear_flg > 0)
  584.     {
  585.         maxcode = MAXCODE (INIT_BITS);
  586.         n_bits = INIT_BITS;
  587.         clear_flg = 0;
  588.     }
  589.  
  590.     for(size=0; size<n_bits; size++)
  591.     {
  592.         if((code=getc_unp(inf))==EOF)
  593.         break;
  594.         else iobuf[size] = code;
  595.     }
  596.  
  597.     if(size <= 0)return -1;     /* end of file */
  598.  
  599.     offset = 0;
  600.     /* Round size down to integral number of codes */
  601.     size = (size << 3) - (n_bits - 1);
  602.     }
  603.     r_off = offset;
  604.     bits = n_bits;
  605.    /*
  606.     * Get to the first byte.
  607.     */
  608.     bp += (r_off >> 3);
  609.     r_off &= 7;
  610.     /* Get first part (low order bits) */
  611.     code = (*bp++ >> r_off);
  612.     bits -= (8 - r_off);
  613.     r_off = 8 - r_off;            /* now, offset into code word */
  614.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  615.     if ( bits >= 8 )
  616.     {
  617.     code |= *bp++ << r_off;
  618.     r_off += 8;
  619.     bits -= 8;
  620.     }
  621.     /* high order bits. */
  622.     code |= (*bp & rmask[bits]) << r_off;
  623.     offset += n_bits;
  624.  
  625.     return code;
  626. }
  627.  
  628. writeerr()
  629. {
  630.     perror ( ofname );
  631.     unlink ( ofname );
  632.     exit ( 1 );
  633. }
  634. /*
  635.  * This routine returns 1 if we are running in the foreground and stdout
  636.  * is a tty.
  637.  */
  638. foreground()
  639. {
  640.     if(bgnd_flag)
  641.     {                    /* background? */
  642.     return(0);
  643.     }
  644.     /* foreground */
  645.     return((isatty(2)));
  646. }
  647.  
  648. onintr ( )
  649. {
  650.     unlink ( ofname );
  651.     exit ( 1 );
  652. }
  653.  
  654.  
  655. cl_block ()                /* table clear for block compress */
  656. {
  657.     register long int rat;
  658.  
  659.     checkpoint = in_count + CHECK_GAP;
  660.     if ( debug )
  661.     {
  662.     printf ( "count: %ld, ratio: ", in_count );
  663.     prratio ( stdout, in_count, bytes_out );
  664.     }
  665.  
  666.     if(in_count > 0x007fffff)
  667.     {                    /* shift will overflow */
  668.     rat = bytes_out >> 8;
  669.     if(rat == 0)
  670.     {                /* Don't divide by zero */
  671.         rat = 0x7fffffff;
  672.     }
  673.     else
  674.     {
  675.         rat = in_count / rat;
  676.     }
  677.     }
  678.     else
  679.     {
  680.     rat = (in_count << 8) / bytes_out; /* 8 fractional bits */
  681.     }
  682.     if ( rat > ratio )
  683.     {
  684.     ratio = rat;
  685.     }
  686.     else
  687.     {
  688.     ratio = 0;
  689. #ifdef DUMPTAB
  690.     if(verbose)
  691.         dump_tab();         /* dump string table */
  692. #endif
  693.  
  694.     clr_hash ();
  695.     free_ent = FIRST;
  696.     clear_flg = 1;
  697.     output( (int) CLEAR );
  698.     if(debug)
  699.         printf ( "clear\n" );
  700.     }
  701. }
  702.  
  703. clr_hash()                /* reset code table */
  704. {
  705.  
  706.     memset(htab,0xffff,sizeof(htab));    /* default everything */
  707. }
  708.  
  709. prratio(stream, num, den)
  710. FILE *stream;
  711. long int num, den;
  712. {
  713.     register int q;            /* Doesn't need to be long */
  714.  
  715.     if(num > 214748L)
  716.     {                    /* 2147483647/10000 */
  717.     q = num / (den / 10000L);
  718.     }
  719.     else
  720.     {
  721.     q = 10000L * num / den;     /* Long calculations, though */
  722.     }
  723.     if (q < 0)
  724.     {
  725.     putc('-', stream);
  726.     q = -q;
  727.     }
  728.     fprintf(stream, "%d.%02d%%\n", q / 100, q % 100);
  729. }
  730.  
  731. version()
  732. {
  733.     printf( "Options: ");
  734.     if(debug)
  735.     {
  736.     printf("DEBUG, ");
  737.     printf( "BITS = %d\n", BITS);
  738.     }
  739. }
  740.  
  741. Usage()
  742. {
  743.     printf("Usage: Squash [-DVfkq] filename.ext\n\t===>filename.arc\n");
  744.     printf("Usage: Squash -u [-DVfkq] filename[.arc] \n");
  745.     printf("\t===>filename.ext -u selects decompress \n");
  746. }
  747.  
  748. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  749.  
  750.   read input, perform crc check, and then function like fgetc
  751.   which is to return a character at a time to the caller
  752.  
  753. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  754.  
  755. unsigned myfgetc(filein)
  756. FILE *filein;
  757. {
  758.     static long lefttoread;        /* count down number of bytes */
  759.     static fchunk=0;            /* amount to take at a time */
  760.     static unsigned char *fbuf=NULL,*fbpos=NULL;
  761.     static short fbsize;
  762.     if( !fbuf)                /* was I here already ? */
  763.     {
  764.     fbsize=_memavl();        /* get free space */
  765.     if(fbsize>32767) fbsize=32767;    /* not more than 32k */
  766.     if(fbsize>512) fbsize-=512;    /* leave some for someone else */
  767.     if(!(fbuf=malloc(fbsize)))
  768.     {
  769.         printf("Not enough memory\n");
  770.         exit(1);
  771.     }
  772.     lefttoread=ahead.length;    /* file size to process */
  773.     }
  774.     if(!fchunk)
  775.     {
  776.     if(!lefttoread)         /* already read to end of file */
  777.     {
  778.         free(fbuf);         /* return malloc'd memory */
  779.         fbuf=NULL;            /* set indicator for next usage */
  780.         fchunk=fbsize=0;
  781.         return 0xffff;        /* return EOF */
  782.     }
  783.     /* read up to buffersize bytes */
  784.     if(fbsize<lefttoread) fchunk=fbsize;
  785.     else
  786.         fchunk=lefttoread;
  787.     if(read(fileno(filein),fbuf,fchunk)!=fchunk)
  788.     {
  789.         printf( "Read error on input file\n");
  790.         exit(1);
  791.     }
  792.     crc=addcrc(crc,fbuf,fchunk);    /* whiz thru the crc check */
  793.     lefttoread-=fchunk;
  794.  
  795.     fbpos=fbuf;            /* crc    check the fbuf */
  796.     }
  797.  
  798.     fchunk--;
  799.     return *fbpos++ ;
  800. }
  801. /* CRC computation logic
  802.  
  803.    The logic for this method of calculating the CRC 16 bit polynomial
  804.    is taken from an article by David Schwaderer in the April 1985
  805.    issue of PC Tech Journal.
  806. */
  807.  
  808.  
  809.  
  810. int addcrc(crc,cc,i)            /* update a CRC check */
  811. register char  *cc;            /* string to check  */
  812. register int crc,            /* running CRC value */
  813. i;                    /* number of bytes to analyze */
  814. {
  815.     for(cc--;i--;)
  816.     crc=((crc>>8)&0x00ff) ^ crctab[(crc^*++cc)&0x00ff];
  817.     return crc;
  818. }
  819.  
  820. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  821.  *
  822.  * compress filein to fileout
  823.  *
  824.  * Algorithm:  use open addressing double hashing (no chaining) on the
  825.  * prefix code / next character combination.  We do a variant of Knuth's
  826.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  827.  * secondary probe.  Here, the modular division first probe is gives way
  828.  * to a faster exclusive-or manipulation.  Also do block compression with
  829.  * an adaptive reset, whereby the code table is cleared when the compression
  830.  * ratio decreases, but after the table fills.    The variable-length output
  831.  * codes are re-sized at this point, and a special CLEAR code is generated
  832.  * for the decompressor.  Late addition:  construct the table according to
  833.  * file size for noticeable speed improvement on small files.  Please direct
  834.  * questions about this implementation to ames!jaw.
  835.  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  836.  
  837. compress(outf,inf)
  838. FILE *outf,*inf;
  839. {
  840.     register int i = 0;
  841.     int c;
  842.     int ent;
  843.     register int disp;
  844.     register int hsize_reg;
  845.     register int hshift;
  846.     register long fcode;
  847.     offset = 0;
  848.     out_count = 0;
  849.     clear_flg = 0;
  850.     ratio = 0;
  851.     in_count = 1;
  852.     checkpoint = CHECK_GAP;
  853.     maxcode = MAXCODE(INIT_BITS);
  854.     n_bits = INIT_BITS;
  855.     free_ent = FIRST ;
  856.     if(EOF ==(ent= (ahead.atype==8?getc_ncr(inf):myfgetc(inf)) ))return EOF;
  857.     hshift = 0;
  858.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )hshift++;
  859.  
  860.     hshift = 8 - hshift;        /* set hash code range bound */
  861.     hsize_reg = hsize;
  862.     clr_hash();             /* clear hash table */
  863.  
  864.     while((c= (ahead.atype==8?getc_ncr(inf):myfgetc(inf))) !=EOF ) /* until not end of file */
  865.     {
  866.     c&=0xff;
  867.     in_count++;
  868.     fcode = (long) (((long) c << max_bits) + ent);
  869.     i = ((c << hshift) ^ ent);    /* xor hashing */
  870.  
  871.     if ( htab[i] == fcode )
  872.     {
  873.         ent = codetab[i];
  874.         continue;
  875.     }
  876.     else if ( (long)htab[i] < 0 )    /* empty slot */
  877.         goto nomatch;
  878.     disp = hsize_reg - i;        /* secondary hash (after G. Knott) */
  879.     if ( i == 0 )
  880.         disp = 1;
  881. probe:
  882.     if ( (i -= disp) < 0 )
  883.         i += hsize_reg;
  884.  
  885.     if ( htab [i] == fcode )
  886.     {
  887.         ent = codetab[i];
  888.         continue;
  889.     }
  890.     if ( (long)htab[i] > 0 )
  891.         goto probe;
  892. nomatch:
  893.     output( (int) ent ,ouhead.l;
  894.     out_count++;
  895.     ent = c;
  896.     if ( free_ent < maxmaxcode )
  897.     {
  898.         codetab[i] = free_ent++;    /* code -> hashtable */
  899.         htab[i] = fcode;
  900.     }
  901.     else if ( (long)in_count >= checkpoint )
  902.         cl_block ();
  903.     }
  904.     /*
  905.      * Put out the final code.
  906.      */
  907.     output( ( int)ent,ouhf);
  908.     out_count++;
  909.     output( ( int)-1,outf);
  910.  
  911. }
  912.  
  913. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  914.  
  915. Initiate a file decompression
  916.  
  917. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  918.  
  919. #ifndef EOF                /* include if never done before */
  920. #include <stdio.h>
  921. #include <ctype.h>            /* class tests */
  922. #include <squash.h>
  923. #endif
  924.  
  925. dodecompress(outf,inf,fileid)
  926. FILE *outf,*inf;
  927. char *fileid;
  928. {
  929.     if(0x1a!=ahead.archmark || (ahead.atype!=8&&ahead.atype!=9))
  930.     {
  931.     printf( "%s: not in compressed format\n",fileid);
  932.     return(-1);
  933.     }
  934.     lzwsize=ahead.lzwsize;        /* amount to read */
  935.     if(ahead.atype==8)
  936.     {
  937.     hsize=5003;
  938.     if(12!=(max_bits=getc_unp(inf)))
  939.     {
  940.         printf("\nCannot continue. %s is non-standard archive\n",fileid);
  941.         exit(1);
  942.     }
  943.     state=NOHIST;
  944.     }
  945.     else
  946.     {
  947.     max_bits=BITS;
  948.     hsize=9001;
  949.     }
  950.     maxmaxcode = 1 << max_bits;
  951.     crc=0;                /* for crc check */
  952.     decompress(outf,inf );
  953.     if(crc!=ahead.crc)printf("CRC error detected on file %s\n",fileid);
  954.     return (crc);
  955. }
  956. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  957.  
  958.   Decompress filein to fileout.  This routine adapts to the codes in the
  959.   file building the "string" table on-the-fly; requiring no table to
  960.   be stored in the compressed file.  The tables used herein are shared
  961.   with those of the compress() routine.  See the definitions above.
  962.  
  963. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  964.  
  965. decompress(outf,inf)
  966. FILE *outf,*inf;
  967. {
  968.     register unsigned char *stackp;
  969.     register int finchar;
  970.     register int code, oldcode;
  971.     int incode,j;
  972.  
  973.     /*
  974.      * As above, initialize the first 256 entries in the table.
  975.      */
  976.  
  977.     maxcode = MAXCODE(INIT_BITS);
  978.     n_bits = INIT_BITS;
  979.     for ( code = 255; code >= 0; code-- )
  980.     {
  981.     tab_prefixof(code) = 0;
  982.     tab_suffixof(code) = (unsigned char)code;
  983.     }
  984.     free_ent = FIRST;
  985.     incode=finchar = oldcode = getcode(inf);
  986.     if(oldcode == -1)            /* EOF already? */
  987.     return;             /* Get out of here */
  988.     crc=addcrc(crc,&incode,1);        /* calc the crc */
  989.     write(fileno(outf),&incode,sizeof(char));/* first code must be 8 bits = char */
  990.     if(ferror(outf))            /* Crash if can't write */
  991.     writeerr();
  992.     stackp = de_stack;
  993.  
  994.     while ( (code = getcode(inf)) > -1 )
  995.     {
  996.     if ( (code == CLEAR) )
  997.     {
  998.         for ( code = 255; code >= 0; code-- )
  999.         tab_prefixof(code) = 0;
  1000.         clear_flg = 1;
  1001.         free_ent = FIRST - 1;
  1002.         if ( (code = getcode (inf)) == -1 ) /* O, untimely death! */
  1003.         {
  1004.         break;
  1005.         }
  1006.     }
  1007.     incode = code;
  1008.     /*
  1009.      * Special case for KwKwK string.
  1010.      */
  1011.     if ( code >= free_ent )
  1012.     {
  1013.         *stackp++ = finchar;
  1014.         code = oldcode;
  1015.     }
  1016.  
  1017.     /*
  1018.      * Generate output characters in reverse order
  1019.      * Stop if input code is in range 0..255
  1020.      */
  1021.     while ( code >= 256 )
  1022.     {
  1023.         *stackp++ = tab_suffixof(code);
  1024.         code = tab_prefixof(code);
  1025.     }
  1026.     *stackp++ = finchar = tab_suffixof(code);
  1027.     /*
  1028.      * And put them out in forward order
  1029.      */
  1030.     if(ahead.atype==9)
  1031.     {
  1032.         if(1<(j=stackp-de_stack))    /* number of bytes in the string */
  1033.         memrev(de_stack,j);    /* reverse the string in place */
  1034.         crc=addcrc(crc,de_stack,j);
  1035.         if(write(fileno(outf),stackp=de_stack,j)!=j)
  1036.         {
  1037.         printf("Outfile error, disk full???\n");
  1038.         writeerr();
  1039.         }
  1040.     }
  1041.     else
  1042.     {                /* ahead.atype==8  */
  1043.         do
  1044.         putc_ncr(*--stackp,outf);
  1045.         while ( stackp > de_stack );
  1046.     }
  1047.     /*
  1048.      * Generate the new entry.
  1049.      */
  1050.     if ( (code=free_ent) < maxmaxcode )
  1051.     {
  1052.         tab_prefixof(code) = (unsigned short)oldcode;
  1053.         tab_suffixof(code) = finchar;
  1054.         free_ent = code+1;
  1055.     }
  1056.     /*
  1057.      * Remember previous code.
  1058.      */
  1059.     oldcode = incode;
  1060.     }
  1061.     setstamp(outf,ahead.date,ahead.time);
  1062.     if(ferror(outf))writeerr();
  1063. }                    /* end decompress */
  1064.  
  1065. getstamp(f,date,time)            /* get a file's date/time stamp */
  1066. FILE *f;                /* file to get stamp from */
  1067. unsigned *date, *time;            /* storage for the stamp */
  1068. {
  1069.     struct WORDREGS reg;
  1070.  
  1071.     reg.ax = 0x5700;            /* get date/time */
  1072.     reg.bx = fileno(f);         /* file handle */
  1073.     intdos(®,®);            /* DOS call */
  1074.     if(reg.cflag )            /* DOS call */
  1075.     printf("Get timestamp fail (%d)\n",reg.ax);
  1076.  
  1077.     *date = reg.dx;            /* save date/time */
  1078.     *time = reg.cx;
  1079. }                    /* getstamp */
  1080. setstamp(f,date,time)            /* set a file's date/time stamp */
  1081. FILE *f;                /* file to set stamp on */
  1082. int date, time;             /* desired date, time */
  1083. {
  1084.  
  1085.     struct WORDREGS reg;
  1086.     fflush(f);                /* force any pending output */
  1087.     reg.ax = 0x5701;            /* set date/time */
  1088.     reg.bx = fileno(f);         /* file handle */
  1089.     reg.cx = time;            /* desired time */
  1090.     reg.dx = date;            /* desired date */
  1091.     intdos(®,®);            /* DOS call */
  1092.     if(reg.cflag)            /* DOS call */
  1093.     printf("Set timestamp fail (%d)\n",reg.ax);
  1094. }                    /* setstamp */
  1095. /*;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  1096.  
  1097. Memrev      reverse string in memory;
  1098.  
  1099. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;*/
  1100.  
  1101. memrev(str,len)
  1102. register unsigned char *str;
  1103. unsigned len;
  1104. {
  1105.     register unsigned char *end;
  1106.     unsigned char i;
  1107.     end=str+len-1;
  1108.     for(len>>=1;len--;)
  1109.     {
  1110.     i=*str;
  1111.     *str++=*end;
  1112.     *end--=i;
  1113.     }
  1114. }
  1115. int       getc_ncr(f)            /* get bytes with collapsed runs */
  1116. FILE *f;                /* file to get from */
  1117. {
  1118.     static int lastc;            /* value returned on last call */
  1119.     static int repcnt;            /* repetition counter */
  1120.     static int c;            /* latest value seen */
  1121.  
  1122.     switch(state)
  1123.     {                    /* depends on our state */
  1124.     case NOHIST:            /* no relevant history */
  1125.     state = SENTCHAR;
  1126.     return lastc = myfgetc(f);    /* remember the value next time */
  1127.  
  1128.     case SENTCHAR:            /* char was sent. look ahead */
  1129.     switch(lastc)
  1130.     {                /* action depends on char */
  1131.     case DLE:            /* if we sent a real DLE */
  1132.         state = NOHIST;        /* then start over again */
  1133.         return 0;            /* but note that the DLE was real */
  1134.  
  1135.     case EOF:            /* EOF is always a special case */
  1136.         return EOF;
  1137.  
  1138.     default:            /* else test for a repeat */
  1139.         for(repcnt=1; (c=myfgetc(f))==lastc && repcnt<255; repcnt++)
  1140.         ;            /* find end of run */
  1141.  
  1142.         switch(repcnt)
  1143.         {                /* action depends on run size */
  1144.  
  1145.         case 1:            /* not a repeat */
  1146.         return lastc = c;    /* but remember value next time */
  1147.  
  1148.         case 2:            /* a repeat, but too short */
  1149.         state = SENDNEWC;    /* send the second one next time */
  1150.         return lastc;
  1151.  
  1152.         default:            /* a run - compress it */
  1153.         state = SENDCNT;    /* send repeat count next time */
  1154.         return DLE;        /* send repeat marker this time */
  1155.         }
  1156.     }
  1157.  
  1158.     case SENDNEWC:            /* send second char of short run */
  1159.     state = SENTCHAR;
  1160.     return lastc = c;
  1161.  
  1162.     case SENDCNT:            /* sent DLE, now send count */
  1163.     state = SENDNEWC;
  1164.     return repcnt;
  1165.  
  1166.     default:
  1167.     printf("Bug - bad ncr state\n");
  1168.     }
  1169. }                    /* getc_ncr */
  1170. pascal putc_unp(c,t)            /* output an unpacked byte */
  1171. char c;                 /* byte to output */
  1172. FILE *t;                /* file to output to */
  1173. {
  1174.     crc = addcrc(crc,&c,1);        /* update the CRC check value */
  1175.     if(fputc(c,t)==EOF)         /* if to console then ignore error */
  1176.     {
  1177.     printf("Disk full???\n");
  1178.     exit(1);
  1179.     }
  1180. }
  1181.  
  1182. /*  This routine is used to decode non-repeat compression.  Bytes are
  1183.     passed one at a time in coded format, and are written out uncoded.
  1184.     The data is stored normally, except that runs of more than two
  1185.     characters are represented as:
  1186.  
  1187.      <char> <DLE> <count>
  1188.  
  1189.     With a special case that a count of zero indicates a DLE as data,
  1190.     not as a repeat marker.
  1191. */
  1192. putc_ncr(c,t)                /* put NCR coded bytes */
  1193. unsigned char c;            /* next byte of stream */
  1194. FILE *t;                /* file to receive data */
  1195. {
  1196.     static int lastc;            /* last character seen */
  1197.  
  1198.     switch(state)
  1199.     {                    /* action depends on our state */
  1200.  
  1201.     case NOHIST:            /* no previous history */
  1202.     if(c==DLE)            /* if starting a series */
  1203.         state = INREP;        /* then remember it next time */
  1204.     else putc_unp(lastc=c,t);    /* else nothing unusual */
  1205.     return;
  1206.  
  1207.     case INREP:             /* in a repeat */
  1208.     if(c)                /* if count is nonzero */
  1209.         while(--c)            /* then repeatedly ... */
  1210.         putc_unp(lastc,t);    /* ... output the byte */
  1211.     else putc_unp(DLE,t);        /* else output DLE as data */
  1212.     state = NOHIST;         /* back to no history */
  1213.     return;
  1214.  
  1215.     default:
  1216.     printf("Incorrect NCR unpacking state (%d)",state);
  1217.     return 1;
  1218.     }
  1219. }
  1220. int getc_unp(f)             /* get a byte from an archive */
  1221. FILE *f;                /* archive file to read */
  1222. {
  1223.     static unsigned getc_wrk=0;
  1224.     if(!getc_wrk)            /* less overhead to manage ints */
  1225.     {
  1226.     /* then indicate end of file */
  1227.     if(!lzwsize) return EOF;    /* if no data left */
  1228.     else
  1229.     {
  1230.         getc_wrk=0xffff;        /* the maximum int */
  1231.         if(getc_wrk>lzwsize) getc_wrk=lzwsize;
  1232.         lzwsize-=getc_wrk;
  1233.     }
  1234.     }
  1235.     getc_wrk--;             /* deduct from input counter */
  1236.     return fgetc(f) ;            /* and return next decoded byte */
  1237. }
  1238.