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