From patchwork Sat Dec 17 06:57:25 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 706657 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 3tgdMd3Nkdz9t2D for ; Sat, 17 Dec 2016 17:59:25 +1100 (AEDT) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; secure) header.d=sourceware.org header.i=@sourceware.org header.b="SudTre4X"; 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=tUywkohqNcreCrBUdSHaGNB45ZXS5oG 3+aNmamiI3deD9S1vmfXi+4FVsUd6TjRxSq+zrJpACTO3wRxQUVwNp9RVesWAFNI 8ZG9rW8FQAme96mIDtugENbrI63WIK85sS3uQ2D93evc+M/7ASqXAfEFyb/SD/zl D/YVeK7S+c4M= 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=f8CXkvxpiaqvUShh0fd4+AwNkTQ=; b=SudTr e4XOwQLTs1+B8DgogUrPTZQzwz7z7EGKlOOOTtE64R3jOTEQhSW1G/TCuiF8jHkc e+z3xhp4Y+kigOyL8bL8zUSTMfySJ00TypMZAjwMB3NVT4vIkxwN8sEtWQWSTihb CqTCMoEgUFmp5luxPosLx8zChYVVwqG+VEU50M= Received: (qmail 93529 invoked by alias); 17 Dec 2016 06:57:54 -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 92928 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=4826, holes X-HELO: mail-pg0-f66.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=uZQhGrnI0vaU2ZY5uzH8QOYAPYsUp672FcobrllGgNQ=; b=YDs9U8SULe7pjKAWqi/ROQN63pCaetCbpturAVGbOpufbNlZ7raKoHHsVolhHFrorc B/nVRr4xX7PL5WwJgE+dAWGCCxV6h5NQbT8a+ubx7flT3kFzirCI3gKDi8/j4upIAFNk K2GD2u0JWeHiXjHd0E1zplkG3WFMXy5RTs/NJVMJk4/bh1Onf33bZfuJLu0uieV/ixlR H+FgZqw3VWvphX6zf9zNiBOwZ+Rk3ELyY87yMVYC2vm5p/+V0tUyfDxrzELyBCyGZzh8 jthIBNsYpBub/WYq/AGsv4hfAK8JbsiVRyzR/9AO5G1K/W89zMGeAXwpztP+gc+/MdWR RAUA== X-Gm-Message-State: AKaTC006LeoprI7WgT7lp4mE0cT0Y5RxWLWnwRd5tFgh3wR3/V3L7AoVx/wTghjIB6GlMg== X-Received: by 10.84.198.129 with SMTP id p1mr15178656pld.14.1481957864048; Fri, 16 Dec 2016 22:57:44 -0800 (PST) From: Richard Henderson To: libc-alpha@sourceware.org Subject: [PATCH 07/11] Improve generic strnlen Date: Fri, 16 Dec 2016 22:57:25 -0800 Message-Id: <20161217065729.28561-8-rth@twiddle.net> In-Reply-To: <20161217065729.28561-1-rth@twiddle.net> References: <20161217065729.28561-1-rth@twiddle.net> * string/strnlen.c: Use haszero.h, whichzero.h. --- string/strnlen.c | 125 +++++++++---------------------------------------------- 1 file changed, 19 insertions(+), 106 deletions(-) diff --git a/string/strnlen.c b/string/strnlen.c index b2b0664..9927b9d 100644 --- a/string/strnlen.c +++ b/string/strnlen.c @@ -21,7 +21,9 @@ not, see . */ #include -#include +#include +#include +#include /* Find the length of S, but scan at most MAXLEN characters. If no '\0' terminator is found in that many characters, return MAXLEN. */ @@ -33,11 +35,12 @@ size_t __strnlen (const char *str, size_t maxlen) { - const char *char_ptr, *end_ptr = str + maxlen; + const char *char_ptr = str, *end_ptr = str + maxlen; const unsigned long int *longword_ptr; - unsigned long int longword, himagic, lomagic; + unsigned long int longword; + size_t i, align; - if (maxlen == 0) + if (__glibc_unlikely (maxlen == 0)) return 0; if (__glibc_unlikely (end_ptr < str)) @@ -45,116 +48,26 @@ __strnlen (const char *str, size_t maxlen) /* 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 = str; ((unsigned long int) char_ptr - & (sizeof (longword) - 1)) != 0; - ++char_ptr) + align = -(uintptr_t)char_ptr % sizeof(longword); + for (i = 0; i < align; ++i, ++char_ptr) if (*char_ptr == '\0') - { - if (char_ptr > end_ptr) - char_ptr = end_ptr; - return char_ptr - str; - } + goto found; - /* All these elucidatory comments refer to 4-byte longwords, - but the theory applies equally well to 8-byte longwords. */ + longword_ptr = (const unsigned long int *) char_ptr; + char_ptr = end_ptr; - 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. */ - himagic = 0x80808080L; - lomagic = 0x01010101L; - if (sizeof (longword) > 4) + while (longword_ptr < (const unsigned long int *) end_ptr) { - /* 64-bit version of the magic. */ - /* Do the shift in two steps to avoid a warning if long has 32 bits. */ - himagic = ((himagic << 16) << 16) | himagic; - lomagic = ((lomagic << 16) << 16) | lomagic; - } - 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. */ - while (longword_ptr < (unsigned long int *) end_ptr) - { - /* 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. */ - - longword = *longword_ptr++; - - if ((longword - lomagic) & himagic) + longword = *longword_ptr; + if (haszero (longword)) { - /* Which of the bytes was the zero? If none of them were, it was - a misfire; continue the search. */ - - const char *cp = (const char *) (longword_ptr - 1); - - char_ptr = cp; - if (cp[0] == 0) - break; - char_ptr = cp + 1; - if (cp[1] == 0) - break; - char_ptr = cp + 2; - if (cp[2] == 0) - break; - char_ptr = cp + 3; - if (cp[3] == 0) - break; - if (sizeof (longword) > 4) - { - char_ptr = cp + 4; - if (cp[4] == 0) - break; - char_ptr = cp + 5; - if (cp[5] == 0) - break; - char_ptr = cp + 6; - if (cp[6] == 0) - break; - char_ptr = cp + 7; - if (cp[7] == 0) - break; - } + char_ptr = (const char *) longword_ptr + whichzero (longword); + break; } - char_ptr = end_ptr; + longword_ptr++; } + found: if (char_ptr > end_ptr) char_ptr = end_ptr; return char_ptr - str;