//*********************************************************
//
// Lempel-Ziv based data compression
//   Copyright	Ver 1.0
// ECE of UMass-Amherst   March 10, 98
//
//*********************************************************
// 
// Note: Use binary format to represent the compressed result
//


#include <stdio.h>
#define L_WIN 128		// size of dictionary window
#define L_LOOK 64		// size of look-ahead buffer
#define L L_WIN+L_LOOK

main(argc, argv)
int argc;
char *argv[];
{
	unsigned char x[L+1];	// 8-bit; use last one to save at all-matching
	unsigned endNumber, lastSymbol, pointer;
	int i, j;
	int new_L_LOOK, maxLen, oldMaxLen, finishup=0, gameOver=0;

	FILE *p1, *p2;
	
	
	if(argc < 3){
		printf("Usage: lz77 source target\n");
		exit(1);
	}
	if( (p1=fopen(argv[1], "r")) == NULL){
	//if( (p1=fopen("zzh.txt", "r")) == NULL){
		printf("\nThe file %s not exist!\n", argv[1]);
		exit(0);
	}
	if( (p2=fopen(argv[2], "w")) == NULL) {
		printf("\nThe target file %s can't be opened!\n", argv[2]);
		exit(0);
	}

	// initialize sliding window & look-ahead buffer
	for(i=1; i<=L+1; i++)
		x[i] = 0;
	for(i=1; i<=L_LOOK+1; i++)
		fread( &x[L_WIN+i], 1, 1, p1 );
	
   do{
	oldMaxLen = 0;
	for(i=1; i<=L_WIN; i++){		// Bug! "i" should caculate from 0 to 255
		maxLen = 0;
		for(j=1; j<=L_LOOK; j++){
			if(x[i+j-1] == x[L_WIN+j]) // compare two-stream
				maxLen++;	
			else break;
		}
		if(maxLen == L_LOOK){ 		// if book-ahead buffer all match
			oldMaxLen = maxLen;
			pointer = i;
			lastSymbol = x[L+1];
			break;
		}
		else if(maxLen >= oldMaxLen) {	//if max-matching, save the pointer & length
			oldMaxLen = maxLen; 	// including maxlen == 0
			pointer = i;
			lastSymbol = x[L_WIN+j];
		}
	}// end of for

	// left-shift the stream
	for(i=1; i <= (L-oldMaxLen); i++)
		x[i] = x[i+oldMaxLen+1];
	
	for(i=1; i <= oldMaxLen+1; i++) {
		if( feof(p1) ) {
			endNumber = i - 1;	// in case of end-of-file
			finishup = 1; 
			break;
		}
		else fread( &x[L-oldMaxLen+i], 1, 1, p1);// refill the look-ahead buffer
	}

	// output the code word
	// pointer + max matching length + last symbol
	fwrite (&pointer, 1, 1, p2);
	fwrite (&oldMaxLen, 1, 1, p2);
	fwrite (&lastSymbol, 1, 1, p2);
	
    // finishing up at the end of the file
    if (finishup == 1)
    {	
      new_L_LOOK = L_LOOK - (oldMaxLen + 1) + endNumber; // change the size of look-ahead buffer
      do{
	oldMaxLen = 0;
	for(i=1; i<=L_WIN; i++){
		maxLen = 0;
		for(j=1; j<=new_L_LOOK; j++){
			if(x[i+j-1] == x[L_WIN+j]) // compare two-stream
				maxLen++;	
			else break;
		}
		if(maxLen == new_L_LOOK){ 	// if look-ahead buffer all match
			oldMaxLen = maxLen;
			pointer = i;
			gameOver= 1;
			//lastSymbol = EOF;	// ???
			break;
		}
		else if(maxLen >= oldMaxLen) {	//if max-matching, save the pointer & length
			oldMaxLen = maxLen;
			pointer = i;
			lastSymbol = x[L_WIN+j];
		}
	}

	fwrite(&pointer, 1, 1, p2);
	fwrite(&oldMaxLen, 1, 1, p2);
	if( !gameOver )	fwrite(&lastSymbol, 1, 1, p2);	//There is no lastSymbol at the end.

	// left-shift the stream
	for(i=1; i <= (L-oldMaxLen); i++)
		x[i] = x[i+oldMaxLen+1];
	
	new_L_LOOK = new_L_LOOK - oldMaxLen - 1;

     }while(maxLen == new_L_LOOK);
   } // end of if
  } while(!finishup);
	
  fclose(p1);
  fclose(p2);
}