/*@Version $Id: strdiff.c,v 2.2 2005/12/30 15:13:25 ksb Exp $@*/
/* $Compile:  gcc -Wall -fwritable-strings -g -DTEST strdiff.c
 */
/*@Header@*/
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <sysexits.h>

extern char *progname;

/*@Explode diff@*/
/* Remove characters from the longer string to make the two more common	(ksb)
 * Record the characters removed in the buffer allocated below.  Restore
 * the original strings as we return.
 */
static void
StrRDiff(char *pcLeft, char *pcRight, char **ppcOut)
{
	register unsigned iMin, iEq;
	register char *pcSub, *pcAdd;

	if ((char *)0 != (pcSub = strstr(pcLeft, pcRight))) {
		pcAdd = ppcOut[0] + strlen(ppcOut[0]);
		while (pcSub > pcLeft) {
			*pcAdd++ = *pcLeft++;
		}
		*pcAdd = '\000';
		pcSub += strlen(pcRight);
		ppcOut[1] -= strlen(pcSub);
		memmove(ppcOut[1], pcSub, strlen(pcSub));
		return;
	}
	if ((char *)0 != (pcSub = strstr(pcRight, pcLeft))) {
		pcAdd = ppcOut[2]+strlen(ppcOut[2]);
		while (pcSub > pcRight) {
			*pcAdd++ = *pcRight++;
		}
		*pcAdd = '\000';
		pcSub += strlen(pcLeft);
		ppcOut[3] -= strlen(pcSub);
		memmove(ppcOut[3], pcSub, strlen(pcSub));
		return;
	}

	/* look for the first common character, if it is not '\000' we
	 * might have something, we know the first characters are not
	 * the same from the caller.
	 */
	for (iEq = 0; '\000' != pcLeft[iEq]; ++iEq) {
		for (iMin = 0; '\000' != pcRight[iMin]; ++iMin) {
			if (pcRight[iMin] == pcLeft[iEq]) {
				break;
			}
		}
		if ('\000' == pcRight[iMin])
			continue;
		pcAdd = ppcOut[0] + strlen(ppcOut[0]);
		for (/* above*/; iEq > 0; --iEq) {
			*pcAdd++ = *pcLeft++;
		}
		*pcAdd = '\000';
		pcAdd = ppcOut[2] + strlen(ppcOut[2]);
		for (/* above*/; iMin > 0; --iMin) {
			*pcAdd++ = *pcRight++;
		}
		*pcAdd = '\000';
		while ('\000' != *pcLeft && '\000' != *pcRight && *pcLeft == *pcRight) {
			++pcLeft, ++pcRight;
		}
		if ('\000' != *pcLeft && '\000' != *pcRight) {
			StrRDiff(pcLeft, pcRight, ppcOut);
			return;
		}
	}

	/* We don't find anything else, return the lot
	 */
	ppcOut[1] -= strlen(pcLeft);
	memmove(ppcOut[1], pcLeft, strlen(pcLeft));
	ppcOut[3] -= strlen(pcRight);
	memmove(ppcOut[3], pcRight, strlen(pcRight));
}

/* Return the difference between two (short) strings.			(ksb)
 * One should free our result, when they don't need it anymore.
 * We don't _have_ to take of the top level common prefix/suffix,
 * but it save a lot of memory in the buffers we build.
 */
char **
StrDiff(char *pcLeft, char *pcRight)
{
	register unsigned iL, iR;
	register int cKeep;
	register char **ppcRet;

	while ('\000' != *pcLeft && *pcLeft == *pcRight) {
		++pcLeft, ++pcRight;
	}
	iL = strlen(pcLeft);
	iR = strlen(pcRight);
	while (iL > 0 && pcLeft[iL-1] == pcRight[iR-1]) {
		--iL, --iR;
	}
	if ((char **)0 == (ppcRet = (char **)malloc(4*sizeof(char *)+(iL|7)+1+(iR|7)+1+4))) {
		return (char **)0;
	}
	/* 4 char pointers in a vector, to:
	 *	left[start], left[end], right[start], right[end]
	 */
	ppcRet[0] = (char *)(& ppcRet[4]);
	ppcRet[1] = ppcRet[0]+(iL|7)+1;
	ppcRet[2] = ppcRet[1]+1;
	ppcRet[3] = ppcRet[2]+iR+1;
	ppcRet[0][0] = '\000';		/* left-head */
	ppcRet[1][0] = '\000';		/* left-tail, grow left */
	ppcRet[2][0] = '\000';		/* right-head */
	ppcRet[3][0] = '\000';		/* right-tail, grow left */
	cKeep = pcLeft[iL];
	pcLeft[iL] = pcRight[iR] = '\000';
	StrRDiff(pcLeft, pcRight, ppcRet);
#if DEBUG
	fprintf(stderr, "\"%s\".\"%s\"   \"%s\".\"%s\"\n", ppcRet[0], ppcRet[1], ppcRet[2], ppcRet[3]);
#endif
	pcLeft[iL] = pcRight[iR] = cKeep;
	memmove(ppcRet[0]+strlen(ppcRet[0]), ppcRet[1], strlen(ppcRet[1])+1);
	memmove(ppcRet[2]+strlen(ppcRet[2]), ppcRet[3], strlen(ppcRet[3])+1);
	ppcRet[1] = ppcRet[2];
	ppcRet[2] = (char *)0;
	return ppcRet;
}
/*@Remove@*/

#if defined(TEST)
/*@Explode main@*/

char *progname = "strdiff-test";

static char acEmpty[] = "";
static char *aapcTest[][4] = {
	{ "===", "===", acEmpty, acEmpty },
	{ "abc", "xyz", "abc", "xyz" },
	{ "abc", "b", "ac", acEmpty },
	{ "b", "abc", acEmpty, "ac" },
	{ "preFIXing", "pre", "FIXing", acEmpty},
	{ "preFIXing", "ing", "preFIX", acEmpty},
	{ "preFIX", "FIXing", "pre", "ing"},
	{ "abcdef", "ab+cd+ef+g", acEmpty, "+++g"},
	{ "ab+cd+ef+g", "abcdef", "+++g", acEmpty},
	{ (char *)0, (char *)0, "ksb", "strdiff" }
};

/* Run the tests above, or compute the difference of argv[1]		(ksb)
 * and argv[2].
 */
int
main(int argc, char **argv, char **envp)
{
	register unsigned i, iFail;
	register char **ppcGot;

	iFail = 0;
	if (3 == argc) {
		if ((char **)0 == (ppcGot = StrDiff(argv[1], argv[2]))) {
			fprintf(stderr, "%s: NULL string difference\n", progname);
			exit(EX_DATAERR);
		}
		printf("%s\n%s\n", ppcGot[0], ppcGot[1]);
		exit(EX_OK);
	}
	for (i = 0; (char *)0 != aapcTest[i][0]; ++i) {
		if ((char **)0 == (ppcGot = StrDiff(aapcTest[i][0], aapcTest[i][1]))) {
			fprintf(stderr, "%s: NULL return from StrDiff(\"%s\", \"%s\")\n", progname, aapcTest[i][0], aapcTest[i][1]);
			continue;
		}
		if (0 == strcmp(ppcGot[0], aapcTest[i][2]) && 0 == strcmp(ppcGot[1], aapcTest[i][3])) {
			fprintf(stderr, "%s: StrDiff(\"%s\", \"%s\") -- OK\n", progname, aapcTest[i][0], aapcTest[i][1]);
			continue;
		}
		++iFail;
		fprintf(stderr, "%s: StrDiff(\"%s\", \"%s\"):\n", progname, aapcTest[i][0], aapcTest[i][1]);
		fprintf(stderr, "\t left \"%s\" \"%s\"\n", aapcTest[i][2], ppcGot[0]);
		fprintf(stderr, "\tright \"%s\" \"%s\"\n", aapcTest[i][3], ppcGot[1]);
	}
	exit(iFail != 0);
}
/*@Remove@*/
#endif