Freeze/Melt program
Paul G. Antonov
apg at hq.demos.su
Sun Nov 25 05:42:06 AEST 1990
___________________________________________________
/ Please send the comments, bug fixes, \
| compression/speed improvement patches DIRECTLY to |
\ <leo at s514.ipmce.su>. /
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
This program is a "compilation" from compress - GNU FSF and
lharc (lzhuf) - H. Yoshizaki & M. Tagawa.
Two minor improvements were made - pipe facility and 20% speedup
by moving the code of GetBit routine into DecodeChar routine.
----------------------- cut here -------------------------
/*
* Freeze - data freezing program
* Version 1.0:
* This program is made from GNU compress.c and Yoshizaki/Tagawa's
* lzhuf.c. (Thanks to all of them.)
* The algorithm is modified for using in pipe
* (added ENDOF symbol in Huffman table).
* Version 1.1:
* Check for lack of bytes in frozen file when melting.
* Put the GetBit routine into DecodeChar for reduce function-
* call overhead when melting.
*
* I think the code is portable, but it is presently working only
* under SCO XENIX and ix/386 (compiled with GNU C).
*/
char magic_header[] = { "\037\236" }; /* 1F 9E = compress + 1 */
static char ident[] = "@(#) freeze.c 1.1 11/24/90 leo at s514.ipmce.su";
#include <stdio.h>
#include <ctype.h>
#include <signal.h>
#include <sys/types.h>
#include <sys/stat.h>
#ifdef MSDOS
#include <stdlib.h>
#endif
#define ARGVAL() (*++(*argv) || (--argc && *++argv))
int exit_stat = 0;
Usage() {
#ifdef DEBUG
# ifdef MSDOS
fprintf(stderr,"Usage: freeze [-cdDfivV] [file ...]\n");
# else
fprintf(stderr,"Usage: freeze [-cdDfvV] [file ...]\n");
# endif /* MSDOS */
}
int debug = 0;
#else
# ifdef MSDOS
fprintf(stderr,"Usage: freeze [-cdfivV] [file ...]\n");
# else
fprintf(stderr,"Usage: freeze [-cdfvV] [file ...]\n");
# endif /* MSDOS */
}
#endif /* DEBUG */
int fcat_flg = 0; /* Write output on stdout, suppress messages */
int precious = 1; /* Don't unlink output file on interrupt */
int quiet = 1; /* don't tell me about freezing */
/* Note indicator_threshold is triangle number of Kbytes (see below) */
long int indicator_threshold, indicator_count;
int force = 0;
char ofname [100];
#ifdef MSDOS
# define PATH_SEP '\\'
int image = 2; /* 1 <=> image (binary) mode; 2 <=> text mode */
#else
# define PATH_SEP '/'
#endif
#ifdef DEBUG
int verbose = 0;
char * pr_char();
long symbols_out = 0, refers_out = 0;
#endif /* DEBUG */
int (*bgnd_flag)();
int do_melt = 0;
/*****************************************************************
* TAG( main )
*
*
* Usage: freeze [-cdfivV] [file ...]
* Inputs:
*
* -c: Write output on stdout, don't remove original.
*
* -d: If given, melting is done instead.
*
* -f: Forces output file to be generated, even if one already
* exists, and even if no space is saved by freezeing.
* If -f is not used, the user will be prompted if stdin is
* a tty, otherwise, the output file will not be overwritten.
*
* -i: Image mode (defined only under MS-DOS). Prevents
* conversion between UNIX text representation (LF line
* termination) in frozen form and MS-DOS text
* representation (CR-LF line termination) in melted
* form. Useful with non-text files.
*
* -v: Write freezing statistics
*
* -V: Write version and compilation options.
*
* file ...: Files to be frozen. If none specified, stdin
* is used.
* Outputs:
* file.F: Frozen form of file with same mode, owner, and utimes
* or stdout (if stdin used as input)
*
* Assumptions:
* When filenames are given, replaces with the frozen version
* (.F suffix) only if the file decreases in size.
* Algorithm:
* Modified Lempel-Ziv-SS method (LZSS), adaptive Huffman coding
* for literal symbols and length info.
* Static Huffman coding for position info. (It is optimal ?)
* Lower bits of position info are put in output
* file without any coding because of their random distribution.
*/
/* From compress.c. Replace .Z --> .F etc */
main( argc, argv )
register int argc; char **argv;
{
int overwrite = 0; /* Do not overwrite unless given -f flag */
char tempname[100];
char **filelist, **fileptr;
char *cp, *rindex(), *malloc();
struct stat statbuf;
extern onintr();
#ifdef MSDOS
char *sufp;
#else
extern oops();
#endif
#ifndef MSDOS
#ifdef __GNUC__
if ( (bgnd_flag = (int (*) ()) signal ( SIGINT, SIG_IGN )) != (int (*) ()) SIG_IGN )
#else
if ( (bgnd_flag = signal ( SIGINT, SIG_IGN )) != SIG_IGN )
#endif
#endif
{
signal ( SIGINT, onintr );
#ifndef MSDOS
signal ( SIGSEGV, oops );
#endif
}
filelist = fileptr = (char **)(malloc(argc * sizeof(*argv)));
*filelist = NULL;
if((cp = rindex(argv[0], PATH_SEP)) != 0) {
cp++;
} else {
cp = argv[0];
}
#ifdef MSDOS
if(strcmp(cp, "MELT.EXE") == 0) {
#else
if(strcmp(cp, "melt") == 0) {
#endif
do_melt = 1;
#ifdef MSDOS
} else if(strcmp(cp, "FCAT.EXE") == 0) {
#else
} else if(strcmp(cp, "fcat") == 0) {
#endif
do_melt = 1;
fcat_flg = 1;
}
#ifdef BSD4_2
/* 4.2BSD dependent - take it out if not */
setlinebuf( stderr );
#endif /* BSD4_2 */
/* Argument Processing
* All flags are optional.
* -D => debug
* -V => print Version; debug verbose
* -d => do_melt
* -v => unquiet
* -f => force overwrite of output file
* -c => cat all output to stdout
* if a string is left, must be an input filename.
*/
for (argc--, argv++; argc > 0; argc--, argv++) {
if (**argv == '-') { /* A flag argument */
while (*++(*argv)) { /* Process all flags in this arg */
switch (**argv) {
#ifdef DEBUG
case 'D':
debug = 1;
break;
case 'V':
verbose = 1;
version();
break;
#else
case 'V':
version();
break;
#endif /* DEBUG */
#ifdef MSDOS
case 'i':
image = 1;
break;
#endif
case 'v':
quiet = 0;
break;
case 'd':
do_melt = 1;
break;
case 'f':
case 'F':
overwrite = 1;
force = 1;
break;
case 'c':
fcat_flg = 1;
break;
case 'q':
quiet = 1;
break;
default:
fprintf(stderr, "Unknown flag: '%c'; ", **argv);
Usage();
exit(1);
}
}
}
else { /* Input file name */
*fileptr++ = *argv; /* Build input file list */
*fileptr = NULL;
}
}
if (*filelist != NULL) {
for (fileptr = filelist; *fileptr; fileptr++) {
exit_stat = 0;
if (do_melt != 0) { /* MELTING */
#ifdef MSDOS
/* Check for .F or XF suffix; add one if necessary */
cp = *fileptr + strlen(*fileptr) - 2;
if ((*cp != '.' && *cp != 'X' && *cp != 'x') ||
(*(++cp) != 'F' && *cp != 'f')) {
strcpy(tempname, *fileptr);
if ((cp=rindex(tempname,'.')) == NULL)
strcat(tempname, ".F");
else if(*(++cp) == '\0') strcat(tempname, "F");
else {
*(++cp) = '\0';
strcat(tempname, "XF");
}
*fileptr = tempname;
}
#else
/* Check for .F suffix */
if (strcmp(*fileptr + strlen(*fileptr) - 2, ".F") != 0) {
/* No .F: tack one on */
strcpy(tempname, *fileptr);
strcat(tempname, ".F");
*fileptr = tempname;
}
#endif /*MSDOS */
/* Open input file for melting */
#ifdef MSDOS
if ((freopen(*fileptr, "rb", stdin)) == NULL)
#else
if ((freopen(*fileptr, "r", stdin)) == NULL)
#endif
{
perror(*fileptr); continue;
}
/* Check the magic number */
if ((getchar() != (magic_header[0] & 0xFF))
|| (getchar() != (magic_header[1] & 0xFF))) {
fprintf(stderr, "%s: not in frozen format\n",
*fileptr);
continue;
}
/* Generate output filename */
strcpy(ofname, *fileptr);
ofname[strlen(*fileptr) - 2] = '\0'; /* Strip off .F */
} else { /* FREEZING */
#ifdef MSDOS
cp = *fileptr + strlen(*fileptr) - 2;
if ((*cp == '.' || *cp == 'X' || *cp == 'x') &&
(*(++cp) == 'F' || *cp == 'f')) {
fprintf(stderr,"%s: already has %s suffix -- no change\n",
*fileptr,--cp); /* } */
#else
if (strcmp(*fileptr + strlen(*fileptr) - 2, ".F") == 0) {
fprintf(stderr, "%s: already has .F suffix -- no change\n",
*fileptr);
#endif /* MSDOS */
continue;
}
/* Open input file for freezing */
#ifdef MSDOS
if ((freopen(*fileptr, image == 2 ? "rt" : "rb", stdin))
== NULL)
#else
if ((freopen(*fileptr, "r", stdin)) == NULL)
#endif
{
perror(*fileptr); continue;
}
stat ( *fileptr, &statbuf );
/* Generate output filename */
strcpy(ofname, *fileptr);
#ifndef BSD4_2 /* Short filenames */
if ((cp = rindex(ofname, PATH_SEP)) != NULL) cp++;
else cp = ofname;
# ifdef MSDOS
if (fcat_flg == 0 && (sufp = rindex(cp, '.')) != NULL &&
strlen(sufp) > 2) fprintf(stderr,
"%s: part of filename extension will be replaced by XF\n",
cp);
# else
if (strlen(cp) > 12) {
fprintf(stderr,"%s: filename too long to tack on .F\n",cp);
continue;
}
# endif
#endif /* BSD4_2 Long filenames allowed */
#ifdef MSDOS
if ((cp = rindex(ofname, '.')) == NULL) strcat(ofname, ".F");
else {
if(*(++cp) != '\0') *(++cp) = '\0';
strcat(ofname, "XF");
}
#else
strcat(ofname, ".F");
#endif /* MSDOS */
}
precious = 0;
/* Check for overwrite of existing file */
if (overwrite == 0 && fcat_flg == 0) {
if (stat(ofname, &statbuf) == 0) {
char response[2];
response[0] = 'n';
fprintf(stderr, "%s already exists;", ofname);
#ifndef MSDOS
if (foreground()) {
#endif
fprintf(stderr,
" do you wish to overwrite %s (y or n)? ", ofname);
fflush(stderr);
read(2, response, 2);
while (response[1] != '\n') {
if (read(2, response+1, 1) < 0) { /* Ack! */
perror("stderr"); break;
}
}
#ifndef MSDOS
}
#endif
if (response[0] != 'y') {
fprintf(stderr, "\tnot overwritten\n");
continue;
}
}
}
if(fcat_flg == 0) { /* Open output file */
#ifdef DEBUG
if (do_melt == 0 || debug == 0) {
#endif
#ifdef MSDOS
if (freopen(ofname, do_melt && image == 2 ? "wt" : "wb",
stdout) == NULL)
#else
if (freopen(ofname, "w", stdout) == NULL)
#endif
{
perror(ofname); continue;
}
#ifdef DEBUG
}
#endif
if(!quiet) {
fprintf(stderr, "%s:", *fileptr);
indicator_threshold = 2048;
indicator_count = 1024;
}
}
/* Actually do the freezing/melting */
if (do_melt == 0) freeze();
#ifndef DEBUG
else melt();
#else
else if (debug == 0) melt();
else printcodes();
#endif /* DEBUG */
if(fcat_flg == 0) {
copystat(*fileptr, ofname); /* Copy stats */
if((exit_stat == 1) || (!quiet))
putc('\n', stderr);
}
}
} else { /* Standard input */
if (do_melt == 0) {
freeze();
if(!quiet)
putc('\n', stderr);
} else {
/* Check the magic number */
if ((getchar()!=(magic_header[0] & 0xFF))
|| (getchar()!=(magic_header[1] & 0xFF))) {
fprintf(stderr, "stdin: not in frozen format\n");
exit(1);
}
#ifndef DEBUG
melt();
#else
if (debug == 0) melt();
else printcodes();
#endif /* DEBUG */
}
}
exit(exit_stat);
}
long int in_count = 1; /* length of input */
long int bytes_out; /* length of frozen output */
/*----------------------------------------------------------------------*/
/* */
/* LZSS ENCODING (lzhuf.c) */
/* */
/*----------------------------------------------------------------------*/
#ifdef lint
#define N 256
#else
#define N 4096 /* buffer size */
#endif
#define F 60 /* pre-sence buffer size */
#define THRESHOLD 2
#define NIL N /* term of tree */
/*
* Increasing of N and F ( N = 8192, F = 80) gives 1.2 - 1.5% of additional
* reducing, but 2 times slower.
*/
unsigned char text_buf[N + F - 1];
unsigned int match_position, match_length;
short lson[N + 1], rson[N + 1 + N], dad[N + 1];
unsigned char same[N + 1];
/* Initialize Tree */
InitTree ()
{
register short *p, *e;
for (p = rson + N + 1, e = rson + N + N; p <= e; )
*p++ = NIL;
for (p = dad, e = dad + N; p < e; )
*p++ = NIL;
}
/* Insert to node */
InsertNode (r)
register int r;
{
register int p;
int cmp;
register unsigned char *key;
register unsigned int c;
register unsigned int i, j;
cmp = 1;
key = &text_buf[r];
i = key[1] ^ key[2];
i ^= i >> 4;
p = N + 1 + key[0] + ((i & 0x0f) << 8);
rson[r] = lson[r] = NIL;
match_length = 0;
i = j = 1;
for ( ; ; ) {
if (cmp >= 0) {
if (rson[p] != NIL) {
p = rson[p];
j = same[p];
} else {
rson[p] = r;
dad[r] = p;
same[r] = i;
return;
}
} else {
if (lson[p] != NIL) {
p = lson[p];
j = same[p];
} else {
lson[p] = r;
dad[r] = p;
same[r] = i;
return;
}
}
if (i > j) {
i = j;
cmp = key[i] - text_buf[p + i];
} else
if (i == j) {
for (; i < F; i++)
if ((cmp = key[i] - text_buf[p + i]) != 0)
break;
}
if (i > THRESHOLD) {
if (i > match_length) {
match_position = ((r - p) & (N - 1)) - 1;
if ((match_length = i) >= F)
break;
} else
if (i == match_length) {
if ((c = ((r - p) & (N - 1)) - 1) < match_position) {
match_position = c;
}
}
}
}
same[r] = same[p];
dad[r] = dad[p];
lson[r] = lson[p];
rson[r] = rson[p];
dad[lson[p]] = r;
dad[rson[p]] = r;
if (rson[dad[p]] == p)
rson[dad[p]] = r;
else
lson[dad[p]] = r;
dad[p] = NIL; /* remove p */
}
static
void
link (n, p, q)
int n, p, q;
{
register unsigned char *s1, *s2, *s3;
if (p >= NIL) {
same[q] = 1;
return;
}
s1 = text_buf + p + n;
s2 = text_buf + q + n;
s3 = text_buf + p + F;
while (s1 < s3) {
if (*s1++ != *s2++) {
#ifdef __GNUC__ /* Not an ideal compiler !! */
n = s1 - text_buf;
same[q] = n - 1 - p;
#else
same[q] = s1 - 1 - text_buf - p;
#endif
return;
}
}
same[q] = F;
}
linknode (p, q, r)
int p, q, r;
{
int cmp;
if ((cmp = same[q] - same[r]) == 0) {
link((int)same[q], p, r);
} else if (cmp < 0) {
same[r] = same[q];
}
}
DeleteNode (p)
register int p;
{
register int q;
if (dad[p] == NIL)
return; /* has no linked */
if (rson[p] == NIL) {
if ((q = lson[p]) != NIL)
linknode(dad[p], p, q);
} else
if (lson[p] == NIL) {
q = rson[p];
linknode(dad[p], p, q);
} else {
q = lson[p];
if (rson[q] != NIL) {
do {
q = rson[q];
} while (rson[q] != NIL);
if (lson[q] != NIL)
linknode(dad[q], q, lson[q]);
link(1, q, lson[p]);
rson[dad[q]] = lson[q];
dad[lson[q]] = dad[q];
lson[q] = lson[p];
dad[lson[p]] = q;
}
link(1, dad[p], q);
link(1, q, rson[p]);
rson[q] = rson[p];
dad[rson[p]] = q;
}
dad[q] = dad[p];
if (rson[dad[p]] == p)
rson[dad[p]] = q;
else
lson[dad[p]] = q;
dad[p] = NIL;
}
/*----------------------------------------------------------------------*/
/* */
/* HUFFMAN ENCODING */
/* */
/*----------------------------------------------------------------------*/
#define N_CHAR (256 - THRESHOLD + F + 1) /* {code : 0 .. N_CHAR-1} */
#define T (N_CHAR * 2 - 1) /* size of table */
#define R (T - 1) /* root position */
#define MAX_FREQ (unsigned)0x8000 /* tree update timing from frequency */
#define ENDOF 256
typedef unsigned char uchar;
/* TABLE OF ENCODE/DECODE for upper 6bits position information */
/* for encode */
uchar p_len[64] = {
0x03, 0x04, 0x04, 0x04, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08
};
uchar p_code[64] = {
0x00, 0x20, 0x30, 0x40, 0x50, 0x58, 0x60, 0x68,
0x70, 0x78, 0x80, 0x88, 0x90, 0x94, 0x98, 0x9C,
0xA0, 0xA4, 0xA8, 0xAC, 0xB0, 0xB4, 0xB8, 0xBC,
0xC0, 0xC2, 0xC4, 0xC6, 0xC8, 0xCA, 0xCC, 0xCE,
0xD0, 0xD2, 0xD4, 0xD6, 0xD8, 0xDA, 0xDC, 0xDE,
0xE0, 0xE2, 0xE4, 0xE6, 0xE8, 0xEA, 0xEC, 0xEE,
0xF0, 0xF1, 0xF2, 0xF3, 0xF4, 0xF5, 0xF6, 0xF7,
0xF8, 0xF9, 0xFA, 0xFB, 0xFC, 0xFD, 0xFE, 0xFF
};
/* for decode */
uchar d_code[256] = {
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01, 0x01,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02, 0x02,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09, 0x09,
0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A, 0x0A,
0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B, 0x0B,
0x0C, 0x0C, 0x0C, 0x0C, 0x0D, 0x0D, 0x0D, 0x0D,
0x0E, 0x0E, 0x0E, 0x0E, 0x0F, 0x0F, 0x0F, 0x0F,
0x10, 0x10, 0x10, 0x10, 0x11, 0x11, 0x11, 0x11,
0x12, 0x12, 0x12, 0x12, 0x13, 0x13, 0x13, 0x13,
0x14, 0x14, 0x14, 0x14, 0x15, 0x15, 0x15, 0x15,
0x16, 0x16, 0x16, 0x16, 0x17, 0x17, 0x17, 0x17,
0x18, 0x18, 0x19, 0x19, 0x1A, 0x1A, 0x1B, 0x1B,
0x1C, 0x1C, 0x1D, 0x1D, 0x1E, 0x1E, 0x1F, 0x1F,
0x20, 0x20, 0x21, 0x21, 0x22, 0x22, 0x23, 0x23,
0x24, 0x24, 0x25, 0x25, 0x26, 0x26, 0x27, 0x27,
0x28, 0x28, 0x29, 0x29, 0x2A, 0x2A, 0x2B, 0x2B,
0x2C, 0x2C, 0x2D, 0x2D, 0x2E, 0x2E, 0x2F, 0x2F,
0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
0x38, 0x39, 0x3A, 0x3B, 0x3C, 0x3D, 0x3E, 0x3F,
};
uchar d_len[256] = {
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
};
unsigned short freq[T + 1]; /* frequency table */
short prnt[T + N_CHAR]; /* points to parent node */
/* notes :
prnt[T .. T + N_CHAR - 1] used by
indicates leaf position that corresponding to code */
short son[T]; /* points to son node (son[i],son[i+]) */
unsigned short getbuf = 0;
uchar getlen = 0;
uchar corrupt_flag = 0; /* If a file is corrupt, use fcat */
/* get one byte */
/* returning in Bit7...0 */
int GetByte ()
{
register unsigned short int dx = getbuf;
register unsigned int c;
if (getlen <= 8) {
c = getchar ();
if ((int)c < 0) {
/* Frozen file is too short. This is fatal error.
* Really the second absent byte indicates a error.
* ("Packed file is corrupt." :-) )
*/
if (corrupt_flag)
oops();
corrupt_flag = 1;
c = 0;
}
dx |= c << (8 - getlen);
getlen += 8;
}
getbuf = dx << 8;
getlen -= 8;
return (dx >> 8) & 0xff;
}
/* get N bit */
/* returning in Bit(N-1)...Bit 0 */
int GetNBits (n)
register unsigned int n;
{
register unsigned int dx = getbuf;
register unsigned int c;
static int mask[17] = {
0x0000,
0x0001, 0x0003, 0x0007, 0x000f,
0x001f, 0x003f, 0x007f, 0x00ff,
0x01ff, 0x03ff, 0x07ff, 0x0fff,
0x1fff, 0x3fff, 0x7fff, 0xffff };
static int shift[17] = {
16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
if (getlen <= 8)
{
c = getchar ();
if ((int)c < 0) {
if (corrupt_flag)
oops();
corrupt_flag = 1;
c = 0;
}
dx |= c << (8 - getlen);
getlen += 8;
}
getbuf = dx << n;
getlen -= n;
return (dx >> shift[n]) & mask[n];
}
unsigned short putbuf = 0;
uchar putlen = 0;
/* output C bits */
Putcode (l, c)
register int l;
unsigned int c;
{
register short len = putlen;
register unsigned short b = putbuf;
b |= c >> len;
if ((len += l) >= 8) {
if (putchar (b >> 8) == EOF) writeerr();
if ((len -= 8) >= 8) {
putchar (b);
bytes_out += 2;
len -= 8;
b = c << (l - len);
} else {
b <<= 8;
bytes_out++;
}
}
putbuf = b;
putlen = len;
}
/* Initialize tree */
StartHuff ()
{
register int i, j;
for (i = 0; i < N_CHAR; i++) {
freq[i] = 1;
son[i] = i + T;
prnt[i + T] = i;
}
i = 0; j = N_CHAR;
while (j <= R) {
freq[j] = freq[i] + freq[i + 1];
son[j] = i;
prnt[i] = prnt[i + 1] = j;
i += 2; j++;
}
freq[T] = 0xffff;
prnt[R] = 0;
in_count = 1;
bytes_out = 2;
#ifdef DEBUG
symbols_out = refers_out = 0;
#endif
putlen = getlen = 0;
putbuf = getbuf = 0;
corrupt_flag = 0;
}
/* reconstruct tree */
reconst ()
{
register int i, j, k;
register unsigned f;
#ifdef DEBUG
if (!quiet)
fprintf(stderr,
"Reconstructing Huffman tree: symbols: %ld, references: %ld\n",
symbols_out, refers_out);
#endif
/* correct leaf node into of first half,
and set these freqency to (freq+1)/2 */
j = 0;
for (i = 0; i < T; i++) {
if (son[i] >= T) {
freq[j] = (freq[i] + 1) / 2;
son[j] = son[i];
j++;
}
}
/* build tree. Link sons first */
for (i = 0, j = N_CHAR; j < T; i += 2, j++) {
k = i + 1;
f = freq[j] = freq[i] + freq[k];
for (k = j - 1; f < freq[k]; k--);
k++;
{ register unsigned short *p, *e;
for (p = &freq[j], e = &freq[k]; p > e; p--)
p[0] = p[-1];
freq[k] = f;
}
{ register short *p, *e;
for (p = &son[j], e = &son[k]; p > e; p--)
p[0] = p[-1];
son[k] = i;
}
}
/* link parents */
for (i = 0; i < T; i++) {
if ((k = son[i]) >= T) {
prnt[k] = i;
} else {
prnt[k] = prnt[k + 1] = i;
}
}
}
/* update given code's frequency, and update tree */
update (c)
unsigned int c;
{
register unsigned short *p;
register int i, j, k, l;
if (freq[R] == MAX_FREQ) {
reconst();
}
c = prnt[c + T];
do {
k = ++freq[c];
/* swap nodes when become wrong frequency order. */
if (k > freq[l = c + 1]) {
for (p = freq+l+1; k > *p++; ) ;
l = p - freq - 2;
freq[c] = p[-2];
p[-2] = k;
i = son[c];
prnt[i] = l;
if (i < T) prnt[i + 1] = l;
j = son[l];
son[l] = i;
prnt[j] = c;
if (j < T) prnt[j + 1] = c;
son[c] = j;
c = l;
}
} while ((c = prnt[c]) != 0); /* loop until reach to root */
}
/* unsigned code, len; */
EncodeChar (c)
unsigned c;
{
register short *p;
unsigned long i;
register int j, k;
i = 0;
j = 0;
p = prnt;
k = p[c + T];
/* trace links from leaf node to root */
do {
i >>= 1;
/* if node index is odd, trace larger of sons */
if (k & 1) i += 0x80000000;
j++;
} while ((k = p[k]) != R) ;
if (j > 16) {
Putcode(16, (unsigned int)(i >> 16));
Putcode(j - 16, (unsigned int)i);
} else {
Putcode(j, (unsigned int)(i >> 16));
}
/* code = i; */
/* len = j; */
update(c);
}
EncodePosition (c)
register unsigned c;
{
register unsigned i;
/* output upper 6bit from table */
i = c >> 6;
Putcode((int)(p_len[i]), (unsigned int)(p_code[i]) << 8);
/* output lower 6 bit */
Putcode(6, (unsigned int)(c & 0x3f) << 10);
}
EncodeEnd ()
{
if (putlen) {
putchar(putbuf >> 8);
bytes_out++;
}
}
int DecodeChar ()
{
register unsigned c;
register unsigned short dx;
register unsigned short cc;
c = son[R];
/* trace from root to leaf,
got bit is 0 to small(son[]), 1 to large (son[]+1) son node */
while (c < T) {
dx = getbuf;
if (getlen <= 8) {
if ((short)(cc = getchar()) < 0) {
if (corrupt_flag)
oops();
corrupt_flag = 1;
cc = 0;
}
dx |= cc << (8 - getlen);
getlen += 8;
}
getbuf = dx << 1;
getlen--;
c += (dx >> 15) & 1;
c = son[c];
}
c -= T;
update(c);
return c;
}
int DecodePosition ()
{
register unsigned short i, j, c;
/* decode upper 6bit from table */
i = GetByte();
c = (unsigned)d_code[i] << 6;
j = d_len[i];
/* get lower 6bit */
j -= 2;
return c | (((i << j) | GetNBits (j)) & 0x3f);
}
/*
* freeze stdin to stdout (as in compress.c & lzhuf.c)
*/
freeze ()
{
register int i, c, len, r, s, last_match_length;
putchar(magic_header[0]);
putchar(magic_header[1]);
StartHuff();
InitTree();
s = 0;
r = N - F;
for (i = s; i < r; i++)
text_buf[i] = ' ';
for (len = 0; len < F && (c = getchar()) != EOF; len++)
text_buf[r + len] = c;
in_count = len;
for (i = 1; i <= F; i++)
InsertNode(r - i);
InsertNode(r);
while (len > 0) {
if (match_length > len)
match_length = len;
if (match_length <= THRESHOLD) {
match_length = 1;
EncodeChar(text_buf[r]);
#ifdef DEBUG
symbols_out ++;
if (verbose)
fprintf(stderr, "'%s'\n", pr_char(text_buf[r]));
#endif /* DEBUG */
} else {
EncodeChar(256 - THRESHOLD + match_length);
EncodePosition(match_position);
#ifdef DEBUG
refers_out ++;
if (verbose) {
register int pos = (r - 1 - match_position) & (N - 1),
len = match_length;
fputc('"', stderr);
for(;len;len--, pos++)
fprintf(stderr, "%s", pr_char(text_buf[pos]));
fprintf(stderr, "\"\n");
}
#endif /* DEBUG */
}
last_match_length = match_length;
for (i = 0; i < last_match_length &&
(c = getchar()) != EOF; i++) {
DeleteNode(s);
text_buf[s] = c;
if (s < F - 1)
text_buf[s + N] = c;
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
InsertNode(r);
}
in_count += i;
if ((in_count > indicator_count) && !quiet) {
fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
fflush (stderr);
indicator_count += indicator_threshold;
indicator_threshold += 1024;
}
while (i++ < last_match_length) {
DeleteNode(s);
s = (s + 1) & (N - 1);
r = (r + 1) & (N - 1);
if (--len) InsertNode(r);
}
}
EncodeChar(ENDOF);
#ifdef DEBUG
symbols_out ++;
#endif
EncodeEnd();
/*
* Print out stats on stderr
*/
if(!quiet) {
#ifdef DEBUG
fprintf( stderr,
"%ld chars in, %ld codes (%ld bytes) out, freezing factor: ",
in_count, symbols_out + refers_out, bytes_out);
prratio( stderr, in_count, bytes_out );
fprintf( stderr, "\n");
fprintf( stderr, "\tFreezing as in compact: " );
prratio( stderr, in_count-bytes_out, in_count );
fprintf( stderr, "\n");
fprintf( stderr, "\tSymbols: %ld; references: %ld.\n",
symbols_out, refers_out);
#else /* !DEBUG */
fprintf( stderr, "Freezing: " );
prratio( stderr, in_count-bytes_out, in_count );
#endif /* DEBUG */
}
if(bytes_out > in_count) /* exit(2) if no savings */
exit_stat = 2;
return;
}
/*
* Melt stdin to stdout.
* Works =~= 1.5 times faster than uncompress (relatively to decompressed
* filesize) - on 16-bit machines.
* !! DO NOT (!!) use arithmetic compression - it is extremely
* slow when decompressing.
*/
melt ()
{
register int i, j, k, r, c;
StartHuff();
for (i = 0; i < N - F; i++)
text_buf[i] = ' ';
r = N - F;
for (in_count = 0;; ) {
c = DecodeChar();
if (c == ENDOF)
break;
if (c < 256) {
putchar (c);
text_buf[r++] = c;
r &= (N - 1);
in_count++;
} else {
i = (r - DecodePosition() - 1) & (N - 1);
j = c - 256 + THRESHOLD;
for (k = 0; k < j; k++) {
c = text_buf[(i + k) & (N - 1)];
putchar (c);
text_buf[r++] = c;
r &= (N - 1);
in_count++;
}
}
if (!quiet && (in_count > indicator_count)) {
fprintf(stderr, "%5dK\b\b\b\b\b\b", in_count / 1024);
fflush (stderr);
indicator_count += indicator_threshold;
indicator_threshold += 1024;
}
}
}
char *
rindex(s, c) /* For those who don't have it in libc.a */
register char *s, c;
{
char *p;
for (p = NULL; *s; s++)
if (*s == c)
p = s;
return(p);
}
#ifdef DEBUG
printcodes()
{
/*
* Just print out codes from input file. For debugging.
*/
register int k, c, col = 0;
StartHuff();
for (;;) {
c = DecodeChar();
if (c == ENDOF)
break;
if (c < 256) {
fprintf(stderr, "%5d%c", c, (col+=8) >= 74 ? (col = 0, '\n') : '\t' );
} else {
c = c - 256 + THRESHOLD;
k = DecodePosition();
fprintf(stderr, "%2d-%d%c", c, k, (col+=8) >= 74 ? (col = 0, '\n') : '\t' );
}
}
putc( '\n', stderr );
exit( 0 );
}
/* for pretty char printing */
char *
pr_char(c)
register unsigned char c;
{
static char buf[5];
register i = 4;
buf[4] = '\0';
if ( (isascii(c) && isprint(c) && c != '\\') || c == ' ' ) {
buf[--i] = c;
} else {
switch( c ) {
case '\n': buf[--i] = 'n'; break;
case '\t': buf[--i] = 't'; break;
case '\b': buf[--i] = 'b'; break;
case '\f': buf[--i] = 'f'; break;
case '\r': buf[--i] = 'r'; break;
case '\\': buf[--i] = '\\'; break;
default:
buf[--i] = '0' + c % 8;
buf[--i] = '0' + (c / 8) % 8;
buf[--i] = '0' + c / 64;
break;
}
buf[--i] = '\\';
}
return &buf[i];
}
#endif /* DEBUG */
writeerr()
{
perror ( ofname );
unlink ( ofname );
exit ( 1 );
}
copystat(ifname, ofname)
char *ifname, *ofname;
{
struct stat statbuf;
int mode;
time_t timep[2];
#ifdef MSDOS
if (_osmajor < 3) freopen("CON","at",stdout); else /* MS-DOS 2.xx bug */
#endif
fclose(stdout);
if (stat(ifname, &statbuf)) { /* Get stat on input file */
perror(ifname);
return;
}
#ifndef MSDOS
if ((statbuf.st_mode & S_IFMT) != S_IFREG) {
if(quiet)
fprintf(stderr, "%s: ", ifname);
fprintf(stderr, " not a regular file: unchanged");
exit_stat = 1;
} else if (statbuf.st_nlink > 1) {
if(quiet)
fprintf(stderr, "%s: ", ifname);
fprintf(stderr, " has %d other links: unchanged",
statbuf.st_nlink - 1);
exit_stat = 1;
} else if (exit_stat == 2 && (!force)) { /* No freezing: remove file.Z */
#else
if (exit_stat == 2 && (!force)) { /* No freezing: remove file.Z */
#endif /* MSDOS */
if(!quiet)
fprintf(stderr, " file unchanged");
} else { /* ***** Successful Freezing ***** */
exit_stat = 0;
mode = statbuf.st_mode & 07777;
if (chmod(ofname, mode)) /* Copy modes */
perror(ofname);
#ifndef MSDOS
chown(ofname, statbuf.st_uid, statbuf.st_gid); /* Copy ownership */
#endif
timep[0] = statbuf.st_atime;
timep[1] = statbuf.st_mtime;
utime(ofname, timep); /* Update last accessed and modified times */
precious = 1;
if (unlink(ifname)) /* Remove input file */
perror(ifname);
if(!quiet)
fprintf(stderr, " -- replaced with %s", ofname);
return; /* Successful return */
}
/* Unsuccessful return -- one of the tests failed */
if (unlink(ofname))
perror(ofname);
}
#ifndef MSDOS
/*
* This routine returns 1 if we are running in the foreground and stderr
* is a tty.
*/
foreground()
{
#ifdef __GNUC__
if(bgnd_flag != (int (*) ()) SIG_DFL) /* background? */
#else
if(bgnd_flag != SIG_DFL) /* background? */
#endif
return(0);
else { /* foreground */
if(isatty(2)) { /* and stderr is a tty */
return(1);
} else {
return(0);
}
}
}
#endif
onintr ( )
{
if (!precious)
unlink ( ofname );
exit ( 1 );
}
oops ( ) /* wild index -- assume bad input (or file too short) */
{
if ( do_melt == 1 )
fprintf ( stderr, "melt: corrupt input\n" );
if ( fcat_flg == 1)
fflush(stdout); /* Something is better than nothing */
else
unlink ( ofname );
exit ( 1 );
}
prratio(stream, num, den)
FILE *stream;
long int num, den;
{
#ifdef DEBUG
register long q; /* permits |result| > 655.36% */
#else
register int q; /* Doesn't need to be long */
#endif
if (!den) den++;
if(num > 214748L) { /* 2147483647/10000 */
q = num / (den / 10000L);
} else {
q = 10000L * num / den; /* Long calculations, though */
}
if (q < 0) {
putc('-', stream);
q = -q;
}
fprintf(stream, "%d.%02d%%", (int)(q / 100), (int)(q % 100));
}
version()
{
fprintf(stderr, "%s\n", ident);
fprintf(stderr, "Options: ");
#ifdef DEBUG
fprintf(stderr, "DEBUG, ");
#endif
#ifdef BSD4_2
fprintf(stderr, "BSD4_2, ");
#endif
#ifdef M_XENIX
fprintf(stderr, "XENIX, ");
#endif
fprintf(stderr, "LZSS: %d (table), %d (match length);\n", N, F);
fprintf(stderr, "HUFFMAN: %ld (max frequency)\n", (long)MAX_FREQ);
}
----------------------- cut here -------------------------
More information about the Alt.sources
mailing list