From f039d18ef95452c07cb45d89fcac44fa993ec8f3 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Sat, 9 Sep 2023 17:14:15 -0700 Subject: [PATCH] mbsstr: support GNULIB_MCEL_PREFER Support mcel API for apps that prefer it. * lib/mbsstr.c [GNULIB_MCEL_PREFER]: Include mcel.h not mbuiter.h. (mbchar_t, mb_equal) [GNULIB_MCEL_PREFER]: New type and function, to make it easier to use common code. (knuth_morris_pratt_multibyte): Don't assume mbchar_t's alignment is at least that of size_t. (knuth_morris_pratt_multibyte, mbsstr) [GNULIB_MCEL_PREFER]: Use mcel API. * modules/mbsstr (Depends-on): Add alignasof. --- ChangeLog | 11 ++++ lib/mbsstr.c | 150 +++++++++++++++++++++++++++++++++++++++++++++++-- modules/mbsstr | 1 + 3 files changed, 158 insertions(+), 4 deletions(-) diff --git a/ChangeLog b/ChangeLog index fe2864b0ee..a97a5081b0 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,16 @@ 2023-09-09 Paul Eggert + mbsstr: support GNULIB_MCEL_PREFER + Support mcel API for apps that prefer it. + * lib/mbsstr.c [GNULIB_MCEL_PREFER]: Include mcel.h not mbuiter.h. + (mbchar_t, mb_equal) [GNULIB_MCEL_PREFER]: New type and function, + to make it easier to use common code. + (knuth_morris_pratt_multibyte): Don't assume mbchar_t's alignment + is at least that of size_t. + (knuth_morris_pratt_multibyte, mbsstr) [GNULIB_MCEL_PREFER]: + Use mcel API. + * modules/mbsstr (Depends-on): Add alignasof. + mbslen: support GNULIB_MCEL_PREFER Support mcel API for apps that prefer it. The following changes are in effect only if GNULIB_MCEL_PREFER. diff --git a/lib/mbsstr.c b/lib/mbsstr.c index 03fb7045e3..b8d15f9521 100644 --- a/lib/mbsstr.c +++ b/lib/mbsstr.c @@ -24,7 +24,14 @@ #include #include "malloca.h" -#include "mbuiter.h" + +#if GNULIB_MCEL_PREFER +# include "mcel.h" +typedef mcel_t mbchar_t; +static bool mb_equal (mcel_t a, mcel_t b) { return mcel_cmp (a, b) == 0; } +#else +# include "mbuiter.h" +#endif /* Knuth-Morris-Pratt algorithm. */ #define UNIT unsigned char @@ -42,25 +49,36 @@ knuth_morris_pratt_multibyte (const char *haystack, const char *needle, { size_t m = mbslen (needle); mbchar_t *needle_mbchars; - size_t *table; + size_t extra_align = (alignof (mbchar_t) < alignof (size_t) + ? alignof (size_t) - alignof (mbchar_t) + : 0); /* Allocate room for needle_mbchars and the table. */ - void *memory = nmalloca (m, sizeof (mbchar_t) + sizeof (size_t)); + void *memory = nmalloca (m + !!extra_align, + sizeof (mbchar_t) + sizeof (size_t)); void *table_memory; if (memory == NULL) return false; needle_mbchars = memory; table_memory = needle_mbchars + m; - table = table_memory; + char *aligned = table_memory; + aligned += extra_align; + aligned -= (uintptr_t) aligned % alignof (size_t); + size_t *table = table_memory = aligned; /* Fill needle_mbchars. */ { +#if GNULIB_MCEL_PREFER + for (size_t j = 0; *needle; needle += needle_mbchars[j++].len) + needle_mbchars[j] = mcel_scanz (needle); +#else mbui_iterator_t iter; size_t j; j = 0; for (mbui_init (iter, needle); mbui_avail (iter); mbui_advance (iter), j++) mb_copy (&needle_mbchars[j], &mbui_cur (iter)); +#endif } /* Fill the table. @@ -132,6 +150,46 @@ knuth_morris_pratt_multibyte (const char *haystack, const char *needle, /* Search, using the table to accelerate the processing. */ { +#if GNULIB_MCEL_PREFER + size_t j; + char const *rhaystack = haystack; + char const *phaystack = haystack; + + j = 0; + /* Invariant: phaystack = rhaystack + j. */ + for (;;) + { + if (!*phaystack) + { + rhaystack = NULL; + break; + } + mcel_t g = mcel_scanz (phaystack); + if (mcel_cmp (needle_mbchars[j], g) == 0) + { + j++; + /* Exit loop successfully if the entire needle has been found. */ + if (j == m) + break; + phaystack += g.len; + } + else if (j == 0) + { + /* Found a mismatch at needle[0] already. */ + rhaystack += mcel_scanz (rhaystack).len; + phaystack += g.len; + } + else + { + /* Found a match of needle[0..j-1], mismatch at needle[j]. */ + size_t count = table[j]; + j -= count; + for (; count != 0; count--) + rhaystack += mcel_scanz (rhaystack).len; + } + } + *resultp = rhaystack; +#else size_t j; mbui_iterator_t rhaystack; mbui_iterator_t phaystack; @@ -173,6 +231,7 @@ knuth_morris_pratt_multibyte (const char *haystack, const char *needle, mbui_advance (rhaystack); mbui_advance (phaystack); } +#endif } freea (memory); @@ -191,6 +250,88 @@ mbsstr (const char *haystack, const char *needle) needle may be found in haystack. */ if (MB_CUR_MAX > 1) { +#if GNULIB_MCEL_PREFER + if (!*needle) + return (char *) haystack; + + mcel_t ng = mcel_scanz (needle); + + /* Minimizing the worst-case complexity: + Let n = mbslen(haystack), m = mbslen(needle). + The naïve algorithm is O(n*m) worst-case. + The Knuth-Morris-Pratt algorithm is O(n) worst-case but it needs a + memory allocation. + To achieve linear complexity and yet amortize the cost of the + memory allocation, we activate the Knuth-Morris-Pratt algorithm + only once the naïve algorithm has already run for some time; more + precisely, when + - the outer loop count is >= 10, + - the average number of comparisons per outer loop is >= 5, + - the total number of comparisons is >= m. + But we try it only once. If the memory allocation attempt failed, + we don't retry it. */ + bool try_kmp = true; + size_t outer_loop_count = 0; + size_t comparison_count = 0; + + /* Last comparison count, and needle + last_ccount. */ + size_t last_ccount = 0; + char const *iter_needle_last_ccount = needle; + + char const *iter_haystack = haystack; + + for (mcel_t hg; *iter_haystack; iter_haystack += hg.len) + { + /* See whether it's advisable to use an asymptotically faster + algorithm. */ + if (try_kmp + && outer_loop_count >= 10 + && comparison_count >= 5 * outer_loop_count) + { + /* See if needle + comparison_count now reaches the end of + needle. */ + size_t count = comparison_count - last_ccount; + for (; + count > 0 && *iter_needle_last_ccount; + count--) + iter_needle_last_ccount + += mcel_scanz (iter_needle_last_ccount).len; + last_ccount = comparison_count; + if (!*iter_needle_last_ccount) + { + char const *result; + if (knuth_morris_pratt_multibyte (haystack, needle, + &result)) + return (char *) result; + try_kmp = false; + } + } + + outer_loop_count++; + comparison_count++; + hg = mcel_scanz (iter_haystack); + if (mcel_cmp (hg, ng) == 0) + /* The first character matches. */ + { + char const *rhaystack = iter_haystack + hg.len; + char const *rneedle = needle + ng.len; + mcel_t rhg, rng; + do + { + if (!*rneedle) + return (char *) iter_haystack; + if (!*rhaystack) + return NULL; + rhg = mcel_scanz (rhaystack); rhaystack += rhg.len; + rng = mcel_scanz (rneedle); rneedle += rng.len; + comparison_count++; + } + while (mcel_cmp (rhg, rng) == 0); + } + } + + return NULL; +#else mbui_iterator_t iter_needle; mbui_init (iter_needle, needle); @@ -287,6 +428,7 @@ mbsstr (const char *haystack, const char *needle) } else return (char *) haystack; +#endif } else { diff --git a/modules/mbsstr b/modules/mbsstr index 654760cfbe..8cca9dd129 100644 --- a/modules/mbsstr +++ b/modules/mbsstr @@ -6,6 +6,7 @@ lib/mbsstr.c lib/str-kmp.h Depends-on: +alignasof mbuiter stdbool string -- 2.39.5