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