LCOV - code coverage report
Current view: | top level - Objects/stringlib - fastsearch.h (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 94 | 327 | 28.7 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 12 | 65 | 18.5 %
|  |  | Branches: | 75 | 226 | 33.2 %

               Branch data     Line data    Source code
           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                 :      17153 : STRINGLIB(find_char)(const STRINGLIB_CHAR* s, Py_ssize_t n, STRINGLIB_CHAR ch)
          51                 :            : {
          52                 :            :     const STRINGLIB_CHAR *p, *e;
          53                 :            :
          54                 :      17153 :     p = s;
          55                 :      17153 :     e = s + n;
          56         [ +  + ]:      17153 :     if (n > MEMCHR_CUT_OFF) {
          57                 :            : #ifdef STRINGLIB_FAST_MEMCHR
          58                 :       1819 :         p = STRINGLIB_FAST_MEMCHR(s, ch, n);
          59         [ +  + ]:       1819 :         if (p != NULL)
          60                 :       1017 :             return (p - s);
          61                 :        802 :         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                 :          0 :         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         [ #  # ]:          0 :         if (needle != 0) {
          71                 :            :             do {
          72                 :          0 :                 void *candidate = memchr(p, needle,
          73                 :          0 :                                          (e - p) * sizeof(STRINGLIB_CHAR));
          74         [ #  # ]:          0 :                 if (candidate == NULL)
          75                 :          0 :                     return -1;
          76                 :          0 :                 s1 = p;
          77                 :          0 :                 p = (const STRINGLIB_CHAR *)
          78                 :          0 :                         _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
          79         [ #  # ]:          0 :                 if (*p == ch)
          80                 :          0 :                     return (p - s);
          81                 :            :                 /* False positive */
          82                 :          0 :                 p++;
          83         [ #  # ]:          0 :                 if (p - s1 > MEMCHR_CUT_OFF)
          84                 :          0 :                     continue;
          85         [ #  # ]:          0 :                 if (e - p <= MEMCHR_CUT_OFF)
          86                 :          0 :                     break;
          87                 :          0 :                 e1 = p + MEMCHR_CUT_OFF;
          88         [ #  # ]:          0 :                 while (p != e1) {
          89         [ #  # ]:          0 :                     if (*p == ch)
          90                 :          0 :                         return (p - s);
          91                 :          0 :                     p++;
          92                 :            :                 }
          93                 :            :             }
          94         [ #  # ]:          0 :             while (e - p > MEMCHR_CUT_OFF);
          95                 :            :         }
          96                 :            : #endif
          97                 :            :     }
          98         [ +  + ]:      71090 :     while (p < e) {
          99         [ +  + ]:      57595 :         if (*p == ch)
         100                 :       1839 :             return (p - s);
         101                 :      55756 :         p++;
         102                 :            :     }
         103                 :      13495 :     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                 :       7309 : 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         [ +  + ]:       7309 :     if (n > MEMRCHR_CUT_OFF) {
         126                 :            : #if STRINGLIB_SIZEOF_CHAR == 1
         127                 :       2699 :         p = memrchr(s, ch, n);
         128         [ +  + ]:       2699 :         if (p != NULL)
         129                 :       2269 :             return (p - s);
         130                 :        430 :         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                 :          0 :         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         [ #  # ]:          0 :         if (needle != 0) {
         141                 :            :             do {
         142                 :          0 :                 void *candidate = memrchr(s, needle,
         143                 :            :                                           n * sizeof(STRINGLIB_CHAR));
         144         [ #  # ]:          0 :                 if (candidate == NULL)
         145                 :          0 :                     return -1;
         146                 :          0 :                 n1 = n;
         147                 :          0 :                 p = (const STRINGLIB_CHAR *)
         148                 :          0 :                         _Py_ALIGN_DOWN(candidate, sizeof(STRINGLIB_CHAR));
         149                 :          0 :                 n = p - s;
         150         [ #  # ]:          0 :                 if (*p == ch)
         151                 :          0 :                     return n;
         152                 :            :                 /* False positive */
         153         [ #  # ]:          0 :                 if (n1 - n > MEMRCHR_CUT_OFF)
         154                 :          0 :                     continue;
         155         [ #  # ]:          0 :                 if (n <= MEMRCHR_CUT_OFF)
         156                 :          0 :                     break;
         157                 :          0 :                 s1 = p - MEMRCHR_CUT_OFF;
         158         [ #  # ]:          0 :                 while (p > s1) {
         159                 :          0 :                     p--;
         160         [ #  # ]:          0 :                     if (*p == ch)
         161                 :          0 :                         return (p - s);
         162                 :            :                 }
         163                 :          0 :                 n = p - s;
         164                 :            :             }
         165         [ #  # ]:          0 :             while (n > MEMRCHR_CUT_OFF);
         166                 :            :         }
         167                 :            : #endif
         168                 :            :     }
         169                 :            : #endif  /* HAVE_MEMRCHR */
         170                 :       4610 :     p = s + n;
         171         [ +  + ]:      31105 :     while (p > s) {
         172                 :      28200 :         p--;
         173         [ +  + ]:      28200 :         if (*p == ch)
         174                 :       1705 :             return (p - s);
         175                 :            :     }
         176                 :       2905 :     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                 :          0 : 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                 :          0 :     Py_ssize_t max_suffix = 0;
         204                 :          0 :     Py_ssize_t candidate = 1;
         205                 :          0 :     Py_ssize_t k = 0;
         206                 :            :     // The period of the right half.
         207                 :          0 :     Py_ssize_t period = 1;
         208                 :            :
         209         [ #  # ]:          0 :     while (candidate + k < len_needle) {
         210                 :            :         // each loop increases candidate + k + max_suffix
         211                 :          0 :         STRINGLIB_CHAR a = needle[candidate + k];
         212                 :          0 :         STRINGLIB_CHAR b = needle[max_suffix + k];
         213                 :            :         // check if the suffix at candidate is better than max_suffix
         214   [ #  #  #  # ]:          0 :         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                 :          0 :             candidate += k + 1;
         219                 :          0 :             k = 0;
         220                 :            :             // We've ruled out any period smaller than what's
         221                 :            :             // been scanned since max_suffix.
         222                 :          0 :             period = candidate - max_suffix;
         223                 :            :         }
         224         [ #  # ]:          0 :         else if (a == b) {
         225         [ #  # ]:          0 :             if (k + 1 != period) {
         226                 :            :                 // Keep scanning the equal strings
         227                 :          0 :                 k++;
         228                 :            :             }
         229                 :            :             else {
         230                 :            :                 // Matched a whole period.
         231                 :            :                 // Start matching the next period.
         232                 :          0 :                 candidate += period;
         233                 :          0 :                 k = 0;
         234                 :            :             }
         235                 :            :         }
         236                 :            :         else {
         237                 :            :             // Did better than max_suffix, so replace it.
         238                 :          0 :             max_suffix = candidate;
         239                 :          0 :             candidate++;
         240                 :          0 :             k = 0;
         241                 :          0 :             period = 1;
         242                 :            :         }
         243                 :            :     }
         244                 :          0 :     *return_period = period;
         245                 :          0 :     return max_suffix;
         246                 :            : }
         247                 :            :
         248                 :            : Py_LOCAL_INLINE(Py_ssize_t)
         249                 :          0 : 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 left).
         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                 :          0 :     cut1 = STRINGLIB(_lex_search)(needle, len_needle, &period1, 0);
         287                 :          0 :     cut2 = STRINGLIB(_lex_search)(needle, len_needle, &period2, 1);
         288                 :            :
         289                 :            :     // Take the later cut.
         290         [ #  # ]:          0 :     if (cut1 > cut2) {
         291                 :          0 :         period = period1;
         292                 :          0 :         cut = cut1;
         293                 :            :     }
         294                 :            :     else {
         295                 :          0 :         period = period2;
         296                 :          0 :         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                 :          0 :     *return_period = period;
         304                 :          0 :     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                 :          0 : STRINGLIB(_preprocess)(const STRINGLIB_CHAR *needle, Py_ssize_t len_needle,
         328                 :            :                        STRINGLIB(prework) *p)
         329                 :            : {
         330                 :          0 :     p->needle = needle;
         331                 :          0 :     p->len_needle = len_needle;
         332                 :          0 :     p->cut = STRINGLIB(_factorize)(needle, len_needle, &(p->period));
         333                 :            :     assert(p->period + p->cut <= len_needle);
         334                 :          0 :     p->is_periodic = (0 == memcmp(needle,
         335                 :          0 :                                   needle + p->period,
         336                 :          0 :                                   p->cut * STRINGLIB_SIZEOF_CHAR));
         337         [ #  # ]:          0 :     if (p->is_periodic) {
         338                 :            :         assert(p->cut <= len_needle/2);
         339                 :            :         assert(p->cut < p->period);
         340                 :          0 :         p->gap = 0; // unused
         341                 :            :     }
         342                 :            :     else {
         343                 :            :         // A lower bound on the period
         344                 :          0 :         p->period = Py_MAX(p->cut, len_needle - p->cut) + 1;
         345                 :            :         // The gap between the last character and the previous
         346                 :            :         // occurrence of an equivalent character (modulo TABLE_SIZE)
         347                 :          0 :         p->gap = len_needle;
         348                 :          0 :         STRINGLIB_CHAR last = needle[len_needle - 1] & TABLE_MASK;
         349         [ #  # ]:          0 :         for (Py_ssize_t i = len_needle - 2; i >= 0; i--) {
         350                 :          0 :             STRINGLIB_CHAR x = needle[i] & TABLE_MASK;
         351         [ #  # ]:          0 :             if (x == last) {
         352                 :          0 :                 p->gap = len_needle - 1 - i;
         353                 :          0 :                 break;
         354                 :            :             }
         355                 :            :         }
         356                 :            :     }
         357                 :            :     // Fill up a compressed Boyer-Moore "Bad Character" table
         358                 :          0 :     Py_ssize_t not_found_shift = Py_MIN(len_needle, MAX_SHIFT);
         359         [ #  # ]:          0 :     for (Py_ssize_t i = 0; i < (Py_ssize_t)TABLE_SIZE; i++) {
         360                 :          0 :         p->table[i] = Py_SAFE_DOWNCAST(not_found_shift,
         361                 :            :                                        Py_ssize_t, SHIFT_TYPE);
         362                 :            :     }
         363         [ #  # ]:          0 :     for (Py_ssize_t i = len_needle - not_found_shift; i < len_needle; i++) {
         364                 :          0 :         SHIFT_TYPE shift = Py_SAFE_DOWNCAST(len_needle - 1 - i,
         365                 :            :                                             Py_ssize_t, SHIFT_TYPE);
         366                 :          0 :         p->table[needle[i] & TABLE_MASK] = shift;
         367                 :            :     }
         368                 :          0 : }
         369                 :            :
         370                 :            : static Py_ssize_t
         371                 :          0 : STRINGLIB(_two_way)(const STRINGLIB_CHAR *haystack, Py_ssize_t len_haystack,
         372                 :            :                     STRINGLIB(prework) *p)
         373                 :            : {
         374                 :            :     // Crochemore and Perrin's (1991) Two-Way algorithm.
         375                 :            :     // See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
         376                 :          0 :     const Py_ssize_t len_needle = p->len_needle;
         377                 :          0 :     const Py_ssize_t cut = p->cut;
         378                 :          0 :     Py_ssize_t period = p->period;
         379                 :          0 :     const STRINGLIB_CHAR *const needle = p->needle;
         380                 :          0 :     const STRINGLIB_CHAR *window_last = haystack + len_needle - 1;
         381                 :          0 :     const STRINGLIB_CHAR *const haystack_end = haystack + len_haystack;
         382                 :          0 :     SHIFT_TYPE *table = p->table;
         383                 :            :     const STRINGLIB_CHAR *window;
         384                 :            :     LOG("===== Two-way: \"%s\" in \"%s\". =====\n", needle, haystack);
         385                 :            :
         386         [ #  # ]:          0 :     if (p->is_periodic) {
         387                 :            :         LOG("Needle is periodic.\n");
         388                 :          0 :         Py_ssize_t memory = 0;
         389                 :          0 :       periodicwindowloop:
         390         [ #  # ]:          0 :         while (window_last < haystack_end) {
         391                 :            :             assert(memory == 0);
         392                 :          0 :             for (;;) {
         393                 :            :                 LOG_LINEUP();
         394                 :          0 :                 Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
         395                 :          0 :                 window_last += shift;
         396         [ #  # ]:          0 :                 if (shift == 0) {
         397                 :          0 :                     break;
         398                 :            :                 }
         399         [ #  # ]:          0 :                 if (window_last >= haystack_end) {
         400                 :          0 :                     return -1;
         401                 :            :                 }
         402                 :            :                 LOG("Horspool skip\n");
         403                 :            :             }
         404                 :          0 :           no_shift:
         405                 :          0 :             window = window_last - len_needle + 1;
         406                 :            :             assert((window[len_needle - 1] & TABLE_MASK) ==
         407                 :            :                    (needle[len_needle - 1] & TABLE_MASK));
         408                 :          0 :             Py_ssize_t i = Py_MAX(cut, memory);
         409         [ #  # ]:          0 :             for (; i < len_needle; i++) {
         410         [ #  # ]:          0 :                 if (needle[i] != window[i]) {
         411                 :            :                     LOG("Right half does not match.\n");
         412                 :          0 :                     window_last += i - cut + 1;
         413                 :          0 :                     memory = 0;
         414                 :          0 :                     goto periodicwindowloop;
         415                 :            :                 }
         416                 :            :             }
         417         [ #  # ]:          0 :             for (i = memory; i < cut; i++) {
         418         [ #  # ]:          0 :                 if (needle[i] != window[i]) {
         419                 :            :                     LOG("Left half does not match.\n");
         420                 :          0 :                     window_last += period;
         421                 :          0 :                     memory = len_needle - period;
         422         [ #  # ]:          0 :                     if (window_last >= haystack_end) {
         423                 :          0 :                         return -1;
         424                 :            :                     }
         425                 :          0 :                     Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
         426         [ #  # ]:          0 :                     if (shift) {
         427                 :            :                         // A mismatch has been identified to the right
         428                 :            :                         // of where i will next start, so we can jump
         429                 :            :                         // at least as far as if the mismatch occurred
         430                 :            :                         // on the first comparison.
         431                 :          0 :                         Py_ssize_t mem_jump = Py_MAX(cut, memory) - cut + 1;
         432                 :            :                         LOG("Skip with Memory.\n");
         433                 :          0 :                         memory = 0;
         434         [ #  # ]:          0 :                         window_last += Py_MAX(shift, mem_jump);
         435                 :          0 :                         goto periodicwindowloop;
         436                 :            :                     }
         437                 :          0 :                     goto no_shift;
         438                 :            :                 }
         439                 :            :             }
         440                 :            :             LOG("Found a match!\n");
         441                 :          0 :             return window - haystack;
         442                 :            :         }
         443                 :            :     }
         444                 :            :     else {
         445                 :          0 :         Py_ssize_t gap = p->gap;
         446                 :          0 :         period = Py_MAX(gap, period);
         447                 :            :         LOG("Needle is not periodic.\n");
         448                 :          0 :         Py_ssize_t gap_jump_end = Py_MIN(len_needle, cut + gap);
         449                 :          0 :       windowloop:
         450         [ #  # ]:          0 :         while (window_last < haystack_end) {
         451                 :          0 :             for (;;) {
         452                 :            :                 LOG_LINEUP();
         453                 :          0 :                 Py_ssize_t shift = table[(*window_last) & TABLE_MASK];
         454                 :          0 :                 window_last += shift;
         455         [ #  # ]:          0 :                 if (shift == 0) {
         456                 :          0 :                     break;
         457                 :            :                 }
         458         [ #  # ]:          0 :                 if (window_last >= haystack_end) {
         459                 :          0 :                     return -1;
         460                 :            :                 }
         461                 :            :                 LOG("Horspool skip\n");
         462                 :            :             }
         463                 :          0 :             window = window_last - len_needle + 1;
         464                 :            :             assert((window[len_needle - 1] & TABLE_MASK) ==
         465                 :            :                    (needle[len_needle - 1] & TABLE_MASK));
         466         [ #  # ]:          0 :             for (Py_ssize_t i = cut; i < gap_jump_end; i++) {
         467         [ #  # ]:          0 :                 if (needle[i] != window[i]) {
         468                 :            :                     LOG("Early right half mismatch: jump by gap.\n");
         469                 :            :                     assert(gap >= i - cut + 1);
         470                 :          0 :                     window_last += gap;
         471                 :          0 :                     goto windowloop;
         472                 :            :                 }
         473                 :            :             }
         474         [ #  # ]:          0 :             for (Py_ssize_t i = gap_jump_end; i < len_needle; i++) {
         475         [ #  # ]:          0 :                 if (needle[i] != window[i]) {
         476                 :            :                     LOG("Late right half mismatch.\n");
         477                 :            :                     assert(i - cut + 1 > gap);
         478                 :          0 :                     window_last += i - cut + 1;
         479                 :          0 :                     goto windowloop;
         480                 :            :                 }
         481                 :            :             }
         482         [ #  # ]:          0 :             for (Py_ssize_t i = 0; i < cut; i++) {
         483         [ #  # ]:          0 :                 if (needle[i] != window[i]) {
         484                 :            :                     LOG("Left half does not match.\n");
         485                 :          0 :                     window_last += period;
         486                 :          0 :                     goto windowloop;
         487                 :            :                 }
         488                 :            :             }
         489                 :            :             LOG("Found a match!\n");
         490                 :          0 :             return window - haystack;
         491                 :            :         }
         492                 :            :     }
         493                 :            :     LOG("Not found. Returning -1.\n");
         494                 :          0 :     return -1;
         495                 :            : }
         496                 :            :
         497                 :            :
         498                 :            : static Py_ssize_t
         499                 :          0 : STRINGLIB(_two_way_find)(const STRINGLIB_CHAR *haystack,
         500                 :            :                          Py_ssize_t len_haystack,
         501                 :            :                          const STRINGLIB_CHAR *needle,
         502                 :            :                          Py_ssize_t len_needle)
         503                 :            : {
         504                 :            :     LOG("###### Finding \"%s\" in \"%s\".\n", needle, haystack);
         505                 :            :     STRINGLIB(prework) p;
         506                 :          0 :     STRINGLIB(_preprocess)(needle, len_needle, &p);
         507                 :          0 :     return STRINGLIB(_two_way)(haystack, len_haystack, &p);
         508                 :            : }
         509                 :            :
         510                 :            :
         511                 :            : static Py_ssize_t
         512                 :          0 : STRINGLIB(_two_way_count)(const STRINGLIB_CHAR *haystack,
         513                 :            :                           Py_ssize_t len_haystack,
         514                 :            :                           const STRINGLIB_CHAR *needle,
         515                 :            :                           Py_ssize_t len_needle,
         516                 :            :                           Py_ssize_t maxcount)
         517                 :            : {
         518                 :            :     LOG("###### Counting \"%s\" in \"%s\".\n", needle, haystack);
         519                 :            :     STRINGLIB(prework) p;
         520                 :          0 :     STRINGLIB(_preprocess)(needle, len_needle, &p);
         521                 :          0 :     Py_ssize_t index = 0, count = 0;
         522                 :          0 :     while (1) {
         523                 :            :         Py_ssize_t result;
         524                 :          0 :         result = STRINGLIB(_two_way)(haystack + index,
         525                 :            :                                      len_haystack - index, &p);
         526         [ #  # ]:          0 :         if (result == -1) {
         527                 :          0 :             return count;
         528                 :            :         }
         529                 :          0 :         count++;
         530         [ #  # ]:          0 :         if (count == maxcount) {
         531                 :          0 :             return maxcount;
         532                 :            :         }
         533                 :          0 :         index += result + len_needle;
         534                 :            :     }
         535                 :            :     return count;
         536                 :            : }
         537                 :            :
         538                 :            : #undef SHIFT_TYPE
         539                 :            : #undef NOT_FOUND
         540                 :            : #undef SHIFT_OVERFLOW
         541                 :            : #undef TABLE_SIZE_BITS
         542                 :            : #undef TABLE_SIZE
         543                 :            : #undef TABLE_MASK
         544                 :            :
         545                 :            : #undef LOG
         546                 :            : #undef LOG_STRING
         547                 :            : #undef LOG_LINEUP
         548                 :            :
         549                 :            : static inline Py_ssize_t
         550                 :       6435 : STRINGLIB(default_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
         551                 :            :                         const STRINGLIB_CHAR* p, Py_ssize_t m,
         552                 :            :                         Py_ssize_t maxcount, int mode)
         553                 :            : {
         554                 :       6435 :     const Py_ssize_t w = n - m;
         555                 :       6435 :     Py_ssize_t mlast = m - 1, count = 0;
         556                 :       6435 :     Py_ssize_t gap = mlast;
         557                 :       6435 :     const STRINGLIB_CHAR last = p[mlast];
         558                 :       6435 :     const STRINGLIB_CHAR *const ss = &s[mlast];
         559                 :            :
         560                 :       6435 :     unsigned long mask = 0;
         561         [ +  + ]:      13038 :     for (Py_ssize_t i = 0; i < mlast; i++) {
         562                 :       6603 :         STRINGLIB_BLOOM_ADD(mask, p[i]);
         563         [ +  + ]:       6603 :         if (p[i] == last) {
         564                 :       1168 :             gap = mlast - i - 1;
         565                 :            :         }
         566                 :            :     }
         567                 :       6435 :     STRINGLIB_BLOOM_ADD(mask, last);
         568                 :            :
         569         [ +  + ]:      72107 :     for (Py_ssize_t i = 0; i <= w; i++) {
         570         [ +  + ]:      68473 :         if (ss[i] == last) {
         571                 :            :             /* candidate match */
         572                 :            :             Py_ssize_t j;
         573         [ +  + ]:       6621 :             for (j = 0; j < mlast; j++) {
         574         [ +  + ]:       3811 :                 if (s[i+j] != p[j]) {
         575                 :        833 :                     break;
         576                 :            :                 }
         577                 :            :             }
         578         [ +  + ]:       3643 :             if (j == mlast) {
         579                 :            :                 /* got a match! */
         580         [ +  + ]:       2810 :                 if (mode != FAST_COUNT) {
         581                 :       2801 :                     return i;
         582                 :            :                 }
         583                 :          9 :                 count++;
         584         [ -  + ]:          9 :                 if (count == maxcount) {
         585                 :          0 :                     return maxcount;
         586                 :            :                 }
         587                 :          9 :                 i = i + mlast;
         588                 :          9 :                 continue;
         589                 :            :             }
         590                 :            :             /* miss: check if next character is part of pattern */
         591         [ +  + ]:        833 :             if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
         592                 :        829 :                 i = i + m;
         593                 :            :             }
         594                 :            :             else {
         595                 :          4 :                 i = i + gap;
         596                 :            :             }
         597                 :            :         }
         598                 :            :         else {
         599                 :            :             /* skip: check if next character is part of pattern */
         600         [ +  + ]:      64830 :             if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
         601                 :      59829 :                 i = i + m;
         602                 :            :             }
         603                 :            :         }
         604                 :            :     }
         605         [ +  + ]:       3634 :     return mode == FAST_COUNT ? count : -1;
         606                 :            : }
         607                 :            :
         608                 :            :
         609                 :            : static Py_ssize_t
         610                 :          0 : STRINGLIB(adaptive_find)(const STRINGLIB_CHAR* s, Py_ssize_t n,
         611                 :            :                          const STRINGLIB_CHAR* p, Py_ssize_t m,
         612                 :            :                          Py_ssize_t maxcount, int mode)
         613                 :            : {
         614                 :          0 :     const Py_ssize_t w = n - m;
         615                 :          0 :     Py_ssize_t mlast = m - 1, count = 0;
         616                 :          0 :     Py_ssize_t gap = mlast;
         617                 :          0 :     Py_ssize_t hits = 0, res;
         618                 :          0 :     const STRINGLIB_CHAR last = p[mlast];
         619                 :          0 :     const STRINGLIB_CHAR *const ss = &s[mlast];
         620                 :            :
         621                 :          0 :     unsigned long mask = 0;
         622         [ #  # ]:          0 :     for (Py_ssize_t i = 0; i < mlast; i++) {
         623                 :          0 :         STRINGLIB_BLOOM_ADD(mask, p[i]);
         624         [ #  # ]:          0 :         if (p[i] == last) {
         625                 :          0 :             gap = mlast - i - 1;
         626                 :            :         }
         627                 :            :     }
         628                 :          0 :     STRINGLIB_BLOOM_ADD(mask, last);
         629                 :            :
         630         [ #  # ]:          0 :     for (Py_ssize_t i = 0; i <= w; i++) {
         631         [ #  # ]:          0 :         if (ss[i] == last) {
         632                 :            :             /* candidate match */
         633                 :            :             Py_ssize_t j;
         634         [ #  # ]:          0 :             for (j = 0; j < mlast; j++) {
         635         [ #  # ]:          0 :                 if (s[i+j] != p[j]) {
         636                 :          0 :                     break;
         637                 :            :                 }
         638                 :            :             }
         639         [ #  # ]:          0 :             if (j == mlast) {
         640                 :            :                 /* got a match! */
         641         [ #  # ]:          0 :                 if (mode != FAST_COUNT) {
         642                 :          0 :                     return i;
         643                 :            :                 }
         644                 :          0 :                 count++;
         645         [ #  # ]:          0 :                 if (count == maxcount) {
         646                 :          0 :                     return maxcount;
         647                 :            :                 }
         648                 :          0 :                 i = i + mlast;
         649                 :          0 :                 continue;
         650                 :            :             }
         651                 :          0 :             hits += j + 1;
         652   [ #  #  #  # ]:          0 :             if (hits > m / 4 && w - i > 2000) {
         653         [ #  # ]:          0 :                 if (mode == FAST_SEARCH) {
         654                 :          0 :                     res = STRINGLIB(_two_way_find)(s + i, n - i, p, m);
         655         [ #  # ]:          0 :                     return res == -1 ? -1 : res + i;
         656                 :            :                 }
         657                 :            :                 else {
         658                 :          0 :                     res = STRINGLIB(_two_way_count)(s + i, n - i, p, m,
         659                 :            :                                                     maxcount - count);
         660                 :          0 :                     return res + count;
         661                 :            :                 }
         662                 :            :             }
         663                 :            :             /* miss: check if next character is part of pattern */
         664         [ #  # ]:          0 :             if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
         665                 :          0 :                 i = i + m;
         666                 :            :             }
         667                 :            :             else {
         668                 :          0 :                 i = i + gap;
         669                 :            :             }
         670                 :            :         }
         671                 :            :         else {
         672                 :            :             /* skip: check if next character is part of pattern */
         673         [ #  # ]:          0 :             if (!STRINGLIB_BLOOM(mask, ss[i+1])) {
         674                 :          0 :                 i = i + m;
         675                 :            :             }
         676                 :            :         }
         677                 :            :     }
         678         [ #  # ]:          0 :     return mode == FAST_COUNT ? count : -1;
         679                 :            : }
         680                 :            :
         681                 :            :
         682                 :            : static Py_ssize_t
         683                 :         22 : STRINGLIB(default_rfind)(const STRINGLIB_CHAR* s, Py_ssize_t n,
         684                 :            :                          const STRINGLIB_CHAR* p, Py_ssize_t m,
         685                 :            :                          Py_ssize_t maxcount, int mode)
         686                 :            : {
         687                 :            :     /* create compressed boyer-moore delta 1 table */
         688                 :         22 :     unsigned long mask = 0;
         689                 :         22 :     Py_ssize_t i, j, mlast = m - 1, skip = m - 1, w = n - m;
         690                 :            :
         691                 :            :     /* process pattern[0] outside the loop */
         692                 :         22 :     STRINGLIB_BLOOM_ADD(mask, p[0]);
         693                 :            :     /* process pattern[:0:-1] */
         694         [ +  + ]:         88 :     for (i = mlast; i > 0; i--) {
         695                 :         66 :         STRINGLIB_BLOOM_ADD(mask, p[i]);
         696         [ -  + ]:         66 :         if (p[i] == p[0]) {
         697                 :          0 :             skip = i - 1;
         698                 :            :         }
         699                 :            :     }
         700                 :            :
         701         [ +  + ]:      14866 :     for (i = w; i >= 0; i--) {
         702         [ +  + ]:      14844 :         if (s[i] == p[0]) {
         703                 :            :             /* candidate match */
         704         [ +  - ]:         74 :             for (j = mlast; j > 0; j--) {
         705         [ +  - ]:         74 :                 if (s[i+j] != p[j]) {
         706                 :         74 :                     break;
         707                 :            :                 }
         708                 :            :             }
         709         [ -  + ]:         74 :             if (j == 0) {
         710                 :            :                 /* got a match! */
         711                 :          0 :                 return i;
         712                 :            :             }
         713                 :            :             /* miss: check if previous character is part of pattern */
         714   [ +  -  +  + ]:         74 :             if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {
         715                 :         73 :                 i = i - m;
         716                 :            :             }
         717                 :            :             else {
         718                 :          1 :                 i = i - skip;
         719                 :            :             }
         720                 :            :         }
         721                 :            :         else {
         722                 :            :             /* skip: check if previous character is part of pattern */
         723   [ +  +  +  + ]:      14770 :             if (i > 0 && !STRINGLIB_BLOOM(mask, s[i-1])) {
         724                 :      14653 :                 i = i - m;
         725                 :            :             }
         726                 :            :         }
         727                 :            :     }
         728                 :         22 :     return -1;
         729                 :            : }
         730                 :            :
         731                 :            :
         732                 :            : static inline Py_ssize_t
         733                 :       4840 : STRINGLIB(count_char)(const STRINGLIB_CHAR *s, Py_ssize_t n,
         734                 :            :                       const STRINGLIB_CHAR p0, Py_ssize_t maxcount)
         735                 :            : {
         736                 :       4840 :     Py_ssize_t i, count = 0;
         737         [ +  + ]:      87660 :     for (i = 0; i < n; i++) {
         738         [ +  + ]:      82820 :         if (s[i] == p0) {
         739                 :        305 :             count++;
         740         [ -  + ]:        305 :             if (count == maxcount) {
         741                 :          0 :                 return maxcount;
         742                 :            :             }
         743                 :            :         }
         744                 :            :     }
         745                 :       4840 :     return count;
         746                 :            : }
         747                 :            :
         748                 :            :
         749                 :            : Py_LOCAL_INLINE(Py_ssize_t)
         750                 :      15847 : FASTSEARCH(const STRINGLIB_CHAR* s, Py_ssize_t n,
         751                 :            :            const STRINGLIB_CHAR* p, Py_ssize_t m,
         752                 :            :            Py_ssize_t maxcount, int mode)
         753                 :            : {
         754   [ +  -  +  +  :      15847 :     if (n < m || (mode == FAST_COUNT && maxcount == 0)) {
                       -  + ]
         755                 :          0 :         return -1;
         756                 :            :     }
         757                 :            :
         758                 :            :     /* look for special cases */
         759         [ +  + ]:      15847 :     if (m <= 1) {
         760         [ -  + ]:       9390 :         if (m <= 0) {
         761                 :          0 :             return -1;
         762                 :            :         }
         763                 :            :         /* use special case for 1-character strings */
         764         [ +  + ]:       9390 :         if (mode == FAST_SEARCH)
         765                 :        163 :             return STRINGLIB(find_char)(s, n, p[0]);
         766         [ +  + ]:       9227 :         else if (mode == FAST_RSEARCH)
         767                 :       4387 :             return STRINGLIB(rfind_char)(s, n, p[0]);
         768                 :            :         else {
         769                 :       4840 :             return STRINGLIB(count_char)(s, n, p[0], maxcount);
         770                 :            :         }
         771                 :            :     }
         772                 :            :
         773         [ +  + ]:       6457 :     if (mode != FAST_RSEARCH) {
         774   [ -  +  -  -  :       6435 :         if (n < 2500 || (m < 100 && n < 30000) || m < 6) {
                 -  -  -  - ]
         775                 :       6435 :             return STRINGLIB(default_find)(s, n, p, m, maxcount, mode);
         776                 :            :         }
         777         [ #  # ]:          0 :         else if ((m >> 2) * 3 < (n >> 2)) {
         778                 :            :             /* 33% threshold, but don't overflow. */
         779                 :            :             /* For larger problems where the needle isn't a huge
         780                 :            :                percentage of the size of the haystack, the relatively
         781                 :            :                expensive O(m) startup cost of the two-way algorithm
         782                 :            :                will surely pay off. */
         783         [ #  # ]:          0 :             if (mode == FAST_SEARCH) {
         784                 :          0 :                 return STRINGLIB(_two_way_find)(s, n, p, m);
         785                 :            :             }
         786                 :            :             else {
         787                 :          0 :                 return STRINGLIB(_two_way_count)(s, n, p, m, maxcount);
         788                 :            :             }
         789                 :            :         }
         790                 :            :         else {
         791                 :            :             /* To ensure that we have good worst-case behavior,
         792                 :            :                here's an adaptive version of the algorithm, where if
         793                 :            :                we match O(m) characters without any matches of the
         794                 :            :                entire needle, then we predict that the startup cost of
         795                 :            :                the two-way algorithm will probably be worth it. */
         796                 :          0 :             return STRINGLIB(adaptive_find)(s, n, p, m, maxcount, mode);
         797                 :            :         }
         798                 :            :     }
         799                 :            :     else {
         800                 :            :         /* FAST_RSEARCH */
         801                 :         22 :         return STRINGLIB(default_rfind)(s, n, p, m, maxcount, mode);
         802                 :            :     }
         803                 :            : }
         804                 :            :

Generated by: LCOV version 1.14