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: 777048 Delivered-To: patch@linaro.org Received: by 2002:adf:e94d:0:b0:33d:f458:43ce with SMTP id m13csp1470518wrn; Fri, 1 Mar 2024 09:15:44 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCXca3f+rRSEDWCRlkMyrwfiYCp97Q8WeK0ioUL8pwQrvhGKJ9eH5AsSoxaFhpNRFaj60+FYhuzgFUz7VH5d4cIF X-Google-Smtp-Source: AGHT+IFoKJhJu+DKtia6gKmNZgu1J3mzC0DW7N8XrHd2h3qe6yEFp5G7+/zzMZiCl56x1y3Nljfi X-Received: by 2002:ac5:ca02:0:b0:4c0:25db:3618 with SMTP id c2-20020ac5ca02000000b004c025db3618mr2069145vkm.0.1709313343719; Fri, 01 Mar 2024 09:15:43 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709313343; cv=pass; d=google.com; s=arc-20160816; b=WF9NWDM/EOfBprsMPUW7uShBufeSLZl9gXvBprhiluh0ZyTu6nM/Hnw/arJg0Ow0ue xeyfYTR1irT8r2ujM404BOk7/xXNz58PwgVb9lwXbeMwe2qyxCJVkKa8lj3/PtJgtLZA 7B7P5tk/ltEeyqLKddgWdhRjOGTpl/2Pq0a3lBPQsv/aVKr66EnpaKdhj+Y+0FAdLZc/ 3TM0GjxUrzeYuiqT4VLDLKu5x92xgeILgAGW+Xcz9+V9H1fbwqODQ7Sb6H+STWGFfFvJ d56MZgxJDSkJWgQzfQzj0Qfcg5RUlSdAWbD/dbTEEAoazkXUggZy5I7DgQcpKKzx0F/m 3baQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:cc:to:from:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=r0H+JM+5GR1BOQxkTn3zRe5HbLBIUAO1vp8wUP7i7WI=; fh=/bzLn4Pu6wt5yJOmVA6NJX5WuFMrzV1CRzIGBeRqGpk=; b=o+UMCuqakuCAwKcWmAdlnKHW9sLxDUmI6VgwsMyUln+9jEQx70t5rCLom/sNyDYXIU UA5FkJTO+jlBtGx23eOxepnacSGYv0rTvXAgAKn8Kv4rRL21MFs6yNwa29rAmiPQ4gOZ FjsHoonWX68TpCtIFRV9JQM+bp2kVEz80GVkIrOYB2J8xCOZRSrY6f/ty5ZSQ72c/B0L 8c/0w+4VYGcrqHZ//uGgt8CPT2Zw6DR8ouV6bAj/RPxwXGj5qLI0zHmHGXoe3RIIv/zW 3srfUkpHJwJDBgOT9Oi1OTusK52BuBDr2h0b3jxEXPUKHMmCICQ4pE3GZSBt9mRf4oqs kdhQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=jGN8kF0v; arc=pass (i=1); spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Return-Path: Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id 32-20020a0561220a2000b004ce910587ebsi740164vkn.52.2024.03.01.09.15.43 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 01 Mar 2024 09:15:43 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@linaro.org header.s=google header.b=jGN8kF0v; arc=pass (i=1); spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 2892B385840C for ; Fri, 1 Mar 2024 17:15:43 +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-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+patch=linaro.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