1/* -*- buffer-read-only: t -*- vi: set ro: */ 2/* DO NOT EDIT! GENERATED AUTOMATICALLY! */ 3#line 1 4/* Byte-wise substring search, using the Two-Way algorithm. 5 Copyright (C) 2008, 2009, 2010 Free Software Foundation, Inc. 6 This file is part of the GNU C Library. 7 Written by Eric Blake <ebb9@byu.net>, 2008. 8 9 This program is free software; you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation; either version 3, or (at your option) 12 any later version. 13 14 This program is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License along 20 with this program; if not, write to the Free Software Foundation, 21 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 22 23/* Before including this file, you need to include <config.h> and 24 <string.h>, and define: 25 RESULT_TYPE A macro that expands to the return type. 26 AVAILABLE(h, h_l, j, n_l) 27 A macro that returns nonzero if there are 28 at least N_L bytes left starting at H[J]. 29 H is 'unsigned char *', H_L, J, and N_L 30 are 'size_t'; H_L is an lvalue. For 31 NUL-terminated searches, H_L can be 32 modified each iteration to avoid having 33 to compute the end of H up front. 34 35 For case-insensitivity, you may optionally define: 36 CMP_FUNC(p1, p2, l) A macro that returns 0 iff the first L 37 characters of P1 and P2 are equal. 38 CANON_ELEMENT(c) A macro that canonicalizes an element right after 39 it has been fetched from one of the two strings. 40 The argument is an 'unsigned char'; the result 41 must be an 'unsigned char' as well. 42 43 This file undefines the macros documented above, and defines 44 LONG_NEEDLE_THRESHOLD. 45*/ 46 47#include <limits.h> 48#include <stdint.h> 49 50/* We use the Two-Way string matching algorithm, which guarantees 51 linear complexity with constant space. Additionally, for long 52 needles, we also use a bad character shift table similar to the 53 Boyer-Moore algorithm to achieve improved (potentially sub-linear) 54 performance. 55 56 See http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 57 and http://en.wikipedia.org/wiki/Boyer-Moore_string_search_algorithm 58*/ 59 60/* Point at which computing a bad-byte shift table is likely to be 61 worthwhile. Small needles should not compute a table, since it 62 adds (1 << CHAR_BIT) + NEEDLE_LEN computations of preparation for a 63 speedup no greater than a factor of NEEDLE_LEN. The larger the 64 needle, the better the potential performance gain. On the other 65 hand, on non-POSIX systems with CHAR_BIT larger than eight, the 66 memory required for the table is prohibitive. */ 67#if CHAR_BIT < 10 68# define LONG_NEEDLE_THRESHOLD 32U 69#else 70# define LONG_NEEDLE_THRESHOLD SIZE_MAX 71#endif 72 73#ifndef MAX 74# define MAX(a, b) ((a < b) ? (b) : (a)) 75#endif 76 77#ifndef CANON_ELEMENT 78# define CANON_ELEMENT(c) c 79#endif 80#ifndef CMP_FUNC 81# define CMP_FUNC memcmp 82#endif 83 84/* Perform a critical factorization of NEEDLE, of length NEEDLE_LEN. 85 Return the index of the first byte in the right half, and set 86 *PERIOD to the global period of the right half. 87 88 The global period of a string is the smallest index (possibly its 89 length) at which all remaining bytes in the string are repetitions 90 of the prefix (the last repetition may be a subset of the prefix). 91 92 When NEEDLE is factored into two halves, a local period is the 93 length of the smallest word that shares a suffix with the left half 94 and shares a prefix with the right half. All factorizations of a 95 non-empty NEEDLE have a local period of at least 1 and no greater 96 than NEEDLE_LEN. 97 98 A critical factorization has the property that the local period 99 equals the global period. All strings have at least one critical 100 factorization with the left half smaller than the global period. 101 102 Given an ordered alphabet, a critical factorization can be computed 103 in linear time, with 2 * NEEDLE_LEN comparisons, by computing the 104 larger of two ordered maximal suffixes. The ordered maximal 105 suffixes are determined by lexicographic comparison of 106 periodicity. */ 107static size_t 108critical_factorization (const unsigned char *needle, size_t needle_len, 109 size_t *period) 110{ 111 /* Index of last byte of left half, or SIZE_MAX. */ 112 size_t max_suffix, max_suffix_rev; 113 size_t j; /* Index into NEEDLE for current candidate suffix. */ 114 size_t k; /* Offset into current period. */ 115 size_t p; /* Intermediate period. */ 116 unsigned char a, b; /* Current comparison bytes. */ 117 118 /* Invariants: 119 0 <= j < NEEDLE_LEN - 1 120 -1 <= max_suffix{,_rev} < j (treating SIZE_MAX as if it were signed) 121 min(max_suffix, max_suffix_rev) < global period of NEEDLE 122 1 <= p <= global period of NEEDLE 123 p == global period of the substring NEEDLE[max_suffix{,_rev}+1...j] 124 1 <= k <= p 125 */ 126 127 /* Perform lexicographic search. */ 128 max_suffix = SIZE_MAX; 129 j = 0; 130 k = p = 1; 131 while (j + k < needle_len) 132 { 133 a = CANON_ELEMENT (needle[j + k]); 134 b = CANON_ELEMENT (needle[max_suffix + k]); 135 if (a < b) 136 { 137 /* Suffix is smaller, period is entire prefix so far. */ 138 j += k; 139 k = 1; 140 p = j - max_suffix; 141 } 142 else if (a == b) 143 { 144 /* Advance through repetition of the current period. */ 145 if (k != p) 146 ++k; 147 else 148 { 149 j += p; 150 k = 1; 151 } 152 } 153 else /* b < a */ 154 { 155 /* Suffix is larger, start over from current location. */ 156 max_suffix = j++; 157 k = p = 1; 158 } 159 } 160 *period = p; 161 162 /* Perform reverse lexicographic search. */ 163 max_suffix_rev = SIZE_MAX; 164 j = 0; 165 k = p = 1; 166 while (j + k < needle_len) 167 { 168 a = CANON_ELEMENT (needle[j + k]); 169 b = CANON_ELEMENT (needle[max_suffix_rev + k]); 170 if (b < a) 171 { 172 /* Suffix is smaller, period is entire prefix so far. */ 173 j += k; 174 k = 1; 175 p = j - max_suffix_rev; 176 } 177 else if (a == b) 178 { 179 /* Advance through repetition of the current period. */ 180 if (k != p) 181 ++k; 182 else 183 { 184 j += p; 185 k = 1; 186 } 187 } 188 else /* a < b */ 189 { 190 /* Suffix is larger, start over from current location. */ 191 max_suffix_rev = j++; 192 k = p = 1; 193 } 194 } 195 196 /* Choose the longer suffix. Return the first byte of the right 197 half, rather than the last byte of the left half. */ 198 if (max_suffix_rev + 1 < max_suffix + 1) 199 return max_suffix + 1; 200 *period = p; 201 return max_suffix_rev + 1; 202} 203 204/* Return the first location of non-empty NEEDLE within HAYSTACK, or 205 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This 206 method is optimized for NEEDLE_LEN < LONG_NEEDLE_THRESHOLD. 207 Performance is guaranteed to be linear, with an initialization cost 208 of 2 * NEEDLE_LEN comparisons. 209 210 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at 211 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. 212 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 * 213 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching. */ 214static RETURN_TYPE 215two_way_short_needle (const unsigned char *haystack, size_t haystack_len, 216 const unsigned char *needle, size_t needle_len) 217{ 218 size_t i; /* Index into current byte of NEEDLE. */ 219 size_t j; /* Index into current window of HAYSTACK. */ 220 size_t period; /* The period of the right half of needle. */ 221 size_t suffix; /* The index of the right half of needle. */ 222 223 /* Factor the needle into two halves, such that the left half is 224 smaller than the global period, and the right half is 225 periodic (with a period as large as NEEDLE_LEN - suffix). */ 226 suffix = critical_factorization (needle, needle_len, &period); 227 228 /* Perform the search. Each iteration compares the right half 229 first. */ 230 if (CMP_FUNC (needle, needle + period, suffix) == 0) 231 { 232 /* Entire needle is periodic; a mismatch can only advance by the 233 period, so use memory to avoid rescanning known occurrences 234 of the period. */ 235 size_t memory = 0; 236 j = 0; 237 while (AVAILABLE (haystack, haystack_len, j, needle_len)) 238 { 239 /* Scan for matches in right half. */ 240 i = MAX (suffix, memory); 241 while (i < needle_len && (CANON_ELEMENT (needle[i]) 242 == CANON_ELEMENT (haystack[i + j]))) 243 ++i; 244 if (needle_len <= i) 245 { 246 /* Scan for matches in left half. */ 247 i = suffix - 1; 248 while (memory < i + 1 && (CANON_ELEMENT (needle[i]) 249 == CANON_ELEMENT (haystack[i + j]))) 250 --i; 251 if (i + 1 < memory + 1) 252 return (RETURN_TYPE) (haystack + j); 253 /* No match, so remember how many repetitions of period 254 on the right half were scanned. */ 255 j += period; 256 memory = needle_len - period; 257 } 258 else 259 { 260 j += i - suffix + 1; 261 memory = 0; 262 } 263 } 264 } 265 else 266 { 267 /* The two halves of needle are distinct; no extra memory is 268 required, and any mismatch results in a maximal shift. */ 269 period = MAX (suffix, needle_len - suffix) + 1; 270 j = 0; 271 while (AVAILABLE (haystack, haystack_len, j, needle_len)) 272 { 273 /* Scan for matches in right half. */ 274 i = suffix; 275 while (i < needle_len && (CANON_ELEMENT (needle[i]) 276 == CANON_ELEMENT (haystack[i + j]))) 277 ++i; 278 if (needle_len <= i) 279 { 280 /* Scan for matches in left half. */ 281 i = suffix - 1; 282 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i]) 283 == CANON_ELEMENT (haystack[i + j]))) 284 --i; 285 if (i == SIZE_MAX) 286 return (RETURN_TYPE) (haystack + j); 287 j += period; 288 } 289 else 290 j += i - suffix + 1; 291 } 292 } 293 return NULL; 294} 295 296/* Return the first location of non-empty NEEDLE within HAYSTACK, or 297 NULL. HAYSTACK_LEN is the minimum known length of HAYSTACK. This 298 method is optimized for LONG_NEEDLE_THRESHOLD <= NEEDLE_LEN. 299 Performance is guaranteed to be linear, with an initialization cost 300 of 3 * NEEDLE_LEN + (1 << CHAR_BIT) operations. 301 302 If AVAILABLE does not modify HAYSTACK_LEN (as in memmem), then at 303 most 2 * HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, 304 and sublinear performance O(HAYSTACK_LEN / NEEDLE_LEN) is possible. 305 If AVAILABLE modifies HAYSTACK_LEN (as in strstr), then at most 3 * 306 HAYSTACK_LEN - NEEDLE_LEN comparisons occur in searching, and 307 sublinear performance is not possible. */ 308static RETURN_TYPE 309two_way_long_needle (const unsigned char *haystack, size_t haystack_len, 310 const unsigned char *needle, size_t needle_len) 311{ 312 size_t i; /* Index into current byte of NEEDLE. */ 313 size_t j; /* Index into current window of HAYSTACK. */ 314 size_t period; /* The period of the right half of needle. */ 315 size_t suffix; /* The index of the right half of needle. */ 316 size_t shift_table[1U << CHAR_BIT]; /* See below. */ 317 318 /* Factor the needle into two halves, such that the left half is 319 smaller than the global period, and the right half is 320 periodic (with a period as large as NEEDLE_LEN - suffix). */ 321 suffix = critical_factorization (needle, needle_len, &period); 322 323 /* Populate shift_table. For each possible byte value c, 324 shift_table[c] is the distance from the last occurrence of c to 325 the end of NEEDLE, or NEEDLE_LEN if c is absent from the NEEDLE. 326 shift_table[NEEDLE[NEEDLE_LEN - 1]] contains the only 0. */ 327 for (i = 0; i < 1U << CHAR_BIT; i++) 328 shift_table[i] = needle_len; 329 for (i = 0; i < needle_len; i++) 330 shift_table[CANON_ELEMENT (needle[i])] = needle_len - i - 1; 331 332 /* Perform the search. Each iteration compares the right half 333 first. */ 334 if (CMP_FUNC (needle, needle + period, suffix) == 0) 335 { 336 /* Entire needle is periodic; a mismatch can only advance by the 337 period, so use memory to avoid rescanning known occurrences 338 of the period. */ 339 size_t memory = 0; 340 size_t shift; 341 j = 0; 342 while (AVAILABLE (haystack, haystack_len, j, needle_len)) 343 { 344 /* Check the last byte first; if it does not match, then 345 shift to the next possible match location. */ 346 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; 347 if (0 < shift) 348 { 349 if (memory && shift < period) 350 { 351 /* Since needle is periodic, but the last period has 352 a byte out of place, there can be no match until 353 after the mismatch. */ 354 shift = needle_len - period; 355 memory = 0; 356 } 357 j += shift; 358 continue; 359 } 360 /* Scan for matches in right half. The last byte has 361 already been matched, by virtue of the shift table. */ 362 i = MAX (suffix, memory); 363 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) 364 == CANON_ELEMENT (haystack[i + j]))) 365 ++i; 366 if (needle_len - 1 <= i) 367 { 368 /* Scan for matches in left half. */ 369 i = suffix - 1; 370 while (memory < i + 1 && (CANON_ELEMENT (needle[i]) 371 == CANON_ELEMENT (haystack[i + j]))) 372 --i; 373 if (i + 1 < memory + 1) 374 return (RETURN_TYPE) (haystack + j); 375 /* No match, so remember how many repetitions of period 376 on the right half were scanned. */ 377 j += period; 378 memory = needle_len - period; 379 } 380 else 381 { 382 j += i - suffix + 1; 383 memory = 0; 384 } 385 } 386 } 387 else 388 { 389 /* The two halves of needle are distinct; no extra memory is 390 required, and any mismatch results in a maximal shift. */ 391 size_t shift; 392 period = MAX (suffix, needle_len - suffix) + 1; 393 j = 0; 394 while (AVAILABLE (haystack, haystack_len, j, needle_len)) 395 { 396 /* Check the last byte first; if it does not match, then 397 shift to the next possible match location. */ 398 shift = shift_table[CANON_ELEMENT (haystack[j + needle_len - 1])]; 399 if (0 < shift) 400 { 401 j += shift; 402 continue; 403 } 404 /* Scan for matches in right half. The last byte has 405 already been matched, by virtue of the shift table. */ 406 i = suffix; 407 while (i < needle_len - 1 && (CANON_ELEMENT (needle[i]) 408 == CANON_ELEMENT (haystack[i + j]))) 409 ++i; 410 if (needle_len - 1 <= i) 411 { 412 /* Scan for matches in left half. */ 413 i = suffix - 1; 414 while (i != SIZE_MAX && (CANON_ELEMENT (needle[i]) 415 == CANON_ELEMENT (haystack[i + j]))) 416 --i; 417 if (i == SIZE_MAX) 418 return (RETURN_TYPE) (haystack + j); 419 j += period; 420 } 421 else 422 j += i - suffix + 1; 423 } 424 } 425 return NULL; 426} 427 428#undef AVAILABLE 429#undef CANON_ELEMENT 430#undef CMP_FUNC 431#undef MAX 432#undef RETURN_TYPE 433