From patchwork Fri Mar 1 17:15:22 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella Netto X-Patchwork-Id: 56748 Return-Path: X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9D48E385840E for ; Fri, 1 Mar 2024 17:16:08 +0000 (GMT) X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pl1-x62d.google.com (mail-pl1-x62d.google.com [IPv6:2607:f8b0:4864:20::62d]) by sourceware.org (Postfix) with ESMTPS id 82A6E3858C5F for ; Fri, 1 Mar 2024 17:15:30 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 82A6E3858C5F Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 82A6E3858C5F Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::62d ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709313332; cv=none; b=goT9Jq7/tsQKVXc2NlfCz/afYP8KC5h8oTo+EK5WdOxJSZDsMNHjKBM7PfVZgmmlMoiTss9b+8ZDzBE6W4qF90NCzMPa21A/a86YTTjMyfJ46AtG2XQ8dihCMxZwxbnoQ6hMejTsYcUqj0zI+RzFdKk7qsvPL2NJdpiEb9xhHww= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1709313332; c=relaxed/simple; bh=iu0M7u5PDySQjGYMejUlz4pOoAQm2gkFyoTfR6TF4Dw=; h=DKIM-Signature:From:To:Subject:Date:Message-Id:MIME-Version; b=Wewa98uzpxrSeV5tx3mgg/wCLmjrOa0br8EUMBoxGoq15+0H5sk/f5ZArWYIVrgDVK2eGgA11tAvYZ+mFX1lVlH7N5V/QT7qB8WBrIQsomXz57CA7EhAVuqwa9X02CMHb6MF9t3iRtaLuUVHfG15tEhyo5OWaT8GX0dLxbRRxTE= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-pl1-x62d.google.com with SMTP id d9443c01a7336-1dbae7b8ff2so7533665ad.3 for ; Fri, 01 Mar 2024 09:15:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; t=1709313329; x=1709918129; darn=sourceware.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=r0H+JM+5GR1BOQxkTn3zRe5HbLBIUAO1vp8wUP7i7WI=; b=jGN8kF0vjc6d4lMZaDGrOSOvIUq5lJtXTIUGWyLuGLxBlBdjHHUtA/qCui2qrbuMiE XMWmTbs8A8EoylGLKDQ8lOfRVx3naFkGFX6smpB7v9iIxIZyMeL+EvSrvzjlEjNHj+iT /4vxBv1g/p//Iz+o7Ire7n5AXhWlIE+ZEqvVWpPe6RsinXOG2WC4yqxetaDZRfZZPDIk ufqirggkEF5KUsJpmmpE4hWtZ2rBGRw7J5Pe3WX7cx0ntHDne8vBa8zL9Wea0dJYSR1V c2yOZfBcsl7jJFCjBBWxVU34HaZjPoTbPtyPqLtyDQyMc2kV7ozERXBZUH/YaR2BHrFb bK3w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709313329; x=1709918129; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=r0H+JM+5GR1BOQxkTn3zRe5HbLBIUAO1vp8wUP7i7WI=; b=al09QHX8W8xRKSHStfOEKw1hrKnZVwYoG9buwUkvzMT5LLIa7zkHGTd5MXBE9fDThk sgHrQQcmf9C5pqPi5nqnCE2qaaHk/JdklayXk73J9iiYKnhmdfS9NcfajviV1DDGjFXe dNzCbKQAMIBrC5w4nf3Fak1vsc9mXwFt5NqAzFOmEPybNA5ErBPprkh3tVtmLnHTvlN0 paNG0xBzyB3ZEUAtAmNvDc+6xgCMslMWxSqbiYjKI7zHgIE0FIebn8DAgh58GTrykI0o bHSXX5uomdGxMOJ1Ha/W4UhrqymnXg73GubM9QzfywGV4PE9SGPiEBOuN1VZEQgT5Uhz 7RFA== X-Gm-Message-State: AOJu0YzvpnxOewHEdmumcatYJhrxSND/xYFBCLYN2K+rOz5LcF/SXn4W v3MWZe6mqRWzqKCTb5dJAaVo5cUTyMJdTJcvp0pRc+XpFM423r0GsbppjBTqt035TQQlxjjuWvx O X-Google-Smtp-Source: AGHT+IEx4z48pSPu61jssCwBq+OD+TTSfsXETHw8IGuiKebCaAa8KfPFMJAiBfE1fZ4VX2oC3fDAiQ== X-Received: by 2002:a17:902:e741:b0:1dc:c45c:5d1d with SMTP id p1-20020a170902e74100b001dcc45c5d1dmr2879441plf.24.1709313329029; Fri, 01 Mar 2024 09:15:29 -0800 (PST) Received: from mandiga.. ([2804:1b3:a7c1:c57d:9e2a:a00b:9999:1e87]) by smtp.gmail.com with ESMTPSA id h15-20020a170902f54f00b001d974ffa1fcsm3702407plf.173.2024.03.01.09.15.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 01 Mar 2024 09:15:28 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org Cc: DJ Delorie Subject: [PATCH v2 0/2] Improve wcsstr Date: Fri, 1 Mar 2024 14:15:22 -0300 Message-Id: <20240301171524.3706554-1-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 MIME-Version: 1.0 X-Spam-Status: No, score=-5.4 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: libc-alpha@sourceware.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: libc-alpha-bounces+patchwork=sourceware.org@sourceware.org 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