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