1 /*
2 * Copyright (C) 2004, 2007-2023 Free Software Foundation, Inc.
3 * Written by Bruno Haible and Eric Blake
4 *
5 * This program is free software: you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation, either version 3 of the License, or
8 * (at your option) any later version.
9 *
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #include <config.h>
19
20 #include <string.h>
21
22 #include "signature.h"
23 SIGNATURE_CHECK (memmem, void *, (void const *, size_t, void const *, size_t));
24
25 #include <signal.h>
26 #include <stdlib.h>
27 #include <unistd.h>
28
29 #include "zerosize-ptr.h"
30 #include "macros.h"
31
32 int
33 main (int argc, char *argv[])
34 {
35 #if HAVE_DECL_ALARM
36 /* Declare failure if test takes too long, by using default abort
37 caused by SIGALRM. All known platforms that lack alarm also lack
38 memmem, and the replacement memmem is known to not take too
39 long. */
40 int alarm_value = 100;
41 signal (SIGALRM, SIG_DFL);
42 alarm (alarm_value);
43 #endif
44
45 {
46 const char input[] = "foo";
47 const char *result = memmem (input, strlen (input), "", 0);
48 ASSERT (result == input);
49 }
50
51 {
52 const char input[] = "foo";
53 const char *result = memmem (input, strlen (input), "o", 1);
54 ASSERT (result == input + 1);
55 }
56
57 {
58 const char input[] = "ABC ABCDAB ABCDABCDABDE";
59 const char *result = memmem (input, strlen (input), "ABCDABD", 7);
60 ASSERT (result == input + 15);
61 }
62
63 {
64 const char input[] = "ABC ABCDAB ABCDABCDABDE";
65 const char *result = memmem (input, strlen (input), "ABCDABE", 7);
66 ASSERT (result == NULL);
67 }
68
69 {
70 const char input[] = "ABC ABCDAB ABCDABCDABDE";
71 const char *result = memmem (input, strlen (input), "ABCDABCD", 8);
72 ASSERT (result == input + 11);
73 }
74
75 /* Check that length 0 does not dereference the pointer. */
76 void *page_boundary = zerosize_ptr ();
77 if (page_boundary)
78 {
79 {
80 const char *result = memmem (page_boundary, 0, "foo", 3);
81 ASSERT (result == NULL);
82 }
83
84 {
85 const char input[] = "foo";
86 const char *result = memmem (input, strlen (input), page_boundary, 0);
87 ASSERT (result == input);
88 }
89 }
90
91 /* Check that a long periodic needle does not cause false positives. */
92 {
93 const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
94 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
95 "_C3_A7_20_EF_BF_BD";
96 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
97 const char *result = memmem (input, strlen (input), need, strlen (need));
98 ASSERT (result == NULL);
99 }
100 {
101 const char input[] = "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD"
102 "_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD"
103 "_C3_A7_20_EF_BF_BD_DA_B5_C2_A6_20"
104 "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
105 const char need[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
106 const char *result = memmem (input, strlen (input), need, strlen (need));
107 ASSERT (result == input + 115);
108 }
109
110 /* Check that a very long haystack is handled quickly if the needle is
111 short and occurs near the beginning. */
112 {
113 size_t repeat = 10000;
114 size_t m = 1000000;
115 const char *needle =
116 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
117 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA";
118 size_t n = strlen (needle);
119 char *haystack = (char *) malloc (m + 1);
120 if (haystack != NULL)
121 {
122 memset (haystack, 'A', m);
123 haystack[0] = 'B';
124
125 for (; repeat > 0; repeat--)
126 {
127 ASSERT (memmem (haystack, m, needle, n) == haystack + 1);
128 }
129
130 free (haystack);
131 }
132 }
133
134 /* Check that a very long needle is discarded quickly if the haystack is
135 short. */
136 {
137 size_t repeat = 10000;
138 size_t m = 1000000;
139 const char *haystack =
140 "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"
141 "ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB";
142 size_t n = strlen (haystack);
143 char *needle = (char *) malloc (m + 1);
144 if (needle != NULL)
145 {
146 memset (needle, 'A', m);
147
148 for (; repeat > 0; repeat--)
149 {
150 ASSERT (memmem (haystack, n, needle, m) == NULL);
151 }
152
153 free (needle);
154 }
155 }
156
157 /* Check that the asymptotic worst-case complexity is not quadratic. */
158 {
159 size_t m = 1000000;
160 char *haystack = (char *) malloc (2 * m + 1);
161 char *needle = (char *) malloc (m + 1);
162 if (haystack != NULL && needle != NULL)
163 {
164 const char *result;
165
166 memset (haystack, 'A', 2 * m);
167 haystack[2 * m] = 'B';
168
169 memset (needle, 'A', m);
170 needle[m] = 'B';
171
172 result = memmem (haystack, 2 * m + 1, needle, m + 1);
173 ASSERT (result == haystack + m);
174 }
175 free (needle);
176 free (haystack);
177 }
178
179 /* Check that long needles not present in a haystack can be handled
180 with sublinear speed. */
181 {
182 size_t repeat = 10000;
183 size_t m = 1000000;
184 size_t n = 1000;
185 char *haystack = (char *) malloc (m);
186 char *needle = (char *) malloc (n);
187 if (haystack != NULL && needle != NULL)
188 {
189 const char *result;
190
191 memset (haystack, 'A', m);
192 memset (needle, 'B', n);
193
194 for (; repeat > 0; repeat--)
195 {
196 result = memmem (haystack, m, needle, n);
197 ASSERT (result == NULL);
198 }
199 }
200 free (haystack);
201 free (needle);
202 }
203
204 {
205 /* Ensure that with a barely periodic "short" needle, memmem's
206 search does not mistakenly skip just past the match point.
207 This use of memmem would mistakenly return NULL before
208 gnulib v0.0-4927. */
209 const char *haystack =
210 "\n"
211 "with_build_libsubdir\n"
212 "with_local_prefix\n"
213 "with_gxx_include_dir\n"
214 "with_cpp_install_dir\n"
215 "enable_generated_files_in_srcdir\n"
216 "with_gnu_ld\n"
217 "with_ld\n"
218 "with_demangler_in_ld\n"
219 "with_gnu_as\n"
220 "with_as\n"
221 "enable_largefile\n"
222 "enable_werror_always\n"
223 "enable_checking\n"
224 "enable_coverage\n"
225 "enable_gather_detailed_mem_stats\n"
226 "enable_build_with_cxx\n"
227 "with_stabs\n"
228 "enable_multilib\n"
229 "enable___cxa_atexit\n"
230 "enable_decimal_float\n"
231 "enable_fixed_point\n"
232 "enable_threads\n"
233 "enable_tls\n"
234 "enable_objc_gc\n"
235 "with_dwarf2\n"
236 "enable_shared\n"
237 "with_build_sysroot\n"
238 "with_sysroot\n"
239 "with_specs\n"
240 "with_pkgversion\n"
241 "with_bugurl\n"
242 "enable_languages\n"
243 "with_multilib_list\n";
244 const char *needle = "\n"
245 "with_gnu_ld\n";
246 const char* p = memmem (haystack, strlen (haystack),
247 needle, strlen (needle));
248 ASSERT (p - haystack == 114);
249 }
250
251 {
252 /* Same bug, shorter trigger. */
253 const char *haystack = "..wi.d.";
254 const char *needle = ".d.";
255 const char* p = memmem (haystack, strlen (haystack),
256 needle, strlen (needle));
257 ASSERT (p - haystack == 4);
258 }
259
260 {
261 /* Like the above, but trigger the flaw in two_way_long_needle
262 by using a needle of length LONG_NEEDLE_THRESHOLD (32) or greater.
263 Rather than trying to find the right alignment manually, I've
264 arbitrarily chosen the following needle and template for the
265 haystack, and ensure that for each placement of the needle in
266 that haystack, memmem finds it. */
267 const char *needle = "\nwith_gnu_ld-extend-to-len-32-b\n";
268 const char *h =
269 "\n"
270 "with_build_libsubdir\n"
271 "with_local_prefix\n"
272 "with_gxx_include_dir\n"
273 "with_cpp_install_dir\n"
274 "with_e_\n"
275 "..............................\n"
276 "with_FGHIJKLMNOPQRSTUVWXYZ\n"
277 "with_567890123456789\n"
278 "with_multilib_list\n";
279 size_t h_len = strlen (h);
280 char *haystack = malloc (h_len + 1);
281 size_t i;
282 ASSERT (haystack);
283 for (i = 0; i < h_len - strlen (needle); i++)
284 {
285 const char *p;
286 memcpy (haystack, h, h_len + 1);
287 memcpy (haystack + i, needle, strlen (needle) + 1);
288 p = memmem (haystack, strlen (haystack), needle, strlen (needle));
289 ASSERT (p);
290 ASSERT (p - haystack == i);
291 }
292 free (haystack);
293 }
294
295 /* Test case from Yves Bastide.
296 <https://www.openwall.com/lists/musl/2014/04/18/2> */
297 {
298 const char input[] = "playing play play play always";
299 const char *result = memmem (input, strlen (input), "play play play", 14);
300 ASSERT (result == input + 8);
301 }
302
303 /* Test long needles. */
304 {
305 size_t m = 1024;
306 char *haystack = (char *) malloc (2 * m + 1);
307 char *needle = (char *) malloc (m + 1);
308 if (haystack != NULL && needle != NULL)
309 {
310 const char *p;
311 haystack[0] = 'x';
312 memset (haystack + 1, ' ', m - 1);
313 memset (haystack + m, 'x', m);
314 haystack[2 * m] = '\0';
315 memset (needle, 'x', m);
316 needle[m] = '\0';
317 p = memmem (haystack, strlen (haystack), needle, strlen (needle));
318 ASSERT (p);
319 ASSERT (p - haystack == m);
320 }
321 free (needle);
322 free (haystack);
323 }
324
325 return 0;
326 }