From patchwork Fri Jan 13 18:27:25 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 642043 Delivered-To: patch@linaro.org Received: by 2002:a17:522:f3c4:b0:4b4:3859:abed with SMTP id in4csp358454pvb; Fri, 13 Jan 2023 10:29:34 -0800 (PST) X-Google-Smtp-Source: AMrXdXs//iccyWOHzI1VNcUxb26d8vf5+CimHunWnblpWtWmhE20dYy4izzObqx8h2X0YTAwOx3t X-Received: by 2002:a05:6402:5285:b0:45c:834b:eb5f with SMTP id en5-20020a056402528500b0045c834beb5fmr85211569edb.42.1673634574767; Fri, 13 Jan 2023 10:29:34 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673634574; cv=none; d=google.com; s=arc-20160816; b=tkXtmRn/FbBCXHHhC7HCnm+AiBSo8stD1gK+efVzuEYAnS1ZYkFVj9xzJa18sn3aUT iuLjdsr12JKhff79h2hcGVMIQwwBxbMnF8mGsr+oJJcYVEqUgNoCG0P0p9DwfLeWok+5 PFtLt/pzF9WmJJo26N/WzRtMsIJXcJ2YCJNxIjt9uSjtKijY3Llsw9RXqk/Z4Xsn5fHn i2FiG3JMwU6l7X1SDyFO25xryOGAnReTvZd8bDWEyCU/nloH1UXKk860M1baS+gXs/fo fKMsSE6vc1YhGMphGUe+6Wm6f+cuLIdNPLDbYYsT2K+qShn4mPDVPSBx2DAgqczd7het P+Sg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=sender:errors-to:reply-to:from:list-subscribe:list-help:list-post :list-archive:list-unsubscribe:list-id:precedence :content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:dmarc-filter:delivered-to :dkim-signature:dkim-filter; bh=Phgzl6cvhbrcYlQf6e5Xz5JDmrDLCzWT1fqECO1nztc=; b=bpdwbvtlosJMKJ/oeDQu68A7Tdm8LJ6hHRyeQWBSYLINz0cab+DmsBNOhx/qxsNTd9 aNJuOIBibV9rspjWd8ckANjueNwETF/STnK2xV8B5oVgFzLWOY8aQLypfF/THPhBq0MO rJUYH6W7H/4A3wM70juBb+++Uh0es4a/z8EfeLaDjrwK4jYWudA33Q8I8a/CGnyWS5jJ SPDLup09EyTf8PDKhQyYTtvtNs4Gj5iW9YQc21TgTMzNeI8X1P/FbLsElZnFOh3CSlur fZLHRZODxXZbfMGK010TSvs6IKJiV02fVuWtPuxPVdbR3m7fhdUbJwfFtrriaF8KOJuU er2g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=Wy4sU81f; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Return-Path: Received: from sourceware.org (server2.sourceware.org. [8.43.85.97]) by mx.google.com with ESMTPS id q11-20020a056402032b00b0048d858ddabfsi20230670edw.414.2023.01.13.10.29.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 10:29:34 -0800 (PST) Received-SPF: pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) client-ip=8.43.85.97; Authentication-Results: mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=Wy4sU81f; spf=pass (google.com: domain of libc-alpha-bounces+patch=linaro.org@sourceware.org designates 8.43.85.97 as permitted sender) smtp.mailfrom="libc-alpha-bounces+patch=linaro.org@sourceware.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 9A1DD38A815F for ; Fri, 13 Jan 2023 18:29:33 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 9A1DD38A815F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1673634573; bh=Phgzl6cvhbrcYlQf6e5Xz5JDmrDLCzWT1fqECO1nztc=; h=To:Cc:Subject:Date:In-Reply-To:References:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=Wy4sU81fdVYfaotXmiP41kG8SXmuWsXIubHAvNhgax/puvnqvogYvj90vkdA0KrLZ V5fosDK5TClPjFdymNmkKE8dL8zXL9I/FU4BiUL8sXJG6qQSv1n9ojHKxuTlH6ROf3 DQXcXvvMEiAfb2RQ++PQXuthjB+QeXn9rWKMwEls= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pj1-x1033.google.com (mail-pj1-x1033.google.com [IPv6:2607:f8b0:4864:20::1033]) by sourceware.org (Postfix) with ESMTPS id 90CFD3858004 for ; Fri, 13 Jan 2023 18:27:51 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 90CFD3858004 Received: by mail-pj1-x1033.google.com with SMTP id cx21-20020a17090afd9500b00228f2ecc6dbso2069747pjb.0 for ; Fri, 13 Jan 2023 10:27:51 -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:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Phgzl6cvhbrcYlQf6e5Xz5JDmrDLCzWT1fqECO1nztc=; b=G+KF4d7iYL3k11/edLYQ4sI9E2GLJdnpFunC+31kmAWVx8U6IAa8qKAQd31NQqms6p Pc0r2vCdxv1hmTojIUY0MMmP+CTQr1uUHWdMsM1CW2xyW5yXmu5DSAtgLwMr0A3WhuXr E6jzjpr6Z/3g2t5Rz1IY2qzNcNHcYIkXyrN3FHzXPBNoDZBfYcxrW0yLEUHpEbWNzuMw msQt7Lw2XQ9CIKjrYrIiHYQwOWGviGu3Xd4jIIf85Wc2m7TV7EosA/GO60AViNGTDgqQ d4mujcBvzVKN03S3LPnOZrk128oyyQDphCBxn/9p/cnvBHGSxLUyT+NZlaPDWxGpUX1P 2bjg== X-Gm-Message-State: AFqh2kr32LyxI16LYwuTQsdSIQPKr8bKvl5dLFDdJbEqZ5rDUDhgwbo1 wtR/cCmhRVqZCU6gviPftsa6rwolAJ0PlHxI X-Received: by 2002:a17:902:d5c8:b0:193:38b4:b9a7 with SMTP id g8-20020a170902d5c800b0019338b4b9a7mr20256032plh.31.1673634469938; Fri, 13 Jan 2023 10:27:49 -0800 (PST) Received: from stoup.. (rrcs-173-198-77-218.west.biz.rr.com. [173.198.77.218]) by smtp.gmail.com with ESMTPSA id s17-20020a170902c65100b001927ebc40e2sm14443640pls.193.2023.01.13.10.27.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 10:27:49 -0800 (PST) To: libc-alpha@sourceware.org Cc: adhemerval.zanella@linaro.org, goldstein.w.n@gmail.com Subject: [PATCH v8 09/17] string: Improve generic strcmp Date: Fri, 13 Jan 2023 08:27:25 -1000 Message-Id: <20230113182733.1268668-10-richard.henderson@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230113182733.1268668-1-richard.henderson@linaro.org> References: <20230113182733.1268668-1-richard.henderson@linaro.org> MIME-Version: 1.0 X-Spam-Status: No, score=-12.0 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: Richard Henderson via Libc-alpha From: Richard Henderson Reply-To: Richard Henderson Errors-To: libc-alpha-bounces+patch=linaro.org@sourceware.org Sender: "Libc-alpha" From: Adhemerval Zanella Netto New generic implementation tries to use word operations along with the new string-fzb.h functions even for inputs with different alignments (with still uses aligned access plus merge operation to get a correct word by word comparison). 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). Co-authored-by: Richard Henderson Message-Id: <20230111204558.2402155-10-adhemerval.zanella@linaro.org> --- string/strcmp.c | 118 +++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 102 insertions(+), 16 deletions(-) diff --git a/string/strcmp.c b/string/strcmp.c index 053f5a8d2b..f4861c0c08 100644 --- a/string/strcmp.c +++ b/string/strcmp.c @@ -15,33 +15,119 @@ License along with the GNU C Library; if not, see . */ +#include +#include +#include #include +#include -#undef strcmp - -#ifndef STRCMP -# define STRCMP strcmp +#ifdef STRCMP +# 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 +strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) +{ + op_t w2 = *x2++; + + while (w1 == w2) + { + if (has_zero (w1)) + return 0; + w1 = *x1++; + w2 = *x2++; + } + + return final_cmp (w1, w2); +} + +/* 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 +strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) +{ + 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)) + { + 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 (w1 != w2) + return final_cmp (w1, w2); + if (has_zero (w2b)) + 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 final_cmp (w1, w2); +} + /* Compare 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 -STRCMP (const char *p1, const char *p2) +strcmp (const char *p1, const char *p2) { - const unsigned char *s1 = (const unsigned char *) p1; - const unsigned char *s2 = (const unsigned char *) p2; - unsigned char c1, c2; - - do + /* Handle the unaligned bytes of p1 first. */ + uintptr_t n = -(uintptr_t)p1 % sizeof(op_t); + for (int i = 0; i < n; ++i) { - c1 = (unsigned char) *s1++; - c2 = (unsigned char) *s2++; - if (c1 == '\0') - return c1 - c2; + unsigned char c1 = *p1++; + unsigned char c2 = *p2++; + int diff = c1 - c2; + if (c1 == '\0' || diff != 0) + return diff; } - while (c1 == c2); - return c1 - c2; + /* 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 + ? strcmp_aligned_loop (x1, (const op_t *)p2, w1) + : strcmp_unaligned_loop (x1, (const op_t *)(p2 - ofs), w1, ofs); } +#ifndef STRCMP libc_hidden_builtin_def (strcmp) +#endif