1 files changed, 53 insertions, 6 deletions

diff --git a/lib/libc/regex/engine.c b/lib/libc/regex/engine.c
index be569b19afe7..04844ba6f437 100644
--- a/lib/libc/regex/engine.c
+++ b/lib/libc/regex/engine.c
@@ -35,6 +35,8 @@
  * SUCH DAMAGE.
  *
  *	@(#)engine.c	8.5 (Berkeley) 3/20/94
+ *
+ * $FreeBSD$
  */
 
 /*
@@ -152,6 +154,13 @@ int eflags;
 	register const sopno gl = g->laststate;
 	char *start;
 	char *stop;
+	/* Boyer-Moore algorithms variables */
+	register char *pp;
+	int cj, mj;
+	register char *mustfirst;
+	register char *mustlast;
+	register int *matchjump;
+	register int *charjump;
 
 	/* simplify the situation where possible */
 	if (g->cflags&REG_NOSUB)
@@ -168,12 +177,46 @@ int eflags;
 
 	/* prescreening; this does wonders for this rather slow code */
 	if (g->must != NULL) {
-		for (dp = start; dp < stop; dp++)
-			if (*dp == g->must[0] && stop - dp >= g->mlen &&
-				memcmp(dp, g->must, (size_t)g->mlen) == 0)
-				break;
-		if (dp == stop)		/* we didn't find g->must */
-			return(REG_NOMATCH);
+		if (g->charjump != NULL && g->matchjump != NULL) {
+			mustfirst = g->must;
+			mustlast = g->must + g->mlen - 1;
+			charjump = g->charjump;
+			matchjump = g->matchjump;
+			pp = mustlast;
+			for (dp = start+g->mlen-1; dp < stop;) {
+				/* Fast skip non-matches */
+				while (dp < stop && charjump[*dp])
+					dp += charjump[*dp];
+
+				if (dp >= stop)
+					break;
+
+				/* Greedy matcher */
+				/* We depend on not being used for
+				 * for strings of length 1
+				 */
+				while (*--dp == *--pp && pp != mustfirst);
+
+				if (*dp == *pp)
+					break;
+
+				/* Jump to next possible match */
+				mj = matchjump[pp - mustfirst];
+				cj = charjump[*dp];
+				dp += (cj < mj ? mj : cj);
+				pp = mustlast;
+			}
+			if (pp != mustfirst)
+				return(REG_NOMATCH);
+		} else {
+			for (dp = start; dp < stop; dp++)
+				if (*dp == g->must[0] &&
+				    stop - dp >= g->mlen &&
+				    memcmp(dp, g->must, (size_t)g->mlen) == 0)
+					break;
+			if (dp == stop)		/* we didn't find g->must */
+				return(REG_NOMATCH);
+		}
 	}
 
 	/* match struct setup */
@@ -191,6 +234,10 @@ int eflags;
 	SETUP(m->empty);
 	CLEAR(m->empty);
 
+	/* Adjust start according to moffset, to speed things up */
+	if (g->moffset > -1)
+		start = ((dp - g->moffset) < start) ? start : dp - g->moffset;
+
 	/* this loop does only one repetition except for backrefs */
 	for (;;) {
 		endp = fast(m, start, stop, gf, gl);