1
/* Byte-wise substring search, using the Two-Way algorithm.
2
Copyright (C) 2008-2011 Free Software Foundation, Inc.
3
This file is part of the GNU C Library.
4
Written by Eric Blake <ebb9@byu.net>, 2008.
6
This program is free software; you can redistribute it and/or modify
7
it under the terms of the GNU General Public License as published by
8
the Free Software Foundation; either version 3, or (at your option)
11
This program is distributed in the hope that it will be useful,
12
but WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14
GNU General Public License for more details.
16
You should have received a copy of the GNU General Public License along
17
with this program; if not, write to the Free Software Foundation,
18
Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20
/* Before including this file, you need to include <config.h> and
21
<string.h>, and define:
22
RESULT_TYPE A macro that expands to the return type.
23
AVAILABLE(h, h_l, j, n_l)
24
A macro that returns nonzero if there are
25
at least N_L bytes left starting at H[J].
26
H is 'unsigned char *', H_L, J, and N_L
27
are 'size_t'; H_L is an lvalue. For
28
NUL-terminated searches, H_L can be
29
modified each iteration to avoid having
30
to compute the end of H up front.
32
For case-insensitivity, you may optionally define:
33
CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L
34
characters of P1 and P2 are equal.
35
CANON_ELEMENT(c) A macro that canonicalizes an element right after
36
it has been fetched from one of the two strings.
37
The argument is an 'unsigned char'; the result
38
must be an 'unsigned char' as well.
40
This file undefines the macros documented above, and defines
41
LONG_NEEDLE_THRESHOLD.
47
/* We use the Two-Way string matching algorithm (also known as
48
Chrochemore-Perrin), which guarantees linear complexity with
49
constant space. Additionally, for long needles, we also use a bad
50
character shift table similar to the Boyer-Moore algorithm to
51
achieve improved (potentially sub-linear) performance.
53
See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260,
54
http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm,
55
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.34.6641&rep=rep1&type=pdf
58
/* Point at which computing a bad-byte shift table is likely to be
59
worthwhile. Small needles should not compute a table, since it
60
adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
61
speedup no greater than a factor of NEEDLE_LEN. The larger the
62
needle, the better the potential performance gain. On the other
63
hand, on non-POSIX systems with CHAR_BIT larger than eight, the
64
memory required for the table is prohibitive. */
66
# define LONG_NEEDLE_THRESHOLD 32U
68
# define LONG_NEEDLE_THRESHOLD SIZE_MAX
72
# define MAX(a, b) ((a < b) ? (b) : (a))
76
# define CANON_ELEMENT(c) c
79
# define CMP_FUNC memcmp
82
/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
83
Return the index of the first byte in the right half, and set
84
*PERIOD to the global period of the right half.
86
The global period of a string is the smallest index (possibly its
87
length) at which all remaining bytes in the string are repetitions
88
of the prefix (the last repetition may be a subset of the prefix).
90
When NEEDLE is factored into two halves, a local period is the
91
length of the smallest word that shares a suffix with the left half
92
and shares a prefix with the right half. All factorizations of a
93
non-empty NEEDLE have a local period of at least 1 and no greater
96
A critical factorization has the property that the local period
97
equals the global period. All strings have at least one critical
98
factorization with the left half smaller than the global period.
99
And while some strings have more than one critical factorization,
100
it is provable that with an ordered alphabet, at least one of the
101
critical factorizations corresponds to a maximal suffix.
103
Given an ordered alphabet, a critical factorization can be computed
104
in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
105
shorter of two ordered maximal suffixes. The ordered maximal
106
suffixes are determined by lexicographic comparison while tracking
109
critical_factorization (const unsigned char *needle, size_t needle_len,
112
/* Index of last byte of left half, or SIZE_MAX. */
113
size_t max_suffix, max_suffix_rev;
114
size_t j; /* Index into NEEDLE for current candidate suffix. */
115
size_t k; /* Offset into current period. */
116
size_t p; /* Intermediate period. */
117
unsigned char a, b; /* Current comparison bytes. */
119
/* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
120
out 0-length needles. */
124
return needle_len - 1;
128
0 <= j < NEEDLE_LEN - 1
129
-1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
130
min(max_suffix, max_suffix_rev) < global period of NEEDLE
131
1 <= p <= global period of NEEDLE
132
p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
136
/* Perform lexicographic search. */
137
max_suffix = SIZE_MAX;
140
while (j + k < needle_len)
142
a = CANON_ELEMENT (needle[j + k]);
143
b = CANON_ELEMENT (needle[max_suffix + k]);
146
/* Suffix is smaller, period is entire prefix so far. */
153
/* Advance through repetition of the current period. */
164
/* Suffix is larger, start over from current location. */
171
/* Perform reverse lexicographic search. */
172
max_suffix_rev = SIZE_MAX;
175
while (j + k < needle_len)
177
a = CANON_ELEMENT (needle[j + k]);
178
b = CANON_ELEMENT (needle[max_suffix_rev + k]);
181
/* Suffix is smaller, period is entire prefix so far. */
184
p = j - max_suffix_rev;
188
/* Advance through repetition of the current period. */
199
/* Suffix is larger, start over from current location. */
200
max_suffix_rev = j++;
205
/* Choose the shorter suffix. Return the index of the first byte of
206
the right half, rather than the last byte of the left half.
208
For some examples, 'banana' has two critical factorizations, both
209
exposed by the two lexicographic extreme suffixes of 'anana' and
210
'nana', where both suffixes have a period of 2. On the other
211
hand, with 'aab' and 'bba', both strings have a single critical
212
factorization of the last byte, with the suffix having a period
213
of 1. While the maximal lexicographic suffix of 'aab' is 'b',
214
the maximal lexicographic suffix of 'bba' is 'ba', which is not a
215
critical factorization. Conversely, the maximal reverse
216
lexicographic suffix of 'a' works for 'bba', but not 'ab' for
217
'aab'. The shorter suffix of the two will always be a critical
219
if (max_suffix_rev + 1 < max_suffix + 1)
220
return max_suffix + 1;
222
return max_suffix_rev + 1;
225
/* Return the first location of non-empty NEEDLE within HAYSTACK, or
226
NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
227
method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
228
Performance is guaranteed to be linear, with an initialization cost
229
of 2 * NEEDLE_LEN comparisons.
231
If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
232
most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
233
If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
234
HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
236
two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
237
const unsigned char *needle, size_t needle_len)
239
size_t i; /* Index into current byte of NEEDLE. */
240
size_t j; /* Index into current window of HAYSTACK. */
241
size_t period; /* The period of the right half of needle. */
242
size_t suffix; /* The index of the right half of needle. */
244
/* Factor the needle into two halves, such that the left half is
245
smaller than the global period, and the right half is
246
periodic (with a period as large as NEEDLE_LEN - suffix). */
247
suffix = critical_factorization (needle, needle_len, &period);
249
/* Perform the search. Each iteration compares the right half
251
if (CMP_FUNC (needle, needle + period, suffix) == 0)
253
/* Entire needle is periodic; a mismatch in the left half can
254
only advance by the period, so use memory to avoid rescanning
255
known occurrences of the period in the right half. */
258
while (AVAILABLE (haystack, haystack_len, j, needle_len))
260
/* Scan for matches in right half. */
261
i = MAX (suffix, memory);
262
while (i < needle_len && (CANON_ELEMENT (needle[i])
263
== CANON_ELEMENT (haystack[i + j])))
267
/* Scan for matches in left half. */
269
while (memory < i + 1 && (CANON_ELEMENT (needle[i])
270
== CANON_ELEMENT (haystack[i + j])))
272
if (i + 1 < memory + 1)
273
return (RETURN_TYPE) (haystack + j);
274
/* No match, so remember how many repetitions of period
275
on the right half were scanned. */
277
memory = needle_len - period;
288
/* The two halves of needle are distinct; no extra memory is
289
required, and any mismatch results in a maximal shift. */
290
period = MAX (suffix, needle_len - suffix) + 1;
292
while (AVAILABLE (haystack, haystack_len, j, needle_len))
294
/* Scan for matches in right half. */
296
while (i < needle_len && (CANON_ELEMENT (needle[i])
297
== CANON_ELEMENT (haystack[i + j])))
301
/* Scan for matches in left half. */
303
while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
304
== CANON_ELEMENT (haystack[i + j])))
307
return (RETURN_TYPE) (haystack + j);
317
/* Return the first location of non-empty NEEDLE within HAYSTACK, or
318
NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
319
method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
320
Performance is guaranteed to be linear, with an initialization cost
321
of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
323
If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
324
most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
325
and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
326
If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
327
HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
328
sublinear performance is not possible. */
330
two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
331
const unsigned char *needle, size_t needle_len)
333
size_t i; /* Index into current byte of NEEDLE. */
334
size_t j; /* Index into current window of HAYSTACK. */
335
size_t period; /* The period of the right half of needle. */
336
size_t suffix; /* The index of the right half of needle. */
337
size_t shift_table[1U << CHAR_BIT]; /* See below. */
339
/* Factor the needle into two halves, such that the left half is
340
smaller than the global period, and the right half is
341
periodic (with a period as large as NEEDLE_LEN - suffix). */
342
suffix = critical_factorization (needle, needle_len, &period);
344
/* Populate shift_table. For each possible byte value c,
345
shift_table[c] is the distance from the last occurrence of c to
346
the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
347
shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
348
for (i = 0; i < 1U << CHAR_BIT; i++)
349
shift_table[i] = needle_len;
350
for (i = 0; i < needle_len; i++)
351
shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
353
/* Perform the search. Each iteration compares the right half
355
if (CMP_FUNC (needle, needle + period, suffix) == 0)
357
/* Entire needle is periodic; a mismatch in the left half can
358
only advance by the period, so use memory to avoid rescanning
359
known occurrences of the period in the right half. */
363
while (AVAILABLE (haystack, haystack_len, j, needle_len))
365
/* Check the last byte first; if it does not match, then
366
shift to the next possible match location. */
367
shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
370
if (memory && shift < period)
372
/* Since needle is periodic, but the last period has
373
a byte out of place, there can be no match until
374
after the mismatch. */
375
shift = needle_len - period;
381
/* Scan for matches in right half. The last byte has
382
already been matched, by virtue of the shift table. */
383
i = MAX (suffix, memory);
384
while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
385
== CANON_ELEMENT (haystack[i + j])))
387
if (needle_len - 1 <= i)
389
/* Scan for matches in left half. */
391
while (memory < i + 1 && (CANON_ELEMENT (needle[i])
392
== CANON_ELEMENT (haystack[i + j])))
394
if (i + 1 < memory + 1)
395
return (RETURN_TYPE) (haystack + j);
396
/* No match, so remember how many repetitions of period
397
on the right half were scanned. */
399
memory = needle_len - period;
410
/* The two halves of needle are distinct; no extra memory is
411
required, and any mismatch results in a maximal shift. */
413
period = MAX (suffix, needle_len - suffix) + 1;
415
while (AVAILABLE (haystack, haystack_len, j, needle_len))
417
/* Check the last byte first; if it does not match, then
418
shift to the next possible match location. */
419
shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
425
/* Scan for matches in right half. The last byte has
426
already been matched, by virtue of the shift table. */
428
while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
429
== CANON_ELEMENT (haystack[i + j])))
431
if (needle_len - 1 <= i)
433
/* Scan for matches in left half. */
435
while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
436
== CANON_ELEMENT (haystack[i + j])))
439
return (RETURN_TYPE) (haystack + j);
added
removed
lib/str-two-way.h
