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