1/* Copyright (C) 1991,93,96,97,99,2000 Free Software Foundation, Inc. 2 Based on strlen implementation by Torbjorn Granlund (tege@sics.se), 3 with help from Dan Sahlin (dan@sics.se) and 4 commentary by Jim Blandy (jimb@ai.mit.edu); 5 adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu), 6 and implemented by Roland McGrath (roland@ai.mit.edu). 7 8NOTE: The canonical source of this file is maintained with the GNU C Library. 9Bugs can be reported to bug-glibc@prep.ai.mit.edu. 10 11This program is free software; you can redistribute it and/or modify it 12under the terms of the GNU General Public License as published by the 13Free Software Foundation; either version 2, or (at your option) any 14later version. 15 16This program is distributed in the hope that it will be useful, 17but WITHOUT ANY WARRANTY; without even the implied warranty of 18MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19GNU General Public License for more details. 20 21You should have received a copy of the GNU General Public License 22along with this program; if not, write to the Free Software 23Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 24USA. */ 25 26#ifdef HAVE_CONFIG_H 27# include <config.h> 28#endif 29 30#undef __ptr_t 31#if defined (__cplusplus) || (defined (__STDC__) && __STDC__) 32# define __ptr_t void * 33#else /* Not C++ or ANSI C. */ 34# define __ptr_t char * 35#endif /* C++ or ANSI C. */ 36 37#if defined _LIBC 38# include <string.h> 39# include <memcopy.h> 40#else 41# define reg_char char 42#endif 43 44#if HAVE_STDLIB_H || defined _LIBC 45# include <stdlib.h> 46#endif 47 48#if HAVE_LIMITS_H || defined _LIBC 49# include <limits.h> 50#endif 51 52#define LONG_MAX_32_BITS 2147483647 53 54#ifndef LONG_MAX 55# define LONG_MAX LONG_MAX_32_BITS 56#endif 57 58#include <sys/types.h> 59#if HAVE_BP_SYM_H || defined _LIBC 60# include <bp-sym.h> 61#else 62# define BP_SYM(sym) sym 63#endif 64 65#undef memchr 66#undef __memchr 67 68/* Search no more than N bytes of S for C. */ 69__ptr_t 70__memchr (s, c_in, n) 71 const __ptr_t s; 72 int c_in; 73 size_t n; 74{ 75 const unsigned char *char_ptr; 76 const unsigned long int *longword_ptr; 77 unsigned long int longword, magic_bits, charmask; 78 unsigned reg_char c; 79 80 c = (unsigned char) c_in; 81 82 /* Handle the first few characters by reading one character at a time. 83 Do this until CHAR_PTR is aligned on a longword boundary. */ 84 for (char_ptr = (const unsigned char *) s; 85 n > 0 && ((unsigned long int) char_ptr 86 & (sizeof (longword) - 1)) != 0; 87 --n, ++char_ptr) 88 if (*char_ptr == c) 89 return (__ptr_t) char_ptr; 90 91 /* All these elucidatory comments refer to 4-byte longwords, 92 but the theory applies equally well to 8-byte longwords. */ 93 94 longword_ptr = (unsigned long int *) char_ptr; 95 96 /* Bits 31, 24, 16, and 8 of this number are zero. Call these bits 97 the "holes." Note that there is a hole just to the left of 98 each byte, with an extra at the end: 99 100 bits: 01111110 11111110 11111110 11111111 101 bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD 102 103 The 1-bits make sure that carries propagate to the next 0-bit. 104 The 0-bits provide holes for carries to fall into. */ 105 106 if (sizeof (longword) != 4 && sizeof (longword) != 8) 107 abort (); 108 109#if LONG_MAX <= LONG_MAX_32_BITS 110 magic_bits = 0x7efefeff; 111#else 112 magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff; 113#endif 114 115 /* Set up a longword, each of whose bytes is C. */ 116 charmask = c | (c << 8); 117 charmask |= charmask << 16; 118#if LONG_MAX > LONG_MAX_32_BITS 119 charmask |= charmask << 32; 120#endif 121 122 /* Instead of the traditional loop which tests each character, 123 we will test a longword at a time. The tricky part is testing 124 if *any of the four* bytes in the longword in question are zero. */ 125 while (n >= sizeof (longword)) 126 { 127 /* We tentatively exit the loop if adding MAGIC_BITS to 128 LONGWORD fails to change any of the hole bits of LONGWORD. 129 130 1) Is this safe? Will it catch all the zero bytes? 131 Suppose there is a byte with all zeros. Any carry bits 132 propagating from its left will fall into the hole at its 133 least significant bit and stop. Since there will be no 134 carry from its most significant bit, the LSB of the 135 byte to the left will be unchanged, and the zero will be 136 detected. 137 138 2) Is this worthwhile? Will it ignore everything except 139 zero bytes? Suppose every byte of LONGWORD has a bit set 140 somewhere. There will be a carry into bit 8. If bit 8 141 is set, this will carry into bit 16. If bit 8 is clear, 142 one of bits 9-15 must be set, so there will be a carry 143 into bit 16. Similarly, there will be a carry into bit 144 24. If one of bits 24-30 is set, there will be a carry 145 into bit 31, so all of the hole bits will be changed. 146 147 The one misfire occurs when bits 24-30 are clear and bit 148 31 is set; in this case, the hole at bit 31 is not 149 changed. If we had access to the processor carry flag, 150 we could close this loophole by putting the fourth hole 151 at bit 32! 152 153 So it ignores everything except 128's, when they're aligned 154 properly. 155 156 3) But wait! Aren't we looking for C, not zero? 157 Good point. So what we do is XOR LONGWORD with a longword, 158 each of whose bytes is C. This turns each byte that is C 159 into a zero. */ 160 161 longword = *longword_ptr++ ^ charmask; 162 163 /* Add MAGIC_BITS to LONGWORD. */ 164 if ((((longword + magic_bits) 165 166 /* Set those bits that were unchanged by the addition. */ 167 ^ ~longword) 168 169 /* Look at only the hole bits. If any of the hole bits 170 are unchanged, most likely one of the bytes was a 171 zero. */ 172 & ~magic_bits) != 0) 173 { 174 /* Which of the bytes was C? If none of them were, it was 175 a misfire; continue the search. */ 176 177 const unsigned char *cp = (const unsigned char *) (longword_ptr - 1); 178 179 if (cp[0] == c) 180 return (__ptr_t) cp; 181 if (cp[1] == c) 182 return (__ptr_t) &cp[1]; 183 if (cp[2] == c) 184 return (__ptr_t) &cp[2]; 185 if (cp[3] == c) 186 return (__ptr_t) &cp[3]; 187#if LONG_MAX > 2147483647 188 if (cp[4] == c) 189 return (__ptr_t) &cp[4]; 190 if (cp[5] == c) 191 return (__ptr_t) &cp[5]; 192 if (cp[6] == c) 193 return (__ptr_t) &cp[6]; 194 if (cp[7] == c) 195 return (__ptr_t) &cp[7]; 196#endif 197 } 198 199 n -= sizeof (longword); 200 } 201 202 char_ptr = (const unsigned char *) longword_ptr; 203 204 while (n-- > 0) 205 { 206 if (*char_ptr == c) 207 return (__ptr_t) char_ptr; 208 else 209 ++char_ptr; 210 } 211 212 return 0; 213} 214#ifdef weak_alias 215weak_alias (__memchr, BP_SYM (memchr)) 216#endif 217