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 MERCHANTIBILITY 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 <X11/fonts/fontmisc.h>
55#include <X11/fonts/bufio.h>
56
57#define BITS	16
58
59/*
60 * a code_int must be able to hold 2**BITS values of type int, and also -1
61 */
62#if BITS > 15
63typedef long int	code_int;
64#else
65typedef int		code_int;
66#endif
67
68typedef long int	  count_int;
69
70#ifdef NO_UCHAR
71 typedef char	char_type;
72#else
73 typedef	unsigned char	char_type;
74#endif /* UCHAR */
75
76static char_type magic_header[] = { "\037\235" };	/* 1F 9D */
77
78/* Defines for third byte of header */
79#define BIT_MASK	0x1f
80#define BLOCK_MASK	0x80
81/* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
82   a fourth header byte (for expansion).
83*/
84
85#define INIT_BITS 9			/* initial number of bits/code */
86
87#ifdef COMPATIBLE		/* But wrong! */
88# define MAXCODE(n_bits)	(1 << (n_bits) - 1)
89#else
90# define MAXCODE(n_bits)	((1 << (n_bits)) - 1)
91#endif /* COMPATIBLE */
92
93/*
94 * the next two codes should not be changed lightly, as they must not
95 * lie within the contiguous general code space.
96 */
97#define FIRST	257	/* first free entry */
98#define	CLEAR	256	/* table clear output code */
99
100#define STACK_SIZE  65300
101
102typedef struct _compressedFILE {
103    BufFilePtr	    file;
104
105    char_type	    *stackp;
106    code_int	    oldcode;
107    char_type	    finchar;
108
109    int		block_compress;
110    int		maxbits;
111    code_int	maxcode, maxmaxcode;
112
113    code_int	free_ent;
114    int		clear_flg;
115    int		n_bits;
116
117    /* bit buffer */
118    int		offset, size;
119    char_type	buf[BITS];
120
121    char_type	    de_stack[STACK_SIZE];
122    char_type	    *tab_suffix;
123    unsigned short  *tab_prefix;
124} CompressedFile;
125
126
127static int BufCompressedClose ( BufFilePtr f, int doClose );
128static int BufCompressedFill ( BufFilePtr f );
129static code_int getcode ( CompressedFile *file );
130static int BufCompressedSkip ( BufFilePtr f, int bytes );
131
132BufFilePtr
133BufFilePushCompressed (BufFilePtr f)
134{
135    int		    code;
136    int		    maxbits;
137    CompressedFile  *file;
138    int		    extra;
139
140    if ((BufFileGet(f) != (magic_header[0] & 0xFF)) ||
141	(BufFileGet(f) != (magic_header[1] & 0xFF)))
142    {
143	return 0;
144    }
145    code = BufFileGet (f);
146    if (code == BUFFILEEOF) return 0;
147
148    maxbits = code & BIT_MASK;
149    if (maxbits > BITS || maxbits <= INIT_BITS)
150	return 0;
151    extra = (1 << maxbits) * sizeof (char_type) +
152	    (1 << maxbits) * sizeof (unsigned short);
153    file = malloc (sizeof (CompressedFile) + extra);
154    if (!file)
155	return 0;
156    file->file = f;
157    file->maxbits = maxbits;
158    file->block_compress = code & BLOCK_MASK;
159    file->maxmaxcode = 1 << file->maxbits;
160    file->tab_suffix = (char_type *) &file[1];
161    file->tab_prefix = (unsigned short *) (file->tab_suffix + file->maxmaxcode);
162    /*
163     * As above, initialize the first 256 entries in the table.
164     */
165    file->maxcode = MAXCODE(file->n_bits = INIT_BITS);
166    for ( code = 255; code >= 0; code-- ) {
167	file->tab_prefix[code] = 0;
168	file->tab_suffix[code] = (char_type) code;
169    }
170    file->free_ent = ((file->block_compress) ? FIRST : 256 );
171    file->oldcode = -1;
172    file->clear_flg = 0;
173    file->offset = 0;
174    file->size = 0;
175    file->stackp = file->de_stack;
176    bzero(file->buf, BITS);
177    return BufFileCreate ((char *) file,
178			  BufCompressedFill,
179			  0,
180			  BufCompressedSkip,
181			  BufCompressedClose);
182}
183
184static int
185BufCompressedClose (BufFilePtr f, int doClose)
186{
187    CompressedFile  *file;
188    BufFilePtr	    raw;
189
190    file = (CompressedFile *) f->private;
191    raw = file->file;
192    free (file);
193    BufFileClose (raw, doClose);
194    return 1;
195}
196
197static int
198BufCompressedFill (BufFilePtr f)
199{
200    CompressedFile  *file;
201    register char_type *stackp, *de_stack;
202    register char_type finchar;
203    register code_int code, oldcode, incode;
204    BufChar	    *buf, *bufend;
205
206    file = (CompressedFile *) f->private;
207
208    buf = f->buffer;
209    bufend = buf + BUFFILESIZE;
210    stackp = file->stackp;
211    de_stack = file->de_stack;
212    finchar = file->finchar;
213    oldcode = file->oldcode;
214    while (buf < bufend) {
215	while (stackp > de_stack && buf < bufend)
216	    *buf++ = *--stackp;
217
218	if (buf == bufend)
219	    break;
220
221	code = getcode (file);
222	if (code == -1)
223	    break;
224
225    	if ( (code == CLEAR) && file->block_compress ) {
226	    for ( code = 255; code >= 0; code-- )
227	    	file->tab_prefix[code] = 0;
228	    file->clear_flg = 1;
229	    file->free_ent = FIRST;
230	    oldcode = -1;
231	    continue;
232    	}
233    	incode = code;
234    	/*
235     	 * Special case for KwKwK string.
236     	 */
237    	if ( code >= file->free_ent ) {
238	    if ( code > file->free_ent || oldcode == -1 ) {
239		/* Bad stream. */
240		return BUFFILEEOF;
241	    }
242	    *stackp++ = finchar;
243	    code = oldcode;
244    	}
245	/*
246	 * The above condition ensures that code < free_ent.
247	 * The construction of tab_prefixof in turn guarantees that
248	 * each iteration decreases code and therefore stack usage is
249	 * bound by 1 << BITS - 256.
250	 */
251
252    	/*
253     	 * Generate output characters in reverse order
254     	 */
255    	while ( code >= 256 )
256    	{
257	    *stackp++ = file->tab_suffix[code];
258	    code = file->tab_prefix[code];
259    	}
260	finchar = file->tab_suffix[code];
261	*stackp++ = finchar;
262
263    	/*
264     	 * Generate the new entry.
265     	 */
266    	if ( (code=file->free_ent) < file->maxmaxcode && oldcode != -1) {
267	    file->tab_prefix[code] = (unsigned short)oldcode;
268	    file->tab_suffix[code] = finchar;
269	    file->free_ent = code+1;
270    	}
271	/*
272	 * Remember previous code.
273	 */
274	oldcode = incode;
275    }
276    file->oldcode = oldcode;
277    file->stackp = stackp;
278    file->finchar = finchar;
279    if (buf == f->buffer) {
280	f->left = 0;
281	return BUFFILEEOF;
282    }
283    f->bufp = f->buffer + 1;
284    f->left = (buf - f->buffer) - 1;
285    return f->buffer[0];
286}
287
288/*****************************************************************
289 * TAG( getcode )
290 *
291 * Read one code from the standard input.  If BUFFILEEOF, return -1.
292 * Inputs:
293 * 	stdin
294 * Outputs:
295 * 	code or -1 is returned.
296 */
297
298static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
299
300static code_int
301getcode(CompressedFile *file)
302{
303    register code_int code;
304    register int r_off, bits;
305    register char_type *bp = file->buf;
306    register BufFilePtr	raw;
307
308    if ( file->clear_flg > 0 || file->offset >= file->size ||
309	file->free_ent > file->maxcode )
310    {
311	/*
312	 * If the next entry will be too big for the current code
313	 * size, then we must increase the size.  This implies reading
314	 * a new buffer full, too.
315	 */
316	if ( file->free_ent > file->maxcode ) {
317	    file->n_bits++;
318	    if ( file->n_bits == file->maxbits )
319		file->maxcode = file->maxmaxcode;	/* won't get any bigger now */
320	    else
321		file->maxcode = MAXCODE(file->n_bits);
322	}
323	if ( file->clear_flg > 0) {
324    	    file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
325	    file->clear_flg = 0;
326	}
327	bits = file->n_bits;
328	raw = file->file;
329	while (bits > 0 && (code = BufFileGet (raw)) != BUFFILEEOF)
330	{
331	    *bp++ = code;
332	    --bits;
333	}
334	bp = file->buf;
335	if (bits == file->n_bits)
336	    return -1;			/* end of file */
337	file->size = file->n_bits - bits;
338	file->offset = 0;
339	/* Round size down to integral number of codes */
340	file->size = (file->size << 3) - (file->n_bits - 1);
341    }
342    r_off = file->offset;
343    bits = file->n_bits;
344    /*
345     * Get to the first byte.
346     */
347    bp += (r_off >> 3);
348    r_off &= 7;
349    /* Get first part (low order bits) */
350#ifdef NO_UCHAR
351    code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
352#else
353    code = (*bp++ >> r_off);
354#endif /* NO_UCHAR */
355    bits -= (8 - r_off);
356    r_off = 8 - r_off;		/* now, offset into code word */
357    /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
358    if ( bits >= 8 ) {
359#ifdef NO_UCHAR
360	code |= (*bp++ & 0xff) << r_off;
361#else
362	code |= *bp++ << r_off;
363#endif /* NO_UCHAR */
364	r_off += 8;
365	bits -= 8;
366    }
367    /* high order bits. */
368    code |= (*bp & rmask[bits]) << r_off;
369    file->offset += file->n_bits;
370
371    return code;
372}
373
374static int
375BufCompressedSkip (BufFilePtr f, int bytes)
376{
377    int		    c;
378    while (bytes--)
379    {
380	c = BufFileGet(f);
381	if (c == BUFFILEEOF)
382	    return BUFFILEEOF;
383    }
384    return 0;
385}
386
387#ifdef TEST
388int
389main (int argc, char *argv[])
390{
391    BufFilePtr	    inputraw, input, output;
392    int		    c;
393
394    inputraw = BufFileOpenRead (0);
395    input = BufFilePushCompressed (inputraw);
396    output = BufFileOpenWrite (1);
397    while ((c = BufFileGet (input)) != BUFFILEEOF)
398	BufFilePut (c, output);
399    BufFileClose (input, FALSE);
400    BufFileClose (output, FALSE);
401    return 0;
402}
403#endif
404