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