decompress.c revision 23a0898a 
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  8192
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 = (CompressedFile *) xalloc (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->clear_flg = 0;
184    file->offset = 0;
185    file->size = 0;
186    file->stackp = file->de_stack;
187    bzero(file->buf, BITS);
188    file->finchar = file->oldcode = getcode (file);
189    if (file->oldcode != -1)
190	*file->stackp++ = file->finchar;
191    return BufFileCreate ((char *) file,
192			  BufCompressedFill,
193			  0,
194			  BufCompressedSkip,
195			  BufCompressedClose);
196}
197
198static int
199BufCompressedClose (BufFilePtr f, int doClose)
200{
201    CompressedFile  *file;
202    BufFilePtr	    raw;
203
204    file = (CompressedFile *) f->private;
205    raw = file->file;
206    xfree (file);
207    BufFileClose (raw, doClose);
208    return 1;
209}
210
211static int
212BufCompressedFill (BufFilePtr f)
213{
214    CompressedFile  *file;
215    register char_type *stackp, *de_stack;
216    register char_type finchar;
217    register code_int code, oldcode, incode;
218    BufChar	    *buf, *bufend;
219
220    file = (CompressedFile *) f->private;
221
222    buf = f->buffer;
223    bufend = buf + BUFFILESIZE;
224    stackp = file->stackp;
225    de_stack = file->de_stack;
226    finchar = file->finchar;
227    oldcode = file->oldcode;
228    while (buf < bufend) {
229	while (stackp > de_stack && buf < bufend)
230	    *buf++ = *--stackp;
231
232	if (buf == bufend)
233	    break;
234
235	if (oldcode == -1)
236	    break;
237
238	code = getcode (file);
239	if (code == -1)
240	    break;
241
242    	if ( (code == CLEAR) && file->block_compress ) {
243	    for ( code = 255; code >= 0; code-- )
244	    	file->tab_prefix[code] = 0;
245	    file->clear_flg = 1;
246	    file->free_ent = FIRST - 1;
247	    if ( (code = getcode (file)) == -1 )	/* O, untimely death! */
248	    	break;
249    	}
250    	incode = code;
251    	/*
252     	 * Special case for KwKwK string.
253     	 */
254    	if ( code >= file->free_ent ) {
255	    *stackp++ = finchar;
256	    code = oldcode;
257    	}
258
259    	/*
260     	 * Generate output characters in reverse order
261     	 */
262    	while ( code >= 256 )
263    	{
264	    *stackp++ = file->tab_suffix[code];
265	    code = file->tab_prefix[code];
266    	}
267	finchar = file->tab_suffix[code];
268	*stackp++ = finchar;
269
270    	/*
271     	 * Generate the new entry.
272     	 */
273    	if ( (code=file->free_ent) < file->maxmaxcode ) {
274	    file->tab_prefix[code] = (unsigned short)oldcode;
275	    file->tab_suffix[code] = finchar;
276	    file->free_ent = code+1;
277    	}
278	/*
279	 * Remember previous code.
280	 */
281	oldcode = incode;
282    }
283    file->oldcode = oldcode;
284    file->stackp = stackp;
285    file->finchar = finchar;
286    if (buf == f->buffer) {
287	f->left = 0;
288	return BUFFILEEOF;
289    }
290    f->bufp = f->buffer + 1;
291    f->left = (buf - f->buffer) - 1;
292    return f->buffer[0];
293}
294
295/*****************************************************************
296 * TAG( getcode )
297 *
298 * Read one code from the standard input.  If BUFFILEEOF, return -1.
299 * Inputs:
300 * 	stdin
301 * Outputs:
302 * 	code or -1 is returned.
303 */
304
305static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
306
307static code_int
308getcode(CompressedFile *file)
309{
310    register code_int code;
311    register int r_off, bits;
312    register char_type *bp = file->buf;
313    register BufFilePtr	raw;
314
315    if ( file->clear_flg > 0 || file->offset >= file->size ||
316	file->free_ent > file->maxcode )
317    {
318	/*
319	 * If the next entry will be too big for the current code
320	 * size, then we must increase the size.  This implies reading
321	 * a new buffer full, too.
322	 */
323	if ( file->free_ent > file->maxcode ) {
324	    file->n_bits++;
325	    if ( file->n_bits == file->maxbits )
326		file->maxcode = file->maxmaxcode;	/* won't get any bigger now */
327	    else
328		file->maxcode = MAXCODE(file->n_bits);
329	}
330	if ( file->clear_flg > 0) {
331    	    file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
332	    file->clear_flg = 0;
333	}
334	bits = file->n_bits;
335	raw = file->file;
336	while (bits > 0 && (code = BufFileGet (raw)) != BUFFILEEOF)
337	{
338	    *bp++ = code;
339	    --bits;
340	}
341	bp = file->buf;
342	if (bits == file->n_bits)
343	    return -1;			/* end of file */
344	file->size = file->n_bits - bits;
345	file->offset = 0;
346	/* Round size down to integral number of codes */
347	file->size = (file->size << 3) - (file->n_bits - 1);
348    }
349    r_off = file->offset;
350    bits = file->n_bits;
351    /*
352     * Get to the first byte.
353     */
354    bp += (r_off >> 3);
355    r_off &= 7;
356    /* Get first part (low order bits) */
357#ifdef NO_UCHAR
358    code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
359#else
360    code = (*bp++ >> r_off);
361#endif /* NO_UCHAR */
362    bits -= (8 - r_off);
363    r_off = 8 - r_off;		/* now, offset into code word */
364    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
365    if ( bits >= 8 ) {
366#ifdef NO_UCHAR
367	code |= (*bp++ & 0xff) << r_off;
368#else
369	code |= *bp++ << r_off;
370#endif /* NO_UCHAR */
371	r_off += 8;
372	bits -= 8;
373    }
374    /* high order bits. */
375    code |= (*bp & rmask[bits]) << r_off;
376    file->offset += file->n_bits;
377
378    return code;
379}
380
381static int
382BufCompressedSkip (BufFilePtr f, int bytes)
383{
384    int		    c;
385    while (bytes--)
386    {
387	c = BufFileGet(f);
388	if (c == BUFFILEEOF)
389	    return BUFFILEEOF;
390    }
391    return 0;
392}
393
394#ifdef TEST
395int
396main (int argc, char *argv[])
397{
398    BufFilePtr	    inputraw, input, output;
399    int		    c;
400
401    inputraw = BufFileOpenRead (0);
402    input = BufFilePushCompressed (inputraw);
403    output = BufFileOpenWrite (1);
404    while ((c = BufFileGet (input)) != BUFFILEEOF)
405	BufFilePut (c, output);
406    BufFileClose (input, FALSE);
407    BufFileClose (output, FALSE);
408    return 0;
409}
410#endif
411