/*
 * @(#) lzh.c - LZH compression routine.
 * (c) 1997 Ivan Maidanski <ivmai@chat.ru> http://ivmai.chat.ru
 * Freeware program source. All rights reserved.
 **
 * Language: ANSI C
 * Tested with: Watcom C16 v10.0
 * Last modified: 1997-06-09 18:45:00 GMT+04:00
 */

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

#define WINSIZELOG 12 /* >=11 */
#define WINSIZE (1<<WINSIZELOG) /* sliding window size */
#define LOOKSIZE 60 /* look-ahead string max size */
#define THRESHOLD 2 /* threshold size */

#define BLANKCHAR ' ' /* character for initial text buffer blanking */

#define NILLNODE WINSIZE
#define TREENODE (WINSIZE+1)

/* Huffman coding parameters */
#define NCHARCNT (UCHAR_MAX+1-THRESHOLD+LOOKSIZE) /* character code count */
#define TSIZE (NCHARCNT*2-1) /* table size */

#define MAXFREQ ((unsigned short)SHRT_MAX+1)
 /* update when cumulative frequency reaches to this value */

static unsigned char p_code[64]=
{
 0x00,0x02,0x04,0x0C,0x01,0x06,0x0A,0x0E,
 0x11,0x16,0x1A,0x1E,0x05,0x09,0x0D,0x15,
 0x19,0x1D,0x25,0x29,0x2D,0x35,0x39,0x3D,
 0x03,0x07,0x0B,0x13,0x17,0x1B,0x23,0x27,
 0x2B,0x33,0x37,0x3B,0x43,0x47,0x4B,0x53,
 0x57,0x5B,0x63,0x67,0x6B,0x73,0x77,0x7B,
 0x0F,0x1F,0x2F,0x3F,0x4F,0x5F,0x6F,0x7F,
 0x8F,0x9F,0xAF,0xBF,0xCF,0xDF,0xEF,0xFF
};

static unsigned char d_code[256]=
{
 0x00,0x04,0x01,0x18,0x02,0x0C,0x05,0x19,
 0x00,0x0D,0x06,0x1A,0x03,0x0E,0x07,0x30,
 0x00,0x08,0x01,0x1B,0x02,0x0F,0x09,0x1C,
 0x00,0x10,0x0A,0x1D,0x03,0x11,0x0B,0x31,
 0x00,0x04,0x01,0x1E,0x02,0x12,0x05,0x1F,
 0x00,0x13,0x06,0x20,0x03,0x14,0x07,0x32,
 0x00,0x08,0x01,0x21,0x02,0x15,0x09,0x22,
 0x00,0x16,0x0A,0x23,0x03,0x17,0x0B,0x33,
 0x00,0x04,0x01,0x24,0x02,0x0C,0x05,0x25,
 0x00,0x0D,0x06,0x26,0x03,0x0E,0x07,0x34,
 0x00,0x08,0x01,0x27,0x02,0x0F,0x09,0x28,
 0x00,0x10,0x0A,0x29,0x03,0x11,0x0B,0x35,
 0x00,0x04,0x01,0x2A,0x02,0x12,0x05,0x2B,
 0x00,0x13,0x06,0x2C,0x03,0x14,0x07,0x36,
 0x00,0x08,0x01,0x2D,0x02,0x15,0x09,0x2E,
 0x00,0x16,0x0A,0x2F,0x03,0x17,0x0B,0x37,
 0x00,0x04,0x01,0x18,0x02,0x0C,0x05,0x19,
 0x00,0x0D,0x06,0x1A,0x03,0x0E,0x07,0x38,
 0x00,0x08,0x01,0x1B,0x02,0x0F,0x09,0x1C,
 0x00,0x10,0x0A,0x1D,0x03,0x11,0x0B,0x39,
 0x00,0x04,0x01,0x1E,0x02,0x12,0x05,0x1F,
 0x00,0x13,0x06,0x20,0x03,0x14,0x07,0x3A,
 0x00,0x08,0x01,0x21,0x02,0x15,0x09,0x22,
 0x00,0x16,0x0A,0x23,0x03,0x17,0x0B,0x3B,
 0x00,0x04,0x01,0x24,0x02,0x0C,0x05,0x25,
 0x00,0x0D,0x06,0x26,0x03,0x0E,0x07,0x3C,
 0x00,0x08,0x01,0x27,0x02,0x0F,0x09,0x28,
 0x00,0x10,0x0A,0x29,0x03,0x11,0x0B,0x3D,
 0x00,0x04,0x01,0x2A,0x02,0x12,0x05,0x2B,
 0x00,0x13,0x06,0x2C,0x03,0x14,0x07,0x3E,
 0x00,0x08,0x01,0x2D,0x02,0x15,0x09,0x2E,
 0x00,0x16,0x0A,0x2F,0x03,0x17,0x0B,0x3F
};

static unsigned char p_len[64]=
{
 3,4,4,4,5,5,5,5,5,5,5,5,6,6,6,6,
 6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,
 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
};

static unsigned char d_len[16]=
{
 3,5,4,7,4,6,5,7,3,6,5,7,4,6,5,8
};

void inittree(unsigned int subtree[], unsigned int dad[])
{
 unsigned int i;
 for (i=0;i<=UCHAR_MAX;i++)
  subtree[i]=NILLNODE; /* root */
 for (i=0;i<WINSIZE;i++)
  dad[i]=NILLNODE; /* nodes */
}

unsigned short insertnode(unsigned char textbuf[], unsigned int subtree[],
                          unsigned int lson[], unsigned int rson[],
                          unsigned int eqson[], unsigned int dad[],
                          unsigned int pos, unsigned int *matchpos)
{
 int res;
 unsigned int curpos;
 unsigned short curlen,matchlen=0;
 *matchpos=NILLNODE;
 for (curpos=subtree[textbuf[pos]];curpos!=NILLNODE;
      curpos=res<0? lson[curpos] : rson[curpos])
 {
  *matchpos=curpos;
  res=textbuf[curpos+2]-textbuf[pos+2];
  if (!res)
   res=textbuf[curpos+1]-textbuf[pos+1];
  if (!res)
   break;
 }
 if (curpos==NILLNODE)
 {
  if (*matchpos==NILLNODE)
   subtree[textbuf[pos]]=pos;
   else (res<0? lson : rson)[*matchpos]=pos;
  lson[pos]=rson[pos]=eqson[pos]=NILLNODE;
  dad[pos]=*matchpos==NILLNODE? TREENODE : *matchpos;
  *matchpos=NILLNODE;
 }
  else
  {
   eqson[pos]=*matchpos;
   dad[pos]=dad[*matchpos];
   dad[*matchpos]=pos;
   if ((rson[pos]=rson[*matchpos])!=NILLNODE)
    dad[rson[pos]]=pos;
   if ((lson[pos]=lson[*matchpos])!=NILLNODE)
    dad[lson[pos]]=pos;
   if (dad[pos]==TREENODE)
    subtree[textbuf[pos]]=pos;
    else (rson[dad[pos]]==*matchpos? rson : lson)[dad[pos]]=pos;
   for (;curpos!=NILLNODE;curpos=eqson[curpos])
   {
    for (curlen=3;curlen<LOOKSIZE;curlen++)
     if (textbuf[curpos+curlen]!=textbuf[pos+curlen])
      break;
    if (matchlen<curlen)
    {
     *matchpos=curpos;
     matchlen=curlen;
    }
    if (curlen==LOOKSIZE)
     break;
   }
  }
 return (matchlen);
}

void deletenode(unsigned int subtree[],
                unsigned int lson[], unsigned int rson[],
                unsigned int eqson[], unsigned int dad[],
                unsigned int pos, unsigned char c)
{
 unsigned int q;
 if (dad[pos]!=NILLNODE)
  if (dad[pos]==TREENODE || eqson[dad[pos]]!=pos)
  {
   q=lson[pos];
   if (rson[pos]!=NILLNODE)
    if (q!=NILLNODE)
    {
     if (rson[q]!=NILLNODE)
     {
      do q=rson[q];
       while (rson[q]!=NILLNODE);
      dad[rson[dad[q]]=lson[q]]=dad[q];
      dad[lson[q]=lson[pos]]=q;
     }
     dad[rson[q]=rson[pos]]=q;
    }
     else q=rson[pos];
   dad[q]=dad[pos];
   if (dad[pos]==TREENODE)
    subtree[c]=q;
    else (rson[dad[pos]]==pos? rson : lson)[dad[pos]]=q;
   dad[pos]=NILLNODE;
  }
   else if ((q=eqson[dad[pos]]=eqson[pos])!=NILLNODE)
    dad[q]=dad[pos];
}

void huffstart(unsigned short freq[],
               unsigned short son[], unsigned short prnt[])
{
 unsigned short i,j;
 for (i=0;i<NCHARCNT;i++)
 {
  freq[i]=1;
  prnt[son[i]=i+TSIZE]=i;
 }
 for (j=NCHARCNT,i=0;j<TSIZE;j++,i+=2)
 {
  freq[j]=freq[i]+freq[i+1];
  son[j]=i;
  prnt[i]=prnt[i+1]=j;
 }
 prnt[TSIZE-1]=0;
}

void huffreconst(unsigned short freq[],
                 unsigned short son[], unsigned short prnt[])
{
 unsigned short i,j,k;
 unsigned short f;
 for (i=0,j=0;i<TSIZE;i++) /* halven cumulative freq for leaf nodes */
  if (son[i]>=TSIZE)
  {
   freq[j]=(freq[i]+1)/2;
   son[j]=son[i];
   j++;
  }
 for (j=NCHARCNT,i=0;j<TSIZE;j++,i+=2) /* connect children nodes */
 {
  f=freq[i]+freq[i+1];
  for (k=j;k>0;k--)
   if (f<freq[k-1])
   {
    freq[k]=freq[k-1];
    son[k]=son[k-1];
   }
    else break;
  freq[k]=f;
  son[k]=i;
 }
 for (i=0;i<TSIZE;i++) /* connect parent nodes */
 {
  prnt[k=son[i]]=i;
  if (k<TSIZE)
   prnt[k+1]=i;
 }
}

void huffupdate(unsigned short freq[], unsigned short son[],
                unsigned short prnt[], unsigned short nc)
{
 unsigned short i,j,k;
 unsigned short f;
 if (freq[TSIZE-1]==MAXFREQ)
  huffreconst(freq,son,prnt);
 nc=prnt[nc+TSIZE];
 do
 {
  f=++freq[nc]; /* swap nodes to keep the tree freq-ordered */
  for (k=nc;k<TSIZE-1;k++)
   if (f<=freq[k+1])
    break;
  if (k>nc)
  {
   freq[nc]=freq[k];
   freq[k]=f;
   prnt[i=son[nc]]=k;
   if (i<TSIZE)
    prnt[i+1]=k;
   j=son[k];
   son[k]=i;
   prnt[j]=nc;
   if (j<TSIZE)
    prnt[j+1]=nc;
   son[nc]=j;
   nc=k;
  }
  nc=prnt[nc];
 } while (nc);
}

void putcode(FILE *f, unsigned char *bitbuf, unsigned char *bitnum,
             unsigned int code, unsigned char len)
{
 *bitbuf|=code<<*bitnum;
 code>>=CHAR_BIT-*bitnum;
 for (*bitnum+=len;*bitnum>=CHAR_BIT;*bitnum-=CHAR_BIT)
 {
  putc(*bitbuf,f);
  *bitbuf=code;
  code>>=CHAR_BIT;
 }
}

unsigned int getcode(FILE *f, unsigned char *bitbuf, unsigned char *bitnum,
                     unsigned char len, short *eofflag)
{
 int c;
 unsigned int code;
 for (code=*bitbuf;*bitnum<len;
      code|=(unsigned int)*bitbuf<<*bitnum,*bitnum+=CHAR_BIT)
  if ((c=getc(f))!=EOF)
   *bitbuf=c;
   else break;
 if (!(*eofflag=*bitnum<len))
 {
  *bitbuf>>=len-(*bitnum>CHAR_BIT? *bitnum-CHAR_BIT : 0);
  *bitnum-=len;
 }
  else *bitbuf=*bitnum=0;
 return (code&((1<<len)-1));
}

void encodenchar(FILE *f, unsigned char *bitbuf, unsigned char *bitnum,
                 unsigned short freq[], unsigned short son[],
                 unsigned short prnt[], unsigned short nc)
{
 unsigned short k,len;
 unsigned int code;
 for (k=prnt[nc+TSIZE],code=0,len=0;k<TSIZE-1;k=prnt[k],len++)
  code=(code<<1) | (k&1);
 putcode(f,bitbuf,bitnum,code,len);
 huffupdate(freq,son,prnt,nc);
}

unsigned short decodenchar(FILE *f,
                           unsigned char *bitbuf, unsigned char *bitnum,
                           unsigned short freq[], unsigned short son[],
                           unsigned short prnt[], short *eofflag)
{
 unsigned short nc=son[TSIZE-1];
 while (nc<TSIZE)
  nc=son[nc+getcode(f,bitbuf,bitnum,1,eofflag)];
 huffupdate(freq,son,prnt,nc-TSIZE);
 return (nc-TSIZE);
}

void encodepos(FILE *f, unsigned char *bitbuf, unsigned char *bitnum,
               unsigned int pos)
{
 putcode(f,bitbuf,bitnum,
         p_code[pos>>(WINSIZELOG-6)],p_len[pos>>(WINSIZELOG-6)]);
 putcode(f,bitbuf,bitnum,pos&((1<<(WINSIZELOG-6))-1),WINSIZELOG-6);
}

unsigned int decodepos(FILE *f, unsigned char *bitbuf,
                       unsigned char *bitnum, short *eofflag)
{
 unsigned char code=getcode(f,bitbuf,bitnum,CHAR_BIT,eofflag);
 unsigned char len=d_len[code%16];
 return (((unsigned int)d_code[code]<<(WINSIZELOG-6)) | (code>>len) |
         ((unsigned int)getcode(f,bitbuf,bitnum,
          (WINSIZELOG-6)-(CHAR_BIT-len),eofflag)<<(CHAR_BIT-len)));
}

void encodeend(FILE *f, unsigned char *bitbuf, unsigned char *bitnum,
               unsigned short prnt[])
{
 unsigned short nc;
 unsigned short k,len;
 unsigned int code;
 if (*bitnum)
 {
  for (nc=0;nc<NCHARCNT;nc++)
  {
   for (k=prnt[nc+TSIZE],code=0,len=0;k<TSIZE-1;k=prnt[k],len++)
    code=(code<<1) | (k&1);
   if (len>CHAR_BIT-*bitnum)
    break;
  }
  putcode(f,bitbuf,bitnum,code,CHAR_BIT-*bitnum);
 }
}

void compress(FILE *fin, FILE *fout)
{
 int c;
 unsigned char bitbuf=0,bitnum=0;
 unsigned int curpos,oldpos,matchpos;
 unsigned short curlen,matchlen,len;
 unsigned char textbuf[WINSIZE+LOOKSIZE];
 unsigned short freq[TSIZE]; /* 1..MAXFREQ */
 unsigned short son[TSIZE]; /* 0..TSIZE+NCHARCNT */
 unsigned short prnt[TSIZE+NCHARCNT]; /* 0..TSIZE-1 */
 unsigned int subtree[UCHAR_MAX+1]; /* 0..WINSIZE */
 unsigned int lson[WINSIZE],rson[WINSIZE],eqson[WINSIZE]; /* 0..WINSIZE */
 unsigned int dad[WINSIZE+1]; /* 0..WINSIZE+1 */
 huffstart(freq,son,prnt);
 inittree(subtree,dad);
 for (oldpos=0;oldpos<WINSIZE;oldpos++)
  textbuf[oldpos]=BLANKCHAR;
 oldpos=0;
 curpos=WINSIZE-LOOKSIZE;
 for (len=0;len<LOOKSIZE && (c=getc(fin))!=EOF;len++)
  textbuf[curpos+len]=c;
 for (curlen=LOOKSIZE;curlen>0;curlen--)
  insertnode(textbuf,subtree,lson,rson,eqson,dad,curpos-curlen,&matchpos);
 matchlen=insertnode(textbuf,subtree,lson,rson,eqson,dad,curpos,&matchpos);
 while (len)
 {
  if (matchlen>len)
   matchlen=len;
  if (matchlen<=THRESHOLD)
  {
   encodenchar(fout,&bitbuf,&bitnum,freq,son,prnt,textbuf[curpos]);
   matchlen=1;
  }
   else
   {
    encodenchar(fout,&bitbuf,&bitnum,freq,son,prnt,
                UCHAR_MAX-THRESHOLD+matchlen);
    encodepos(fout,&bitbuf,&bitnum,(curpos-matchpos-1)%WINSIZE);
   }
  for (curlen=matchlen;curlen>0 && (c=getc(fin))!=EOF;
       curlen--,oldpos=(oldpos+1)%WINSIZE)
  {
   deletenode(subtree,lson,rson,eqson,dad,oldpos,textbuf[oldpos]);
   textbuf[oldpos]=c;
   if (oldpos<LOOKSIZE)
    textbuf[oldpos+WINSIZE]=c;
   curpos=(curpos+1)%WINSIZE;
   matchlen=insertnode(textbuf,subtree,lson,rson,eqson,dad,curpos,&matchpos);
  }
  for (;curlen>0;curlen--,oldpos=(oldpos+1)%WINSIZE,len--)
  {
   deletenode(subtree,lson,rson,eqson,dad,oldpos,textbuf[oldpos]);
   curpos=(curpos+1)%WINSIZE;
   matchlen=insertnode(textbuf,subtree,lson,rson,eqson,dad,curpos,&matchpos);
  }
 }
 encodeend(fout,&bitbuf,&bitnum,prnt);
}

void decompress(FILE *fin, FILE *fout)
{
 unsigned short nc;
 unsigned char bitbuf=0,bitnum=0;
 short eofflag;
 unsigned int curpos,oldpos;
 unsigned char textbuf[WINSIZE];
 unsigned short freq[TSIZE]; /* 1..MAXFREQ */
 unsigned short son[TSIZE]; /* 0..TSIZE+NCHARCNT */
 unsigned short prnt[TSIZE+NCHARCNT]; /* 0..TSIZE-1 */
 huffstart(freq,son,prnt);
 for (oldpos=0;oldpos<WINSIZE;oldpos++)
  textbuf[oldpos]=BLANKCHAR;
 curpos=WINSIZE-LOOKSIZE;
 for (;;)
 {
  nc=decodenchar(fin,&bitbuf,&bitnum,freq,son,prnt,&eofflag);
  if (eofflag)
   break;
  if (nc<=UCHAR_MAX)
  {
   putc(textbuf[curpos]=nc,fout);
   curpos=(curpos+1)%WINSIZE;
  }
   else for (nc-=UCHAR_MAX-THRESHOLD,
             oldpos=curpos-decodepos(fin,&bitbuf,&bitnum,&eofflag)-1;
             nc;nc--,curpos=(curpos+1)%WINSIZE,oldpos++)
    putc(textbuf[curpos]=textbuf[oldpos%WINSIZE],fout);
 }
}

int main(int argc, char *argv[])
{
 FILE *fin,*fout;
 if (argc<4)
 {
  puts("Usage parameters: E/D <source_file> <target_file>");
  return (1);
 }
 if (!(fin=fopen(argv[2],"rb")))
 {
  puts("Error: cannot open source file!");
  return (2);
 }
 if (!(fout=fopen(argv[3],"wb")))
 {
  fclose(fin);
  puts("Error: cannot open target file!");
  return (2);
 }
 if (argv[1][0]!='D' && argv[1][0]!='d')
  compress(fin,fout);
  else decompress(fin,fout);
 fclose(fin);
 fclose(fout);
 return (0);
}