rev.hst

和Unix的compress/uncompress兼容的压缩/解压算法16位程序

/* $@(#) compress rev.hst,v 4.3 90/01/06 08:00:00 don Release ^
 * compress.c - File compression ala IEEE Computer, June 1984.
 *
 * Authors:
 *      Spencer W. Thomas   (decvax!harpo!utah-cs!utah-gr!thomas)
 *      Jim McKie           (decvax!mcvax!jim)
 *      Steve Davies        (decvax!vax135!petsd!peora!srd)
 *      Ken Turkowski       (decvax!decwrl!turtlevax!ken)
 *      James A. Woods      (decvax!ihnp4!ames!jaw)
 *      Joe Orost           (decvax!vax135!petsd!joe)
 *      Don Gloistein via:  (!rutgers!princeton!mccc!pjh)
 *      Don Gloistein       (Compuserve,Unixforum 76010,474)
 *      Lyle Rains          (Compuserve,Unixforum 72150,324)
 *
 * $Header: compress.c,v 4.3c 90/01/06 08:00:00 don Release $
 * $Log:    compress.c,v $
 *
 * Revision 4.3c  90/01/06 08:00:00 don
 *
 * Fixed dereferenced pointer in error message. 
 * Changed some defines because some 68000 systems with some compilers used
 * sign extension on pointers. See README4.3 for more information.
 *
 * Revision 4.3   89/10/25  08:00:00 don
 *
 * Changed some cosmetics. Revised version() function to clean it up.
 * Revised testing for links. Now done in beginning rather than after a
 * compress. Put all the utility scripts and atob v4 back in so the
 * distributed package now has all the old release 4.0 files.
 *
 * Revision 4.3   89/05/20  08:00:00  don
 *
 * Added changes submitted by Dale Schumacher for Minix version port. One
 * change that affected the rest of the code was the addition of the
 * get_one() function. A somewhat cleaner way of getting console input.
 *
 * Revision 4.3   88/12/26  08:00:00  don
 *
 * Fixed bug with output file always going to the default directory even if
 * filename was fully qualified. Fixed bug with file name > 12 characters.
 * Fixed problem with Atari ST desktop not reading program name properly.
 * Added -B option, same as -b option.
 *
 * Revision 4.2   88/12/18  08:00:00  don
 *
 * Fixed problems with various xenix compilers. Now compiles properly with
 * included makefile.xen in the large model. Fixed error in compusi.uni that
 * tested for the wrong program name. More compatibility changes. Fixed
 * problem with os/2 operating system. Streams now closed before unlinks.
 *
 * Replaced adaptive reset of tables as an option in the code. This will
 * result with smaller compressed files at a sacrifice of some processing
 * speed. It is smaller only on files that push compress to 16 bits.
 *
 * Revision 4.1e  88/12/11  22:00:00  don
 *
 * Re-established unix defaults for all versions; i.e., it now will unlink
 * input file on success and operates as full unix filter. Changed some
 * defines and constructs to allow it to compile on more compilers. Cleaned
 * up some casts.
 *
 * Revision 4.1d  88/11/28  00:00:00  don
 *
 * Changed compusi.dos module to force lower case program name and compare.
 * Modified allocation routines to be defined in header file. One place to
 * change the function name. Fixed some typos, added some more compiler
 * dependent defines.
 *
 * Revision 4.1c  88/11/04  09:00:00  don
 *
 * More cleaning up. Changed some allocation functions to avoid longs. Changed
 * signal() to be optional. Added some libc.a functions for compilers without
 * some newer string functions. Cleaned up more logic. First release out of
 * beta.
 *
 * Revision 4.10b 88/11/01  09:10:00  don
 *
 * More cleaning up. Now will compile in small model with near heap with
 * 12 bits. Cleaned up declarations. Added some other MsDos compiler
 * defines. Fixed bugs with finding the path and file name. Fixed bugs with
 * inpath and outpath and where the files would be placed.
 *
 * Revision 4.10a 88/10/30  13:00:00  don
 *
 * No longer needs huge pointers. Did more cleaning up on the code. Future
 * changes will revolve around supporting other compilers/operating systems.
 * See COMPRESS.H for the various defines you need for your system.
 * Because of the changes in the algorithm, it no longer uses adaptive
 * reset of the block. It just assumes to do it. This decision was made in
 * the interests of speed. The original compress code compressed a 220k byte
 * file on my machine in about 4 minutes. It now takes less than 45 seconds.
 *
 * Revision 4.10  88/10/08  13:00:00  don
 *
 * Changed compress() decompress() functions to use far *arrays and stay
 * within a segment.  Code changes courtesy of Lyle V. Rains. Now should
 * compile on Xenix properly. See makefile and .lnk files for compiling and
 * linking information.  Compiles in small memory model now.
 *
 ******** BELOW KEPT FOR HISTORICAL PURPOSES. ALGORITHM CHANGED WITH 4.1 ****
 ******** New compress() and decompress() compatible with current        ****
 ******** version 4.0 joe release, including command options             ****
 *
 * Revision 4.01  88/09/04  22:00:00  don
 *
 * revised the files to now have compress.c compusi.c and compapi.c. The
 * globals are in compress.h and the prototypes are in compress.fns.
 *
 * revised some msdos code, adapted for 16 bit compression, Microsoft C
 * compiler version 5.1.  Must compile in compact model. Compiler must support
 * huge pointers. Now uses about 447929 bytes to load.  Debug version is not
 * supported under 16 bit compression. More work on the argv[0] and the use of
 * three letter extensions for naming the compressed files. Now works with
 * swichchar set to dash. Debug version will compile to 16 bits, but is too
 * large to load.
 *
 * Fixed irrationality of the ^C interupt.  If interupted while decompressing
 * to the console, it would unlink a file if it also existed on the disk.
 *
 * Added in and out path parameters. More realistic on specified extension for
 * MsDos, eg:  uncomp program.exe  will search for program.exz and call it
 * program.exe instead of dropping final letter. If uncomp program.exz is
 * the command line, the z is dropped and no adjustment is made.
 *
 * Revision 4.0  87/09/09  09:00:00  don
 * added MSDOS if defined's to adapt for pcxt and msdos. As written it
 * will compile with Microsoft C version 4 compiler.  Revised code for
 * file names, argv[0] checking, added option -k to kill the source file
 * after compress.  Changed the default to keep the source. Fixed bug with
 * filename/pathname.
 *
 * Revision 4.0  85/07/30  12:50:00  joe
 * Removed ferror() calls in output routine on every output except first.
 * Prepared for release to the world.
 *
 * Revision 3.6  85/07/04  01:22:21  joe
 * Remove much wasted storage by overlaying hash table with the tables
 * used by decompress: tab_suffix[1<<BITS], stack[8000].  Updated USERMEM
 * computations.  Fixed dump_tab() DEBUG routine.
 *
 * Revision 3.5  85/06/30  20:47:21  jaw
 * Change hash function to use exclusive-or.  Rip out hash cache.  These
 * speedups render the megamemory version defunct, for now.  Make decoder
 * stack global.  Parts of the RCS trunks 2.7, 2.6, and 2.1 no longer apply.
 *
 * Revision 3.4  85/06/27  12:00:00  ken
 * Get rid of all floating-point calculations by doing all compression ratio
 * calculations in fixed point.
 *
 * Revision 3.3  85/06/24  21:53:24  joe
 * Incorporate portability suggestion for M_XENIX.  Got rid of text on #else
 * and #endif lines.  Cleaned up #ifdefs for vax and interdata.
 *
 * Revision 3.2  85/06/06  21:53:24  jaw
 * Incorporate portability suggestions for Z8000, IBM PC/XT from mailing list.
 * Default to "quiet" output (no compression statistics).
 *
 * Revision 3.1  85/05/12  18:56:13  jaw
 * Integrate decompress() stack speedups (from early pointer mods by McKie).
 * Repair multi-file USERMEM gaffe.  Unify 'force' flags to mimic semantics
 * of SVR2 'pack'.  Streamline block-compress table clear logic.  Increase
 * output byte count by magic number size.
 *
 * Revision 3.0   84/11/27  11:50:00  petsd!joe
 * Set HSIZE depending on BITS.  Set BITS depending on USERMEM.  Unrolled
 * loops in clear routines.  Added "-C" flag for 2.0 compatibility.  Used
 * unsigned compares on Perkin-Elmer.  Fixed foreground check.
 *
 * Revision 2.7   84/11/16  19:35:39  ames!jaw
 * Cache common hash codes based on input statistics; this improves
 * performance for low-density raster images.  Pass on #ifdef bundle
 * from Turkowski.
 *
 * Revision 2.6   84/11/05  19:18:21  ames!jaw
 * Vary size of hash tables to reduce time for small files.
 * Tune PDP-11 hash function.
 *
 * Revision 2.5   84/10/30  20:15:14  ames!jaw
 * Junk chaining; replace with the simpler (and, on the VAX, faster)
 * double hashing, discussed within.  Make block compression standard.
 *
 * Revision 2.4   84/10/16  11:11:11  ames!jaw
 * Introduce adaptive reset for block compression, to boost the rate
 * another several percent.  (See mailing list notes.)
 *
 * Revision 2.3   84/09/22  22:00:00  petsd!joe
 * Implemented "-B" block compress.  Implemented REVERSE sorting of tab_next.
 * Bug fix for last bits.  Changed fwrite to putchar loop everywhere.
 *
 * Revision 2.2   84/09/18  14:12:21  ames!jaw
 * Fold in news changes, small machine typedef from thomas,
 * #ifdef interdata from joe.
 *
 * Revision 2.1   84/09/10  12:34:56  ames!jaw
 * Configured fast table lookup for 32-bit machines.
 * This cuts user time in half for b <= FBITS, and is useful for news batching
 * from VAX to PDP sites.  Also sped up decompress() [fwrite->putc] and
 * added signal catcher [plus beef in writeerr()] to delete effluvia.
 *
 * Revision 2.0   84/08/28  22:00:00  petsd!joe
 * Add check for foreground before prompting user.  Insert maxbits into
 * compressed file.  Force file being uncompressed to end with ".Z".
 * Added "-c" flag and "zcat".  Prepared for release.
 *
 * Revision 1.10  84/08/24  18:28:00  turtlevax!ken
 * Will only compress regular files (no directories), added a magic number
 * header (plus an undocumented -n flag to handle old files without headers),
 * added -f flag to force overwriting of possibly existing destination file,
 * otherwise the user is prompted for a response.  Will tack on a .Z to a
 * filename if it doesn't have one when decompressing.  Will only replace
 * file if it was compressed.
 *
 * Revision 1.9  84/08/16  17:28:00  turtlevax!ken
 * Removed scanargs(), getopt(), added .Z extension and unlimited number of
 * filenames to compress.  Flags may be clustered (-Ddvb12) or separated
 * (-D -d -v -b 12), or combination thereof.  Modes and other status is
 * copied with copystat().  -O bug for 4.2 seems to have disappeared with
 * 1.8.
 *
 * Revision 1.8  84/08/09  23:15:00  joe
 * Made it compatible with vax version, installed jim's fixes/enhancements
 *
 * Revision 1.6  84/08/01  22:08:00  joe
 * Sped up algorithm significantly by sorting the compress chain.
 *
 * Revision 1.5  84/07/13  13:11:00  srd
 * Added C version of vax asm routines.  Changed structure to arrays to
 * save much memory.  Do unsigned compares where possible (faster on
 * Perkin-Elmer)
 *
 * Revision 1.4  84/07/05  03:11:11  thomas
 * Clean up the code a little and lint it.  (Lint complains about all
 * the regs used in the asm, but I'm not going to "fix" this.)
 *
 * Revision 1.3  84/07/05  02:06:54  thomas
 * Minor fixes.
 *
 * Revision 1.2  84/07/05  00:27:27  thomas
 * Add variable bit length output.
 *
 */