/*********** Dynamische Lempel-Ziv-Welch Datacompressie **************/
/* Programma compexp.c                                               */
/* Overgenomen uit Duitse Chip, December 1990, nr. 12                */
/* Met dank aan dr. F. Bauern”ppel.                                  */


#include <stdio.h>

/*********** Codetabel (voor Compressie en Expansie ******************/
#define size       0x0fff            /* Tabel grootte (12 bit codes) */

int            prefix[size+1];       /* Verwijs naar string-prefix   */
unsigned char    tail[size+1];       /* Laatste byte in de string    */

int               freepos=256;       /* Geldige invoer:              */
                                     /* 0..255:  vaste invoer (bytes)*/
                                     /* 256..freepos-1: dynamische
                                                             invoer  */


/************* Hashtabel (Compressor) ********************************/

#define hashmod     0x3fff           /* Hashtabelgrootte             */
#define empty           -1           /* Teken voor "niet bezet"      */

int       htab[hashmod+1];           /* Hashtabel, voor compressie   */

#define hash(i,x)  (((i<<3)^x) & hashmod)
                                     /* Hashfunctie                  */

void InitHash(void)
{ int i;
  for (i=0; i<=hashmod; htab[i++]=empty);
  freepos=256;
}


/****************** Code in- en uitvoer ******************************/

long ibits=-8, obits=0, reset=0;     /* Grootte voor de statistiek   */

FILE *fin, *fout;

int codelength=9;                    /* werkelijke bitlengte voor een
							        code */

unsigned long putbuffer;             /* uitvoerbuffer                */
int putbits=0;                       /* vullingsgraad uitvoerbuffer  */

void PutCode(int k)          /* Compressor: Code schrijven 9..12 bits*/
{
 if      (freepos==0x101) codelength=9;   /* codelengte omschakelen  */
 else if (freepos==0x201) codelength=10;  /* in afhankelijkheid van  */
 else if (freepos==0x401) codelength=11;  /* freepos                 */
 else if (freepos==0x801) codelength=12;
 putbuffer=(putbuffer<<codelength) | k;   /* codebits toevoegen      */
 putbits+=codelength;
 obits+=codelength;
 while (putbits>=8)  {
        putbits-=8;
        putc(0xff & (putbuffer>>putbits),fout); /* wegschrijven      */
 }
}

void FlushCode(void)                    /* schrijf laatste 1..7 bits */
{
 if (putbits) putc(putbuffer<<(8-putbits),fout);
}

#define _eof        0x7fff              /* end of file teken         */

unsigned long getbuffer;                /* invoerbuffer              */
int getbits=0;                          /* vullingsgraad invoerbuffer*/
unsigned GetCode(void)         /* Expansie: code lezen  (9..12 bits) */
{ int x;
 if      (freepos==0x100) codelength=9;   /* codelengte omschakelen  */
 else if (freepos==0x200) codelength=10;  /* in afhankelijkheid van  */
 else if (freepos==0x400) codelength=11;  /* freepos                 */
 else if (freepos==0x800) codelength=12;
 while (getbits<codelength) {         /* zolang nog onvoldoende bits */
   if ((x=getc(fin))==EOF) {
        return _eof;
   }
   getbuffer=(getbuffer<<8) |  x;     /* inlezen en "vastplakken"    */
   getbits+=8;
 }
 getbits-=codelength;
 return ((unsigned long)0xffffffffl>>(32-codelength))&(getbuffer>>getbits);
}


/*********************** Byte in- en uitvoer *************************/

#define GetByte() (ibits+=8,getc(fin))        /* byte lezen          */

int PutStr(int k)            /* Expansie: schrijf string  met code k */
{ int x;
  if (k<256) {
      x=k;                   /* vaste invoer voor ‚‚n byte           */
      putc(k,fout);
  } else {
      x=PutStr(prefix[k]);   /* Recursie : Eerst prefix wegschrijven */
      putc(tail[k],fout);    /*            daarna laatste byte       */
  }
  return x;            /* Teruggave eerste byte (voor nieuwe invoer) */
}

/************************ Compressie *********************************/
void Compress(void)
{ int kx,ky,x,y;
  InitHash();
  if ((x=GetByte())==EOF) return;        /* eerste byte lezen        */
  for (;;) {
       kx=x;				 /* nieuwe string (‚‚n byte) */
       for (;;) {			 /* probeer langer te maken  */
	 if ((x=GetByte())==EOF) {       /* lees volgende byte       */
	    PutCode(kx); FlushCode();    /* EOF : terminatie         */
	    return;
	 }
	 y=hash(kx,x);                   /* Bereken hashindex        */
	 ky=htab[y];
	 if ((ky!=empty) && ((prefix[ky]!=kx) || (tail[ky]!=x))) {
	      y=(y+(hashmod>>1)) & hashmod; /* "Botsing", zoek verder*/
	      ky=htab[y];
	 }
	 if ((ky!=empty) && (prefix[ky]==kx) && (tail[ky]==x)) {
	      kx=ky;                  /* gevonden; verder verlengen  */
	 } else {
	   break;
	 }
       }
       PutCode(kx);     /* Code voor gevonden beginstuk wegschrijven */
       prefix[freepos]=kx;  /* en het verlengde stuk string inpassen */
       tail[freepos]=x;
       htab[y]=freepos++;
       if (freepos>size) {             /* Codetabel vol --> Reset    */
	   InitHash();
	   reset++;
       }
  }
}


/**************************** Expansie *******************************/

void Expand(void)
{ int k,lastk,x;
  while ((k=GetCode())!=_eof) {         /* Lees eerste code          */
    x=PutStr(k);                        /* Uitlezen                  */
    for (;;) {
       lastk=k;                         /* Laatste kode merken       */
       if ((k=GetCode())==_eof) return; /* Lees volgende code        */
       if (k<freepos) {                 /* Code is bekend (normaal)  */
	   x=PutStr(k);                 /* Eerst string uitlezen     */
	   prefix[freepos]=lastk;    /* dan nieuwe string behandelen */
	   tail[freepos]=x;
	   freepos++;
       } else if (k==freepos) {   /* Apart geval zoals bv. "abababa" */
	   prefix[freepos]=lastk;
	   tail[freepos]=x;         /* Eerst nieuwe string inlezen   */
	   freepos++;
	   x=PutStr(k);            /* dan nieuwe string wegschrijven */
       }   else {
	      printf("\nERROR: illegal code");  /* Fout in  Codefile */
       }
       if (freepos>size)
	      freepos=256;         /* Codetabel vol --> Reset        */
    }
  }
}


void usage(void)
{
 printf("usage: \n");
 printf(" compexp c infile outfile   to compress.\n");
 printf(" compexp x infile outfile   to expand.\n");
}
int main(int argc, char **argv)
{ int c;
  if (argc!=4) {
      usage();
      return 1;
  }
  if ((fin=fopen(argv[2],"rb"))==NULL) {           /* invoerfile     */
       printf("can't open %s",argv[2]);
       return 2;
  }
  if ((fout=fopen(argv[3],"wb"))==NULL) {          /* uitvoerfile    */
       printf("can't create %s",argv[3]);
       return 3;
  }
  if ((c=*argv[1])=='C' || c=='c') {                /* Compressie     */
       printf("\nCompressing %s to %s",argv[2],argv[3]);
       Compress();
       printf(",\n(%2ld%%, %2ld * %d + %2d entries), done."
	 ,((ibits-obits)*100)/ibits,reset,size+1,freepos-1);
  } else
    if (c=='x' || c=='X') {                        /* Expansie       */
       printf("\nExpanding %s to %s",argv[2],argv[3]);
       Expand();
       printf(", done.");
    }
    else {
       printf("unknown option\n");
       usage();
       return 5;
    }
  fclose(fin);
  fclose(fout);
  return 0;
}  /* einde compexp.c  */