v17i067: freeze - Freeze/Melt compression package, Part01/02
Leonid A. Broukhis
leo at s514.ipmce.su
Mon Mar 25 13:00:41 AEST 1991
Submitted-by: Leonid A. Broukhis <leo at s514.ipmce.su>
Posting-number: Volume 17, Issue 67
Archive-name: freeze/part01
I have written a new compression program (Freeze/Melt), which
gives a compression rate a bit worse (1-2%) than ARJ 1.00 & LHA 2.05
(MS-DOS), has nearly the same speed as ARJ, but works under UN*X
and has a compress-like interface (pipe facility, etc.)
When file names are given, the ownership modes, accessed and
modified times are maintained between the file and its compressed
.F version if possible due to ownership restrictions. In this
respect, freeze can be used for archival purposes, yet can
still be used with make(1) after melting.
Leonid
---
#! /bin/sh
# This is a shell archive. Remove anything before this line, then feed it
# into a shell via "sh file" or similar. To overwrite existing files,
# type "sh file -c".
# The tool that generated this appeared in the comp.sources.unix newsgroup;
# send mail to comp-sources-unix at uunet.uu.net if you want that tool.
# Contents: README bitio.c encode.c freeze.1 freeze.c huf.c statist.c
# Wrapped by kent at sparky on Sun Mar 24 20:41:08 1991
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
echo If this archive is complete, you will see the following message:
echo ' "shar: End of archive 1 (of 2)."'
if test -f 'README' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'README'\"
else
echo shar: Extracting \"'README'\" \(6234 characters\)
sed "s/^X//" >'README' <<'END_OF_FILE'
X FREEZE / MELT COMPRESSION PROGRAM
X
XThis is Alpha version. It is tested under ISC 2.2.
X
XThe following preprocessor symbols control the compilation of Freeze
Xpackage:
X
X o BITS The size of hash table (default is 18,
X reducing to 14 gives a 50% speeddown).
X o COMPAT Turns on backwards compatibility
X with Freeze 1.0
X o M_XENIX & M_I286 Makes arrays < 65536 bytes each
X o BSD4_2 Allow long filenames ( > 14 characters) &
X Call setlinebuf(stderr)
X o INT_SIG signal is int (*)() unstead of void
X o MSDOS Turns off some UNIX-dependencies
X and MSDOS' ones - vice versa
X (this version is completely untested)
X o __TURBOC__ For compiling under TURBO C
X (untested)
X
XOther preprocessor symbols (DEBUG, GATHER_STAT) are for internal use
Xonly.
X
XThe format of frozen (2.1) file is incompatible with that of frozen (1.0),
Xbut if this package is compiled with -DCOMPAT switch, you will able to
Xunpack frozen (1.0) files, if you have them.
X
X----
X
X Format of a frozen file is as follows:
X (version 1.0 had only 2-bytes header)
X
Xoffset type value comment
X 0 byte 037 2 byte magic header
X 1 byte 0237 (version 1.0 - 0236)
X 2 short X (little endian)
X 4 byte Y
X
XX = 0 e e e e e d d d d c c c b b a \
X > [a-f] are binary digits
XY = 0 0 f f f f f f /
X
Xa - number of 1-bit static Huffman codes in the `matching positions'
Xtable (see freeze.1)
Xbb - number of 2-bit codes,
X etc.
X
XThe numbers of 7- and 8-bits codes are evaluated from the
Xconditions: sum(codes) = 62(dec), max code = 1111111(bin).
X
XThe default values are: 0 1 1 1 4 10 27 18, what means:
Xno 1-bit codes,
Xone 2-bit, 3-bit and 4-bit codes, etc., so Huffman codes are:
X00, 010, 0110, 01110, 01111, 10000, .... , 11111111.
X
X------------------- !!!!!!!!!! -----------------
X
X(If you do not deal with compression algorithms, you may skip
Xuntil asterisks.)
X
XGeneral format of frozen file is:
X
Xmagic header - table description - stream of bits
X
XThe stream of bits is considered as a sequence of variable length dynamic
XHuffman codes (if their values are in the range of 0-255, they mean single
Xbytes, special value of 256 means EOF, and further values mean the lengths
Xof matched string.) If we have the value greater than 256, we get a static
XHuffman code from the stream (his value is 6 higher bits of matched
Xstring's position in the buffer), and then we get 7 bits literally.
X
XBecause buffer length is 8192 bytes and maximum match length is 256 bytes,
Xthe position of matched string cannot be greater than 8192-256, that's why
Xthere is only (8192-256)/2^7 = 62 static codes.
X
X * * *
X
XThe default table is tuned for both C texts and executable files (as in
XLHARC). If you will freeze any other files (databases, images, fonts,
Xetc.) you can calculate the matching positions distribution using the
X`statist' program, which calculates and displays the mentioned
Xdistribution for the given file. It is useful for large (100K or more)
Xfiles !!!
X
XThough the built-in position table is polyvalent, the tuning can increase
Xthe compression rate up to one additional percent. (Or even more, if the
Xmatching strings distribution is very bizarre!)
X
XUsage: statist < sample_file ; you can also see the intermediate values
Xand watch their changes by pressing INTR key when you wish.
X
XNote: If you use "gensample | statist", remember that INTR influence BOTH
Xprocesses !!
X
XThe sum of numbers which are given by statist can be not equal to 62. This
Xmeans the sample was too trivial or random-like.
X
XYou may create the /etc/default/freeze file (if you don't like
X/etc/default/ directory, choose another - in MS-DOS it is FREEZE.CNF in
Xthe directory of FREEZE.EXE), which has the following format: name =
X``statist's output (8 numbers)'', f.ex.:
X
X---------- cut here -----------
X# This is freeze's defaults file
Xgif = 0 0 0 0 2 60 0 0 # This is NOT! a optimal data
X # for GIF files
Xdoc=0 0 1 2 7 16 36 0 # The sample was gcc.lp
X# End of file
X---------- cut here -----------
X
XIf you find values, which are better THAN DEFAULT both for text (C
Xprograms) and binary (executable) files, please send them to me.
X
XImportant note: statist.c is NOT a part of freeze package, it is an
Xaditional feature.
X
X------------------- LINT ----------------------------
X
XLint complains about MANY `constant in conditional context', but ALL these
Xcontexts aren't `conditional', because they are unconditional (!)
Xexpressions:
X
X#define BITS 18
X. . .
X#define LEN0 (BITS/3 + (BITS%3 != 0))
X. . .
X ... + (key[0] >> LEN0) ....
X
XDo you think about /*CONDITIONAL*/ pseudo-comment for lint?
X
XOther lint's complaints about `used/declared inconsistently' are (in my
Xcase) due to inconsistencies of /usr/include/* and /usr/lib/llib*ln. It
Xisn't dangerous.
X
X------------------- BUGS ----------------------------
X
XFound bugs descriptions, incompatibilities, etc. please send to
Xleo at s514.ipmce.su. MS-DOS version will not be supported in future
Xversions !! (If they will be :-) )
X
X------------ SPEED & COMPRESSION RATE ---------------
X
XWhen using 18 bits table (about 600K) and gcc, the speed of freeze is more
Xthan the same of ARJ 1.00, but is less than of LHA 2.05.
X
XMy aim is not the maximum speed, the same range is enough.
X
XNote: the percents mean 'relatively to compressed size', if you want have
Xthem relatively to original size, divide them to 2-2.5.
X
XCompression rate is *INDEPENDENT* of the hash table size, but may vary
Xwith different static Huffman tables. It is about 2% worse than the same
Xof ARJ and LHA.
X
XMy aim is not the maximum compression, the same range is enough. :-)
X
XNote: if you see Compress works nearly as Freeze (on some files), this
Xmeans the maximum is gained, so LHA and ARJ won't better more than
X1-1.5%.
X
X--------------- POSSIBLE IMPROVEMENTS ---------------
X
XThe high-level routines (freeze, melt) are almost independent from
Xlow-level routines (Get_Next_Match, Insert/Delete_Node,
XEncode/Decode_Char/Position), so if you want the speed and/or compression
Xrate `a la vogue' you may replace the low-level routines with the homebrew
X(f. ex.) ones and enjoy the results.
END_OF_FILE
if test 6234 -ne `wc -c <'README'`; then
echo shar: \"'README'\" unpacked with wrong size!
fi
# end of 'README'
fi
if test -f 'bitio.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'bitio.c'\"
else
echo shar: Extracting \"'bitio.c'\" \(1650 characters\)
sed "s/^X//" >'bitio.c' <<'END_OF_FILE'
X#include "freeze.h"
X#include "huf.h"
X
X/* get one byte */
X/* returning in Bit7...0 */
X
Xshort GetByte ()
X{
X register u_short dx = getbuf;
X register u_short c;
X
X if (getlen <= 8) {
X c = getchar ();
X if ((short)c < 0) {
X
X/* Frozen file is too short. This is fatal error.
X * Really the second absent byte indicates a error.
X * ("Packed file is corrupt." :-) )
X */
X if (corrupt_flag)
X corrupt_message();
X corrupt_flag = 1;
X c = 0;
X }
X dx |= c << (8 - getlen);
X getlen += 8;
X }
X getbuf = dx << 8;
X getlen -= 8;
X return (dx >> 8) & 0xff;
X}
X
X/* get N bit */
X/* returning in Bit(N-1)...Bit 0 */
X
Xshort GetNBits (n)
X register u_short n;
X{
X register u_short dx = getbuf;
X register u_short c;
X
X static u_short mask[17] = {
X 0x0000,
X 0x0001, 0x0003, 0x0007, 0x000f,
X 0x001f, 0x003f, 0x007f, 0x00ff,
X 0x01ff, 0x03ff, 0x07ff, 0x0fff,
X 0x1fff, 0x3fff, 0x7fff, 0xffff };
X
X static u_short shift[17] = {
X 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
X };
X
X if (getlen <= 8)
X {
X c = getchar ();
X if ((short)c < 0) {
X if (corrupt_flag)
X corrupt_message();
X corrupt_flag = 1;
X c = 0;
X }
X dx |= c << (8 - getlen);
X getlen += 8;
X }
X getbuf = dx << n;
X getlen -= n;
X return (dx >> shift[n]) & mask[n];
X}
X
X/* output C bits */
XPutcode (l, c)
X register u_short l;
X u_short c;
X{
X register u_short len = putlen;
X register u_short b = putbuf;
X b |= c >> len;
X if ((len += l) >= 8) {
X if (putchar ((int)(b >> 8)) == EOF) writeerr();
X if ((len -= 8) >= 8) {
X putchar ((int)b);
X bytes_out += 2;
X len -= 8;
X b = c << (l - len);
X } else {
X b <<= 8;
X bytes_out++;
X }
X }
X putbuf = b;
X putlen = len;
X}
END_OF_FILE
if test 1650 -ne `wc -c <'bitio.c'`; then
echo shar: \"'bitio.c'\" unpacked with wrong size!
fi
# end of 'bitio.c'
fi
if test -f 'encode.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'encode.c'\"
else
echo shar: Extracting \"'encode.c'\" \(3800 characters\)
sed "s/^X//" >'encode.c' <<'END_OF_FILE'
X#include "freeze.h"
X
X#include "lz.h"
X
Xextern hash_t prev[];
X#ifdef __XENIX__
Xextern u_short *next[];
X#else
Xextern u_short next[];
X#endif
X
X/*
X * freeze stdin to stdout
X */
X
Xfreeze ()
X{
X register u_short i, len, r, s;
X register short c;
X putchar((int)(magic_header[0]));
X#ifdef COMPAT
X putchar((int)(magic_header[1] | 1));
X#else
X putchar((int)(magic_header[1]));
X#endif
X write_header();
X StartHuff();
X InitTree();
X s = 0;
X r = N - _F;
X for (i = s; i < r; i++)
X text_buf[i] = ' ';
X for (len = 0; len < _F && (c = getchar()) != EOF; len++)
X text_buf[r + len] = c;
X if(!topipe && text_buf[r] == magic_header[0] &&
X (text_buf[r + 1] ^ magic_header[1]) <= 1) {
X if (!quiet)
X fprintf(stderr, " already frozen ");
X exit_stat = 2;
X return;
X }
X
X in_count = len;
X for (i = 0; i <= _F; i++)
X InsertNode(r + i - _F);
X while (len != 0) {
X Get_Next_Match(r);
X
X if (match_length > len)
X match_length = len;
X
X if (match_length <= THRESHOLD) {
X match_length = 1;
X EncodeChar(text_buf[r]);
X#ifdef DEBUG
X symbols_out ++;
X if (verbose)
X fprintf(stderr, "'%s'\n",
X pr_char(text_buf[r]));
X#endif /* DEBUG */
X } else {
X register u_short orig_length, orig_position, oldchar;
X
X/* This fragment (delayed coding, non-greedy) is due to ideas of
X Jan Mark Wams' <jms at cs.vu.nl> COMIC:
X*/
X oldchar = text_buf[r];
X orig_length = match_length;
X orig_position = match_position;
X
X DeleteNode(s);
X Next_Char();
X Get_Next_Match(r);
X
X if (match_length > len) match_length = len;
X
X if (orig_length > match_length) {
X EncodeChar((u_short)
X (256 - THRESHOLD + orig_length));
X EncodePosition((u_short)orig_position);
X#ifdef DEBUG
X match_position = orig_position;
X#endif /* DEBUG */
X match_length = orig_length - 1;
X } else {
X EncodeChar(oldchar);
X#ifdef DEBUG
X symbols_out ++;
X if (verbose)
X fprintf(stderr, "'%s'\n",
X pr_char(oldchar));
X#endif /* DEBUG */
X EncodeChar(256 - THRESHOLD + match_length);
X EncodePosition(match_position);
X }
X#ifdef DEBUG
X refers_out ++;
X if (verbose) {
X register short pos =
X (r - 1 - match_position) & (N - 1),
X len = match_length;
X fputc('"', stderr);
X for(;len;len--, pos++)
X fprintf(stderr, "%s",
X pr_char(text_buf[pos]));
X fprintf(stderr, "\"\n");
X }
X#endif /* DEBUG */
X }
X for (i = 0; i < match_length &&
X (c = getchar()) != EOF; i++) {
X DeleteNode(s);
X text_buf[s] = c;
X if (s < _F - 1)
X text_buf[s + N] = c;
X s = (s + 1) & (N - 1);
X r = (r + 1) & (N - 1);
X InsertNode(r);
X }
X
X in_count += i;
X if ((in_count > indicator_count) && !quiet) {
X fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
X fflush (stderr);
X indicator_count += indicator_threshold;
X indicator_threshold += 1024;
X }
X while (i++ < match_length) {
X DeleteNode(s);
X s = (s + 1) & (N - 1);
X r = (r + 1) & (N - 1);
X if (--len) InsertNode(r);
X }
X }
X EncodeChar((short)ENDOF);
X#ifdef DEBUG
X symbols_out ++;
X#endif
X EncodeEnd();
X /*
X * Print out stats on stderr
X */
X if(!quiet) {
X#ifdef GATHER_STAT
X fprintf(stderr, "Average number of steps: ");
X prratio(stderr, node_steps, node_matches);
X fprintf(stderr, "\n");
X#endif
X#ifdef DEBUG
X fprintf( stderr,
X "%ld chars in, %ld codes (%ld bytes) out, freezing factor: ",
X in_count, symbols_out + refers_out, bytes_out);
X prratio( stderr, in_count, bytes_out );
X fprintf( stderr, "\n");
X fprintf( stderr, "\tFreezing as in compact: " );
X prratio( stderr, in_count-bytes_out, in_count );
X fprintf( stderr, "\n");
X fprintf( stderr, "\tSymbols: %ld; references: %ld.\n",
X symbols_out, refers_out);
X#else /* !DEBUG */
X fprintf( stderr, "Freezing: " );
X prratio( stderr, in_count-bytes_out, in_count );
X#endif /* DEBUG */
X }
X if(bytes_out >= in_count) /* exit(2) if no savings */
X exit_stat = 2;
X return;
X}
END_OF_FILE
if test 3800 -ne `wc -c <'encode.c'`; then
echo shar: \"'encode.c'\" unpacked with wrong size!
fi
# end of 'encode.c'
fi
if test -f 'freeze.1' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'freeze.1'\"
else
echo shar: Extracting \"'freeze.1'\" \(5973 characters\)
sed "s/^X//" >'freeze.1' <<'END_OF_FILE'
X.PU
X.TH FREEZE 1 local
X.SH NAME
Xfreeze, melt, fcat \- compress and uncompress files
X.SH SYNOPSIS
X.ll +8
X.B freeze
X[
X.B \-c
X] [
X.B \-d
X] [
X.B \-f
X] [
X.B \-V
X] [
X.B \-v
X] [
X.I "filename | +type \&..."
X]
X.ll -8
X.br
X.B melt
X[
X.B \-c
X] [
X.B \-f
X] [
X.B \-v
X] [
X.B \-V
X] [
X.I "filename \&..."
X]
X.br
X.B fcat
X[
X.I "filename \&..."
X]
X.SH DESCRIPTION
XCompresses the specified files or standard input.
XEach file is replaced by a file with the extension
X.B "\&.F,"
Xbut only if the file got smaller.
XIf no files are specified,
Xthe compression is applied to the standard input
Xand is written to standard output
Xregardless of the results.
XCompressed files can be restored
Xto their original form by specifying the
X.B \-d
Xoption, or by running
X.I melt
X(linked to
X.IR freeze ),
Xon the
X.B "\&.F"
Xfiles or the standard input.
X.PP
XIf the output file exists, it will not be overwritten unless the
X.B \-f
Xflag is given. If
X.B \-f
Xis not specified and
X.I freeze
Xis run in the foreground,
Xthe user is prompted
Xas to whether the file should be overwritten.
X.PP
XIf the
X.B \-f
Xflag is given, all files specified are replaced with
X.B "\&.F"
Xfiles \- even if the file didn't get smaller.
X.PP
XWhen file names are given, the ownership (if run by root), modes, accessed
Xand modified times are maintained between the file and its
X.B "\&.F"
Xversion. In this respect,
X.I freeze
Xcan be used for archival purposes, yet can still be used with
X.IR make "(1)"
Xafter melting.
X.PP
XThe
X.B \-c
Xoption causes the results of the freeze/melt operation to be written
Xto stdout; no files are changed. The
X.I fcat
Xprogram is the same as specifying
X.B \-c
Xto
X.I melt
X(all files are unpacked and written to stdout).
X.PP
XType is a token preceded by a '+', which defines the type
Xof following files in the command string. An explicite definition
Xof the file's type can give up to 2% of additional compression.
XThe list of types is stored in file
X.IR /etc/default/freeze .
XTypes may be abbreviated while not ambigious.
X.PP
X.I Freeze
Xuses the Lempel-Ziv algorithm on the first pass and the dynamic
XHuffman algorithm on the second one. The size of sliding window
Xis 8K, and the maximum length of matched string is 256.
XThe positions on the window are coded using a static Huffman table.
X.PP
XA two byte magic number is prepended to the file
Xto ensure that neither melting of random text nor refreezing of
Xalready frozen text are attempted. In addition, the characteristics
Xof the static Huffman table being used during
X.I freeze
Xis written to the file so that these characteristics may be adapted
Xto concrete conditions.
X.PP
X.ne 8
XThe amount of compression obtained depends on the size of the
Xinput file and the distribution of character substrings and their
Xprobabilities.
XTypically, text files, such as C programs,
Xare reduced by 60\-75%, executable files are reduced by 50%.
XCompression is generally much better than that achieved by
XLZW coding (as used in
X.IR compress ),
Xor Huffman coding
X.RI ( pack ),
Xthough takes more time to compute.
X.PP
X.PP
XIf the
X.B \-v
X(verbose) flag is given, then when freezing each file the kilobytes
Xcounter is displayed, and
Xafter the file is frozen, a message is printed giving the percentage of
Xthe input file that has been saved by compression.
X.PP
XIf the
X.B \-V
X(version) flag is given, the program's version number and compilation
Xoptions are printed.
X.PP
XThe exit status is normally 0;
Xif the last file gets bigger after freezing, the exit status is 2;
Xif an error occurs, the exit status is 1.
X.SH "SEE ALSO"
Xcompact(1), pack(1), compress(1)
X.SH "DIAGNOSTICS"
XUsage: freeze [-cdfvV] [file ...]
X.in +8
XInvalid options were specified on the command line.
X.in -8
XUnknown flag:
X.I "\'x\';"
X.in +8
XInvalid flags were specified on the command line.
X.in -8
X.IR file :
Xnot in frozen format
X.in +8
XThe specified file has not been frozen.
X.in -8
X.IR file :
Xalready has .F suffix -- no change
X.in +8
XCannot compress a file that has a ".F" suffix.
X.IR mv "(1)"
Xthe file to a different name and try again.
X.in -8
X.IR file :
Xfilename too long to tack on .F
X.in +8
XThe specified file cannot be compressed because its filename is longer than
X12 characters.
X.IR mv "(1)"
Xthe file to a different name and try again. This message does not occur on
X4.XBSD systems.
X.in -8
X.I file
Xalready exists; do you wish to overwrite (y or n)?
X.in +8
XRespond "y" if you want the output file to be replaced; "n" if you want it
Xto be left alone.
X.in -8
X.IR file :
X.IR xxx K
X.in +8
XThis message fragment is written during the processing of a file.
X.in -8
XFreezing:
X.I "xx.xx%"
X.in +8
XThis message fragment gives the percentage of the input file that has been
Xsaved by freezing.
X.in -8
X-- not a regular file: unchanged
X.in +8
XThis message fragment is written when the input file is not a regular file.
XThe input file is left unchanged.
X.in -8
X-- has
X.I xx
Xother links: unchanged
X.in +8
XThis message fragment is written when the input file has links. The input
Xfile is left unchanged. See
X.IR ln "(1)"
Xfor more information.
X.in -8
X-- file unchanged
X.in +8
XThis message fragment is written when no savings are achieved by
Xfreezing. The input file is left unchanged.
X.in -8
X-- replaced with
X.I file
X.in +8
XThis message fragment is written when a file has been sucessfully
Xfrozen/melt.
X.in -8
XUsing "
X.I type
X" type
X.in +8
XThis message indicates a successful switching to
Xposition table for mentioned file type.
X.in -8
Xmelt: corrupt input
X.in +8
XThis message fragment is written when an error in header or
Xunexpected end of frozen file is detected. Partial
X(or empty, is there was an error in the header) file is created.
X.in -8
Xalready frozen -- file unchanged
X.in +8
XThis message fragment is written when an input file already has
XFreeze's magic header.
X.in -8
XInvalid position table
X.in +8
Xor
X.in -8
X"
X.I type
X" - invalid entry
X.in +8
XThese messages appear only if Freeze has been made with incorrect
Xdata for static Huffman table. It does never appear when freeze
Xis called from a public access directory.
X.in -8
END_OF_FILE
if test 5973 -ne `wc -c <'freeze.1'`; then
echo shar: \"'freeze.1'\" unpacked with wrong size!
fi
# end of 'freeze.1'
fi
if test -f 'freeze.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'freeze.c'\"
else
echo shar: Extracting \"'freeze.c'\" \(16740 characters\)
sed "s/^X//" >'freeze.c' <<'END_OF_FILE'
X#include "freeze.h"
X#include "lz.h"
X#include "huf.h"
X
X/*
X * Freeze - data freezing program
X * Version 1.0:
X * This program is made from GNU compress.c and Yoshizaki/Tagawa's
X * lzhuf.c. (Thanks to all of them.)
X * The algorithm is modified for using in pipe
X * (added ENDOF symbol in Huffman table).
X * Version 1.1:
X * Check for lack of bytes in frozen file when melting.
X * Put the GetBit routine into DecodeChar for reduce function-
X * call overhead when melting.
X * Version 1.2:
X * Added delayed coding a la COMIC.
X * Now freeze works on Intels (*NIX, Microsoft, Turbo),
X * Sun (SunOS).
X * Version 2.0:
X * Buffer size is now 8192 bytes, maximum match length - 256 bytes.
X * Improved hash function (with tuning of hash-table)
X * Version 2.1: Noticeable speedup: Insert_Node and Get_Next_Match
X * are now separated.
X */
X
X#ifdef COMPAT
Xuchar magic_header[] = { "\037\236" }; /* 1F 9E = compress + 1 */
X#else
Xuchar magic_header[] = { "\037\237" }; /* 1F 9F = freeze 1.X + 1 */
X#endif
X
Xstatic char ident[] = "@(#) freeze.c 2.1 Alpha 3/21/91 leo at s514.ipmce.su";
X
X#define ARGVAL() (*++(*argv) || (--argc && *++argv))
X
Xint exit_stat = 0;
X
XUsage() {
X#ifdef DEBUG
X
X# ifdef MSDOS
X fprintf(stderr,"Usage: freeze [-cdDfivV] [file | +type ...]\n");
X# else
X fprintf(stderr,"Usage: freeze [-cdDfvV] [file | +type ...]\n");
X# endif /* MSDOS */
X
X#else
X
X# ifdef MSDOS
X fprintf(stderr,"Usage: freeze [-cdfivV] [file | +type ...]\n");
X# else
X fprintf(stderr,"Usage: freeze [-cdfvV] [file | +type ...]\n");
X# endif /* MSDOS */
X
X#endif /* DEBUG */
X}
X
Xshort topipe = 0; /* Write output on stdout, suppress messages */
Xshort precious = 1; /* Don't unlink output file on interrupt */
Xshort quiet = 1; /* Don't tell me about freezing */
X
X#ifdef COMPAT
Xshort new_flg; /* File is frozen using BIG freeze */
X#endif
X
Xshort force = 0;
Xchar ofname [100];
X
X#ifdef MSDOS
X# define PATH_SEP '\\'
Xshort image = 2; /* 1 <=> image (binary) mode; 2 <=> text mode */
X#else
Xchar deffile[] = "/etc/default/freeze";
X# define PATH_SEP '/'
X#endif
X
X#ifdef DEBUG
Xshort debug = 0;
Xshort verbose = 0;
Xchar * pr_char();
Xlong symbols_out = 0, refers_out = 0;
X#endif /* DEBUG */
X
Xunsigned long indicator_count, indicator_threshold;
X
X#ifdef INT_SIG
Xint
X#else
Xvoid
X#endif
X(*bgnd_flag)();
X
Xshort do_melt = 0;
X
X/*****************************************************************
X * TAG( main )
X *
X *
X * Usage: freeze [-cdfivV] [-t type] [file ...]
X * Inputs:
X *
X * -c: Write output on stdout, don't remove original.
X *
X * -d: If given, melting is done instead.
X *
X * -f: Forces output file to be generated, even if one already
X * exists, and even if no space is saved by freezeing.
X * If -f is not used, the user will be prompted if stdin is
X * a tty, otherwise, the output file will not be overwritten.
X *
X * -i: Image mode (defined only under MS-DOS). Prevents
X * conversion between UNIX text representation (LF line
X * termination) in frozen form and MS-DOS text
X * representation (CR-LF line termination) in melted
X * form. Useful with non-text files.
X *
X * -v: Write freezing statistics
X *
X * -V: Write version and compilation options.
X *
X * file ...: Files to be frozen. If none specified, stdin
X * is used.
X * Outputs:
X * file.F: Frozen form of file with same mode, owner, and utimes
X * or stdout (if stdin used as input)
X *
X * Assumptions:
X * When filenames are given, replaces with the frozen version
X * (.F suffix) only if the file decreases in size.
X * Algorithm:
X * Modified Lempel-Ziv-SS method (LZSS), adaptive Huffman coding
X * for literal symbols and length info.
X * Static Huffman coding for position info. (It is optimal ?)
X * Lower bits of position info are put in output
X * file without any coding because of their random distribution.
X */
X
X/* From compress.c. Replace .Z --> .F etc */
X
Xmain( argc, argv )
Xregister int argc; char **argv;
X{
X short overwrite = 0; /* Do not overwrite unless given -f flag */
X char tempname[100];
X char **filelist, **fileptr;
X char *cp, *rindex();
X#ifndef MSDOS
Xchar *malloc();
X#endif
X struct stat statbuf;
X#if defined(__TURBOC__) || !defined(INT_SIG)
X extern void onintr();
X#else
X extern onintr();
X#endif
X
X
X#ifdef MSDOS
X char *sufp;
X#else
X#ifdef INT_SIG
X extern oops();
X#else
X extern void oops();
X#endif
X#endif
X
X#ifndef MSDOS
X if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN )
X#endif
X {
X signal ( SIGINT, onintr );
X#ifdef __TURBOC__
X setcbrk(1);
X#endif
X#ifndef MSDOS
X signal ( SIGSEGV, oops );
X#endif
X }
X
X filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
X *filelist = NULL;
X
X if((cp = rindex(argv[0], PATH_SEP)) != 0) {
X cp++;
X } else {
X cp = argv[0];
X }
X
X#ifdef MSDOS
X if(strcmp(cp, "MELT.EXE") == 0) {
X#else
X if(strcmp(cp, "melt") == 0) {
X#endif
X
X do_melt = 1;
X
X#ifdef MSDOS
X } else if(strcmp(cp, "FCAT.EXE") == 0) {
X#else
X } else if(strcmp(cp, "fcat") == 0) {
X#endif
X
X do_melt = 1;
X topipe = 1;
X
X } else {
X /* Freezing */
X#ifndef MSDOS
X defopen(deffile);
X#else
X cp = rindex(cp, '.');
X *++cp = 'C';
X *++cp = 'N';
X *++cp = 'F';
X *++cp = '\0';
X defopen(argv[0]);
X#endif
X }
X#ifdef BSD4_2
X /* 4.2BSD dependent - take it out if not */
X setlinebuf( stderr );
X#endif /* BSD4_2 */
X
X /* Argument Processing
X * All flags are optional.
X * -D => debug
X * -V => print Version; debug verbose
X * -d => do_melt
X * -v => unquiet
X * -f => force overwrite of output file
X * -c => cat all output to stdout
X * if a string is left, must be an input filename.
X */
X for (argc--, argv++; argc > 0; argc--, argv++) {
X if (**argv == '-') { /* A flag argument */
X while (*++(*argv)) { /* Process all flags in this arg */
X switch (**argv) {
X#ifdef DEBUG
X case 'D':
X debug = 1;
X break;
X case 'V':
X verbose = 1;
X#else
X case 'V':
X version();
X#endif /* DEBUG */
X break;
X#ifdef MSDOS
X case 'i':
X image = 1;
X break;
X#endif
X
X case 'v':
X quiet = 0;
X break;
X case 'd':
X do_melt = 1;
X break;
X case 'f':
X case 'F':
X overwrite = 1;
X force = 1;
X break;
X case 'c':
X topipe = 1;
X break;
X case 'q':
X quiet = 1;
X break;
X default:
X fprintf(stderr, "Unknown flag: '%c'; ", **argv);
X Usage();
X exit(1);
X }
X }
X }
X else { /* Input file name */
X *fileptr++ = *argv; /* Build input file list */
X *fileptr = NULL;
X }
X }
X
X# ifdef DEBUG
X if (verbose && !debug)
X version();
X#endif
X
X if (*filelist != NULL) {
X for (fileptr = filelist; *fileptr; fileptr++) {
X if (**fileptr == '+' && do_melt == 0) {
X tune_table(*fileptr + 1);
X /* If a file type is given, but no file names */
X if (filelist[1] == NULL)
X goto Pipe;
X continue;
X }
X exit_stat = 0;
X if (do_melt != 0) { /* MELTING */
X
X#ifdef MSDOS
X /* Check for .F or XF suffix; add one if necessary */
X cp = *fileptr + strlen(*fileptr) - 2;
X if ((*cp != '.' && *cp != 'X' && *cp != 'x') ||
X (*(++cp) != 'F' && *cp != 'f')) {
X strcpy(tempname, *fileptr);
X if ((cp=rindex(tempname,'.')) == NULL)
X strcat(tempname, ".F");
X else if(*(++cp) == '\0') strcat(tempname, "F");
X else {
X *(++cp) = '\0';
X strcat(tempname, "XF");
X }
X *fileptr = tempname;
X }
X#else
X /* Check for .F suffix */
X if (strcmp(*fileptr + strlen(*fileptr) - 2, ".F") != 0) {
X /* No .F: tack one on */
X strcpy(tempname, *fileptr);
X strcat(tempname, ".F");
X *fileptr = tempname;
X }
X#endif /*MSDOS */
X
X /* Open input file for melting */
X
X#ifdef MSDOS
X if ((freopen(*fileptr, "rb", stdin)) == NULL)
X#else
X if ((freopen(*fileptr, "r", stdin)) == NULL)
X#endif
X {
X perror(*fileptr); continue;
X }
X /* Check the magic number; note the lower bit
X of the second byte indicates the BIG version
X was used.
X */
X if (getchar() != magic_header[0]
X#ifdef COMPAT
X || (((new_flg = getchar()) & 0xFE) != magic_header[1]))
X#else
X || getchar() != magic_header[1])
X#endif
X {
X fprintf(stderr, "%s: not in frozen format\n",
X *fileptr);
X continue;
X }
X#ifdef COMPAT
X new_flg &= 1;
X#endif
X /* Generate output filename */
X strcpy(ofname, *fileptr);
X ofname[strlen(*fileptr) - 2] = '\0'; /* Strip off .F */
X } else {
X
X /* FREEZING */
X#ifdef COMPAT
X new_flg = 1;
X#endif
X
X#ifdef MSDOS
X cp = *fileptr + strlen(*fileptr) - 2;
X if ((*cp == '.' || *cp == 'X' || *cp == 'x') &&
X (*(++cp) == 'F' || *cp == 'f')) {
X fprintf(stderr,"%s: already has %s suffix -- no change\n",
X *fileptr,--cp); /* } */
X#else
X if (strcmp(*fileptr + strlen(*fileptr) - 2, ".F") == 0) {
X fprintf(stderr, "%s: already has .F suffix -- no change\n",
X *fileptr);
X#endif /* MSDOS */
X
X continue;
X }
X /* Open input file for freezing */
X
X#ifdef MSDOS
X if ((freopen(*fileptr, image == 2 ? "rt" : "rb", stdin))
X == NULL)
X#else
X if ((freopen(*fileptr, "r", stdin)) == NULL)
X#endif
X {
X perror(*fileptr); continue;
X }
X stat ( *fileptr, &statbuf );
X
X /* Generate output filename */
X strcpy(ofname, *fileptr);
X#ifndef BSD4_2 /* Short filenames */
X if ((cp = rindex(ofname, PATH_SEP)) != NULL) cp++;
X else cp = ofname;
X# ifdef MSDOS
X if (topipe == 0 && (sufp = rindex(cp, '.')) != NULL &&
X strlen(sufp) > 2) fprintf(stderr,
X "%s: part of filename extension will be replaced by XF\n",
X cp);
X# else
X if (strlen(cp) > 12) {
X fprintf(stderr,"%s: filename too long to tack on .F\n",cp);
X continue;
X }
X# endif
X#endif /* BSD4_2 Long filenames allowed */
X
X#ifdef MSDOS
X if ((cp = rindex(ofname, '.')) == NULL) strcat(ofname, ".F");
X else {
X if(*(++cp) != '\0') *(++cp) = '\0';
X strcat(ofname, "XF");
X }
X#else
X strcat(ofname, ".F");
X#endif /* MSDOS */
X
X }
X precious = 0;
X /* Check for overwrite of existing file */
X if (overwrite == 0 && topipe == 0) {
X if (stat(ofname, &statbuf) == 0) {
X char response[2];
X response[0] = 'n';
X fprintf(stderr, "%s already exists;", ofname);
X#ifndef MSDOS
X if (foreground()) {
X#endif
X fprintf(stderr,
X " do you wish to overwrite %s (y or n)? ", ofname);
X fflush(stderr);
X read(2, response, 2);
X while (response[1] != '\n') {
X if (read(2, response+1, 1) < 0) { /* Ack! */
X perror("stderr"); break;
X }
X }
X#ifndef MSDOS
X }
X#endif
X if (response[0] != 'y') {
X fprintf(stderr, "\tnot overwritten\n");
X continue;
X }
X }
X }
X if(topipe == 0) { /* Open output file */
X
X#ifdef DEBUG
X if (do_melt == 0 || debug == 0) {
X#endif
X#ifdef MSDOS
X if (freopen(ofname, do_melt && image == 2 ? "wt" : "wb",
X stdout) == NULL)
X#else
X if (freopen(ofname, "w", stdout) == NULL)
X#endif
X {
X perror(ofname); continue;
X }
X#ifdef DEBUG
X }
X#endif
X if(!quiet) {
X fprintf(stderr, "%s:", *fileptr);
X indicator_threshold = 2048;
X indicator_count = 1024;
X }
X }
X /* Actually do the freezing/melting */
X if (do_melt == 0)
X freeze();
X#ifndef DEBUG
X else melt();
X#else
X else if (debug == 0) melt();
X else printcodes();
X#endif /* DEBUG */
X if(topipe == 0) {
X copystat(*fileptr, ofname); /* Copy stats */
X if((exit_stat == 1) || (!quiet))
X putc('\n', stderr);
X }
X }
X } else { /* Standard input */
XPipe:
X topipe = 1;
X if (do_melt == 0) {
X#ifdef COMPAT
X new_flg = 1;
X#endif
X freeze();
X if(!quiet)
X putc('\n', stderr);
X } else {
X /* Check the magic number */
X if ((getchar() != magic_header[0])
X#ifdef COMPAT
X || (((new_flg = getchar()) & 0xFE) !=magic_header[1]))
X#else
X || (getchar() != magic_header[1]))
X#endif
X {
X fprintf(stderr, "stdin: not in frozen format\n");
X exit(1);
X }
X#ifdef COMPAT
X new_flg &= 1;
X#endif
X
X#ifndef DEBUG
X melt();
X#else
X if (debug == 0) melt();
X else printcodes();
X#endif /* DEBUG */
X }
X }
X exit(exit_stat);
X}
X
Xlong in_count = 1; /* length of input */
Xlong bytes_out; /* length of frozen output */
X
Xprratio(stream, num, den)
XFILE *stream;
Xlong num, den;
X{
X register long q; /* This works everywhere */
X
X if (!den) den++;
X
X if(num > 214748L) { /* 2147483647/10000 */
X q = num / (den / 10000L);
X } else {
X q = 10000L * num / den; /* Long calculations, though */
X }
X if (q < 0) {
X putc('-', stream);
X q = -q;
X }
X fprintf(stream, "%d.%02d%%", (int)(q / 100), (int)(q % 100));
X#ifdef GATHER_STAT
X fprintf(stream, "(%ld / %ld)", num, den);
X#endif
X}
X
X
Xchar *
Xrindex(s, c) /* For those who don't have it in libc.a */
Xregister char *s, c;
X{
X char *p;
X for (p = NULL; *s; s++)
X if (*s == c)
X p = s;
X return(p);
X}
X
Xwriteerr()
X{
X perror ( ofname );
X unlink ( ofname );
X exit ( 1 );
X}
X
Xcopystat(ifname, ofname)
Xchar *ifname, *ofname;
X{
X#ifdef __TURBOC__
Xstruct ftime utimbuf;
X#endif
X struct stat statbuf;
X int mode;
X#ifndef __TURBOC__
X time_t timep[2];
X#endif
X
X#ifdef MSDOS
X if (_osmajor < 3) freopen("CON","at",stdout); else /* MS-DOS 2.xx bug */
X#endif
X
X fclose(stdout);
X if (stat(ifname, &statbuf)) { /* Get stat on input file */
X perror(ifname);
X return;
X }
X
X#ifndef MSDOS
X if ((statbuf.st_mode & S_IFMT) != S_IFREG) {
X if(quiet)
X fprintf(stderr, "%s: ", ifname);
X fprintf(stderr, " not a regular file: unchanged");
X exit_stat = 1;
X } else if (statbuf.st_nlink > 1) {
X if(quiet)
X fprintf(stderr, "%s: ", ifname);
X fprintf(stderr, " has %d other links: unchanged",
X statbuf.st_nlink - 1);
X exit_stat = 1;
X } else if (exit_stat == 2 && (!force)) { /* No freezing: remove file.F */
X#else
X if (exit_stat == 2 && (!force)) { /* No freezing: remove file.F */
X#endif /* MSDOS */
X
X if(!quiet)
X fprintf(stderr, "-- file unchanged");
X } else { /* ***** Successful Freezing ***** */
X exit_stat = 0;
X mode = statbuf.st_mode & 07777;
X if (chmod(ofname, mode)) /* Copy modes */
X perror(ofname);
X
X#ifndef MSDOS
X chown(ofname, statbuf.st_uid, statbuf.st_gid); /* Copy ownership */
X#endif
X
X#ifdef __TURBOC__
X getftime(fileno(stdin),&utimbuf);
X freopen(ofname,"rb",stdout);
X setftime(fileno(stdout),&utimbuf);
X fclose(stdout);
X#else
X timep[0] = statbuf.st_atime;
X timep[1] = statbuf.st_mtime;
X utime(ofname, timep); /* Update last accessed and modified times */
X#endif
X precious = 1;
X if (unlink(ifname)) /* Remove input file */
X perror(ifname);
X if(!quiet)
X fprintf(stderr, " -- replaced with %s", ofname);
X return; /* Successful return */
X }
X
X /* Unsuccessful return -- one of the tests failed */
X if (unlink(ofname))
X perror(ofname);
X}
X
X#ifndef MSDOS
X/*
X * This routine returns 1 if we are running in the foreground and stderr
X * is a tty.
X */
Xforeground()
X{
X if(bgnd_flag != SIG_DFL) /* background? */
X return(0);
X else { /* foreground */
X if(isatty(2)) { /* and stderr is a tty */
X return(1);
X } else {
X return(0);
X }
X }
X}
X#endif
X
X#if defined(__TURBOC__) || !defined(INT_SIG)
Xvoid
X#endif
Xonintr ( ) {
X if (!precious) {
X fclose(stdout);
X unlink ( ofname );
X }
X exit ( 1 );
X}
X
X#if defined(__TURBOC__) || !defined(INT_SIG)
Xvoid
X#endif
Xoops ( ) /* file is corrupt or internal error */
X{
X fflush(stdout);
X fprintf(stderr, "Segmentation violation occured...\n");
X exit ( 1 );
X}
X
Xversion()
X{
X fprintf(stderr, "%s\n", ident);
X fprintf(stderr, "Options: ");
X#ifdef DEBUG
X fprintf(stderr, "DEBUG, ");
X#endif
X#ifdef BSD4_2
X fprintf(stderr, "BSD4_2, ");
X#endif
X#ifdef __XENIX__
X fprintf(stderr, "XENIX, ");
X#endif
X#ifdef __TURBOC__
X fprintf(stderr, "TURBO, ");
X#endif
X#ifdef GATHER_STAT
X fprintf(stderr, "GATHER_STAT, ");
X#endif
X#ifdef COMPAT
X fprintf(stderr, "compatible with vers. 1.0, ");
X#endif
X fprintf(stderr, "\nLZSS: %d (table), %d (match length);\n", _NN, _F);
X fprintf(stderr, "Static Huffman table: %d %d %d %d %d %d %d %d\n",
X Table[1], Table[2], Table[3], Table[4],
X Table[5], Table[6], Table[7], Table[8]);
X fprintf(stderr, "HUFFMAN: %ld (max frequency)\n", (long)MAX_FREQ);
X fprintf(stderr, "HASH: %d bits\n", BITS);
X exit(0);
X}
X
Xtune_table(type) char *type;
X{
X extern char * defread();
X register char *s = defread(type), *t;
X static short v[8];
X int i;
X if(!s) {
X if(!quiet)
X fprintf(stderr, "\"%s\" - no such file type\n", type);
X exit(1);
X }
X
X if(!(t = rindex(s, '='))) {
X if(!quiet)
X fprintf(stderr, "\"%s\" - invalid entry\n", type);
X exit(1);
X }
X t++;
X if(sscanf(t, "%d %d %d %d %d %d %d %d",
X v, v+1, v+2, v+3, v+4, v+5, v+6, v+7) != 8) {
X if(!quiet)
X fprintf(stderr, "\"%s\" - invalid entry\n", type);
X exit(1);
X }
X for(i = 0; i < 8; i++)
X Table[i+1] = v[i];
X if(!quiet) {
X t = s;
X while(*s != '=' && *s != ' ' && *s != '\t') s++;
X *s = '\0';
X fprintf(stderr, "Using \"%s%s\" type\n", type, t);
X }
X}
END_OF_FILE
if test 16740 -ne `wc -c <'freeze.c'`; then
echo shar: \"'freeze.c'\" unpacked with wrong size!
fi
# end of 'freeze.c'
fi
if test -f 'huf.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'huf.c'\"
else
echo shar: Extracting \"'huf.c'\" \(8291 characters\)
sed "s/^X//" >'huf.c' <<'END_OF_FILE'
X#include "freeze.h"
X#include "huf.h"
X
X/*----------------------------------------------------------------------*/
X/* */
X/* HUFFMAN ENCODING */
X/* */
X/*----------------------------------------------------------------------*/
X
X#ifdef COMPAT
X#undef N
X#undef F
X#define F (new_flg ? _F : _FO)
X#define N (new_flg ? _NN : _NO)
X#endif
X
X
X/* TABLE OF ENCODE/DECODE for upper 6 bits position information */
X
X/* The contents of this table are used for freezing only, so we use
X * this table freely when melting
X */
X
Xuchar Table[9] = { 0, 0, 1, 1, 1, 4, 10, 27, 18 };
X
Xuchar p_len[64];
Xuchar d_len[256];
Xuchar code[256];
X
X#ifdef COMPAT
Xuchar table_old[9] = { 0, 0, 0, 1, 3, 8, 12, 24, 16 };
X#endif
X
Xu_short freq[_T + 1]; /* frequency table */
X
Xshort prnt[_T + _NCHAR]; /* points to parent node */
X/* notes :
X prnt[T .. T + N_CHAR - 1] used by
X indicates leaf position that corresponding to code */
X
Xshort son[_T]; /* points to son node (son[i],son[i+]) */
X
Xu_short getbuf = 0;
Xuchar getlen = 0;
X
Xuchar corrupt_flag = 0; /* If a file is corrupt, use fcat */
X
Xu_short putbuf = 0;
Xuchar putlen = 0;
X
X/* Initialize tree */
X
XStartHuff ()
X{
X register short i, j;
X#ifdef COMPAT
X if(do_melt == 0 || new_flg)
X init(Table);
X else
X init(table_old);
X#else
X init(Table);
X#endif
X for (i = 0; i < N_CHAR; i++) {
X freq[i] = 1;
X son[i] = i + T;
X prnt[i + T] = i;
X }
X i = 0; j = N_CHAR;
X while (j <= R) {
X freq[j] = freq[i] + freq[i + 1];
X son[j] = i;
X prnt[i] = prnt[i + 1] = j;
X i += 2; j++;
X }
X freq[T] = 0xffff;
X prnt[R] = 0;
X in_count = 1;
X bytes_out = 5;
X#ifdef DEBUG
X symbols_out = refers_out = 0;
X#endif
X putlen = getlen = 0;
X putbuf = getbuf = 0;
X corrupt_flag = 0;
X}
X
X
X/* reconstruct tree */
Xreconst ()
X{
X register u_short i, j, k;
X register u_short f;
X#ifdef DEBUG
X if (!quiet)
X fprintf(stderr,
X "Reconstructing Huffman tree: symbols: %ld, references: %ld\n",
X symbols_out, refers_out);
X#endif
X /* correct leaf node into of first half,
X and set these freqency to (freq+1)/2 */
X j = 0;
X for (i = 0; i < T; i++) {
X if (son[i] >= T) {
X freq[j] = (freq[i] + 1) / 2;
X son[j] = son[i];
X j++;
X }
X }
X /* build tree. Link sons first */
X for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
X k = i + 1;
X f = freq[j] = freq[i] + freq[k];
X for (k = j - 1; f < freq[k]; k--);
X k++;
X { register u_short *p, *e;
X for (p = &freq[j], e = &freq[k]; p > e; p--)
X p[0] = p[-1];
X freq[k] = f;
X }
X { register short *p, *e;
X for (p = &son[j], e = &son[k]; p > e; p--)
X p[0] = p[-1];
X son[k] = i;
X }
X }
X /* link parents */
X for (i = 0; i < T; i++) {
X if ((k = son[i]) >= T) {
X prnt[k] = i;
X } else {
X prnt[k] = prnt[k + 1] = i;
X }
X }
X}
X
X
X/* update given code's frequency, and update tree */
X
Xupdate (c)
X u_short c;
X{
X register u_short *p;
X register u_short i, j, k, l;
X
X if (freq[_R] == MAX_FREQ) {
X reconst();
X }
X c = prnt[c + _T];
X do {
X k = ++freq[c];
X
X /* swap nodes when become wrong frequency order. */
X if (k > freq[l = c + 1]) {
X for (p = freq+l+1; k > *p++; ) ;
X l = p - freq - 2;
X freq[c] = p[-2];
X p[-2] = k;
X
X i = son[c];
X prnt[i] = l;
X if (i < _T) prnt[i + 1] = l;
X
X j = son[l];
X son[l] = i;
X
X prnt[j] = c;
X if (j < _T) prnt[j + 1] = c;
X son[c] = j;
X
X c = l;
X }
X } while ((c = prnt[c]) != 0); /* loop until reach to root */
X}
X
XEncodeChar (c)
X u_short c;
X{
X register short *p;
X unsigned long i;
X register u_short j, k;
X
X i = 0;
X j = 0;
X p = prnt;
X k = p[c + _T];
X
X /* trace links from leaf node to root */
X do {
X i >>= 1;
X
X /* if node index is odd, trace larger of sons */
X if (k & 1) i += 0x80000000;
X
X j++;
X } while ((k = p[k]) != _R) ;
X if (j > 16) {
X Putcode(16, (u_short)(i >> 16));
X Putcode(j - 16, (u_short)i);
X } else {
X Putcode(j, (u_short)(i >> 16));
X }
X update(c);
X}
X
XEncodePosition (c)
X register u_short c;
X{
X register u_short i;
X
X /* output upper 6bit from table */
X i = c >> 7;
X Putcode((u_short)(p_len[i]), (u_short)(code[i]) << 8);
X
X /* output lower 7bit */
X Putcode(7, (u_short)(c & 0x7f) << 9);
X}
X
XEncodeEnd ()
X{
X if (putlen) {
X putchar((int)(putbuf >> 8));
X bytes_out++;
X }
X}
X
Xshort DecodeChar ()
X{
X register u_short c;
X register u_short dx;
X register u_short cc;
X c = son[_R];
X
X /* trace from root to leaf,
X got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
X while (c < _T) {
X dx = getbuf;
X if (getlen <= 8) {
X if ((short)(cc = getchar()) < 0) {
X if (corrupt_flag) {
X corrupt_message();
X return ENDOF;
X }
X corrupt_flag = 1;
X cc = 0;
X }
X dx |= cc << (8 - getlen);
X getlen += 8;
X }
X getbuf = dx << 1;
X getlen--;
X c += (dx >> 15) & 1;
X c = son[c];
X }
X c -= _T;
X update(c);
X return c;
X}
X
Xshort DecodePosition ()
X{
X register u_short i, j, c;
X
X /* decode upper 6 bits from table */
X i = GetByte();
X c = (u_short)code[i] << 7;
X j = d_len[i] - 1;
X
X /* get lower 7 bits */
X return c | (((i << j) | GetNBits (j)) & 0x7f);
X}
X
X#ifdef COMPAT
X/* update given code's frequency, and update tree */
X
XupdateO (c)
X u_short c;
X{
X register u_short *p;
X register u_short i, j, k, l;
X
X if (freq[_RO] == MAX_FREQ) {
X reconst();
X }
X c = prnt[c + _TO];
X do {
X k = ++freq[c];
X
X /* swap nodes when become wrong frequency order. */
X if (k > freq[l = c + 1]) {
X for (p = freq+l+1; k > *p++; ) ;
X l = p - freq - 2;
X freq[c] = p[-2];
X p[-2] = k;
X
X i = son[c];
X prnt[i] = l;
X if (i < _TO) prnt[i + 1] = l;
X
X j = son[l];
X son[l] = i;
X
X prnt[j] = c;
X if (j < _TO) prnt[j + 1] = c;
X son[c] = j;
X
X c = l;
X }
X } while ((c = prnt[c]) != 0); /* loop until reach to root */
X}
X
Xshort DecodeCOld ()
X{
X register u_short c;
X register u_short dx;
X register u_short cc;
X c = son[_RO];
X
X /* trace from root to leaf,
X got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
X while (c < _TO) {
X dx = getbuf;
X if (getlen <= 8) {
X if ((short)(cc = getchar()) < 0) {
X if (corrupt_flag) {
X corrupt_message();
X return ENDOF;
X }
X corrupt_flag = 1;
X cc = 0;
X }
X dx |= cc << (8 - getlen);
X getlen += 8;
X }
X getbuf = dx << 1;
X getlen--;
X c += (dx >> 15) & 1;
X c = son[c];
X }
X c -= _TO;
X updateO(c);
X return c;
X}
X
Xshort DecodePOld ()
X{
X register u_short i, j, c;
X
X /* decode upper 6 bits from table */
X i = GetByte();
X c = (u_short)code[i] << 6;
X j = d_len[i] - 2;
X
X /* get lower 6 bits */
X return c | (((i << j) | GetNBits (j)) & 0x3f);
X}
X
X#endif
X
Xinit(table) uchar * table; {
X short i, j, k, num;
X num = 0;
X for(i = 1, j = 0; i <= 8; i++) {
X num += Table[i] << (8 - i);
X for(k = table[i]; k; j++, k--)
X p_len[j] = i;
X }
X if (num != 256) {
X fprintf(stderr, "Invalid position table\n");
X exit(1);
X }
X num = j;
X if (do_melt == 0)
X for(i = j = 0;;) {
X code[j] = i << (8 - p_len[j]);
X i++;
X j++;
X if(j == num) break;
X i <<= p_len[j] - p_len[j-1];
X }
X else {
X for(k = j = 0; j < num; j ++)
X for(i = 1 << (8 - p_len[j]); i--;)
X code[k++] = j;
X for(k = j = 0; j < num; j ++)
X for(i = 1 << (8 - p_len[j]); i--;)
X d_len[k++] = p_len[j];
X }
X}
X
Xwrite_header() {
X u_short i;
X
X i = Table[5] & 0x1F; i <<= 4;
X i |= Table[4] & 0xF; i <<= 3;
X i |= Table[3] & 7; i <<= 2;
X i |= Table[2] & 3; i <<= 1;
X i |= Table[1] & 1;
X
X putchar((int)(i & 0xFF));
X putchar((int)((i >> 8) & 0x7F));
X putchar((int)(Table[6] & 0x3F));
X}
X
Xread_header() {
X short i, j;
X i = getchar() | (getchar() << 8);
X Table[1] = i & 1; i >>= 1;
X Table[2] = i & 3; i >>= 2;
X Table[3] = i & 7; i >>= 3;
X Table[4] = i & 0xF; i >>= 4;
X Table[5] = i & 0x1F;
X Table[6] = getchar() & 0x3F;
X
X i = Table[1] + Table[2] + Table[3] + Table[4] +
X Table[5] + Table[6];
X
X i = 62 - i; /* free variable length codes for 7 & 8 bits */
X
X j = 128 * Table[1] + 64 * Table[2] + 32 * Table[3] +
X 16 * Table[4] + 8 * Table[5] + 4 * Table[6];
X
X j = 256 - j; /* free byte images for these codes */
X
X/* Equation:
X Table[7] + Table[8] = i
X 2 * Table[7] + Table[8] = j
X*/
X j -= i;
X if (j < 0 || i < j) {
X corrupt_message();
X return EOF;
X }
X Table[7] = j;
X Table[8] = i - j;
X
X#ifdef DEBUG
X fprintf(stderr, "Codes: %d %d %d %d %d %d %d %d\n",
X Table[1], Table[2], Table[3], Table[4],
X Table[5], Table[6], Table[7], Table[8]);
X#endif
X return 0;
X}
X
Xcorrupt_message ( ) /* file too short or invalid header */
X{
X fprintf ( stderr, "melt: corrupt input\n" );
X}
END_OF_FILE
if test 8291 -ne `wc -c <'huf.c'`; then
echo shar: \"'huf.c'\" unpacked with wrong size!
fi
# end of 'huf.c'
fi
if test -f 'statist.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'statist.c'\"
else
echo shar: Extracting \"'statist.c'\" \(4475 characters\)
sed "s/^X//" >'statist.c' <<'END_OF_FILE'
X#include "freeze.h"
X#include "lz.h"
X#include "huf.h"
X
X#undef _NCHAR
X#define _NCHAR 62
X
Xlong in_count, bytes_out;
X
Xunsigned long indicator_threshold = 4096, indicator_count;
X
Xu_short bits[9];
X
Xshort prnt[_T + _NCHAR];
X
Xhash_t prev[N + 1];
X
X#ifndef __XENIX__
Xu_short next[array_size];
X#else
X#if parts == 2
Xu_short next0[32768], next1[8193];
X#elif parts == 3
Xu_short next0[32768], next1[32768], next2[8193];
X#elif parts == 5
Xu_short next0[32768], next1[32768], next2[32768], next3[32768], next4[8193];
X#else
Xu_short next0[32768], next1[32768], next2[32768], next3[32768], next4[32768],
X next5[32768], next6[32768], next7[32768], next8[8193];
X#endif
X
Xu_short *next[parts] = {
Xnext0, next1
X#if parts > 2
X,next2
X#if parts > 3
X,next3, next4
X#if parts > 5
X,next5, next6,
Xnext7, next8
X#endif
X#endif
X#endif
X};
X#endif
X
X#ifndef INT_SIG
Xvoid
X#endif
Xgiveres();
X
Xmain(argc) {
X if(argc != 1) {
X fprintf(stderr, "Usage: statist < sample_file\n");
X fprintf(stderr, "Press INTR to display current values\n");
X exit(0);
X }
X signal(SIGINT, giveres);
X freeze();
X giveres();
X}
X
X#ifndef INT_SIG
Xvoid
X#endif
Xgiveres() {
X u_short c;
X signal(SIGINT, giveres);
X for(c = 0; c < 62; c++) {
X register short *p;
X register int j, k;
X
X j = 0;
X p = prnt;
X k = p[c + T];
X
X do j++; while ((k = p[k]) != R) ;
X if (j <= 8)
X bits[j]++;
X }
X printf("%d %d %d %d %d %d %d %d\n",
X bits[1], bits[2], bits[3], bits[4],
X bits[5], bits[6], bits[7], bits[8]);
X fflush(stdout);
X for (c = 1; c <= 8; c++) bits[c] = 0;
X}
X
Xfreeze ()
X{
X register u_short i, len, r, s;
X register short c;
X StartHuff();
X InitTree();
X s = 0;
X r = N - _F;
X for (i = s; i < r; i++)
X text_buf[i] = ' ';
X for (len = 0; len < _F && (c = getchar()) != EOF; len++)
X text_buf[r + len] = c;
X in_count = len;
X for (i = 0; i <= _F; i++)
X InsertNode(r + i - _F);
X while (len != 0) {
X Get_Next_Match(r);
X if (match_length > len)
X match_length = len;
X if (match_length <= THRESHOLD) {
X match_length = 1;
X } else {
X register u_short orig_length, orig_position;
X orig_length = match_length;
X orig_position = match_position;
X DeleteNode(s);
X Next_Char();
X Get_Next_Match(r);
X if (match_length > len) match_length = len;
X if (orig_length > match_length) {
X update((u_short)orig_position >> 7);
X match_length = orig_length - 1;
X } else
X update(match_position >> 7);
X }
X for (i = 0; i < match_length &&
X (c = getchar()) != EOF; i++) {
X DeleteNode(s);
X text_buf[s] = c;
X if (s < _F - 1)
X text_buf[s + N] = c;
X s = (s + 1) & (N - 1);
X r = (r + 1) & (N - 1);
X InsertNode(r);
X }
X in_count += i;
X if ((in_count > indicator_count)) {
X fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
X fflush (stderr);
X indicator_count += indicator_threshold;
X }
X while (i++ < match_length) {
X DeleteNode(s);
X s = (s + 1) & (N - 1);
X r = (r + 1) & (N - 1);
X if (--len) InsertNode(r);
X }
X }
X}
X
Xuchar text_buf[N + _F - 1];
Xu_short match_position, match_length;
X
XInitTree ()
X{
X long i;
X for (i = N + 1; i < array_size; i++ )
X nextof(i) = NIL;
X for (i = 0; i < sizeof(prev)/sizeof(*prev); i++ )
X prev[i] = NIL;
X}
X
XGet_Next_Match (r)
X u_short r;
X{
X register uchar *key;
X register u_short m, i, p;
X key = &text_buf[p = r];
X m = 0;
X while(m < _F) {
X if ((p = nextof(p)) == NIL) {
X match_length = m;
X return;
X }
X if(key[m] != text_buf[p + m])
X continue;
X if(key[m >> 1] != text_buf[p + (m >> 1)])
X continue;
X for (i = 0; i < _F && key[i] == text_buf[p + i]; i++);
X if (i > m) {
X match_position = ((r - p) & (N - 1)) - 1;
X m = i;
X }
X }
X nextof(prev[p]) = nextof(p);
X prev[nextof(p)] = prev[p];
X prev[p] = NIL;
X match_length = _F;
X}
X
Xunsigned long freq[_T + 1];
X
Xshort son[_T];
X
XStartHuff ()
X{
X register short i, j;
X for (i = 0; i < N_CHAR; i++) {
X freq[i] = 1;
X son[i] = i + T;
X prnt[i + T] = i;
X }
X i = 0; j = N_CHAR;
X while (j <= R) {
X freq[j] = freq[i] + freq[i + 1];
X son[j] = i;
X prnt[i] = prnt[i + 1] = j;
X i += 2; j++;
X }
X freq[T] = 0xffffffff;
X prnt[R] = 0;
X in_count = 1;
X bytes_out = 2;
X}
X
Xupdate (c)
X u_short c;
X{
X register unsigned long *p, k;
X register u_short i, j, l;
X c = prnt[c + _T];
X do {
X k = ++freq[c];
X if (k > freq[l = c + 1]) {
X for (p = freq+l+1; k > *p++; ) ;
X l = p - freq - 2;
X freq[c] = p[-2];
X p[-2] = k;
X i = son[c];
X prnt[i] = l;
X if (i < _T) prnt[i + 1] = l;
X j = son[l];
X son[l] = i;
X prnt[j] = c;
X if (j < _T) prnt[j + 1] = c;
X son[c] = j;
X c = l;
X }
X } while ((c = prnt[c]) != 0);
X}
END_OF_FILE
if test 4475 -ne `wc -c <'statist.c'`; then
echo shar: \"'statist.c'\" unpacked with wrong size!
fi
# end of 'statist.c'
fi
echo shar: End of archive 1 \(of 2\).
cp /dev/null ark1isdone
MISSING=""
for I in 1 2 ; do
if test ! -f ark${I}isdone ; then
MISSING="${MISSING} ${I}"
fi
done
if test "${MISSING}" = "" ; then
echo You have unpacked both archives.
rm -f ark[1-9]isdone
else
echo You still must unpack the following archives:
echo " " ${MISSING}
fi
exit 0
exit 0 # Just in case...
--
Kent Landfield INTERNET: kent at sparky.IMD.Sterling.COM
Sterling Software, IMD UUCP: uunet!sparky!kent
Phone: (402) 291-8300 FAX: (402) 291-4362
Please send comp.sources.misc-related mail to kent at uunet.uu.net.
More information about the Comp.sources.misc
mailing list