home *** CD-ROM | disk | FTP | other *** search
/ Resource Library: Multimedia / Resource Library: Multimedia.iso / archvrs / msdos / comp430 / source / compapi.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-18  |  22.7 KB  |  685 lines
  1. /*@H************************ < COMPRESS API    > ****************************
  2. *   $@(#) compapi.c,v 4.3d 90/01/18 03:00:00 don Release ^                  *
  3. *                                                                           *
  4. *   compress : compapi.c  <current version of compress algorithm>           *
  5. *                                                                           *
  6. *   port by  : Donald J. Gloistein                                          *
  7. *                                                                           *
  8. *   Source, Documentation, Object Code:                                     *
  9. *   released to Public Domain.  This code is based on code as documented    *
  10. *   below in release notes.                                                 *
  11. *                                                                           *
  12. *---------------------------  Module Description  --------------------------*
  13. *   Contains source code for modified Lempel-Ziv method (LZW) compression   *
  14. *   and decompression.                                                      *
  15. *                                                                           *
  16. *   This code module can be maintained to keep current on releases on the   *
  17. *   Unix system. The command shell and dos modules can remain the same.     *
  18. *                                                                           *
  19. *--------------------------- Implementation Notes --------------------------*
  20. *                                                                           *
  21. *   compiled with : compress.h compress.fns compress.c                      *
  22. *   linked with   : compress.obj compusi.obj                                *
  23. *                                                                           *
  24. *   problems:                                                               *
  25. *                                                                           *
  26. *                                                                           *
  27. *   CAUTION: Uses a number of defines for access and speed. If you change   *
  28. *            anything, make sure about side effects.                        *
  29. *                                                                           *
  30. * Compression:                                                              *
  31. * Algorithm:  use open addressing double hashing (no chaining) on the       *
  32. * prefix code / next character combination.  We do a variant of Knuth's     *
  33. * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime     *
  34. * secondary probe.  Here, the modular division first probe is gives way     *
  35. * to a faster exclusive-or manipulation.                                    *
  36. * Also block compression with an adaptive reset was used in original code,  *
  37. * whereby the code table is cleared when the compression ration decreases   *
  38. * but after the table fills.  This was removed from this edition. The table *
  39. * is re-sized at this point when it is filled , and a special CLEAR code is *
  40. * generated for the decompressor. This results in some size difference from *
  41. * straight version 4.0 joe Release. But it is fully compatible in both v4.0 *
  42. * and v4.01                                                                 *
  43. *                                                                           *
  44. * Decompression:                                                            *
  45. * This routine adapts to the codes in the file building the "string" table  *
  46. * on-the-fly; requiring no table to be stored in the compressed file.  The  *
  47. * tables used herein are shared with those of the compress() routine.       *
  48. *                                                                           *
  49. *     Initials ---- Name ---------------------------------                  *
  50. *      DjG          Donald J. Gloistein, current port to MsDos 16 bit       *
  51. *                   Plus many others, see rev.hst file for full list        *
  52. *      LvR          Lyle V. Rains, many thanks for improved implementation  *
  53. *                   of the compression and decompression routines.          *
  54. *************************************************************************@H*/
  55.  
  56. #include <stdio.h>
  57.  
  58. #include "compress.h" /* contains the rest of the include file declarations */
  59.  
  60. static int offset;
  61. static long int in_count ;         /* length of input */
  62. static long int bytes_out;         /* length of compressed output */
  63.  
  64. static INTCODE prefxcode, nextfree;
  65. static INTCODE highcode;
  66. static INTCODE maxcode;
  67. static HASH hashsize;
  68. static int  bits;
  69.  
  70.  
  71. /*
  72.  * The following two parameter tables are the hash table sizes and
  73.  * maximum code values for various code bit-lengths.  The requirements
  74.  * are that Hashsize[n] must be a prime number and Maxcode[n] must be less
  75.  * than Maxhash[n].  Table occupancy factor is (Maxcode - 256)/Maxhash.
  76.  * Note:  I am using a lower Maxcode for 16-bit codes in order to
  77.  * keep the hash table size less than 64k entries.
  78.  */
  79. CONST HASH hs[] = {
  80.   0x13FF,       /* 12-bit codes, 75% occupancy */
  81.   0x26C3,       /* 13-bit codes, 80% occupancy */
  82.   0x4A1D,       /* 14-bit codes, 85% occupancy */
  83.   0x8D0D,       /* 15-bit codes, 90% occupancy */
  84.   0xFFD9        /* 16-bit codes, 94% occupancy, 6% of code values unused */
  85. };
  86. #define Hashsize(maxb) (hs[(maxb) -MINBITS])
  87.  
  88. CONST INTCODE mc[] = {
  89.   0x0FFF,       /* 12-bit codes */
  90.   0x1FFF,       /* 13-bit codes */
  91.   0x3FFF,       /* 14-bit codes */
  92.   0x7FFF,       /* 15-bit codes */
  93.   0xEFFF        /* 16-bit codes, 6% of code values unused */
  94. };
  95. #define Maxcode(maxb) (mc[(maxb) -MINBITS])
  96.  
  97. #ifdef __STDC__
  98. #ifdef DEBUG
  99. #define allocx(type, ptr, size) \
  100.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  101.     ?   (fprintf(stderr,"%s: "#ptr" -- ", prog_name), NOMEM) : OK \
  102.     )
  103. #else
  104. #define allocx(type,ptr,size) \
  105.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  106.     ? NOMEM : OK \
  107.     )
  108. #endif
  109. #else
  110. #define allocx(type,ptr,size) \
  111.     (((ptr) = (type FAR *) emalloc((unsigned int)(size),sizeof(type))) == NULLPTR(type) \
  112.     ? NOMEM : OK \
  113.     )
  114. #endif
  115.  
  116. #define free_array(type,ptr,offset) \
  117.     if (ptr != NULLPTR(type)) { \
  118.         efree((ALLOCTYPE FAR *)((ptr) + (offset))); \
  119.         (ptr) = NULLPTR(type); \
  120.     }
  121.  
  122.   /*
  123.    * Macro to allocate new memory to a pointer with an offset value.
  124.    */
  125. #define alloc_array(type, ptr, size, offset) \
  126.     ( allocx(type, ptr, (size) - (offset)) != OK \
  127.       ? NOMEM \
  128.       : (((ptr) -= (offset)), OK) \
  129.     )
  130.  
  131. static char FAR *sfx = NULLPTR(char) ;
  132. #define suffix(code)     sfx[code]
  133.  
  134.  
  135. #if (SPLIT_PFX)
  136.   static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
  137. #else
  138.   static CODE FAR *pfx = NULLPTR(CODE);
  139. #endif
  140.  
  141.  
  142. #if (SPLIT_HT)
  143.   static CODE FAR *ht[2] = {NULLPTR(CODE),NULLPTR(CODE)};
  144. #else
  145.   static CODE FAR *ht = NULLPTR(CODE);
  146. #endif
  147.  
  148.  
  149. int alloc_tables(maxcode, hashsize)
  150.   INTCODE maxcode;
  151.   HASH hashsize;
  152. {
  153.   static INTCODE oldmaxcode = 0;
  154.   static HASH oldhashsize = 0;
  155.  
  156.   if (hashsize > oldhashsize) {
  157. #if (SPLIT_HT)
  158.       free_array(CODE,ht[1], 0);
  159.       free_array(CODE,ht[0], 0);
  160. #else
  161.       free_array(CODE,ht, 0);
  162. #endif
  163.     oldhashsize = 0;
  164.   }
  165.  
  166.     if (maxcode > oldmaxcode) {
  167. #if (SPLIT_PFX)
  168.         free_array(CODE,pfx[1], 128);
  169.         free_array(CODE,pfx[0], 128);
  170. #else
  171.         free_array(CODE,pfx, 256);
  172. #endif
  173.         free_array(char,sfx, 256);
  174.  
  175.         if (   alloc_array(char, sfx, maxcode + 1, 256)
  176. #if (SPLIT_PFX)
  177.             || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
  178.             || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
  179. #else
  180.             || alloc_array(CODE, pfx, (maxcode + 1), 256)
  181. #endif
  182.         ) {
  183.             oldmaxcode = 0;
  184.             exit_stat = NOMEM;
  185.             return(NOMEM);
  186.         }
  187.         oldmaxcode = maxcode;
  188.     }
  189.     if (hashsize > oldhashsize) {
  190.         if (
  191. #if (SPLIT_HT)
  192.             alloc_array(CODE, ht[0], (hashsize / 2) + 1, 0)
  193.             || alloc_array(CODE, ht[1], hashsize / 2, 0)
  194. #else
  195.             alloc_array(CODE, ht, hashsize, 0)
  196. #endif
  197.         ) {
  198.             oldhashsize = 0;
  199.             exit_stat = NOMEM;
  200.             return(NOMEM);
  201.         }
  202.         oldhashsize = hashsize;
  203.     }
  204.     return (OK);
  205. }
  206.  
  207. # if (SPLIT_PFX)
  208.     /*
  209.      * We have to split pfx[] table in half,
  210.      * because it's potentially larger than 64k bytes.
  211.      */
  212. #   define prefix(code)   (pfx[(code) & 1][(code) >> 1])
  213. # else
  214.     /*
  215.      * Then pfx[] can't be larger than 64k bytes,
  216.      * or we don't care if it is, so we don't split.
  217.      */
  218. #   define prefix(code) (pfx[code])
  219. # endif
  220.  
  221.  
  222. /* The initializing of the tables can be done quicker with memset() */
  223. /* but this way is portable through out the memory models.          */
  224. /* If you use Microsoft halloc() to allocate the arrays, then       */
  225. /* include the pragma #pragma function(memset)  and make sure that  */
  226. /* the length of the memory block is not greater than 64K.          */
  227. /* This also means that you MUST compile in a model that makes the  */
  228. /* default pointers to be far pointers (compact or large models).   */
  229. /* See the file COMPUSI.DOS to modify function emalloc().           */
  230.  
  231. # if (SPLIT_HT)
  232.     /*
  233.      * We have to split ht[] hash table in half,
  234.      * because it's potentially larger than 64k bytes.
  235.      */
  236. #   define probe(hash)    (ht[(hash) & 1][(hash) >> 1])
  237. #   define init_tables() \
  238.     { \
  239.       hash = hashsize >> 1; \
  240.       ht[0][hash] = 0; \
  241.       while (hash--) ht[0][hash] = ht[1][hash] = 0; \
  242.       highcode = ~(~(INTCODE)0 << (bits = INITBITS)); \
  243.       nextfree = (block_compress ? FIRSTFREE : 256); \
  244.     }
  245.  
  246. # else
  247.  
  248.     /*
  249.      * Then ht[] can't be larger than 64k bytes,
  250.      * or we don't care if it is, so we don't split.
  251.      */
  252. #   define probe(hash) (ht[hash])
  253. #   define init_tables() \
  254.     { \
  255.       hash = hashsize; \
  256.       while (hash--) ht[hash] = 0; \
  257.       highcode = ~(~(INTCODE)0 << (bits = INITBITS)); \
  258.       nextfree = (block_compress ? FIRSTFREE : 256); \
  259.     }
  260.  
  261. # endif
  262.  
  263. #ifdef COMP40
  264. /* table clear for block compress */
  265. /* this is for adaptive reset present in version 4.0 joe release */
  266. /* DjG, sets it up and returns TRUE to compress and FALSE to not compress */
  267. int cl_block ()     
  268. {
  269.     register long int rat;
  270.  
  271.     checkpoint = in_count + CHECK_GAP;
  272. #ifdef DEBUG
  273.     if ( debug ) {
  274.         fprintf ( stderr, "count: %ld, ratio: ", in_count );
  275.         prratio ( stderr, in_count, bytes_out );
  276.         fprintf ( stderr, "\n");
  277.     }
  278. #endif
  279.  
  280.     if(in_count > 0x007fffff) {    /* shift will overflow */
  281.         rat = bytes_out >> 8;
  282.         if(rat == 0)       /* Don't divide by zero */
  283.             rat = 0x7fffffff;
  284.         else
  285.             rat = in_count / rat;
  286.     }
  287.     else
  288.         rat = (in_count << 8) / bytes_out;  /* 8 fractional bits */
  289.  
  290.     if ( rat > ratio ){
  291.         ratio = rat;
  292.         return FALSE;
  293.     }
  294.     else {
  295.         ratio = 0;
  296. #ifdef DEBUG
  297.         if(debug)
  298.             fprintf ( stderr, "clear\n" );
  299. #endif
  300.         return TRUE;    /* clear the table */
  301.     }
  302.     return FALSE; /* don't clear the table */
  303. }
  304. #endif
  305.  
  306. /*
  307.  * compress stdin to stdout
  308.  *
  309.  */
  310. void compress()
  311. {
  312.     int c,adjbits;
  313.     register HASH hash;
  314.     register INTCODE code;
  315.     HASH hashf[256];
  316.  
  317.     maxcode = Maxcode(maxbits);
  318.     hashsize = Hashsize(maxbits);
  319.  
  320. #ifdef COMP40
  321. /* Only needed for adaptive reset */
  322.     checkpoint = CHECK_GAP;
  323.     ratio = 0;
  324. #endif
  325.  
  326.     adjbits = maxbits -10;
  327.     for (c = 256; --c >= 0; ){
  328.         hashf[c] = ((( c &0x7) << 7) ^ c) << adjbits;
  329.     }
  330.     exit_stat = OK;
  331.     if (alloc_tables(maxcode, hashsize))  /* exit_stat already set */
  332.         return;
  333.     init_tables();
  334.     /* if not zcat or filter */
  335.     if(is_list && !zcat_flg) {  /* Open output file */
  336.         if (freopen(ofname, WRITE_FILE_TYPE, stdout) == NULL) {
  337.             exit_stat = NOTOPENED;
  338.             return;
  339.         }
  340.         if (!quiet)
  341.             fprintf(stderr, "%s: ",ifname);
  342.         setvbuf(stdout,zbuf,_IOFBF,ZBUFSIZE);
  343.     }
  344.  /*
  345.    * Check the input stream for previously seen strings.  We keep
  346.    * adding characters to the previously seen prefix string until we
  347.    * get a character which forms a new (unseen) string.  We then send
  348.    * the code for the previously seen prefix string, and add the new
  349.    * string to our tables.  The check for previous strings is done by
  350.    * hashing.  If the code for the hash value is unused, then we have
  351.    * a new string.  If the code is used, we check to see if the prefix
  352.    * and suffix values match the current input; if so, we have found
  353.    * a previously seen string.  Otherwise, we have a hash collision,
  354.    * and we try secondary hash probes until we either find the current
  355.    * string, or we find an unused entry (which indicates a new string).
  356.    */
  357.     if (!nomagic) {
  358.         putchar(magic_header[0]); putchar(magic_header[1]);
  359.         putchar((char)(maxbits | block_compress));
  360.         if(ferror(stdout)){  /* check it on entry */
  361.             exit_stat = WRITEERR;
  362.             return;
  363.         }
  364.         bytes_out = 3L;     /* includes 3-byte header mojo */
  365.     }
  366.     else
  367.         bytes_out = 0L;      /* no 3-byte header mojo */
  368.     in_count = 1L;
  369.     offset = 0;
  370.  
  371.     if ((c = getchar()) == EOF) {
  372.         exit_stat = ferror(stdin) ? READERR : OK;
  373.         return;
  374.     }
  375.     prefxcode = (INTCODE)c;
  376.  
  377.     while ((c = getchar()) != EOF) {
  378.         in_count++;
  379.         hash = prefxcode ^ hashf[c];
  380.         /* I need to check that my hash value is within range
  381.         * because my 16-bit hash table is smaller than 64k.
  382.         */
  383.         if (hash >= hashsize)
  384.             hash -= hashsize;
  385.         if ((code = (INTCODE)probe(hash)) != UNUSED) {
  386.             if (suffix(code) != (char)c || (INTCODE)prefix(code) != prefxcode) {
  387.             /* hashdelta is subtracted from hash on each iteration of
  388.             * the following hash table search loop.  I compute it once
  389.             * here to remove it from the loop.
  390.             */
  391.                 HASH hashdelta = (0x120 - c) << (adjbits);
  392.                 do  {
  393.                     /* rehash and keep looking */
  394.                     assert(code >= FIRSTFREE && code <= maxcode);
  395.                     if (hash >= hashdelta) hash -= hashdelta;
  396.                         else hash += (hashsize - hashdelta);
  397.                     assert(hash < hashsize);
  398.                     if ((code = (INTCODE)probe(hash)) == UNUSED)
  399.                         goto newcode;
  400.                 } while (suffix(code) != (char)c || (INTCODE)prefix(code) != prefxcode);
  401.             }
  402.             prefxcode = code;
  403.         }
  404.         else {
  405.             newcode: {
  406.                 putcode(prefxcode, bits);
  407.                 code = nextfree;
  408.                 assert(hash < hashsize);
  409.                 assert(code >= FIRSTFREE);
  410.                 assert(code <= maxcode + 1);
  411.                 if (code <= maxcode) {
  412.                     probe(hash) = (CODE)code;
  413.                     prefix(code) = (CODE)prefxcode;
  414.                     suffix(code) = (char)c;
  415.                     if (code > highcode) {
  416.                         highcode += code;
  417.                         ++bits;
  418.                     }
  419.                     nextfree = code + 1;
  420.                 }
  421. #ifdef COMP40
  422.                 else if (in_count >= checkpoint && block_compress ) {
  423.                     if (cl_block()){
  424. #else
  425.                 else if (block_compress){
  426. #endif
  427.                         putcode((INTCODE)c, bits);
  428.                         putcode(CLEAR, bits);
  429.                         init_tables();
  430.                         if ((c = getchar()) == EOF)
  431.                             break;
  432.                         in_count++;
  433. #ifdef COMP40
  434.                     }
  435. #endif
  436.                 }
  437.                 prefxcode = (INTCODE)c;
  438.             }
  439.         }
  440.     }
  441.     putcode(prefxcode, bits);
  442.     putcode(CLEAR, 0);
  443.     if (ferror(stdout)){ /* check it on exit */
  444.         exit_stat = WRITEERR;
  445.         return;
  446.     }
  447.     /*
  448.      * Print out stats on stderr
  449.      */
  450.     if(zcat_flg == 0 && !quiet) {
  451. #ifdef DEBUG
  452.         fprintf( stderr,
  453.             "%ld chars in, (%ld bytes) out, compression factor: ",
  454.             in_count, bytes_out );
  455.         prratio( stderr, in_count, bytes_out );
  456.         fprintf( stderr, "\n");
  457.         fprintf( stderr, "\tCompression as in compact: " );
  458.         prratio( stderr, in_count-bytes_out, in_count );
  459.         fprintf( stderr, "\n");
  460.         fprintf( stderr, "\tLargest code (of last block) was %d (%d bits)\n",
  461.             prefxcode - 1, bits );
  462. #else
  463.         fprintf( stderr, "Compression: " );
  464.         prratio( stderr, in_count-bytes_out, in_count );
  465. #endif /* DEBUG */
  466.     }
  467.     if(bytes_out > in_count)      /*  if no savings */
  468.         exit_stat = NOSAVING;
  469.     return ;
  470. }
  471.  
  472. CONST UCHAR rmask[9] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff};
  473.  
  474. void putcode(code,bits)
  475.   INTCODE code;
  476.   register int bits;
  477. {
  478.   static int oldbits = 0;
  479.   static UCHAR outbuf[MAXBITS];
  480.   register UCHAR *buf;
  481.   register int shift;
  482.  
  483.   if (bits != oldbits) {
  484.     if (bits == 0) {
  485.       /* bits == 0 means EOF, write the rest of the buffer. */
  486.       if (offset > 0) {
  487.           fwrite(outbuf,1,(offset +7) >> 3, stdout);
  488.           bytes_out += ((offset +7) >> 3);
  489.       }
  490.       offset = 0;
  491.       oldbits = 0;
  492.       fflush(stdout);
  493.       return;
  494.     }
  495.     else {
  496.       /* Change the code size.  We must write the whole buffer,
  497.        * because the expand side won't discover the size change
  498.        * until after it has read a buffer full.
  499.        */
  500.       if (offset > 0) {
  501.         fwrite(outbuf, 1, oldbits, stdout);
  502.         bytes_out += oldbits;
  503.         offset = 0;
  504.       }
  505.       oldbits = bits;
  506. #ifdef DEBUG
  507.       if ( debug )
  508.         fprintf( stderr, "\nChange to %d bits\n", bits );
  509. #endif /* DEBUG */
  510.     }
  511.   }
  512.   /*  Get to the first byte. */
  513.   buf = outbuf + ((shift = offset) >> 3);
  514.   if ((shift &= 7) != 0) {
  515.     *(buf) |= (*buf & rmask[shift]) | (UCHAR)(code << shift);
  516.     *(++buf) = (UCHAR)(code >> (8 - shift));
  517.     if (bits + shift > 16)
  518.         *(++buf) = (UCHAR)(code >> (16 - shift));
  519.   }
  520.   else {
  521.     /* Special case for fast execution */
  522.     *(buf) = (UCHAR)code;
  523.     *(++buf) = (UCHAR)(code >> 8);
  524.   }
  525.   if ((offset += bits) == (bits << 3)) {
  526.     bytes_out += bits;
  527.     fwrite(outbuf,1,bits,stdout);
  528.     offset = 0;
  529.   }
  530.   return;
  531. }
  532.  
  533. int nextcode(codeptr)
  534.   INTCODE *codeptr;
  535. /* Get the next code from input and put it in *codeptr.
  536.  * Return (TRUE) on success, or return (FALSE) on end-of-file.
  537.  * Adapted from COMPRESS V4.0.
  538.  */
  539. {
  540.   static int prevbits = 0;
  541.   register INTCODE code;
  542.   static int size;
  543.   static UCHAR inbuf[MAXBITS];
  544.   register int shift;
  545.   UCHAR *bp;
  546.  
  547.   /* If the next entry is a different bit-size than the preceeding one
  548.    * then we must adjust the size and scrap the old buffer.
  549.    */
  550.   if (prevbits != bits) {
  551.     prevbits = bits;
  552.     size = 0;
  553.   }
  554.   /* If we can't read another code from the buffer, then refill it.
  555.    */
  556.   if (size - (shift = offset) < bits) {
  557.     /* Read more input and convert size from # of bytes to # of bits */
  558.     if ((size = fread(inbuf, 1, bits, stdin) << 3) <= 0 || ferror(stdin))
  559.       return(NO);
  560.     offset = shift = 0;
  561.   }
  562.   /* Get to the first byte. */
  563.   bp = inbuf + (shift >> 3);
  564.   /* Get first part (low order bits) */
  565.   code = (*bp++ >> (shift &= 7));
  566.   /* high order bits. */
  567.   code |= *bp++ << (shift = 8 - shift);
  568.   if ((shift += 8) < bits) code |= *bp << shift;
  569.   *codeptr = code & highcode;
  570.   offset += bits;
  571.   return (TRUE);
  572. }
  573.  
  574. void decompress()
  575. {
  576.   register int i;
  577.   register INTCODE code;
  578.   char sufxchar;
  579.   INTCODE savecode;
  580.   FLAG fulltable, cleartable;
  581.   static char *token= NULL;         /* String buffer to build token */
  582.   static int maxtoklen = MAXTOKLEN;
  583.  
  584.   exit_stat = OK;
  585.  
  586.   /* Initialze the token buffer. */
  587.     if (token == NULL && (token = (char*)malloc(maxtoklen)) == NULL) {
  588.             exit_stat = NOMEM;
  589.             return;
  590.     }
  591.  
  592.   if (alloc_tables(maxcode = ~(~(INTCODE)0 << maxbits),0)) /* exit_stat already set */
  593.      return;
  594.  
  595.     /* if not zcat or filter */
  596.     if(is_list && !zcat_flg) {  /* Open output file */
  597.         if (freopen(ofname, WRITE_FILE_TYPE, stdout) == NULL) {
  598.             exit_stat = NOTOPENED;
  599.             return;
  600.         }
  601.         if (!quiet)
  602.             fprintf(stderr, "%s: ",ifname);
  603.         setvbuf(stdout,xbuf,_IOFBF,XBUFSIZE);
  604.     }
  605.   cleartable = TRUE;
  606.   savecode = CLEAR;
  607.   offset = 0;
  608.   do {
  609.     if ((code = savecode) == CLEAR && cleartable) {
  610.       highcode = ~(~(INTCODE)0 << (bits = INITBITS));
  611.       fulltable = FALSE;
  612.       nextfree = (cleartable = block_compress) == FALSE ? 256 : FIRSTFREE;
  613.       if (!nextcode(&prefxcode))
  614.         break;
  615.       putc((sufxchar = (char)prefxcode), stdout);
  616.       continue;
  617.     }
  618.     i = 0;
  619.     if (code >= nextfree && !fulltable) {
  620.       if (code != nextfree){
  621.         exit_stat = CODEBAD;
  622.         return ;     /* Non-existant code */
  623.     }
  624.       /* Special case for sequence KwKwK (see text of article)         */
  625.       code = prefxcode;
  626.       token[i++] = sufxchar;
  627.     }
  628.     /* Build the token string in reverse order by chasing down through
  629.      * successive prefix tokens of the current token.  Then output it.
  630.      */
  631.     while (code >= 256) {
  632. #     ifdef DEBUG
  633.         /* These are checks to ease paranoia. Prefix codes must decrease
  634.          * monotonically, otherwise we must have corrupt tables.  We can
  635.          * also check that we haven't overrun the token buffer.
  636.          */
  637.         if (code <= (INTCODE)prefix(code)){
  638.             exit_stat= TABLEBAD;
  639.             return;
  640.         }
  641. #     endif
  642.       if (i >= maxtoklen) {
  643.         maxtoklen *= 2;   /* double the size of the token buffer */
  644.         if ((token = realloc(token, maxtoklen)) == NULL) {
  645.           exit_stat = TOKTOOBIG;
  646.           return;
  647.         }
  648.       }
  649.       token[i++] = suffix(code);
  650.       code = (INTCODE)prefix(code);
  651.     }
  652.     putc(sufxchar = (char)code, stdout);
  653.     while (--i >= 0)
  654.         putc(token[i], stdout);
  655.     if (ferror(stdout)) {
  656.         exit_stat = WRITEERR;
  657.         return;
  658.     }
  659.     /* If table isn't full, add new token code to the table with
  660.      * codeprefix and codesuffix, and remember current code.
  661.      */
  662.     if (!fulltable) {
  663.       code = nextfree;
  664.       assert(256 <= code && code <= maxcode);
  665.       prefix(code) = (CODE)prefxcode;
  666.       suffix(code) = sufxchar;
  667.       prefxcode = savecode;
  668.       if (code++ == highcode) {
  669.         if (highcode >= maxcode) {
  670.           fulltable = TRUE;
  671.           --code;
  672.         }
  673.         else {
  674.           ++bits;
  675.           highcode += code;           /* nextfree == highcode + 1 */
  676.         }
  677.       }
  678.       nextfree = code;
  679.     }
  680.   } while (nextcode(&savecode));
  681.   exit_stat = (ferror(stdin))? READERR : OK;
  682.   return ;
  683. }
  684.  
  685.