summaryrefslogtreecommitdiffstats
path: root/gl/str-two-way.h
diff options
context:
space:
mode:
Diffstat (limited to 'gl/str-two-way.h')
-rw-r--r--gl/str-two-way.h429
1 files changed, 429 insertions, 0 deletions
diff --git a/gl/str-two-way.h b/gl/str-two-way.h
new file mode 100644
index 0000000..c08f60e
--- /dev/null
+++ b/gl/str-two-way.h
@@ -0,0 +1,429 @@
1/* Byte-wise substring search, using the Two-Way algorithm.
2 Copyright (C) 2008, 2009, 2010 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, 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)
51 performance.
52
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
55*/
56
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. */
64#if CHAR_BIT < 10
65# define LONG_NEEDLE_THRESHOLD 32U
66#else
67# define LONG_NEEDLE_THRESHOLD SIZE_MAX
68#endif
69
70#ifndef MAX
71# define MAX(a, b) ((a < b) ? (b) : (a))
72#endif
73
74#ifndef CANON_ELEMENT
75# define CANON_ELEMENT(c) c
76#endif
77#ifndef CMP_FUNC
78# define CMP_FUNC memcmp
79#endif
80
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.
84
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).
88
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
93 than NEEDLE_LEN.
94
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
99 Given an ordered alphabet, a critical factorization can be computed
100 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
101 larger of two ordered maximal suffixes. The ordered maximal
102 suffixes are determined by lexicographic comparison of
103 periodicity. */
104static size_t
105critical_factorization (const unsigned char *needle, size_t needle_len,
106 size_t *period)
107{
108 /* Index of last byte of left half, or SIZE_MAX. */
109 size_t max_suffix, max_suffix_rev;
110 size_t j; /* Index into NEEDLE for current candidate suffix. */
111 size_t k; /* Offset into current period. */
112 size_t p; /* Intermediate period. */
113 unsigned char a, b; /* Current comparison bytes. */
114
115 /* Invariants:
116 0 <= j < NEEDLE_LEN - 1
117 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
118 min(max_suffix, max_suffix_rev) < global period of NEEDLE
119 1 <= p <= global period of NEEDLE
120 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
121 1 <= k <= p
122 */
123
124 /* Perform lexicographic search. */
125 max_suffix = SIZE_MAX;
126 j = 0;
127 k = p = 1;
128 while (j + k < needle_len)
129 {
130 a = CANON_ELEMENT (needle[j + k]);
131 b = CANON_ELEMENT (needle[max_suffix + k]);
132 if (a < b)
133 {
134 /* Suffix is smaller, period is entire prefix so far. */
135 j += k;
136 k = 1;
137 p = j - max_suffix;
138 }
139 else if (a == b)
140 {
141 /* Advance through repetition of the current period. */
142 if (k != p)
143 ++k;
144 else
145 {
146 j += p;
147 k = 1;
148 }
149 }
150 else /* b < a */
151 {
152 /* Suffix is larger, start over from current location. */
153 max_suffix = j++;
154 k = p = 1;
155 }
156 }
157 *period = p;
158
159 /* Perform reverse lexicographic search. */
160 max_suffix_rev = SIZE_MAX;
161 j = 0;
162 k = p = 1;
163 while (j + k < needle_len)
164 {
165 a = CANON_ELEMENT (needle[j + k]);
166 b = CANON_ELEMENT (needle[max_suffix_rev + k]);
167 if (b < a)
168 {
169 /* Suffix is smaller, period is entire prefix so far. */
170 j += k;
171 k = 1;
172 p = j - max_suffix_rev;
173 }
174 else if (a == b)
175 {
176 /* Advance through repetition of the current period. */
177 if (k != p)
178 ++k;
179 else
180 {
181 j += p;
182 k = 1;
183 }
184 }
185 else /* a < b */
186 {
187 /* Suffix is larger, start over from current location. */
188 max_suffix_rev = j++;
189 k = p = 1;
190 }
191 }
192
193 /* Choose the longer suffix. Return the first byte of the right
194 half, rather than the last byte of the left half. */
195 if (max_suffix_rev + 1 < max_suffix + 1)
196 return max_suffix + 1;
197 *period = p;
198 return max_suffix_rev + 1;
199}
200
201/* Return the first location of non-empty NEEDLE within HAYSTACK, or
202 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
203 method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
204 Performance is guaranteed to be linear, with an initialization cost
205 of 2 * NEEDLE_LEN comparisons.
206
207 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
208 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
209 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
210 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
211static RETURN_TYPE
212two_way_short_needle (const unsigned char *haystack, size_t haystack_len,
213 const unsigned char *needle, size_t needle_len)
214{
215 size_t i; /* Index into current byte of NEEDLE. */
216 size_t j; /* Index into current window of HAYSTACK. */
217 size_t period; /* The period of the right half of needle. */
218 size_t suffix; /* The index of the right half of needle. */
219
220 /* Factor the needle into two halves, such that the left half is
221 smaller than the global period, and the right half is
222 periodic (with a period as large as NEEDLE_LEN - suffix). */
223 suffix = critical_factorization (needle, needle_len, &period);
224
225 /* Perform the search. Each iteration compares the right half
226 first. */
227 if (CMP_FUNC (needle, needle + period, suffix) == 0)
228 {
229 /* Entire needle is periodic; a mismatch can only advance by the
230 period, so use memory to avoid rescanning known occurrences
231 of the period. */
232 size_t memory = 0;
233 j = 0;
234 while (AVAILABLE (haystack, haystack_len, j, needle_len))
235 {
236 /* Scan for matches in right half. */
237 i = MAX (suffix, memory);
238 while (i < needle_len && (CANON_ELEMENT (needle[i])
239 == CANON_ELEMENT (haystack[i + j])))
240 ++i;
241 if (needle_len <= i)
242 {
243 /* Scan for matches in left half. */
244 i = suffix - 1;
245 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
246 == CANON_ELEMENT (haystack[i + j])))
247 --i;
248 if (i + 1 < memory + 1)
249 return (RETURN_TYPE) (haystack + j);
250 /* No match, so remember how many repetitions of period
251 on the right half were scanned. */
252 j += period;
253 memory = needle_len - period;
254 }
255 else
256 {
257 j += i - suffix + 1;
258 memory = 0;
259 }
260 }
261 }
262 else
263 {
264 /* The two halves of needle are distinct; no extra memory is
265 required, and any mismatch results in a maximal shift. */
266 period = MAX (suffix, needle_len - suffix) + 1;
267 j = 0;
268 while (AVAILABLE (haystack, haystack_len, j, needle_len))
269 {
270 /* Scan for matches in right half. */
271 i = suffix;
272 while (i < needle_len && (CANON_ELEMENT (needle[i])
273 == CANON_ELEMENT (haystack[i + j])))
274 ++i;
275 if (needle_len <= i)
276 {
277 /* Scan for matches in left half. */
278 i = suffix - 1;
279 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
280 == CANON_ELEMENT (haystack[i + j])))
281 --i;
282 if (i == SIZE_MAX)
283 return (RETURN_TYPE) (haystack + j);
284 j += period;
285 }
286 else
287 j += i - suffix + 1;
288 }
289 }
290 return NULL;
291}
292
293/* Return the first location of non-empty NEEDLE within HAYSTACK, or
294 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
295 method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
296 Performance is guaranteed to be linear, with an initialization cost
297 of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
298
299 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
300 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
301 and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
302 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
303 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
304 sublinear performance is not possible. */
305static RETURN_TYPE
306two_way_long_needle (const unsigned char *haystack, size_t haystack_len,
307 const unsigned char *needle, size_t needle_len)
308{
309 size_t i; /* Index into current byte of NEEDLE. */
310 size_t j; /* Index into current window of HAYSTACK. */
311 size_t period; /* The period of the right half of needle. */
312 size_t suffix; /* The index of the right half of needle. */
313 size_t shift_table[1U << CHAR_BIT]; /* See below. */
314
315 /* Factor the needle into two halves, such that the left half is
316 smaller than the global period, and the right half is
317 periodic (with a period as large as NEEDLE_LEN - suffix). */
318 suffix = critical_factorization (needle, needle_len, &period);
319
320 /* Populate shift_table. For each possible byte value c,
321 shift_table[c] is the distance from the last occurrence of c to
322 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
323 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
324 for (i = 0; i < 1U << CHAR_BIT; i++)
325 shift_table[i] = needle_len;
326 for (i = 0; i < needle_len; i++)
327 shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1;
328
329 /* Perform the search. Each iteration compares the right half
330 first. */
331 if (CMP_FUNC (needle, needle + period, suffix) == 0)
332 {
333 /* Entire needle is periodic; a mismatch can only advance by the
334 period, so use memory to avoid rescanning known occurrences
335 of the period. */
336 size_t memory = 0;
337 size_t shift;
338 j = 0;
339 while (AVAILABLE (haystack, haystack_len, j, needle_len))
340 {
341 /* Check the last byte first; if it does not match, then
342 shift to the next possible match location. */
343 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
344 if (0 < shift)
345 {
346 if (memory && shift < period)
347 {
348 /* Since needle is periodic, but the last period has
349 a byte out of place, there can be no match until
350 after the mismatch. */
351 shift = needle_len - period;
352 memory = 0;
353 }
354 j += shift;
355 continue;
356 }
357 /* Scan for matches in right half. The last byte has
358 already been matched, by virtue of the shift table. */
359 i = MAX (suffix, memory);
360 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
361 == CANON_ELEMENT (haystack[i + j])))
362 ++i;
363 if (needle_len - 1 <= i)
364 {
365 /* Scan for matches in left half. */
366 i = suffix - 1;
367 while (memory < i + 1 && (CANON_ELEMENT (needle[i])
368 == CANON_ELEMENT (haystack[i + j])))
369 --i;
370 if (i + 1 < memory + 1)
371 return (RETURN_TYPE) (haystack + j);
372 /* No match, so remember how many repetitions of period
373 on the right half were scanned. */
374 j += period;
375 memory = needle_len - period;
376 }
377 else
378 {
379 j += i - suffix + 1;
380 memory = 0;
381 }
382 }
383 }
384 else
385 {
386 /* The two halves of needle are distinct; no extra memory is
387 required, and any mismatch results in a maximal shift. */
388 size_t shift;
389 period = MAX (suffix, needle_len - suffix) + 1;
390 j = 0;
391 while (AVAILABLE (haystack, haystack_len, j, needle_len))
392 {
393 /* Check the last byte first; if it does not match, then
394 shift to the next possible match location. */
395 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])];
396 if (0 < shift)
397 {
398 j += shift;
399 continue;
400 }
401 /* Scan for matches in right half. The last byte has
402 already been matched, by virtue of the shift table. */
403 i = suffix;
404 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i])
405 == CANON_ELEMENT (haystack[i + j])))
406 ++i;
407 if (needle_len - 1 <= i)
408 {
409 /* Scan for matches in left half. */
410 i = suffix - 1;
411 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i])
412 == CANON_ELEMENT (haystack[i + j])))
413 --i;
414 if (i == SIZE_MAX)
415 return (RETURN_TYPE) (haystack + j);
416 j += period;
417 }
418 else
419 j += i - suffix + 1;
420 }
421 }
422 return NULL;
423}
424
425#undef AVAILABLE
426#undef CANON_ELEMENT
427#undef CMP_FUNC
428#undef MAX
429#undef RETURN_TYPE