1 /* Copyright (C) 1991,92,93,94,96,97,98,2000,2004,2007,2008 Free Software
3 This file is part of the GNU C Library.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License along
16 with this program; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
19 /* This particular implementation was written by Eric Blake, 2008. */
25 /* Specification of strstr. */
34 # define __builtin_expect(expr, val) (expr)
37 /* We use the Two-Way string matching algorithm, which guarantees
38 linear complexity with constant space. Additionally, for long
39 needles, we also use a bad character shift table similar to the
40 Boyer-Moore algorithm to achieve better performance.
42 See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
43 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
46 /* Point at which computing a bad-byte shift table is likely to be
47 worthwhile. Small needles should not compute a table, since it
48 adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a
49 speedup no greater than a factor of NEEDLE_LEN. The larger the
50 needle, the better the potential performance gain. On the other
51 hand, on non-POSIX systems with CHAR_BIT larger than eight, the
52 memory required for the table is prohibitive. */
54 # define LONG_NEEDLE_THRESHOLD 32U
56 # define LONG_NEEDLE_THRESHOLD SIZE_MAX
59 #define MAX(a, b) ((a < b) ? (b) : (a))
61 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
62 Return the index of the first byte in the right half, and set
63 *PERIOD to the global period of the right half.
65 The global period of a string is the smallest index (possibly its
66 length) at which all remaining bytes in the string are repetitions
67 of the prefix (the last repetition may be a subset of the prefix).
69 When NEEDLE is factored into two halves, a local period is the
70 length of the smallest word that shares a suffix with the left half
71 and shares a prefix with the right half. All factorizations of a
72 non-empty NEEDLE have a local period of at least 1 and no greater
75 A critical factorization has the property that the local period
76 equals the global period. All strings have at least one critical
77 factorization with the left half smaller than the global period.
79 Given an ordered alphabet, a critical factorization can be computed
80 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
81 larger of two ordered maximal suffixes. The ordered maximal
82 suffixes are determined by lexicographic comparison of
85 critical_factorization (const unsigned char *needle, size_t needle_len,
88 /* Index of last byte of left half, or SIZE_MAX. */
89 size_t max_suffix, max_suffix_rev;
90 size_t j; /* Index into NEEDLE for current candidate suffix. */
91 size_t k; /* Offset into current period. */
92 size_t p; /* Intermediate period. */
93 unsigned char a, b; /* Current comparison bytes. */
96 0 <= j < NEEDLE_LEN - 1
97 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
98 min(max_suffix, max_suffix_rev) < global period of NEEDLE
99 1 <= p <= global period of NEEDLE
100 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
104 /* Perform lexicographic search. */
105 max_suffix = SIZE_MAX;
108 while (j + k < needle_len)
111 b = needle[max_suffix + k];
114 /* Suffix is smaller, period is entire prefix so far. */
121 /* Advance through repetition of the current period. */
132 /* Suffix is larger, start over from current location. */
139 /* Perform reverse lexicographic search. */
140 max_suffix_rev = SIZE_MAX;
143 while (j + k < needle_len)
146 b = needle[max_suffix_rev + k];
149 /* Suffix is smaller, period is entire prefix so far. */
152 p = j - max_suffix_rev;
156 /* Advance through repetition of the current period. */
167 /* Suffix is larger, start over from current location. */
168 max_suffix_rev = j++;
173 /* Choose the longer suffix. Return the first byte of the right
174 half, rather than the last byte of the left half. */
175 if (max_suffix_rev + 1 < max_suffix + 1)
176 return max_suffix + 1;
178 return max_suffix_rev + 1;
181 /* Return the first location of NEEDLE within HAYSTACK, or NULL. This
182 method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
183 for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD. Performance is linear,
184 with 2 * NEEDLE_LEN comparisons in preparation, and at most 3 *
185 HAYSTACK_LEN - NEEDLE_LEN comparisons in searching. */
187 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
188 const unsigned char *needle, size_t needle_len)
190 size_t i; /* Index into current byte of NEEDLE. */
191 size_t j; /* Index into current window of HAYSTACK. */
192 size_t period; /* The period of the right half of needle. */
193 size_t suffix; /* The index of the right half of needle. */
195 /* Factor the needle into two halves, such that the left half is
196 smaller than the global period, and the right half is
197 periodic (with a period as large as NEEDLE_LEN - suffix). */
198 suffix = critical_factorization (needle, needle_len, &period);
200 /* Perform the search. Each iteration compares the right half
202 if (memcmp (needle, needle + period, suffix) == 0)
204 /* Entire needle is periodic; a mismatch can only advance by the
205 period, so use memory to avoid rescanning known occurrences
209 while (!memchr (&haystack[haystack_len], '\0',
210 j + needle_len - haystack_len)
211 && (haystack_len = j + needle_len))
213 /* Scan for matches in right half. */
214 i = MAX (suffix, memory);
215 while (i < needle_len && needle[i] == haystack[i + j])
219 /* Scan for matches in left half. */
221 while (memory < i + 1 && needle[i] == haystack[i + j])
223 if (i + 1 < memory + 1)
224 return (char *) (haystack + j);
225 /* No match, so remember how many repetitions of period
226 on the right half were scanned. */
228 memory = needle_len - period;
239 /* The two halves of needle are distinct; no extra memory is
240 required, and any mismatch results in a maximal shift. */
241 period = MAX (suffix, needle_len - suffix) + 1;
243 while (!memchr (&haystack[haystack_len], '\0',
244 j + needle_len - haystack_len)
245 && (haystack_len = j + needle_len))
247 /* Scan for matches in right half. */
249 while (i < needle_len && needle[i] == haystack[i + j])
253 /* Scan for matches in left half. */
255 while (i != SIZE_MAX && needle[i] == haystack[i + j])
258 return (char *) (haystack + j);
268 /* Return the first location of NEEDLE within HAYSTACK, or NULL. This
269 method requires 0 < NEEDLE_LEN <= HAYSTACK_LEN, and is optimized
270 for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN. Performance is linear,
271 with 3 * NEEDLE_LEN + (1U << CHAR_BIT) operations in preparation,
272 and at most 3 * HAYSTACK_LEN - NEEDLE_LEN comparisons in searching.
273 The extra initialization cost allows for as few as HAYSTACK_LEN +
274 HAYSTACK_LEN / NEEDLE_LEN. */
276 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
277 const unsigned char *needle, size_t needle_len)
279 size_t i; /* Index into current byte of NEEDLE. */
280 size_t j; /* Index into current window of HAYSTACK. */
281 size_t period; /* The period of the right half of needle. */
282 size_t suffix; /* The index of the right half of needle. */
283 size_t shift_table[1U << CHAR_BIT]; /* See below. */
285 /* Factor the needle into two halves, such that the left half is
286 smaller than the global period, and the right half is
287 periodic (with a period as large as NEEDLE_LEN - suffix). */
288 suffix = critical_factorization (needle, needle_len, &period);
290 /* Populate shift_table. For each possible byte value c,
291 shift_table[c] is the distance from the last occurrence of c to
292 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
293 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
294 for (i = 0; i < 1U << CHAR_BIT; i++)
295 shift_table[i] = needle_len;
296 for (i = 0; i < needle_len; i++)
297 shift_table[needle[i]] = needle_len - i - 1;
299 /* Perform the search. Each iteration compares the right half
301 if (memcmp (needle, needle + period, suffix) == 0)
303 /* Entire needle is periodic; a mismatch can only advance by the
304 period, so use memory to avoid rescanning known occurrences
308 while (!memchr (&haystack[haystack_len], '\0',
309 j + needle_len - haystack_len)
310 && (haystack_len = j + needle_len))
312 /* Check the last byte first; if it does not match, then
313 shift to the next possible match location. */
314 size_t shift = shift_table[haystack[j + needle_len - 1]];
317 if (memory && shift < period)
319 /* Since needle is periodic, but the last period has
320 a byte out of place, there can be no match until
321 after the mismatch. */
322 shift = needle_len - period;
328 /* Scan for matches in right half. The last byte has
329 already been matched, by virtue of the shift table. */
330 i = MAX (suffix, memory);
331 while (i < needle_len - 1 && needle[i] == haystack[i + j])
333 if (needle_len - 1 <= i)
335 /* Scan for matches in left half. */
337 while (memory < i + 1 && needle[i] == haystack[i + j])
339 if (i + 1 < memory + 1)
340 return (char *) (haystack + j);
341 /* No match, so remember how many repetitions of period
342 on the right half were scanned. */
344 memory = needle_len - period;
355 /* The two halves of needle are distinct; no extra memory is
356 required, and any mismatch results in a maximal shift. */
357 period = MAX (suffix, needle_len - suffix) + 1;
359 while (!memchr (&haystack[haystack_len], '\0',
360 j + needle_len - haystack_len)
361 && (haystack_len = j + needle_len))
363 /* Check the last byte first; if it does not match, then
364 shift to the next possible match location. */
365 size_t shift = shift_table[haystack[j + needle_len - 1]];
371 /* Scan for matches in right half. The last byte has
372 already been matched, by virtue of the shift table. */
374 while (i < needle_len - 1 && needle[i] == haystack[i + j])
376 if (needle_len - 1 <= i)
378 /* Scan for matches in left half. */
380 while (i != SIZE_MAX && needle[i] == haystack[i + j])
383 return (char *) (haystack + j);
393 /* Return the first occurrence of NEEDLE in HAYSTACK. Return HAYSTACK
394 if NEEDLE is empty, otherwise NULL if NEEDLE is not found in
397 strstr (const char *haystack_start, const char *needle_start)
399 const char *haystack = haystack_start;
400 const char *needle = needle_start;
401 size_t needle_len; /* Length of NEEDLE. */
402 size_t haystack_len; /* Known minimum length of HAYSTACK. */
403 bool ok = true; /* True if NEEDLE is prefix of HAYSTACK. */
405 /* Determine length of NEEDLE, and in the process, make sure
406 HAYSTACK is at least as long (no point processing all of a long
407 NEEDLE if HAYSTACK is too short). */
408 while (*haystack && *needle)
409 ok &= *haystack++ == *needle++;
413 return (char *) haystack_start;
415 /* Reduce the size of haystack using strchr, since it has a smaller
416 linear coefficient than the Two-Way algorithm. */
417 needle_len = needle - needle_start;
418 haystack = strchr (haystack_start + 1, *needle_start);
419 if (!haystack || __builtin_expect (needle_len == 1, 0))
420 return (char *) haystack;
421 needle -= needle_len;
422 haystack_len = (haystack > haystack_start + needle_len ? 1
423 : needle_len + haystack_start - haystack);
425 /* Perform the search. Abstract memory is considered to be an array
426 of 'unsigned char' values, not an array of 'char' values. See
427 ISO C 99 section 6.2.6.1. */
428 if (needle_len < LONG_NEEDLE_THRESHOLD)
429 return two_way_short_needle ((const unsigned char *) haystack,
431 (const unsigned char *) needle, needle_len);
432 return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
433 (const unsigned char *) needle, needle_len);
436 #undef LONG_NEEDLE_THRESHOLD