mbox series

[v2,0/2] Improve wcsstr

Message ID 20240301171524.3706554-1-adhemerval.zanella@linaro.org
Headers show
Series Improve wcsstr | expand

Message

Adhemerval Zanella March 1, 2024, 5:15 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:
  - Dropped c_strstr removal from tst-strstr.c.
  - Adjusted Copyright years for wcs-two-way.h.

Adhemerval Zanella (2):
  wcsmbs: Add test-wcsstr
  wcsmbs: Ensure wcstr worst-case linear execution time (BZ 23865)

 string/test-strstr.c | 322 ++++++++++++++++++++++++++++++++++++-------
 wcsmbs/Makefile      |   1 +
 wcsmbs/test-wcsstr.c |  20 +++
 wcsmbs/wcs-two-way.h | 312 +++++++++++++++++++++++++++++++++++++++++
 wcsmbs/wcsstr.c      | 103 ++++----------
 5 files changed, 632 insertions(+), 126 deletions(-)
 create mode 100644 wcsmbs/test-wcsstr.c
 create mode 100644 wcsmbs/wcs-two-way.h