git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/os/decompress.c

   1 /* $XConsortium: decompress.c,v 1.5 94/04/17 20:26:57 dpw Exp $ */
   2 /*
   3
   4 Copyright (c) 1990  X Consortium
   5
   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:
  13
  14 The above copyright notice and this permission notice shall be included
  15 in all copies or substantial portions of the Software.
  16
  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.
  24
  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.
  29
  30 */
  31
  32
  33 /*
  34  * decompress - cat a compressed file
  35  */
  36
  37 #include <stdio.h>
  38
  39 #ifdef TEST
  40 #define xalloc(s)   malloc(s)
  41 #define xfree(s)    free(s)
  42
  43 typedef char    *FID;
  44
  45 #include <sys/types.h>
  46 #include <sys/stat.h>
  47 #include <ctype.h>
  48
  49 #else
  50 #include    "Xos.h"
  51 #include    "misc.h"
  52 #endif
  53
  54 #define BITS    16
  55
  56 /*
  57  * a code_int must be able to hold 2**BITS values of type int, and also -1
  58  */
  59 #if BITS > 15
  60 typedef long int        code_int;
  61 #else
  62 typedef int             code_int;
  63 #endif
  64
  65 typedef long int          count_int;
  66
  67 #ifdef NO_UCHAR
  68  typedef char   char_type;
  69 #else
  70  typedef        unsigned char   char_type;
  71 #endif /* UCHAR */
  72
  73 static char_type magic_header[] = { "\037\235" };       /* 1F 9D */
  74
  75 /* Defines for third byte of header */
  76 #define BIT_MASK        0x1f
  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).
  80 */
  81
  82 #define INIT_BITS 9                     /* initial number of bits/code */
  83
  84 #ifdef COMPATIBLE               /* But wrong! */
  85 # define MAXCODE(n_bits)        (1 << (n_bits) - 1)
  86 #else
  87 # define MAXCODE(n_bits)        ((1 << (n_bits)) - 1)
  88 #endif /* COMPATIBLE */
  89
  90 static code_int getcode();
  91
  92 /*
  93  * the next two codes should not be changed lightly, as they must not
  94  * lie within the contiguous general code space.
  95  */
  96 #define FIRST   257     /* first free entry */
  97 #define CLEAR   256     /* table clear output code */
  98
  99 #define STACK_SIZE  8192
 100
 101 typedef struct _compressedFILE {
 102     FILE        *file;
 103
 104     char_type       *stackp;
 105     code_int        oldcode;
 106     char_type       finchar;
 107
 108     int         block_compress;
 109     int         maxbits;
 110     code_int    maxcode, maxmaxcode;
 111
 112     code_int    free_ent;
 113     int         clear_flg;
 114     int         n_bits;
 115
 116     /* bit buffer */
 117     int         offset, size;
 118     char_type   buf[BITS];
 119
 120     char_type       de_stack[STACK_SIZE];
 121     char_type       *tab_suffix;
 122     unsigned short  *tab_prefix;
 123 } CompressedFile;
 124
 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 */
 131 };
 132
 133 FID
 134 CompressedFontFileInit (f)
 135     FILE        *f;
 136 {
 137     int             code;
 138     int             maxbits;
 139     int             hsize;
 140     CompressedFile  *file;
 141     int             extra;
 142
 143     if ((getc(f) != (magic_header[0] & 0xFF)) ||
 144         (getc(f) != (magic_header[1] & 0xFF)))
 145     {
 146         return 0;
 147     }
 148     code = getc (f);
 149     maxbits = code & BIT_MASK;
 150     if (maxbits > BITS || maxbits < 12)
 151         return 0;
 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);
 156     if (!file)
 157         return 0;
 158     file->file = f;
 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);
 164     /*
 165      * As above, initialize the first 256 entries in the table.
 166      */
 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;
 171     }
 172     file->free_ent = ((file->block_compress) ? FIRST : 256 );
 173     file->clear_flg = 0;
 174     file->offset = 0;
 175     file->size = 0;
 176     file->stackp = file->de_stack;
 177     file->finchar = file->oldcode = getcode (file);
 178     if (file->oldcode != -1)
 179         *file->stackp++ = file->finchar;
 180     return (FID) file;
 181 }
 182
 183 FILE *
 184 CompressedFontFileDone (fid)
 185     FID             fid;
 186 {
 187     CompressedFile  *file;
 188     FILE    *f;
 189
 190     file = (CompressedFile *) fid;
 191     f = file->file;
 192     xfree (file);
 193     return f;
 194 }
 195
 196 #define getdcchar(file)    ((file)->stackp > (file)->de_stack ? (*--((file)->stackp)) : _filldcbuf (file))
 197
 198 _filldcbuf (file)
 199     CompressedFile  *file;
 200 {
 201     register char_type *stackp;
 202     register code_int code, incode;
 203
 204     if (file->stackp > file->de_stack)
 205         return *--file->stackp;
 206
 207     if (file->oldcode == -1)
 208         return EOF;
 209
 210     stackp = file->stackp;
 211     code = getcode (file);
 212     if (code == -1)
 213         return EOF;
 214
 215     if ( (code == CLEAR) && file->block_compress ) {
 216         for ( code = 255; code >= 0; code-- )
 217             file->tab_prefix[code] = 0;
 218         file->clear_flg = 1;
 219         file->free_ent = FIRST - 1;
 220         if ( (code = getcode (file)) == -1 )    /* O, untimely death! */
 221             return EOF;
 222     }
 223     incode = code;
 224     /*
 225      * Special case for KwKwK string.
 226      */
 227     if ( code >= file->free_ent ) {
 228         *stackp++ = file->finchar;
 229         code = file->oldcode;
 230     }
 231
 232     /*
 233      * Generate output characters in reverse order
 234      */
 235     while ( code >= 256 )
 236     {
 237         *stackp++ = file->tab_suffix[code];
 238         code = file->tab_prefix[code];
 239     }
 240     file->finchar = file->tab_suffix[code];
 241
 242     /*
 243      * Generate the new entry.
 244      */
 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;
 249     }
 250     /*
 251      * Remember previous code.
 252      */
 253     file->oldcode = incode;
 254     file->stackp = stackp;
 255     return file->finchar;
 256 }
 257
 258 /*****************************************************************
 259  * TAG( getcode )
 260  *
 261  * Read one code from the standard input.  If EOF, return -1.
 262  * Inputs:
 263  *      stdin
 264  * Outputs:
 265  *      code or -1 is returned.
 266  */
 267
 268 static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
 269
 270 static code_int
 271 getcode(file)
 272     CompressedFile  *file;
 273 {
 274     register code_int code;
 275     register int r_off, bits;
 276     register char_type *bp = file->buf;
 277     register FILE   *fp;
 278
 279     if ( file->clear_flg > 0 || file->offset >= file->size ||
 280         file->free_ent > file->maxcode )
 281     {
 282         /*
 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.
 286          */
 287         if ( file->free_ent > file->maxcode ) {
 288             file->n_bits++;
 289             if ( file->n_bits == file->maxbits )
 290                 file->maxcode = file->maxmaxcode;       /* won't get any bigger now */
 291             else
 292                 file->maxcode = MAXCODE(file->n_bits);
 293         }
 294         if ( file->clear_flg > 0) {
 295             file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
 296             file->clear_flg = 0;
 297         }
 298         bits = file->n_bits;
 299         fp = file->file;
 300         while (bits > 0 && (code = getc (fp)) != EOF)
 301         {
 302             *bp++ = code;
 303             --bits;
 304         }
 305         bp = file->buf;
 306         if (bits == file->n_bits)
 307             return -1;                  /* end of file */
 308         file->size = file->n_bits - bits;
 309         file->offset = 0;
 310         /* Round size down to integral number of codes */
 311         file->size = (file->size << 3) - (file->n_bits - 1);
 312     }
 313     r_off = file->offset;
 314     bits = file->n_bits;
 315     /*
 316      * Get to the first byte.
 317      */
 318     bp += (r_off >> 3);
 319     r_off &= 7;
 320     /* Get first part (low order bits) */
 321 #ifdef NO_UCHAR
 322     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
 323 #else
 324     code = (*bp++ >> r_off);
 325 #endif /* NO_UCHAR */
 326     bits -= (8 - r_off);
 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). */
 329     if ( bits >= 8 ) {
 330 #ifdef NO_UCHAR
 331         code |= (*bp++ & 0xff) << r_off;
 332 #else
 333         code |= *bp++ << r_off;
 334 #endif /* NO_UCHAR */
 335         r_off += 8;
 336         bits -= 8;
 337     }
 338     /* high order bits. */
 339     code |= (*bp & rmask[bits]) << r_off;
 340     file->offset += file->n_bits;
 341
 342     return code;
 343 }
 344
 345 CompressedFontFileRead (buf, itemsize, nitems, fid)
 346     char        *buf;
 347     unsigned    itemsize;
 348     unsigned    nitems;
 349     FID         fid;
 350 {
 351     CompressedFile  *file;
 352     int             c;
 353     int             nbytes;
 354
 355     file = (CompressedFile *) fid;
 356     nbytes = nitems * itemsize;
 357     while (nbytes)
 358     {
 359         if ((c = getdcchar (file)) == EOF)
 360             break;
 361         *buf++ = c;
 362         --nbytes;
 363     }
 364     return nitems - nbytes / itemsize;
 365 }
 366
 367 CompressedFontFileSkip (bytes, fid)
 368     unsigned    bytes;
 369     FID         fid;
 370 {
 371     int     c;
 372
 373     while (bytes-- && ((c = getdcchar((CompressedFile *)fid)) != EOF))
 374             ;
 375     return c;
 376 }
 377
 378 #ifdef TEST
 379 main ()
 380 {
 381     CompressedFile  *input;
 382     int             c;
 383
 384     input = (CompressedFile *) CompressedFontFileInit (stdin);
 385     while ((c = getdcchar (input)) != -1)
 386         putchar (c);
 387 }
 388 #endif