kmx git

/*
* ========== Copyright Header Begin ==========================================
*
* Hypervisor Software File: comp.c
* 
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
* 
*  - Do no alter or remove copyright notices
* 
*  - Redistribution and use of this software in source and binary forms, with 
*    or without modification, are permitted provided that the following 
*    conditions are met: 
* 
*  - Redistribution of source code must retain the above copyright notice, 
*    this list of conditions and the following disclaimer.
* 
*  - Redistribution in binary form must reproduce the above copyright notice,
*    this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution. 
* 
*    Neither the name of Sun Microsystems, Inc. or the names of contributors 
* may be used to endorse or promote products derived from this software 
* without specific prior written permission. 
* 
*     This software is provided "AS IS," without a warranty of any kind. 
* ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, 
* INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A 
* PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN 
* MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR 
* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR 
* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN 
* OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR 
* FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE 
* DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY, 
* ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF 
* SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
* 
* You acknowledge that this software is not designed, licensed or
* intended for use in the design, construction, operation or maintenance of
* any nuclear facility. 
* 
* ========== Copyright Header End ============================================
*/
/* @(#) comp.c 1.4@(#) */
/*
 * New simplified putcode(), adaptive block compress.
 */

#include <stdio.h>

#define HSIZE	18013		/* 91% occupancy */
#define BITS 14

typedef short		code_int;
typedef	unsigned char	char_type;
typedef long int	count_int;

#define INIT_BITS 9		/* initial number of bits/code */

static count_int	htab[HSIZE];
static unsigned short	codetab[HSIZE];

static char_type magic_header[] = { "\037\236" };	/* 1F 9E */

static int n_bits;			/* number of bits/code */
static int maxbits = BITS;		/* user settable max # bits/code */
static code_int maxcode;		/* maximum code, given n_bits */
static code_int maxmaxcode = 1 << BITS;	/* should NEVER generate this code */
static code_int hsize = HSIZE;		/* for dynamic table sizing */

#define MAXCODE(n_bits)	((1 << (n_bits)) - 1)

static code_int free_ent = 0;		/* first unused entry */

static long int in_count = 1;		/* length of input */
static long int bytes_out;		/* length of compressed output */

#define ROUNDOUT	4		/* XXX round for SPARC alignment */
static long int alloutbytes = 0;	/* num. of output bytes (w. header) */

/*
 * block compression parameters -- after all codes are used up,
 * and compression rate changes, start over.
 */
static long int ratio = 0;
#define CHECK_GAP 10000	/* ratio check interval */
static count_int checkpoint = CHECK_GAP;

/*
 * the next two codes should not be changed lightly, as they must not
 * lie within the contiguous general code space.
 */ 
#define FIRST	258	/* first free entry */
#define END	257	/* End of file marker */
#define	CLEAR	256	/* table clear output code */

static void build_hdr();
static void compress();
static void initout();
static void putcode();
static void endout();
static void cl_block();
static void cl_hash();

#ifndef NOMAIN
/*
 * 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 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.
 */

int
main(argc,argv)
    int argc;
    char **argv;
{
    build_hdr();
    compress();
    return 0;
}
#else

static unsigned char *inbuf;
static unsigned char *outbuf;
static int putcount;
static int getcount;
static int srcsize;

#undef putchar
#undef getchar
#define putchar(x)	outbuf[putcount++] = (unsigned char) (x)
#define getchar()	((getcount < srcsize) ? inbuf[getcount++] : EOF )

int comp( src, size, dest )
    unsigned char *src;
    int size;
    unsigned char *dest;
{
    inbuf	= src;
    srcsize	= size;
    putcount	= 0;
    getcount	= 0;
    outbuf	= dest;

    build_hdr();
    compress();

    return alloutbytes;
}

#endif

static void build_hdr()
{
#ifdef newheader
    putstring("#!lzdecode ");
    putstring("E ");				/* Maxbits */
    putstring(argc < 2 ? "lz.out" : argv[1] );	/* File name */
    putstring("\n");
#else
    ++alloutbytes;
    putchar(magic_header[0]);

    ++alloutbytes;
    putchar(magic_header[1]);

    ++alloutbytes;
    putchar((char)(maxbits));
#endif
}

static void compress() {
    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;

    initout();

    maxcode = MAXCODE(n_bits = INIT_BITS);
    free_ent = FIRST;

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

    ent = getchar ();

    while ( (c = getchar()) != EOF ) {
	in_count++;
	fcode = (long) (((long) c << maxbits) + ent);
 	i = ((c << hshift) ^ ent);	/* xor hashing */

	if ( htab[i] == fcode ) {
	    ent = codetab[i];
	    continue;
	} else if ( (long)htab[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 ( htab[i] == fcode ) {
	    ent = codetab[i];
	    continue;
	}
	if ( (long)htab[i] > 0 ) 
	    goto probe;
nomatch:
	putcode ( (code_int) ent );
	ent = c;
	/*
	 * If the next entry is going to be too big for the code size,
	 * then increase it, if possible.
	 */
	if ( free_ent > maxcode )
	{
	    n_bits++;
	    if ( n_bits == maxbits )
		maxcode = maxmaxcode;
	    else
		maxcode = MAXCODE(n_bits);
	}
	if ( free_ent < maxmaxcode ) {
 	    codetab[i] = free_ent++;	/* code -> hashtable */
	    htab[i] = fcode;
	}
	else if ( (count_int)in_count >= checkpoint)
	    cl_block ();
    }
    /*
     * Put out the final code and the End of File marker.
     */
    putcode( (code_int)ent );
    putcode( (code_int)END );
    endout();

    return;
}

/*****************************************************************
 * TAG( putcode )
 *
 * Output the given code.
 * Inputs:
 * 	code:	A n_bits-bit integer.
 *		Assumes that n_bits =< (long)wordsize - 1.
 * Outputs:
 * 	Outputs code to the file.
 * Assumptions:
 *	Chars are 8 bits long.
 */

static oldcode = 0;
static offset = 0;

static void initout()
{
    offset = 0;
    oldcode = 0;
    ratio = 0;
    in_count = 1;
    bytes_out = 0;		/* Header doesn't count */
    checkpoint = CHECK_GAP;
}

static void putcode( code )
    code_int  code;
{
    register long r_code;
    register int r_off = offset;

    r_code = (code << offset) + oldcode;
    r_off += n_bits;
    do {
	putchar( r_code & 0xff );
	++alloutbytes;
	bytes_out++;
	r_code = r_code >> 8;
	r_off -= 8;
    } while (r_off >= 8);
    oldcode = r_code;
    offset = r_off;
}

static void endout()
{
    if (offset)
    {
	++alloutbytes;
	putchar(oldcode);
    }

    {
	int i;

	i = alloutbytes % ROUNDOUT;
	if (i != 0)
		while (i-- > 0)
		{
			++alloutbytes;
			putchar(0);
		}
    }

    oldcode = 0;
    offset = 0;
}

static void cl_block ()		/* table clear for block compress */
{
    register long int rat;

    checkpoint = in_count + CHECK_GAP;

    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;
 	cl_hash ( (count_int) hsize );
	free_ent = FIRST;
/*	clear_flg = 1;*/
	putcode ( (code_int) CLEAR );
	maxcode = MAXCODE (n_bits = INIT_BITS);
    }
}

static void 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;
}
openbios/openboot/tools/comp.c

Commit

tools/comp.c
