- Use a heuristic to bound memory and cpu usage, at the cost of

producing suboptimal diffs for large file containing lots of changes.
Switch heuristic off with -d/--minimal (GNU compatible). Some hints
from millert@.
- Improve performance by reducing the number of realloc(3) calls.

ok millert@ tedu@

4 files changed, 68 insertions, 26 deletions

diff --git a/usr.bin/diff/diff.1 b/usr.bin/diff/diff.1
index b88f170e43b..877c19c468a 100644
--- a/usr.bin/diff/diff.1
+++ b/usr.bin/diff/diff.1
@@ -1,4 +1,4 @@
-.\" $OpenBSD: diff.1,v 1.18 2003/07/22 01:23:51 millert Exp $
+.\" $OpenBSD: diff.1,v 1.19 2003/07/27 07:39:52 otto Exp $
 .\"
 .\" Copyright (c) 1980, 1990, 1993
 .\"	The Regents of the University of California.  All rights reserved.
@@ -37,7 +37,7 @@
 .Nd differential file and directory comparator
 .Sh SYNOPSIS
 .Nm diff
-.Op Fl abilqtTw
+.Op Fl abdilqtTw
 .Oo
 .Fl c | Fl e | Fl f |
 .Fl n | Fl u
@@ -45,21 +45,21 @@
 .Op Fl L Ar label
 .Ar file1 file2
 .Nm diff
-.Op Fl abilqtTw
+.Op Fl abdilqtTw
 .Op Fl L Ar label
 .Fl C Ar number
 .Ar file1 file2
 .Nm diff
-.Op Fl abilqtw
+.Op Fl abdilqtw
 .Fl D Ar string
 .Ar file1 file2
 .Nm diff
-.Op Fl abilqtTw
+.Op Fl abdilqtTw
 .Op Fl L Ar label
 .Fl U Ar number
 .Ar file1 file2
 .Nm diff
-.Op Fl abilNqtTw
+.Op Fl abdilNqtTw
 .Oo
 .Fl c | Fl e | Fl f |
 .Fl n | Fl u
@@ -105,7 +105,12 @@ are marked
 Lines which are changed from one file to the other are marked in
 both files with
 .Sq !\ \& .
-Changes which lie within 3 lines of each other are grouped together on output.
+Changes which lie within 3 lines of each other are grouped together on
+output.
+.It Fl d
+Try very hard to produce a diff as small as possible. This may consume a
+lot of processing power and memory when processing large files with
+many changes.
 .It Fl e
 Produces output in a form suitable as input for the editor utility,
 .Xr ed 1 ,
diff --git a/usr.bin/diff/diff.c b/usr.bin/diff/diff.c
index b671ec3892e..56b11e3da95 100644
--- a/usr.bin/diff/diff.c
+++ b/usr.bin/diff/diff.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert Exp $	*/
+/*	$OpenBSD: diff.c,v 1.35 2003/07/27 07:39:52 otto Exp $	*/
 
 /*
  * Copyright (c) 2003 Todd C. Miller <Todd.Miller@courtesan.com>
@@ -21,7 +21,7 @@
  */
 
 #ifndef lint
-static const char rcsid[] = "$OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert Exp $";
+static const char rcsid[] = "$OpenBSD: diff.c,v 1.35 2003/07/27 07:39:52 otto Exp $";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -39,19 +39,20 @@ static const char rcsid[] = "$OpenBSD: diff.c,v 1.34 2003/07/22 16:42:58 millert
 
 #include "diff.h"
 
-int	 aflag, bflag, iflag, lflag, Nflag, Pflag, rflag, sflag, tflag, Tflag,
-	 wflag;
+int	 aflag, bflag, dflag, iflag, lflag, Nflag, Pflag, rflag, sflag, tflag, 
+	 Tflag, wflag;
 int	 format, context, status;
 char	*start, *ifdefname, *diffargs, *label;
 struct stat stb1, stb2;
 struct excludes *excludes_list;
 
-#define	OPTIONS	"abC:cD:efhiL:lnNPqrS:sTtU:uwX:x:"
+#define	OPTIONS	"abC:cdD:efhiL:lnNPqrS:sTtU:uwX:x:"
 static struct option longopts[] = {
 	{ "text",			no_argument,		0,	'a' },
 	{ "ignore-space-change",	no_argument,		0,	'b' },
 	{ "context",			optional_argument,	0,	'C' },
 	{ "ifdef",			required_argument,	0,	'D' },
+	{ "minimal",			no_argument,		0,	'd' },
 	{ "ed",				no_argument,		0,	'e' },
 	{ "forward-ed",			no_argument,		0,	'f' },
 	{ "ignore-case",		no_argument,		0,	'i' },
@@ -107,6 +108,9 @@ main(int argc, char **argv)
 			} else
 				context = 3;
 			break;
+		case 'd':
+			dflag = 1;
+			break;
 		case 'D':
 			format = D_IFDEF;
 			ifdefname = optarg;
@@ -361,11 +365,11 @@ __dead void
 usage(void)
 {
 	(void)fprintf(stderr,
-	    "usage: diff [-bilqtTw] [-c | -e | -f | -n | -u] [-L label] file1 file2\n"
-	    "       diff [-bilqtTw] [-L label] -C number file1 file2\n"
-	    "       diff [-bilqtw] -D string file1 file2\n"
-	    "       diff [-bilqtTw] [-L label] -U number file1 file2\n"
-	    "       diff [-bilNPqwtT] [-c | -e | -f | -n | -u ] [-L label] [-r] [-s] [-S name]\n"
+	    "usage: diff [-bdilqtTw] [-c | -e | -f | -n | -u] [-L label] file1 file2\n"
+	    "       diff [-bdilqtTw] [-L label] -C number file1 file2\n"
+	    "       diff [-bdilqtw] -D string file1 file2\n"
+	    "       diff [-bdilqtTw] [-L label] -U number file1 file2\n"
+	    "       diff [-bdilNPqwtT] [-c | -e | -f | -n | -u ] [-L label] [-r] [-s] [-S name]\n"
 	    "            [-X file] [-x pattern] dir1 dir2\n");
 
 	exit(2);
diff --git a/usr.bin/diff/diff.h b/usr.bin/diff/diff.h
index 4ac9d45c62e..fd60b13da2d 100644
--- a/usr.bin/diff/diff.h
+++ b/usr.bin/diff/diff.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: diff.h,v 1.21 2003/07/22 01:16:01 millert Exp $	*/
+/*	$OpenBSD: diff.h,v 1.22 2003/07/27 07:39:52 otto Exp $	*/
 
 /*-
  * Copyright (c) 1991, 1993
@@ -68,7 +68,7 @@ struct excludes {
 	struct excludes *next;
 };
 
-extern int	aflag, bflag, iflag, lflag, Nflag, Pflag, rflag, sflag,
+extern int	aflag, bflag, dflag, iflag, lflag, Nflag, Pflag, rflag, sflag,
 		tflag, Tflag, wflag;
 extern int	format, context, status, anychange;
 extern char	*start, *ifdefname, *diffargs, *label;
diff --git a/usr.bin/diff/diffreg.c b/usr.bin/diff/diffreg.c
index 2d71a665583..85f4e45fcdd 100644
--- a/usr.bin/diff/diffreg.c
+++ b/usr.bin/diff/diffreg.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: diffreg.c,v 1.42 2003/07/23 22:01:36 tedu Exp $	*/
+/*	$OpenBSD: diffreg.c,v 1.43 2003/07/27 07:39:52 otto Exp $	*/
 
 /*
  * Copyright (C) Caldera International Inc.  2001-2002.
@@ -65,7 +65,7 @@
  */
 
 #ifndef lint
-static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.42 2003/07/23 22:01:36 tedu Exp $";
+static const char rcsid[] = "$OpenBSD: diffreg.c,v 1.43 2003/07/27 07:39:52 otto Exp $";
 #endif /* not lint */
 
 #include <sys/param.h>
@@ -188,6 +188,7 @@ static int   anychange;
 static long *ixnew;		/* will be overlaid on file[1] */
 static long *ixold;		/* will be overlaid on klist */
 static struct cand *clist;	/* merely a free storage pot for candidates */
+static int   clistlen;		/* the length of clist */
 static struct line *sfile[2];	/* shortened by pruning common prefix/suffix */
 static u_char *chrtran;		/* translation table for case-folding */
 static struct context_vec *context_vec_start;
@@ -213,9 +214,13 @@ static int  fetch(long *, int, int, FILE *, int, int);
 static int  newcand(int, int, int);
 static int  search(int *, int, int);
 static int  skipline(FILE *);
+static int  isqrt(int);
 static int  stone(int *, int, int *, int *);
 static int  readhash(FILE *);
 static int  files_differ(FILE *, FILE *, int);
+static __inline int min(int, int);
+static __inline int max(int, int);
+
 
 /*
  * chrtran points to one of 2 translation tables: cup2low if folding upper to
@@ -413,7 +418,8 @@ notsame:
 	class = erealloc(class, (slen[0] + 2) * sizeof(int));
 
 	klist = emalloc((slen[0] + 2) * sizeof(int));
-	clist = emalloc(sizeof(cand));
+	clistlen = 100;
+	clist = emalloc(clistlen * sizeof(cand));
 	i = stone(class, slen[0], member, klist);
 	free(member);
 	free(class);
@@ -594,11 +600,33 @@ equiv(struct line *a, int n, struct line *b, int m, int *c)
 	c[j] = -1;
 }
 
+/* Code taken from ping.c */
+static int
+isqrt(int n)
+{
+	int y, x = 1;
+
+	if (n == 0)
+		return(0);
+
+	do { /* newton was a stinker */
+		y = x;
+		x = n / x;
+		x += y;
+		x /= 2;
+	} while ((x - y) > 1 || (x - y) < -1);
+
+	return (x);
+}
+
 static int
 stone(int *a, int n, int *b, int *c)
 {
 	int i, k, y, j, l;
 	int oldc, tc, oldl;
+	u_int loopcount;
+	
+	const u_int bound = dflag ? UINT_MAX : max(256, isqrt(n));
 
 	k = 0;
 	c[0] = newcand(0, 0, 0);
@@ -609,7 +637,9 @@ stone(int *a, int n, int *b, int *c)
 		y = -b[j];
 		oldl = 0;
 		oldc = c[0];
+		loopcount = 0;
 		do {
+			loopcount++;
 			if (y <= clist[oldc].y)
 				continue;
 			l = search(c, k, y);
@@ -627,7 +657,7 @@ stone(int *a, int n, int *b, int *c)
 				k++;
 				break;
 			}
-		} while ((y = b[++j]) > 0);
+		} while ((y = b[++j]) > 0 && loopcount < bound);
 	}
 	return (k);
 }
@@ -637,12 +667,15 @@ newcand(int x, int y, int pred)
 {
 	struct cand *q;
 
-	clist = erealloc(clist, ++clen * sizeof(cand));
-	q = clist + clen - 1;
+	if (clen == clistlen) {
+		clistlen = clistlen * 11 / 10;
+		clist = erealloc(clist, clistlen * sizeof(cand));
+	}
+	q = clist + clen;
 	q->x = x;
 	q->y = y;
 	q->pred = pred;
-	return (clen - 1);
+	return (clen++);
 }
 
 static int