home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / X / mit / server / os / decompress.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-11-07  |  8.0 KB  |  364 lines
  1. /* 
  2.  * decompress - cat a compressed file
  3.  */
  4.  
  5. #include <stdio.h>
  6.  
  7. #ifdef TEST
  8. #define xalloc(s)   malloc(s)
  9. #define xfree(s)    free(s)
  10.  
  11. typedef char    *FID;
  12.  
  13. #include <ctype.h>
  14. #include <signal.h>
  15. #include <sys/types.h>
  16. #include <sys/stat.h>
  17.  
  18. #else
  19. #include    "Xos.h"
  20. #include    "misc.h"
  21. #endif
  22.  
  23. #define BITS    16
  24.  
  25. /*
  26.  * a code_int must be able to hold 2**BITS values of type int, and also -1
  27.  */
  28. #if BITS > 15
  29. typedef long int    code_int;
  30. #else
  31. typedef int        code_int;
  32. #endif
  33.  
  34. typedef long int      count_int;
  35.  
  36. #ifdef NO_UCHAR
  37.  typedef char    char_type;
  38. #else
  39.  typedef    unsigned char    char_type;
  40. #endif /* UCHAR */
  41.  
  42. char_type magic_header[] = { "\037\235" };    /* 1F 9D */
  43.  
  44. /* Defines for third byte of header */
  45. #define BIT_MASK    0x1f
  46. #define BLOCK_MASK    0x80
  47. /* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
  48.    a fourth header byte (for expansion).
  49. */
  50.  
  51. #define INIT_BITS 9            /* initial number of bits/code */
  52.  
  53. #ifdef COMPATIBLE        /* But wrong! */
  54. # define MAXCODE(n_bits)    (1 << (n_bits) - 1)
  55. #else
  56. # define MAXCODE(n_bits)    ((1 << (n_bits)) - 1)
  57. #endif /* COMPATIBLE */
  58.  
  59. static code_int getcode();
  60.  
  61. /*
  62.  * the next two codes should not be changed lightly, as they must not
  63.  * lie within the contiguous general code space.
  64.  */ 
  65. #define FIRST    257    /* first free entry */
  66. #define    CLEAR    256    /* table clear output code */
  67.  
  68. #define STACK_SIZE  8192
  69.  
  70. typedef struct _compressedFILE {
  71.     FILE    *file;
  72.  
  73.     char_type        *stackp;
  74.     code_int        oldcode;
  75.     char_type        finchar;
  76.  
  77.     int        block_compress;
  78.     int        maxbits;
  79.     code_int    maxcode, maxmaxcode;
  80.  
  81.     code_int    free_ent;
  82.     int        clear_flg;
  83.     int        n_bits;
  84.  
  85.     /* bit buffer */
  86.     int        offset, size;
  87.     char_type    buf[BITS];
  88.  
  89.     char_type        de_stack[STACK_SIZE];
  90.     char_type        *tab_suffix;
  91.     unsigned short  *tab_prefix;
  92. } CompressedFile;
  93.  
  94. writeerr ()
  95. {
  96.     fprintf (stderr, "cannot write output\n");
  97.     exit (1);
  98. }
  99.  
  100. int hsize_table[] = {
  101.     5003,    /* 12 bits - 80% occupancy */
  102.     9001,    /* 13 bits - 91% occupancy */
  103.     18013,    /* 14 bits - 91% occupancy */
  104.     35023,    /* 15 bits - 94% occupancy */
  105.     69001    /* 16 bits - 95% occupancy */
  106. };
  107.  
  108. FID
  109. CompressedFontFileInit (f)
  110.     FILE    *f;
  111. {
  112.     int            code;
  113.     int            maxbits;
  114.     int            hsize;
  115.     CompressedFile  *file;
  116.     int            extra;
  117.  
  118.     if ((getc(f) != (magic_header[0] & 0xFF)) ||
  119.     (getc(f) != (magic_header[1] & 0xFF)))
  120.     {
  121.     return 0;
  122.     }
  123.     code = getc (f);
  124.     maxbits = code & BIT_MASK;
  125.     if (maxbits > BITS || maxbits < 12)
  126.     return 0;
  127.     hsize = hsize_table[maxbits - 12];
  128.     extra = (1 << maxbits) * sizeof (char_type) +
  129.         hsize * sizeof (unsigned short);
  130.     file = (CompressedFile *) xalloc (sizeof (CompressedFile) + extra);
  131.     if (!file)
  132.     return 0;
  133.     file->file = f;
  134.     file->maxbits = maxbits;
  135.     file->block_compress = code & BLOCK_MASK;
  136.     file->maxmaxcode = 1 << file->maxbits;
  137.     file->tab_suffix = (char_type *) &file[1];
  138.     file->tab_prefix = (unsigned short *) (file->tab_suffix + file->maxmaxcode);
  139.     /*
  140.      * As above, initialize the first 256 entries in the table.
  141.      */
  142.     file->maxcode = MAXCODE(file->n_bits = INIT_BITS);
  143.     for ( code = 255; code >= 0; code-- ) {
  144.     file->tab_prefix[code] = 0;
  145.     file->tab_suffix[code] = (char_type) code;
  146.     }
  147.     file->free_ent = ((file->block_compress) ? FIRST : 256 );
  148.     file->clear_flg = 0;
  149.     file->offset = 0;
  150.     file->size = 0;
  151.     file->stackp = file->de_stack;
  152.     file->finchar = file->oldcode = getcode (file);
  153.     if (file->oldcode != -1)
  154.     *file->stackp++ = file->finchar;
  155.     return (FID) file;
  156. }
  157.  
  158. FILE *
  159. CompressedFontFileDone (fid)
  160.     FID            fid;
  161. {
  162.     CompressedFile  *file;
  163.     FILE    *f;
  164.  
  165.     file = (CompressedFile *) fid;
  166.     f = file->file;
  167.     xfree (file);
  168.     return f;
  169. }
  170.  
  171. #define getdcchar(file)    ((file)->stackp > (file)->de_stack ? (*--((file)->stackp)) : _filldcbuf (file))
  172.  
  173. _filldcbuf (file)
  174.     CompressedFile  *file;
  175. {
  176.     register char_type *stackp;
  177.     register code_int code, incode;
  178.  
  179.     if (file->stackp > file->de_stack)
  180.     return *--file->stackp;
  181.  
  182.     if (file->oldcode == -1)
  183.     return EOF;
  184.  
  185.     stackp = file->stackp;
  186.     code = getcode (file);
  187.     if (code == -1)
  188.     return EOF;
  189.  
  190.     if ( (code == CLEAR) && file->block_compress ) {
  191.     for ( code = 255; code >= 0; code-- )
  192.         file->tab_prefix[code] = 0;
  193.     file->clear_flg = 1;
  194.     file->free_ent = FIRST - 1;
  195.     if ( (code = getcode (file)) == -1 )    /* O, untimely death! */
  196.         return EOF;
  197.     }
  198.     incode = code;
  199.     /*
  200.      * Special case for KwKwK string.
  201.      */
  202.     if ( code >= file->free_ent ) {
  203.     *stackp++ = file->finchar;
  204.     code = file->oldcode;
  205.     }
  206.  
  207.     /*
  208.      * Generate output characters in reverse order
  209.      */
  210.     while ( code >= 256 )
  211.     {
  212.     *stackp++ = file->tab_suffix[code];
  213.     code = file->tab_prefix[code];
  214.     }
  215.     file->finchar = file->tab_suffix[code];
  216.  
  217.     /*
  218.      * Generate the new entry.
  219.      */
  220.     if ( (code=file->free_ent) < file->maxmaxcode ) {
  221.     file->tab_prefix[code] = (unsigned short)file->oldcode;
  222.     file->tab_suffix[code] = file->finchar;
  223.     file->free_ent = code+1;
  224.     } 
  225.     /*
  226.      * Remember previous code.
  227.      */
  228.     file->oldcode = incode;
  229.     file->stackp = stackp;
  230.     return file->finchar;
  231. }
  232.  
  233. /*****************************************************************
  234.  * TAG( getcode )
  235.  *
  236.  * Read one code from the standard input.  If EOF, return -1.
  237.  * Inputs:
  238.  *     stdin
  239.  * Outputs:
  240.  *     code or -1 is returned.
  241.  */
  242.  
  243. static char_type rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  244.  
  245. static code_int
  246. getcode(file)
  247.     CompressedFile  *file;
  248. {
  249.     register code_int code;
  250.     register int r_off, bits;
  251.     register char_type *bp = file->buf;
  252.     register FILE   *fp;
  253.  
  254.     if ( file->clear_flg > 0 || file->offset >= file->size ||
  255.     file->free_ent > file->maxcode )
  256.     {
  257.     /*
  258.      * If the next entry will be too big for the current code
  259.      * size, then we must increase the size.  This implies reading
  260.      * a new buffer full, too.
  261.      */
  262.     if ( file->free_ent > file->maxcode ) {
  263.         file->n_bits++;
  264.         if ( file->n_bits == file->maxbits )
  265.         file->maxcode = file->maxmaxcode;    /* won't get any bigger now */
  266.         else
  267.         file->maxcode = MAXCODE(file->n_bits);
  268.     }
  269.     if ( file->clear_flg > 0) {
  270.             file->maxcode = MAXCODE (file->n_bits = INIT_BITS);
  271.         file->clear_flg = 0;
  272.     }
  273.     bits = file->n_bits;
  274.     fp = file->file;
  275.     while (bits > 0 && (code = getc (fp)) != EOF)
  276.     {
  277.         *bp++ = code;
  278.         --bits;
  279.     }
  280.     bp = file->buf;
  281.     if (bits == file->n_bits)
  282.         return -1;            /* end of file */
  283.     file->size = file->n_bits - bits;
  284.     file->offset = 0;
  285.     /* Round size down to integral number of codes */
  286.     file->size = (file->size << 3) - (file->n_bits - 1);
  287.     }
  288.     r_off = file->offset;
  289.     bits = file->n_bits;
  290.     /*
  291.      * Get to the first byte.
  292.      */
  293.     bp += (r_off >> 3);
  294.     r_off &= 7;
  295.     /* Get first part (low order bits) */
  296. #ifdef NO_UCHAR
  297.     code = ((*bp++ >> r_off) & rmask[8 - r_off]) & 0xff;
  298. #else
  299.     code = (*bp++ >> r_off);
  300. #endif /* NO_UCHAR */
  301.     bits -= (8 - r_off);
  302.     r_off = 8 - r_off;        /* now, offset into code word */
  303.     /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  304.     if ( bits >= 8 ) {
  305. #ifdef NO_UCHAR
  306.     code |= (*bp++ & 0xff) << r_off;
  307. #else
  308.     code |= *bp++ << r_off;
  309. #endif /* NO_UCHAR */
  310.     r_off += 8;
  311.     bits -= 8;
  312.     }
  313.     /* high order bits. */
  314.     code |= (*bp & rmask[bits]) << r_off;
  315.     file->offset += file->n_bits;
  316.  
  317.     return code;
  318. }
  319.  
  320. CompressedFontFileRead (buf, itemsize, nitems, fid)
  321.     char    *buf;
  322.     unsigned    itemsize;
  323.     unsigned    nitems;
  324.     FID        fid;
  325. {
  326.     CompressedFile  *file;
  327.     int            c;
  328.     int            nbytes;
  329.  
  330.     file = (CompressedFile *) fid;
  331.     nbytes = nitems * itemsize;
  332.     while (nbytes)
  333.     {
  334.     if ((c = getdcchar (file)) == EOF)
  335.         break;
  336.     *buf++ = c;
  337.     --nbytes;
  338.     }
  339.     return nitems - nbytes / itemsize;
  340. }
  341.  
  342. CompressedFontFileSkip (bytes, fid)
  343.     unsigned    bytes;
  344.     FID        fid;
  345. {
  346.     int        c;
  347.  
  348.     while (bytes-- && ((c = getdcchar((CompressedFile *)fid)) != EOF))
  349.         ;
  350.     return c;
  351. }
  352.  
  353. #ifdef TEST
  354. main ()
  355. {
  356.     CompressedFile  *input;
  357.     int            c;
  358.     
  359.     input = (CompressedFile *) CompressedFontFileInit (stdin);
  360.     while ((c = getdcchar (input)) != -1)
  361.     putchar (c);
  362. }
  363. #endif
  364.