From patchwork Wed May 27 11:42:01 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ondrej Bilka X-Patchwork-Id: 6944 Received: (qmail 92618 invoked by alias); 27 May 2015 11:42:23 -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 92606 invoked by uid 89); 27 May 2015 11:42:22 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=2.1 required=5.0 tests=AWL, BAYES_99, BAYES_999, FREEMAIL_FROM, SPF_NEUTRAL autolearn=no version=3.3.2 X-HELO: popelka.ms.mff.cuni.cz Date: Wed, 27 May 2015 13:42:01 +0200 From: =?utf-8?B?T25kxZllaiBCw61sa2E=?= To: libc-alpha@sourceware.org Subject: [PATCH 4/*] Generic string memchr and strnlen Message-ID: <20150527114201.GA4018@domone> References: <20150527060121.GA19105@domone> <20150527090717.GA27814@domone> <20150527091858.GC27814@domone> MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: <20150527091858.GC27814@domone> User-Agent: Mutt/1.5.20 (2009-06-14) Here we first deal with functions that use size bound. Main technical complication is pointer wraparound for large n so it needs to be handled accordingly. Otherwise its almost same as rawmemchr. As I wrote before that we could optimize memchr(x,0,n) to strnlen opposite is also true. Here strnlen uses memchr and lets gcc simply that. Comments? * string/memchr.c: Use skeleton. * string/strnlen.c: Likewise. diff --git a/string/memchr.c b/string/memchr.c index 6896465..fede01a 100644 --- a/string/memchr.c +++ b/string/memchr.c @@ -1,10 +1,5 @@ /* Copyright (C) 1991-2015 Free Software Foundation, Inc. This file is part of the GNU C Library. - Based on strlen implementation by Torbjorn Granlund (tege@sics.se), - with help from Dan Sahlin (dan@sics.se) and - commentary by Jim Blandy (jimb@ai.mit.edu); - adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu), - and implemented by Roland McGrath (roland@ai.mit.edu). The GNU C Library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public @@ -20,143 +15,41 @@ License along with the GNU C Library; if not, see . */ -#ifndef _LIBC -# include -#endif - #include - -#include - -#include +#include #undef __memchr -#ifdef _LIBC -# undef memchr -#endif +#undef memchr -#ifndef weak_alias -# define __memchr memchr -#endif +/* Return the length of the null-terminated string STR. Scan for + the null terminator quickly by testing four bytes at a time. */ + +#include "string/common.h" +#define EXPRESSION(p, c) (contains_zero (p ^ c)) +#define BOUND(p) ((uintptr_t) p >= (uintptr_t) end) +#include "string/skeleton.h" #ifndef MEMCHR # define MEMCHR __memchr #endif -/* Search no more than N bytes of S for C. */ +#ifdef STATIC +static __always_inline +#endif void * -MEMCHR (void const *s, int c_in, size_t n) +MEMCHR (const void *_str, int c, size_t n) { - /* On 32-bit hardware, choosing longword to be a 32-bit unsigned - long instead of a 64-bit uintmax_t tends to give better - performance. On 64-bit hardware, unsigned long is generally 64 - bits already. Change this typedef to experiment with - performance. */ - typedef unsigned long int longword; - - const unsigned char *char_ptr; - const longword *longword_ptr; - longword repeated_one; - longword repeated_c; - unsigned char c; - - c = (unsigned char) c_in; - - /* Handle the first few bytes by reading one byte at a time. - Do this until CHAR_PTR is aligned on a longword boundary. */ - for (char_ptr = (const unsigned char *) s; - n > 0 && (size_t) char_ptr % sizeof (longword) != 0; - --n, ++char_ptr) - if (*char_ptr == c) - return (void *) char_ptr; - - longword_ptr = (const longword *) char_ptr; - - /* All these elucidatory comments refer to 4-byte longwords, - but the theory applies equally well to any size longwords. */ - - /* Compute auxiliary longword values: - repeated_one is a value which has a 1 in every byte. - repeated_c has c in every byte. */ - repeated_one = 0x01010101; - repeated_c = c | (c << 8); - repeated_c |= repeated_c << 16; - if (0xffffffffU < (longword) -1) - { - repeated_one |= repeated_one << 31 << 1; - repeated_c |= repeated_c << 31 << 1; - if (8 < sizeof (longword)) - { - size_t i; - - for (i = 64; i < sizeof (longword) * 8; i *= 2) - { - repeated_one |= repeated_one << i; - repeated_c |= repeated_c << i; - } - } - } - - /* Instead of the traditional loop which tests each byte, 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 equal to c. We first use an xor - with repeated_c. This reduces the task to testing whether *any of the - four* bytes in longword1 is zero. - - We compute tmp = - ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). - That is, we perform the following operations: - 1. Subtract repeated_one. - 2. & ~longword1. - 3. & a mask consisting of 0x80 in every byte. - Consider what happens in each byte: - - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, - and step 3 transforms it into 0x80. A carry can also be propagated - to more significant bytes. - - If a byte of longword1 is nonzero, let its lowest 1 bit be at - position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, - the byte ends in a single bit of value 0 and k bits of value 1. - After step 2, the result is just k bits of value 1: 2^k - 1. After - step 3, the result is 0. And no carry is produced. - So, if longword1 has only non-zero bytes, tmp is zero. - Whereas if longword1 has a zero byte, call j the position of the least - significant zero byte. Then the result has a zero at positions 0, ..., - j-1 and a 0x80 at position j. We cannot predict the result at the more - significant bytes (positions j+1..3), but it does not matter since we - already have a non-zero bit at position 8*j+7. - - So, the test whether any byte in longword1 is zero is equivalent to - testing whether tmp is nonzero. */ - - while (n >= sizeof (longword)) - { - longword longword1 = *longword_ptr ^ repeated_c; - - if ((((longword1 - repeated_one) & ~longword1) - & (repeated_one << 7)) != 0) - break; - longword_ptr++; - n -= sizeof (longword); - } - - char_ptr = (const unsigned char *) longword_ptr; - - /* At this point, we know that either n < sizeof (longword), or one of the - sizeof (longword) bytes starting at char_ptr is == c. On little-endian - machines, we could determine the first such byte without any further - memory accesses, just by looking at the tmp result from the last loop - iteration. But this does not work on big-endian machines. Choose code - that works in both cases. */ - - for (; n > 0; --n, ++char_ptr) - { - if (*char_ptr == c) - return (void *) char_ptr; - } - - return NULL; + if (n == 0) + return NULL; + char *str = (char *) _str; + char *end = (char *) (((uintptr_t) str) + n); + if ((uintptr_t) end < (uintptr_t) str) + end = (char *) UINTPTR_MAX; + char *ret = string_skeleton (str, c, end); + return (void *)((uintptr_t) ret < (uintptr_t) end ? ret : NULL); } -#ifdef weak_alias + +#ifndef STATIC weak_alias (__memchr, memchr) -#endif libc_hidden_builtin_def (memchr) +#endif diff --git a/string/strnlen.c b/string/strnlen.c index 803d78b..a5917de 100644 --- a/string/strnlen.c +++ b/string/strnlen.c @@ -1,15 +1,10 @@ -/* Find the length of STRING, but scan at most MAXLEN characters. - Copyright (C) 1991-2015 Free Software Foundation, Inc. - Contributed by Jakub Jelinek . - - Based on strlen written by Torbjorn Granlund (tege@sics.se), - with help from Dan Sahlin (dan@sics.se); - commentary by Jim Blandy (jimb@ai.mit.edu). +/* Copyright (C) 1991-2015 Free Software Foundation, Inc. + This file is part of the GNU C Library. The GNU C Library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public License as - published by the Free Software Foundation; either version 2.1 of the - License, or (at your option) any later version. + modify it under the terms of the GNU Lesser General Public + License as published by the Free Software Foundation; either + version 2.1 of the License, or (at your option) any later version. The GNU C Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of @@ -17,149 +12,28 @@ Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public - License along with the GNU C Library; see the file COPYING.LIB. If - not, see . */ + License along with the GNU C Library; if not, see + . */ #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. */ +#undef strlen + +/* Return the length of the null-terminated string STR. Scan for + the null terminator quickly by testing four bytes at a time. */ -#ifdef STRNLEN -# define __strnlen STRNLEN -#endif +#define STATIC +#define MEMCHR memchr_static +#include "string/memchr.c" size_t -__strnlen (const char *str, size_t maxlen) +__strnlen (const char *str, size_t n) { - const char *char_ptr, *end_ptr = str + maxlen; - const unsigned long int *longword_ptr; - unsigned long int longword, himagic, lomagic; - - if (maxlen == 0) - return 0; - - if (__glibc_unlikely (end_ptr < str)) - end_ptr = (const char *) ~0UL; - - /* 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) - if (*char_ptr == '\0') - { - if (char_ptr > end_ptr) - char_ptr = end_ptr; - return char_ptr - str; - } - - /* 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. */ - himagic = 0x80808080L; - lomagic = 0x01010101L; - if (sizeof (longword) > 4) - { - /* 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) - { - /* 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 = end_ptr; - } - - if (char_ptr > end_ptr) - char_ptr = end_ptr; - return char_ptr - str; + char *ret = MEMCHR (str, 0, n); + return ret ? ret - str : n; } -#ifndef STRNLEN + weak_alias (__strnlen, strnlen) -#endif libc_hidden_def (strnlen) +