[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
wcsstr: Ensure worst-case linear execution time
|
From: |
Bruno Haible |
|
Subject: |
wcsstr: Ensure worst-case linear execution time |
|
Date: |
Mon, 27 Mar 2023 15:49:02 +0200 |
The same two-way algorithm
<https://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260>
that provides worst-case linear execution time for strstr() and memmem()
also provides worst-case linear execution time for wcsstr(). Only the
"shift table" optimization that Eric Blake added into it doesn't apply,
because the shift table would be way too large.
Since, so far, only musl libc has a worst-case linear wcsstr() function
— also based on the two-way algorithm —, it makes sense to add this fast
algorithm to wcsstr(), like we already did for strstr() and strcasestr()
many years ago.
2023-03-27 Bruno Haible <bruno@clisp.org>
wcsstr: Ensure worst-case linear execution time.
* lib/wchar.in.h (wcsstr): Consider REPLACE_WCSSTR.
* lib/wcs-two-way.h: New file, based on lib/str-two-way.h.
* lib/wcsstr-impl.h: If requested, use the two-way algorithm. New code
based on lib/strstr.c.
* m4/wcsstr.m4 (gl_FUNC_WCSSTR_SIMPLE): Renamed from gl_FUNC_WCSSTR.
(gl_FUNC_WCSSTR): New macro, based on gl_FUNC_STRSTR in m4/strstr.m4.
* m4/wchar_h.m4 (gl_WCHAR_H_DEFAULTS): Initialize REPLACE_WCSSTR.
* modules/wchar (Makefile.am): Substitute REPLACE_WCSSTR.
* modules/wcsstr-simple: New file, based on modules/wcsstr.
* modules/wcsstr (Description): Document that this module now provides
an efficient implementation.
(Files): Add lib/wcs-two-way.h.
(Depends-on): Depend on wcsstr-simple and the dependencies of the
two-way implementation.
(configure.ac): Use AC_LIBOBJ instead of a conditional. Don't invoke
gl_WCHAR_MODULE_INDICATOR.
(Makefile.am): Don't augment lib_SOURCES.
* tests/test-wcsstr.c: New file, based on tests/test-strstr.c.
* modules/wcsstr-tests: New file, based on modules/strstr-tests.
* doc/posix-functions/wcsstr.texi: Mention the worst-case complexity.
Mention the new 'wcsstr-simple' module.
* doc/posix-functions/strstr.texi: Fix typo.
diff --git a/doc/posix-functions/strstr.texi b/doc/posix-functions/strstr.texi
index 1b124a0e53..3a36cfdeed 100644
--- a/doc/posix-functions/strstr.texi
+++ b/doc/posix-functions/strstr.texi
@@ -21,7 +21,7 @@
glibc 2.28.
@end itemize
-Portability problems fixed by Gnulib @code{strstr}:
+Portability problems fixed by Gnulib module @code{strstr}:
@itemize
@item
This function has quadratic instead of linear worst-case complexity on some
diff --git a/doc/posix-functions/wcsstr.texi b/doc/posix-functions/wcsstr.texi
index c5711d0821..e69a036658 100644
--- a/doc/posix-functions/wcsstr.texi
+++ b/doc/posix-functions/wcsstr.texi
@@ -4,15 +4,23 @@
POSIX specification:@*
@url{https://pubs.opengroup.org/onlinepubs/9699919799/functions/wcsstr.html}
-Gnulib module: wcsstr
+Gnulib module: wcsstr or wcsstr-simple
-Portability problems fixed by Gnulib:
+Portability problems fixed by either Gnulib module @code{wcsstr-simple} or
@code{wcsstr}:
@itemize
@item
This function is missing on some platforms:
HP-UX 11.00.
@end itemize
+Portability problems fixed by Gnulib module @code{wcsstr}:
+@itemize
+@item
+This function has quadratic instead of linear worst-case complexity on some
+platforms:
+glibc 2.37, macOS 12.5, FreeBSD 13.1, NetBSD 9.0, OpenBSD 7.2, AIX 7.2, HP-UX
11, IRIX 6.5, Solaris 11.4, Cygwin 2.9.0, mingw, MSVC 14.
+@end itemize
+
Portability problems not fixed by Gnulib:
@itemize
@item
diff --git a/lib/wchar.in.h b/lib/wchar.in.h
index 2beddd780f..194a1c6723 100644
--- a/lib/wchar.in.h
+++ b/lib/wchar.in.h
@@ -1234,12 +1234,25 @@ _GL_WARN_ON_USE (wcspbrk, "wcspbrk is unportable - "
/* Find the first occurrence of NEEDLE in HAYSTACK. */
#if @GNULIB_WCSSTR@
-# if !@HAVE_WCSSTR@
+# if @REPLACE_WCSSTR@
+# if !(defined __cplusplus && defined GNULIB_NAMESPACE)
+# undef wcsstr
+# define wcsstr rpl_wcsstr
+# endif
+_GL_FUNCDECL_RPL (wcsstr, wchar_t *,
+ (const wchar_t *restrict haystack,
+ const wchar_t *restrict needle)
+ _GL_ATTRIBUTE_PURE);
+_GL_CXXALIAS_RPL (wcsstr, wchar_t *,
+ (const wchar_t *restrict haystack,
+ const wchar_t *restrict needle));
+# else
+# if !@HAVE_WCSSTR@
_GL_FUNCDECL_SYS (wcsstr, wchar_t *,
(const wchar_t *restrict haystack,
const wchar_t *restrict needle)
_GL_ATTRIBUTE_PURE);
-# endif
+# endif
/* On some systems, this function is defined as an overloaded function:
extern "C++" {
const wchar_t * std::wcsstr (const wchar_t *, const wchar_t *);
@@ -1250,6 +1263,7 @@ _GL_CXXALIAS_SYS_CAST2 (wcsstr,
(const wchar_t *restrict, const wchar_t *restrict),
const wchar_t *,
(const wchar_t *restrict, const wchar_t *restrict));
+# endif
# if ((__GLIBC__ == 2 && __GLIBC_MINOR__ >= 10) && !defined __UCLIBC__) \
&& (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4))
_GL_CXXALIASWARN1 (wcsstr, wchar_t *,
diff --git a/lib/wcs-two-way.h b/lib/wcs-two-way.h
new file mode 100644
index 0000000000..0879026f2b
--- /dev/null
+++ b/lib/wcs-two-way.h
@@ -0,0 +1,303 @@
+/* Wide character substring search, using the Two-Way algorithm.
+ Copyright (C) 2008-2023 Free Software Foundation, Inc.
+ This file is part of the GNU C Library.
+ Written by Eric Blake <ebb9@byu.net>, 2008.
+
+ This file is free software: you can redistribute it and/or modify
+ it under the terms of the GNU Lesser General Public License as
+ published by the Free Software Foundation; either version 2.1 of the
+ License, or (at your option) any later version.
+
+ This file is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU Lesser General Public License for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+/* Before including this file, you need to include <config.h> and
+ <string.h>, and define:
+ RETURN_TYPE A macro that expands to the return type.
+ AVAILABLE(h, h_l, j, n_l)
+ A macro that returns nonzero if there are
+ at least N_L characters left starting at H[J].
+ H is 'wchar_t *', H_L, J, and N_L
+ are 'size_t'; H_L is an lvalue. For
+ NUL-terminated searches, H_L can be
+ modified each iteration to avoid having
+ to compute the end of H up front.
+
+ For case-insensitivity, you may optionally define:
+ CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L
+ characters of P1 and P2 are equal.
+ CANON_ELEMENT(c) A macro that canonicalizes an element right after
+ it has been fetched from one of the two strings.
+ The argument is a 'wchar_t'; the result
+ must be a 'wchar_t' as well.
+
+ This file undefines the macros documented above, and defines
+ LONG_NEEDLE_THRESHOLD.
+*/
+
+#include <limits.h>
+#include <stdint.h>
+
+/* We use the Two-Way string matching algorithm (also known as
+ Chrochemore-Perrin), which guarantees linear complexity with
+ constant space.
+
+ See https://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
+*/
+
+#ifndef MAX
+# define MAX(a, b) ((a < b) ? (b) : (a))
+#endif
+
+#ifndef CANON_ELEMENT
+# define CANON_ELEMENT(c) c
+#endif
+#ifndef CMP_FUNC
+# define CMP_FUNC wmemcmp
+#endif
+
+/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
+ Return the index of the first character in the right half, and set
+ *PERIOD to the global period of the right half.
+
+ The global period of a string is the smallest index (possibly its
+ length) at which all remaining bytes in the string are repetitions
+ of the prefix (the last repetition may be a subset of the prefix).
+
+ When NEEDLE is factored into two halves, a local period is the
+ length of the smallest word that shares a suffix with the left half
+ and shares a prefix with the right half. All factorizations of a
+ non-empty NEEDLE have a local period of at least 1 and no greater
+ than NEEDLE_LEN.
+
+ A critical factorization has the property that the local period
+ equals the global period. All strings have at least one critical
+ factorization with the left half smaller than the global period.
+ And while some strings have more than one critical factorization,
+ it is provable that with an ordered alphabet, at least one of the
+ critical factorizations corresponds to a maximal suffix.
+
+ Given an ordered alphabet, a critical factorization can be computed
+ in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
+ shorter of two ordered maximal suffixes. The ordered maximal
+ suffixes are determined by lexicographic comparison while tracking
+ periodicity. */
+static size_t
+critical_factorization (const wchar_t *needle, size_t needle_len,
+ size_t *period)
+{
+ /* Index of last character of left half, or SIZE_MAX. */
+ size_t max_suffix, max_suffix_rev;
+ size_t j; /* Index into NEEDLE for current candidate suffix. */
+ size_t k; /* Offset into current period. */
+ size_t p; /* Intermediate period. */
+ wchar_t a, b; /* Current comparison characters. */
+
+ /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
+ out 0-length needles. */
+ if (needle_len < 3)
+ {
+ *period = 1;
+ return needle_len - 1;
+ }
+
+ /* Invariants:
+ 0 <= j < NEEDLE_LEN - 1
+ -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
+ min(max_suffix, max_suffix_rev) < global period of NEEDLE
+ 1 <= p <= global period of NEEDLE
+ p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
+ 1 <= k <= p
+ */
+
+ /* Perform lexicographic search. */
+ max_suffix = SIZE_MAX;
+ j = 0;
+ k = p = 1;
+ while (j + k < needle_len)
+ {
+ a = CANON_ELEMENT (needle[j + k]);
+ b = CANON_ELEMENT (needle[max_suffix + k]);
+ if (a < b)
+ {
+ /* Suffix is smaller, period is entire prefix so far. */
+ j += k;
+ k = 1;
+ p = j - max_suffix;
+ }
+ else if (a == b)
+ {
+ /* Advance through repetition of the current period. */
+ if (k != p)
+ ++k;
+ else
+ {
+ j += p;
+ k = 1;
+ }
+ }
+ else /* b < a */
+ {
+ /* Suffix is larger, start over from current location. */
+ max_suffix = j++;
+ k = p = 1;
+ }
+ }
+ *period = p;
+
+ /* Perform reverse lexicographic search. */
+ max_suffix_rev = SIZE_MAX;
+ j = 0;
+ k = p = 1;
+ while (j + k < needle_len)
+ {
+ a = CANON_ELEMENT (needle[j + k]);
+ b = CANON_ELEMENT (needle[max_suffix_rev + k]);
+ if (b < a)
+ {
+ /* Suffix is smaller, period is entire prefix so far. */
+ j += k;
+ k = 1;
+ p = j - max_suffix_rev;
+ }
+ else if (a == b)
+ {
+ /* Advance through repetition of the current period. */
+ if (k != p)
+ ++k;
+ else
+ {
+ j += p;
+ k = 1;
+ }
+ }
+ else /* a < b */
+ {
+ /* Suffix is larger, start over from current location. */
+ max_suffix_rev = j++;
+ k = p = 1;
+ }
+ }
+
+ /* Choose the shorter suffix. Return the index of the first character
+ of the right half, rather than the last character of the left half.
+
+ For some examples, 'banana' has two critical factorizations, both
+ exposed by the two lexicographic extreme suffixes of 'anana' and
+ 'nana', where both suffixes have a period of 2. On the other
+ hand, with 'aab' and 'bba', both strings have a single critical
+ factorization of the last character, with the suffix having a period
+ of 1. While the maximal lexicographic suffix of 'aab' is 'b',
+ the maximal lexicographic suffix of 'bba' is 'ba', which is not a
+ critical factorization. Conversely, the maximal reverse
+ lexicographic suffix of 'a' works for 'bba', but not 'ab' for
+ 'aab'. The shorter suffix of the two will always be a critical
+ factorization. */
+ if (max_suffix_rev + 1 < max_suffix + 1)
+ return max_suffix + 1;
+ *period = p;
+ return max_suffix_rev + 1;
+}
+
+/* Return the first location of non-empty NEEDLE within HAYSTACK, or
+ NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
+ method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
+ Performance is guaranteed to be linear, with an initialization cost
+ of 2 * NEEDLE_LEN comparisons.
+
+ If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
+ most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
+ If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
+ HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
+static RETURN_TYPE _GL_ATTRIBUTE_PURE
+two_way_short_needle (const wchar_t *haystack, size_t haystack_len,
+ const wchar_t *needle, size_t needle_len)
+{
+ size_t i; /* Index into current character of NEEDLE. */
+ size_t j; /* Index into current window of HAYSTACK. */
+ size_t period; /* The period of the right half of needle. */
+ size_t suffix; /* The index of the right half of needle. */
+
+ /* Factor the needle into two halves, such that the left half is
+ smaller than the global period, and the right half is
+ periodic (with a period as large as NEEDLE_LEN - suffix). */
+ suffix = critical_factorization (needle, needle_len, &period);
+
+ /* Perform the search. Each iteration compares the right half
+ first. */
+ if (CMP_FUNC (needle, needle + period, suffix) == 0)
+ {
+ /* Entire needle is periodic; a mismatch in the left half can
+ only advance by the period, so use memory to avoid rescanning
+ known occurrences of the period in the right half. */
+ size_t memory = 0;
+ j = 0;
+ while (AVAILABLE (haystack, haystack_len, j, needle_len))
+ {
+ /* Scan for matches in right half. */
+ i = MAX (suffix, memory);
+ while (i < needle_len && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ ++i;
+ if (needle_len <= i)
+ {
+ /* Scan for matches in left half. */
+ i = suffix - 1;
+ while (memory < i + 1 && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ --i;
+ if (i + 1 < memory + 1)
+ return (RETURN_TYPE) (haystack + j);
+ /* No match, so remember how many repetitions of period
+ on the right half were scanned. */
+ j += period;
+ memory = needle_len - period;
+ }
+ else
+ {
+ j += i - suffix + 1;
+ memory = 0;
+ }
+ }
+ }
+ else
+ {
+ /* The two halves of needle are distinct; no extra memory is
+ required, and any mismatch results in a maximal shift. */
+ period = MAX (suffix, needle_len - suffix) + 1;
+ j = 0;
+ while (AVAILABLE (haystack, haystack_len, j, needle_len))
+ {
+ /* Scan for matches in right half. */
+ i = suffix;
+ while (i < needle_len && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ ++i;
+ if (needle_len <= i)
+ {
+ /* Scan for matches in left half. */
+ i = suffix - 1;
+ while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
+ == CANON_ELEMENT (haystack[i + j])))
+ --i;
+ if (i == SIZE_MAX)
+ return (RETURN_TYPE) (haystack + j);
+ j += period;
+ }
+ else
+ j += i - suffix + 1;
+ }
+ }
+ return NULL;
+}
+
+#undef AVAILABLE
+#undef CANON_ELEMENT
+#undef CMP_FUNC
+#undef MAX
+#undef RETURN_TYPE
diff --git a/lib/wcsstr-impl.h b/lib/wcsstr-impl.h
index c0eaa8575a..ccd64672b4 100644
--- a/lib/wcsstr-impl.h
+++ b/lib/wcsstr-impl.h
@@ -1,6 +1,5 @@
/* Locate a substring in a wide string.
Copyright (C) 1999, 2011-2023 Free Software Foundation, Inc.
- Written by Bruno Haible <bruno@clisp.org>, 1999.
This file is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as
@@ -15,6 +14,56 @@
You should have received a copy of the GNU Lesser General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>. */
+/* Written by Bruno Haible, 1999, and Eric Blake, 2008. */
+
+#if NEED_LINEAR_WCSSTR
+
+/* Use Two-Way algorithm, worst-case O(n+m). */
+
+# define RETURN_TYPE wchar_t *
+# define AVAILABLE(h, h_l, j, n_l) \
+ (!wmemchr ((h) + (h_l), L'\0', (j) + (n_l) - (h_l)) \
+ && ((h_l) = (j) + (n_l)))
+# include "wcs-two-way.h"
+
+wchar_t *
+wcsstr (const wchar_t *haystack_start, const wchar_t *needle_start)
+{
+ const wchar_t *haystack = haystack_start;
+ const wchar_t *needle = needle_start;
+ size_t needle_len; /* Length of NEEDLE. */
+ size_t haystack_len; /* Known minimum length of HAYSTACK. */
+ bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */
+
+ /* Determine length of NEEDLE, and in the process, make sure
+ HAYSTACK is at least as long (no point processing all of a long
+ NEEDLE if HAYSTACK is too short). */
+ while (*haystack && *needle)
+ ok &= *haystack++ == *needle++;
+ if (*needle)
+ return NULL;
+ if (ok)
+ return (wchar_t *) haystack_start;
+
+ /* Reduce the size of haystack using wcschr, since it has a smaller
+ linear coefficient than the Two-Way algorithm. */
+ needle_len = needle - needle_start;
+ haystack = wcschr (haystack_start + 1, *needle_start);
+ if (!haystack || __builtin_expect (needle_len == 1, 0))
+ return (wchar_t *) haystack;
+ needle -= needle_len;
+ haystack_len = (haystack > haystack_start + needle_len ? 1
+ : needle_len + haystack_start - haystack);
+
+ /* Perform the search. */
+ return two_way_short_needle (haystack, haystack_len,
+ needle, needle_len);
+}
+
+#else
+
+/* Use simple implementation, worst-case O(nm). */
+
wchar_t *
wcsstr (const wchar_t *haystack, const wchar_t *needle)
{
@@ -49,3 +98,5 @@ wcsstr (const wchar_t *haystack, const wchar_t *needle)
return NULL;
}
+
+#endif
diff --git a/m4/wchar_h.m4 b/m4/wchar_h.m4
index ad3d4ecbb4..8cc38ef804 100644
--- a/m4/wchar_h.m4
+++ b/m4/wchar_h.m4
@@ -7,7 +7,7 @@
dnl Written by Eric Blake.
-# wchar_h.m4 serial 56
+# wchar_h.m4 serial 57
AC_DEFUN_ONCE([gl_WCHAR_H],
[
@@ -253,6 +253,7 @@ AC_DEFUN([gl_WCHAR_H_DEFAULTS]
REPLACE_WCWIDTH=0; AC_SUBST([REPLACE_WCWIDTH])
REPLACE_WCSWIDTH=0; AC_SUBST([REPLACE_WCSWIDTH])
REPLACE_WCSFTIME=0; AC_SUBST([REPLACE_WCSFTIME])
+ REPLACE_WCSSTR=0; AC_SUBST([REPLACE_WCSSTR])
REPLACE_WCSTOK=0; AC_SUBST([REPLACE_WCSTOK])
REPLACE_WMEMPCPY=0; AC_SUBST([REPLACE_WMEMPCPY])
])
diff --git a/m4/wcsstr.m4 b/m4/wcsstr.m4
index 861c88b566..029c90ea66 100644
--- a/m4/wcsstr.m4
+++ b/m4/wcsstr.m4
@@ -1,10 +1,11 @@
-# wcsstr.m4 serial 2
+# wcsstr.m4 serial 3
dnl Copyright (C) 2011-2023 Free Software Foundation, Inc.
dnl This file is free software; the Free Software Foundation
dnl gives unlimited permission to copy and/or distribute it,
dnl with or without modifications, as long as this notice is preserved.
-AC_DEFUN([gl_FUNC_WCSSTR],
+dnl Check that wcsstr exists and works.
+AC_DEFUN([gl_FUNC_WCSSTR_SIMPLE],
[
AC_REQUIRE([gl_WCHAR_H_DEFAULTS])
AC_CHECK_FUNCS_ONCE([wcsstr])
@@ -12,3 +13,61 @@ AC_DEFUN([gl_FUNC_WCSSTR]
HAVE_WCSSTR=0
fi
])
+
+dnl Additionally, check that wcsstr is efficient.
+AC_DEFUN([gl_FUNC_WCSSTR],
+[
+ AC_REQUIRE([gl_FUNC_WCSSTR_SIMPLE])
+ if test $HAVE_WCSSTR = 1; then
+ AC_CACHE_CHECK([whether wcsstr works in linear time],
+ [gl_cv_func_wcsstr_linear],
+ [AC_RUN_IFELSE([AC_LANG_PROGRAM([[
+#include <signal.h> /* for signal */
+#include <wchar.h> /* for wcsstr */
+#include <stdlib.h> /* for malloc */
+#include <unistd.h> /* for alarm */
+static void quit (int sig) { _exit (sig + 128); }
+]], [[
+ int result = 0;
+ size_t m = 1000000;
+ wchar_t *haystack = (wchar_t *) malloc ((2 * m + 2) * sizeof (wchar_t));
+ wchar_t *needle = (wchar_t *) malloc ((m + 2) * sizeof (wchar_t));
+ /* Failure to compile this test due to missing alarm is okay,
+ since all such platforms (mingw) also have quadratic strstr. */
+ signal (SIGALRM, quit);
+ alarm (5);
+ /* Check for quadratic performance. */
+ if (haystack && needle)
+ {
+ size_t i;
+ for (i = 0; i < 2 * m; i++)
+ haystack[i] = L'A';
+ haystack[2 * m] = L'B';
+ haystack[2 * m + 1] = 0;
+ for (i = 0; i < m; i++)
+ needle[i] = L'A';
+ needle[m] = L'B';
+ needle[m + 1] = 0;
+ if (!wcsstr (haystack, needle))
+ result |= 1;
+ }
+ /* Free allocated memory, in case some sanitizer is watching. */
+ free (haystack);
+ free (needle);
+ return result;
+ ]])],
+ [gl_cv_func_wcsstr_linear=yes], [gl_cv_func_wcsstr_linear=no],
+ [gl_cv_func_wcsstr_linear="$gl_cross_guess_normal"])
+ ])
+ case "$gl_cv_func_wcsstr_linear" in
+ *yes) ;;
+ *)
+ REPLACE_WCSSTR=1
+ ;;
+ esac
+ fi
+ if test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1; then
+ AC_DEFINE([NEED_LINEAR_WCSSTR], [1],
+ [Define to 1 to get a worst-case linear time implementation of wcsstr.])
+ fi
+])
diff --git a/modules/wchar b/modules/wchar
index 4a507f0167..feacaffff1 100644
--- a/modules/wchar
+++ b/modules/wchar
@@ -142,6 +142,7 @@ wchar.h: wchar.in.h $(top_builddir)/config.status
$(CXXDEFS_H) $(ARG_NONNULL_H)
-e 's|@''REPLACE_WCWIDTH''@|$(REPLACE_WCWIDTH)|g' \
-e 's|@''REPLACE_WCSWIDTH''@|$(REPLACE_WCSWIDTH)|g' \
-e 's|@''REPLACE_WCSFTIME''@|$(REPLACE_WCSFTIME)|g' \
+ -e 's|@''REPLACE_WCSSTR''@|$(REPLACE_WCSSTR)|g' \
-e 's|@''REPLACE_WCSTOK''@|$(REPLACE_WCSTOK)|g' \
-e 's|@''REPLACE_WMEMPCPY''@|$(REPLACE_WMEMPCPY)|g' \
-e '/definitions of _GL_FUNCDECL_RPL/r $(CXXDEFS_H)' \
diff --git a/modules/wcsstr b/modules/wcsstr
index e2362d8d2b..87ac47fa65 100644
--- a/modules/wcsstr
+++ b/modules/wcsstr
@@ -1,24 +1,26 @@
Description:
-wcsstr() function: locate a substring in a wide string.
+wcsstr() function: efficiently locate a substring in a wide string.
Files:
lib/wcsstr.c
lib/wcsstr-impl.h
+lib/wcs-two-way.h
m4/wcsstr.m4
Depends-on:
-wchar
-wcschr [test $HAVE_WCSSTR = 0]
+wcsstr-simple
+builtin-expect [test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1]
+wcschr [test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1]
+wmemchr [test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1]
+wmemcmp [test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1]
configure.ac:
gl_FUNC_WCSSTR
-gl_CONDITIONAL([GL_COND_OBJ_WCSSTR], [test $HAVE_WCSSTR = 0])
-gl_WCHAR_MODULE_INDICATOR([wcsstr])
+if test $HAVE_WCSSTR = 0 || test $REPLACE_WCSSTR = 1; then
+ AC_LIBOBJ([wcsstr])
+fi
Makefile.am:
-if GL_COND_OBJ_WCSSTR
-lib_SOURCES += wcsstr.c
-endif
Include:
<wchar.h>
diff --git a/modules/wcsstr-simple b/modules/wcsstr-simple
new file mode 100644
index 0000000000..827d50c4f8
--- /dev/null
+++ b/modules/wcsstr-simple
@@ -0,0 +1,29 @@
+Description:
+wcsstr() function: locate a substring in a wide string.
+
+Files:
+lib/wcsstr.c
+lib/wcsstr-impl.h
+m4/wcsstr.m4
+
+Depends-on:
+wchar
+wcschr [test $HAVE_WCSSTR = 0]
+
+configure.ac:
+gl_FUNC_WCSSTR_SIMPLE
+if test $HAVE_WCSSTR = 0; then
+ AC_LIBOBJ([wcsstr])
+fi
+gl_WCHAR_MODULE_INDICATOR([wcsstr])
+
+Makefile.am:
+
+Include:
+<wchar.h>
+
+License:
+LGPL
+
+Maintainer:
+all
diff --git a/modules/wcsstr-tests b/modules/wcsstr-tests
new file mode 100644
index 0000000000..128720f237
--- /dev/null
+++ b/modules/wcsstr-tests
@@ -0,0 +1,22 @@
+Files:
+tests/test-wcsstr.c
+tests/zerosize-ptr.h
+tests/signature.h
+tests/macros.h
+m4/mmap-anon.m4
+
+Depends-on:
+extensions
+getpagesize
+wcscpy
+wmemset
+
+configure.ac:
+AC_CHECK_DECLS_ONCE([alarm])
+gl_FUNC_MMAP_ANON
+AC_CHECK_HEADERS_ONCE([sys/mman.h])
+AC_CHECK_FUNCS_ONCE([mprotect])
+
+Makefile.am:
+TESTS += test-wcsstr
+check_PROGRAMS += test-wcsstr
diff --git a/tests/test-wcsstr.c b/tests/test-wcsstr.c
new file mode 100644
index 0000000000..5bc671124a
--- /dev/null
+++ b/tests/test-wcsstr.c
@@ -0,0 +1,274 @@
+/*
+ * Copyright (C) 2004, 2007-2023 Free Software Foundation, Inc.
+ * Written by Bruno Haible and Eric Blake
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <https://www.gnu.org/licenses/>. */
+
+#include <config.h>
+
+#include <wchar.h>
+
+#include "signature.h"
+SIGNATURE_CHECK (wcsstr, wchar_t *, (wchar_t const *, wchar_t const *));
+
+#include <signal.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "zerosize-ptr.h"
+#include "macros.h"
+
+int
+main (int argc, char *argv[])
+{
+#if HAVE_DECL_ALARM
+ /* Declare failure if test takes too long, by using default abort
+ caused by SIGALRM. All known platforms that lack alarm also have
+ a quadratic wcsstr, and the replacement wcsstr is known to not
+ take too long. */
+ int alarm_value = 50;
+ signal (SIGALRM, SIG_DFL);
+ alarm (alarm_value);
+#endif
+
+ {
+ const wchar_t input[] = L"foo";
+ const wchar_t *result = wcsstr (input, L"");
+ ASSERT (result == input);
+ }
+
+ {
+ const wchar_t input[] = L"foo";
+ const wchar_t *result = wcsstr (input, L"o");
+ ASSERT (result == input + 1);
+ }
+
+ {
+ /* On some platforms, the memchr() functions reads past the first
+ occurrence of the byte to be searched, leading to an out-of-bounds
+ read access for wcsstr().
+ See <https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=521737>.
+ This is a bug in memchr(), see the Austin Group's clarification
+ <https://www.opengroup.org/austin/docs/austin_454.txt>. */
+ const wchar_t *fix = L"aBaaaaaaaaaaax";
+ wchar_t *page_boundary = (wchar_t *) zerosize_ptr ();
+ size_t len = wcslen (fix) + 1;
+ wchar_t *input =
+ page_boundary ? page_boundary - len : malloc (len * sizeof (wchar_t));
+ const wchar_t *result;
+
+ wcscpy (input, fix);
+ result = wcsstr (input, L"B1x");
+ ASSERT (result == NULL);
+ if (!page_boundary)
+ free (input);
+ }
+
+ {
+ const wchar_t input[] = L"ABC ABCDAB ABCDABCDABDE";
+ const wchar_t *result = wcsstr (input, L"ABCDABD");
+ ASSERT (result == input + 15);
+ }
+
+ {
+ const wchar_t input[] = L"ABC ABCDAB ABCDABCDABDE";
+ const wchar_t *result = wcsstr (input, L"ABCDABE");
+ ASSERT (result == NULL);
+ }
+
+ {
+ const wchar_t input[] = L"ABC ABCDAB ABCDABCDABDE";
+ const wchar_t *result = wcsstr (input, L"ABCDABCD");
+ ASSERT (result == input + 11);
+ }
+
+ /* Check that a long periodic needle does not cause false positives. */
+ {
+ const wchar_t input[] = L"F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
+ "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
+ "_C3_A7_20_EF_BF_BD";
+ const wchar_t need[] = L"_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
+ const wchar_t *result = wcsstr (input, need);
+ ASSERT (result == NULL);
+ }
+ {
+ const wchar_t input[] = L"F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
+ "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
+ "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
+ "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
+ const wchar_t need[] = L"_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
+ const wchar_t *result = wcsstr (input, need);
+ ASSERT (result == input + 115);
+ }
+
+ /* Check that a very long haystack is handled quickly if the needle is
+ short and occurs near the beginning. */
+ {
+ size_t repeat = 10000;
+ size_t m = 1000000;
+ const wchar_t *needle =
+ L"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
+ "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
+ wchar_t *haystack = (wchar_t *) malloc ((m + 1) * sizeof (wchar_t));
+ if (haystack != NULL)
+ {
+ wmemset (haystack, L'A', m);
+ haystack[0] = L'B';
+ haystack[m] = L'\0';
+
+ for (; repeat > 0; repeat--)
+ {
+ ASSERT (wcsstr (haystack, needle) == haystack + 1);
+ }
+
+ free (haystack);
+ }
+ }
+
+ /* Check that a very long needle is discarded quickly if the haystack is
+ short. */
+ {
+ size_t repeat = 10000;
+ size_t m = 1000000;
+ const wchar_t *haystack =
+ L"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
+ "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
+ wchar_t *needle = (wchar_t *) malloc ((m + 1) * sizeof (wchar_t));
+ if (needle != NULL)
+ {
+ wmemset (needle, L'A', m);
+ needle[m] = L'\0';
+
+ for (; repeat > 0; repeat--)
+ {
+ ASSERT (wcsstr (haystack, needle) == NULL);
+ }
+
+ free (needle);
+ }
+ }
+
+ /* Check that the asymptotic worst-case complexity is not quadratic. */
+ {
+ size_t m = 1000000;
+ wchar_t *haystack = (wchar_t *) malloc ((2 * m + 2) * sizeof (wchar_t));
+ wchar_t *needle = (wchar_t *) malloc ((m + 2) * sizeof (wchar_t));
+ if (haystack != NULL && needle != NULL)
+ {
+ const wchar_t *result;
+
+ wmemset (haystack, L'A', 2 * m);
+ haystack[2 * m] = L'B';
+ haystack[2 * m + 1] = L'\0';
+
+ wmemset (needle, L'A', m);
+ needle[m] = L'B';
+ needle[m + 1] = L'\0';
+
+ result = wcsstr (haystack, needle);
+ ASSERT (result == haystack + m);
+ }
+ free (needle);
+ free (haystack);
+ }
+
+ /* Sublinear speed is only possible in memmem; wcsstr must examine
+ every character of haystack to find its length. */
+
+
+ {
+ /* Ensure that with a barely periodic "short" needle, wcsstr's
+ search does not mistakenly skip just past the match point. */
+ const wchar_t *haystack =
+ L"\n"
+ "with_build_libsubdir\n"
+ "with_local_prefix\n"
+ "with_gxx_include_dir\n"
+ "with_cpp_install_dir\n"
+ "enable_generated_files_in_srcdir\n"
+ "with_gnu_ld\n"
+ "with_ld\n"
+ "with_demangler_in_ld\n"
+ "with_gnu_as\n"
+ "with_as\n"
+ "enable_largefile\n"
+ "enable_werror_always\n"
+ "enable_checking\n"
+ "enable_coverage\n"
+ "enable_gather_detailed_mem_stats\n"
+ "enable_build_with_cxx\n"
+ "with_stabs\n"
+ "enable_multilib\n"
+ "enable___cxa_atexit\n"
+ "enable_decimal_float\n"
+ "enable_fixed_point\n"
+ "enable_threads\n"
+ "enable_tls\n"
+ "enable_objc_gc\n"
+ "with_dwarf2\n"
+ "enable_shared\n"
+ "with_build_sysroot\n"
+ "with_sysroot\n"
+ "with_specs\n"
+ "with_pkgversion\n"
+ "with_bugurl\n"
+ "enable_languages\n"
+ "with_multilib_list\n";
+ const wchar_t *needle =
+ L"\n"
+ "with_gnu_ld\n";
+ const wchar_t* p = wcsstr (haystack, needle);
+ ASSERT (p - haystack == 114);
+ }
+
+ {
+ /* Same bug, shorter trigger. */
+ const wchar_t *haystack = L"..wi.d.";
+ const wchar_t *needle = L".d.";
+ const wchar_t* p = wcsstr (haystack, needle);
+ ASSERT (p - haystack == 4);
+ }
+
+ /* Test case from Yves Bastide.
+ <https://www.openwall.com/lists/musl/2014/04/18/2> */
+ {
+ const wchar_t input[] = L"playing play play play always";
+ const wchar_t *result = wcsstr (input, L"play play play");
+ ASSERT (result == input + 8);
+ }
+
+ /* Test long needles. */
+ {
+ size_t m = 1024;
+ wchar_t *haystack = (wchar_t *) malloc ((2 * m + 1) * sizeof (wchar_t));
+ wchar_t *needle = (wchar_t *) malloc ((m + 1) * sizeof (wchar_t));
+ if (haystack != NULL && needle != NULL)
+ {
+ const wchar_t *p;
+ haystack[0] = L'x';
+ wmemset (haystack + 1, L' ', m - 1);
+ wmemset (haystack + m, L'x', m);
+ haystack[2 * m] = L'\0';
+ wmemset (needle, L'x', m);
+ needle[m] = L'\0';
+ p = wcsstr (haystack, needle);
+ ASSERT (p);
+ ASSERT (p - haystack == m);
+ }
+ free (needle);
+ free (haystack);
+ }
+
+ return 0;
+}
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- wcsstr: Ensure worst-case linear execution time,
Bruno Haible <=