1 /* $XConsortium: decompress.c,v 1.5 94/04/17 20:26:57 dpw Exp $ */
4 Copyright (c) 1990 X Consortium
6 Permission is hereby granted, free of charge, to any person obtaining
7 a copy of this software and associated documentation files (the
8 "Software"), to deal in the Software without restriction, including
9 without limitation the rights to use, copy, modify, merge, publish,
10 distribute, sublicense, and/or sell copies of the Software, and to
11 permit persons to whom the Software is furnished to do so, subject to
12 the following conditions:
14 The above copyright notice and this permission notice shall be included
15 in all copies or substantial portions of the Software.
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
20 IN NO EVENT SHALL THE X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR
21 OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
22 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
23 OTHER DEALINGS IN THE SOFTWARE.
25 Except as contained in this notice, the name of the X Consortium shall
26 not be used in advertising or otherwise to promote the sale, use or
27 other dealings in this Software without prior written authorization
28 from the X Consortium.
34 * decompress - cat a compressed file
40 #define xalloc(s) malloc(s)
41 #define xfree(s) free(s)
45 #include <sys/types.h>
57 * a code_int must be able to hold 2**BITS values of type int, and also -1
60 typedef long int code_int;
65 typedef long int count_int;
68 typedef char char_type;
70 typedef unsigned char char_type;
73 static char_type magic_header[] = { "\037\235" }; /* 1F 9D */
75 /* Defines for third byte of header */
77 #define BLOCK_MASK 0x80
78 /* Masks 0x40 and 0x20 are free. I think 0x20 should mean that there is
79 a fourth header byte (for expansion).
82 #define INIT_BITS 9 /* initial number of bits/code */
84 #ifdef COMPATIBLE /* But wrong! */
85 # define MAXCODE(n_bits) (1 << (n_bits) - 1)
87 # define MAXCODE(n_bits) ((1 << (n_bits)) - 1)
88 #endif /* COMPATIBLE */
90 static code_int getcode();
93 * the next two codes should not be changed lightly, as they must not
94 * lie within the contiguous general code space.
96 #define FIRST 257 /* first free entry */
97 #define CLEAR 256 /* table clear output code */
99 #define STACK_SIZE 8192
101 typedef struct _compressedFILE {
110 code_int maxcode, maxmaxcode;
120 char_type de_stack[STACK_SIZE];
121 char_type *tab_suffix;
122 unsigned short *tab_prefix;
125 static int hsize_table[] = {
126 5003, /* 12 bits - 80% occupancy */
127 9001, /* 13 bits - 91% occupancy */
128 18013, /* 14 bits - 91% occupancy */
129 35023, /* 15 bits - 94% occupancy */
130 69001 /* 16 bits - 95% occupancy */
134 CompressedFontFileInit (f)
140 CompressedFile *file;
143 if ((getc(f) != (magic_header[0] & 0xFF)) ||
144 (getc(f) != (magic_header[1] & 0xFF)))
149 maxbits = code & BIT_MASK;
150 if (maxbits > BITS || maxbits < 12)
152 hsize = hsize_table[maxbits - 12];
153 extra = (1 << maxbits) * sizeof (char_type) +
154 hsize * sizeof (unsigned short);
155 file = (CompressedFile *) xalloc (sizeof (CompressedFile) + extra);
159 file->maxbits = maxbits;
160 file->block_compress = code & BLOCK_MASK;
161 file->maxmaxcode = 1 << file->maxbits;
162 file->tab_suffix = (char_type *) &file[1];
163 file->tab_prefix = (unsigned short *) (file->tab_suffix + file->maxmaxcode);
165 * As above, initialize the first 256 entries in the table.
167 file->maxcode = MAXCODE(file->n_bits = INIT_BITS);
168 for ( code = 255; code >= 0; code-- ) {
169 file->tab_prefix[code] = 0;
170 file->tab_suffix[code] = (char_type) code;
172 file->free_ent = ((file->block_compress) ? FIRST : 256 );
176 file->stackp = file->de_stack;
177 file->finchar = file->oldcode = getcode (file);
178 if (file->oldcode != -1)
179 *file->stackp++ = file->finchar;
184 CompressedFontFileDone (fid)
187 CompressedFile *file;
190 file = (CompressedFile *) fid;
196 #define getdcchar(file) ((file)->stackp > (file)->de_stack ? (*--((file)->stackp)) : _filldcbuf (file))
199 CompressedFile *file;
201 register char_type *stackp;
202 register code_int code, incode;
204 if (file->stackp > file->de_stack)
205 return *--file->stackp;
207 if (file->oldcode == -1)
210 stackp = file->stackp;
211 code = getcode (file);
215 if ( (code == CLEAR) && file->block_compress ) {
216 for ( code = 255; code >= 0; code-- )
217 file->tab_prefix[code] = 0;
219 file->free_ent = FIRST - 1;
220 if ( (code = getcode (file)) == -1 ) /* O, untimely death! */
225 * Special case for KwKwK string.
227 if ( code >= file->free_ent ) {
228 *stackp++ = file->finchar;
229 code = file->oldcode;
233 * Generate output characters in reverse order
235 while ( code >= 256 )
237 *stackp++ = file->tab_suffix[code];
238 code = file->tab_prefix[code];
240 file->finchar = file->tab_suffix[code];
243 * Generate the new entry.
245 if ( (code=file->free_ent) < file->maxmaxcode ) {
246 file->tab_prefix[code] = (unsigned short)file->oldcode;
247 file->tab_suffix[code] = file->finchar;
248 file->free_ent = code+1;
251 * Remember previous code.
253 file->oldcode = incode;
254 file->stackp = stackp;
255 return file->finchar;
258 /*****************************************************************
261 * Read one code from the standard input. If EOF, return -1.
265 * code or -1 is returned.
268 static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
272 CompressedFile *file;
274 register code_int code;
275 register int r_off, bits;
276 register char_type *bp = file->buf;
279 if ( file->clear_flg > 0 || file->offset >= file->size ||
280 file->free_ent > file->maxcode )
283 * If the next entry will be too big for the current code
284 * size, then we must increase the size. This implies reading
285 * a new buffer full, too.
287 if ( file->free_ent > file->maxcode ) {
289 if ( file->n_bits == file->maxbits )
290 file->maxcode = file->maxmaxcode; /* won't get any bigger now */
292 file->maxcode = MAXCODE(file->n_bits);
294 if ( file->clear_flg > 0) {
295 file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
300 while (bits > 0 && (code = getc (fp)) != EOF)
306 if (bits == file->n_bits)
307 return -1; /* end of file */
308 file->size = file->n_bits - bits;
310 /* Round size down to integral number of codes */
311 file->size = (file->size << 3) - (file->n_bits - 1);
313 r_off = file->offset;
316 * Get to the first byte.
320 /* Get first part (low order bits) */
322 code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
324 code = (*bp++ >> r_off);
325 #endif /* NO_UCHAR */
327 r_off = 8 - r_off; /* now, offset into code word */
328 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
331 code |= (*bp++ & 0xff) << r_off;
333 code |= *bp++ << r_off;
334 #endif /* NO_UCHAR */
338 /* high order bits. */
339 code |= (*bp & rmask[bits]) << r_off;
340 file->offset += file->n_bits;
345 CompressedFontFileRead (buf, itemsize, nitems, fid)
351 CompressedFile *file;
355 file = (CompressedFile *) fid;
356 nbytes = nitems * itemsize;
359 if ((c = getdcchar (file)) == EOF)
364 return nitems - nbytes / itemsize;
367 CompressedFontFileSkip (bytes, fid)
373 while (bytes-- && ((c = getdcchar((CompressedFile *)fid)) != EOF))
381 CompressedFile *input;
384 input = (CompressedFile *) CompressedFontFileInit (stdin);
385 while ((c = getdcchar (input)) != -1)