From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ot1-x330.google.com (mail-ot1-x330.google.com [IPv6:2607:f8b0:4864:20::330]) by sourceware.org (Postfix) with ESMTPS id 53A413857C5A for ; Thu, 2 Feb 2023 18:12:17 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 53A413857C5A 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-ot1-x330.google.com with SMTP id d21-20020a056830005500b0068bd2e0b25bso698862otp.1 for ; Thu, 02 Feb 2023 10:12:17 -0800 (PST) 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:to:from:from:to:cc:subject:date:message-id :reply-to; bh=a/Zspv675rhfTQmqLMxUF+7k75/mM3dVzA7D6r+lHKo=; b=nZJAd/emLlmhgDiv+VCQfWdCmVyyNvQgr3SyxPOZL6T692BKT45q8pGi1Hrb7MFW// QlnckVAlio1IjoLupxD1MlgwUV2RBNM9J3ip0oB3F70DhufvEP4O6ZjBlr80kBvTxB52 326ny5XufONkqaVI8/2lyKqMJyYPvaHyV1VKSw39NfDQZqc66N1a0PrpZLhjwiNPTWqL DNpgK05TA8wLtp37Yw0iiZukUwcMD9EBwYN33XF5qWwf0HCPhDC0S1bUFnVBSvptszqW QFppkh9c4zHEBbRJYp09nAbqw7ymQBvIV64MZ78IXYaNZ5iWwT3SJyaeYJXlNFJGz1Ah ongg== 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=a/Zspv675rhfTQmqLMxUF+7k75/mM3dVzA7D6r+lHKo=; b=2I30iGRFowYOrJOADGkveqO6HX9CpFX4Q0SoUJO/jCDcigbWJnO/ibxqig6YrLVMBR kSdADdoHP7uQLN3XOooXrCB3Z5qSts/6vNCl86DRYjZr+1AcjAXBwAalrQLhk7TCmyM0 733gcZEbAeb+FI9uFBuGAK8kaPUvqAtVwRXa24PY8wW+M1bEUM7f24uAQuZ45KtiaThI AG6sFfdW82YEQ26Lj894p1NjRD9ciTQDsAvXIVjyAbh9dJR18HpnkvxtCUQoKPyNl3r0 S9oh9Y+05HCNS2upmJx4JA1J/WTOuMXtoDLux3UMROBSDnraJ/tT5Kf8Jy4c1dIQxZgP S3tw== X-Gm-Message-State: AO0yUKVrcTK1LMUU7KT/hLkP7xU9fewnZ9Vn8ThhaBQKeWzKfw0OZypD 27eCr9lGEvuloVh6S2MalRjtU8nSf1kfV+Lwy4s= X-Google-Smtp-Source: AK7set94uvwLU4CpGdllbT16hp2j+BdPPD5Yx/N5JdfgcI8YAmFLIZCqPhJOitWZpbButLU3SMy9Hg== X-Received: by 2002:a05:6830:4803:b0:68b:a341:b93b with SMTP id dg3-20020a056830480300b0068ba341b93bmr3242179otb.36.1675361536308; Thu, 02 Feb 2023 10:12:16 -0800 (PST) Received: from mandiga.. ([2804:1b3:a7c2:1887:da12:b9d3:2162:a28c]) by smtp.gmail.com with ESMTPSA id ci10-20020a05683063ca00b00684a10970adsm126689otb.16.2023.02.02.10.12.14 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 02 Feb 2023 10:12:15 -0800 (PST) From: Adhemerval Zanella To: libc-alpha@sourceware.org, Richard Henderson , Jeff Law , Xi Ruoyao , Noah Goldstein Subject: [PATCH v12 08/31] string: Improve generic strncmp Date: Thu, 2 Feb 2023 15:11:26 -0300 Message-Id: <20230202181149.2181553-9-adhemerval.zanella@linaro.org> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20230202181149.2181553-1-adhemerval.zanella@linaro.org> References: <20230202181149.2181553-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 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: 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/strncmp.c | 138 ++++++++++++++++++++++++++++++++++------------- 1 file changed, 101 insertions(+), 37 deletions(-) diff --git a/string/strncmp.c b/string/strncmp.c index fd7cee09b6..4c8bf36bb9 100644 --- a/string/strncmp.c +++ b/string/strncmp.c @@ -15,7 +15,12 @@ License along with the GNU C Library; if not, see . */ +#include +#include +#include +#include #include +#include #include #undef strncmp @@ -24,51 +29,110 @@ #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) +static inline int +final_cmp (const op_t w1, const op_t w2, size_t n) +{ + unsigned int idx = index_first_zero_ne (w1, w2); + if (n <= idx) + return 0; + return extractbyte (w1, idx) - extractbyte (w2, idx); +} + +/* 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 0; + + /* 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) -- 2.34.1