From patchwork Wed Dec 21 23:05:56 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 18621 Received: (qmail 51413 invoked by alias); 21 Dec 2016 23:06:21 -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 51245 invoked by uid 89); 21 Dec 2016 23:06:20 -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=1638, HX-Gm-Message-State:AIkVDXI X-HELO: mail-pg0-f67.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=bBhTR/bsI7gzt9Nz+QYg4oR97JHIGaH4fkvFr4rcP2I=; b=NI1UwJ/3V3aAGjDIe9EAecdNXYRv+I2iuV+8kDwuwf4I0oUP4kVN7JV8Tm5MInpY64 WSvxgdTDQ3EJRbcRTtKkQppVdZMrHhWEMP7wVHMIlwZz52xBg+mmTmuL6O6/cyZ65AB+ ZD7CKKUrzv652YAJ6yQD+/KlXkfKzAR2rMCJhEt7KSOzFm5Cv9K+i7ZRpoo/6Ug9ZTbS 4yz7ZiWm9ryMXI038+OdIEfh6/WFakoVdot7gAxNcDzdYoB/adhyXYg2nOL4AEN1AQbU DhTYKiUhw0BoUSF5HcNzozoCmFnckl2NVnQodesdL5rzETa7zmlBREpRG2/0F8l3kQHX YG7w== X-Gm-Message-State: AIkVDXI/ZIMclhOgKMdzmZENheoCcpXbp3fTCikvrGROOqxVZ6nOGofesIgrqpBsyGSGEg== X-Received: by 10.84.191.131 with SMTP id a3mr13071929pld.62.1482361573432; Wed, 21 Dec 2016 15:06:13 -0800 (PST) From: Richard Henderson To: libc-alpha@sourceware.org Subject: [PATCH v2 07/16] Improve generic strrchr Date: Wed, 21 Dec 2016 15:05:56 -0800 Message-Id: <20161221230605.28638-8-rth@twiddle.net> In-Reply-To: <20161221230605.28638-1-rth@twiddle.net> References: <20161221230605.28638-1-rth@twiddle.net> * string/strrchr.c: Use string-fzb.h and string-fzi.h. --- string/strrchr.c | 76 +++++++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 61 insertions(+), 15 deletions(-) diff --git a/string/strrchr.c b/string/strrchr.c index a07457e..09c1043 100644 --- a/string/strrchr.c +++ b/string/strrchr.c @@ -16,38 +16,84 @@ . */ #include +#include +#include +#include +#include #undef strrchr +#undef rindex -#ifndef STRRCHR -# define STRRCHR strrchr +#ifdef STRRCHR +#define strrchr STRRCHR #endif /* 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 op_t *found_w = NULL, *ptr_w; + op_t word, 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 word boundary. */ + align = -(uintptr_t)ptr_c % sizeof(word); + 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') + return (char *) found_c; + } - if (c == '\0') - return strchr (s, '\0'); + /* Set up a word, each of whose bytes is C. */ + repeated_c = ((op_t)-1 / 0xff) * c; - found = NULL; - while ((p = strchr (s, c)) != NULL) + /* Search words for C. At this point, merely record the last word + that contained the character. Stop when we find EOS. */ + ptr_w = (const op_t *) ptr_c; + while (1) { - found = p; - s = p + 1; + word = *ptr_w; + if (has_zero (word)) + break; + if (has_eq (word, repeated_c)) + found_w = ptr_w; + ptr_w++; } - return (char *) found; + /* Check to see if we've got C in the last word. */ + i = index_first_zero_eq (word, repeated_c); + if (extractbyte (word, i) == c) + found_w = ptr_w; + + /* If we found a word containing C, go back and search it byte by byte. + This is probably cheaper than indexing for the zero within WORD, + using that to mask out following bytes that might be C, and then + indexing to find the last C. */ + if (found_w) + { + ptr_c = (const unsigned char *) found_w; + for (i = 0; i < sizeof (word); ++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_c; } -#ifdef weak_alias -#undef rindex +#ifndef STRRCHR weak_alias (strrchr, rindex) #endif libc_hidden_builtin_def (strrchr)