1 /* Byte-wise substring search, using the Two-Way algorithm.
2 Copyright (C) 2008, 2009 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
70 #define MAX(a, b) ((a < b) ? (b) : (a))
73 # define CANON_ELEMENT(c) c
76 # define CMP_FUNC memcmp
79 /* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN.
80 Return the index of the first byte in the right half, and set
81 *PERIOD to the global period of the right half.
83 The global period of a string is the smallest index (possibly its
84 length) at which all remaining bytes in the string are repetitions
85 of the prefix (the last repetition may be a subset of the prefix).
87 When NEEDLE is factored into two halves, a local period is the
88 length of the smallest word that shares a suffix with the left half
89 and shares a prefix with the right half. All factorizations of a
90 non-empty NEEDLE have a local period of at least 1 and no greater
93 A critical factorization has the property that the local period
94 equals the global period. All strings have at least one critical
95 factorization with the left half smaller than the global period.
97 Given an ordered alphabet, a critical factorization can be computed
98 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the
99 larger of two ordered maximal suffixes. The ordered maximal
100 suffixes are determined by lexicographic comparison of
103 critical_factorization (const unsigned char *needle
, size_t needle_len
,
106 /* Index of last byte of left half, or SIZE_MAX. */
107 size_t max_suffix
, max_suffix_rev
;
108 size_t j
; /* Index into NEEDLE for current candidate suffix. */
109 size_t k
; /* Offset into current period. */
110 size_t p
; /* Intermediate period. */
111 unsigned char a
, b
; /* Current comparison bytes. */
114 0 <= j < NEEDLE_LEN - 1
115 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed)
116 min(max_suffix, max_suffix_rev) < global period of NEEDLE
117 1 <= p <= global period of NEEDLE
118 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j]
122 /* Perform lexicographic search. */
123 max_suffix
= SIZE_MAX
;
126 while (j
+ k
< needle_len
)
128 a
= CANON_ELEMENT (needle
[j
+ k
]);
129 b
= CANON_ELEMENT (needle
[max_suffix
+ k
]);
132 /* Suffix is smaller, period is entire prefix so far. */
139 /* Advance through repetition of the current period. */
150 /* Suffix is larger, start over from current location. */
157 /* Perform reverse lexicographic search. */
158 max_suffix_rev
= SIZE_MAX
;
161 while (j
+ k
< needle_len
)
163 a
= CANON_ELEMENT (needle
[j
+ k
]);
164 b
= CANON_ELEMENT (needle
[max_suffix_rev
+ k
]);
167 /* Suffix is smaller, period is entire prefix so far. */
170 p
= j
- max_suffix_rev
;
174 /* Advance through repetition of the current period. */
185 /* Suffix is larger, start over from current location. */
186 max_suffix_rev
= j
++;
191 /* Choose the longer suffix. Return the first byte of the right
192 half, rather than the last byte of the left half. */
193 if (max_suffix_rev
+ 1 < max_suffix
+ 1)
194 return max_suffix
+ 1;
196 return max_suffix_rev
+ 1;
199 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
200 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
201 method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD.
202 Performance is guaranteed to be linear, with an initialization cost
203 of 2 * NEEDLE_LEN comparisons.
205 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
206 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching.
207 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
208 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */
210 two_way_short_needle (const unsigned char *haystack
, size_t haystack_len
,
211 const unsigned char *needle
, size_t needle_len
)
213 size_t i
; /* Index into current byte of NEEDLE. */
214 size_t j
; /* Index into current window of HAYSTACK. */
215 size_t period
; /* The period of the right half of needle. */
216 size_t suffix
; /* The index of the right half of needle. */
218 /* Factor the needle into two halves, such that the left half is
219 smaller than the global period, and the right half is
220 periodic (with a period as large as NEEDLE_LEN - suffix). */
221 suffix
= critical_factorization (needle
, needle_len
, &period
);
223 /* Perform the search. Each iteration compares the right half
225 if (CMP_FUNC (needle
, needle
+ period
, suffix
) == 0)
227 /* Entire needle is periodic; a mismatch can only advance by the
228 period, so use memory to avoid rescanning known occurrences
232 while (AVAILABLE (haystack
, haystack_len
, j
, needle_len
))
234 /* Scan for matches in right half. */
235 i
= MAX (suffix
, memory
);
236 while (i
< needle_len
&& (CANON_ELEMENT (needle
[i
])
237 == CANON_ELEMENT (haystack
[i
+ j
])))
241 /* Scan for matches in left half. */
243 while (memory
< i
+ 1 && (CANON_ELEMENT (needle
[i
])
244 == CANON_ELEMENT (haystack
[i
+ j
])))
246 if (i
+ 1 < memory
+ 1)
247 return (RETURN_TYPE
) (haystack
+ j
);
248 /* No match, so remember how many repetitions of period
249 on the right half were scanned. */
251 memory
= needle_len
- period
;
262 /* The two halves of needle are distinct; no extra memory is
263 required, and any mismatch results in a maximal shift. */
264 period
= MAX (suffix
, needle_len
- suffix
) + 1;
266 while (AVAILABLE (haystack
, haystack_len
, j
, needle_len
))
268 /* Scan for matches in right half. */
270 while (i
< needle_len
&& (CANON_ELEMENT (needle
[i
])
271 == CANON_ELEMENT (haystack
[i
+ j
])))
275 /* Scan for matches in left half. */
277 while (i
!= SIZE_MAX
&& (CANON_ELEMENT (needle
[i
])
278 == CANON_ELEMENT (haystack
[i
+ j
])))
281 return (RETURN_TYPE
) (haystack
+ j
);
291 /* Return the first location of non-empty NEEDLE within HAYSTACK, or
292 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This
293 method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN.
294 Performance is guaranteed to be linear, with an initialization cost
295 of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations.
297 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at
298 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching,
299 and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible.
300 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 *
301 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and
302 sublinear performance is not possible. */
304 two_way_long_needle (const unsigned char *haystack
, size_t haystack_len
,
305 const unsigned char *needle
, size_t needle_len
)
307 size_t i
; /* Index into current byte of NEEDLE. */
308 size_t j
; /* Index into current window of HAYSTACK. */
309 size_t period
; /* The period of the right half of needle. */
310 size_t suffix
; /* The index of the right half of needle. */
311 size_t shift_table
[1U << CHAR_BIT
]; /* See below. */
313 /* Factor the needle into two halves, such that the left half is
314 smaller than the global period, and the right half is
315 periodic (with a period as large as NEEDLE_LEN - suffix). */
316 suffix
= critical_factorization (needle
, needle_len
, &period
);
318 /* Populate shift_table. For each possible byte value c,
319 shift_table[c] is the distance from the last occurrence of c to
320 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE.
321 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */
322 for (i
= 0; i
< 1U << CHAR_BIT
; i
++)
323 shift_table
[i
] = needle_len
;
324 for (i
= 0; i
< needle_len
; i
++)
325 shift_table
[CANON_ELEMENT (needle
[i
])] = needle_len
- i
- 1;
327 /* Perform the search. Each iteration compares the right half
329 if (CMP_FUNC (needle
, needle
+ period
, suffix
) == 0)
331 /* Entire needle is periodic; a mismatch can only advance by the
332 period, so use memory to avoid rescanning known occurrences
337 while (AVAILABLE (haystack
, haystack_len
, j
, needle_len
))
339 /* Check the last byte first; if it does not match, then
340 shift to the next possible match location. */
341 shift
= shift_table
[CANON_ELEMENT (haystack
[j
+ needle_len
- 1])];
344 if (memory
&& shift
< period
)
346 /* Since needle is periodic, but the last period has
347 a byte out of place, there can be no match until
348 after the mismatch. */
349 shift
= needle_len
- period
;
355 /* Scan for matches in right half. The last byte has
356 already been matched, by virtue of the shift table. */
357 i
= MAX (suffix
, memory
);
358 while (i
< needle_len
- 1 && (CANON_ELEMENT (needle
[i
])
359 == CANON_ELEMENT (haystack
[i
+ j
])))
361 if (needle_len
- 1 <= i
)
363 /* Scan for matches in left half. */
365 while (memory
< i
+ 1 && (CANON_ELEMENT (needle
[i
])
366 == CANON_ELEMENT (haystack
[i
+ j
])))
368 if (i
+ 1 < memory
+ 1)
369 return (RETURN_TYPE
) (haystack
+ j
);
370 /* No match, so remember how many repetitions of period
371 on the right half were scanned. */
373 memory
= needle_len
- period
;
384 /* The two halves of needle are distinct; no extra memory is
385 required, and any mismatch results in a maximal shift. */
387 period
= MAX (suffix
, needle_len
- suffix
) + 1;
389 while (AVAILABLE (haystack
, haystack_len
, j
, needle_len
))
391 /* Check the last byte first; if it does not match, then
392 shift to the next possible match location. */
393 shift
= shift_table
[CANON_ELEMENT (haystack
[j
+ needle_len
- 1])];
399 /* Scan for matches in right half. The last byte has
400 already been matched, by virtue of the shift table. */
402 while (i
< needle_len
- 1 && (CANON_ELEMENT (needle
[i
])
403 == CANON_ELEMENT (haystack
[i
+ j
])))
405 if (needle_len
- 1 <= i
)
407 /* Scan for matches in left half. */
409 while (i
!= SIZE_MAX
&& (CANON_ELEMENT (needle
[i
])
410 == CANON_ELEMENT (haystack
[i
+ j
])))
413 return (RETURN_TYPE
) (haystack
+ j
);
This page took 0.065273 seconds and 4 git commands to generate.