[BZ #9895]
[glibc.git] / string / str-two-way.h
blob87ed8a03668ce113db7d364dba3e96d69b516de9
1 /* Byte-wise substring search, using the Two-Way algorithm.
2 Copyright (C) 2008 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Written by Eric Blake <ebb9@byu.net>, 2008.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library 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 GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19 02111-1307 USA. */
21 /* Before including this file, you need to include <string.h> (and
22 <config.h> before that, if not part of libc), and define:
23 RESULT_TYPE A macro that expands to the return type.
24 AVAILABLE(h, h_l, j, n_l)
25 A macro that returns nonzero if there are
26 at least N_L bytes left starting at H[J].
27 H is 'unsigned char *', H_L, J, and N_L
28 are 'size_t'; H_L is an lvalue. For
29 NUL-terminated searches, H_L can be
30 modified each iteration to avoid having
31 to compute the end of H up front.
33 For case-insensitivity, you may optionally define:
34 CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L
35 characters of P1 and P2 are equal.
36 CANON_ELEMENT(c) A macro that canonicalizes an element right after
37 it has been fetched from one of the two strings.
38 The argument is an 'unsigned char'; the result
39 must be an 'unsigned char' as well.
41 This file undefines the macros documented above, and defines
42 LONG_NEEDLE_THRESHOLD.
45 #include <limits.h>
46 #include <stdint.h>
48 /* We use the Two-Way string matching algorithm, which guarantees
49 linear complexity with constant space. Additionally, for long
50 needles, we also use a bad character shift table similar to the
51 Boyer-Moore algorithm to achieve improved (potentially sub-linear)
52 performance.
54 See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260
55 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm
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
71 #ifndef MAX
72 # define MAX(a, b) ((a < b) ? (b) : (a))
73 #endif
75 #ifndef CANON_ELEMENT
76 # define CANON_ELEMENT(c) c
77 #endif
78 #ifndef CMP_FUNC
79 # define CMP_FUNC memcmp
80 #endif
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
94 than NEEDLE_LEN.
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.
100 Given an ordered alphabet, a critical factorization can be computed
101 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
102 larger of two ordered maximal suffixes. The ordered maximal
103 suffixes are determined by lexicographic comparison of
104 periodicity. */
105 static size_t
106 critical_factorization (const unsigned char *needle, size_t needle_len,
107 size_t *period)
109 /* Index of last byte of left half, or SIZE_MAX. */
110 size_t max_suffix, max_suffix_rev;
111 size_t j; /* Index into NEEDLE for current candidate suffix. */
112 size_t k; /* Offset into current period. */
113 size_t p; /* Intermediate period. */
114 unsigned char a, b; /* Current comparison bytes. */
116 /* Invariants:
117 0 <= j < NEEDLE_LEN - 1
118 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
119 min(max_suffix, max_suffix_rev) < global period of NEEDLE
120 1 <= p <= global period of NEEDLE
121 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
122 1 <= k <= p
125 /* Perform lexicographic search. */
126 max_suffix = SIZE_MAX;
127 j = 0;
128 k = p = 1;
129 while (j + k < needle_len)
131 a = CANON_ELEMENT (needle[j + k]);
132 b = CANON_ELEMENT (needle[max_suffix + k]);
133 if (a < b)
135 /* Suffix is smaller, period is entire prefix so far. */
136 j += k;
137 k = 1;
138 p = j - max_suffix;
140 else if (a == b)
142 /* Advance through repetition of the current period. */
143 if (k != p)
144 ++k;
145 else
147 j += p;
148 k = 1;
151 else /* b < a */
153 /* Suffix is larger, start over from current location. */
154 max_suffix = j++;
155 k = p = 1;
158 *period = p;
160 /* Perform reverse lexicographic search. */
161 max_suffix_rev = SIZE_MAX;
162 j = 0;
163 k = p = 1;
164 while (j + k < needle_len)
166 a = CANON_ELEMENT (needle[j + k]);
167 b = CANON_ELEMENT (needle[max_suffix_rev + k]);
168 if (b < a)
170 /* Suffix is smaller, period is entire prefix so far. */
171 j += k;
172 k = 1;
173 p = j - max_suffix_rev;
175 else if (a == b)
177 /* Advance through repetition of the current period. */
178 if (k != p)
179 ++k;
180 else
182 j += p;
183 k = 1;
186 else /* a < b */
188 /* Suffix is larger, start over from current location. */
189 max_suffix_rev = j++;
190 k = p = 1;
194 /* Choose the longer suffix. Return the first byte of the right
195 half, rather than the last byte of the left half. */
196 if (max_suffix_rev + 1 < max_suffix + 1)
197 return max_suffix + 1;
198 *period = p;
199 return max_suffix_rev + 1;
202 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
203 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
204 method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
205 Performance is guaranteed to be linear, with an initialization cost
206 of 2 * NEEDLE_LEN comparisons.
208 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
209 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
210 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
211 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
212 static RETURN_TYPE
213 two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
214 const unsigned char *needle, size_t needle_len)
216 size_t i; /* Index into current byte of NEEDLE. */
217 size_t j; /* Index into current window of HAYSTACK. */
218 size_t period; /* The period of the right half of needle. */
219 size_t suffix; /* The index of the right half of needle. */
221 /* Factor the needle into two halves, such that the left half is
222 smaller than the global period, and the right half is
223 periodic (with a period as large as NEEDLE_LEN - suffix). */
224 suffix = critical_factorization (needle, needle_len, &period);
226 /* Perform the search. Each iteration compares the right half
227 first. */
228 if (CMP_FUNC (needle, needle + period, suffix) == 0)
230 /* Entire needle is periodic; a mismatch can only advance by the
231 period, so use memory to avoid rescanning known occurrences
232 of the period. */
233 size_t memory = 0;
234 j = 0;
235 while (AVAILABLE (haystack, haystack_len, j, needle_len))
237 /* Scan for matches in right half. */
238 i = MAX (suffix, memory);
239 while (i < needle_len && (CANON_ELEMENT (needle[i])
240 == CANON_ELEMENT (haystack[i + j])))
241 ++i;
242 if (needle_len <= i)
244 /* Scan for matches in left half. */
245 i = suffix - 1;
246 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
247 == CANON_ELEMENT (haystack[i + j])))
248 --i;
249 if (i + 1 < memory + 1)
250 return (RETURN_TYPE) (haystack + j);
251 /* No match, so remember how many repetitions of period
252 on the right half were scanned. */
253 j += period;
254 memory = needle_len - period;
256 else
258 j += i - suffix + 1;
259 memory = 0;
263 else
265 /* The two halves of needle are distinct; no extra memory is
266 required, and any mismatch results in a maximal shift. */
267 period = MAX (suffix, needle_len - suffix) + 1;
268 j = 0;
269 while (AVAILABLE (haystack, haystack_len, j, needle_len))
271 /* Scan for matches in right half. */
272 i = suffix;
273 while (i < needle_len && (CANON_ELEMENT (needle[i])
274 == CANON_ELEMENT (haystack[i + j])))
275 ++i;
276 if (needle_len <= i)
278 /* Scan for matches in left half. */
279 i = suffix - 1;
280 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
281 == CANON_ELEMENT (haystack[i + j])))
282 --i;
283 if (i == SIZE_MAX)
284 return (RETURN_TYPE) (haystack + j);
285 j += period;
287 else
288 j += i - suffix + 1;
291 return NULL;
294 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
295 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
296 method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
297 Performance is guaranteed to be linear, with an initialization cost
298 of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
300 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
301 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
302 and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
303 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
304 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
305 sublinear performance is not possible. */
306 static RETURN_TYPE
307 two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
308 const unsigned char *needle, size_t needle_len)
310 size_t i; /* Index into current byte of NEEDLE. */
311 size_t j; /* Index into current window of HAYSTACK. */
312 size_t period; /* The period of the right half of needle. */
313 size_t suffix; /* The index of the right half of needle. */
314 size_t shift_table[1U << CHAR_BIT]; /* See below. */
316 /* Factor the needle into two halves, such that the left half is
317 smaller than the global period, and the right half is
318 periodic (with a period as large as NEEDLE_LEN - suffix). */
319 suffix = critical_factorization (needle, needle_len, &period);
321 /* Populate shift_table. For each possible byte value c,
322 shift_table[c] is the distance from the last occurrence of c to
323 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
324 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
325 for (i = 0; i < 1U << CHAR_BIT; i++)
326 shift_table[i] = needle_len;
327 for (i = 0; i < needle_len; i++)
328 shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
330 /* Perform the search. Each iteration compares the right half
331 first. */
332 if (CMP_FUNC (needle, needle + period, suffix) == 0)
334 /* Entire needle is periodic; a mismatch can only advance by the
335 period, so use memory to avoid rescanning known occurrences
336 of the period. */
337 size_t memory = 0;
338 size_t shift;
339 j = 0;
340 while (AVAILABLE (haystack, haystack_len, j, needle_len))
342 /* Check the last byte first; if it does not match, then
343 shift to the next possible match location. */
344 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
345 if (0 < shift)
347 if (memory && shift < period)
349 /* Since needle is periodic, but the last period has
350 a byte out of place, there can be no match until
351 after the mismatch. */
352 shift = needle_len - period;
353 memory = 0;
355 j += shift;
356 continue;
358 /* Scan for matches in right half. The last byte has
359 already been matched, by virtue of the shift table. */
360 i = MAX (suffix, memory);
361 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
362 == CANON_ELEMENT (haystack[i + j])))
363 ++i;
364 if (needle_len - 1 <= i)
366 /* Scan for matches in left half. */
367 i = suffix - 1;
368 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
369 == CANON_ELEMENT (haystack[i + j])))
370 --i;
371 if (i + 1 < memory + 1)
372 return (RETURN_TYPE) (haystack + j);
373 /* No match, so remember how many repetitions of period
374 on the right half were scanned. */
375 j += period;
376 memory = needle_len - period;
378 else
380 j += i - suffix + 1;
381 memory = 0;
385 else
387 /* The two halves of needle are distinct; no extra memory is
388 required, and any mismatch results in a maximal shift. */
389 size_t shift;
390 period = MAX (suffix, needle_len - suffix) + 1;
391 j = 0;
392 while (AVAILABLE (haystack, haystack_len, j, needle_len))
394 /* Check the last byte first; if it does not match, then
395 shift to the next possible match location. */
396 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
397 if (0 < shift)
399 j += shift;
400 continue;
402 /* Scan for matches in right half. The last byte has
403 already been matched, by virtue of the shift table. */
404 i = suffix;
405 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
406 == CANON_ELEMENT (haystack[i + j])))
407 ++i;
408 if (needle_len - 1 <= i)
410 /* Scan for matches in left half. */
411 i = suffix - 1;
412 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
413 == CANON_ELEMENT (haystack[i + j])))
414 --i;
415 if (i == SIZE_MAX)
416 return (RETURN_TYPE) (haystack + j);
417 j += period;
419 else
420 j += i - suffix + 1;
423 return NULL;
426 #undef AVAILABLE
427 #undef CANON_ELEMENT
428 #undef CMP_FUNC
429 #undef MAX
430 #undef RETURN_TYPE