From: Zhaoxiu Zeng <[email protected]> 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 <[email protected]> --- 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
