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. 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 430