compress.c

操作系统源代码

				if (strcmp(*fileptr + strlen(*fileptr) - 2, DOTZ) == 0) 
				{
			    	fprintf(stderr, "%s: already has .Z suffix -- no change\n",
				    *fileptr);
				    continue;
				}
				/* Open input file */
				if ((freopen(*fileptr, "r", stdin)) == NULL) 
				{
				    perror(*fileptr); continue;
				}
				(void)stat( *fileptr, &statbuf );
				fsize = (long) statbuf.st_size;
				/*
				 * 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; /*lint -e506 -e712 */
				if ( fsize < (1 << 12) )
				    hsize = min ( 5003, HSIZE );
				else if ( fsize < (1 << 13) )
				    hsize = min ( 9001, HSIZE );
				else if ( fsize < (1 << 14) )
				    hsize = min ( 18013, HSIZE );
				else if ( fsize < (1 << 15) )
				    hsize = min ( 35023, HSIZE );
				else if ( fsize < 47000 )
				    hsize = min ( 50021, HSIZE ); /*lint +e506 +e712 */

				/* Generate output filename */
				strcpy(ofname, *fileptr);
#ifndef BSD4_2		/* Short filenames */
				if ((cp=strrchr(ofname,'/')) != NULL)
					cp++;
				else
					cp = ofname;
				if (strlen(cp) > 12) 
				{
				    fprintf(stderr,"%s: filename too long to tack on .Z\n",cp);
				    continue;
				}
#ifdef PCDOS
				else
				{
					/* either tack one on or replace last character */
					char *dot;
					if (NULL == (dot = strchr(cp,'.')))
					{
						strcat(cp,".Z");
					}
					else
					/* if there is a dot then either tack a z on
					   or replace last character */
					{
						if (strlen(dot) < 4)
							strcat(cp,DOTZ);
						else
							dot[3] = 'Z';
					}
				}
#endif
#endif  /* BSD4_2		Long filenames allowed */
#ifndef PCDOS
			/* PCDOS takes care of this above */
				strcat(ofname, DOTZ);
#endif
		    }
		    /* Check for overwrite of existing file */
		    if (overwrite == 0 && zcat_flg == 0) 
			{
				if (stat(ofname, &statbuf) == 0) 
				{
				    char response[2]; int fd;
				    response[0] = 'n';
				    fprintf(stderr, "%s already exists;", ofname);
				    if (foreground()) 
					{
						fd = open("/dev/tty", O_RDONLY);
						fprintf(stderr, 
						" do you wish to overwrite %s (y or n)? ", ofname);
						fflush(stderr);
						(void)read(fd, response, 2);
						while (response[1] != '\n') 
						{
						    if (read(fd, response+1, 1) < 0) 
							{	/* Ack! */
								perror("stderr"); 
								break;
						    }
						}
						close(fd);
				    }
				    if (response[0] != 'y') 
					{
						fprintf(stderr, "\tnot overwritten\n");
						continue;
				    }
				}
		    }
		    if(zcat_flg == 0) 
			{		/* Open output file */
				if (freopen(ofname, "w", stdout) == NULL) 
				{
				    perror(ofname);
				    continue;
				}
				if(!quiet)
					fprintf(stderr, "%s: ", *fileptr);
		    }

		    /* Actually do the compression/decompression */
		    if (do_decomp == 0)	
				compress();
#ifndef DEBUG
		    else			
				decompress();
#else
		    else if (debug == 0)	
				decompress();
		    else			
				printcodes();
		    if (verbose)		
				dump_tab();
#endif /* DEBUG */
		    if(zcat_flg == 0) 
			{
				copystat(*fileptr, ofname);	/* Copy stats */
				if((exit_stat == 1) || (!quiet))
					putc('\n', stderr);
		    }
		}
    } else 
	{		/* Standard input */
		if (do_decomp == 0) 
		{
			compress();
#ifdef DEBUG
			if(verbose)		dump_tab();
#endif /* DEBUG */
			if(!quiet)
				putc('\n', stderr);
		} else 
		{
		    /* Check the magic number */
		    if (nomagic == 0) 
			{
				if ((getc(stdin)!=(magic_header[0] & 0xFF))
				 || (getc(stdin)!=(magic_header[1] & 0xFF))) 
				{
				    fprintf(stderr, "stdin: not in compressed format\n");
				    exit(1);
				}
				maxbits = getc(stdin);	/* set -b from file */
				block_compress = maxbits & BLOCK_MASK;
				maxbits &= BIT_MASK;
				maxmaxcode = 1 << maxbits;
				fsize = 100000;		/* assume stdin large for USERMEM */
				if(maxbits > BITS) 
				{
					fprintf(stderr,
					"stdin: compressed with %d bits, can only handle %d bits\n",
					maxbits, BITS);
					exit(1);
				}
		    }
#ifndef DEBUG
		    decompress();
#else
		    if (debug == 0)	decompress();
		    else		printcodes();
		    if (verbose)	dump_tab();
#endif /* DEBUG */
		}
    }
    return(exit_stat);
}

static int offset;
long int in_count = 1;			/* length of input */
long int bytes_out;			/* length of compressed output */
long int out_count = 0;			/* # of codes output (for debugging) */

/*
 * compress stdin to stdout
 *
 * 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.
 */

void compress() 
{
    REGISTER long fcode;
    REGISTER code_int i = 0;
    REGISTER int c;
    REGISTER code_int ent;
#ifdef XENIX_16
    REGISTER code_int disp;
#else	/* Normal machine */
    REGISTER int disp;
#endif
    REGISTER code_int hsize_reg;
    REGISTER int hshift;

#ifndef COMPATIBLE
    if (nomagic == 0) 
	{
		putc(magic_header[0],stdout); 
		putc(magic_header[1],stdout);
		putc((char)(maxbits | block_compress),stdout);
		if(ferror(stdout))
			writeerr();
    }
#endif /* COMPATIBLE */

    offset = 0;
    bytes_out = 3;		/* includes 3-byte header mojo */
    out_count = 0;
    clear_flg = 0;
    ratio = 0;
    in_count = 1;
    checkpoint = CHECK_GAP;
    maxcode = MAXCODE(n_bits = INIT_BITS);
    free_ent = ((block_compress) ? FIRST : 256 );

    ent = getc(stdin);

    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 */

#ifdef SIGNED_COMPARE_SLOW
    while ( (c = getc(stdin)) != (unsigned) EOF )
#else
    while ( (c = getc(stdin)) != EOF )
#endif
	{
		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;
#ifdef SIGNED_COMPARE_SLOW
		if ( (unsigned) free_ent < (unsigned) maxmaxcode)
#else
		if ( free_ent < maxmaxcode )
#endif
		{
	 	    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;
    return;
}

/*****************************************************************
 * 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];

#ifndef vax
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};
#endif /* vax */
void output( code )
code_int  code;
{
#ifdef DEBUG
    static int col = 0;
#endif /* DEBUG */

    /*
     * On the VAX, it is important to have the REGISTER declarations
     * in exactly the order given, or the asm will break.
     */
    REGISTER int r_off = offset, bits= n_bits;
    REGISTER char * bp = buf;
#ifndef BREAKHIGHC
#ifdef METAWARE
	int temp;
#endif
#endif
#ifdef DEBUG
	if ( verbose )
	    fprintf( stderr, "%5d%c", code,
		    (col+=6) >= 74 ? (col = 0, '\n') : ' ' );
#endif /* DEBUG */
    if ( code >= 0 ) 
	{
#ifdef vax
	/* VAX DEPENDENT!! Implementation on other machines is below.
	 *
	 * Translation: Insert BITS bits from the argument starting at
	 * offset bits from the beginning of buf.
	 */
	0;	/* Work around for pcc -O bug with asm and if stmt */
	asm( "insv	4(ap),r11,r10,(r9)" );
#else /* not a vax */
/* 
 * 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.
	 */
#ifndef BREAKHIGHC
#ifdef METAWARE
	*bp &= rmask[r_off];
	temp = (code << r_off) & lmask[r_off];
	*bp |= temp;
#else
	*bp = (*bp & rmask[r_off]) | ((code << r_off) & lmask[r_off]);
#endif
#else
	*bp = (*bp & rmask[r_off]) | ((code << r_off) & lmask[r_off]);
#endif
	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;
#endif /* vax */
	offset += n_bits;
	if ( offset == (n_bits << 3) ) 
	{
	    bp = buf;
	    bits = n_bits;
	    bytes_out += bits;
	    do
		putc(*bp++,stdout);
	    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, (size_t)1, (size_t)n_bits, stdout ) != n_bits)
				writeerr();
			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, (size_t)1, (size_t)(offset + 7) / 8, stdout );
	bytes_out += (offset + 7) / 8;
	offset = 0;
	fflush( stdout );
#ifdef DEBUG
	if ( verbose )
	    fprintf( stderr, "\n" );
#endif /* DEBUG */
	if( ferror( stdout ) )
		writeerr();
    }
}
/*
 * Decompress stdin to stdout.  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.
 */

void decompress() {
    REGISTER char_type *stackp;
    REGISTER int finchar;
    REGISTER code_int code, oldcode, incode;

    /*
     * 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 */
    putc( (char)finchar,stdout );		/* first code must be 8 bits = char */
    if(ferror(stdout))		/* Crash if can't write */
	writeerr();
    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
	 */
#ifdef SIGNED_COMPARE_SLOW