105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2012 205436638acc7c010349a69c3395f1a57c642dc62Ying Wang Free Software Foundation, Inc. 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang Based on strlen implementation by Torbjorn Granlund (tege@sics.se), 505436638acc7c010349a69c3395f1a57c642dc62Ying Wang with help from Dan Sahlin (dan@sics.se) and 605436638acc7c010349a69c3395f1a57c642dc62Ying Wang commentary by Jim Blandy (jimb@ai.mit.edu); 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu), 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang and implemented by Roland McGrath (roland@ai.mit.edu). 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1005436638acc7c010349a69c3395f1a57c642dc62Ying WangNOTE: The canonical source of this file is maintained with the GNU C Library. 1105436638acc7c010349a69c3395f1a57c642dc62Ying WangBugs can be reported to bug-glibc@prep.ai.mit.edu. 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1305436638acc7c010349a69c3395f1a57c642dc62Ying WangThis program is free software: you can redistribute it and/or modify it 1405436638acc7c010349a69c3395f1a57c642dc62Ying Wangunder the terms of the GNU General Public License as published by the 1505436638acc7c010349a69c3395f1a57c642dc62Ying WangFree Software Foundation; either version 3 of the License, or any 1605436638acc7c010349a69c3395f1a57c642dc62Ying Wanglater version. 1705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1805436638acc7c010349a69c3395f1a57c642dc62Ying WangThis program is distributed in the hope that it will be useful, 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wangbut WITHOUT ANY WARRANTY; without even the implied warranty of 2005436638acc7c010349a69c3395f1a57c642dc62Ying WangMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 2105436638acc7c010349a69c3395f1a57c642dc62Ying WangGNU General Public License for more details. 2205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2305436638acc7c010349a69c3395f1a57c642dc62Ying WangYou should have received a copy of the GNU General Public License 2405436638acc7c010349a69c3395f1a57c642dc62Ying Wangalong with this program. If not, see <http://www.gnu.org/licenses/>. */ 2505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#ifndef _LIBC 2705436638acc7c010349a69c3395f1a57c642dc62Ying Wang# include <config.h> 2805436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 2905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <string.h> 3105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <stddef.h> 3305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3405436638acc7c010349a69c3395f1a57c642dc62Ying Wang#if defined _LIBC 3505436638acc7c010349a69c3395f1a57c642dc62Ying Wang# include <memcopy.h> 3605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#else 3705436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define reg_char char 3805436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 3905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include <limits.h> 4105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#if HAVE_BP_SYM_H || defined _LIBC 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang# include <bp-sym.h> 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang#else 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define BP_SYM(sym) sym 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wang#undef __memchr 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wang#ifdef _LIBC 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang# undef memchr 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 5305436638acc7c010349a69c3395f1a57c642dc62Ying Wang#ifndef weak_alias 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang# define __memchr memchr 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Search no more than N bytes of S for C. */ 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wangvoid * 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang__memchr (void const *s, int c_in, size_t n) 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* On 32-bit hardware, choosing longword to be a 32-bit unsigned 6205436638acc7c010349a69c3395f1a57c642dc62Ying Wang long instead of a 64-bit uintmax_t tends to give better 6305436638acc7c010349a69c3395f1a57c642dc62Ying Wang performance. On 64-bit hardware, unsigned long is generally 64 6405436638acc7c010349a69c3395f1a57c642dc62Ying Wang bits already. Change this typedef to experiment with 6505436638acc7c010349a69c3395f1a57c642dc62Ying Wang performance. */ 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang typedef unsigned long int longword; 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 6805436638acc7c010349a69c3395f1a57c642dc62Ying Wang const unsigned char *char_ptr; 6905436638acc7c010349a69c3395f1a57c642dc62Ying Wang const longword *longword_ptr; 7005436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword repeated_one; 7105436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword repeated_c; 7205436638acc7c010349a69c3395f1a57c642dc62Ying Wang unsigned reg_char c; 7305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 7405436638acc7c010349a69c3395f1a57c642dc62Ying Wang c = (unsigned char) c_in; 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 7605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Handle the first few bytes by reading one byte at a time. 7705436638acc7c010349a69c3395f1a57c642dc62Ying Wang Do this until CHAR_PTR is aligned on a longword boundary. */ 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (char_ptr = (const unsigned char *) s; 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wang n > 0 && (size_t) char_ptr % sizeof (longword) != 0; 8005436638acc7c010349a69c3395f1a57c642dc62Ying Wang --n, ++char_ptr) 8105436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (*char_ptr == c) 8205436638acc7c010349a69c3395f1a57c642dc62Ying Wang return (void *) char_ptr; 8305436638acc7c010349a69c3395f1a57c642dc62Ying Wang 8405436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword_ptr = (const longword *) char_ptr; 8505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 8605436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* All these elucidatory comments refer to 4-byte longwords, 8705436638acc7c010349a69c3395f1a57c642dc62Ying Wang but the theory applies equally well to any size longwords. */ 8805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 8905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Compute auxiliary longword values: 9005436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_one is a value which has a 1 in every byte. 9105436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_c has c in every byte. */ 9205436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_one = 0x01010101; 9305436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_c = c | (c << 8); 9405436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_c |= repeated_c << 16; 9505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (0xffffffffU < (longword) -1) 9605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 9705436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_one |= repeated_one << 31 << 1; 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_c |= repeated_c << 31 << 1; 9905436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (8 < sizeof (longword)) 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10105436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 10205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 64; i < sizeof (longword) * 8; i *= 2) 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_one |= repeated_one << i; 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang repeated_c |= repeated_c << i; 10705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 10805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 10905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 11005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11105436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Instead of the traditional loop which tests each byte, we will test a 11205436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword at a time. The tricky part is testing if *any of the four* 11305436638acc7c010349a69c3395f1a57c642dc62Ying Wang bytes in the longword in question are equal to c. We first use an xor 11405436638acc7c010349a69c3395f1a57c642dc62Ying Wang with repeated_c. This reduces the task to testing whether *any of the 11505436638acc7c010349a69c3395f1a57c642dc62Ying Wang four* bytes in longword1 is zero. 11605436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11705436638acc7c010349a69c3395f1a57c642dc62Ying Wang We compute tmp = 11805436638acc7c010349a69c3395f1a57c642dc62Ying Wang ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). 11905436638acc7c010349a69c3395f1a57c642dc62Ying Wang That is, we perform the following operations: 12005436638acc7c010349a69c3395f1a57c642dc62Ying Wang 1. Subtract repeated_one. 12105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 2. & ~longword1. 12205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 3. & a mask consisting of 0x80 in every byte. 12305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Consider what happens in each byte: 12405436638acc7c010349a69c3395f1a57c642dc62Ying Wang - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, 12505436638acc7c010349a69c3395f1a57c642dc62Ying Wang and step 3 transforms it into 0x80. A carry can also be propagated 12605436638acc7c010349a69c3395f1a57c642dc62Ying Wang to more significant bytes. 12705436638acc7c010349a69c3395f1a57c642dc62Ying Wang - If a byte of longword1 is nonzero, let its lowest 1 bit be at 12805436638acc7c010349a69c3395f1a57c642dc62Ying Wang position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, 12905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the byte ends in a single bit of value 0 and k bits of value 1. 13005436638acc7c010349a69c3395f1a57c642dc62Ying Wang After step 2, the result is just k bits of value 1: 2^k - 1. After 13105436638acc7c010349a69c3395f1a57c642dc62Ying Wang step 3, the result is 0. And no carry is produced. 13205436638acc7c010349a69c3395f1a57c642dc62Ying Wang So, if longword1 has only non-zero bytes, tmp is zero. 13305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Whereas if longword1 has a zero byte, call j the position of the least 13405436638acc7c010349a69c3395f1a57c642dc62Ying Wang significant zero byte. Then the result has a zero at positions 0, ..., 13505436638acc7c010349a69c3395f1a57c642dc62Ying Wang j-1 and a 0x80 at position j. We cannot predict the result at the more 13605436638acc7c010349a69c3395f1a57c642dc62Ying Wang significant bytes (positions j+1..3), but it does not matter since we 13705436638acc7c010349a69c3395f1a57c642dc62Ying Wang already have a non-zero bit at position 8*j+7. 13805436638acc7c010349a69c3395f1a57c642dc62Ying Wang 13905436638acc7c010349a69c3395f1a57c642dc62Ying Wang So, the test whether any byte in longword1 is zero is equivalent to 14005436638acc7c010349a69c3395f1a57c642dc62Ying Wang testing whether tmp is nonzero. */ 14105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 14205436638acc7c010349a69c3395f1a57c642dc62Ying Wang while (n >= sizeof (longword)) 14305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 14405436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword longword1 = *longword_ptr ^ repeated_c; 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wang 14605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if ((((longword1 - repeated_one) & ~longword1) 14705436638acc7c010349a69c3395f1a57c642dc62Ying Wang & (repeated_one << 7)) != 0) 14805436638acc7c010349a69c3395f1a57c642dc62Ying Wang break; 14905436638acc7c010349a69c3395f1a57c642dc62Ying Wang longword_ptr++; 15005436638acc7c010349a69c3395f1a57c642dc62Ying Wang n -= sizeof (longword); 15105436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 15205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 15305436638acc7c010349a69c3395f1a57c642dc62Ying Wang char_ptr = (const unsigned char *) longword_ptr; 15405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 15505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* At this point, we know that either n < sizeof (longword), or one of the 15605436638acc7c010349a69c3395f1a57c642dc62Ying Wang sizeof (longword) bytes starting at char_ptr is == c. On little-endian 15705436638acc7c010349a69c3395f1a57c642dc62Ying Wang machines, we could determine the first such byte without any further 15805436638acc7c010349a69c3395f1a57c642dc62Ying Wang memory accesses, just by looking at the tmp result from the last loop 15905436638acc7c010349a69c3395f1a57c642dc62Ying Wang iteration. But this does not work on big-endian machines. Choose code 16005436638acc7c010349a69c3395f1a57c642dc62Ying Wang that works in both cases. */ 16105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16205436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (; n > 0; --n, ++char_ptr) 16305436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 16405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (*char_ptr == c) 16505436638acc7c010349a69c3395f1a57c642dc62Ying Wang return (void *) char_ptr; 16605436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16805436638acc7c010349a69c3395f1a57c642dc62Ying Wang return NULL; 16905436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 17005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#ifdef weak_alias 17105436638acc7c010349a69c3395f1a57c642dc62Ying Wangweak_alias (__memchr, BP_SYM (memchr)) 17205436638acc7c010349a69c3395f1a57c642dc62Ying Wang#endif 173