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