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