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

/*
* ========== Copyright Header Begin ==========================================
*
* Hypervisor Software File: decomp.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 ============================================
*/
#ifndef STANDALONE
#include <stdio.h>
#endif /* STANDALONE */

/*
 * @(#)decomp.c 1.6 03/04/01
 * Copyright 2000, 2003 Sun Microsystems, Inc.  All Rights Reserved
 * Use is subject to license terms.
 * New simplified getcode() routine, adaptive block compress.
 */

/* marker for needed scope management of symbols in this file */
#define	PRIVATE

typedef unsigned char uchar_t;

#define	HSIZE		18013		/* 91% occupancy */
#define	BITS		14
#define	INIT_BITS	9		/* initial number of bits/code */

/*
 * Character output.
 */
PRIVATE unsigned char	*output;
PRIVATE unsigned char	*input;
PRIVATE int		data_count;

#ifdef STANDALONE
#define	putbyte(c)	*output++ = (c)
#else
#define	putbyte(c)	putchar((c))
#endif /* STANDALONE */
PRIVATE int getbyte();

#define	init_output(op)		output = (op)

#define	init_input(ip, size)	input = (ip), data_count = (size)
/*
 * Start of Uninitialized globals
 */
typedef short		code_int;
typedef	unsigned char	char_type;
typedef int		count_int;

PRIVATE char_type		tab_suffix[HSIZE];
PRIVATE unsigned short		tab_prefix[HSIZE];
PRIVATE char_type		de_stack[8000];

/*
 * End of uninitialized globals
 */

PRIVATE code_int		getcode();

#define	maxmaxcode ((code_int)1 << BITS) /* should NEVER generate this code */
#define	MAXCODE(n_bits)	((1 << (n_bits)) - 1)

/*
 * block compression parameters -- after all codes are used up,
 * and compression rate changes, start over.
 * These codes should not be changed lightly, as they must not
 * lie within the contiguous general code space.
 * The END marker is used because some file transfer programs are
 * prone to adding garbage bytes to the end of the file.
 */
#define	FIRST	258	/* first free entry */
#define	END	257	/* End of file marker */
#define	CLEAR	256	/* table clear output code */

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

/*
 * Don't initialize these explicitly because we want them in the
 * BSS segment for ROM/RAM systems.  It would probably be a good
 * idea to initialize them to 0 at run time (when decompress()
 * begins).
 */
static int	getcode_offset;
static int	getcode_oldcode;

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

PRIVATE void
decompress(ip, insize, op)
    unsigned char *ip;
    int insize;
    unsigned char *op;
{
	register char_type	*stackp;
	register int		finchar;
	register code_int	code,
				oldcode,
				incode;
	register int		n_bits;		/* number of bits/code */
	code_int		maxcode;	/* max code, given n_bits */
	code_int		free_ent;	/* first unused entry */

	getcode_offset = 0;
	getcode_oldcode = 0;

	init_input(ip, insize);
	init_output(op);
	/* Check the magic number */
	if ((getbyte() != (magic_header[0] & 0xFF)) ||
	    (getbyte() != (magic_header[1] & 0xFF))) {

#if defined(DEBUG) && ! defined(STANDALONE)
		fprintf(stderr, "Bad MAGIC number\n");
		exit(1);
#endif /* DEBUG */
		*(short *)1 = 1;
	}
	if (getbyte() != BITS) {
#if defined(DEBUG) && ! defined(STANDALONE)
		fprintf(stderr, "Bad #bits\n");
#endif /* DEBUG */
		*(short *)1 = 2;
	}
	/*
	 * As above, initialize the first 256 entries in the table.
	 */
	maxcode = MAXCODE(n_bits = INIT_BITS);

	for (code = 255; code >= 0; code--) {
		tab_prefix[code] = 0;
		tab_suffix[code] = (char_type)code;
	}

	free_ent = FIRST;

	finchar = oldcode = getcode(n_bits);
	if (oldcode == -1 || oldcode == END)	/* EOF already? */
		*(short *)1 = 3;
	putbyte((char)finchar);	/* first code must be 8 bits = char */
	stackp = de_stack;

	while ((code = getcode(n_bits)) > (code_int)-1 && code != END) {

		if (code == CLEAR) {
			for (code = 255; code >= 0; code--)
				tab_prefix[code] = 0;
			maxcode = MAXCODE(n_bits = INIT_BITS);
			free_ent = FIRST - 1;
			if ((code = getcode(n_bits)) == -1)  /* EOF */
				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_suffix[code];
			code = tab_prefix[code];
		}
		*stackp++ = finchar = tab_suffix[code];

		/*
		 * And put them out in forward order
		 */
		do
			putbyte(*--stackp);
		while (stackp > de_stack);

		/*
		 * Generate the new entry.
		 */
		if ((code = free_ent) < (code_int)maxmaxcode) {
			tab_prefix[code] = (unsigned short)oldcode;
			tab_suffix[code] = finchar;
			free_ent = code+1;
		}

		/*
		 * Remember previous code.
		 */
		oldcode = incode;

		/*
		 * If the next entry will be too big for the current code
		 * size, then we must increase the size.
		 */
		if (free_ent > maxcode) {
			n_bits++;
			if (n_bits == BITS)
				/* won't get any bigger now */
				maxcode = maxmaxcode;
			else
				maxcode = MAXCODE(n_bits);
		}
	}
}

/*
 * getcode
 * Read one code from the standard input.  If EOF, return -1.
 */

PRIVATE code_int rmask[] = {
	0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f,
	0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff,
	0x3fff, 0x7fff, (code_int)0xffff
};

PRIVATE code_int
getcode(bits)
	register int	bits;
{
	register int	r_off = getcode_offset;
	register int	code = getcode_oldcode;
	register int	c;

	do {
		if ((c = getbyte()) == -1)
			return (-1);
		code += c << r_off;
		r_off += 8;
	} while (r_off < bits);

	getcode_oldcode = code >> bits;
	getcode_offset = r_off - bits;
#if defined(DEBUG) && ! defined(STANDALONE)
	fprintf(stderr, "[%x]\n", code & rmask[bits]);
#endif /* DEBUG */
	return (code & rmask[bits]);
}

PRIVATE int
getbyte()
{
#ifndef STANDALONE
	int c;
	c = getchar();
#ifdef DEBUG
	fprintf(stderr, "%2x ", c);
#endif /* DEBUG */
	if (c == EOF) c = -1;
	return (c);
#else
	if (--data_count < 0)
		return (-1);
	return ((int)*input++);
#endif /* STANDALONE */
}

#ifndef STANDALONE
main(void)
{
	decompress(0, 0, 0);
	return (0);
}
#endif /* STANDALONE */

#ifdef DROPIN_LIB
int
decomp(uchar_t *src, int size, uchar_t *dest)
{
	decompress(src, size, dest);
	return (output - dest);
}
#endif /* DROPIN_LIB */
Commit	Line	Data
920dae64 AT	1	/*
	2	* ========== Copyright Header Begin ==========================================
	3	*
	4	* Hypervisor Software File: decomp.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	#ifndef STANDALONE
	45	#include <stdio.h>
	46	#endif /* STANDALONE */
	47
	48	/*
	49	* @(#)decomp.c 1.6 03/04/01
	50	* Copyright 2000, 2003 Sun Microsystems, Inc. All Rights Reserved
	51	* Use is subject to license terms.
	52	* New simplified getcode() routine, adaptive block compress.
	53	*/
	54
	55	/* marker for needed scope management of symbols in this file */
	56	#define PRIVATE
	57
	58	typedef unsigned char uchar_t;
	59
	60	#define HSIZE 18013 /* 91% occupancy */
	61	#define BITS 14
	62	#define INIT_BITS 9 /* initial number of bits/code */
	63
	64	/*
65	* Character output.
66	*/
67	PRIVATE unsigned char *output;
68	PRIVATE unsigned char *input;
69	PRIVATE int data_count;
70
71	#ifdef STANDALONE
72	#define putbyte(c) *output++ = (c)
73	#else
74	#define putbyte(c) putchar((c))
75	#endif /* STANDALONE */
76	PRIVATE int getbyte();
77
78	#define init_output(op) output = (op)
79
80	#define init_input(ip, size) input = (ip), data_count = (size)
81	/*
82	* Start of Uninitialized globals
83	*/
84	typedef short code_int;
85	typedef unsigned char char_type;
86	typedef int count_int;
87
88	PRIVATE char_type tab_suffix[HSIZE];
89	PRIVATE unsigned short tab_prefix[HSIZE];
90	PRIVATE char_type de_stack[8000];
91
92	/*
93	* End of uninitialized globals
94	*/
95
96	PRIVATE code_int getcode();
97
98	#define maxmaxcode ((code_int)1 << BITS) /* should NEVER generate this code */
99	#define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
100
101	/*
102	* block compression parameters -- after all codes are used up,
103	* and compression rate changes, start over.
104	* These codes should not be changed lightly, as they must not
105	* lie within the contiguous general code space.
106	* The END marker is used because some file transfer programs are
107	* prone to adding garbage bytes to the end of the file.
108	*/
109	#define FIRST 258 /* first free entry */
110	#define END 257 /* End of file marker */
111	#define CLEAR 256 /* table clear output code */
112
113	static char_type magic_header[] = { "\037\236" }; /* 1F 9E */
114
115	/*
116	* Don't initialize these explicitly because we want them in the
117	* BSS segment for ROM/RAM systems. It would probably be a good
118	* idea to initialize them to 0 at run time (when decompress()
119	* begins).
120	*/
121	static int getcode_offset;
122	static int getcode_oldcode;
123
124	/*
125	* Decompress stdin to stdout. This routine adapts to the codes in the
126	* file building the "string" table on-the-fly; requiring no table to
127	* be stored in the compressed file. The tables used herein are shared
128	* with those of the compress() routine. See the definitions above.
129	*/
130
131	PRIVATE void
132	decompress(ip, insize, op)
133	unsigned char *ip;
134	int insize;
135	unsigned char *op;
136	{
137	register char_type *stackp;
138	register int finchar;
139	register code_int code,
140	oldcode,
141	incode;
142	register int n_bits; /* number of bits/code */
143	code_int maxcode; /* max code, given n_bits */
144	code_int free_ent; /* first unused entry */
145
146	getcode_offset = 0;
147	getcode_oldcode = 0;
148
149	init_input(ip, insize);
150	init_output(op);
151	/* Check the magic number */
152	if ((getbyte() != (magic_header[0] & 0xFF)) \|\|
153	(getbyte() != (magic_header[1] & 0xFF))) {
154
155	#if defined(DEBUG) && ! defined(STANDALONE)
156	fprintf(stderr, "Bad MAGIC number\n");
157	exit(1);
158	#endif /* DEBUG */
159	(short )1 = 1;
160	}
161	if (getbyte() != BITS) {
162	#if defined(DEBUG) && ! defined(STANDALONE)
163	fprintf(stderr, "Bad #bits\n");
164	#endif /* DEBUG */
165	(short )1 = 2;
166	}
167	/*
168	* As above, initialize the first 256 entries in the table.
169	*/
170	maxcode = MAXCODE(n_bits = INIT_BITS);
171
172	for (code = 255; code >= 0; code--) {
173	tab_prefix[code] = 0;
174	tab_suffix[code] = (char_type)code;
175	}
176
177	free_ent = FIRST;
178
179	finchar = oldcode = getcode(n_bits);
180	if (oldcode == -1 \|\| oldcode == END) /* EOF already? */
181	(short )1 = 3;
182	putbyte((char)finchar); /* first code must be 8 bits = char */
183	stackp = de_stack;
184
185	while ((code = getcode(n_bits)) > (code_int)-1 && code != END) {
186
187	if (code == CLEAR) {
188	for (code = 255; code >= 0; code--)
189	tab_prefix[code] = 0;
190	maxcode = MAXCODE(n_bits = INIT_BITS);
191	free_ent = FIRST - 1;
192	if ((code = getcode(n_bits)) == -1) /* EOF */
193	break;
194	}
195	incode = code;
196
197	/*
198	* Special case for KwKwK string.
199	*/
200	if (code >= free_ent) {
201	*stackp++ = finchar;
202	code = oldcode;
203	}
204
205	/*
206	* Generate output characters in reverse order
207	*/
208	while (code >= 256) {
209	*stackp++ = tab_suffix[code];
210	code = tab_prefix[code];
211	}
212	*stackp++ = finchar = tab_suffix[code];
213
214	/*
215	* And put them out in forward order
216	*/
217	do
218	putbyte(*--stackp);
219	while (stackp > de_stack);
220
221	/*
222	* Generate the new entry.
223	*/
224	if ((code = free_ent) < (code_int)maxmaxcode) {
225	tab_prefix[code] = (unsigned short)oldcode;
226	tab_suffix[code] = finchar;
227	free_ent = code+1;
228	}
229
230	/*
231	* Remember previous code.
232	*/
233	oldcode = incode;
234
235	/*
236	* If the next entry will be too big for the current code
237	* size, then we must increase the size.
238	*/
239	if (free_ent > maxcode) {
240	n_bits++;
241	if (n_bits == BITS)
242	/* won't get any bigger now */
243	maxcode = maxmaxcode;
244	else
245	maxcode = MAXCODE(n_bits);
246	}
247	}
248	}
249
250	/*
251	* getcode
252	* Read one code from the standard input. If EOF, return -1.
253	*/
254
255	PRIVATE code_int rmask[] = {
256	0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f,
257	0x007f, 0x00ff, 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff,
258	0x3fff, 0x7fff, (code_int)0xffff
259	};
260
261	PRIVATE code_int
262	getcode(bits)
263	register int bits;
264	{
265	register int r_off = getcode_offset;
266	register int code = getcode_oldcode;
267	register int c;
268
269	do {
270	if ((c = getbyte()) == -1)
271	return (-1);
272	code += c << r_off;
273	r_off += 8;
274	} while (r_off < bits);
275
276	getcode_oldcode = code >> bits;
277	getcode_offset = r_off - bits;
278	#if defined(DEBUG) && ! defined(STANDALONE)
279	fprintf(stderr, "[%x]\n", code & rmask[bits]);
280	#endif /* DEBUG */
281	return (code & rmask[bits]);
282	}
283
284	PRIVATE int
285	getbyte()
286	{
287	#ifndef STANDALONE
288	int c;
289	c = getchar();
290	#ifdef DEBUG
291	fprintf(stderr, "%2x ", c);
292	#endif /* DEBUG */
293	if (c == EOF) c = -1;
294	return (c);
295	#else
296	if (--data_count < 0)
297	return (-1);
298	return ((int)*input++);
299	#endif /* STANDALONE */
300	}
301
302	#ifndef STANDALONE
303	main(void)
304	{
305	decompress(0, 0, 0);
306	return (0);
307	}
308	#endif /* STANDALONE */
309
310	#ifdef DROPIN_LIB
311	int
312	decomp(uchar_t src, int size, uchar_t dest)
313	{
314	decompress(src, size, dest);
315	return (output - dest);
316	}
317	#endif /* DROPIN_LIB */