Faster strrpos implementation

2 files changed, 96 insertions, 17 deletions

diff --git a/Zend/zend_operators.c b/Zend/zend_operators.c
index 052623b97e..3bbe0ce924 100644
--- a/Zend/zend_operators.c
+++ b/Zend/zend_operators.c
@@ -2763,54 +2763,96 @@ process_double:
 }
 /* }}} */
 
-static zend_always_inline void zend_memstr_ex_pre(unsigned int td[], const char *needle, size_t needle_len) /* {{{ */ {
+/* 
+ * String matching - Sunday algorithm
+ * http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
+ */
+static zend_always_inline void zend_memnstr_ex_pre(unsigned int td[], const char *needle, size_t needle_len, int reverse) /* {{{ */ {
 	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;
+	if (reverse) {
+		for (i = needle_len - 1; i >= 0; i--) {
+			td[(unsigned char)needle[i]] = i + 1;
+		}
+	} else {
+		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;
+	register const char *p;
 
 	if (needle_len == 0 || (end - haystack) == 0) {
 		return NULL;
 	}
 
-	zend_memstr_ex_pre(td, needle, needle_len);
+	zend_memnstr_ex_pre(td, needle, needle_len, 0);
 
-	p = (const unsigned char *)haystack;
+	p = haystack;
 	end -= needle_len;
 
-	while (p <= (unsigned char *)end) {
+	while (p <= end) {
 		for (i = 0; i < needle_len; i++) {
 			if (needle[i] != p[i]) {
 				break;
 			}
 		}
 		if (i == needle_len) {
-			return (const char *)p;
+			return p;
 		}
-		p += td[p[needle_len]];
+		p += td[(unsigned char)(p[needle_len])];
 	}
 
 	return NULL;
 }
 /* }}} */
 
+ZEND_API const char* zend_memnrstr_ex(const char *haystack, const char *needle, size_t needle_len, char *end) /* {{{ */
+{
+	unsigned int td[256];
+	register size_t i;
+	register const char *p;
+
+	if (needle_len == 0 || (end - haystack) == 0) {
+		return NULL;
+	}
+
+	zend_memnstr_ex_pre(td, needle, needle_len, 1);
+
+	p = end;
+	p -= needle_len;
+
+	while (p >= haystack) {
+		for (i = 0; i < needle_len; i++) {
+			if (needle[i] != p[i]) {
+				break;
+			}
+		}
+
+		if (i == needle_len) {
+			return (const char *)p;
+		}
+		
+		if (p == haystack) {
+			return NULL;
+		}
+
+		p -= td[(unsigned char)(p[-1])];
+	}
+
+	return NULL;
+}
+/* }}} */
 
 /*
  * Local variables:
diff --git a/Zend/zend_operators.h b/Zend/zend_operators.h
index ccbadc6f23..d57c4f59b1 100644
--- a/Zend/zend_operators.h
+++ b/Zend/zend_operators.h
@@ -88,6 +88,7 @@ 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);
+ZEND_API const char* zend_memnrstr_ex(const char *haystack, const char *needle, size_t needle_len, char *end);
 
 END_EXTERN_C()
 
@@ -174,11 +175,12 @@ zend_memnstr(const char *haystack, const char *needle, size_t needle_len, char *
 	size_t off_s;
 
 	if (needle_len == 1) {
-		return (char *)memchr(p, *needle, (end-p));
+		return (const char *)memchr(p, *needle, (end-p));
 	}
 
 	off_p = end - haystack;
 	off_s = (off_p > 0) ? (size_t)off_p : 0;
+
 	if (needle_len > off_s) {
 		return NULL;
 	}
@@ -187,7 +189,7 @@ zend_memnstr(const char *haystack, const char *needle, size_t needle_len, char *
 		end -= needle_len;
 
 		while (p <= end) {
-			if ((p = (char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
+			if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
 				if (!memcmp(needle, p, needle_len-1)) {
 					return p;
 				}
@@ -209,7 +211,6 @@ zend_memnstr(const char *haystack, const char *needle, size_t needle_len, char *
 static zend_always_inline const void *zend_memrchr(const void *s, int c, size_t n)
 {
 	register const unsigned char *e;
-
 	if (n <= 0) {
 		return NULL;
 	}
@@ -219,10 +220,46 @@ static zend_always_inline const void *zend_memrchr(const void *s, int c, size_t
 			return (const void *)e;
 		}
 	}
-
 	return NULL;
 }
 
+
+static zend_always_inline const char *
+zend_memnrstr(const char *haystack, const char *needle, size_t needle_len, char *end)
+{
+    const char *p = end;
+    const char ne = needle[needle_len-1];
+    ptrdiff_t off_p;
+    size_t off_s;
+
+    if (needle_len == 1) {
+        return (const char *)zend_memrchr(haystack, *needle, (p - haystack));
+    }
+
+    off_p = end - haystack;
+    off_s = (off_p > 0) ? (size_t)off_p : 0;
+
+    if (needle_len > off_s) {
+        return NULL;
+    }
+
+	if (EXPECTED(off_s < 1024 || needle_len < 3)) {
+		p -= needle_len;
+
+		do {
+			if ((p = (const char *)zend_memrchr(haystack, *needle, (p - haystack) + 1)) && ne == p[needle_len-1]) {
+				if (!memcmp(needle, p, needle_len - 1)) {
+					return p;
+				}
+			}
+		} while (p-- >= haystack);
+
+		return NULL;
+	} else {
+		return zend_memnrstr_ex(haystack, needle, needle_len, end);
+	}
+}
+
 BEGIN_EXTERN_C()
 ZEND_API int increment_function(zval *op1);
 ZEND_API int decrement_function(zval *op2);