/*---------------------------------------------------------------------------*/
/*
	File: replace.c
*/
/*---------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <fcntl.h>
#include <io.h>
#include <sys/stat.h>

#define _FILE "REPLACE.C"


/*---------------------------------------------------------------------------*/

typedef char BOOL;
#ifndef TRUE
#define TRUE  (0==0)
#endif
#ifndef FALSE
#define FALSE (0==1)
#endif


/*---------------------------------------------------------------------------*/

#define FILE_BUFFER_SIZE 512
unsigned char FileBuffer[FILE_BUFFER_SIZE];


#define OCCURRENCE_TABLE_ENTRIES 2048

BOOL ReplaceTemplate (int fdInput, int fdOutput,
	const unsigned char *Template, unsigned int TemplateSize,
	const unsigned char *Replacement, unsigned int ReplacementSize,
	unsigned long *pTotalOccurrences)
/*
	Returns TRUE on success.
	The string find algorithm according to Knuth, Morris, Pratt (see algorithm
	of program 1.2 in Niklaus Wirth "Algorithmen und Datenstrukturen", 4. Aufl.
	S.66 ff) is applied.
*/
{
	unsigned int *MismatchIndexTable;
	unsigned long SearchPos, ReadPos, WritePos, EndPos, FileSize;
	int Occ, Occurrences, BytesRead, BytesWritten, n;
	unsigned int i, j;
	unsigned long OccurrenceTable[OCCURRENCE_TABLE_ENTRIES];

	*pTotalOccurrences = 0;
		
	MismatchIndexTable = (unsigned int *)(malloc (TemplateSize * sizeof(unsigned int)));
	if (MismatchIndexTable == NULL)
	{
		fprintf (stderr, "(%s, %d) can't allocate mismatch index table\n", _FILE, __LINE__);
		exit (1);
	}
	MismatchIndexTable[0] = ((unsigned int) -1);
	j = 0;
	for (i = 1; i < TemplateSize; i++)
	{
		MismatchIndexTable[i] = (Template[i] == Template[j]) ? MismatchIndexTable[j] : j;
		while ((j != ((unsigned int) -1)) && (Template[i] != Template[j]))
			j = MismatchIndexTable[j];
		j++;
	}

	FileSize = filelength (fdInput);
	if (FileSize == -1L)
	{
		free (MismatchIndexTable);
		fprintf (stderr, "(%s, %d) can't get file size (%d)\n", _FILE, __LINE__, errno);
		return (FALSE);
	}
	SearchPos = 0;
	do
	{
		Occurrences = 0;
		lseek (fdInput, SearchPos, SEEK_SET);
		i = 0;
		do
		{
			BytesRead = read (fdInput, FileBuffer, FILE_BUFFER_SIZE);
			if (BytesRead > 0)
			{
				j = 0;
				do
				{
					while ((j < ((unsigned int) BytesRead)) && (i < TemplateSize) && (FileBuffer[j] == Template[i]))
					{
						i++;
						j++;
					}
					if (i == TemplateSize)
					{
						OccurrenceTable[Occurrences++] = SearchPos + j - TemplateSize;
						i = 0;
					}
					else if (j < ((unsigned int) BytesRead))
					{
						i = MismatchIndexTable[i];
						if (i == ((unsigned int) -1))
						{
							i = 0;
							j++;
						}
					}
				} while ((j < ((unsigned int) BytesRead)) && (Occurrences < OCCURRENCE_TABLE_ENTRIES));
				SearchPos += j;
			}
		} while ((BytesRead > 0) && (Occurrences < OCCURRENCE_TABLE_ENTRIES));
		if (BytesRead < 0)
		{
			free (MismatchIndexTable);
			fprintf (stderr, "(%s, %d) can't read input (%d)\n", _FILE, __LINE__, errno);
			return (FALSE);
		}
		if ((BytesRead == 0) && (SearchPos != FileSize))
		{
			free (MismatchIndexTable);
			fprintf (stderr, "(%s, %d) FileEndPos (%ld) != FileSize (%ld)\n", _FILE, __LINE__, SearchPos, FileSize);
			return (FALSE);
		}

		*pTotalOccurrences += Occurrences;
		if (Occurrences != 0)
		{
			if (ReplacementSize <= TemplateSize)
			{
				ReadPos = 0;
				WritePos = 0;
				Occ = 0;
				do
				{
					EndPos = (Occ < Occurrences) ? OccurrenceTable[Occ] : FileSize;
					while (ReadPos < EndPos)
					{
						if (lseek (fdInput, ReadPos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek input (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						n = (EndPos - ReadPos < FILE_BUFFER_SIZE) ? (int)(EndPos - ReadPos) : FILE_BUFFER_SIZE;
						BytesRead = read (fdInput, FileBuffer, n);
						if (BytesRead <= 0)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't read input (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						if (lseek (fdOutput, WritePos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						BytesWritten = write (fdOutput, FileBuffer, BytesRead);
						if (BytesWritten != BytesRead)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't write output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						ReadPos += BytesRead;
						WritePos += BytesWritten;
					}
					if (Occ < Occurrences)
					{
						if (lseek (fdOutput, WritePos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						if (ReplacementSize != 0)
						{
							BytesWritten = write (fdOutput, Replacement, ReplacementSize);
							if (((unsigned int) BytesWritten) != ReplacementSize)
							{
								free (MismatchIndexTable);
								fprintf (stderr, "(%s, %d) can't write output (%d)\n", _FILE, __LINE__, errno);
								return (FALSE);
							}
						}
						ReadPos += TemplateSize;
						WritePos += ReplacementSize;
					}
					Occ++;
				} while (Occ <= Occurrences);
				if (lseek (fdInput, 0L, SEEK_SET) == -1L)
				{
					free (MismatchIndexTable);
					fprintf (stderr, "(%s, %d) can't seek input (%d)\n", _FILE, __LINE__, errno);
					return (FALSE);
				}
				if (chsize (fdOutput, WritePos) == -1)
				{
					free (MismatchIndexTable);
					fprintf (stderr, "(%s, %d) can't change size of output (%d)\n", _FILE, __LINE__, errno);
					return (FALSE);
				}
			}
			else
			{
				ReadPos = FileSize;
				WritePos = FileSize + Occurrences * (ReplacementSize - TemplateSize);
				if (chsize (fdOutput, WritePos) == -1)
				{
					free (MismatchIndexTable);
					fprintf (stderr, "(%s, %d) can't change size of output (%d)\n", _FILE, __LINE__, errno);
					return (FALSE);
				}
				Occ = Occurrences + 1;
				do
				{
					Occ--;
					if (Occ < Occurrences)
					{
						ReadPos -= TemplateSize;
						WritePos -= ReplacementSize;
						if (lseek (fdOutput, WritePos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						if (ReplacementSize != 0)
						{
							BytesWritten = write (fdOutput, Replacement, ReplacementSize);
							if (((unsigned int) BytesWritten) != ReplacementSize)
							{
								free (MismatchIndexTable);
								fprintf (stderr, "(%s, %d) can't write output (%d)\n", _FILE, __LINE__, errno);
								return (FALSE);
							}
						}
					}
					EndPos = (Occ != 0) ? OccurrenceTable[Occ-1] + TemplateSize : 0;
					while (ReadPos > EndPos)
					{
						n = (ReadPos - EndPos < FILE_BUFFER_SIZE) ? (int)(ReadPos - EndPos) : FILE_BUFFER_SIZE;
						ReadPos -= n;
						WritePos -= n;
						if (lseek (fdInput, ReadPos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek input (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						BytesRead = read (fdInput, FileBuffer, n);
						if (BytesRead != n)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't read input (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						if (lseek (fdOutput, WritePos, SEEK_SET) == -1L)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't seek output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
						BytesWritten = write (fdOutput, FileBuffer, BytesRead);
						if (BytesWritten != BytesRead)
						{
							free (MismatchIndexTable);
							fprintf (stderr, "(%s, %d) can't write output (%d)\n", _FILE, __LINE__, errno);
							return (FALSE);
						}
					}
				} while (Occ > 0);
			}
		}
		SearchPos = SearchPos - ((unsigned long) Occurrences) * ((unsigned long) TemplateSize) +
			((unsigned long) Occurrences) * ((unsigned long) ReplacementSize);
		FileSize = FileSize - ((unsigned long) Occurrences) * ((unsigned long) TemplateSize) +
			((unsigned long) Occurrences) * ((unsigned long) ReplacementSize);
	} while (SearchPos < FileSize);
	free (MismatchIndexTable);
	return (TRUE);
}


/*---------------------------------------------------------------------------*/

static char UsageMsg[] =
	"REPLACE replaces all occurrences of <Template> with <Replacement>.\n"
	"The known limitation is that the file size must not be greater than 2GB.\n"
	"(c) G.Diehl ISDN GmbH, 1996\n"
	"\n"
	"Usage: REPLACE [options] <File> <Template> <Replacement>\n"
	"options:\n"
	"  -x      Ignore if template not found\n"
	"  -e<num> Expected number of matches\n"
	"  -b      Binary, expects hex strings xx xx xx\n";


void main (int argc, char *(argv[]))
{
	int fd, arg;
	unsigned long Occurrences;
	unsigned long ExpectedOccurrences;
	BOOL IgnoreTemplateNotFound, BinaryMode;
	unsigned char *BinaryTemplate, *BinaryReplacement;
	unsigned int TemplateSize, ReplacementSize;
	char *p;

	ExpectedOccurrences = 0;
	IgnoreTemplateNotFound = FALSE;
	BinaryMode = FALSE;
	arg = 1;
	while ((arg < argc) && ((argv[arg][0] == '-') || (argv[arg][0] == '/')))
	{
		switch (argv[arg][1])
		{
		case 'x':
		case 'X':
			IgnoreTemplateNotFound = TRUE;
			break;

		case 'e':
		case 'E':
			ExpectedOccurrences = atol (&(argv[arg][2]));
			break;

		case 'b':
		case 'B':
			BinaryMode = TRUE;
			break;

		default:
			fprintf (stderr, "Unknown option '%s'\n%s", argv[arg], UsageMsg);
			exit (1);
		}
		arg++;
	}
	if (argc - arg < 3)
	{
		fprintf (stderr, "Missing arguments\n%s", UsageMsg);
		exit (1);
	}
	if (argv[arg+1][0] == '\0')
	{
		fprintf (stderr, "Template must not be empty\n");
		exit (1);
	}

	fd = open (argv[arg], O_RDWR | O_BINARY);
	if (fd == -1)
	{
		fprintf (stderr, "Cannot open file '%s' (%d)\n", argv[arg], errno);
		exit (1);
	}
	if (BinaryMode)
	{
		BinaryTemplate = (unsigned char *)(malloc ((strlen (argv[arg+1]) + 1) >> 1));
		if (BinaryTemplate == NULL)
		{
			fprintf (stderr, "(%s, %d) can't allocate binary template\n", _FILE, __LINE__);
			close (fd);
			exit (1);
		}
		BinaryReplacement = (unsigned char *)(malloc ((strlen (argv[arg+2]) + 1) >> 1));
		if (BinaryReplacement == NULL)
		{
			fprintf (stderr, "(%s, %d) can't allocate binary replacement\n", _FILE, __LINE__);
			free (BinaryTemplate);
			close (fd);
			exit (1);
		}
		TemplateSize = 0;
		p = argv[arg+1];
		do
		{
			while ((*p != '\0') && !isxdigit (*p))
				p++;
			if (*p != '\0')
			{
				BinaryTemplate[TemplateSize] =
					(isdigit (*p) ? *p - '0' : tolower (*p) - 'a' + 10) << 4;
				p++;
				if (!isxdigit (*p))
				{
					fprintf (stderr, "Odd number of digits in template\n");
					free (BinaryReplacement);
					free (BinaryTemplate);
					close (fd);
					exit (1);
				}
				BinaryTemplate[TemplateSize] |=
					isdigit (*p) ? *p - '0' : tolower (*p) - 'a' + 10;
				p++;
				TemplateSize++;
			}
		} while (*p != '\0');
		if (TemplateSize == 0)
		{
			fprintf (stderr, "Template must not be empty\n");
			free (BinaryReplacement);
			free (BinaryTemplate);
			close (fd);
			exit (1);
		}
		ReplacementSize = 0;
		p = argv[arg+2];
		do
		{
			while ((*p != '\0') && !isxdigit (*p))
				p++;
			if (*p != '\0')
			{
				BinaryReplacement[ReplacementSize] =
					(isdigit (*p) ? *p - '0' : tolower (*p) - 'a' + 10) << 4;
				p++;
				if (!isxdigit (*p))
				{
					fprintf (stderr, "Odd number of digits in replacement\n");
					free (BinaryReplacement);
					free (BinaryTemplate);
					close (fd);
					exit (1);
				}
				BinaryReplacement[ReplacementSize] |=
					isdigit (*p) ? *p - '0' : tolower (*p) - 'a' + 10;
				p++;
				ReplacementSize++;
			}
		} while (*p != '\0');
		if (!ReplaceTemplate (fd, fd,
			BinaryTemplate, TemplateSize, BinaryReplacement, ReplacementSize,
			&Occurrences))
		{
			free (BinaryReplacement);
			free (BinaryTemplate);
			close (fd);
			exit (1);
		}
		free (BinaryReplacement);
		free (BinaryTemplate);
	}
	else
	{
		if (!ReplaceTemplate (fd, fd,
			argv[arg+1], strlen (argv[arg+1]), argv[arg+2], strlen (argv[arg+2]),
			&Occurrences))
		{
			close (fd);
			exit (1);
		}
	}
	if ((Occurrences == 0) && !IgnoreTemplateNotFound)
	{
		fprintf (stderr, "No occurrence of '%s'\n", argv[arg+1]);
		close (fd);
		exit (1);
	}
	if ((Occurrences != ExpectedOccurrences) && (ExpectedOccurrences != 0))
	{
		fprintf (stderr, "Not expected number of occurrences (%ld)\n", ExpectedOccurrences);
		close (fd);
		exit (1);
	}
	fprintf (stderr, "%ld occurrences replaced\n", Occurrences);
	close (fd);
}


/*---------------------------------------------------------------------------*/
