1 /* strstr - find a substring within a string */
2
3 /* Copyright (C) 1994, 1999 Free Software Foundation, Inc.
4
5 This file is part of GNU Bash, the Bourne Again SHell.
6
7 Bash is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 Bash is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Bash. If not, see <http://www.gnu.org/licenses/>.
19 */
20
21 /*
22 * My personal strstr() implementation that beats most other algorithms.
23 * Until someone tells me otherwise, I assume that this is the
24 * fastest implementation of strstr() in C.
25 * I deliberately chose not to comment it. You should have at least
26 * as much fun trying to understand it, as I had to write it :-).
27 *
28 * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */
29
30 #if HAVE_CONFIG_H
31 # include <config.h>
32 #endif
33
34 #if defined _LIBC || defined HAVE_STRING_H
35 # include <string.h>
36 #endif
37 #include <sys/types.h>
38
39 typedef unsigned chartype;
40
41 #undef strstr
42
43 char *
strstr(const char * phaystack,const char * pneedle)44 strstr (const char *phaystack, const char *pneedle)
45 {
46 register const unsigned char *haystack, *needle;
47 register chartype b, c;
48
49 haystack = (const unsigned char *) phaystack;
50 needle = (const unsigned char *) pneedle;
51
52 b = *needle;
53 if (b != '\0')
54 {
55 haystack--; /* possible ANSI violation */
56 do
57 {
58 c = *++haystack;
59 if (c == '\0')
60 goto ret0;
61 }
62 while (c != b);
63
64 c = *++needle;
65 if (c == '\0')
66 goto foundneedle;
67 ++needle;
68 goto jin;
69
70 for (;;)
71 {
72 register chartype a;
73 register const unsigned char *rhaystack, *rneedle;
74
75 do
76 {
77 a = *++haystack;
78 if (a == '\0')
79 goto ret0;
80 if (a == b)
81 break;
82 a = *++haystack;
83 if (a == '\0')
84 goto ret0;
85 shloop:; }
86 while (a != b);
87
88 jin: a = *++haystack;
89 if (a == '\0')
90 goto ret0;
91
92 if (a != c)
93 goto shloop;
94
95 rhaystack = haystack-- + 1;
96 rneedle = needle;
97 a = *rneedle;
98
99 if (*rhaystack == a)
100 do
101 {
102 if (a == '\0')
103 goto foundneedle;
104 ++rhaystack;
105 a = *++needle;
106 if (*rhaystack != a)
107 break;
108 if (a == '\0')
109 goto foundneedle;
110 ++rhaystack;
111 a = *++needle;
112 }
113 while (*rhaystack == a);
114
115 needle = rneedle; /* took the register-poor approach */
116
117 if (a == '\0')
118 break;
119 }
120 }
121 foundneedle:
122 return (char*) haystack;
123 ret0:
124 return 0;
125 }
126