1 // SPDX-License-Identifier: BSD-3-Clause
2 /*
3  * Copyright (c) 1994-2009  Red Hat, Inc.
4  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright notice,
10  * this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright notice,
13  * this list of conditions and the following disclaimer in the documentation
14  * and/or other materials provided with the distribution.
15  *
16  * 3. Neither the name of the copyright holder nor the names of its
17  * contributors may be used to endorse or promote products derived from this
18  * software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
24  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30  * POSSIBILITY OF SUCH DAMAGE.
31  */
32 
33 /*
34 FUNCTION
35 	<<strstr>>---find string segment
36 
37 INDEX
38 	strstr
39 
40 ANSI_SYNOPSIS
41 	#include <string.h>
42 	char *strstr(const char *<[s1]>, const char *<[s2]>);
43 
44 TRAD_SYNOPSIS
45 	#include <string.h>
46 	char *strstr(<[s1]>, <[s2]>)
47 	char *<[s1]>;
48 	char *<[s2]>;
49 
50 DESCRIPTION
51 	Locates the first occurrence in the string pointed to by <[s1]> of
52 	the sequence of characters in the string pointed to by <[s2]>
53 	(excluding the terminating null character).
54 
55 RETURNS
56 	Returns a pointer to the located string segment, or a null
57 	pointer if the string <[s2]> is not found. If <[s2]> points to
58 	a string with zero length, <[s1]> is returned.
59 
60 PORTABILITY
61 <<strstr>> is ANSI C.
62 
63 <<strstr>> requires no supporting OS subroutines.
64 
65 QUICKREF
66 	strstr ansi pure
67 */
68 
69 #include "_ansi.h"
70 #include <string.h>
71 
72 #if !defined(PREFER_SIZE_OVER_SPEED) && !defined(__OPTIMIZE_SIZE__)
73 # define RETURN_TYPE char *
74 # define AVAILABLE(h, h_l, j, n_l)			\
75   (!memchr ((h) + (h_l), '\0', (j) + (n_l) - (h_l))	\
76    && ((h_l) = (j) + (n_l)))
77 # include "str-two-way.h"
78 #endif
79 
80 char *
81 _DEFUN (strstr, (searchee, lookfor),
82 	_CONST char *searchee _AND
83 	_CONST char *lookfor)
84 {
85 #if defined(PREFER_SIZE_OVER_SPEED) || defined(__OPTIMIZE_SIZE__)
86 
87   /* Less code size, but quadratic performance in the worst case.  */
88   if (*searchee == 0)
89     {
90       if (*lookfor)
91 	return (char *) NULL;
92       return (char *) searchee;
93     }
94 
95   while (*searchee)
96     {
97       size_t i;
98       i = 0;
99 
100       while (1)
101 	{
102 	  if (lookfor[i] == 0)
103 	    {
104 	      return (char *) searchee;
105 	    }
106 
107 	  if (lookfor[i] != searchee[i])
108 	    {
109 	      break;
110 	    }
111 	  i++;
112 	}
113       searchee++;
114     }
115 
116   return (char *) NULL;
117 
118 #else /* compilation for speed */
119 
120   /* Larger code size, but guaranteed linear performance.  */
121   const char *haystack = searchee;
122   const char *needle = lookfor;
123   size_t needle_len; /* Length of NEEDLE.  */
124   size_t haystack_len; /* Known minimum length of HAYSTACK.  */
125   int ok = 1; /* True if NEEDLE is prefix of HAYSTACK.  */
126 
127   /* Determine length of NEEDLE, and in the process, make sure
128      HAYSTACK is at least as long (no point processing all of a long
129      NEEDLE if HAYSTACK is too short).  */
130   while (*haystack && *needle)
131     ok &= *haystack++ == *needle++;
132   if (*needle)
133     return NULL;
134   if (ok)
135     return (char *) searchee;
136 
137   /* Reduce the size of haystack using strchr, since it has a smaller
138      linear coefficient than the Two-Way algorithm.  */
139   needle_len = needle - lookfor;
140   haystack = strchr (searchee + 1, *lookfor);
141   if (!haystack || needle_len == 1)
142     return (char *) haystack;
143   haystack_len = (haystack > searchee + needle_len ? 1
144 		  : needle_len + searchee - haystack);
145 
146   /* Perform the search.  */
147   if (needle_len < LONG_NEEDLE_THRESHOLD)
148     return two_way_short_needle ((const unsigned char *) haystack,
149 				 haystack_len,
150 				 (const unsigned char *) lookfor, needle_len);
151   return two_way_long_needle ((const unsigned char *) haystack, haystack_len,
152 			      (const unsigned char *) lookfor, needle_len);
153 #endif /* compilation for speed */
154 }
155