[v2,0/3] Improve wcsstr

Message ID 20240220200445.4000158-1-adhemerval.zanella@linaro.org
Headers
Series Improve wcsstr |

Message

Adhemerval Zanella Netto Feb. 20, 2024, 8:04 p.m. UTC
  Different than strstr, wcsstr still uses an O(m*n) algorithm that might
be considered a security issue (although BZ 23865 was marked security-
since there is no actual application impact). 

The gnulib recently added a wrapper to fix it [1] and it is used as the
base de str-two-way.h implementation. This patch adds a similar
implementation, and different than strstr, neither the "shift table"
optimization nor the self-adapting filtering check is used because it
would result in a too-large shift table (and it also simplifies the
implementation bit).

The patchset also added a proper tests for wcsstr, based on strstr one.

[1] https://git.savannah.gnu.org/gitweb/?p=gnulib.git;a=commit;h=9411c5e467cf60f6295b9fed306029f341a0f24f

Changes from v1:
* Add more tests from gnulib.
* Removed unused macros from wcsstr.

Adhemerval Zanella (3):
  string: Remove c_strstr from test-strstr
  wcsmbs: Add test-wcsstr
  wcsmbs: Ensure wcstr worst-case linear execution time (BZ 23865)

 string/test-strstr.c | 305 ++++++++++++++++++++++++++++++++++--------
 wcsmbs/Makefile      |   1 +
 wcsmbs/test-wcsstr.c |  20 +++
 wcsmbs/wcs-two-way.h | 312 +++++++++++++++++++++++++++++++++++++++++++
 wcsmbs/wcsstr.c      |  95 ++++---------
 5 files changed, 609 insertions(+), 124 deletions(-)
 create mode 100644 wcsmbs/test-wcsstr.c
 create mode 100644 wcsmbs/wcs-two-way.h