home *** CD-ROM | disk | FTP | other *** search
/ back2roots/padua / padua.7z / padua / uucp / duucp-1.17 / AU-117b4-src.lha / src / lib / uccompress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-27  |  28.0 KB  |  966 lines
  1. /*
  2.  * Copyright (c) 1985, 1986 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * James A. Woods, derived from original work by Spencer Thomas
  7.  * and Joseph Orost.
  8.  *
  9.  * Redistribution and use in source and binary forms are permitted
  10.  * provided that: (1) source distributions retain this entire copyright
  11.  * notice and comment, and (2) distributions including binaries display
  12.  * the following acknowledgement:  ``This product includes software
  13.  * developed by the University of California, Berkeley and its contributors''
  14.  * in the documentation or other materials provided with the distribution
  15.  * and in all advertising materials mentioning features or use of this
  16.  * software. Neither the name of the University nor the names of its
  17.  * contributors may be used to endorse or promote products derived
  18.  * from this software without specific prior written permission.
  19.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  20.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  21.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  22.  */
  23.  
  24.  
  25. #ifndef lint
  26. static char copyright[] =
  27. "@(#) Copyright (c) 1985, 1986 The Regents of the University of California.\n\
  28.  All rights reserved.\n";
  29. #endif /* not lint */
  30.  
  31. #ifndef lint
  32. static char sccsid[] = "@(#)compress.c  5.12 (Berkeley) 6/1/90";
  33. #endif /* not lint */
  34.  
  35. #define BITS 16
  36.  
  37. /*
  38.  * Compress - data compression program
  39.  */
  40. /*#define min(a,b)        ((a>b) ? b : a)
  41. */
  42.  
  43. /*
  44.  * Set USERMEM to the maximum amount of physical user memory available
  45.  * in bytes.  USERMEM is used to determine the maximum BITS that can be used
  46.  * for compression.
  47.  *
  48.  * SACREDMEM is the amount of physical memory saved for others; compress
  49.  * will hog the rest.
  50.  */
  51. #ifndef SACREDMEM
  52. #define SACREDMEM       0
  53. #endif
  54.  
  55. #ifndef USERMEM
  56. # define USERMEM        450000  /* default user memory */
  57. #endif
  58.  
  59. #ifdef USERMEM
  60. # if USERMEM >= (433484+SACREDMEM)
  61. #  define PBITS 16
  62. # else
  63. #  if USERMEM >= (229600+SACREDMEM)
  64. #   define PBITS        15
  65. #  else
  66. #   if USERMEM >= (127536+SACREDMEM)
  67. #    define PBITS       14
  68. #   else
  69. #    if USERMEM >= (73464+SACREDMEM)
  70. #     define PBITS      13
  71. #    else
  72. #     define PBITS      12
  73. #    endif
  74. #   endif
  75. #  endif
  76. # endif
  77. # undef USERMEM
  78. #endif /* USERMEM */
  79.  
  80. #ifdef PBITS            /* Preferred BITS for this memory size */
  81. # ifndef BITS
  82. #  define BITS PBITS
  83. # endif
  84. #endif /* PBITS */
  85.  
  86. #if BITS == 16
  87. # define HSIZE  69001           /* 95% occupancy */
  88. #endif
  89. #if BITS == 15
  90. # define HSIZE  35023           /* 94% occupancy */
  91. #endif
  92. #if BITS == 14
  93. # define HSIZE  18013           /* 91% occupancy */
  94. #endif
  95. #if BITS == 13
  96. # define HSIZE  9001            /* 91% occupancy */
  97. #endif
  98. #if BITS <= 12
  99. # define HSIZE  5003            /* 80% occupancy */
  100. #endif
  101.  
  102. /*
  103.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  104.  */
  105. #if BITS > 15
  106. typedef long int        code_int;
  107. #else
  108. typedef int             code_int;
  109. #endif
  110.  
  111. typedef long int        count_int;
  112. typedef unsigned char   char_type;
  113.  
  114. static char_type magic_header[] = { "\037\235" };      /* 1F 9D */
  115.  
  116. /* Defines for third byte of header */
  117. #define BIT_MASK        0x1f
  118. #define BLOCK_MASK      0x80
  119.  
  120. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  121.    a fourth header byte (for expansion).
  122. */
  123. #define INIT_BITS 9                     /* initial number of bits/code */
  124.  
  125.  
  126. /*
  127.  * compress.c - File compression ala IEEE Computer, June 1984.
  128.  *
  129.  * Authors:     Spencer W. Thomas       (decvax!utah-cs!thomas)
  130.  *              Jim McKie               (decvax!mcvax!jim)
  131.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  132.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  133.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  134.  *              Joe Orost               (decvax!vax135!petsd!joe)
  135.  *
  136.  * Revision 4.0AMIGA
  137.  *      * dynamic allocation so it works with fragmented memory
  138.  *      * #ifdef's for the AMIGA and for #inclusion as core code
  139.  *        to other programs (rnews, cbatch)
  140.  *      * core code returns a value instead of exiting
  141.  *
  142.  * $Header: compress.c,v 4.0 85/07/30 12:50:00 joe Release $
  143.  * $Log:        compress.c,v $
  144.  * Revision 4.0  85/07/30  12:50:00  joe
  145.  * Removed ferror() calls in output routine on every output except first.
  146.  * Prepared for release to the world.
  147.  *
  148.  * Revision 3.6  85/07/04  01:22:21  joe
  149.  * Remove much wasted storage by overlaying hash table with the tables
  150.  * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
  151.  * computations.  Fixed dump_tab() DEBUG routine.
  152.  *
  153.  * Revision 3.5  85/06/30  20:47:21  jaw
  154.  * Change hash function to use exclusive-or.  Rip out hash cache.  These
  155.  * speedups render the megamemory version defunct, for now.  Make decoder
  156.  * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
  157.  *
  158.  * Revision 3.4  85/06/27  12:00:00  ken
  159.  * Get rid of all floating-point calculations by doing all compression ratio
  160.  * calculations in fixed point.
  161.  *
  162.  * Revision 3.3  85/06/24  21:53:24  joe
  163.  * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
  164.  * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
  165.  *
  166.  * Revision 3.2  85/06/06  21:53:24  jaw
  167.  * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
  168.  * Default to "quiet" output (no compression statistics).
  169.  *
  170.  * Revision 3.1  85/05/12  18:56:13  jaw
  171.  * Integrate decompress() stack speedups (from early pointer mods by McKie).
  172.  * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
  173.  * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase
  174.  * output byte count by magic number size.
  175.  *
  176.  * Revision 3.0   84/11/27  11:50:00  petsd!joe
  177.  * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
  178.  * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
  179.  * unsigned compares on Perkin-Elmer.  Fixed foreground check.
  180.  *
  181.  * Revision 2.7   84/11/16  19:35:39  ames!jaw
  182.  * Cache common hash codes based on input statistics; this improves
  183.  * performance for low-density raster images.  Pass on #ifdef bundle
  184.  * from Turkowski.
  185.  *
  186.  * Revision 2.6   84/11/05  19:18:21  ames!jaw
  187.  * Vary size of hash tables to reduce time for small files.
  188.  * Tune PDP-11 hash function.
  189.  *
  190.  * Revision 2.5   84/10/30  20:15:14  ames!jaw
  191.  * Junk chaining; replace with the simpler (and, on the VAX, faster)
  192.  * double hashing, discussed within.  Make block compression standard.
  193.  *
  194.  * Revision 2.4   84/10/16  11:11:11  ames!jaw
  195.  * Introduce adaptive reset for block compression, to boost the rate
  196.  * another several percent.  (See mailing list notes.)
  197.  *
  198.  * Revision 2.3   84/09/22  22:00:00  petsd!joe
  199.  * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
  200.  * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
  201.  *
  202.  * Revision 2.2   84/09/18  14:12:21  ames!jaw
  203.  * Fold in news changes, small machine typedef from thomas,
  204.  * #ifdef interdata from joe.
  205.  *
  206.  * Revision 2.1   84/09/10  12:34:56  ames!jaw
  207.  * Configured fast table lookup for 32-bit machines.
  208.  * This cuts user time in half for b <= FBITS, and is useful for news batching
  209.  * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
  210.  * added signal catcher [plus beef in writeerr()] to delete effluvia.
  211.  *
  212.  * Revision 2.0   84/08/28  22:00:00  petsd!joe
  213.  * Add check for foreground before prompting user.  Insert maxbits into
  214.  * compressed file.  Force file being uncompressed to end with ".Z".
  215.  * Added "-c" flag and "zcat".  Prepared for release.
  216.  *
  217.  * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
  218.  * Will only compress regular files (no directories), added a magic number
  219.  * header (plus an undocumented -n flag to handle old files without headers),
  220.  * added -f flag to force overwriting of possibly existing destination file,
  221.  * otherwise the user is prompted for a response.  Will tack on a .Z to a
  222.  * filename if it doesn't have one when decompressing.  Will only replace
  223.  * file if it was compressed.
  224.  *
  225.  * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
  226.  * Removed scanargs(), getopt(), added .Z extension and unlimited number of
  227.  * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
  228.  * (-D -d -v -b 12), or combination thereof.  Modes and other status is
  229.  * copied with copystat().  -O bug for 4.2 seems to have disappeared with
  230.  * 1.8.
  231.  *
  232.  * Revision 1.8  84/08/09  23:15:00  joe
  233.  * Made it compatible with vax version, installed jim's fixes/enhancements
  234.  *
  235.  * Revision 1.6  84/08/01  22:08:00  joe
  236.  * Sped up algorithm significantly by sorting the compress chain.
  237.  *
  238.  * Revision 1.5  84/07/13  13:11:00  srd
  239.  * Added C version of vax asm routines.  Changed structure to arrays to
  240.  * save much memory.  Do unsigned compares where possible (faster on
  241.  * Perkin-Elmer)
  242.  *
  243.  * Revision 1.4  84/07/05  03:11:11  thomas
  244.  * Clean up the code a little and lint it.  (Lint complains about all
  245.  * the regs used in the asm, but I'm not going to "fix" this.)
  246.  *
  247.  * Revision 1.3  84/07/05  02:06:54  thomas
  248.  * Minor fixes.
  249.  *
  250.  * Revision 1.2  84/07/05  00:27:27  thomas
  251.  * Add variable bit length output.
  252.  *
  253.  */
  254. static char rcs_ident[] = "$Header: compress.c,v 4.0AMIGA 85/07/30 12:50:00 joe Release $";
  255.  
  256. #include <stdio.h>
  257. #include <ctype.h>
  258. #include <sys/types.h>
  259. #include <sys/stat.h>
  260.  
  261. #include <time.h>               /*  time_t              */
  262. #include <stdlib.h>
  263. #include <string.h>
  264.  
  265. #include <config.h>
  266.  
  267. Prototype int  initcomp(FILE *fi, FILE *fo, int bits, int logbits, int logerr);
  268. Prototype void deletecomp(void);
  269. Prototype int  compress(FILE *fi, FILE *fo);
  270. Prototype int  decompress(FILE *fi, FILE *fo, short *pbits);
  271.  
  272. static void output(code_int code, FILE *fo);
  273. static code_int getcode(FILE *fi);
  274. static void cl_block (FILE *fo);
  275. static void cl_hash(count_int hsize);
  276. static void prratio(FILE*, long, long);
  277.  
  278. static int logerr = 0;
  279.  
  280. static int n_bits;                             /* number of bits/code */
  281. static int maxbits = BITS;                     /* user settable max # bits/code */
  282. static code_int maxcode;                       /* maximum code, given n_bits */
  283. static code_int maxmaxcode = 1 << BITS;        /* should NEVER generate this code */
  284.  
  285. # define MAXCODE(n_bits)        ((1 << (n_bits)) - 1)
  286.  
  287. static count_int *htab[9];
  288.  
  289. #define htabof(i)       (htab[(i) >> 13][(i) & 0x1fff])
  290.  
  291. static unsigned short *codetab[5];
  292.  
  293. #define codetabof(i)    (codetab[(i) >> 14][(i) & 0x3fff])
  294.  
  295.  
  296. static code_int hsize = HSIZE;                 /* for dynamic table sizing */
  297. static count_int fsize;
  298. static int gc_offset = 0, gc_size = 0;
  299.  
  300. /*
  301.  * To save much memory, we overlay the table used by compress() with those
  302.  * used by decompress().  The tab_prefix table is the same size and type
  303.  * as the codetab.  The tab_suffix table needs 2**BITS characters.  We
  304.  * get this from the beginning of htab.  The output stack uses the rest
  305.  * of htab, and contains characters.  There is plenty of room for any
  306.  * possible stack (stack used to be 8000 characters).
  307.  */
  308.  
  309. #define tab_prefixof(i) codetabof(i)
  310. #define tab_suffixof(i) ((char_type *)htab[(i)>>15])[(i) & 0x7fff]
  311.  
  312. /*
  313.  *  it looked wrong the way it was before, so de_stack is back to normal
  314.  */
  315. static char_type de_stack[24000];
  316.  
  317. static code_int free_ent = 0;                  /* first unused entry */
  318. static int exit_stat = 0;                      /* per-file status */
  319. static int perm_stat = 0;                      /* permanent status */
  320.  
  321. static int nomagic = 0;        /* Use a 3-byte magic number header, unless old file */
  322. static int zcat_flg = 0;       /* Write output on stdout, suppress messages */
  323. static int precious = 1;       /* Don't unlink output file on interrupt */
  324. static int quiet = 1;          /* don't tell me about compression */
  325.  
  326. /*
  327.  * block compression parameters -- after all codes are used up,
  328.  * and compression rate changes, start over.
  329.  */
  330. static int block_compress = BLOCK_MASK;
  331. static int clear_flg = 0;
  332. static long int ratio = 0;
  333. #define CHECK_GAP 10000 /* ratio check interval */
  334. static count_int checkpoint = CHECK_GAP;
  335. /*
  336.  * the next two codes should not be changed lightly, as they must not
  337.  * lie within the contiguous general code space.
  338.  */
  339. #define FIRST   257     /* first free entry */
  340. #define CLEAR   256     /* table clear output code */
  341.  
  342. static int force = 0;
  343. static char ofname [100];
  344.  
  345. static int bgnd_flag;
  346.  
  347. static int do_decomp = 0;
  348.  
  349. static int offset;
  350. static long int in_count = 1;           /* length of input */
  351. static long int bytes_out;              /* length of compressed output */
  352. static long int out_count = 0;          /* # of codes output (for debugging) */
  353.  
  354. int
  355. initcomp(fi, fo, bits, logbits, logerror)
  356. FILE *fi;
  357. FILE *fo;
  358. int bits;
  359. int logbits;
  360. int logerror;
  361. {
  362.     logerr = logerror;
  363.  
  364.     if (bits < 0)                       /*  block compress */
  365.         bits = -bits | BLOCK_MASK;
  366.  
  367.     if (fi) {
  368.         if ((getc(fi)!=(magic_header[0] & 0xFF))
  369.         || (getc(fi)!=(magic_header[1] & 0xFF))) {
  370.                 return(-1);
  371.         }
  372.         bits = getc(fi);  /* set -b from file */
  373.     }
  374.  
  375.     block_compress = bits & BLOCK_MASK;
  376.     bits &= BIT_MASK;
  377.     maxmaxcode = ((code_int)1) << bits;
  378.     maxbits = bits;
  379.  
  380.     /*
  381.      *  some of these might be redundant
  382.      */
  383.  
  384.     offset = clear_flg = ratio = 0;
  385.     gc_offset = gc_size = 0;
  386.     in_count = 1;
  387.     checkpoint = CHECK_GAP;
  388.     n_bits = INIT_BITS;
  389.     maxcode = MAXCODE(INIT_BITS);
  390.     free_ent = ((block_compress) ? FIRST : 256);
  391.  
  392.     /*
  393.      *  set hsize
  394.      */
  395.  
  396.     switch(bits) {
  397.     case 16:
  398.         hsize = 69001;
  399.         break;
  400.     case 15:
  401.         hsize = 35023;
  402.         break;
  403.     case 14:
  404.         hsize = 18013;
  405.         break;
  406.     case 13:
  407.         hsize = 9001;
  408.         break;
  409.     default:
  410.         hsize = 5003;       /*  note: de_stack still fits   */
  411.         break;
  412.     }
  413.  
  414.     if (logbits)
  415.         ulog(1, "[de]compress bits=%d", bits);
  416.  
  417.     {
  418.         int i;
  419.         long n;
  420.  
  421.         for (i = 0, n = hsize; i < 9 && n > 0; ++i) {
  422.             long entries = (n > 8192) ? 8192 : n;
  423.  
  424.             if ((htab[i] = calloc(1, sizeof(count_int) * entries)) == NULL) {
  425.                 fprintf(stderr, "no memory\n");
  426.                 exit(20);
  427.             }
  428.             n -= entries;
  429.         }
  430.  
  431.         for (i = 0, n = hsize; i < 5 && n > 0; ++i) {
  432.             long entries = (n > 16384) ? 16384 : n;
  433.  
  434.             if ((codetab[i] = calloc(1, sizeof(short) * entries)) == NULL) {
  435.                 fprintf(stderr, "no memory\n");
  436.                 exit(20);
  437.             }
  438.             n -= entries;
  439.         }
  440.     }
  441.     return(0);
  442. }
  443.  
  444. void
  445. deletecomp(void)
  446. {
  447.     int i;
  448.  
  449.     for (i = 0; i < sizeof(htab)/sizeof(htab[0]); ++i) {
  450.         if (htab[i]) {
  451.             free(htab[i]);
  452.             htab[i] = NULL;
  453.         }
  454.     }
  455.     for (i = 0; i < sizeof(codetab)/sizeof(codetab[0]); ++i) {
  456.         if (codetab[i]) {
  457.             free(codetab[i]);
  458.             codetab[i] = NULL;
  459.         }
  460.     }
  461. }
  462.  
  463. /*
  464.  * compress stdin to stdout
  465.  *
  466.  * Algorithm:  use open addressing double hashing (no chaining) on the
  467.  * prefix code / next character combination.  We do a variant of Knuth's
  468.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  469.  * secondary probe.  Here, the modular division first probe is gives way
  470.  * to a faster exclusive-or manipulation.  Also do block compression with
  471.  * an adaptive reset, whereby the code table is cleared when the compression
  472.  * ratio decreases, but after the table fills.  The variable-length output
  473.  * codes are re-sized at this point, and a special CLEAR code is generated
  474.  * for the decompressor.  Late addition:  construct the table according to
  475.  * file size for noticeable speed improvement on small files.  Please direct
  476.  * questions about this implementation to ames!jaw.
  477.  */
  478.  
  479. int
  480. compress(fi, fo)
  481. FILE *fi;
  482. FILE *fo;
  483. {
  484.     register long fcode;
  485.     register code_int i = 0;
  486.     register int c;
  487.     register code_int ent;
  488.     register code_int disp;
  489.     register code_int hsize_reg;
  490.     register int hshift;
  491.  
  492.     if (nomagic == 0) {
  493.         fputc(magic_header[0], fo); fputc(magic_header[1], fo);
  494.         fputc((char)(maxbits | block_compress), fo);
  495.         if (ferror(fo))
  496.             return(-1);
  497.     }
  498.  
  499.     offset = 0;
  500.     bytes_out = 3;              /* includes 3-byte header mojo */
  501.     out_count = 0;
  502.     clear_flg = 0;
  503.     ratio = 0;
  504.     in_count = 1;
  505.     checkpoint = CHECK_GAP;
  506.     maxcode = MAXCODE(n_bits = INIT_BITS);
  507.     free_ent = ((block_compress) ? FIRST : 256 );
  508.  
  509.     ent = fgetc(fi);
  510.  
  511.     hshift = 0;
  512.     for ( fcode = (long) hsize;  fcode < 65536L; fcode *= 2L )
  513.         hshift++;
  514.     hshift = 8 - hshift;                /* set hash code range bound */
  515.  
  516.     hsize_reg = hsize;
  517.     cl_hash( (count_int) hsize_reg);            /* clear hash table */
  518.  
  519.     while ( (c = fgetc(fi)) != EOF ) {
  520.         in_count++;
  521.         fcode = (long) (((long) c << maxbits) + ent);
  522.         i = ((c << hshift) ^ ent);      /* xor hashing */
  523.  
  524.         if ( htabof (i) == fcode ) {
  525.             ent = codetabof (i);
  526.             continue;
  527.         } else if ( (long)htabof (i) < 0 )      /* empty slot */
  528.             goto nomatch;
  529.         disp = hsize_reg - i;           /* secondary hash (after G. Knott) */
  530.         if ( i == 0 )
  531.             disp = 1;
  532. probe:
  533.         if ( (i -= disp) < 0 )
  534.             i += hsize_reg;
  535.  
  536.         if ( htabof (i) == fcode ) {
  537.             ent = codetabof (i);
  538.             continue;
  539.         }
  540.         if ( (long)htabof (i) > 0 )
  541.             goto probe;
  542. nomatch:
  543.         output ( (code_int) ent, fo );
  544.         out_count++;
  545.         ent = c;
  546.         if ( free_ent < maxmaxcode ) {
  547.             codetabof (i) = free_ent++; /* code -> hashtable */
  548.             htabof (i) =  fcode;
  549.         }
  550.         else if ( (count_int)in_count >= checkpoint && block_compress )
  551.             cl_block (fo);
  552.     }
  553.     /*
  554.      * Put out the final code.
  555.      */
  556.     output( (code_int)ent, fo );
  557.     out_count++;
  558.     output( (code_int)-1, fo );
  559.  
  560.     /*
  561.      * Print out stats on stderr
  562.      */
  563.     if(zcat_flg == 0 && !quiet) {
  564.         fprintf( stderr, "Compression: " );
  565.         prratio( stderr, in_count-bytes_out, in_count );
  566.     }
  567.     if(bytes_out > in_count)    /* exit(2) if no savings */
  568.         exit_stat = 2;
  569.     if (ferror(fo))
  570.         return(-1);
  571.     return(0);
  572. }
  573.  
  574. /*****************************************************************
  575.  * TAG( output )
  576.  *
  577.  * Output the given code.
  578.  * Inputs:
  579.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  580.  *              that n_bits =< (long)wordsize - 1.
  581.  * Outputs:
  582.  *      Outputs code to the file.
  583.  * Assumptions:
  584.  *      Chars are 8 bits long.
  585.  * Algorithm:
  586.  *      Maintain a BITS character long buffer (so that 8 codes will
  587.  * fit in it exactly).  Use the VAX insv instruction to insert each
  588.  * code in turn.  When the buffer fills up empty it and start over.
  589.  */
  590.  
  591. static char buf[BITS];
  592.  
  593. static char_type lmask[9] = {0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00};
  594. static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  595.  
  596. static
  597. void
  598. output( code, fo )
  599. code_int  code;
  600. FILE *fo;
  601. {
  602.     /*
  603.      * On the VAX, it is important to have the register declarations
  604.      * in exactly the order given, or the asm will break.
  605.      */
  606.     register int r_off = offset, bits= n_bits;
  607.     register char * bp = buf;
  608.  
  609.     if ( code >= 0 ) {
  610. /*
  611.  * byte/bit numbering on the VAX is simulated by the following code
  612.  */
  613.         /*
  614.          * Get to the first byte.
  615.          */
  616.         bp += (r_off >> 3);
  617.         r_off &= 7;
  618.         /*
  619.          * Since code is always >= 8 bits, only need to mask the first
  620.          * hunk on the left.
  621.          */
  622.         *bp = (*bp & rmask[r_off]) | (code << r_off) & lmask[r_off];
  623.         bp++;
  624.         bits -= (8 - r_off);
  625.         code >>= 8 - r_off;
  626.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  627.         if ( bits >= 8 ) {
  628.             *bp++ = code;
  629.             code >>= 8;
  630.             bits -= 8;
  631.         }
  632.         /* Last bits. */
  633.         if(bits)
  634.             *bp = code;
  635.  
  636.         offset += n_bits;
  637.         if ( offset == (n_bits << 3) ) {
  638.             bp = buf;
  639.             bits = n_bits;
  640.             bytes_out += bits;
  641.             do
  642.                 fputc(*bp++, fo);
  643.             while(--bits);
  644.             offset = 0;
  645.         }
  646.  
  647.         /*
  648.          * If the next entry is going to be too big for the code size,
  649.          * then increase it, if possible.
  650.          */
  651.         if ( free_ent > maxcode || (clear_flg > 0))
  652.         {
  653.             /*
  654.              * Write the whole buffer, because the input side won't
  655.              * discover the size increase until after it has read it.
  656.              */
  657.             if ( offset > 0 ) {
  658.                 fwrite( buf, 1, n_bits, fo );
  659.                 bytes_out += n_bits;
  660.             }
  661.             offset = 0;
  662.  
  663.             if ( clear_flg ) {
  664.                 maxcode = MAXCODE (n_bits = INIT_BITS);
  665.                 clear_flg = 0;
  666.             }
  667.             else {
  668.                 n_bits++;
  669.                 if ( n_bits == maxbits )
  670.                     maxcode = maxmaxcode;
  671.                 else
  672.                     maxcode = MAXCODE(n_bits);
  673.             }
  674.         }
  675.     } else {
  676.         /*
  677.          * At EOF, write the rest of the buffer.
  678.          */
  679.         if ( offset > 0 )
  680.             fwrite( buf, 1, (offset + 7) / 8, fo );
  681.         bytes_out += (offset + 7) / 8;
  682.         offset = 0;
  683.         fflush( fo );
  684.     }
  685. }
  686.  
  687. /*
  688.  * Decompress stdin to stdout.  This routine adapts to the codes in the
  689.  * file building the "string" table on-the-fly; requiring no table to
  690.  * be stored in the compressed file.  The tables used herein are shared
  691.  * with those of the compress() routine.  See the definitions above.
  692.  */
  693.  
  694. int
  695. decompress(fi, fo, pbits)
  696. FILE *fi;
  697. FILE *fo;
  698. short *pbits;
  699. {
  700.     register char_type *stackp;
  701.     register int finchar;
  702.     register code_int code, oldcode, incode;
  703.  
  704.     /*
  705.      * As above, initialize the first 256 entries in the table.
  706.      */
  707.     maxcode = MAXCODE(n_bits = INIT_BITS);
  708.     for ( code = 255; code >= 0; code-- ) {
  709.         tab_prefixof(code) = 0;
  710.         tab_suffixof(code) = (char_type)code;
  711.     }
  712.     free_ent = ((block_compress) ? FIRST : 256 );
  713.  
  714.     finchar = oldcode = getcode(fi);
  715.     if(oldcode == -1)   /* EOF already? */
  716.         return(-1);             /* Get out of here */
  717.     fputc( (char)finchar, fo ); /* first code must be 8 bits = char */
  718.     if(ferror(fo))          /* Crash if can't write */
  719.         return(-1);
  720.     stackp = de_stack;
  721.  
  722.     while ( (code = getcode(fi)) > -1 ) {
  723.  
  724.         if ( (code == CLEAR) && block_compress ) {
  725.             for ( code = 255; code >= 0; code-- )
  726.                 tab_prefixof(code) = 0;
  727.             clear_flg = 1;
  728.             free_ent = FIRST - 1;
  729.             if ( (code = getcode (fi)) == -1 )    /* O, untimely death! */
  730.                 break;
  731.         }
  732.         incode = code;
  733.         /*
  734.          * Special case for KwKwK string.
  735.          */
  736.         if ( code >= free_ent ) {
  737.             *stackp++ = finchar;
  738.             code = oldcode;
  739.         }
  740.  
  741.         /*
  742.          * Generate output characters in reverse order
  743.          */
  744.         while ( code >= 256 ) {
  745.             *stackp++ = tab_suffixof(code);
  746.             code = tab_prefixof(code);
  747.  
  748.             if (stackp == de_stack + sizeof(de_stack)) {
  749.                 --stackp;
  750.  
  751.                 if (logerr)
  752.                     ulog(-1, "UNCOMPRESS ERROR");
  753.  
  754.                 return(-1);
  755.             }
  756.         }
  757.         *stackp++ = finchar = tab_suffixof(code);
  758.  
  759.         /*
  760.          * And put them out in forward order
  761.          */
  762.         do
  763.             fputc ( *--stackp, fo );
  764.         while ( stackp > de_stack );
  765.  
  766.         /*
  767.          * Generate the new entry.
  768.          */
  769.         if ( (code=free_ent) < maxmaxcode ) {
  770.             tab_prefixof(code) = (unsigned short)oldcode;
  771.             tab_suffixof(code) = finchar;
  772.             free_ent = code+1;
  773.         }
  774.         /*
  775.          * Remember previous code.
  776.          */
  777.         oldcode = incode;
  778.     }
  779.  
  780.     fflush( fo );
  781.     if (ferror(fo))
  782.         return(-1);
  783.  
  784.     if (pbits)
  785.         *pbits = maxbits;
  786.  
  787.     return(0);
  788. }
  789.  
  790. /*****************************************************************
  791.  * TAG( getcode )
  792.  *
  793.  * Read one code from the standard input.  If EOF, return -1.
  794.  * Inputs:
  795.  *      stdin
  796.  * Outputs:
  797.  *      code or -1 is returned.
  798.  */
  799.  
  800.  
  801. static
  802. code_int
  803. getcode(fi)
  804. FILE *fi;
  805. {
  806.     /*
  807.      * On the VAX, it is important to have the register declarations
  808.      * in exactly the order given, or the asm will break.
  809.      */
  810.     register code_int code;
  811.     static char_type buf[BITS];
  812.     register int r_off, bits;
  813.     register char_type *bp = buf;
  814.  
  815.     if ( clear_flg > 0 || gc_offset >= gc_size || free_ent > maxcode ) {
  816.         /*
  817.          * If the next entry will be too big for the current code
  818.          * size, then we must increase the size.  This implies reading
  819.          * a new buffer full, too.
  820.          */
  821.         if ( free_ent > maxcode ) {
  822.             n_bits++;
  823.             if ( n_bits == maxbits )
  824.                 maxcode = maxmaxcode;   /* won't get any bigger now */
  825.             else
  826.                 maxcode = MAXCODE(n_bits);
  827.         }
  828.         if ( clear_flg > 0) {
  829.             maxcode = MAXCODE (n_bits = INIT_BITS);
  830.             clear_flg = 0;
  831.         }
  832.         gc_size = fread( buf, 1, n_bits, fi );
  833.         if ( gc_size <= 0 )
  834.             return -1;                  /* end of file */
  835.         gc_offset = 0;
  836.         /* Round size down to integral number of codes */
  837.         gc_size = (gc_size << 3) - (n_bits - 1);
  838.     }
  839.     r_off = gc_offset;
  840.     bits = n_bits;
  841.         /*
  842.          * Get to the first byte.
  843.          */
  844.         bp += (r_off >> 3);
  845.         r_off &= 7;
  846.         /* Get first part (low order bits) */
  847.         code = (*bp++ >> r_off);
  848.         bits -= (8 - r_off);
  849.         r_off = 8 - r_off;              /* now, offset into code word */
  850.         /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  851.         if ( bits >= 8 ) {
  852.             code |= *bp++ << r_off;
  853.             r_off += 8;
  854.             bits -= 8;
  855.         }
  856.         /* high order bits. */
  857.         code |= (*bp & rmask[bits]) << r_off;
  858.  
  859.     gc_offset += n_bits;
  860.     if (code >= maxmaxcode) {
  861.  
  862.         if (logerr)
  863.             ulog(-1, "UNCOMPRESS ERROR");
  864.  
  865.         return(-1);
  866.     }
  867.  
  868.     return code;
  869. }
  870.  
  871. static
  872. void
  873. cl_block (fo)             /* table clear for block compress */
  874. FILE *fo;
  875. {
  876.     register long int rat;
  877.  
  878.     checkpoint = in_count + CHECK_GAP;
  879.  
  880.     if (in_count > 0x007fffff) { /* shift will overflow */
  881.         rat = bytes_out >> 8;
  882.         if(rat == 0) {          /* Don't divide by zero */
  883.             rat = 0x7fffffff;
  884.         } else {
  885.             rat = in_count / rat;
  886.         }
  887.     } else {
  888.         rat = (in_count << 8) / bytes_out;      /* 8 fractional bits */
  889.     }
  890.     if ( rat > ratio ) {
  891.         ratio = rat;
  892.     } else {
  893.         ratio = 0;
  894.         cl_hash ( (count_int) hsize );
  895.         free_ent = FIRST;
  896.         clear_flg = 1;
  897.         output ( (code_int) CLEAR, fo );
  898.     }
  899. }
  900.  
  901. static
  902. void
  903. cl_hash(hsize)          /* reset code table */
  904. register count_int hsize;
  905. {
  906.         register j;
  907.         register long k = hsize;
  908.         register count_int *htab_p;
  909.         register long i;
  910.         register long m1 = -1;
  911.  
  912.     for(j=0; j<=8 && k>=0; j++,k-=8192) {
  913.         i = 8192;
  914.         if(k < 8192) {
  915.                 i = k;
  916.         }
  917.         htab_p = &(htab[j][i]);
  918.         i -= 16;
  919.         if(i > 0) {
  920.  
  921.         do {                            /* might use Sys V memset(3) here */
  922.                 *(htab_p-16) = m1;
  923.                 *(htab_p-15) = m1;
  924.                 *(htab_p-14) = m1;
  925.                 *(htab_p-13) = m1;
  926.                 *(htab_p-12) = m1;
  927.                 *(htab_p-11) = m1;
  928.                 *(htab_p-10) = m1;
  929.                 *(htab_p-9) = m1;
  930.                 *(htab_p-8) = m1;
  931.                 *(htab_p-7) = m1;
  932.                 *(htab_p-6) = m1;
  933.                 *(htab_p-5) = m1;
  934.                 *(htab_p-4) = m1;
  935.                 *(htab_p-3) = m1;
  936.                 *(htab_p-2) = m1;
  937.                 *(htab_p-1) = m1;
  938.                 htab_p -= 16;
  939.         } while ((i -= 16) >= 0);
  940.         }
  941.     }
  942.         for ( i += 16; i > 0; i-- )
  943.                 *--htab_p = m1;
  944. }
  945.  
  946. static
  947. void
  948. prratio(stream, num, den)
  949. FILE *stream;
  950. long int num, den;
  951. {
  952.         register int q;                 /* Doesn't need to be long */
  953.  
  954.         if(num > 214748L) {             /* 2147483647/10000 */
  955.                 q = num / (den / 10000L);
  956.         } else {
  957.                 q = 10000L * num / den;         /* Long calculations, though */
  958.         }
  959.         if (q < 0) {
  960.                 putc('-', stream);
  961.                 q = -q;
  962.         }
  963.         fprintf(stream, "%d.%02d%%", q / 100, q % 100);
  964. }
  965.  
  966.