| 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 |
|