[OpenSPARC-T2-SAM] / obp / tools / comp.c

/*
* ========== 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;
}
Commit	Line	Data
920dae64 AT	1	/*
	2	* ========== Copyright Header Begin ==========================================
	3	*
	4	* Hypervisor Software File: comp.c
	5	*
	6	* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
	7	*
	8	* - Do no alter or remove copyright notices
	9	*
	10	* - Redistribution and use of this software in source and binary forms, with
	11	* or without modification, are permitted provided that the following
	12	* conditions are met:
	13	*
	14	* - Redistribution of source code must retain the above copyright notice,
	15	* this list of conditions and the following disclaimer.
	16	*
	17	* - Redistribution in binary form must reproduce the above copyright notice,
	18	* this list of conditions and the following disclaimer in the
	19	* documentation and/or other materials provided with the distribution.
	20	*
	21	* Neither the name of Sun Microsystems, Inc. or the names of contributors
	22	* may be used to endorse or promote products derived from this software
	23	* without specific prior written permission.
	24	*
	25	* This software is provided "AS IS," without a warranty of any kind.
	26	* ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
	27	* INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
	28	* PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN
	29	* MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL NOT BE LIABLE FOR
	30	* ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
	31	* DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES. IN NO EVENT WILL SUN
	32	* OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE, PROFIT OR DATA, OR
	33	* FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL, INCIDENTAL OR PUNITIVE
	34	* DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY OF LIABILITY,
	35	* ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE, EVEN IF
	36	* SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
	37	*
	38	* You acknowledge that this software is not designed, licensed or
	39	* intended for use in the design, construction, operation or maintenance of
	40	* any nuclear facility.
	41	*
	42	* ========== Copyright Header End ============================================
	43	*/
	44	/* @(#) comp.c 1.4@(#) */
	45	/*
	46	* New simplified putcode(), adaptive block compress.
	47	*/
	48
	49	#include <stdio.h>
	50
	51	#define HSIZE 18013 /* 91% occupancy */
	52	#define BITS 14
	53
	54	typedef short code_int;
	55	typedef unsigned char char_type;
	56	typedef long int count_int;
	57
	58	#define INIT_BITS 9 /* initial number of bits/code */
	59
	60	static count_int htab[HSIZE];
	61	static unsigned short codetab[HSIZE];
	62
	63	static char_type magic_header[] = { "\037\236" }; /* 1F 9E */
	64
65	static int n_bits; /* number of bits/code */
66	static int maxbits = BITS; /* user settable max # bits/code */
67	static code_int maxcode; /* maximum code, given n_bits */
68	static code_int maxmaxcode = 1 << BITS; /* should NEVER generate this code */
69	static code_int hsize = HSIZE; /* for dynamic table sizing */
70
71	#define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
72
73	static code_int free_ent = 0; /* first unused entry */
74
75	static long int in_count = 1; /* length of input */
76	static long int bytes_out; /* length of compressed output */
77
78	#define ROUNDOUT 4 /* XXX round for SPARC alignment */
79	static long int alloutbytes = 0; /* num. of output bytes (w. header) */
80
81	/*
82	* block compression parameters -- after all codes are used up,
83	* and compression rate changes, start over.
84	*/
85	static long int ratio = 0;
86	#define CHECK_GAP 10000 /* ratio check interval */
87	static count_int checkpoint = CHECK_GAP;
88
89	/*
90	* the next two codes should not be changed lightly, as they must not
91	* lie within the contiguous general code space.
92	*/
93	#define FIRST 258 /* first free entry */
94	#define END 257 /* End of file marker */
95	#define CLEAR 256 /* table clear output code */
96
97	static void build_hdr();
98	static void compress();
99	static void initout();
100	static void putcode();
101	static void endout();
102	static void cl_block();
103	static void cl_hash();
104
105	#ifndef NOMAIN
106	/*
107	* compress stdin to stdout
108	*
109	* Algorithm: use open addressing double hashing (no chaining) on the
110	* prefix code / next character combination. We do a variant of Knuth's
111	* algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
112	* secondary probe. Here, the modular division first probe gives way
113	* to a faster exclusive-or manipulation. Also do block compression with
114	* an adaptive reset, whereby the code table is cleared when the compression
115	* ratio decreases, but after the table fills. The variable-length output
116	* codes are re-sized at this point, and a special CLEAR code is generated
117	* for the decompressor.
118	*/
119
120	int
121	main(argc,argv)
122	int argc;
123	char **argv;
124	{
125	build_hdr();
126	compress();
127	return 0;
128	}
129	#else
130
131	static unsigned char *inbuf;
132	static unsigned char *outbuf;
133	static int putcount;
134	static int getcount;
135	static int srcsize;
136
137	#undef putchar
138	#undef getchar
139	#define putchar(x) outbuf[putcount++] = (unsigned char) (x)
140	#define getchar() ((getcount < srcsize) ? inbuf[getcount++] : EOF )
141
142	int comp( src, size, dest )
143	unsigned char *src;
144	int size;
145	unsigned char *dest;
146	{
147	inbuf = src;
148	srcsize = size;
149	putcount = 0;
150	getcount = 0;
151	outbuf = dest;
152
153	build_hdr();
154	compress();
155
156	return alloutbytes;
157	}
158
159	#endif
160
161	static void build_hdr()
162	{
163	#ifdef newheader
164	putstring("#!lzdecode ");
165	putstring("E "); /* Maxbits */
166	putstring(argc < 2 ? "lz.out" : argv[1] ); /* File name */
167	putstring("\n");
168	#else
169	++alloutbytes;
170	putchar(magic_header[0]);
171
172	++alloutbytes;
173	putchar(magic_header[1]);
174
175	++alloutbytes;
176	putchar((char)(maxbits));
177	#endif
178	}
179
180	static void compress() {
181	register long fcode;
182	register code_int i = 0;
183	register int c;
184	register code_int ent;
185	register int disp;
186	register code_int hsize_reg;
187	register int hshift;
188
189	initout();
190
191	maxcode = MAXCODE(n_bits = INIT_BITS);
192	free_ent = FIRST;
193
194	hshift = 0;
195	for ( fcode = (long) hsize; fcode < 65536L; fcode *= 2L )
196	hshift++;
197	hshift = 8 - hshift; /* set hash code range bound */
198
199	hsize_reg = hsize;
200	cl_hash( (count_int) hsize_reg); /* clear hash table */
201
202	ent = getchar ();
203
204	while ( (c = getchar()) != EOF ) {
205	in_count++;
206	fcode = (long) (((long) c << maxbits) + ent);
207	i = ((c << hshift) ^ ent); /* xor hashing */
208
209	if ( htab[i] == fcode ) {
210	ent = codetab[i];
211	continue;
212	} else if ( (long)htab[i] < 0 ) /* empty slot */
213	goto nomatch;
214	disp = hsize_reg - i; /* secondary hash (after G. Knott) */
215	if ( i == 0 )
216	disp = 1;
217	probe:
218	if ( (i -= disp) < 0 )
219	i += hsize_reg;
220
221	if ( htab[i] == fcode ) {
222	ent = codetab[i];
223	continue;
224	}
225	if ( (long)htab[i] > 0 )
226	goto probe;
227	nomatch:
228	putcode ( (code_int) ent );
229	ent = c;
230	/*
231	* If the next entry is going to be too big for the code size,
232	* then increase it, if possible.
233	*/
234	if ( free_ent > maxcode )
235	{
236	n_bits++;
237	if ( n_bits == maxbits )
238	maxcode = maxmaxcode;
239	else
240	maxcode = MAXCODE(n_bits);
241	}
242	if ( free_ent < maxmaxcode ) {
243	codetab[i] = free_ent++; /* code -> hashtable */
244	htab[i] = fcode;
245	}
246	else if ( (count_int)in_count >= checkpoint)
247	cl_block ();
248	}
249	/*
250	* Put out the final code and the End of File marker.
251	*/
252	putcode( (code_int)ent );
253	putcode( (code_int)END );
254	endout();
255
256	return;
257	}
258
259	/*****************************************************************
260	* TAG( putcode )
261	*
262	* Output the given code.
263	* Inputs:
264	* code: A n_bits-bit integer.
265	* Assumes that n_bits =< (long)wordsize - 1.
266	* Outputs:
267	* Outputs code to the file.
268	* Assumptions:
269	* Chars are 8 bits long.
270	*/
271
272	static oldcode = 0;
273	static offset = 0;
274
275	static void initout()
276	{
277	offset = 0;
278	oldcode = 0;
279	ratio = 0;
280	in_count = 1;
281	bytes_out = 0; /* Header doesn't count */
282	checkpoint = CHECK_GAP;
283	}
284
285	static void putcode( code )
286	code_int code;
287	{
288	register long r_code;
289	register int r_off = offset;
290
291	r_code = (code << offset) + oldcode;
292	r_off += n_bits;
293	do {
294	putchar( r_code & 0xff );
295	++alloutbytes;
296	bytes_out++;
297	r_code = r_code >> 8;
298	r_off -= 8;
299	} while (r_off >= 8);
300	oldcode = r_code;
301	offset = r_off;
302	}
303
304	static void endout()
305	{
306	if (offset)
307	{
308	++alloutbytes;
309	putchar(oldcode);
310	}
311
312	{
313	int i;
314
315	i = alloutbytes % ROUNDOUT;
316	if (i != 0)
317	while (i-- > 0)
318	{
319	++alloutbytes;
320	putchar(0);
321	}
322	}
323
324	oldcode = 0;
325	offset = 0;
326	}
327
328	static void cl_block () /* table clear for block compress */
329	{
330	register long int rat;
331
332	checkpoint = in_count + CHECK_GAP;
333
334	if(in_count > 0x007fffff) { /* shift will overflow */
335	rat = bytes_out >> 8;
336	if(rat == 0) { /* Don't divide by zero */
337	rat = 0x7fffffff;
338	} else {
339	rat = in_count / rat;
340	}
341	} else {
342	rat = (in_count << 8) / bytes_out; /* 8 fractional bits */
343	}
344	if ( rat > ratio ) {
345	ratio = rat;
346	} else {
347	ratio = 0;
348	cl_hash ( (count_int) hsize );
349	free_ent = FIRST;
350	/* clear_flg = 1;*/
351	putcode ( (code_int) CLEAR );
352	maxcode = MAXCODE (n_bits = INIT_BITS);
353	}
354	}
355
356	static void cl_hash(hsize) /* reset code table */
357	register count_int hsize;
358	{
359	register count_int *htab_p = htab+hsize;
360	register long i;
361	register long m1 = -1;
362
363	i = hsize - 16;
364	do { /* might use Sys V memset(3) here */
365	*(htab_p-16) = m1;
366	*(htab_p-15) = m1;
367	*(htab_p-14) = m1;
368	*(htab_p-13) = m1;
369	*(htab_p-12) = m1;
370	*(htab_p-11) = m1;
371	*(htab_p-10) = m1;
372	*(htab_p-9) = m1;
373	*(htab_p-8) = m1;
374	*(htab_p-7) = m1;
375	*(htab_p-6) = m1;
376	*(htab_p-5) = m1;
377	*(htab_p-4) = m1;
378	*(htab_p-3) = m1;
379	*(htab_p-2) = m1;
380	*(htab_p-1) = m1;
381	htab_p -= 16;
382	} while ((i -= 16) >= 0);
383
384	for ( i += 16; i > 0; i-- )
385	*--htab_p = m1;
386	}
387
388