decompress.c revision 94917da6 
1/* $Xorg: decompress.c,v 1.4 2001/02/09 02:04:03 xorgcvs Exp $ */
2/*
3 * Copyright 1985, 1986 The Regents of the University of California.
4 * All rights reserved.
5 *
6 * This code is derived from software contributed to Berkeley by
7 * James A. Woods, derived from original work by Spencer Thomas
8 * and Joseph Orost.
9 *
10 * Redistribution and use in source and binary forms are permitted
11 * provided that the above copyright notice and this paragraph are
12 * duplicated in all such forms and that any documentation,
13 * advertising materials, and other materials related to such
14 * distribution and use acknowledge that the software was developed
15 * by the University of California, Berkeley.  The name of the
16 * University may not be used to endorse or promote products derived
17 * from this software without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
20 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
21 */
22
23/*
24
25Copyright 1993, 1998  The Open Group
26
27Permission to use, copy, modify, distribute, and sell this software and its
28documentation for any purpose is hereby granted without fee, provided that
29the above copyright notice appear in all copies and that both that
30copyright notice and this permission notice appear in supporting
31documentation.
32
33The above copyright notice and this permission notice shall be included in
34all copies or substantial portions of the Software.
35
36THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
37IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
38FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
39OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
40AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
41CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
42
43Except as contained in this notice, the name of The Open Group shall not be
44used in advertising or otherwise to promote the sale, use or other dealings
45in this Software without prior written authorization from The Open Group.
46
47*/
48/* $XFree86: xc/lib/font/fontfile/decompress.c,v 1.4 2001/01/17 19:43:29 dawes Exp $ */
49/*
50 * decompress - cat a compressed file
51 */
52
53#ifdef HAVE_CONFIG_H
54#include <config.h>
55#endif
56#include <X11/fonts/fontmisc.h>
57#include <X11/fonts/bufio.h>
58
59#define BITS	16
60
61/*
62 * a code_int must be able to hold 2**BITS values of type int, and also -1
63 */
64#if BITS > 15
65typedef long int	code_int;
66#else
67typedef int		code_int;
68#endif
69
70typedef long int	  count_int;
71
72#ifdef NO_UCHAR
73 typedef char	char_type;
74#else
75 typedef	unsigned char	char_type;
76#endif /* UCHAR */
77
78static char_type magic_header[] = { "\037\235" };	/* 1F 9D */
79
80/* Defines for third byte of header */
81#define BIT_MASK	0x1f
82#define BLOCK_MASK	0x80
83/* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
84   a fourth header byte (for expansion).
85*/
86
87#define INIT_BITS 9			/* initial number of bits/code */
88
89#ifdef COMPATIBLE		/* But wrong! */
90# define MAXCODE(n_bits)	(1 << (n_bits) - 1)
91#else
92# define MAXCODE(n_bits)	((1 << (n_bits)) - 1)
93#endif /* COMPATIBLE */
94
95/*
96 * the next two codes should not be changed lightly, as they must not
97 * lie within the contiguous general code space.
98 */
99#define FIRST	257	/* first free entry */
100#define	CLEAR	256	/* table clear output code */
101
102#define STACK_SIZE  65300
103
104typedef struct _compressedFILE {
105    BufFilePtr	    file;
106
107    char_type	    *stackp;
108    code_int	    oldcode;
109    char_type	    finchar;
110
111    int		block_compress;
112    int		maxbits;
113    code_int	maxcode, maxmaxcode;
114
115    code_int	free_ent;
116    int		clear_flg;
117    int		n_bits;
118
119    /* bit buffer */
120    int		offset, size;
121    char_type	buf[BITS];
122
123    char_type	    de_stack[STACK_SIZE];
124    char_type	    *tab_suffix;
125    unsigned short  *tab_prefix;
126} CompressedFile;
127
128
129static int hsize_table[] = {
130    5003,	/* 12 bits - 80% occupancy */
131    9001,	/* 13 bits - 91% occupancy */
132    18013,	/* 14 bits - 91% occupancy */
133    35023,	/* 15 bits - 94% occupancy */
134    69001	/* 16 bits - 95% occupancy */
135};
136
137static int BufCompressedClose ( BufFilePtr f, int doClose );
138static int BufCompressedFill ( BufFilePtr f );
139static code_int getcode ( CompressedFile *file );
140static int BufCompressedSkip ( BufFilePtr f, int bytes );
141
142BufFilePtr
143BufFilePushCompressed (BufFilePtr f)
144{
145    int		    code;
146    int		    maxbits;
147    int		    hsize;
148    CompressedFile  *file;
149    int		    extra;
150
151    if ((BufFileGet(f) != (magic_header[0] & 0xFF)) ||
152	(BufFileGet(f) != (magic_header[1] & 0xFF)))
153    {
154	return 0;
155    }
156    code = BufFileGet (f);
157    if (code == BUFFILEEOF) return 0;
158
159    maxbits = code & BIT_MASK;
160    if (maxbits > BITS || maxbits < 12)
161	return 0;
162    hsize = hsize_table[maxbits - 12];
163    extra = (1 << maxbits) * sizeof (char_type) +
164	    hsize * sizeof (unsigned short);
165    file = malloc (sizeof (CompressedFile) + extra);
166    if (!file)
167	return 0;
168    file->file = f;
169    file->maxbits = maxbits;
170    file->block_compress = code & BLOCK_MASK;
171    file->maxmaxcode = 1 << file->maxbits;
172    file->tab_suffix = (char_type *) &file[1];
173    file->tab_prefix = (unsigned short *) (file->tab_suffix + file->maxmaxcode);
174    /*
175     * As above, initialize the first 256 entries in the table.
176     */
177    file->maxcode = MAXCODE(file->n_bits = INIT_BITS);
178    for ( code = 255; code >= 0; code-- ) {
179	file->tab_prefix[code] = 0;
180	file->tab_suffix[code] = (char_type) code;
181    }
182    file->free_ent = ((file->block_compress) ? FIRST : 256 );
183    file->oldcode = -1;
184    file->clear_flg = 0;
185    file->offset = 0;
186    file->size = 0;
187    file->stackp = file->de_stack;
188    bzero(file->buf, BITS);
189    return BufFileCreate ((char *) file,
190			  BufCompressedFill,
191			  0,
192			  BufCompressedSkip,
193			  BufCompressedClose);
194}
195
196static int
197BufCompressedClose (BufFilePtr f, int doClose)
198{
199    CompressedFile  *file;
200    BufFilePtr	    raw;
201
202    file = (CompressedFile *) f->private;
203    raw = file->file;
204    free (file);
205    BufFileClose (raw, doClose);
206    return 1;
207}
208
209static int
210BufCompressedFill (BufFilePtr f)
211{
212    CompressedFile  *file;
213    register char_type *stackp, *de_stack;
214    register char_type finchar;
215    register code_int code, oldcode, incode;
216    BufChar	    *buf, *bufend;
217
218    file = (CompressedFile *) f->private;
219
220    buf = f->buffer;
221    bufend = buf + BUFFILESIZE;
222    stackp = file->stackp;
223    de_stack = file->de_stack;
224    finchar = file->finchar;
225    oldcode = file->oldcode;
226    while (buf < bufend) {
227	while (stackp > de_stack && buf < bufend)
228	    *buf++ = *--stackp;
229
230	if (buf == bufend)
231	    break;
232
233	code = getcode (file);
234	if (code == -1)
235	    break;
236
237    	if ( (code == CLEAR) && file->block_compress ) {
238	    for ( code = 255; code >= 0; code-- )
239	    	file->tab_prefix[code] = 0;
240	    file->clear_flg = 1;
241	    file->free_ent = FIRST;
242	    oldcode = -1;
243	    continue;
244    	}
245    	incode = code;
246    	/*
247     	 * Special case for KwKwK string.
248     	 */
249    	if ( code >= file->free_ent ) {
250	    if ( code > file->free_ent || oldcode == -1 ) {
251		/* Bad stream. */
252		return BUFFILEEOF;
253	    }
254	    *stackp++ = finchar;
255	    code = oldcode;
256    	}
257	/*
258	 * The above condition ensures that code < free_ent.
259	 * The construction of tab_prefixof in turn guarantees that
260	 * each iteration decreases code and therefore stack usage is
261	 * bound by 1 << BITS - 256.
262	 */
263
264    	/*
265     	 * Generate output characters in reverse order
266     	 */
267    	while ( code >= 256 )
268    	{
269	    *stackp++ = file->tab_suffix[code];
270	    code = file->tab_prefix[code];
271    	}
272	finchar = file->tab_suffix[code];
273	*stackp++ = finchar;
274
275    	/*
276     	 * Generate the new entry.
277     	 */
278    	if ( (code=file->free_ent) < file->maxmaxcode && oldcode != -1) {
279	    file->tab_prefix[code] = (unsigned short)oldcode;
280	    file->tab_suffix[code] = finchar;
281	    file->free_ent = code+1;
282    	}
283	/*
284	 * Remember previous code.
285	 */
286	oldcode = incode;
287    }
288    file->oldcode = oldcode;
289    file->stackp = stackp;
290    file->finchar = finchar;
291    if (buf == f->buffer) {
292	f->left = 0;
293	return BUFFILEEOF;
294    }
295    f->bufp = f->buffer + 1;
296    f->left = (buf - f->buffer) - 1;
297    return f->buffer[0];
298}
299
300/*****************************************************************
301 * TAG( getcode )
302 *
303 * Read one code from the standard input.  If BUFFILEEOF, return -1.
304 * Inputs:
305 * 	stdin
306 * Outputs:
307 * 	code or -1 is returned.
308 */
309
310static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
311
312static code_int
313getcode(CompressedFile *file)
314{
315    register code_int code;
316    register int r_off, bits;
317    register char_type *bp = file->buf;
318    register BufFilePtr	raw;
319
320    if ( file->clear_flg > 0 || file->offset >= file->size ||
321	file->free_ent > file->maxcode )
322    {
323	/*
324	 * If the next entry will be too big for the current code
325	 * size, then we must increase the size.  This implies reading
326	 * a new buffer full, too.
327	 */
328	if ( file->free_ent > file->maxcode ) {
329	    file->n_bits++;
330	    if ( file->n_bits == file->maxbits )
331		file->maxcode = file->maxmaxcode;	/* won't get any bigger now */
332	    else
333		file->maxcode = MAXCODE(file->n_bits);
334	}
335	if ( file->clear_flg > 0) {
336    	    file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
337	    file->clear_flg = 0;
338	}
339	bits = file->n_bits;
340	raw = file->file;
341	while (bits > 0 && (code = BufFileGet (raw)) != BUFFILEEOF)
342	{
343	    *bp++ = code;
344	    --bits;
345	}
346	bp = file->buf;
347	if (bits == file->n_bits)
348	    return -1;			/* end of file */
349	file->size = file->n_bits - bits;
350	file->offset = 0;
351	/* Round size down to integral number of codes */
352	file->size = (file->size << 3) - (file->n_bits - 1);
353    }
354    r_off = file->offset;
355    bits = file->n_bits;
356    /*
357     * Get to the first byte.
358     */
359    bp += (r_off >> 3);
360    r_off &= 7;
361    /* Get first part (low order bits) */
362#ifdef NO_UCHAR
363    code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
364#else
365    code = (*bp++ >> r_off);
366#endif /* NO_UCHAR */
367    bits -= (8 - r_off);
368    r_off = 8 - r_off;		/* now, offset into code word */
369    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
370    if ( bits >= 8 ) {
371#ifdef NO_UCHAR
372	code |= (*bp++ & 0xff) << r_off;
373#else
374	code |= *bp++ << r_off;
375#endif /* NO_UCHAR */
376	r_off += 8;
377	bits -= 8;
378    }
379    /* high order bits. */
380    code |= (*bp & rmask[bits]) << r_off;
381    file->offset += file->n_bits;
382
383    return code;
384}
385
386static int
387BufCompressedSkip (BufFilePtr f, int bytes)
388{
389    int		    c;
390    while (bytes--)
391    {
392	c = BufFileGet(f);
393	if (c == BUFFILEEOF)
394	    return BUFFILEEOF;
395    }
396    return 0;
397}
398
399#ifdef TEST
400int
401main (int argc, char *argv[])
402{
403    BufFilePtr	    inputraw, input, output;
404    int		    c;
405
406    inputraw = BufFileOpenRead (0);
407    input = BufFilePushCompressed (inputraw);
408    output = BufFileOpenWrite (1);
409    while ((c = BufFileGet (input)) != BUFFILEEOF)
410	BufFilePut (c, output);
411    BufFileClose (input, FALSE);
412    BufFileClose (output, FALSE);
413    return 0;
414}
415#endif
416