Mercurial > hg > octave-kai > gnulib-hg
annotate lib/memchr2.c @ 17476:6057744acd2c default tip master
autoupdate
| author | Karl Berry <karl@freefriends.org> |
|---|---|
| date | Fri, 16 Aug 2013 06:32:22 -0700 (2013-08-16) |
| parents | 2760c772c42c |
| children |
| rev | line source |
|---|---|
|
17249
e542fd46ad6f
maint: update all copyright year number ranges
Eric Blake <eblake@redhat.com>
parents:
16358
diff
changeset
|
1 /* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2013 |
|
14079
97fc9a21a8fb
maint: update almost all copyright ranges to include 2011
Jim Meyering <meyering@redhat.com>
parents:
12559
diff
changeset
|
2 Free Software Foundation, Inc. |
| 9742 | 3 |
| 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 in glibc by Roland McGrath (roland@ai.mit.edu). | |
| 9 Extension to memchr2 implemented by Eric Blake (ebb9@byu.net). | |
| 10 | |
| 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 3 of the License, or any | |
| 14 later version. | |
| 15 | |
| 16 This program is distributed in the hope that it will be useful, | |
| 17 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 19 GNU General Public License for more details. | |
| 20 | |
| 21 You should have received a copy of the GNU General Public License | |
| 22 along with this program. If not, see <http://www.gnu.org/licenses/>. */ | |
| 23 | |
| 24 #include <config.h> | |
| 25 | |
| 26 #include "memchr2.h" | |
| 27 | |
| 28 #include <limits.h> | |
| 29 #include <stdint.h> | |
| 30 #include <string.h> | |
| 31 | |
| 32 /* Return the first address of either C1 or C2 (treated as unsigned | |
| 33 char) that occurs within N bytes of the memory region S. If | |
| 34 neither byte appears, return NULL. */ | |
|
14612
6ef4f1f39105
Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE"
Jim Meyering <meyering@redhat.com>
parents:
14610
diff
changeset
|
35 void * |
| 9742 | 36 memchr2 (void const *s, int c1_in, int c2_in, size_t n) |
| 37 { | |
| 9967 | 38 /* On 32-bit hardware, choosing longword to be a 32-bit unsigned |
| 39 long instead of a 64-bit uintmax_t tends to give better | |
| 40 performance. On 64-bit hardware, unsigned long is generally 64 | |
| 41 bits already. Change this typedef to experiment with | |
| 42 performance. */ | |
| 9995 | 43 typedef unsigned long int longword; |
| 9967 | 44 |
| 9742 | 45 const unsigned char *char_ptr; |
|
17405
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
46 void const *void_ptr; |
| 9967 | 47 const longword *longword_ptr; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
48 longword repeated_one; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
49 longword repeated_c1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
50 longword repeated_c2; |
| 9742 | 51 unsigned char c1; |
| 52 unsigned char c2; | |
| 53 | |
| 54 c1 = (unsigned char) c1_in; | |
| 55 c2 = (unsigned char) c2_in; | |
| 56 | |
| 57 if (c1 == c2) | |
| 58 return memchr (s, c1, n); | |
| 59 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
60 /* Handle the first few bytes by reading one byte at a time. |
|
17405
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
61 Do this until VOID_PTR is aligned on a longword boundary. */ |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
62 for (void_ptr = s; |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
63 n > 0 && (uintptr_t) void_ptr % sizeof (longword) != 0; |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
64 --n) |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
65 { |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
66 char_ptr = void_ptr; |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
67 if (*char_ptr == c1 || *char_ptr == c2) |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
68 return (void *) void_ptr; |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
69 void_ptr = char_ptr + 1; |
|
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
70 } |
| 9742 | 71 |
|
17405
2760c772c42c
memchr2: port --enable-gcc-warnings to clang
Paul Eggert <eggert@cs.ucla.edu>
parents:
17249
diff
changeset
|
72 longword_ptr = void_ptr; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
73 |
| 9742 | 74 /* All these elucidatory comments refer to 4-byte longwords, |
| 75 but the theory applies equally well to any size longwords. */ | |
| 76 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
77 /* Compute auxiliary longword values: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
78 repeated_one is a value which has a 1 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
79 repeated_c1 has c1 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
80 repeated_c2 has c2 in every byte. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
81 repeated_one = 0x01010101; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
82 repeated_c1 = c1 | (c1 << 8); |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
83 repeated_c2 = c2 | (c2 << 8); |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
84 repeated_c1 |= repeated_c1 << 16; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
85 repeated_c2 |= repeated_c2 << 16; |
| 9995 | 86 if (0xffffffffU < (longword) -1) |
|
9951
03b212920228
Work around preprocessors that don't handle UINTMAX_MAX.
Eric Blake <ebb9@byu.net>
parents:
9745
diff
changeset
|
87 { |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
88 repeated_one |= repeated_one << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
89 repeated_c1 |= repeated_c1 << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
90 repeated_c2 |= repeated_c2 << 31 << 1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
91 if (8 < sizeof (longword)) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
92 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
93 size_t i; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
94 |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
95 for (i = 64; i < sizeof (longword) * 8; i *= 2) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
96 { |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
97 repeated_one |= repeated_one << i; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
98 repeated_c1 |= repeated_c1 << i; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
99 repeated_c2 |= repeated_c2 << i; |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
100 } |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
101 } |
|
9951
03b212920228
Work around preprocessors that don't handle UINTMAX_MAX.
Eric Blake <ebb9@byu.net>
parents:
9745
diff
changeset
|
102 } |
| 9742 | 103 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
104 /* Instead of the traditional loop which tests each byte, we will test a |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
105 longword at a time. The tricky part is testing if *any of the four* |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
106 bytes in the longword in question are equal to c1 or c2. We first use |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
107 an xor with repeated_c1 and repeated_c2, respectively. This reduces |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
108 the task to testing whether *any of the four* bytes in longword1 or |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
109 longword2 is zero. |
| 9967 | 110 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
111 Let's consider longword1. We compute tmp1 = |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
112 ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
113 That is, we perform the following operations: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
114 1. Subtract repeated_one. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
115 2. & ~longword1. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
116 3. & a mask consisting of 0x80 in every byte. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
117 Consider what happens in each byte: |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
118 - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
119 and step 3 transforms it into 0x80. A carry can also be propagated |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
120 to more significant bytes. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
121 - If a byte of longword1 is nonzero, let its lowest 1 bit be at |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
122 position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
123 the byte ends in a single bit of value 0 and k bits of value 1. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
124 After step 2, the result is just k bits of value 1: 2^k - 1. After |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
125 step 3, the result is 0. And no carry is produced. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
126 So, if longword1 has only non-zero bytes, tmp1 is zero. |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
127 Whereas if longword1 has a zero byte, call j the position of the least |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
128 significant zero byte. Then the result has a zero at positions 0, ..., |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
129 j-1 and a 0x80 at position j. We cannot predict the result at the more |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
130 significant bytes (positions j+1..3), but it does not matter since we |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
131 already have a non-zero bit at position 8*j+7. |
| 9967 | 132 |
| 16358 | 133 Similarly, we compute tmp2 = |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
134 ((longword2 - repeated_one) & ~longword2) & (repeated_one << 7). |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
135 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
136 The test whether any byte in longword1 or longword2 is zero is equivalent |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
137 to testing whether tmp1 is nonzero or tmp2 is nonzero. We can combine |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
138 this into a single test, whether (tmp1 | tmp2) is nonzero. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
139 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
140 while (n >= sizeof (longword)) |
| 9742 | 141 { |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
142 longword longword1 = *longword_ptr ^ repeated_c1; |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
143 longword longword2 = *longword_ptr ^ repeated_c2; |
| 9742 | 144 |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
145 if (((((longword1 - repeated_one) & ~longword1) |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
146 | ((longword2 - repeated_one) & ~longword2)) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
147 & (repeated_one << 7)) != 0) |
|
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
148 break; |
| 9967 | 149 longword_ptr++; |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
150 n -= sizeof (longword); |
| 9742 | 151 } |
| 152 | |
| 153 char_ptr = (const unsigned char *) longword_ptr; | |
| 154 | |
|
9971
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
155 /* At this point, we know that either n < sizeof (longword), or one of the |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
156 sizeof (longword) bytes starting at char_ptr is == c1 or == c2. On |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
157 little-endian machines, we could determine the first such byte without |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
158 any further memory accesses, just by looking at the (tmp1 | tmp2) result |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
159 from the last loop iteration. But this does not work on big-endian |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
160 machines. Choose code that works in both cases. */ |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
161 |
|
e70f61b955b9
Superficial improvements and comments.
Bruno Haible <bruno@clisp.org>
parents:
9967
diff
changeset
|
162 for (; n > 0; --n, ++char_ptr) |
| 9742 | 163 { |
| 164 if (*char_ptr == c1 || *char_ptr == c2) | |
|
12421
e8d2c6fc33ad
Use spaces for indentation, not tabs.
Bruno Haible <bruno@clisp.org>
parents:
9995
diff
changeset
|
165 return (void *) char_ptr; |
| 9742 | 166 } |
| 167 | |
| 9967 | 168 return NULL; |
| 9742 | 169 } |