/* precom.c -- Experiments on file precompression
	Usage: precom <blocksize>
	Reads stdin and writes compressed file onto stdout
  */

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

void assert(int c, char *s)
{	if (!c) {
		fprintf(stderr, "%s\n", s);
		exit(0);
	}
}

/* MAIN TYPES AND DATA */

typedef long PosType;			/* Position in file */
typedef unsigned long SigType;	/* Rabin-Karp fingerprint signature */
#define MAXB 100000
#define MAXN 100000000
char origa[MAXN+MAXB];	/* Input string storage */
char *a;				/* Access origa through a (to allow negative indexing) */
int b;					/* Block size */
PosType n=0;			/* File size */
PosType clear=0;		/* Start of uncompressed text */

/* SEARCH FOR GOOD MATCHES */

int bestlen;			/* Longest match found: length */
PosType bestoldstart;	/* Start in transmitted portion */
PosType bestnewstart;	/* Start after a[clear] */

void expandmatch(PosType m1, PosType m2) /* m1 = new, m2 = old */
{	int i, len;
	m1 = m1-b+1;	/* Point at start of strings, */
	m2 = m2-b+1;	/*    not ends */
	for (i = 0; i < b; i++)
		if (a[m1+i] != a[m2+i])
			return;
	len = b;
	while ((a[m1-1] == a[m2-1]) && (m1 > clear)) {
		m1--; m2--; len++;
	}
	while (a[m1+len] == a[m2+len])
		len++;
	if (len > bestlen) {
		bestlen = len;
		bestnewstart = m1;
		bestoldstart = m2;
	}
}

void writeseq(PosType n1, PosType n2)
{	PosType i;
	/* works on PC with printf("\n"); here -- see precom8.c */
	for (i = n1; i <= n2; i++) {
		if (a[i] == '<')
				putchar(a[i]);	/* << is quoted < */
		putchar(a[i]);
	}
}

/* HASH TABLE */

typedef struct hnode *Hptr;
typedef struct hnode {
	Hptr	next;
	SigType	sig;
	PosType	pos;
} Hnode;

#define HSIZE 999983
Hptr htab[HSIZE];

void hashinit()
{	int i;
	for (i = 0; i < HSIZE; i++)
		htab[i] = 0;
}

void store(SigType s, PosType i)
{	int j = s % HSIZE;
	Hptr p = (Hptr) malloc(sizeof(Hnode));
	assert(p != 0, "malloc died");
	p->next = htab[j];
	htab[j] = p;
	p->sig = s;
	p->pos = i;
}

void checksig(SigType s, PosType i)
{	Hptr p;
	bestlen = -1;
	for (p = htab[s%HSIZE]; p; p = p->next)
		if (p->sig == s)
			expandmatch(i, p->pos);
	if (bestlen >= b) {
		writeseq(clear, bestnewstart-1);
		printf("<%ld,%ld>", bestoldstart, bestlen);
			/* replace first parm with betsnewstart-bestoldstart?? */
		clear = bestnewstart+bestlen;
	}
}


/* MAIN */

long mod(double a, long b)
{	long c = (int) (a / (double) b);
	return (long) (a - ((double) b * (double) c));
}

#define CHARSIZE 256

int main(int argc, char *argv[])
{	PosType i;
	int j, c, oldc;
	SigType s = 0, db; /* d^(b-1), mod q */
	SigType d = 32, q = 1999999973;
	a = origa;
	b = atoi(argv[1]);
	assert(b > 0 && b <= MAXB, "invalid b");
	hashinit();
	for (j = 0; j < b; j++) {
		a[0] = 0;
		a++; /* zeros at negative elements */
	}
	db = 1;
	for (j = 1; j < b; j++) {
		/* db = (db * d) % q; */
		db = mod((double) db * d, q);
	}
	while ((c=getchar()) != EOF)
		a[n++] = c;
	a[n] = a[n-1]+1; /* Must differ from a[n-1] */
	for (i = 0; i < n; i++) {
		oldc = a[i-b];
		c = a[i];
		s = mod(s + CHARSIZE * (double) q - oldc * (double) db, q);
		s = mod(s * (double) d + c, q);
		if (i-b+1 >= clear)
			checksig(s, i);
		if (i % b == b-1)
			store(s, i);
		if (0 && i > 0 && i % 1000000 == 0)
			fprintf(stderr, "Checkpoint %d\n", i);
	}
	writeseq(clear, n-1);
	return 0;
}



