From patchwork Sat Dec 17 06:57:23 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 706650 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3tgdLL1QYlz9t2D for ; Sat, 17 Dec 2016 17:58:18 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="QOge+11n"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; q=dns; s=default; b=lNdT4GfWMJ4BRj9Ybg2LHSnZzigQgrn /mngpjGxpZLUU8eStX2EmShXCpexVtWp/v1cyLRKx/ZkXBQxbigkiOAO3IdYr7Lb cco5grZOQi6J3w7A3xPQUCpjyi47QKusQ0aotHKtnk0lKOxM0yVEp2SCfj23yc0u x+ayC7oSNYtY= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id :list-unsubscribe:list-subscribe:list-archive:list-post :list-help:sender:from:to:subject:date:message-id:in-reply-to :references; s=default; bh=422IIpdMojO9lqFw3GNz8E3jlqs=; b=QOge+ 11nJGYCZr6e8WtAavMSDrXsteesksDpUNbq5gpun6KQzB4kXP7so3AFnd+2EdjS3 /x+wRrq/HeQEIYUXsYI2l/BHPhhPpYRcAgP4PIGaNSKL0W9QZtPGSmwr47Yryx9w cLCE7saVAu27stk4qbypyMWtEW8ZtXHvpuKQQ8= Received: (qmail 93093 invoked by alias); 17 Dec 2016 06:57:52 -0000 Mailing-List: contact libc-alpha-help@sourceware.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Subscribe: List-Archive: List-Post: List-Help: , Sender: libc-alpha-owner@sourceware.org Delivered-To: mailing list libc-alpha@sourceware.org Received: (qmail 92934 invoked by uid 89); 17 Dec 2016 06:57:51 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-1.6 required=5.0 tests=BAYES_00, FREEMAIL_ENVFROM_END_DIGIT, FREEMAIL_FROM, RCVD_IN_DNSWL_NONE, SPF_PASS autolearn=no version=3.3.2 spammy=eos X-HELO: mail-pf0-f193.google.com X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:sender:from:to:subject:date:message-id :in-reply-to:references; bh=RmraR7x5gLmmxfS7Hb1jkxLViFOvWXke+ssdMcnVZLo=; b=Qboo6o2d5wQ1ADmiBGNEEuGLIMxCBj8idO/gAhMQGUr43mBfZq5TMqUljnb1CqxkaC KptTh38y9B/wRD6jmWJARGiSb5D/96vgfKHLvMrekpqnf2JFNzVtpiu45Nuyy1Qa23bP HMtuP/UaKOHsDHQ0i1wKGFnGQmgvF6IaH1Uknto1uCkaHBwkD/4y1f7+PyPY7xOR8f+6 eFOpGzDnyEktou8Q7I2vF1PMz49/Sxtg+9pB9Qsz4HcxziwDSzwEOTsXzghvdEuMRws+ 7tzBYCNfMJWY1X0fQ91y6uVZ+5/8asqiEym69w7pKbg+Ggk2Pw4UlwHwI99wQszqhA1P 1V8w== X-Gm-Message-State: AKaTC012F/gFtGqfSIfH8nPQwBTf7r3R6g9masjYEueziIroCi6L85puAKs+BIRpAxc6NA== X-Received: by 10.84.217.149 with SMTP id p21mr15016194pli.121.1481957862598; Fri, 16 Dec 2016 22:57:42 -0800 (PST) From: Richard Henderson To: libc-alpha@sourceware.org Subject: [PATCH 05/11] Improve generic strrchr Date: Fri, 16 Dec 2016 22:57:23 -0800 Message-Id: <20161217065729.28561-6-rth@twiddle.net> In-Reply-To: <20161217065729.28561-1-rth@twiddle.net> References: <20161217065729.28561-1-rth@twiddle.net> * string/strrchr.c: Use haszero.h. --- string/strrchr.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++---------- 1 file changed, 56 insertions(+), 11 deletions(-) diff --git a/string/strrchr.c b/string/strrchr.c index a07457e..bea7d76 100644 --- a/string/strrchr.c +++ b/string/strrchr.c @@ -16,6 +16,10 @@ . */ #include +#include +#include +#include +#include #undef strrchr @@ -25,25 +29,66 @@ /* Find the last occurrence of C in S. */ char * -STRRCHR (const char *s, int c) +STRRCHR (const char *s, int int_c) { - const char *found, *p; + const unsigned char *found_c = NULL, *ptr_c; + const unsigned long int *found_w = NULL, *ptr_w; + unsigned long int longword, repeated_c; + uintptr_t i, align; + unsigned char c; - c = (unsigned char) c; + c = (unsigned char) int_c; + ptr_c = (const unsigned char *) s; - /* Since strchr is fast, we use it rather than the obvious loop. */ + /* Handle the first few characters by reading one character at a time. + Do this until CHAR_PTR is aligned on a longword boundary. */ + align = -(uintptr_t)ptr_c % sizeof(longword); + for (i = 0; i < align; ++i, ++ptr_c) + { + unsigned char this_c = *ptr_c; + if (this_c == c) + found_c = ptr_c; + if (this_c == '\0') + goto done; + } + + /* Set up a longword, each of whose bytes is C. */ + repeated_c = (-1ul / 0xff) * c; + + /* Search words for C. At this point, merely record the last word + that contained the character. Stop when we find EOS. */ + ptr_w = (const unsigned long int *) ptr_c; + while (1) + { + longword = *ptr_w; + if (haszero (longword)) + break; + if (haszero (longword ^ repeated_c)) + found_w = ptr_w; + ptr_w++; + } - if (c == '\0') - return strchr (s, '\0'); + /* Check to see if we've got C in the last longword. */ + i = whichzero2 (longword, longword ^ repeated_c); + if (extractbyte (longword, i) == c) + found_w = ptr_w; - found = NULL; - while ((p = strchr (s, c)) != NULL) + /* If we found a word containing C, go back and search it byte by byte. */ + if (found_w) { - found = p; - s = p + 1; + ptr_c = (const unsigned char *) found_w; + for (i = 0; i < sizeof(longword); ++i, ++ptr_c) + { + unsigned char this_c = *ptr_c; + if (this_c == c) + found_c = ptr_c; + if (this_c == '\0') + break; + } } - return (char *) found; + done: + return (char *) found_c; } #ifdef weak_alias