src/fontfile/decompress.c

   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
  24 Copyright 1993, 1998  The Open Group
  25
  26 Permission to use, copy, modify, distribute, and sell this software and its
  27 documentation for any purpose is hereby granted without fee, provided that
  28 the above copyright notice appear in all copies and that both that
  29 copyright notice and this permission notice appear in supporting
  30 documentation.
  31
  32 The above copyright notice and this permission notice shall be included in
  33 all copies or substantial portions of the Software.
  34
  35 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  36 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  37 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  38 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  39 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  40 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  41
  42 Except as contained in this notice, the name of The Open Group shall not be
  43 used in advertising or otherwise to promote the sale, use or other dealings
  44 in 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
  63 typedef long int        code_int;
  64 #else
  65 typedef int             code_int;
  66 #endif
  67
  68 typedef 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
  76 static 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
 102 typedef 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
 127 static int BufCompressedClose ( BufFilePtr f, int doClose );
 128 static int BufCompressedFill ( BufFilePtr f );
 129 static code_int getcode ( CompressedFile *file );
 130 static int BufCompressedSkip ( BufFilePtr f, int bytes );
 131
 132 BufFilePtr
 133 BufFilePushCompressed (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
 184 static int
 185 BufCompressedClose (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
 197 static int
 198 BufCompressedFill (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
 298 static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
 299
 300 static code_int
 301 getcode(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
 374 static int
 375 BufCompressedSkip (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
 388 int
 389 main (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