/*
 * bindiff 0.0.1, testing binary diff utility.
 *
 * Copyright (C) 2006 Jindrich Novy (jnovy@users.sourceforge.net)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>

#include <inttypes.h>

#ifndef QSORT
#include "qsufsort.c"
#endif

#define MINMATCH 10

uint8_t *b1, *b2;
off_t b1size, b2size;
uint32_t *b1off, b1offs, *c2o;

void *check_malloc( size_t s ) {
	void *p = malloc(s);

	if ( !p ) {
		printf("Can't allocate %llu bytes, exiting...\n", s);
		exit(1);
	}
	
	return p;
}

#ifdef QSORT
int sort_func( const void *ptr1, const void *ptr2 ) {
	uint32_t o1 = *(uint32_t*)ptr1;
	uint32_t o2 = *(uint32_t*)ptr2;

	if ( b1[o1] > b1[o2] ) return  1;
	if ( b1[o1] < b1[o2] ) return -1;

	{
		uint32_t i, p1, p2;

		for ( i=1; i<b1size; i++ ) {
			p1 = o1+i;
			if ( p1 >= b1size ) break;

			p2 = o2+i;
			if ( p2 >= b1size ) break;

			if ( b1[p1] > b1[p2] ) return  1;
			if ( b1[p1] < b1[p2] ) return -1;
		}
	}

        return 0;
}
#endif

uint32_t match( uint32_t o2, uint32_t *b1pos ) {
	uint32_t i, o, best_match, os, oe;

	*b1pos = 0;
	best_match = 0;
	os = c2o[b2[o2]+256*b2[o2+1]];
	oe = c2o[b2[o2]+256*b2[o2+1]+1];

	for ( i=os; i<oe; i++ ) {
		if ( best_match && b1off[i]+best_match-1 < b1size ) {
			int32_t n, b=0;
			
			for ( o=best_match-1; o>0; o-- )
				if ( b1[b1off[i]+o] != b2[o2+o] ) {
					b=1;
					break;
				}
			
			if ( b ) break;
		}
		for ( o=best_match; b1off[i]+o < b1size && b1[b1off[i]+o] == b2[o2+o]; o++ );
		if ( o > best_match ) {
			best_match = o;
			*b1pos = b1off[i];
		} else {
			if ( b1off[i]+o < b1size && b1[b1off[i]+o] > b2[o2+o] ) break;
		}
	}

	return best_match;
}

int main( int argc, char **argv ) {
	FILE *f1, *f2;
	struct stat s1, s2;
	int32_t *X, *P;
	
	if ( argc != 3 ) {
		printf("Usage: %s file1 file2\n", argv[0]);
		exit(0);
	}
	
	if ( stat(argv[1], &s1 ) ) {
		perror("");
		exit(1);
	}
	if ( stat(argv[2], &s2 ) ) {
		perror("");
		exit(1);
	}
		
	b1size = s1.st_size;
	b2size = s2.st_size;
	b1offs = b1size>MINMATCH?b1size-MINMATCH:0;
//	b1offs = b1size;
	
	f1 = fopen(argv[1],"rb");
	f2 = fopen(argv[2],"rb");
	
	b1    = check_malloc(b1size);
	b2    = check_malloc(b2size);
	b1off = check_malloc(b1offs*sizeof(uint32_t));
	c2o   = check_malloc((0x10001)*sizeof(uint32_t));
	X     = check_malloc((b1offs+1)*sizeof(int32_t));
	P     = check_malloc((b1offs+1)*sizeof(int32_t));
	
	fread( b1, 1, b1size, f1 );
	fread( b2, 1, b2size, f2 );
	
	fclose( f2 );
	fclose( f1 );
	
	{
		size_t i;
#ifdef QSORT
		for ( i=0; i<b1offs; i++ )
			b1off[i] = i;
	
		qsort( b1off, b1offs, sizeof(uint32_t), &sort_func );
#else
		for ( i=0; i<b1offs; i++ )
			X[i] = b1[i];
		
		suffixsort( X, P, b1offs, 256, 0 );
		
		for ( i=0; i<b1offs; i++ )
			b1off[i] = P[i+1];

/*		for ( i=0; i<b1offs; i++ )
			printf("%d\n", b1off[i]);*/
#endif
		
		c2o[b1[b1off[0]]] = 0;
		
		for ( i=0; i<=0xffff; i++ )
			c2o[i] = 0xffffffff;
		
		for ( i=1; i<b1offs; i++ ) {
			if ( b1[b1off[i]]   != b1[b1off[i-1]] ||
			     b1[b1off[i]+1] != b1[b1off[i-1]+1])
				c2o[b1[b1off[i]]+256*b1[b1off[i]+1]] = i;
		}
		c2o[0x10000] = b1offs;
		
		{
			int32_t in, ooff = 0x10000;
			
			for ( in=0xffff; in>=0; in-- )
				if ( c2o[in] != 0xffffffff )
					ooff = in;
				else
					c2o[in] = c2o[ooff];
		}
		
		FILE *ff = fopen("outc","wb");

		for ( i=0; i<0x10000; i++ )
			fprintf(ff, "%5d: %d %c%c\n", i, c2o[i], b1[c2o[i]], b1[c2o[i]+1]);
		
		fclose(ff);

/*		FILE *f = fopen("out","wb");
		int x, y;
		
		for ( y=0; y<b1offs; y++ ) {
			fprintf(f,"%5d %5d: ", y, b1off[y]);
			for ( x=0; x<64 && b1off[y]+x < b1size; x++ ) {
				if ( b1[b1off[y]+x] != '\n' )
					fputc( b1[b1off[y]+x], f );
				else
					fputc( ' ', f );
			}
			fputc('\n', f);
		}		
		fclose(f);*/
	}
	
	{
		size_t i, match_size, unmatched=0;
		off_t fpos=0, ofpos;
		uint32_t b1pos;
		FILE *umf=fopen("um","wb");
		
		fputc(0,umf);
		fputc(0,umf);
		fputc(0,umf);
		
		for ( i=0; i<b2size; i+=match_size ) {
			match_size = match(i, &b1pos);
			if ( match_size < MINMATCH ) {
				unmatched++;
				match_size=1;
				fputc(b2[i],umf);
				continue;
			}
			
			ofpos = ftell(umf);
			if ( unmatched ) {
				fseek(umf, fpos, SEEK_SET);
				fputc(unmatched,umf);
				fputc(unmatched>>8,umf);
				fputc(unmatched>>16,umf);
				fseek(umf, ofpos, SEEK_SET);
				unmatched = 0;
			}
			fpos = ofpos;
			
			fputc(0,umf);
			fputc(0,umf);
			fputc(0,umf);
			fputc(b1pos,umf);
			fputc(b1pos>>8,umf);
			fputc(b1pos>>16,umf);
			fputc(match_size,umf);
			fputc(match_size>>8,umf);
			fputc(match_size>>16,umf);

#ifdef DEBUG			
			printf("%5d == %5d, %8d\n", b1pos, i, match_size);
#endif
		}
		
		if ( unmatched ) {
			ofpos = ftell(umf);
			fseek(umf, fpos, SEEK_SET);
			fputc(unmatched,umf);
			fputc(unmatched>>8,umf);
			fputc(unmatched>>16,umf);
			fseek(umf, ofpos, SEEK_SET);
		}
		
		fclose(umf);
	}
	
	free( c2o );
	free( b1off );
	free( b2 );
	free( b1 );
	
	return 0;
}