[PATCH 1/1] lib: use sunday algorithm to do strstr() and strnstr()
From: Zhaoxiu Zeng
Date: Sun Jul 22 2018 - 13:39:35 EST
From: Zhaoxiu Zeng <zhaoxiu.zeng@xxxxxxxxx>
The Sunday algorithm is a variation of Boyer-Moore algorithm, it is easy and fast.
For the Sunday algorithm, to see
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
Signed-off-by: Zhaoxiu Zeng <zhaoxiu.zeng@xxxxxxxxx>
---
lib/string.c | 92 +++++++++++++++++++++++++++++++++++++++++++++-------
1 file changed, 81 insertions(+), 11 deletions(-)
diff --git a/lib/string.c b/lib/string.c
index 2c0900a5d51a..ed4ab9ee3373 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -898,19 +898,51 @@ EXPORT_SYMBOL(memscan);
*/
char *strstr(const char *s1, const char *s2)
{
- size_t l1, l2;
+ size_t l2;
+ const char *pchk = s1;
+#ifdef __HAVE_ARCH_STRLEN
l2 = strlen(s2);
+#else
+ for (l2 = 0; s2[l2] != 0; l2++)
+ /* nothing */;
+#endif
if (!l2)
return (char *)s1;
- l1 = strlen(s1);
- while (l1 >= l2) {
- l1--;
- if (!memcmp(s1, s2, l2))
+
+ /*
+ * Sunday matching
+ */
+ while (1) {
+ size_t i;
+ char k;
+
+ /* compare */
+ for (i = 0; i < l2; i++) {
+ if (s1[i] != s2[i])
+ break;
+ }
+ if (i >= l2)
return (char *)s1;
- s1++;
+
+ /* if s1 terminate early? */
+ if (pchk < s1 + i)
+ pchk = s1 + i;
+ do {
+ k = *pchk;
+ if (k == 0)
+ return NULL;
+ } while (pchk++ != s1 + l2);
+
+ /* find the k's last presence in s2 (k = s1[l2]) */
+ for (i = l2; --i != (size_t)-1; ) {
+ if (k == s2[i])
+ break;
+ }
+
+ /* shift */
+ s1 += l2 - i;
}
- return NULL;
}
EXPORT_SYMBOL(strstr);
#endif
@@ -925,16 +957,54 @@ EXPORT_SYMBOL(strstr);
char *strnstr(const char *s1, const char *s2, size_t len)
{
size_t l2;
+ const char *pchk = s1;
+#ifdef __HAVE_ARCH_STRLEN
l2 = strlen(s2);
+#else
+ for (l2 = 0; s2[l2] != 0; l2++)
+ /* nothing */;
+#endif
if (!l2)
return (char *)s1;
+
+ /*
+ * Sunday matching
+ */
while (len >= l2) {
- len--;
- if (!memcmp(s1, s2, l2))
- return (char *)s1;
- s1++;
+ size_t i;
+ char k;
+
+ /* compare */
+ for (i = 0; i < l2; i++) {
+ if (s1[i] != s2[i])
+ break;
+ }
+ if (i >= l2)
+ return (char *)s1;
+ if (len == l2)
+ break;
+
+ /* if s1 terminate early? */
+ if (pchk < s1 + i)
+ pchk = s1 + i;
+ do {
+ k = *pchk;
+ if (k == 0)
+ return NULL;
+ } while (pchk++ != s1 + l2);
+
+ /* find the k's last presence in s2 (k = s1[l2]) */
+ for (i = l2; --i != (size_t)-1; ) {
+ if (k == s2[i])
+ break;
+ }
+
+ /* shift */
+ s1 += l2 - i;
+ len -= l2 - i;
}
+
return NULL;
}
EXPORT_SYMBOL(strnstr);
--
2.17.1