From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-oa1-x31.google.com (mail-oa1-x31.google.com [IPv6:2001:4860:4864:20::31]) by sourceware.org (Postfix) with ESMTPS id 54CE03857BB2 for ; Fri, 2 Sep 2022 20:40:01 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 54CE03857BB2 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=linaro.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=linaro.org Received: by mail-oa1-x31.google.com with SMTP id 586e51a60fabf-11ee4649dfcso7672653fac.1 for ; Fri, 02 Sep 2022 13:40:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linaro.org; s=google; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date; bh=x4vZLjiQkKxxpJOXFAu7UXxa3yTyub2DnkcytVdKPfw=; b=JcmF4q4hlF8cNnDeEf053ppArfnk4fYX8n4fCgbBsuMrbbgPD6ECvFRhJbBG/HJ2tL I6XwpxqhZxUcfc7UHS5Ya01XrYlD4ytzziUgBkScq+Bo+P5cSuMEU0awo26u4X2IcQxT UVeG7P05Iv0hMDXJq0stshDZp6pd7WEEHDLhn5kYw6ADN2JxZJtxPJbSIgVIrNdBM6mK xxXcooRZ9Y9OEKoIqpLdfoVAsTOUTvBWV91S1TX1ImWXFxKN5AhSh+9l5Xx2J+APmR7E vM+SX+MvPuNTXAraMPWO4vF8qTL08XlWPjW6YaYrKgCbLlXD0dSIQarWBcneF06eEUpK ueWg== 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; bh=x4vZLjiQkKxxpJOXFAu7UXxa3yTyub2DnkcytVdKPfw=; b=l4ZVb+wY/Z3bec9gbFpgrMGjEkCsoS8W5QIc0Kg4Mf7VX0lEfQ5Cnk1R7VHAoeg3bS EmvdtbRB7AOgMWzecn8xnXdpJLYF6UsvFdIlnbUiAOaL6WAF6L4ugcIV630VNvHc6pTQ zsHulsiMfC8Y2NgeFSSWBLU66W1DcFcZ16YTwfCYk2jMUqkzccQL+wfTUT0olYGJa0A9 BUyy70Ks+BQNKQBejglI8/opm3Y19fr28kYRjDO+PzVEMAosvKmdgo+3D07zJ7Hs4Sly +Cn2n/UTCErAPcZfsjTcIMje1sjS4gbwrXDGNizfLsLrSBmYnp75exISkmpfromTljrI COQQ== X-Gm-Message-State: ACgBeo2MgHmV7exU5IPbcznoV4LRYJJfKlT1PbW/oO6/KJ2dSy7Zqdu0 7KyaCCPZBI2JFf+rk493Nn/AVu6jCi3oyA== X-Google-Smtp-Source: AA6agR7Iyx/DzlJN4aqA6Kox1oTVI+rxGZSXF/8HjsanBGYnFj+avzlSMxPykzfzL7z0Iu6de2m17Q== X-Received: by 2002:a05:6870:17a9:b0:11d:1762:4cb1 with SMTP id r41-20020a05687017a900b0011d17624cb1mr3080815oae.193.1662151200834; Fri, 02 Sep 2022 13:40:00 -0700 (PDT) Received: from mandiga.. ([2804:1b3:a7c0:dfed:72d1:946c:4eb1:ce5f]) by smtp.gmail.com with ESMTPSA id i27-20020a4a6f5b000000b00425678b9c4bsm1107902oof.0.2022.09.02.13.39.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 02 Sep 2022 13:40:00 -0700 (PDT) From: Adhemerval Zanella To: libc-alpha@sourceware.org Cc: Joseph Myers , caiyinyu , Richard Henderson Subject: [PATCH 09/17] string: Improve generic strcmp Date: Fri, 2 Sep 2022 17:39:32 -0300 Message-Id: <20220902203940.2385967-10-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20220902203940.2385967-1-adhemerval.zanella@linaro.org> References: <20220902203940.2385967-1-adhemerval.zanella@linaro.org> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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,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 List-Id: New generic implementation tries to use word operations along with the new string-fz{b,i} 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 --- string/strcmp.c | 117 +++++++++++++++++++++++++++++++++++++++++------- 1 file changed, 101 insertions(+), 16 deletions(-) diff --git a/string/strcmp.c b/string/strcmp.c index d4962be4ec..c8acc5c0b5 100644 --- a/string/strcmp.c +++ b/string/strcmp.c @@ -15,33 +15,118 @@ License along with the GNU C Library; if not, see . */ +#include +#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) +{ + unsigned char c1, c2; + for (size_t i = 0; i < sizeof (op_t); i++) + { + c1 = extractbyte (w1, i); + c2 = extractbyte (w2, i); + if (c1 == '\0' || c1 != c2) + return c1 - c2; + } + return c1 - c2; +} + +/* 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 unsigned long. 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 -- 2.34.1