Commit | Line | Data |
---|---|---|
7a6dbc2f | 1 | /* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2018 |
f434ba03 | 2 | Free Software Foundation, Inc. |
f6ea5628 DJ |
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 by Roland McGrath (roland@ai.mit.edu). | |
9 | ||
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. | |
12 | ||
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 3 of the License, or any | |
16 | later version. | |
17 | ||
18 | This program is distributed in the hope that it will be useful, | |
19 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
20 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
21 | GNU General Public License for more details. | |
22 | ||
23 | You should have received a copy of the GNU General Public License | |
7a6dbc2f | 24 | along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
f6ea5628 DJ |
25 | |
26 | #ifndef _LIBC | |
27 | # include <config.h> | |
28 | #endif | |
29 | ||
30 | #include <string.h> | |
31 | ||
32 | #include <stddef.h> | |
33 | ||
34 | #if defined _LIBC | |
35 | # include <memcopy.h> | |
36 | #else | |
37 | # define reg_char char | |
38 | #endif | |
39 | ||
40 | #include <limits.h> | |
41 | ||
42 | #if HAVE_BP_SYM_H || defined _LIBC | |
43 | # include <bp-sym.h> | |
44 | #else | |
45 | # define BP_SYM(sym) sym | |
46 | #endif | |
47 | ||
f6ea5628 | 48 | #undef __memchr |
f434ba03 PA |
49 | #ifdef _LIBC |
50 | # undef memchr | |
51 | #endif | |
52 | ||
53 | #ifndef weak_alias | |
54 | # define __memchr memchr | |
55 | #endif | |
f6ea5628 DJ |
56 | |
57 | /* Search no more than N bytes of S for C. */ | |
58 | void * | |
59 | __memchr (void const *s, int c_in, size_t n) | |
60 | { | |
f434ba03 PA |
61 | /* On 32-bit hardware, choosing longword to be a 32-bit unsigned |
62 | long instead of a 64-bit uintmax_t tends to give better | |
63 | performance. On 64-bit hardware, unsigned long is generally 64 | |
64 | bits already. Change this typedef to experiment with | |
65 | performance. */ | |
66 | typedef unsigned long int longword; | |
67 | ||
f6ea5628 | 68 | const unsigned char *char_ptr; |
f434ba03 PA |
69 | const longword *longword_ptr; |
70 | longword repeated_one; | |
71 | longword repeated_c; | |
f6ea5628 | 72 | unsigned reg_char c; |
f6ea5628 DJ |
73 | |
74 | c = (unsigned char) c_in; | |
75 | ||
f434ba03 | 76 | /* Handle the first few bytes by reading one byte at a time. |
f6ea5628 DJ |
77 | Do this until CHAR_PTR is aligned on a longword boundary. */ |
78 | for (char_ptr = (const unsigned char *) s; | |
f434ba03 | 79 | n > 0 && (size_t) char_ptr % sizeof (longword) != 0; |
f6ea5628 DJ |
80 | --n, ++char_ptr) |
81 | if (*char_ptr == c) | |
82 | return (void *) char_ptr; | |
83 | ||
f434ba03 PA |
84 | longword_ptr = (const longword *) char_ptr; |
85 | ||
f6ea5628 DJ |
86 | /* All these elucidatory comments refer to 4-byte longwords, |
87 | but the theory applies equally well to any size longwords. */ | |
88 | ||
f434ba03 PA |
89 | /* Compute auxiliary longword values: |
90 | repeated_one is a value which has a 1 in every byte. | |
91 | repeated_c has c in every byte. */ | |
92 | repeated_one = 0x01010101; | |
93 | repeated_c = c | (c << 8); | |
94 | repeated_c |= repeated_c << 16; | |
95 | if (0xffffffffU < (longword) -1) | |
96 | { | |
97 | repeated_one |= repeated_one << 31 << 1; | |
98 | repeated_c |= repeated_c << 31 << 1; | |
99 | if (8 < sizeof (longword)) | |
100 | { | |
101 | size_t i; | |
102 | ||
103 | for (i = 64; i < sizeof (longword) * 8; i *= 2) | |
104 | { | |
105 | repeated_one |= repeated_one << i; | |
106 | repeated_c |= repeated_c << i; | |
107 | } | |
108 | } | |
109 | } | |
f6ea5628 | 110 | |
f434ba03 PA |
111 | /* Instead of the traditional loop which tests each byte, we will test a |
112 | longword at a time. The tricky part is testing if *any of the four* | |
113 | bytes in the longword in question are equal to c. We first use an xor | |
114 | with repeated_c. This reduces the task to testing whether *any of the | |
115 | four* bytes in longword1 is zero. | |
116 | ||
117 | We compute tmp = | |
118 | ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7). | |
119 | That is, we perform the following operations: | |
120 | 1. Subtract repeated_one. | |
121 | 2. & ~longword1. | |
122 | 3. & a mask consisting of 0x80 in every byte. | |
123 | Consider what happens in each byte: | |
124 | - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff, | |
125 | and step 3 transforms it into 0x80. A carry can also be propagated | |
126 | to more significant bytes. | |
127 | - If a byte of longword1 is nonzero, let its lowest 1 bit be at | |
128 | position k (0 <= k <= 7); so the lowest k bits are 0. After step 1, | |
129 | the byte ends in a single bit of value 0 and k bits of value 1. | |
130 | After step 2, the result is just k bits of value 1: 2^k - 1. After | |
131 | step 3, the result is 0. And no carry is produced. | |
132 | So, if longword1 has only non-zero bytes, tmp is zero. | |
133 | Whereas if longword1 has a zero byte, call j the position of the least | |
134 | significant zero byte. Then the result has a zero at positions 0, ..., | |
135 | j-1 and a 0x80 at position j. We cannot predict the result at the more | |
136 | significant bytes (positions j+1..3), but it does not matter since we | |
137 | already have a non-zero bit at position 8*j+7. | |
138 | ||
139 | So, the test whether any byte in longword1 is zero is equivalent to | |
140 | testing whether tmp is nonzero. */ | |
141 | ||
142 | while (n >= sizeof (longword)) | |
f6ea5628 | 143 | { |
f434ba03 PA |
144 | longword longword1 = *longword_ptr ^ repeated_c; |
145 | ||
146 | if ((((longword1 - repeated_one) & ~longword1) | |
147 | & (repeated_one << 7)) != 0) | |
148 | break; | |
149 | longword_ptr++; | |
150 | n -= sizeof (longword); | |
f6ea5628 DJ |
151 | } |
152 | ||
153 | char_ptr = (const unsigned char *) longword_ptr; | |
154 | ||
f434ba03 PA |
155 | /* At this point, we know that either n < sizeof (longword), or one of the |
156 | sizeof (longword) bytes starting at char_ptr is == c. On little-endian | |
157 | machines, we could determine the first such byte without any further | |
158 | memory accesses, just by looking at the tmp result from the last loop | |
159 | iteration. But this does not work on big-endian machines. Choose code | |
160 | that works in both cases. */ | |
161 | ||
162 | for (; n > 0; --n, ++char_ptr) | |
f6ea5628 DJ |
163 | { |
164 | if (*char_ptr == c) | |
f434ba03 | 165 | return (void *) char_ptr; |
f6ea5628 DJ |
166 | } |
167 | ||
f434ba03 | 168 | return NULL; |
f6ea5628 DJ |
169 | } |
170 | #ifdef weak_alias | |
171 | weak_alias (__memchr, BP_SYM (memchr)) | |
172 | #endif |