/*                          E X P A N D . C 
 *
 *  A file maintenance filter utility to EXPAND files compressed by the
 *  public domain COMPRESS v4.0 utility by Spencer W. Thomas, et al.
 *
 *  Algorithm from "A Technique for High Performance Data Compression",
 *  Terry A. Welch, IEEE Computer Vol 17, No 6 (June 1984), pp 8-19.
 *
 *  The impetus for this program comes from a desire to EXPAND files
 *  in an MS-DOS environment which have been COMPRESSed with 16 bit
 *  codes in UNIX(tm) or other environments.  Memory usage for this
 *  program is less than 250 kbytes for the full 16 bit case.
 *  The code uses many ANSI-C style contructs with no apologies.
 *-----------------------------------------------------------------------
 *  Author: Lyle V. Rains
 *      Based on the sources of COMPRESS.C v4.0 by Spencer Thomas, et al.
 *-----------------------------------------------------------------------
 *  Revision History:
 */

#define EXPAND
#include "expand.h"

CONST int Maxbits = MAXBITS;

static char FAR * sfx = NULLPTR(char);

#if (SPLIT_PFX)
  static CODE FAR *pfx[2] = {NULLPTR(CODE), NULLPTR(CODE)};
#else
  static CODE FAR *pfx = NULLPTR(CODE);
#endif


static int alloc_tables(maxcode)
  CODE maxcode;
{
  static CODE oldmaxcode = 0;
   if (maxcode > oldmaxcode) {
#   if (SPLIT_PFX)
      free_array(CODE, pfx[1], 128);
      free_array(CODE, pfx[0], 128);
#   else
      free_array(CODE, pfx, 256);
#   endif
    free_array(char, sfx, 256);
    if (   alloc_array(char, sfx, maxcode + 1, 256)
#     if (SPLIT_PFX)
        || alloc_array(CODE, pfx[0], (maxcode + 1) / 2, 128)
        || alloc_array(CODE, pfx[1], (maxcode + 1) / 2, 128)
#     else
        || alloc_array(CODE, pfx, maxcode + 1, 256)
#     endif
      )
    {
      oldmaxcode = 0;
      return (NOMEM);
    }
    oldmaxcode = maxcode;
  }
  DBG(("   sfx = 0x%lx\n", (long)sfx));
# if (SPLIT_PFX)
    DBG(("   pfx = {0x%lx,  0x%lx}\n", (long)pfx[0], (long)pfx[1]));
# else
    DBG(("   pfx = 0x%lx\n", (long)pfx));
# endif
  return (OK);
}



int expand(in, out, maxbits, clearmode)
  FILE *in;
  FILE *out;
  int maxbits;
  int clearmode;
{
  register int i;
  unsigned int bits;
  char sufxchar;
  register CODE code;
  CODE prefxcode, savecode;
  CODE nextfree, highcode, maxcode;
  int fulltable, cleartable;
  static char token[MAXTOKLEN];         /* String buffer to build token */
  static CODE tablesize = 0;

  
  alloc_tables(maxcode = ~(~(CODE)0 << maxbits));
  cleartable = YES;
  savecode = CLEAR;
  do {
    if ((code = savecode) == CLEAR && cleartable) {
      highcode = ~(~(CODE)0 << (bits = INITBITS));
      fulltable = NO;
      nextfree = (cleartable = clearmode) == NO ? 256 : FIRSTFREE;
      DBG(("table cleared\n"));
      if (!nextcode(in, &prefxcode, bits, highcode)) break;
      putc((sufxchar = (char)prefxcode), out);
      continue;
    }
    i = 0;
    if (code >= nextfree && !fulltable) {
      if (code != nextfree) return (CODEBAD);     /* Non-existant code */
      /* Special case for sequence KwKwK (see text of article)         */
      code = prefxcode;
      token[i++] = sufxchar;
    }
    /* Build the token string in reverse order by chasing down through
     * successive prefix tokens of the current token.  Then output it.
     */
    while (code >= 256) {
#     ifndef NDEBUG
        /* These are checks to ease paranoia. Prefix codes must decrease
         * monotonically, otherwise we must have corrupt tables.  We can
         * also check that we haven't overrun the token buffer.
         */
        if (code <= prefix(code)) return (TABLEBAD);
        if (i >= MAXTOKLEN) return (TOKTOOBIG);
#     endif
      token[i++] = suffix(code);
      code = prefix(code);
    }
    putc(sufxchar = (char)code, out);
    while (--i >= 0) putc(token[i], out);
    if (ferror(out)) return (WRITEERR);
    /* If table isn't full, add new token code to the table with
     * prefxcode and sufxchar, and remember current code.
     */
    if (!fulltable) {
      code = nextfree;
      assert(256 <= code && code <= maxcode);
      prefix(code) = prefxcode;
      suffix(code) = sufxchar;
      prefxcode = savecode;
      if (code++ == highcode) {
        if (highcode >= maxcode) {
          DBG(("table full\n"));
          fulltable = YES;
          --code;
        }
        else {
          ++bits;
          highcode += code;        /* code == highcode + 1 */
        }
      }
      nextfree = code;
    }
  } while (nextcode(in, &savecode, bits, highcode));
  return (ferror(in) ? READERR : OK);
}