Debian Codegraph @

Objects/stringlib/fastsearch.h

raw
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:
8 https://web.archive.org/web/20201107074620/http://effbot.org/zone/stringlib.htm */
9
10 /* note: fastsearch may access s[n], which isn't a problem when using
11 Python's ordinary string types, but may cause problems if you're
12 using this code in other contexts. also, the count mode returns -1
13 if there cannot possibly be a match in the target string, and 0 if
14 it has actually checked for matches, but didn't find any. callers
15 beware! */
16
17 /* If the strings are long enough, use Crochemore and Perrin's Two-Way
18 algorithm, which has worst-case O(n) runtime and best-case O(n/k).
19 Also compute a table of shifts to achieve O(n/k) in more cases,
20 and often (data dependent) deduce larger shifts than pure C&P can
21 deduce. See stringlib_find_two_way_notes.txt in this folder for a
22 detailed explanation. */
23
24 #define FAST_COUNT 0
25 #define FAST_SEARCH 1
26 #define FAST_RSEARCH 2
27
28 #if LONG_BIT >= 128
29 #define STRINGLIB_BLOOM_WIDTH 128
30 #elif LONG_BIT >= 64
31 #define STRINGLIB_BLOOM_WIDTH 64
32 #elif LONG_BIT >= 32
33 #define STRINGLIB_BLOOM_WIDTH 32
34 #else
35 #error "LONG_BIT is smaller than 32"
36 #endif
37
38 #define STRINGLIB_BLOOM_ADD(mask, ch) \
39 ((mask |= (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
40 #define STRINGLIB_BLOOM(mask, ch) \
41 ((mask & (1UL << ((ch) & (STRINGLIB_BLOOM_WIDTH -1)))))
42
43 #ifdef STRINGLIB_FAST_MEMCHR
44 # define MEMCHR_CUT_OFF 15
45 #else
46 # define MEMCHR_CUT_OFF 40
47 #endif
48
49 Py_LOCAL_INLINE(Py_ssize_t)
50 STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
51 {
52 const STRINGLIB_CHAR *p, *e;
53
54 p = s;
55 e = s + n;
56 if (n > MEMCHR_CUT_OFF) {
57 #ifdef STRINGLIB_FAST_MEMCHR
58 p = STRINGLIB_FAST_MEMCHR(s, ch, n);
59 if (p != NULL)
60 return (p - s);
61 return -1;
62 #else
63 /* use memchr if we can choose a needle without too many likely
64 false positives */
65 const STRINGLIB_CHAR *s1, *e1;
66 unsigned char needle = ch & 0xff;
67 /* If looking for a multiple of 256, we'd have too
68 many false positives looking for the '\0' byte in UCS2
69 and UCS4 representations. */
70 if (needle != 0) {
71 do {
72 const void *candidate = memchr(p, needle,
73 (e - p) * sizeof(STRINGLIB_CHAR));
74 if (candidate == NULL)
75 return -1;
76 s1 = p;
77 p = (const STRINGLIB_CHAR *)
78 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
79 if (*p == ch)
80 return (p - s);
81 /* False positive */
82 p++;
83 if (p - s1 > MEMCHR_CUT_OFF)
84 continue;
85 if (e - p <= MEMCHR_CUT_OFF)
86 break;
87 e1 = p + MEMCHR_CUT_OFF;
88 while (p != e1) {
89 if (*p == ch)
90 return (p - s);
91 p++;
92 }
93 }
94 while (e - p > MEMCHR_CUT_OFF);
95 }
96 #endif
97 }
98 while (p < e) {
99 if (*p == ch)
100 return (p - s);
101 p++;
102 }
103 return -1;
104 }
105
106 #undef MEMCHR_CUT_OFF
107
108 #if STRINGLIB_SIZEOF_CHAR == 1
109 # define MEMRCHR_CUT_OFF 15
110 #else
111 # define MEMRCHR_CUT_OFF 40
112 #endif
113
114
115 Py_LOCAL_INLINE(Py_ssize_t)
116 STRINGLIB(rfind_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
117 {
118 const STRINGLIB_CHAR *p;
119 #ifdef HAVE_MEMRCHR
120 /* memrchr() is a GNU extension, available since glibc 2.1.91. it
121 doesn't seem as optimized as memchr(), but is still quite
122 faster than our hand-written loop below. There is no wmemrchr
123 for 4-byte chars. */
124
125 if (n > MEMRCHR_CUT_OFF) {
126 #if STRINGLIB_SIZEOF_CHAR == 1
127 p = memrchr(s, ch, n);
128 if (p != NULL)
129 return (p - s);
130 return -1;
131 #else
132 /* use memrchr if we can choose a needle without too many likely
133 false positives */
134 const STRINGLIB_CHAR *s1;
135 Py_ssize_t n1;
136 unsigned char needle = ch & 0xff;
137 /* If looking for a multiple of 256, we'd have too
138 many false positives looking for the '\0' byte in UCS2
139 and UCS4 representations. */
140 if (needle != 0) {
141 do {
142 void *candidate = memrchr(s, needle,
143 n * sizeof(STRINGLIB_CHAR));
144 if (candidate == NULL)
145 return -1;
146 n1 = n;
147 p = (const STRINGLIB_CHAR *)
148 _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
149 n = p - s;
150 if (*p == ch)
151 return n;
152 /* False positive */
153 if (n1 - n > MEMRCHR_CUT_OFF)
154 continue;
155 if (n <= MEMRCHR_CUT_OFF)
156 break;
157 s1 = p - MEMRCHR_CUT_OFF;
158 while (p > s1) {
159 p--;
160 if (*p == ch)
161 return (p - s);
162 }
163 n = p - s;
164 }
165 while (n > MEMRCHR_CUT_OFF);
166 }
167 #endif
168 }
169 #endif /* HAVE_MEMRCHR */
170 p = s + n;
171 while (p > s) {
172 p--;
173 if (*p == ch)
174 return (p - s);
175 }
176 return -1;
177 }
178
179 #undef MEMRCHR_CUT_OFF
180
181 /* Change to a 1 to see logging comments walk through the algorithm. */
182 #if 0 && STRINGLIB_SIZEOF_CHAR == 1
183 # define LOG(...) printf(__VA_ARGS__)
184 # define LOG_STRING(s, n) printf("\"%.*s\"", (int)(n), s)
185 # define LOG_LINEUP() do { \
186 LOG("> "); LOG_STRING(haystack, len_haystack); LOG("\n> "); \
187 LOG("%*s",(int)(window_last - haystack + 1 - len_needle), ""); \
188 LOG_STRING(needle, len_needle); LOG("\n"); \
189 } while(0)
190 #else
191 # define LOG(...)
192 # define LOG_STRING(s, n)
193 # define LOG_LINEUP()
194 #endif
195
196 Py_LOCAL_INLINE(Py_ssize_t)
197 STRINGLIB(_lex_search)(const STRINGLIB_CHAR *needle, Py_ssize_t len_needle,
198 Py_ssize_t *return_period, int invert_alphabet)
199 {
200 /* Do a lexicographic search. Essentially this:
201 >>> max(needle[i:] for i in range(len(needle)+1))
202 Also find the period of the right half. */
203 Py_ssize_t max_suffix = 0;
204 Py_ssize_t candidate = 1;
205 Py_ssize_t k = 0;
206 // The period of the right half.
207 Py_ssize_t period = 1;
208
209 while (candidate + k < len_needle) {
210 // each loop increases candidate + k + max_suffix
211 STRINGLIB_CHAR a = needle[candidate + k];
212 STRINGLIB_CHAR b = needle[max_suffix + k];
213 // check if the suffix at candidate is better than max_suffix
214 if (invert_alphabet ? (b < a) : (a < b)) {
215 // Fell short of max_suffix.
216 // The next k + 1 characters are non-increasing
217 // from candidate, so they won't start a maximal suffix.
218 candidate += k + 1;
219 k = 0;
220 // We've ruled out any period smaller than what's
221 // been scanned since max_suffix.
222 period = candidate - max_suffix;
223 }
224 else if (a == b) {
225 if (k + 1 != period) {
226 // Keep scanning the equal strings
227 k++;
228 }
229 else {
230 // Matched a whole period.
231 // Start matching the next period.
232 candidate += period;
233 k = 0;
234 }
235 }
236 else {
237 // Did better than max_suffix, so replace it.
238 max_suffix = candidate;
239 candidate++;
240 k = 0;
241 period = 1;
242 }
243 }
244 *return_period = period;
245 return max_suffix;
246 }
247
248 Py_LOCAL_INLINE(Py_ssize_t)
249 STRINGLIB(_factorize)(const STRINGLIB_CHAR *needle,
250 Py_ssize_t len_needle,
251 Py_ssize_t *return_period)
252 {
253 /* Do a "critical factorization", making it so that:
254 >>> needle = (left := needle[:cut]) + (right := needle[cut:])
255 where the "local period" of the cut is maximal.
256
257 The local period of the cut is the minimal length of a string w
258 such that (left endswith w or w endswith left)
259 and (right startswith w or w startswith right).
260
261 The Critical Factorization Theorem says that this maximal local
262 period is the global period of the string.
263
264 Crochemore and Perrin (1991) show that this cut can be computed
265 as the later of two cuts: one that gives a lexicographically
266 maximal right half, and one that gives the same with the
267 with respect to a reversed alphabet-ordering.
268
269 This is what we want to happen:
270 >>> x = "GCAGAGAG"
271 >>> cut, period = factorize(x)
272 >>> x[:cut], (right := x[cut:])
273 ('GC', 'AGAGAG')
274 >>> period # right half period
275 2
276 >>> right[period:] == right[:-period]
277 True
278
279 This is how the local period lines up in the above example:
280 GC | AGAGAG
281 AGAGAGC = AGAGAGC
282 The length of this minimal repetition is 7, which is indeed the
283 period of the original string. */
284
285 Py_ssize_t cut1, period1, cut2, period2, cut, period;
286 cut1 = STRINGLIB(_lex_search)(needle, len_needle, &period1, 0);
287 cut2 = STRINGLIB(_lex_search)(needle, len_needle, &period2, 1);
288
289 // Take the later cut.
290 if (cut1 > cut2) {
291 period = period1;
292 cut = cut1;
293 }
294 else {
295 period = period2;
296 cut = cut2;
297 }
298
299 LOG("split: "); LOG_STRING(needle, cut);
300 LOG(" + "); LOG_STRING(needle + cut, len_needle - cut);
301 LOG("\n");
302
303 *return_period = period;
304 return cut;
305 }
306
307
308 #define SHIFT_TYPE uint8_t
309 #define MAX_SHIFT UINT8_MAX
310
311 #define TABLE_SIZE_BITS 6u
312 #define TABLE_SIZE (1U << TABLE_SIZE_BITS)
313 #define TABLE_MASK (TABLE_SIZE - 1U)
314
315 typedef struct STRINGLIB(_pre) {
316 const STRINGLIB_CHAR *needle;
317 Py_ssize_t len_needle;
318 Py_ssize_t cut;
319 Py_ssize_t period;
320 Py_ssize_t gap;
321 int is_periodic;
322 SHIFT_TYPE table[TABLE_SIZE];
323 } STRINGLIB(prework);
324
325
326 static void
327 STRINGLIB(_preprocess)(const STRINGLIB_CHAR *needle, Py_ssize_t len_needle,
328 STRINGLIB(prework) *p)
329 {
330 p->needle = needle;
331 p->len_needle = len_needle;
332 p->cut = STRINGLIB(_factorize)(needle, len_needle, &(p->period));
333 assert(p->period + p->cut <= len_needle);
334 p->is_periodic = (0 == memcmp(needle,
335 needle + p->period,
336 p->cut * STRINGLIB_SIZEOF_CHAR));
337 if (p->is_periodic) {
338 assert(p->cut <= len_needle/2);
339 assert(p->cut < p->period);
340 }
341 else {
342 // A lower bound on the period
343 p->period = Py_MAX(p->cut, len_needle - p->cut) + 1;
344 }
345 // The gap between the last character and the previous
346 // occurrence of an equivalent character (modulo TABLE_SIZE)
347 p->gap = len_needle;
348 STRINGLIB_CHAR last = needle[len_needle - 1] & TABLE_MASK;
349 for (Py_ssize_t i = len_needle - 2; i >= 0; i--) {
350 STRINGLIB_CHAR x = needle[i] & TABLE_MASK;
351 if (x == last) {
352 p->gap = len_needle - 1 - i;
353 break;
354 }
355 }
356 // Fill up a compressed Boyer-Moore "Bad Character" table
357 Py_ssize_t not_found_shift = Py_MIN(len_needle, MAX_SHIFT);
358 for (Py_ssize_t i = 0; i < (Py_ssize_t)TABLE_SIZE; i++) {
359 p->table[i] = Py_SAFE_DOWNCAST(not_found_shift,
360 Py_ssize_t, SHIFT_TYPE);
361 }
362 for (Py_ssize_t i = len_needle - not_found_shift; i < len_needle; i++) {
363 SHIFT_TYPE shift = Py_SAFE_DOWNCAST(len_needle - 1 - i,
364 Py_ssize_t, SHIFT_TYPE);
365 p->table[needle[i] & TABLE_MASK] = shift;
366 }
367 }
368
369 static Py_ssize_t
370 STRINGLIB(_two_way)(const STRINGLIB_CHAR *haystack, Py_ssize_t len_haystack,
371 STRINGLIB(prework) *p)
372 {
373 // Crochemore and Perrin's (1991) Two-Way algorithm.
374 // See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
375 const Py_ssize_t len_needle = p->len_needle;
376 const Py_ssize_t cut = p->cut;
377 Py_ssize_t period = p->period;
378 const STRINGLIB_CHAR *const needle = p->needle;
379 const STRINGLIB_CHAR *window_last = haystack + len_needle - 1;
380 const STRINGLIB_CHAR *const haystack_end = haystack + len_haystack;
381 SHIFT_TYPE *table = p->table;
382 const STRINGLIB_CHAR *window;
383 LOG("===== Two-way: \"%s\" in \"%s\". =====\n", needle, haystack);
384
385 Py_ssize_t gap = p->gap;
386 Py_ssize_t gap_jump_end = Py_MIN(len_needle, cut + gap);
387 if (p->is_periodic) {
388 LOG("Needle is periodic.\n");
389 Py_ssize_t memory = 0;
390 periodicwindowloop:
391 while (window_last < haystack_end) {
392 assert(memory == 0);
393 for (;;) {
394 LOG_LINEUP();
395 Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
396 window_last += shift;
397 if (shift == 0) {
398 break;
399 }
400 if (window_last >= haystack_end) {
401 return -1;
402 }
403 LOG("Horspool skip\n");
404 }
405 no_shift:
406 window = window_last - len_needle + 1;
407 assert((window[len_needle - 1] & TABLE_MASK) ==
408 (needle[len_needle - 1] & TABLE_MASK));
409 Py_ssize_t i = Py_MAX(cut, memory);
410 for (; i < len_needle; i++) {
411 if (needle[i] != window[i]) {
412 if (i < gap_jump_end) {
413 LOG("Early right half mismatch: jump by gap.\n");
414 assert(gap >= i - cut + 1);
415 window_last += gap;
416 }
417 else {
418 LOG("Late right half mismatch: jump by n (>gap)\n");
419 assert(i - cut + 1 > gap);
420 window_last += i - cut + 1;
421 }
422 memory = 0;
423 goto periodicwindowloop;
424 }
425 }
426 for (i = memory; i < cut; i++) {
427 if (needle[i] != window[i]) {
428 LOG("Left half does not match.\n");
429 window_last += period;
430 memory = len_needle - period;
431 if (window_last >= haystack_end) {
432 return -1;
433 }
434 Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
435 if (shift) {
436 // A mismatch has been identified to the right
437 // of where i will next start, so we can jump
438 // at least as far as if the mismatch occurred
439 // on the first comparison.
440 Py_ssize_t mem_jump = Py_MAX(cut, memory) - cut + 1;
441 LOG("Skip with Memory.\n");
442 memory = 0;
443 window_last += Py_MAX(shift, mem_jump);
444 goto periodicwindowloop;
445 }
446 goto no_shift;
447 }
448 }
449 LOG("Found a match!\n");
450 return window - haystack;
451 }
452 }
453 else {
454 period = Py_MAX(gap, period);
455 LOG("Needle is not periodic.\n");
456 windowloop:
457 while (window_last < haystack_end) {
458 for (;;) {
459 LOG_LINEUP();
460 Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
461 window_last += shift;
462 if (shift == 0) {
463 break;
464 }
465 if (window_last >= haystack_end) {
466 return -1;
467 }
468 LOG("Horspool skip\n");
469 }
470 window = window_last - len_needle + 1;
471 assert((window[len_needle - 1] & TABLE_MASK) ==
472 (needle[len_needle - 1] & TABLE_MASK));
473 Py_ssize_t i = cut;
474 for (; i < len_needle; i++) {
475 if (needle[i] != window[i]) {
476 if (i < gap_jump_end) {
477 LOG("Early right half mismatch: jump by gap.\n");
478 assert(gap >= i - cut + 1);
479 window_last += gap;
480 }
481 else {
482 LOG("Late right half mismatch: jump by n (>gap)\n");
483 assert(i - cut + 1 > gap);
484 window_last += i - cut + 1;
485 }
486 goto windowloop;
487 }
488 }
489 for (Py_ssize_t i = 0; i < cut; i++) {
490 if (needle[i] != window[i]) {
491 LOG("Left half does not match.\n");
492 window_last += period;
493 goto windowloop;
494 }
495 }
496 LOG("Found a match!\n");
497 return window - haystack;
498 }
499 }
500 LOG("Not found. Returning -1.\n");
501 return -1;
502 }
503
504
505 static Py_ssize_t
506 STRINGLIB(_two_way_find)(const STRINGLIB_CHAR *haystack,
507 Py_ssize_t len_haystack,
508 const STRINGLIB_CHAR *needle,
509 Py_ssize_t len_needle)
510 {
511 LOG("###### Finding \"%s\" in \"%s\".\n", needle, haystack);
512 STRINGLIB(prework) p;
513 STRINGLIB(_preprocess)(needle, len_needle, &p);
514 return STRINGLIB(_two_way)(haystack, len_haystack, &p);
515 }
516
517
518 static Py_ssize_t
519 STRINGLIB(_two_way_count)(const STRINGLIB_CHAR *haystack,
520 Py_ssize_t len_haystack,
521 const STRINGLIB_CHAR *needle,
522 Py_ssize_t len_needle,
523 Py_ssize_t maxcount)
524 {
525 LOG("###### Counting \"%s\" in \"%s\".\n", needle, haystack);
526 STRINGLIB(prework) p;
527 STRINGLIB(_preprocess)(needle, len_needle, &p);
528 Py_ssize_t index = 0, count = 0;
529 while (1) {
530 Py_ssize_t result;
531 result = STRINGLIB(_two_way)(haystack + index,
532 len_haystack - index, &p);
533 if (result == -1) {
534 return count;
535 }
536 count++;
537 if (count == maxcount) {
538 return maxcount;
539 }
540 index += result + len_needle;
541 }
542 return count;
543 }
544
545 #undef SHIFT_TYPE
546 #undef NOT_FOUND
547 #undef SHIFT_OVERFLOW
548 #undef TABLE_SIZE_BITS
549 #undef TABLE_SIZE
550 #undef TABLE_MASK
551
552 #undef LOG
553 #undef LOG_STRING
554 #undef LOG_LINEUP
555
556 static inline Py_ssize_t
557 STRINGLIB(default_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
558 const STRINGLIB_CHAR* p, Py_ssize_t m,
559 Py_ssize_t maxcount, int mode)
560 {
561 const Py_ssize_t w = n - m;
562 Py_ssize_t mlast = m - 1, count = 0;
563 Py_ssize_t gap = mlast;
564 const STRINGLIB_CHAR last = p[mlast];
565 const STRINGLIB_CHAR *const ss = &s[mlast];
566
567 unsigned long mask = 0;
568 for (Py_ssize_t i = 0; i < mlast; i++) {
569 STRINGLIB_BLOOM_ADD(mask, p[i]);
570 if (p[i] == last) {
571 gap = mlast - i - 1;
572 }
573 }
574 STRINGLIB_BLOOM_ADD(mask, last);
575
576 for (Py_ssize_t i = 0; i <= w; i++) {
577 if (ss[i] == last) {
578 /* candidate match */
579 Py_ssize_t j;
580 for (j = 0; j < mlast; j++) {
581 if (s[i+j] != p[j]) {
582 break;
583 }
584 }
585 if (j == mlast) {
586 /* got a match! */
587 if (mode != FAST_COUNT) {
588 return i;
589 }
590 count++;
591 if (count == maxcount) {
592 return maxcount;
593 }
594 i = i + mlast;
595 continue;
596 }
597 /* miss: check if next character is part of pattern */
598 if (i + 1 <= w && !STRINGLIB_BLOOM(mask, ss[i+1])) {
599 i = i + m;
600 }
601 else {
602 i = i + gap;
603 }
604 }
605 else {
606 /* skip: check if next character is part of pattern */
607 if (i + 1 <= w && !STRINGLIB_BLOOM(mask, ss[i+1])) {
608 i = i + m;
609 }
610 }
611 }
612 return mode == FAST_COUNT ? count : -1;
613 }
614
615
616 static Py_ssize_t
617 STRINGLIB(adaptive_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
618 const STRINGLIB_CHAR* p, Py_ssize_t m,
619 Py_ssize_t maxcount, int mode)
620 {
621 const Py_ssize_t w = n - m;
622 Py_ssize_t mlast = m - 1, count = 0;
623 Py_ssize_t gap = mlast;
624 Py_ssize_t hits = 0, res;
625 const STRINGLIB_CHAR last = p[mlast];
626 const STRINGLIB_CHAR *const ss = &s[mlast];
627
628 unsigned long mask = 0;
629 for (Py_ssize_t i = 0; i < mlast; i++) {
630 STRINGLIB_BLOOM_ADD(mask, p[i]);
631 if (p[i] == last) {
632 gap = mlast - i - 1;
633 }
634 }
635 STRINGLIB_BLOOM_ADD(mask, last);
636
637 for (Py_ssize_t i = 0; i <= w; i++) {
638 if (ss[i] == last) {
639 /* candidate match */
640 Py_ssize_t j;
641 for (j = 0; j < mlast; j++) {
642 if (s[i+j] != p[j]) {
643 break;
644 }
645 }
646 if (j == mlast) {
647 /* got a match! */
648 if (mode != FAST_COUNT) {
649 return i;
650 }
651 count++;
652 if (count == maxcount) {
653 return maxcount;
654 }
655 i = i + mlast;
656 continue;
657 }
658 hits += j + 1;
659 if (hits > m / 4 && w - i > 2000) {
660 if (mode == FAST_SEARCH) {
661 res = STRINGLIB(_two_way_find)(s + i, n - i, p, m);
662 return res == -1 ? -1 : res + i;
663 }
664 else {
665 res = STRINGLIB(_two_way_count)(s + i, n - i, p, m,
666 maxcount - count);
667 return res + count;
668 }
669 }
670 /* miss: check if next character is part of pattern */
671 if (i + 1 <= w && !STRINGLIB_BLOOM(mask, ss[i+1])) {
672 i = i + m;
673 }
674 else {
675 i = i + gap;
676 }
677 }
678 else {
679 /* skip: check if next character is part of pattern */
680 if (i + 1 <= w && !STRINGLIB_BLOOM(mask, ss[i+1])) {
681 i = i + m;
682 }
683 }
684 }
685 return mode == FAST_COUNT ? count : -1;
686 }
687
688
689 static Py_ssize_t
690 STRINGLIB(default_rfind)(const STRINGLIB_CHAR* s, Py_ssize_t n,
691 const STRINGLIB_CHAR* p, Py_ssize_t m,
692 Py_ssize_t maxcount, int mode)
693 {
694 /* create compressed boyer-moore delta 1 table */
695 unsigned long mask = 0;
696 Py_ssize_t i, j, mlast = m - 1, skip = m - 1, w = n - m;
697
698 /* process pattern[0] outside the loop */
699 STRINGLIB_BLOOM_ADD(mask, p[0]);
700 /* process pattern[:0:-1] */
701 for (i = mlast; i > 0; i--) {
702 STRINGLIB_BLOOM_ADD(mask, p[i]);
703 if (p[i] == p[0]) {
704 skip = i - 1;
705 }
706 }
707
708 for (i = w; i >= 0; i--) {
709 if (s[i] == p[0]) {
710 /* candidate match */
711 for (j = mlast; j > 0; j--) {
712 if (s[i+j] != p[j]) {
713 break;
714 }
715 }
716 if (j == 0) {
717 /* got a match! */
718 return i;
719 }
720 /* miss: check if previous character is part of pattern */
721 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {
722 i = i - m;
723 }
724 else {
725 i = i - skip;
726 }
727 }
728 else {
729 /* skip: check if previous character is part of pattern */
730 if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {
731 i = i - m;
732 }
733 }
734 }
735 return -1;
736 }
737
738
739 static inline Py_ssize_t
740 STRINGLIB(count_char)(const STRINGLIB_CHAR *s, Py_ssize_t n,
741 const STRINGLIB_CHAR p0, Py_ssize_t maxcount)
742 {
743 Py_ssize_t i, count = 0;
744 for (i = 0; i < n; i++) {
745 if (s[i] == p0) {
746 count++;
747 if (count == maxcount) {
748 return maxcount;
749 }
750 }
751 }
752 return count;
753 }
754
755
756 static inline Py_ssize_t
757 STRINGLIB(count_char_no_maxcount)(const STRINGLIB_CHAR *s, Py_ssize_t n,
758 const STRINGLIB_CHAR p0)
759 /* A specialized function of count_char that does not cut off at a maximum.
760 As a result, the compiler is able to vectorize the loop. */
761 {
762 Py_ssize_t count = 0;
763 for (Py_ssize_t i = 0; i < n; i++) {
764 if (s[i] == p0) {
765 count++;
766 }
767 }
768 return count;
769 }
770
771
772 Py_LOCAL_INLINE(Py_ssize_t)
773 FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,
774 const STRINGLIB_CHAR* p, Py_ssize_t m,
775 Py_ssize_t maxcount, int mode)
776 {
777 if (n < m || (mode == FAST_COUNT && maxcount == 0)) {
778 return -1;
779 }
780
781 /* look for special cases */
782 if (m <= 1) {
783 if (m <= 0) {
784 return -1;
785 }
786 /* use special case for 1-character strings */
787 if (mode == FAST_SEARCH)
788 return STRINGLIB(find_char)(s, n, p[0]);
789 else if (mode == FAST_RSEARCH)
790 return STRINGLIB(rfind_char)(s, n, p[0]);
791 else {
792 if (maxcount == PY_SSIZE_T_MAX) {
793 return STRINGLIB(count_char_no_maxcount)(s, n, p[0]);
794 }
795 return STRINGLIB(count_char)(s, n, p[0], maxcount);
796 }
797 }
798
799 if (mode != FAST_RSEARCH) {
800 if (n < 2500 || (m < 100 && n < 30000) || m < 6) {
801 return STRINGLIB(default_find)(s, n, p, m, maxcount, mode);
802 }
803 else if ((m >> 2) * 3 < (n >> 2)) {
804 /* 33% threshold, but don't overflow. */
805 /* For larger problems where the needle isn't a huge
806 percentage of the size of the haystack, the relatively
807 expensive O(m) startup cost of the two-way algorithm
808 will surely pay off. */
809 if (mode == FAST_SEARCH) {
810 return STRINGLIB(_two_way_find)(s, n, p, m);
811 }
812 else {
813 return STRINGLIB(_two_way_count)(s, n, p, m, maxcount);
814 }
815 }
816 else {
817 /* To ensure that we have good worst-case behavior,
818 here's an adaptive version of the algorithm, where if
819 we match O(m) characters without any matches of the
820 entire needle, then we predict that the startup cost of
821 the two-way algorithm will probably be worth it. */
822 return STRINGLIB(adaptive_find)(s, n, p, m, maxcount, mode);
823 }
824 }
825 else {
826 /* FAST_RSEARCH */
827 return STRINGLIB(default_rfind)(s, n, p, m, maxcount, mode);
828 }
829 }
830