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 2, 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, which guarantees
48 linear complexity with constant space. Additionally, for long
49 needles, we also use a bad character shift table similar to the
50 Boyer-Moore algorithm to achieve improved (potentially sub-linear)
53 See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
54 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
57 /* Point at which computing a bad-byte shift table is likely to be
58 worthwhile. Small needles should not compute a table, since it
59 adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
60 speedup no greater than a factor of NEEDLE_LEN. The larger the
61 needle, the better the potential performance gain. On the other
62 hand, on non-POSIX systems with CHAR_BIT larger than eight, the
63 memory required for the table is prohibitive. */
65 # define LONG_NEEDLE_THRESHOLD 32U
67 # define LONG_NEEDLE_THRESHOLD SIZE_MAX
71 # define MAX(a, b) ((a < b) ? (b) : (a))
75 # define CANON_ELEMENT(c) c
78 # define CMP_FUNC memcmp
81 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
82 Return the index of the first byte in the right half, and set
83 *PERIOD to the global period of the right half.
85 The global period of a string is the smallest index (possibly its
86 length) at which all remaining bytes in the string are repetitions
87 of the prefix (the last repetition may be a subset of the prefix).
89 When NEEDLE is factored into two halves, a local period is the
90 length of the smallest word that shares a suffix with the left half
91 and shares a prefix with the right half. All factorizations of a
92 non-empty NEEDLE have a local period of at least 1 and no greater
95 A critical factorization has the property that the local period
96 equals the global period. All strings have at least one critical
97 factorization with the left half smaller than the global period.
98 And while some strings have more than one critical factorization,
99 it is provable that with an ordered alphabet, at least one of the
100 critical factorizations corresponds to a maximal suffix.
102 Given an ordered alphabet, a critical factorization can be computed
103 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
104 shorter of two ordered maximal suffixes. The ordered maximal
105 suffixes are determined by lexicographic comparison while tracking
108 critical_factorization (const unsigned char *needle, size_t needle_len,
111 /* Index of last byte of left half. */
112 size_t max_suffix, max_suffix_rev;
113 size_t j; /* Index into NEEDLE for current candidate suffix. */
114 size_t k; /* Offset into current period. */
115 size_t p; /* Intermediate period. */
116 unsigned char a, b; /* Current comparison bytes. */
118 /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
119 out 0-length needles. */
123 return needle_len - 1;
127 1 <= j < NEEDLE_LEN - 1
128 0 <= max_suffix{,_rev} < j
129 min(max_suffix, max_suffix_rev) < global period of NEEDLE
130 1 <= p <= global period of NEEDLE
131 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
135 /* Perform lexicographic search. */
138 while (j + k < needle_len)
140 a = CANON_ELEMENT (needle[j + k]);
141 b = CANON_ELEMENT (needle[max_suffix + k]);
144 /* Suffix is smaller, period is entire prefix so far. */
151 /* Advance through repetition of the current period. */
162 /* Suffix is larger, start over from current location. */
169 /* Perform reverse lexicographic search. */
172 while (j + k < needle_len)
174 a = CANON_ELEMENT (needle[j + k]);
175 b = CANON_ELEMENT (needle[max_suffix_rev + k]);
178 /* Suffix is smaller, period is entire prefix so far. */
181 p = j - max_suffix_rev;
185 /* Advance through repetition of the current period. */
196 /* Suffix is larger, start over from current location. */
197 max_suffix_rev = j++;
202 /* Choose the shorter suffix. Return the index of the first byte of
203 the right half, rather than the last byte of the left half.
205 For some examples, 'banana' has two critical factorizations, both
206 exposed by the two lexicographic extreme suffixes of 'anana' and
207 'nana', where both suffixes have a period of 2. On the other
208 hand, with 'aab' and 'bba', both strings have a single critical
209 factorization of the last byte, with the suffix having a period
210 of 1. While the maximal lexicographic suffix of 'aab' is 'b',
211 the maximal lexicographic suffix of 'bba' is 'ba', which is not a
212 critical factorization. Conversely, the maximal reverse
213 lexicographic suffix of 'a' works for 'bba', but not 'ab' for
214 'aab'. The shorter suffix of the two will always be a critical
216 if (max_suffix_rev + 1 < max_suffix + 1)
217 return max_suffix + 1;
219 return max_suffix_rev + 1;
222 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
223 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
224 method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
225 Performance is guaranteed to be linear, with an initialization cost
226 of 2 * NEEDLE_LEN comparisons.
228 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
229 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
230 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
231 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
233 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
234 const unsigned char *needle, size_t needle_len)
236 size_t i; /* Index into current byte of NEEDLE. */
237 size_t j; /* Index into current window of HAYSTACK. */
238 size_t period; /* The period of the right half of needle. */
239 size_t suffix; /* The index of the right half of needle. */
241 /* Factor the needle into two halves, such that the left half is
242 smaller than the global period, and the right half is
243 periodic (with a period as large as NEEDLE_LEN - suffix). */
244 suffix = critical_factorization (needle, needle_len, &period);
246 /* Perform the search. Each iteration compares the right half
248 if (CMP_FUNC (needle, needle + period, suffix) == 0)
250 /* Entire needle is periodic; a mismatch in the left half can
251 only advance by the period, so use memory to avoid rescanning
252 known occurrences of the period in the right half. */
255 while (AVAILABLE (haystack, haystack_len, j, needle_len))
257 /* Scan for matches in right half. */
258 i = MAX (suffix, memory);
259 while (i < needle_len && (CANON_ELEMENT (needle[i])
260 == CANON_ELEMENT (haystack[i + j])))
264 /* Scan for matches in left half. */
266 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
267 == CANON_ELEMENT (haystack[i + j])))
269 if (i + 1 < memory + 1)
270 return (RETURN_TYPE) (haystack + j);
271 /* No match, so remember how many repetitions of period
272 on the right half were scanned. */
274 memory = needle_len - period;
285 /* The two halves of needle are distinct; no extra memory is
286 required, and any mismatch results in a maximal shift. */
287 period = MAX (suffix, needle_len - suffix) + 1;
289 while (AVAILABLE (haystack, haystack_len, j, needle_len))
291 /* Scan for matches in right half. */
293 while (i < needle_len && (CANON_ELEMENT (needle[i])
294 == CANON_ELEMENT (haystack[i + j])))
298 /* Scan for matches in left half. */
300 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
301 == CANON_ELEMENT (haystack[i + j])))
304 return (RETURN_TYPE) (haystack + j);
314 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
315 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
316 method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
317 Performance is guaranteed to be linear, with an initialization cost
318 of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
320 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
321 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
322 and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
323 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
324 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
325 sublinear performance is not possible. */
327 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
328 const unsigned char *needle, size_t needle_len)
330 size_t i; /* Index into current byte of NEEDLE. */
331 size_t j; /* Index into current window of HAYSTACK. */
332 size_t period; /* The period of the right half of needle. */
333 size_t suffix; /* The index of the right half of needle. */
334 size_t shift_table[1U << CHAR_BIT]; /* See below. */
336 /* Factor the needle into two halves, such that the left half is
337 smaller than the global period, and the right half is
338 periodic (with a period as large as NEEDLE_LEN - suffix). */
339 suffix = critical_factorization (needle, needle_len, &period);
341 /* Populate shift_table. For each possible byte value c,
342 shift_table[c] is the distance from the last occurrence of c to
343 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
344 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
345 for (i = 0; i < 1U << CHAR_BIT; i++)
346 shift_table[i] = needle_len;
347 for (i = 0; i < needle_len; i++)
348 shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
350 /* Perform the search. Each iteration compares the right half
352 if (CMP_FUNC (needle, needle + period, suffix) == 0)
354 /* Entire needle is periodic; a mismatch in the left half can
355 only advance by the period, so use memory to avoid rescanning
356 known occurrences of the period in the right half. */
360 while (AVAILABLE (haystack, haystack_len, j, needle_len))
362 /* Check the last byte first; if it does not match, then
363 shift to the next possible match location. */
364 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
367 if (memory && shift < period)
369 /* Since needle is periodic, but the last period has
370 a byte out of place, there can be no match until
371 after the mismatch. */
372 shift = needle_len - period;
378 /* Scan for matches in right half. The last byte has
379 already been matched, by virtue of the shift table. */
380 i = MAX (suffix, memory);
381 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
382 == CANON_ELEMENT (haystack[i + j])))
384 if (needle_len - 1 <= i)
386 /* Scan for matches in left half. */
388 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
389 == CANON_ELEMENT (haystack[i + j])))
391 if (i + 1 < memory + 1)
392 return (RETURN_TYPE) (haystack + j);
393 /* No match, so remember how many repetitions of period
394 on the right half were scanned. */
396 memory = needle_len - period;
407 /* The two halves of needle are distinct; no extra memory is
408 required, and any mismatch results in a maximal shift. */
410 period = MAX (suffix, needle_len - suffix) + 1;
412 while (AVAILABLE (haystack, haystack_len, j, needle_len))
414 /* Check the last byte first; if it does not match, then
415 shift to the next possible match location. */
416 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
422 /* Scan for matches in right half. The last byte has
423 already been matched, by virtue of the shift table. */
425 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
426 == CANON_ELEMENT (haystack[i + j])))
428 if (needle_len - 1 <= i)
430 /* Scan for matches in left half. */
432 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
433 == CANON_ELEMENT (haystack[i + j])))
436 return (RETURN_TYPE) (haystack + j);