1/* Copyright (C) 1994, 1999 Free Software Foundation, Inc.
2This file is part of the GNU C Library.
3
4This program is free software; you can redistribute it and/or modify
5it under the terms of the GNU General Public License as published by
6the Free Software Foundation; either version 2, or (at your option)
7any later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License
15along with this program; if not, write to the Free Software
16Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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#if HAVE_CONFIG_H
28# include <config.h>
29#endif
30
31#if defined _LIBC || defined HAVE_STRING_H
32# include <string.h>
33#endif
34#include <sys/types.h>
35
36typedef unsigned chartype;
37
38#undef strstr
39
40char *
41strstr (const char *phaystack, const char *pneedle)
42{
43  register const unsigned char *haystack, *needle;
44  register chartype b, c;
45
46  haystack = (const unsigned char *) phaystack;
47  needle = (const unsigned char *) pneedle;
48
49  b = *needle;
50  if (b != '\0')
51    {
52      haystack--;				/* possible ANSI violation */
53      do
54	{
55	  c = *++haystack;
56	  if (c == '\0')
57	    goto ret0;
58	}
59      while (c != b);
60
61      c = *++needle;
62      if (c == '\0')
63	goto foundneedle;
64      ++needle;
65      goto jin;
66
67      for (;;)
68        {
69          register chartype a;
70	  register const unsigned char *rhaystack, *rneedle;
71
72	  do
73	    {
74	      a = *++haystack;
75	      if (a == '\0')
76		goto ret0;
77	      if (a == b)
78		break;
79	      a = *++haystack;
80	      if (a == '\0')
81		goto ret0;
82shloop:;    }
83          while (a != b);
84
85jin:	  a = *++haystack;
86	  if (a == '\0')
87	    goto ret0;
88
89	  if (a != c)
90	    goto shloop;
91
92	  rhaystack = haystack-- + 1;
93	  rneedle = needle;
94	  a = *rneedle;
95
96	  if (*rhaystack == a)
97	    do
98	      {
99		if (a == '\0')
100		  goto foundneedle;
101		++rhaystack;
102		a = *++needle;
103		if (*rhaystack != a)
104		  break;
105		if (a == '\0')
106		  goto foundneedle;
107		++rhaystack;
108		a = *++needle;
109	      }
110	    while (*rhaystack == a);
111
112	  needle = rneedle;		   /* took the register-poor approach */
113
114	  if (a == '\0')
115	    break;
116        }
117    }
118foundneedle:
119  return (char*) haystack;
120ret0:
121  return 0;
122}
123