From 9411c5e467cf60f6295b9fed306029f341a0f24f Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Mon, 27 Mar 2023 15:41:30 +0200 Subject: [PATCH] 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. --- ChangeLog | 26 +++ doc/posix-functions/strstr.texi | 2 +- doc/posix-functions/wcsstr.texi | 12 +- lib/wchar.in.h | 18 +- lib/wcs-two-way.h | 303 ++++++++++++++++++++++++++++++++ lib/wcsstr-impl.h | 53 +++++- m4/wchar_h.m4 | 3 +- m4/wcsstr.m4 | 63 ++++++- modules/wchar | 1 + modules/wcsstr | 18 +- modules/wcsstr-simple | 29 +++ modules/wcsstr-tests | 22 +++ tests/test-wcsstr.c | 274 +++++++++++++++++++++++++++++ 13 files changed, 807 insertions(+), 17 deletions(-) create mode 100644 lib/wcs-two-way.h create mode 100644 modules/wcsstr-simple create mode 100644 modules/wcsstr-tests create mode 100644 tests/test-wcsstr.c diff --git a/ChangeLog b/ChangeLog index c17835425c..ac69cde6e2 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,29 @@ +2023-03-27 Bruno Haible + + 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. + 2023-03-27 Bruno Haible Add test case from a past musl libc bug. 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 @@ This function may fail to find matches on some platforms: 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 , 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 . */ + +/* Before including this file, you need to include and + , 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 +#include + +/* 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 , 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 . */ +/* 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 with or without modifications, as long as this notice is preserved. 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 /* for signal */ +#include /* for wcsstr */ +#include /* for malloc */ +#include /* 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: 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: + + +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 . */ + +#include + +#include + +#include "signature.h" +SIGNATURE_CHECK (wcsstr, wchar_t *, (wchar_t const *, wchar_t const *)); + +#include +#include +#include + +#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 . + This is a bug in memchr(), see the Austin Group's clarification + . */ + 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. + */ + { + 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; +} -- 2.39.5