1 /* stringlib: fastsearch implementation */
2
3 #define STRINGLIB_FASTSEARCH_H
4
5 /* fast search/count implementation, based on a mix between boyer-
6 moore and horspool, with a few more bells and whistles on the top.
7 for some more background, see: http://effbot.org/zone/stringlib.htm */
8
9 /* note: fastsearch may access s[n], which isn't a problem when using
10 Python's ordinary string types, but may cause problems if you're
11 using this code in other contexts. also, the count mode returns -1
12 if there cannot possible be a match in the target string, and 0 if
13 it has actually checked for matches, but didn't find any. callers
14 beware! */
15
16 #define FAST_COUNT 0
17 #define FAST_SEARCH 1
18 #define FAST_RSEARCH 2
19
20 #if LONG_BIT >= 128
21 #define STRINGLIB_BLOOM_WIDTH 128
22 #elif LONG_BIT >= 64
23 #define STRINGLIB_BLOOM_WIDTH 64
24 #elif LONG_BIT >= 32
25 #define STRINGLIB_BLOOM_WIDTH 32
26 #else
27 #error "LONG_BIT is smaller than 32"
28 #endif
29
30 #define STRINGLIB_BLOOM_ADD(mask, ch) \
31 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
32 #define STRINGLIB_BLOOM(mask, ch) \
33 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
34
35 #if STRINGLIB_SIZEOF_CHAR == 1
36 # define MEMCHR_CUT_OFF 15
37 #else
38 # define MEMCHR_CUT_OFF 40
39 #endif
40
41 Py_LOCAL_INLINE(Py_ssize_t)
STRINGLIB(find_char)42 STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
43 {
44 const STRINGLIB_CHAR *p, *e;
45
46 p = s;
47 e = s + n;
48 if (n > MEMCHR_CUT_OFF) {
49 #if STRINGLIB_SIZEOF_CHAR == 1
50 p = memchr(s, ch, n);
51 if (p != NULL)
52 return (p - s);
53 return -1;
54 #else
55 /* use memchr if we can choose a needle without two many likely
56 false positives */
57 const STRINGLIB_CHAR *s1, *e1;
58 unsigned char needle = ch & 0xff;
59 /* If looking for a multiple of 256, we'd have too
60 many false positives looking for the '\0' byte in UCS2
61 and UCS4 representations. */
62 if (needle != 0) {
63 do {
64 void *candidate = memchr(p, needle,
65 (e - p) * sizeof(STRINGLIB_CHAR));
66 if (candidate == NULL)
67 return -1;
68 s1 = p;
69 p = (const STRINGLIB_CHAR *)
70 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
71 if (*p == ch)
72 return (p - s);
73 /* False positive */
74 p++;
75 if (p - s1 > MEMCHR_CUT_OFF)
76 continue;
77 if (e - p <= MEMCHR_CUT_OFF)
78 break;
79 e1 = p + MEMCHR_CUT_OFF;
80 while (p != e1) {
81 if (*p == ch)
82 return (p - s);
83 p++;
84 }
85 }
86 while (e - p > MEMCHR_CUT_OFF);
87 }
88 #endif
89 }
90 while (p < e) {
91 if (*p == ch)
92 return (p - s);
93 p++;
94 }
95 return -1;
96 }
97
98 Py_LOCAL_INLINE(Py_ssize_t)
STRINGLIB(rfind_char)99 STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
100 {
101 const STRINGLIB_CHAR *p;
102 #ifdef HAVE_MEMRCHR
103 /* memrchr() is a GNU extension, available since glibc 2.1.91.
104 it doesn't seem as optimized as memchr(), but is still quite
105 faster than our hand-written loop below */
106
107 if (n > MEMCHR_CUT_OFF) {
108 #if STRINGLIB_SIZEOF_CHAR == 1
109 p = memrchr(s, ch, n);
110 if (p != NULL)
111 return (p - s);
112 return -1;
113 #else
114 /* use memrchr if we can choose a needle without two many likely
115 false positives */
116 const STRINGLIB_CHAR *s1;
117 Py_ssize_t n1;
118 unsigned char needle = ch & 0xff;
119 /* If looking for a multiple of 256, we'd have too
120 many false positives looking for the '\0' byte in UCS2
121 and UCS4 representations. */
122 if (needle != 0) {
123 do {
124 void *candidate = memrchr(s, needle,
125 n * sizeof(STRINGLIB_CHAR));
126 if (candidate == NULL)
127 return -1;
128 n1 = n;
129 p = (const STRINGLIB_CHAR *)
130 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
131 n = p - s;
132 if (*p == ch)
133 return n;
134 /* False positive */
135 if (n1 - n > MEMCHR_CUT_OFF)
136 continue;
137 if (n <= MEMCHR_CUT_OFF)
138 break;
139 s1 = p - MEMCHR_CUT_OFF;
140 while (p > s1) {
141 p--;
142 if (*p == ch)
143 return (p - s);
144 }
145 n = p - s;
146 }
147 while (n > MEMCHR_CUT_OFF);
148 }
149 #endif
150 }
151 #endif /* HAVE_MEMRCHR */
152 p = s + n;
153 while (p > s) {
154 p--;
155 if (*p == ch)
156 return (p - s);
157 }
158 return -1;
159 }
160
161 #undef MEMCHR_CUT_OFF
162
163 Py_LOCAL_INLINE(Py_ssize_t)
FASTSEARCH(const STRINGLIB_CHAR * s,Py_ssize_t n,const STRINGLIB_CHAR * p,Py_ssize_t m,Py_ssize_t maxcount,int mode)164 FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,
165 const STRINGLIB_CHAR* p, Py_ssize_t m,
166 Py_ssize_t maxcount, int mode)
167 {
168 unsigned long mask;
169 Py_ssize_t skip, count = 0;
170 Py_ssize_t i, j, mlast, w;
171
172 w = n - m;
173
174 if (w < 0 || (mode == FAST_COUNT && maxcount == 0))
175 return -1;
176
177 /* look for special cases */
178 if (m <= 1) {
179 if (m <= 0)
180 return -1;
181 /* use special case for 1-character strings */
182 if (mode == FAST_SEARCH)
183 return STRINGLIB(find_char)(s, n, p[0]);
184 else if (mode == FAST_RSEARCH)
185 return STRINGLIB(rfind_char)(s, n, p[0]);
186 else { /* FAST_COUNT */
187 for (i = 0; i < n; i++)
188 if (s[i] == p[0]) {
189 count++;
190 if (count == maxcount)
191 return maxcount;
192 }
193 return count;
194 }
195 return -1;
196 }
197
198 mlast = m - 1;
199 skip = mlast - 1;
200 mask = 0;
201
202 if (mode != FAST_RSEARCH) {
203 const STRINGLIB_CHAR *ss = s + m - 1;
204 const STRINGLIB_CHAR *pp = p + m - 1;
205
206 /* create compressed boyer-moore delta 1 table */
207
208 /* process pattern[:-1] */
209 for (i = 0; i < mlast; i++) {
210 STRINGLIB_BLOOM_ADD(mask, p[i]);
211 if (p[i] == p[mlast])
212 skip = mlast - i - 1;
213 }
214 /* process pattern[-1] outside the loop */
215 STRINGLIB_BLOOM_ADD(mask, p[mlast]);
216
217 for (i = 0; i <= w; i++) {
218 /* note: using mlast in the skip path slows things down on x86 */
219 if (ss[i] == pp[0]) {
220 /* candidate match */
221 for (j = 0; j < mlast; j++)
222 if (s[i+j] != p[j])
223 break;
224 if (j == mlast) {
225 /* got a match! */
226 if (mode != FAST_COUNT)
227 return i;
228 count++;
229 if (count == maxcount)
230 return maxcount;
231 i = i + mlast;
232 continue;
233 }
234 /* miss: check if next character is part of pattern */
235 if (!STRINGLIB_BLOOM(mask, ss[i+1]))
236 i = i + m;
237 else
238 i = i + skip;
239 } else {
240 /* skip: check if next character is part of pattern */
241 if (!STRINGLIB_BLOOM(mask, ss[i+1]))
242 i = i + m;
243 }
244 }
245 } else { /* FAST_RSEARCH */
246
247 /* create compressed boyer-moore delta 1 table */
248
249 /* process pattern[0] outside the loop */
250 STRINGLIB_BLOOM_ADD(mask, p[0]);
251 /* process pattern[:0:-1] */
252 for (i = mlast; i > 0; i--) {
253 STRINGLIB_BLOOM_ADD(mask, p[i]);
254 if (p[i] == p[0])
255 skip = i - 1;
256 }
257
258 for (i = w; i >= 0; i--) {
259 if (s[i] == p[0]) {
260 /* candidate match */
261 for (j = mlast; j > 0; j--)
262 if (s[i+j] != p[j])
263 break;
264 if (j == 0)
265 /* got a match! */
266 return i;
267 /* miss: check if previous character is part of pattern */
268 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
269 i = i - m;
270 else
271 i = i - skip;
272 } else {
273 /* skip: check if previous character is part of pattern */
274 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1]))
275 i = i - m;
276 }
277 }
278 }
279
280 if (mode != FAST_COUNT)
281 return -1;
282 return count;
283 }
284
285