From patchwork Fri Jan 13 18:27:23 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 642040 Delivered-To: patch@linaro.org Received: by 2002:a17:522:f3c4:b0:4b4:3859:abed with SMTP id in4csp358166pvb; Fri, 13 Jan 2023 10:28:54 -0800 (PST) X-Google-Smtp-Source: AMrXdXspgwQB7M5LUqwkftyk5I/DrWFHTWoAseXKDM+Cy/2eimajBnuzLjm58vcuMTy4ukk0cI/4 X-Received: by 2002:a17:906:ce3c:b0:84d:3606:959f with SMTP id sd28-20020a170906ce3c00b0084d3606959fmr3902710ejb.28.1673634534447; Fri, 13 Jan 2023 10:28:54 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1673634534; cv=none; d=google.com; s=arc-20160816; b=tUMs7BGQJj2neTLOQKJzfOtSwvdtUHhqiZCio1yNQdDQQdWDVqKhdKsMi2o9772JZF 6tL39GfsSU/M9VZ5n82/DrWMvHe6j0Glf9xtdDRJYn8/1kUlHWM0g0euFEzZUa/HXQN7 T5Lbka43hNO97dbJA+DlqDqmLTknZ16Z3/5EfsfGimUomWSn7B/pSIked/J9BrynvOri y9NEFJyvm494n+HsMSc+E0EQrHQVBfT3fdVa5Nc+itFwnKTm6x+ANQ2Q/xkd/ZhjAN1l hCo7xlGelwWk+gzXZ6m+gFcAiEsI25nz81Ik+Qbv5cknx4pQsuXwJmvQHbj294zWkfsj OWTA== 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=Lr8fcCFCLEXMcMa2jAwiXGOwETn0rlrYauVuqLzbHJI=; b=tVcGGoQbXB/4Bx28fX98h0fkov6KrxgTcxS9lhES433DDqzEzd4f+ypVTM1izgDPLv NwPsJSsqt4BbUGvFZ/0dfVds3VrfiOYctg1oEfcGKMVg/7JQuiZ+dw8BNWGjbTdkFEZT hd5kXER5lGZ9I4ZLOYgAaHW1u5FCY4lXF2DcVpbVe3PDIVq1qTDT7eOBuf1crSzfUWBv Uaoe+64Nt+VVfK/IQi4bcF+KRAt/j7e3MVukM/SPvXEq/cjbBCQljN+xQZrr6j8R/hMd I7lC6kgVVLZ4IFvBaSewKxQbn91AEGnADAgOAh/dQXqb8+23paDOEpa3R485x8zy0T1M SrPA== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@sourceware.org header.s=default header.b=Ctq96kwR; 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=sourceware.org Return-Path: Received: from sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id hw20-20020a170907a0d400b007c12c63d1f4si16715086ejc.813.2023.01.13.10.28.54 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 10:28:54 -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=@sourceware.org header.s=default header.b=Ctq96kwR; 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=sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 18EEB388456B for ; Fri, 13 Jan 2023 18:28:53 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 18EEB388456B DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=sourceware.org; s=default; t=1673634533; bh=Lr8fcCFCLEXMcMa2jAwiXGOwETn0rlrYauVuqLzbHJI=; 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=Ctq96kwRC46SObv+0Il0sO/X/8Y0uD7TD3s99JV9uLpxZjglzhny8B494Eydg9+AJ gGhRTNUa50hawYOtOqr/wH3mPkwinkYUAL/N5sUocMDX96pvTwS5fZI2eNcCovAlHk jQVRlqYOaMqL2x3W6L0zeMmViNOmZsGaRwS3xypw= X-Original-To: libc-alpha@sourceware.org Delivered-To: libc-alpha@sourceware.org Received: from mail-pj1-x102c.google.com (mail-pj1-x102c.google.com [IPv6:2607:f8b0:4864:20::102c]) by sourceware.org (Postfix) with ESMTPS id E2D5C383FB85 for ; Fri, 13 Jan 2023 18:27:47 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org E2D5C383FB85 Received: by mail-pj1-x102c.google.com with SMTP id s13-20020a17090a6e4d00b0022900843652so6273447pjm.1 for ; Fri, 13 Jan 2023 10:27:47 -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=Lr8fcCFCLEXMcMa2jAwiXGOwETn0rlrYauVuqLzbHJI=; b=EIoDQULnvPqLF4k44R3Yyo9zj3T1HD8Ow1iyCp1R1KI6Qjif7aDHAuMa4Lhe8LYB6O S/GPZjRyGwviaLqx+zM0Svfc1K+tMRiPgGwlye5YKr87R2aukFdj07+LbGDFg7Fo8srx xIPXyHFEF8E4NXR9tuqiafzhI2bNoAIk9dg9D6qp8kvOOHdUmg8fNC5i05ah+j67JUpB rDrhw2HqBLQEynVMLnJab+Go2Mqda+VlTMrJ6PGly0DsGQE9IZpAfa5CSSZdm2m6+jSd 241axyh4yz6jwoVILANspCEJVWBAToIhO60MkpZeUj34bXNQwRD2WBby/nqnteX7iU0j ZToQ== X-Gm-Message-State: AFqh2krSOzjQcYFLkyO235P28m7t3edlsNCybp4J8n+6mP3Dtb92pxrT kiT5aa8uMJNW6lMYwLrd8LwUXdnxrkjHl2es X-Received: by 2002:a17:903:250:b0:194:7220:3c1d with SMTP id j16-20020a170903025000b0019472203c1dmr3452841plh.64.1673634466877; Fri, 13 Jan 2023 10:27:46 -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.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 13 Jan 2023 10:27:46 -0800 (PST) To: libc-alpha@sourceware.org Cc: adhemerval.zanella@linaro.org, goldstein.w.n@gmail.com Subject: [PATCH v8 07/17] string: Improve generic strchr Date: Fri, 13 Jan 2023 08:27:23 -1000 Message-Id: <20230113182733.1268668-8-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=-11.9 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 algorithm now calls strchrnul. Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc-linux-gnu, and powerpc64-linux-gnu by removing the arch-specific assembly implementation and disabling multi-arch (it covers both LE and BE for 64 and 32 bits). Message-Id: <20230111204558.2402155-8-adhemerval.zanella@linaro.org> --- string/strchr.c | 159 ++-------------------------------------- sysdeps/s390/strchr-c.c | 13 ++-- 2 files changed, 15 insertions(+), 157 deletions(-) diff --git a/string/strchr.c b/string/strchr.c index 1572b8b42e..30c3eb10f2 100644 --- a/string/strchr.c +++ b/string/strchr.c @@ -21,165 +21,22 @@ . */ #include -#include #undef strchr +#undef index -#ifndef STRCHR -# define STRCHR strchr +#ifdef STRCHR +# define strchr STRCHR #endif /* Find the first occurrence of C in S. */ char * -STRCHR (const char *s, int c_in) +strchr (const char *s, int c_in) { - const unsigned char *char_ptr; - const unsigned long int *longword_ptr; - unsigned long int longword, magic_bits, charmask; - unsigned char c; - - c = (unsigned char) c_in; - - /* Handle the first few characters by reading one character at a time. - Do this until CHAR_PTR is aligned on a longword boundary. */ - for (char_ptr = (const unsigned char *) s; - ((unsigned long int) char_ptr & (sizeof (longword) - 1)) != 0; - ++char_ptr) - if (*char_ptr == c) - return (void *) char_ptr; - else if (*char_ptr == '\0') - return NULL; - - /* All these elucidatory comments refer to 4-byte longwords, - but the theory applies equally well to 8-byte longwords. */ - - longword_ptr = (unsigned long int *) char_ptr; - - /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits - the "holes." Note that there is a hole just to the left of - each byte, with an extra at the end: - - bits: 01111110 11111110 11111110 11111111 - bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD - - The 1-bits make sure that carries propagate to the next 0-bit. - The 0-bits provide holes for carries to fall into. */ - magic_bits = -1; - magic_bits = magic_bits / 0xff * 0xfe << 1 >> 1 | 1; - - /* Set up a longword, each of whose bytes is C. */ - charmask = c | (c << 8); - charmask |= charmask << 16; - if (sizeof (longword) > 4) - /* Do the shift in two steps to avoid a warning if long has 32 bits. */ - charmask |= (charmask << 16) << 16; - if (sizeof (longword) > 8) - abort (); - - /* Instead of the traditional loop which tests each character, - we will test a longword at a time. The tricky part is testing - if *any of the four* bytes in the longword in question are zero. */ - for (;;) - { - /* We tentatively exit the loop if adding MAGIC_BITS to - LONGWORD fails to change any of the hole bits of LONGWORD. - - 1) Is this safe? Will it catch all the zero bytes? - Suppose there is a byte with all zeros. Any carry bits - propagating from its left will fall into the hole at its - least significant bit and stop. Since there will be no - carry from its most significant bit, the LSB of the - byte to the left will be unchanged, and the zero will be - detected. - - 2) Is this worthwhile? Will it ignore everything except - zero bytes? Suppose every byte of LONGWORD has a bit set - somewhere. There will be a carry into bit 8. If bit 8 - is set, this will carry into bit 16. If bit 8 is clear, - one of bits 9-15 must be set, so there will be a carry - into bit 16. Similarly, there will be a carry into bit - 24. If one of bits 24-30 is set, there will be a carry - into bit 31, so all of the hole bits will be changed. - - The one misfire occurs when bits 24-30 are clear and bit - 31 is set; in this case, the hole at bit 31 is not - changed. If we had access to the processor carry flag, - we could close this loophole by putting the fourth hole - at bit 32! - - So it ignores everything except 128's, when they're aligned - properly. - - 3) But wait! Aren't we looking for C as well as zero? - Good point. So what we do is XOR LONGWORD with a longword, - each of whose bytes is C. This turns each byte that is C - into a zero. */ - - longword = *longword_ptr++; - - /* Add MAGIC_BITS to LONGWORD. */ - if ((((longword + magic_bits) - - /* Set those bits that were unchanged by the addition. */ - ^ ~longword) - - /* Look at only the hole bits. If any of the hole bits - are unchanged, most likely one of the bytes was a - zero. */ - & ~magic_bits) != 0 - - /* That caught zeroes. Now test for C. */ - || ((((longword ^ charmask) + magic_bits) ^ ~(longword ^ charmask)) - & ~magic_bits) != 0) - { - /* Which of the bytes was C or zero? - If none of them were, it was a misfire; continue the search. */ - - const unsigned char *cp = (const unsigned char *) (longword_ptr - 1); - - if (*cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (sizeof (longword) > 4) - { - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - if (*++cp == c) - return (char *) cp; - else if (*cp == '\0') - return NULL; - } - } - } - - return NULL; + char *r = __strchrnul (s, c_in); + return (*(unsigned char *)r == (unsigned char)c_in) ? r : NULL; } - -#ifdef weak_alias -# undef index +#ifndef STRCHR weak_alias (strchr, index) -#endif libc_hidden_builtin_def (strchr) +#endif diff --git a/sysdeps/s390/strchr-c.c b/sysdeps/s390/strchr-c.c index c00f2cceea..90822ae0f4 100644 --- a/sysdeps/s390/strchr-c.c +++ b/sysdeps/s390/strchr-c.c @@ -21,13 +21,14 @@ #if HAVE_STRCHR_C # if HAVE_STRCHR_IFUNC # define STRCHR STRCHR_C -# undef weak_alias -# if defined SHARED && IS_IN (libc) -# undef libc_hidden_builtin_def -# define libc_hidden_builtin_def(name) \ - __hidden_ver1 (__strchr_c, __GI_strchr, __strchr_c); -# endif # endif # include + +# if HAVE_STRCHR_IFUNC +# if defined SHARED && IS_IN (libc) +__hidden_ver1 (__strchr_c, __GI_strchr, __strchr_c); +# endif +# endif + #endif