1 /* Byte-wise substring search, using the Two-Way algorithm.
2 Copyright (C) 2008-2012 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Eric Blake <ebb9@byu.net>, 2008.
5
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)
9 any later version.
10
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.
15
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. */
19
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.
31
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.
39
40 This file undefines the macros documented above, and defines
41 LONG_NEEDLE_THRESHOLD.
42 */
43
44 #include <limits.h>
45 #include <stdint.h>
46
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.
52
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
56 */
57
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. */
65 #if CHAR_BIT < 10
66 # define LONG_NEEDLE_THRESHOLD 32U
67 #else
68 # define LONG_NEEDLE_THRESHOLD SIZE_MAX
69 #endif
70
71 #ifndef MAX
72 # define MAX(a, b) ((a < b) ? (b) : (a))
73 #endif
74
75 #ifndef CANON_ELEMENT
76 # define CANON_ELEMENT(c) c
77 #endif
78 #ifndef CMP_FUNC
79 # define CMP_FUNC memcmp
80 #endif
81
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.
85
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).
89
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
94 than NEEDLE_LEN.
95
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.
102
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
107 periodicity. */
108 static size_t
critical_factorization(const unsigned char * needle,size_t needle_len,size_t * period)109 critical_factorization (const unsigned char *needle, size_t needle_len,
110 size_t *period)
111 {
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. */
118
119 /* Special case NEEDLE_LEN of 1 or 2 (all callers already filtered
120 out 0-length needles. */
121 if (needle_len < 3)
122 {
123 *period = 1;
124 return needle_len - 1;
125 }
126
127 /* Invariants:
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]
133 1 <= k <= p
134 */
135
136 /* Perform lexicographic search. */
137 max_suffix = SIZE_MAX;
138 j = 0;
139 k = p = 1;
140 while (j + k < needle_len)
141 {
142 a = CANON_ELEMENT (needle[j + k]);
143 b = CANON_ELEMENT (needle[max_suffix + k]);
144 if (a < b)
145 {
146 /* Suffix is smaller, period is entire prefix so far. */
147 j += k;
148 k = 1;
149 p = j - max_suffix;
150 }
151 else if (a == b)
152 {
153 /* Advance through repetition of the current period. */
154 if (k != p)
155 ++k;
156 else
157 {
158 j += p;
159 k = 1;
160 }
161 }
162 else /* b < a */
163 {
164 /* Suffix is larger, start over from current location. */
165 max_suffix = j++;
166 k = p = 1;
167 }
168 }
169 *period = p;
170
171 /* Perform reverse lexicographic search. */
172 max_suffix_rev = SIZE_MAX;
173 j = 0;
174 k = p = 1;
175 while (j + k < needle_len)
176 {
177 a = CANON_ELEMENT (needle[j + k]);
178 b = CANON_ELEMENT (needle[max_suffix_rev + k]);
179 if (b < a)
180 {
181 /* Suffix is smaller, period is entire prefix so far. */
182 j += k;
183 k = 1;
184 p = j - max_suffix_rev;
185 }
186 else if (a == b)
187 {
188 /* Advance through repetition of the current period. */
189 if (k != p)
190 ++k;
191 else
192 {
193 j += p;
194 k = 1;
195 }
196 }
197 else /* a < b */
198 {
199 /* Suffix is larger, start over from current location. */
200 max_suffix_rev = j++;
201 k = p = 1;
202 }
203 }
204
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.
207
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
218 factorization. */
219 if (max_suffix_rev + 1 < max_suffix + 1)
220 return max_suffix + 1;
221 *period = p;
222 return max_suffix_rev + 1;
223 }
224
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.
230
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. */
235 static RETURN_TYPE
two_way_short_needle(const unsigned char * haystack,size_t haystack_len,const unsigned char * needle,size_t needle_len)236 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
237 const unsigned char *needle, size_t needle_len)
238 {
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. */
243
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);
248
249 /* Perform the search. Each iteration compares the right half
250 first. */
251 if (CMP_FUNC (needle, needle + period, suffix) == 0)
252 {
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. */
256 size_t memory = 0;
257 j = 0;
258 while (AVAILABLE (haystack, haystack_len, j, needle_len))
259 {
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])))
264 ++i;
265 if (needle_len <= i)
266 {
267 /* Scan for matches in left half. */
268 i = suffix - 1;
269 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
270 == CANON_ELEMENT (haystack[i + j])))
271 --i;
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. */
276 j += period;
277 memory = needle_len - period;
278 }
279 else
280 {
281 j += i - suffix + 1;
282 memory = 0;
283 }
284 }
285 }
286 else
287 {
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;
291 j = 0;
292 while (AVAILABLE (haystack, haystack_len, j, needle_len))
293 {
294 /* Scan for matches in right half. */
295 i = suffix;
296 while (i < needle_len && (CANON_ELEMENT (needle[i])
297 == CANON_ELEMENT (haystack[i + j])))
298 ++i;
299 if (needle_len <= i)
300 {
301 /* Scan for matches in left half. */
302 i = suffix - 1;
303 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
304 == CANON_ELEMENT (haystack[i + j])))
305 --i;
306 if (i == SIZE_MAX)
307 return (RETURN_TYPE) (haystack + j);
308 j += period;
309 }
310 else
311 j += i - suffix + 1;
312 }
313 }
314 return NULL;
315 }
316
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.
322
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. */
329 static RETURN_TYPE
two_way_long_needle(const unsigned char * haystack,size_t haystack_len,const unsigned char * needle,size_t needle_len)330 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
331 const unsigned char *needle, size_t needle_len)
332 {
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. */
338
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);
343
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;
352
353 /* Perform the search. Each iteration compares the right half
354 first. */
355 if (CMP_FUNC (needle, needle + period, suffix) == 0)
356 {
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. */
360 size_t memory = 0;
361 size_t shift;
362 j = 0;
363 while (AVAILABLE (haystack, haystack_len, j, needle_len))
364 {
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])];
368 if (0 < shift)
369 {
370 if (memory && shift < period)
371 {
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;
376 }
377 memory = 0;
378 j += shift;
379 continue;
380 }
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])))
386 ++i;
387 if (needle_len - 1 <= i)
388 {
389 /* Scan for matches in left half. */
390 i = suffix - 1;
391 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
392 == CANON_ELEMENT (haystack[i + j])))
393 --i;
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. */
398 j += period;
399 memory = needle_len - period;
400 }
401 else
402 {
403 j += i - suffix + 1;
404 memory = 0;
405 }
406 }
407 }
408 else
409 {
410 /* The two halves of needle are distinct; no extra memory is
411 required, and any mismatch results in a maximal shift. */
412 size_t shift;
413 period = MAX (suffix, needle_len - suffix) + 1;
414 j = 0;
415 while (AVAILABLE (haystack, haystack_len, j, needle_len))
416 {
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])];
420 if (0 < shift)
421 {
422 j += shift;
423 continue;
424 }
425 /* Scan for matches in right half. The last byte has
426 already been matched, by virtue of the shift table. */
427 i = suffix;
428 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
429 == CANON_ELEMENT (haystack[i + j])))
430 ++i;
431 if (needle_len - 1 <= i)
432 {
433 /* Scan for matches in left half. */
434 i = suffix - 1;
435 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
436 == CANON_ELEMENT (haystack[i + j])))
437 --i;
438 if (i == SIZE_MAX)
439 return (RETURN_TYPE) (haystack + j);
440 j += period;
441 }
442 else
443 j += i - suffix + 1;
444 }
445 }
446 return NULL;
447 }
448
449 #undef AVAILABLE
450 #undef CANON_ELEMENT
451 #undef CMP_FUNC
452 #undef MAX
453 #undef RETURN_TYPE
454