Faster zend_memnstr for long text

3 files changed, 71 insertions, 13 deletions

diff --git a/UPGRADING b/UPGRADING
index 3cdf4f5a2e..4e1baaca5b 100644
--- a/UPGRADING
+++ b/UPGRADING
@@ -54,6 +54,7 @@ PHP X.Y UPGRADE NOTES
   . zend_function.common.num_args don't include the variadic argument anymore.
   . ob_start() no longer issues an E_ERROR, but instead an E_RECOVERABLE_ERROR in case an 
     output buffer is created in an output buffer handler.
+  . Add zend_memnstr_ex, which is based on string matching sunday algo.
 
 - DBA
   . dba_delete() now returns false if the key was not found for the inifile
diff --git a/Zend/zend_operators.c b/Zend/zend_operators.c
index 95f82ecfe8..052623b97e 100644
--- a/Zend/zend_operators.c
+++ b/Zend/zend_operators.c
@@ -2620,11 +2620,12 @@ ZEND_API zend_string *zend_long_to_str(zend_long num) /* {{{ */
 }
 /* }}} */
 
-ZEND_API zend_uchar is_numeric_str_function(const zend_string *str, zend_long *lval, double *dval) {
+ZEND_API zend_uchar is_numeric_str_function(const zend_string *str, zend_long *lval, double *dval) /* {{{ */ {
     return is_numeric_string_ex(str->val, str->len, lval, dval, -1, NULL);
 }
+/* }}} */
 
-ZEND_API zend_uchar _is_numeric_string_ex(const char *str, size_t length, zend_long *lval, double *dval, int allow_errors, int *oflow_info)
+ZEND_API zend_uchar _is_numeric_string_ex(const char *str, size_t length, zend_long *lval, double *dval, int allow_errors, int *oflow_info) /* {{{ */
 {
 	const char *ptr;
 	int base = 10, digits = 0, dp_or_e = 0;
@@ -2760,6 +2761,56 @@ process_double:
 		return IS_DOUBLE;
 	}
 }
+/* }}} */
+
+static zend_always_inline void zend_memstr_ex_pre(unsigned int td[], const char *needle, size_t needle_len) /* {{{ */ {
+	int i;
+
+	for (i = 0; i < 256; i++) {
+		td[i] = needle_len + 1;
+	}
+
+	for (i = 0; i < needle_len; i++) {
+		td[(unsigned char)needle[i]] = (int)needle_len - i;
+	}
+}
+/* }}} */
+
+/* 
+ * String matching - Sunday algorithm
+ * http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
+ */
+ZEND_API const char* zend_memnstr_ex(const char *haystack, const char *needle, size_t needle_len, char *end) /* {{{ */
+{
+	unsigned int td[256];
+	register size_t i;
+	const unsigned register char *p;
+
+	if (needle_len == 0 || (end - haystack) == 0) {
+		return NULL;
+	}
+
+	zend_memstr_ex_pre(td, needle, needle_len);
+
+	p = (const unsigned char *)haystack;
+	end -= needle_len;
+
+	while (p <= (unsigned char *)end) {
+		for (i = 0; i < needle_len; i++) {
+			if (needle[i] != p[i]) {
+				break;
+			}
+		}
+		if (i == needle_len) {
+			return (const char *)p;
+		}
+		p += td[p[needle_len]];
+	}
+
+	return NULL;
+}
+/* }}} */
+
 
 /*
  * Local variables:
diff --git a/Zend/zend_operators.h b/Zend/zend_operators.h
index 58c5958859..ccbadc6f23 100644
--- a/Zend/zend_operators.h
+++ b/Zend/zend_operators.h
@@ -87,6 +87,8 @@ ZEND_API zend_bool instanceof_function(const zend_class_entry *instance_ce, cons
  */
 ZEND_API zend_uchar _is_numeric_string_ex(const char *str, size_t length, zend_long *lval, double *dval, int allow_errors, int *oflow_info);
 
+ZEND_API const char* zend_memnstr_ex(const char *haystack, const char *needle, size_t needle_len, char *end);
+
 END_EXTERN_C()
 
 #if SIZEOF_ZEND_LONG == 4
@@ -181,23 +183,27 @@ zend_memnstr(const char *haystack, const char *needle, size_t needle_len, char *
 		return NULL;
 	}
 
-	end -= needle_len;
+	if (EXPECTED(off_s < 1024 || needle_len < 3)) {
+		end -= needle_len;
 
-	while (p <= end) {
-		if ((p = (char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
-			if (!memcmp(needle, p, needle_len-1)) {
-				return p;
+		while (p <= end) {
+			if ((p = (char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
+				if (!memcmp(needle, p, needle_len-1)) {
+					return p;
+				}
+			}
+
+			if (p == NULL) {
+				return NULL;
 			}
-		}
 
-		if (p == NULL) {
-			return NULL;
+			p++;
 		}
 
-		p++;
+		return NULL;
+	} else {
+		return zend_memnstr_ex(haystack, needle, needle_len, end);
 	}
-
-	return NULL;
 }
 
 static zend_always_inline const void *zend_memrchr(const void *s, int c, size_t n)