/* * Compress.c - data compression/decompression routines. * This is an adaptation of the public domain Un*x compress v4.0. */ #include #include #define min(a,b) ((a>b) ? b : a) #ifdef DEBUG #define DBG(x) x #else #define DBG(x) #endif extern int errno; /* * Set USERMEM to the maximum amount of physical user memory available * in bytes. USERMEM is used to determine the maximum BITS that can be used * for compression. * * SACREDMEM is the amount of physical memory saved for others; compress * will hog the rest. */ #ifndef SACREDMEM #define SACREDMEM 0 #endif #ifndef USERMEM # define USERMEM 450000 /* default user memory */ #endif # define MAXFILES 100 /* arbitrary maximum - see note below */ # define BITS 12 /* > 12 crashes system (?) */ # undef USERMEM long filesize(); char *scdir(); #ifdef USERMEM # if USERMEM >= (433484+SACREDMEM) # define PBITS 16 # else # if USERMEM >= (229600+SACREDMEM) # define PBITS 15 # else # if USERMEM >= (127536+SACREDMEM) # define PBITS 14 # else # if USERMEM >= (73464+SACREDMEM) # define PBITS 13 # else # define PBITS 12 # endif # endif # endif # endif # undef USERMEM #endif /* USERMEM */ #ifdef PBITS /* Preferred BITS for this memory size */ # ifndef BITS # define BITS PBITS # endif BITS #endif /* PBITS */ #if BITS == 16 # define HSIZE 69001L /* 95% occupancy */ #endif #if BITS == 15 # define HSIZE 35023L /* 94% occupancy */ #endif #if BITS == 14 # define HSIZE 18013L /* 91% occupancy */ #endif #if BITS == 13 # define HSIZE 9001L /* 91% occupancy */ #endif #if BITS <= 12 # define HSIZE 5003L /* 80% occupancy */ #endif /* * a code_int must be able to hold 2**BITS values of type int, and also -1 */ #if BITS > 15 typedef long int code_int; #else typedef int code_int; #endif #ifdef SIGNED_COMPARE_SLOW typedef unsigned long int count_int; typedef unsigned short int count_short; #else typedef long int count_int; #endif #ifdef NO_UCHAR typedef char char_type; #else typedef unsigned char char_type; #endif /* UCHAR */ char_type magic_header[]= { "\037\235" }; /* 1F 9D */ /* Defines for third byte of header */ #define BIT_MASK 0x1f #define BLOCK_MASK 0x80 /* Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is a fourth header byte (for expansion). */ #define INIT_BITS 9 /* initial number of bits/code */ /* * 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) * Mark R. Rinfret (mods) (mark@unisec.USI.COM) */ int n_bits; /* number of bits/code */ int maxbits = BITS; /* user settable max # bits/code */ code_int maxcode; /* maximum code, given n_bits */ code_int maxmaxcode = 1 << BITS; /* NEVER generate this code */ #define MAXCODE(n_bits) ((1 << (n_bits)) - 1) count_int htab [HSIZE]; unsigned short codetab [HSIZE]; #define htabof(i) htab[i] #define codetabof(i) codetab[i] code_int hsize = HSIZE; /* for dynamic table sizing */ count_int fsize; static FILE *infile, *outfile; static char iname[256], oname[256]; /* * To save much memory, we overlay the table used by compress() with those * used by decompress(). The tab_prefix table is the same size and type * as the codetab. The tab_suffix table needs 2**BITS characters. We * get this from the beginning of htab. The output stack uses the rest * of htab, and contains characters. There is plenty of room for any * possible stack (stack used to be 8000 characters). */ #define tab_prefixof(i) codetabof(i) #define tab_suffixof(i) ((char_type *)(htab))[i] #define de_stack ((char_type *)&tab_suffixof(1< BITS) maxbits = BITS; maxmaxcode = 1 << maxbits; } static int offset; static long int in_count = 1; /* length of input */ static long int bytes_out; /* length of compressed output */ static long int out_count = 0; /* # of codes output (for debugging) */ /* * compress "from" to "to" * * Algorithm: use open addressing double hashing (no chaining) on the * prefix code / next character combination. We do a variant of Knuth's * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime * secondary probe. Here, the modular division first probe is gives way * to a faster exclusive-or manipulation. Also do block compression with * an adaptive reset, whereby the code table is cleared when the compression * ratio decreases, but after the table fills. The variable-length output * codes are re-sized at this point, and a special CLEAR code is generated * for the decompressor. Late addition: construct the table according to * file size for noticeable speed improvement on small files. Please direct * questions about this implementation to ames!jaw. */ int compress(from, to) char *from, *to; { register long fcode; register code_int i = 0; register int c; register code_int ent; register int disp; register code_int hsize_reg; register int hshift; int fail = 0; char *s; char *err_msg[256]; comp_init(); /* * tune hash table size for small files -- ad hoc, * but the sizes match earlier #defines, which * serve as upper bounds on the number of output codes. */ hsize = HSIZE; if (fsize < (1L << 12)) hsize = min (5003L,HSIZE ); else if (fsize < (1L << 13)) hsize = min (9001L,HSIZE ); else if (fsize < (1L << 14)) hsize = min (18013L,HSIZE ); else if (fsize < (1L << 15)) hsize = min (35023L,HSIZE ); else if (fsize < 47000L ) hsize = min (50021L,HSIZE ); if (!(infile = fopen(from,"r"))) { perror(from); return 1; } if (!(outfile = fopen(to,"w"))) { perror(to); fclose(infile); return 1; } if (nomagic == 0){ putc(magic_header[0],outfile); putc(magic_header[1],outfile); putc((char)(maxbits | block_compress),outfile); if(ferror(outfile)) { writeerr(); ++fail; cleanup: fclose(infile); fclose(outfile); return fail; } } offset = 0; bytes_out = 3; /* includes 3-byte header mojo */ out_count = 0; clear_flg = 0; ratio = 0L; in_count = 1; checkpoint = CHECK_GAP; maxcode = MAXCODE(n_bits = INIT_BITS); free_ent = ((block_compress)?FIRST :256 ); ent = getc (infile); hshift = 0; for (fcode = (long)hsize;fcode < 65536L;fcode *= 2L ) hshift++; hshift = 8 - hshift; /* set hash code range bound */ hsize_reg = hsize; cl_hash((count_int)hsize_reg); /* clear hash table */ while ((c = getc(infile))!= EOF ){ in_count++; fcode = (long)(((long)c << maxbits)+ ent); i = ((c << hshift)^ ent); /* xor hashing */ if (htabof (i)== fcode ){ ent = codetabof (i); continue; } else if ((long)htabof (i)< 0 )/* empty slot */ goto nomatch; disp = hsize_reg - i; /* secondary hash (after G. Knott) */ if (i == 0 ) disp = 1; probe: if ((i -= disp)< 0 ) i += hsize_reg; if (htabof (i)== fcode ){ ent = codetabof (i); continue; } if ((long)htabof (i)> 0 ) goto probe; nomatch: output ((code_int)ent ); out_count++; ent = c; if (free_ent < maxmaxcode ){ codetabof (i)= free_ent++;/* code -> hashtable */ htabof (i)= fcode; } else if ((count_int)in_count >= checkpoint && block_compress ) cl_block (); } /* * Put out the final code. */ output((code_int)ent ); out_count++; output((code_int)-1 ); /* * Print out stats on stderr */ if(zcat_flg == 0 && !quiet){ #ifdef DEBUG fprintf(stderr, "%ld chars in, %ld codes (%ld bytes) out, compression factor: ", in_count,out_count,bytes_out ); prratio(stderr,in_count,bytes_out ); fprintf(stderr,"\n"); fprintf(stderr,"\tCompression as in compact: " ); prratio(stderr,in_count-bytes_out,in_count ); fprintf(stderr,"\n"); fprintf(stderr,"\tLargest code (of last block) was %d (%d bits)\n", free_ent - 1,n_bits ); #else /* !DEBUG */ fprintf(stderr,"Compression: " ); prratio(stderr,in_count-bytes_out,in_count ); #endif /* DEBUG */ } if(bytes_out > in_count) /* exit(2) if no savings */ exit_stat = 2; goto cleanup; } /***************************************************************** * TAG( output ) * * Output the given code. * Inputs: * code: A n_bits-bit integer. If == -1, then EOF. This assumes * that n_bits =< (long)wordsize - 1. * Outputs: * Outputs code to the file. * Assumptions: * Chars are 8 bits long. * Algorithm: * Maintain a BITS character long buffer (so that 8 codes will * fit in it exactly). Use the VAX insv instruction to insert each * code in turn. When the buffer fills up empty it and start over. */ static char buf[BITS]; char_type lmask[9]= { 0xff,0xfe,0xfc,0xf8,0xf0,0xe0,0xc0,0x80,0x00 }; char_type rmask[9]= { 0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f,0xff }; output(code ) code_int code; { #ifdef DEBUG static int col = 0; #endif /* DEBUG */ register int r_off = offset,bits= n_bits; register char * bp = buf; #ifdef DEBUG if (verbose ) fprintf(stderr,"%5d%c",code, (col+=6)>= 74 ?(col = 0,'\n'):' ' ); #endif /* DEBUG */ if (code >= 0 ){ /* * byte/bit numbering on the VAX is simulated by the following code */ /* * Get to the first byte. */ bp += (r_off >> 3); r_off &= 7; /* * Since code is always >= 8 bits, only need to mask the first * hunk on the left. */ *bp = (*bp & rmask[r_off])| (code << r_off)& lmask[r_off]; bp++; bits -= (8 - r_off); code >>= 8 - r_off; /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ if (bits >= 8 ){ *bp++= code; code >>= 8; bits -= 8; } /* Last bits. */ if(bits) *bp = code; offset += n_bits; if (offset == (n_bits << 3)){ bp = buf; bits = n_bits; bytes_out += bits; do putc(*bp++, outfile); while(--bits); offset = 0; } /* * If the next entry is going to be too big for the code size, * then increase it, if possible. */ if (free_ent > maxcode || (clear_flg > 0)){ /* * Write the whole buffer, because the input side won't * discover the size increase until after it has read it. */ if (offset > 0 ){ if(fwrite(buf,1,n_bits,outfile)!= n_bits) { writeerr(); return 1; } bytes_out += n_bits; } offset = 0; if (clear_flg ){ maxcode = MAXCODE (n_bits = INIT_BITS); clear_flg = 0; } else { n_bits++; if (n_bits == maxbits ) maxcode = maxmaxcode; else maxcode = MAXCODE(n_bits); } #ifdef DEBUG if (debug ){ fprintf(stderr,"\nChange to %d bits\n",n_bits ); col = 0; } #endif /* DEBUG */ } } else { /* * At EOF, write the rest of the buffer. */ if (offset > 0 ) fwrite(buf,1,(offset + 7)/ 8,outfile); bytes_out += (offset + 7)/ 8; offset = 0; fflush(outfile); #ifdef DEBUG if (verbose ) fprintf(stderr,"\n" ); #endif /* DEBUG */ if(ferror(outfile)) { writeerr(); return 1; } } return 0; } /* * Decompress infile to outfile. This routine adapts to the codes in the * file building the "string" table on-the-fly; requiring no table to * be stored in the compressed file. The tables used herein are shared * with those of the compress() routine. See the definitions above. */ int decompress(from, to) char *from, *to; { register char_type *stackp; register int finchar; register code_int code,oldcode,incode; int fail = 0; if (!(infile = fopen(from, "r"))) { printf("decompress: %s failed to open for input!\n",from); return errno; } if (!(outfile = fopen(to, "w"))) { printf("decompress: %s failed to open for output!\n",to); fclose(infile); return errno; } if (nomagic == 0){ if ((getc(infile)!= (magic_header[0]& 0xFF)) || (getc(infile)!= (magic_header[1]& 0xFF))){ fprintf(stderr,"decompress: %s not in compressed format\n", from); ++fail; cleanup: fclose(infile); fclose(outfile); return fail; } maxbits = getc(infile);/* set -b from file */ block_compress = maxbits & BLOCK_MASK; maxbits &= BIT_MASK; maxmaxcode = 1 << maxbits; if(maxbits > BITS){ fprintf(stderr, "%s: compressed with %d bits, can only handle %d bits\n", from,maxbits,BITS); ++fail; goto cleanup; } } /* * As above, initialize the first 256 entries in the table. */ maxcode = MAXCODE(n_bits = INIT_BITS); for (code = 255;code >= 0;code--){ tab_prefixof(code)= 0; tab_suffixof(code)= (char_type)code; } free_ent = ((block_compress)?FIRST :256 ); finchar = oldcode = getcode(); if(oldcode == -1) /* EOF already? */ /*return ;*/ /* Get out of here */ goto cleanup; putc((char)finchar,outfile ); /* first code must be 8 bits = char */ if(ferror(outfile)) { /* Crash if can't write */ writeerr (); ++fail; goto cleanup; } stackp = de_stack; while ((code = getcode())> -1 ){ if ((code == CLEAR)&& block_compress ){ for (code = 255;code >= 0;code--) tab_prefixof(code)= 0; clear_flg = 1; free_ent = FIRST - 1; if ((code = getcode ())== -1 )/* O, untimely death! */ break ; } incode = code; /* * Special case for KwKwK string. */ if (code >= free_ent ){ *stackp++= finchar; code = oldcode; } /* * Generate output characters in reverse order */ while (code >= 256 ){ *stackp++= tab_suffixof(code); code = tab_prefixof(code); } *stackp++= finchar = tab_suffixof(code); /* * And put them out in forward order */ do putc (*--stackp , outfile); while (stackp > de_stack ); /* * Generate the new entry. */ if ((code=free_ent)< maxmaxcode ){ tab_prefixof(code)= (unsigned short)oldcode; tab_suffixof(code)= finchar; free_ent = code+1; } /* * Remember previous code. */ oldcode = incode; } fflush(outfile); if(ferror(outfile)) { writeerr(); ++fail; } goto cleanup; } /***************************************************************** * TAG( getcode ) * * Read one code from the standard input. If EOF, return -1. * Inputs: * infile * Outputs: * code or -1 is returned. */ code_int getcode(){ /* * On the VAX, it is important to have the register declarations * in exactly the order given, or the asm will break. */ register code_int code; static int offset = 0,size = 0; static char_type buf[BITS]; register int r_off,bits; register char_type *bp = buf; if (clear_flg > 0 || offset >= size || free_ent > maxcode ){ /* * If the next entry will be too big for the current code * size, then we must increase the size. This implies reading * a new buffer full, too. */ if (free_ent > maxcode ){ n_bits++; if (n_bits == maxbits ) maxcode = maxmaxcode;/* won't get any bigger now */ else maxcode = MAXCODE(n_bits); } if (clear_flg > 0){ maxcode = MAXCODE (n_bits = INIT_BITS); clear_flg = 0; } size = fread(buf,1,n_bits,infile); if (size <= 0 ) return -1; /* end of file */ offset = 0; /* Round size down to integral number of codes */ size = (size << 3)- (n_bits - 1); } r_off = offset; bits = n_bits; /* * Get to the first byte. */ bp += (r_off >> 3); r_off &= 7; /* Get first part (low order bits) */ #ifdef NO_UCHAR code = ((*bp++>> r_off)& rmask[8 - r_off])& 0xff; #else code = (*bp++>> r_off); #endif /* NO_UCHAR */ bits -= (8 - r_off); r_off = 8 - r_off; /* now, offset into code word */ /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ if (bits >= 8 ){ #ifdef NO_UCHAR code |= (*bp++& 0xff)<< r_off; #else code |= *bp++<< r_off; #endif /* NO_UCHAR */ r_off += 8; bits -= 8; } /* high order bits. */ code |= (*bp & rmask[bits])<< r_off; offset += n_bits; return code; } 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); } writeerr(){ perror (ofname ); unlink (ofname ); } /* * This routine returns 1 if we are running in the foreground and stderr * is a tty. */ foreground(){ /* I don't know how to test for background, yet. */ return (isatty(2)); } onintr (){ unlink (ofname ); exit (1 ); } oops (){ /* wild pointer -- assume bad input */ if (do_decomp == 1 ) fprintf (stderr,"uncompress: corrupt input\n" ); unlink (ofname ); exit (1 ); } cl_block (){ /* table clear for block compress */ register long int rat; checkpoint = in_count + CHECK_GAP; #ifdef DEBUG if (debug ){ fprintf (stderr,"count: %ld, ratio: ",in_count ); prratio (stderr,in_count,bytes_out ); fprintf (stderr,"\n"); } #endif /* DEBUG */ if(in_count > 0x007fffff){ /* shift will overflow */ rat = bytes_out >> 8; if(rat == 0){ /* Don't divide by zero */ rat = 0x7fffffff; } else { rat = in_count / rat; } } else { rat = (in_count << 8)/ bytes_out;/* 8 fractional bits */ } if (rat > ratio ){ ratio = rat; } else { ratio = 0; #ifdef DEBUG if(verbose) dump_tab(); /* dump string table */ #endif cl_hash ((count_int)hsize ); free_ent = FIRST; clear_flg = 1; output ((code_int)CLEAR ); #ifdef DEBUG if(debug) fprintf (stderr,"clear\n" ); #endif /* DEBUG */ } } cl_hash(hsize) /* reset code table */ register count_int hsize; { register count_int *htab_p = htab+hsize; register long i; register long m1 = -1; i = hsize - 16; do { /* might use Sys V memset(3) here */ *(htab_p-16)= m1; *(htab_p-15)= m1; *(htab_p-14)= m1; *(htab_p-13)= m1; *(htab_p-12)= m1; *(htab_p-11)= m1; *(htab_p-10)= m1; *(htab_p-9)= m1; *(htab_p-8)= m1; *(htab_p-7)= m1; *(htab_p-6)= m1; *(htab_p-5)= m1; *(htab_p-4)= m1; *(htab_p-3)= m1; *(htab_p-2)= m1; *(htab_p-1)= m1; htab_p -= 16; }while ((i -= 16)>= 0); for (i += 16;i > 0;i--) *--htab_p = m1; } prratio(stream,num,den) FILE *stream; long int num,den; { register int q; /* Doesn't need to be long */ 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%%",q / 100,q % 100); }