From patchwork Wed Feb 1 17:03:46 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Adhemerval Zanella X-Patchwork-Id: 1735782 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=sourceware.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org; receiver=) Authentication-Results: legolas.ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.a=rsa-sha256 header.s=default header.b=I4tZF5xz; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4P6Syt68Rnz23gY for ; Thu, 2 Feb 2023 04:07:34 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id BE1D03945C2B for ; Wed, 1 Feb 2023 17:07:32 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org BE1D03945C2B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1675271252; bh=RigOSPcp4SguP2O0hFzmhpvXg5H4AzvcsiJvlR6LFeo=; h=To:Subject:Date:In-Reply-To:References:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=I4tZF5xzwwXTIY4mY0v6yH8ZIQqj5S/F0qTUJ6u243j/m75HsQgjGgpC/F2jtep3l nde8ZCnfnXPBa+qechj3nxL6PwRR7i6pkWSiaorLS6lxrXdzs4Hv7RUh6KrT/LJWbf Kj2XQ07cORkZVPZaoK9d9knYfjG2A8QmBaMdDpug= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-oi1-x22d.google.com (mail-oi1-x22d.google.com [IPv6:2607:f8b0:4864:20::22d]) by sourceware.org (Postfix) with ESMTPS id 3C5FD3858C36 for ; Wed, 1 Feb 2023 17:04:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 3C5FD3858C36 Received: by mail-oi1-x22d.google.com with SMTP id r9so16261961oig.12 for ; Wed, 01 Feb 2023 09:04:37 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=RigOSPcp4SguP2O0hFzmhpvXg5H4AzvcsiJvlR6LFeo=; b=qFT2aC1mtIJ4p8lAvBBav6HDpbl4Ti6KaKPrrZMpZz/LK3RamDWqqCe/xbyfOnZXTX LjjEtRlY/R4R6GxGZiEJjgT204XY7bkcvhW+N6EJW4xYeE3LhImZg0nQ1zViZKowyDcG XfLD8syXjAD+l4Czi9vNFw4ERS9XdhboXkokA+ZgsQ+jwYazDbI/Da0rjnuSX3FJl7I8 7j2jxdbCQbPdT+dmFjpW1R5gaDjpVT9tm/SbtExcmLzLyDQ56ozIjEYiM6q0Ix3abbuq HJjDZIIeaR8Aa/fEi6/cptg/dAJa6xznZxqcrsNMgwNIgRXt3cm6sNJOf18mGK/ya5rb L8KQ== X-Gm-Message-State: AO0yUKUCP0hjsfJZhDqwxDNvKb2MsSm6G7pcexdk/dpmNSkAL4s/13Tp hIOtYKntlphQujJck6jE1/GZDYWlJg5k5grkg/M= X-Google-Smtp-Source: AK7set9kvpXYpE1NzvyvKiPuUuoeNwxmmSBwIzOSf7/V+uUh6AekRrwZMxWti85qHs0Twn2tZklQcg== X-Received: by 2002:a05:6808:5cf:b0:378:81a0:f640 with SMTP id d15-20020a05680805cf00b0037881a0f640mr1500722oij.43.1675271076232; Wed, 01 Feb 2023 09:04:36 -0800 (PST) Received: from mandiga.. ([2804:1b3:a7c2:1887:d2ed:98c2:d2cc:bf06]) by smtp.gmail.com with ESMTPSA id b17-20020a056830311100b006863ccbf067sm8077090ots.74.2023.02.01.09.04.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Feb 2023 09:04:35 -0800 (PST) To: libc-alpha@sourceware.org, Richard Henderson , Noah Goldstein , Jeff Law , Xi Ruoyao Subject: [PATCH v11 09/29] string: Improve generic strncmp Date: Wed, 1 Feb 2023 14:03:46 -0300 Message-Id: <20230201170406.303978-10-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230201170406.303978-1-adhemerval.zanella@linaro.org> References: <20230201170406.303978-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-12.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP 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.29 Precedence: list List-Id: Libc-alpha mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: Adhemerval Zanella via Libc-alpha From: Adhemerval Zanella Reply-To: Adhemerval Zanella Errors-To: libc-alpha-bounces+incoming=patchwork.ozlabs.org@sourceware.org Sender: "Libc-alpha" It follows the strategy: - Align the first input to word boundary using byte operations. - If second input is also word aligned, read a word per time, check for null (using has_zero), and check final words using byte operation. - If second input is not word aligned, loop by aligning the source, and merge the result of two reads. Similar to aligned case, check for null with has_zero, and check final words using byte operation. Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, and powerpc-linux-gnu by removing the arch-specific assembly implementation and disabling multi-arch (it covers both LE and BE for 64 and 32 bits). --- string/strcmp-impl.h | 41 ++++++++++++++ string/strcmp.c | 23 ++------ string/strncmp.c | 130 +++++++++++++++++++++++++++++++------------ 3 files changed, 138 insertions(+), 56 deletions(-) create mode 100644 string/strcmp-impl.h diff --git a/string/strcmp-impl.h b/string/strcmp-impl.h new file mode 100644 index 0000000000..618240368a --- /dev/null +++ b/string/strcmp-impl.h @@ -0,0 +1,41 @@ +/* Common definition for string compare implementations. + Copyright (C) 2023 Free Software Foundation, Inc. + This file is part of the GNU C Library. + + The GNU C Library is free software; you can redistribute it and/or + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. + + The GNU C Library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public + License along with the GNU C Library; if not, see + . */ + +#ifndef _STRCMP_IMPL_H +#define _STRCMP_IMPL_H + +#include +#include + +static inline int +final_cmp (const op_t w1, const op_t w2, size_t n) +{ + /* It can not use index_first_zero_ne because it must not compare past the + final '\0' is present (and final_cmp is called before has_zero check). + */ + for (size_t i = 0; i < n; i++) + { + unsigned char c1 = extractbyte (w1, i); + unsigned char c2 = extractbyte (w2, i); + if (c1 == '\0' || c1 != c2) + return c1 - c2; + } + return 0; +} + +#endif diff --git a/string/strcmp.c b/string/strcmp.c index 42e24242b6..8e7b3310db 100644 --- a/string/strcmp.c +++ b/string/strcmp.c @@ -16,6 +16,7 @@ . */ #include +#include #include #include #include @@ -25,22 +26,6 @@ # define strcmp STRCMP #endif -static inline int -final_cmp (const op_t w1, const op_t w2) -{ - /* It can not use index_first_zero_ne because it must not compare past the - final '\0' is present (and final_cmp is called before has_zero check). - */ - for (size_t i = 0; i < sizeof (op_t); i++) - { - unsigned char c1 = extractbyte (w1, i); - unsigned char c2 = extractbyte (w2, i); - if (c1 == '\0' || c1 != c2) - return c1 - c2; - } - return 0; -} - /* Aligned loop: if a difference is found, exit to compare the bytes. Else if a zero is found we have equal strings. */ static inline int @@ -56,7 +41,7 @@ strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) w2 = *x2++; } - return final_cmp (w1, w2); + return final_cmp (w1, w2, sizeof (op_t)); } /* Unaligned loop: align the first partial of P2, with 0xff for the rest of @@ -83,7 +68,7 @@ strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) w2b = *x2++; w2 = MERGE (w2a, sh_1, w2b, sh_2); if (w1 != w2) - return final_cmp (w1, w2); + return final_cmp (w1, w2, sizeof (op_t)); if (has_zero (w2b)) break; w1 = *x1++; @@ -100,7 +85,7 @@ strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) w2 = MERGE (w2b, sh_1, 0, sh_2); } - return final_cmp (w1, w2); + return final_cmp (w1, w2, sizeof (op_t)); } /* Compare S1 and S2, returning less than, equal to or diff --git a/string/strncmp.c b/string/strncmp.c index fd7cee09b6..3e6040df09 100644 --- a/string/strncmp.c +++ b/string/strncmp.c @@ -15,7 +15,13 @@ License along with the GNU C Library; if not, see . */ +#include +#include +#include +#include +#include #include +#include #include #undef strncmp @@ -24,51 +30,101 @@ #define STRNCMP strncmp #endif -/* Compare no more than N characters of S1 and S2, - returning less than, equal to or greater than zero - if S1 is lexicographically less than, equal to or - greater than S2. */ -int -STRNCMP (const char *s1, const char *s2, size_t n) +/* Aligned loop: if a difference is found, exit to compare the bytes. Else + if a zero is found we have equal strings. */ +static inline int +strncmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1, size_t n) { - unsigned char c1 = '\0'; - unsigned char c2 = '\0'; + op_t w2 = *x2++; - if (n >= 4) + while (w1 == w2) { - size_t n4 = n >> 2; - do - { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - } while (--n4 > 0); - n &= 3; + if (n <= sizeof (op_t)) + break; + n -= sizeof (op_t); + + if (has_zero (w1)) + return 0; + w1 = *x1++; + w2 = *x2++; } - while (n > 0) + return final_cmp (w1, w2, n); +} + +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of + the bytes so that we can also apply the has_zero test to see if we have + already reached EOS. If we have, then we can simply fall through to the + final comparison. */ +static inline int +strncmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs, + size_t n) +{ + op_t w2a = *x2++; + uintptr_t sh_1 = ofs * CHAR_BIT; + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; + + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); + if (!has_zero (w2) && n > (sizeof (op_t) - ofs)) { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0' || c1 != c2) - return c1 - c2; - n--; + op_t w2b; + + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, + does not contain end-of-string. Therefore it is safe (and necessary) + to read another word from each while we do not have a difference. */ + while (1) + { + w2b = *x2++; + w2 = MERGE (w2a, sh_1, w2b, sh_2); + if (n <= sizeof (op_t) || w1 != w2) + return final_cmp (w1, w2, n); + n -= sizeof(op_t); + if (has_zero (w2b) || n <= (sizeof (op_t) - ofs)) + break; + w1 = *x1++; + w2a = w2b; + } + + /* Zero found in the second partial of P2. If we had EOS in the aligned + word, we have equality. */ + if (has_zero (w1)) + return 0; + + /* Load the final word of P1 and align the final partial of P2. */ + w1 = *x1++; + w2 = MERGE (w2b, sh_1, 0, sh_2); } - return c1 - c2; + return final_cmp (w1, w2, n); } +/* Compare no more than N characters of S1 and S2, + returning less than, equal to or greater than zero + if S1 is lexicographically less than, equal to or + greater than S2. */ +int +STRNCMP (const char *p1, const char *p2, size_t n) +{ + /* Handle the unaligned bytes of p1 first. */ + uintptr_t a = MIN (-(uintptr_t)p1 % sizeof(op_t), n); + int diff = 0; + for (int i = 0; i < a; ++i) + { + unsigned char c1 = *p1++; + unsigned char c2 = *p2++; + diff = c1 - c2; + if (c1 == '\0' || diff != 0) + return diff; + } + if (a == n) + return diff; + + /* P1 is now aligned to op_t. P2 may or may not be. */ + const op_t *x1 = (const op_t *) p1; + op_t w1 = *x1++; + uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); + return ofs == 0 + ? strncmp_aligned_loop (x1, (const op_t *) p2, w1, n - a) + : strncmp_unaligned_loop (x1, (const op_t *) (p2 - ofs), w1, ofs, n - a); +} libc_hidden_builtin_def (STRNCMP)