#define PBITS 16
#define BITS PBITS

unsigned       char magic_header[] = { 
       "\037\235" };   /* 1F 9D */

/* Defines for third byte of header */
#define BIT_MASK       0x1f
#define BLOCK_MASK     0x80
/* Masks 0x40 and 0x20 are free.  I think 0x20 should mean that there is
a fourth header byte (for expansion).
*/
#define INIT_BITS 9            /* initial number of bits/code */

#include <stdio.h>

int n_bits;                            /* number of bits/code */
int maxbits = BITS;                    /* user settable max # bits/code */
long   int maxcode;                    /* maximum code, given n_bits */
long   int maxmaxcode = 1 << BITS;     /* should NEVER generate this code */
# define MAXCODE(n_bits)       ((1 << (n_bits)) - 1)

/*
* One code could conceivably represent (1<<BITS) characters, but
* to get a code of length N requires an input string of at least
* N*(N-1)/2 characters.  With 5000 chars in the stack, an input
* file would have to contain a 25Mb string of a single character.
* This seems unlikely.
*/
# define MAXSTACK    8000              /* size of output stack */

unsigned short tab_prefix [69001];
unsigned       char    tab_suffix[1<<BITS];    /* last char in this entry */

long   int free_ent = 0;                       /* first unused entry */
int exit_stat = 0;

long   int getcode();

/*
* block compression parameters -- after all codes are used up,
* and compression rate changes, start over.
*/
int block_compress = BLOCK_MASK;
int clear_flg = 0;
/*
* the next two codes should not be changed lightly, as they must not
* lie within the contiguous general code space.
*/
#define FIRST  257     /* first free entry */
#define        CLEAR   256     /* table clear output code */

main()
{
       if(maxbits < INIT_BITS) maxbits = INIT_BITS;
       if (maxbits > BITS) maxbits = BITS;
       maxmaxcode = 1 << maxbits;

       exit_stat = 0;
       /* Check the magic number */
       if ((getchar() != (magic_header[0] & 0xFF))
           || (getchar() != (magic_header[1] & 0xFF))) {
               fprintf(stderr,"not in compressed format\n");
               exit(1);
       }
       maxbits = getchar();    /* set -b from file */
       block_compress = maxbits & BLOCK_MASK;
       maxbits &= BIT_MASK;
       maxmaxcode = 1 << maxbits;
       if(maxbits > BITS) {
               fprintf(stderr,
                   "compressed with %d bits, can only handle %d bits\n",
                   maxbits, BITS);
               exit(1);
       }
       decompress();
       exit(exit_stat);
}
unsigned       char rmask[9] = {
       0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
decompress() {
       register int stack_top = MAXSTACK;
       register long   int code, oldcode, incode;
       register int finchar;
       char stack[MAXSTACK];

       /*
* As above, initialize the first 256 entries in the table.
*/
       maxcode = MAXCODE(n_bits = INIT_BITS);
       for ( code = 255; code >= 0; code-- ) {
               tab_prefix[code] = 0;
               tab_suffix[code] = (unsigned    char)code;
       }
       free_ent = ((block_compress) ? FIRST : 256 );

       finchar = oldcode = getcode();
       putchar( (char)finchar );               /* first code must be 8 bits = char */

       while ( (code = getcode()) != -1 ) {

               if ( (code == CLEAR) && block_compress ) {
                       for ( code = 255; code > 0; code -= 4 ) {
                               tab_prefix [code-3] = 0;
                               tab_prefix [code-2] = 0;
                               tab_prefix [code-1] = 0;
                               tab_prefix [code] = 0;
                       }
                       clear_flg = 1;
                       free_ent = FIRST - 1;
                       if ( (code = getcode ()) == -1 )        /* O, untimely death! */
                               break;
               }
               incode = code;
               /*
* Special case for KwKwK string.
*/
               if ( code >= free_ent ) {
                       stack[--stack_top] = finchar;
                       code = oldcode;
               }

               /*
* Generate output characters in reverse order
*/
               while ( code >= 256 ) {
                       stack[--stack_top] = tab_suffix[code];
                       code = tab_prefix[code];
               }
               stack[--stack_top] = finchar = tab_suffix[code];

               /*
* And put them out in forward order
*/
               for ( ; stack_top < MAXSTACK; stack_top++ )
                       putchar(stack[stack_top]);
               if (ferror(stdout))
                       writeerr ( );
               stack_top = MAXSTACK;

               /*
* Generate the new entry.
*/
               if ( (code=free_ent) < maxmaxcode ) {
                       tab_prefix[code] = (unsigned short)oldcode;
                       tab_suffix[code] = finchar;
                       free_ent = code+1;
               }
               /*
* Remember previous code.
*/
               oldcode = incode;
       }
       fflush( stdout );
       if(ferror(stdout))
               writeerr();
}


/*****************************************************************
* TAG( getcode )
*
* Read one code from the standard input.  If EOF, return -1.
* Inputs:
*      stdin
* Outputs:
*      code or -1 is returned.
*/

long   int
getcode() {
       /*
* On the VAX, it is important to have the register declarations
* in exactly the order given, or the asm will break.
*/
       register long   int code;
       static int offset = 0, size = 0;
       static unsigned char buf[BITS];
       register int r_off, bits;
       register unsigned       char *bp = buf;

       if ( clear_flg > 0 || offset >= size || free_ent > maxcode ) {
               /*
* If the next entry will be too big for the current code
* size, then we must increase the size.  This implies reading
* a new buffer full, too.
*/
               if ( free_ent > maxcode ) {
                       n_bits++;
                       if ( n_bits == maxbits )
                               maxcode = maxmaxcode;   /* won't get any bigger now */
                       else
                               maxcode = MAXCODE(n_bits);
               }
               if ( clear_flg > 0) {
                       maxcode = MAXCODE (n_bits = INIT_BITS);
                       clear_flg = 0;
               }
               size = fread( buf, 1, n_bits, stdin );
               if ( size <= 0 )
                       return -1;                      /* end of file */
               offset = 0;
               /* Round size down to integral number of codes */
               size = (size << 3) - (n_bits - 1);
       }
       r_off = offset;
       bits = n_bits;
       /*
* Get to the first byte.
*/
       bp += (r_off >> 3);
       r_off &= 7;
       /* Get first part (low order bits) */
       code = (*bp++ >> r_off);
       bits -= (8 - r_off);
       r_off = 8 - r_off;              /* now, offset into code word */
       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
       if ( bits >= 8 ) {
               code |= *bp++ << r_off;
               r_off += 8;
               bits -= 8;
       }
       /* high order bits. */
       code |= (*bp & rmask[bits]) << r_off;
       offset += n_bits;

       return code;
}
/*****************************************************************
* TAG( writeerr )
*
* Exits with a message.  We only check for write errors often enough
* to avoid a lot of "file system full" messages, not on every write.
* ferror() check after fflush will catch any others (I trust).
*
*/

writeerr()
{
       exit ( 1 );
}